Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.64
URN: urn:nbn:de:0030-drops-175670
URL: https://drops.dagstuhl.de/opus/volltexte/2023/17567/
Grewal, Sabee ; Iyer, Vishnu ; Kretschmer, William ; Liang, Daniel
Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{grewal_et_al:LIPIcs.ITCS.2023.64,
author = {Grewal, Sabee and Iyer, Vishnu and Kretschmer, William and Liang, Daniel},
title = {{Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {64:1--64:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-263-1},
ISSN = {1868-8969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17567},
URN = {urn:nbn:de:0030-drops-175670},
doi = {10.4230/LIPIcs.ITCS.2023.64},
annote = {Keywords: Pseudorandom quantum states, Clifford + T, Haar random, Bell sampling, stabilizer formalism, stabilizer extent, stabilizer fidelity, learning theory, complexity theory}
}
| Keywords: | Pseudorandom quantum states, Clifford + T, Haar random, Bell sampling, stabilizer formalism, stabilizer extent, stabilizer fidelity, learning theory, complexity theory | |
| Seminar: | 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) | |
| Issue date: | 2023 | |
| Date of publication: | 01.02.2023 |
