Document Open Access Logo

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

Authors Sabee Grewal , Vishnu Iyer , William Kretschmer , Daniel Liang

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.64.pdf
  • Filesize: 0.81 MB
  • 20 pages

Document Identifiers

Author Details

Sabee Grewal
  • The University of Texas at Austin, TX, USA
Vishnu Iyer
  • The University of Texas at Austin, TX, USA
William Kretschmer
  • The University of Texas at Austin, TX, USA
Daniel Liang
  • The University of Texas at Austin, TX, USA

Funding

SG, VI, DL are supported by Scott Aaronson’s Vannevar Bush Fellowship from the US Department of Defense, the Berkeley NSF-QLCI CIQC Center, a Simons Investigator Award, and the Simons "It from Qubit" collaboration.
  • Kretschmer, William: Supported by an NDSEG Fellowship.

Acknowledgements

We thank Scott Aaronson for helpful comments.

Cite As Get BibTex

Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 64:1-64:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.64

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
Keywords
  • Pseudorandom quantum states
  • Clifford + T
  • Haar random
  • Bell sampling
  • stabilizer formalism
  • stabilizer extent
  • stabilizer fidelity
  • learning theory
  • complexity theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5), November 2004. URL: https://doi.org/10.1103/physreva.70.052328.
  2. Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. Optimal algorithms for learning quantum phase states, 2022. URL: https://doi.org/10.48550/arxiv.2208.07851.
  3. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-Testing/Correcting with Applications to Numerical Problems. J. Comput. Syst. Sci., 47(3):549-595, 1993. URL: https://doi.org/10.1016/0022-0000(93)90044-W.
  4. Zvika Brakerski and Omri Shmueli. (Pseudo) Random Quantum States with Binary Phase. In Theory of Cryptography, 2019. URL: https://doi.org/10.1007/978-3-030-36030-6_10.
  5. Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum Amplitude Amplification and Estimation, 2002. URL: https://doi.org/10.1090/conm/305/05215.
  6. Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard. Simulation of quantum circuits by low-rank stabilizer decompositions. Quantum, 3:181, September 2019. URL: https://doi.org/10.22331/q-2019-09-02-181.
  7. Sergey Bravyi and David Gosset. Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates. Phys. Rev. Lett., 116:250501, 2016. URL: https://doi.org/10.1103/PhysRevLett.116.250501.
  8. A. R. Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Phys. Rev. A, 54:1098-1105, 1996. URL: https://doi.org/10.1103/PhysRevA.54.1098.
  9. Zhiyuan Fan, Jiatu Li, and Tianqi Yang. The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 962-975, 2022. URL: https://doi.org/10.1145/3519935.3520010.
  10. Manuel Gerken. Measure concentration: Levy’s Lemma, 2013. Google Scholar
  11. Daniel Gottesman. Stabilizer Codes and Quantum Error Correction, 1997. URL: https://doi.org/10.48550/arxiv.quant-ph/9705052.
  12. Daniel Gottesman. The Heisenberg Representation of Quantum Computers, 1998. URL: https://doi.org/10.48550/arXiv.quant-ph/9807006.
  13. David Gross, Sepehr Nezami, and Michael Walter. Schur-Weyl duality for the Clifford group with applications: Property testing, a robust Hudson theorem, and de Finetti representations. Communications in Mathematical Physics, 385(3):1325-1393, 2021. URL: https://doi.org/10.1007/s00220-021-04118-7.
  14. Jonas Haferkamp, Felipe Montealegre-Mora, Markus Heinrich, Jens Eisert, David Gross, and Ingo Roth. Quantum homeopathy works: Efficient unitary designs with a system-size independent number of non-Clifford gates, 2020. URL: https://doi.org/10.48550/arxiv.2002.09524.
  15. Marcel Hinsche, Marios Ioannou, Alexander Nietner, Jonas Haferkamp, Yihui Quek, Dominik Hangleiter, Jean-Pierre Seifert, Jens Eisert, and Ryan Sweke. A single t-gate makes distribution learning hard, 2022. URL: https://doi.org/10.48550/arxiv.2207.03140.
  16. Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10):1050-1057, 2020. URL: https://doi.org/10.1038/s41567-020-0932-7.
  17. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Cryptography with Constant Computational Overhead. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, pages 433-442, 2008. URL: https://doi.org/10.1145/1374376.1374438.
  18. Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom Quantum States. In Advances in Cryptology - CRYPTO 2018. Springer International Publishing, 2018. URL: https://doi.org/10.1007/978-3-319-96878-0_5.
  19. E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland. Randomized benchmarking of quantum gates. Physical Review A, 77(1), 2008. URL: https://doi.org/10.1103/physreva.77.012307.
  20. Richard Kueng and David Gross. Qubit stabilizer states are complex projective 3-designs, 2015. URL: https://doi.org/10.48550/arXiv.1510.02767.
  21. Ching-Yi Lai and Hao-Chung Cheng. Learning Quantum Circuits of Some T Gates. IEEE Transactions on Information Theory, 68(6):3951-3964, 2022. URL: https://doi.org/10.1109/TIT.2022.3151760.
  22. Ashley Montanaro. Learning stabilizer states by Bell sampling. arXiv preprint arXiv:1707.04012, 2017. URL: https://doi.org/10.48550/arXiv.1707.04012.
  23. Michael A. Nielsen and Isaac Chuang. Quantum Computation and Quantum Information, 2002. URL: https://doi.org/10.1017/CBO9780511976667.
  24. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. URL: https://doi.org/10.1017/CBO9781139814782.
  25. Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett. Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities. Phys. Rev. Lett., 115:070501, 2015. URL: https://doi.org/10.1103/PhysRevLett.115.070501.
  26. Patrick Rall, Daniel Liang, Jeremy Cook, and William Kretschmer. Simulation of qubit quantum circuits via Pauli propagation. Phys. Rev. A, 99:062337, 2019. URL: https://doi.org/10.1103/PhysRevA.99.062337.
  27. Robert Raussendorf and Hans J. Briegel. Quantum computing via measurements only, 2000. URL: https://doi.org/10.48550/arxiv.quant-ph/0010033.
  28. Peter W. Shor. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A, 52:R2493-R2496, 1995. URL: https://doi.org/10.1103/PhysRevA.52.R2493.
  29. Zak Webb. The Clifford Group Forms a Unitary 3-Design. Quantum Info. Comput., 16(15–16):1379-1400, 2016. Google Scholar
  30. Huangjun Zhu, Richard Kueng, Markus Grassl, and David Gross. The Clifford group fails gracefully to be a unitary 4-design, 2016. URL: http://arxiv.org/abs/1609.08172.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact