2026-07-21T12:28:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17567 2024-03-06T10:59:56Z ddc:004 open_access

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom Grewal, Sabee Iyer, Vishnu Kretschmer, William Liang, Daniel Pseudorandom quantum states Clifford + T Haar random Bell sampling stabilizer formalism stabilizer extent stabilizer fidelity learning theory complexity theory We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. Specifically, given an n-qubit pure state |ψ⟩, we give an efficient algorithm that distinguishes whether |ψ⟩ is (i) Haar-random or (ii) a state with stabilizer fidelity at least 1/k (i.e., has fidelity at least 1/k with some stabilizer state), promised that one of these is the case. With black-box access to |ψ⟩, our algorithm uses O(k^{12} log(1/δ)) copies of |ψ⟩ and O(n k^{12} log(1/δ)) time to succeed with probability at least 1-δ, and, with access to a state preparation unitary for |ψ⟩ (and its inverse), O(k³ log(1/δ)) queries and O(n k³ log(1/δ)) time suffice. As a corollary, we prove that ω(log(n)) T-gates are necessary for any Clifford+T circuit to prepare computationally pseudorandom quantum states, a first-of-its-kind lower bound. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sabee Grewal and Vishnu Iyer and William Kretschmer and Daniel Liang 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.64 urn:nbn:de:0030-drops-175670 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.64 eng https://creativecommons.org/licenses/by/4.0/legalcode