Document Open Access Logo

Quantum Pseudorandomness and Classical Complexity

Author William Kretschmer

PDF
Thumbnail PDF

File

LIPIcs.TQC.2021.2.pdf
  • Filesize: 0.77 MB
  • 20 pages

Document Identifiers

Author Details

William Kretschmer
  • University of Texas at Austin, TX, USA

Funding

  • Kretschmer, William: Supported by a National Defense Science and Engineering Graduate (NDSEG) Fellowship from the US Department of Defense.

Acknowledgements

Thanks to Scott Aaronson for suggestions on the writing, Adam Bouland for insightful discussions, and Qipeng Liu for clarifying some questions about [Kai-Min Chung et al., 2020].

Cite AsGet BibTex

William Kretschmer. Quantum Pseudorandomness and Classical Complexity. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.TQC.2021.2

Abstract

We construct a quantum oracle relative to which BQP = QMA but cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist, a counterintuitive result in light of the fact that pseudorandom states can be "broken" by quantum Merlin-Arthur adversaries. We explain how this nuance arises as the result of a distinction between algorithms that operate on quantum and classical inputs. On the other hand, we show that some computational complexity assumption is needed to construct pseudorandom states, by proving that pseudorandom states do not exist if BQP = PP. We discuss implications of these results for cryptography, complexity theory, and quantum tomography.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
Keywords
  • pseudorandom quantum states
  • quantum Merlin-Arthur

Metrics

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

Related Versions

References

  1. Scott Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society A, 461:3473-3482, 2005. Google Scholar
  2. Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 325-338, New York, NY, USA, 2018. Association for Computing Machinery. Google Scholar
  3. Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Phys. Rev. A, 70:052328, November 2004. Google Scholar
  4. Scott Aaronson and Greg Kuperberg. Quantum versus classical proofs and advice. Theory of Computing, 3(7):129-157, 2007. Google Scholar
  5. Dorit Aharonov, Alexei Kitaev, and Noam Nisan. Quantum circuits with mixed states. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC '98, pages 20-30, New York, NY, USA, 1998. Association for Computing Machinery. Google Scholar
  6. Eric Allender. The Complexity of Complexity, pages 79-94. Springer International Publishing, Cham, 2017. Google Scholar
  7. Eric Allender. The new complexity landscape around circuit minimization. In Alberto Leporati, Carlos Martín-Vide, Dana Shapira, and Claudio Zandron, editors, Language and Automata Theory and Applications, pages 3-16, Cham, 2020. Springer International Publishing. Google Scholar
  8. Andris Ambainis and Joseph Emerson. Quantum t-designs: T-wise independence in the quantum world. In Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, CCC '07, pages 129-140, USA, 2007. IEEE Computer Society. Google Scholar
  9. Aleksandrs Belovs and Ansis Rosmanis. Tight quantum lower bound for approximate counting with quantum states, 2020. Google Scholar
  10. Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510-1523, 1997. Google Scholar
  11. James O. Berger. Statistical Decision Theory and Bayesian Analysis. Springer Series in Statistics. Springer New York, 2013. Google Scholar
  12. Adam Bouland, Bill Fefferman, and Umesh Vazirani. Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract). In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 63:1-63:2, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  13. Zvika Brakerski and Omri Shmueli. (Pseudo) random quantum states with binary phase. In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography, pages 229-250, Cham, 2019. Springer International Publishing. Google Scholar
  14. Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki. Efficient quantum pseudorandomness. Phys. Rev. Lett., 116:170502, April 2016. Google Scholar
  15. Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki. Local random quantum circuits are approximate polynomial-designs. Communications in Mathematical Physics, 346(2):397-434, 2016. Google Scholar
  16. Kai-Min Chung, Siyao Guo, Qipeng Liu, and Luowen Qian. Tight quantum time-space tradeoffs for function inversion. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 673-684, 2020. Google Scholar
  17. Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 2020. Google Scholar
  18. Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC '89, pages 44-61, New York, NY, USA, 1989. Association for Computing Machinery. Google Scholar
  19. Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018, pages 126-152, Cham, 2018. Springer International Publishing. Google Scholar
  20. Robert Koenig and John A. Smolin. How to efficiently select an arbitrary Clifford group element. Journal of Mathematical Physics, 55(12):122202, 2014. Google Scholar
  21. Greg Kuperberg. How hard is it to approximate the Jones polynomial? Theory of Computing, 11(6):183-219, 2015. Google Scholar
  22. Elizabeth S. Meckes. The Random Matrix Theory of the Classical Compact Groups. Cambridge Tracts in Mathematics. Cambridge University Press, 2019. Google Scholar
  23. Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 899-912, New York, NY, USA, 2016. Association for Computing Machinery. Google Scholar
  24. Leonard Susskind. Addendum to computational complexity and black hole horizons. Fortschritte der Physik, 64(1):44-48, 2016. Google Scholar
  25. Leonard Susskind. Computational complexity and black hole horizons. Fortschritte der Physik, 64(1):24-43, 2016. Google Scholar
  26. Juha J. Vartiainen, Mikko Möttönen, and Martti M. Salomaa. Efficient decomposition of quantum gates. Phys. Rev. Lett., 92:177902, April 2004. Google Scholar
  27. Yaakov S. Weinstein, Winton G. Brown, and Lorenza Viola. Parameters of pseudorandom quantum circuits. Phys. Rev. A, 78:052332, November 2008. Google Scholar
  28. Mark Zhandry. Secure identity-based encryption in the quantum random oracle model. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology - CRYPTO 2012, pages 758-775, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
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 Imprint Privacy Contact