Document Open Access Logo

The Acrobatics of BQP

Authors Scott Aaronson, DeVon Ingram, William Kretschmer

PDF
Thumbnail PDF

File

LIPIcs.CCC.2022.20.pdf
  • Filesize: 0.8 MB
  • 17 pages

Document Identifiers

Author Details

Scott Aaronson
  • University of Texas at Austin, TX, USA
DeVon Ingram
  • University of Chicago, IL, USA
William Kretschmer
  • University of Texas at Austin, TX, USA

Funding

  • Aaronson, Scott: Supported by a Vannevar Bush Fellowship from the US Department of Defense, a Simons Investigator Award, and the Simons "It from Qubit" collaboration.
  • Ingram, DeVon: Supported by an NSF Graduate Research Fellowship.
  • Kretschmer, William: Supported by an NDSEG Fellowship.

Acknowledgements

We thank Lance Fortnow, Greg Kuperberg, Patrick Rall, and Avishay Tal for helpful conversations. We are especially grateful to Avishay Tal for helping us prove a tail bound on the block sensitivity of AC⁰ circuits.

Cite As Get BibTex

Scott Aaronson, DeVon Ingram, and William Kretschmer. The Acrobatics of BQP. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CCC.2022.20

Abstract

One can fix the randomness used by a randomized algorithm, but there is no analogous notion of fixing the quantumness used by a quantum algorithm. Underscoring this fundamental difference, we show that, in the black-box setting, the behavior of quantum polynomial-time (BQP) can be remarkably decoupled from that of classical complexity classes like NP. Specifically:
- There exists an oracle relative to which NP^{BQP} ⊄ BQP^{PH}, resolving a 2005 problem of Fortnow. As a corollary, there exists an oracle relative to which 𝖯 = NP but BQP ≠ QCMA. 
- Conversely, there exists an oracle relative to which BQP^{NP} ⊄ PH^{BQP}. 
- Relative to a random oracle, PP is not contained in the "QMA hierarchy" QMA^{QMA^{QMA^{⋯}}}. 
- Relative to a random oracle, Σ_{k+1}^𝖯 ⊄ BQP^{Σ_k^𝖯} for every k. 
- There exists an oracle relative to which BQP = P^#P and yet PH is infinite. (By contrast, relative to all oracles, if NP ⊆ BPP, then PH collapses.) 
- There exists an oracle relative to which 𝖯 = NP ≠ BQP = 𝖯^#P. 
To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which BQP ⊄ PH, and associated results about the Forrelation problem. We also introduce new tools that might be of independent interest. These include a "quantum-aware" version of the random restriction method, a concentration theorem for the block sensitivity of AC⁰ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
  • Theory of computation → Complexity classes
Keywords
  • BQP
  • Forrelation
  • oracle separations
  • Polynomial Hierarchy
  • query complexity

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. URL: https://doi.org/10.1098/rspa.2005.1546.
  2. Scott Aaronson. BQP and the polynomial hierarchy. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC '10, pages 141-150, New York, NY, USA, 2010. Association for Computing Machinery. URL: https://doi.org/10.1145/1806689.1806711.
  3. Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups. Theory of Computing, 10(6):133-166, 2014. URL: https://doi.org/10.4086/toc.2014.v010a006.
  4. Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. SIAM Journal on Computing, 47(3):982-1038, 2018. URL: https://doi.org/10.1137/15M1050902.
  5. Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. Theory of Computing, 9(4):143-252, 2013. URL: https://doi.org/10.4086/toc.2013.v009a004.
  6. Scott Aaronson and Lijie Chen. Complexity-Theoretic Foundations of Quantum Supremacy Experiments. In Ryan O'Donnell, editor, 32nd Computational Complexity Conference (CCC 2017), volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1-22:67, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.22.
  7. Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, and Elham Kashefi. Complexity-Theoretic Limitations on Blind Delegated Quantum Computation. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1-6:13, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.6.
  8. Scott Aaronson, DeVon Ingram, and William Kretschmer. The acrobatics of BQP, 2021. URL: http://arxiv.org/abs/2111.10409.
  9. Leonard Adleman. Two theorems on random polynomial time. In 19th Annual Symposium on Foundations of Computer Science (SFCS 1978), pages 75-83, 1978. URL: https://doi.org/10.1109/SFCS.1978.37.
  10. Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh A. Huang. Quantum computability. SIAM Journal on Computing, 26(5):1524-1540, 1997. URL: https://doi.org/10.1137/S0097539795293639.
  11. Frank Arute, Kunal Arya, Ryan Babbush, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505-510, 2019. URL: https://doi.org/10.1038/s41586-019-1666-5.
  12. László Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. computational complexity, 1(1):3-40, 1991. URL: https://doi.org/10.1007/BF01200056.
  13. Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P=?NP question. SIAM Journal on Computing, 4(4):431-442, 1975. URL: https://doi.org/10.1137/0204037.
  14. 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. URL: https://doi.org/10.1137/S0097539796300933.
  15. Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411-1473, 1997. URL: https://doi.org/10.1137/S0097539796300921.
  16. Elmar Böhler, Christian Glaßer, and Daniel Meister. Error-bounded probabilistic computations between MA and AM. Journal of Computer and System Sciences, 72(6):1043-1076, 2006. URL: https://doi.org/10.1016/j.jcss.2006.05.001.
  17. Ravi B. Boppana, Johan Håstad, and Stathis Zachos. Does co-NP have short interactive proofs? Inf. Process. Lett., 25(2):127-132, May 1987. URL: https://doi.org/10.1016/0020-0190(87)90232-8.
  18. Sergey Bravyi, Anirban Chowdhury, David Gosset, and Pawel Wocjan. On the complexity of quantum partition functions, 2021. URL: http://arxiv.org/abs/2110.15466.
  19. Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A, 467:459-472, 2010. URL: https://doi.org/10.1098/rspa.2010.0301.
  20. Lance Fortnow. Pulling out the quantumness [online]. December 2005. URL: https://blog.computationalcomplexity.org/2005/12/pulling-out-quantumness.html.
  21. Lance Fortnow and John Rogers. Complexity limitations on quantum computation. In Proceedings. Thirteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat. No.98CB36247), pages 202-209, 1998. URL: https://doi.org/10.1109/CCC.1998.694606.
  22. Merrick Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. URL: https://doi.org/10.1007/BF01744431.
  23. Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2). In Igor Potapov, Paul Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of Leibniz International Proceedings in Informatics (LIPIcs), pages 58:1-58:16, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.58.
  24. Parikshit Gopalan, Rocco Servedio, Avishay Tal, and Avi Wigderson. Degree and sensitivity: tails of two distributions, 2016. Earlier version in CCC 2016. URL: http://arxiv.org/abs/1604.07432.
  25. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC '96, pages 212-219, New York, NY, USA, 1996. Association for Computing Machinery. URL: https://doi.org/10.1145/237814.237866.
  26. Yenjo Han, Lane A. Hemaspaandra, and Thomas Thierauf. Threshold computation and cryptographic security. SIAM Journal on Computing, 26(1):59-78, 1997. URL: https://doi.org/10.1137/S0097539792240467.
  27. Johan Håstad. Computational Limitations of Small-Depth Circuits. MIT Press, Cambridge, MA, USA, 1987. Google Scholar
  28. Johan Håstad, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan. An average-case depth hierarchy theorem for Boolean circuits. J. ACM, 64(5), August 2017. URL: https://doi.org/10.1145/3095799.
  29. Hao Huang. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Annals of Mathematics, 190(3):949-955, 2019. URL: https://doi.org/10.4007/annals.2019.190.3.6.
  30. Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP*=RE, 2020. URL: http://arxiv.org/abs/2001.04383.
  31. Richard M. Karp and Richard J. Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC '80, pages 302-309, New York, NY, USA, 1980. Association for Computing Machinery. URL: https://doi.org/10.1145/800141.804678.
  32. William Kretschmer. Quantum Pseudorandomness and Classical Complexity. In Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1-2:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.TQC.2021.2.
  33. Greg Kuperberg. How hard is it to approximate the Jones polynomial? Theory of Computing, 11(6):183-219, 2015. URL: https://doi.org/10.4086/toc.2015.v011a006.
  34. Clemens Lautemann. BPP and the polynomial hierarchy. Information Processing Letters, 17(4):215-217, 1983. URL: https://doi.org/10.1016/0020-0190(83)90044-3.
  35. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, Fourier transform, and learnability. J. ACM, 40(3):607-620, July 1993. URL: https://doi.org/10.1145/174130.174138.
  36. Ashley Montanaro. Some applications of hypercontractive inequalities in quantum information theory. Journal of Mathematical Physics, 53(12):122206, 2012. URL: https://doi.org/10.1063/1.4769269.
  37. Ryan O'Donnell and Yu Zhao. Polynomial Bounds for Decoupling, with Applications. In Ran Raz, editor, 31st Conference on Computational Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1-24:18, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.24.
  38. Ran Raz and Avishay Tal. Oracle separation of BQP and PH. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 13-23, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3313276.3316315.
  39. Ben W. Reichardt, Falk Unger, and Umesh Vazirani. A classical leash for a quantum system: Command of quantum systems via rigidity of CHSH games. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS '13, pages 321-322, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2422436.2422473.
  40. Benjamin Rossman. An entropy proof of the switching lemma and tight bounds on the decision-tree size of AC0. Manuscript, 2017. URL: https://users.cs.duke.edu/~br148/logsize.pdf.
  41. Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan. Complexity theory column 89: The polynomial hierarchy, random oracles, and Boolean circuits. SIGACT News, 46(4):50-68, December 2015. URL: https://doi.org/10.1145/2852040.2852052.
  42. Adi Shamir. IP = PSPACE. J. ACM, 39(4):869-877, October 1992. URL: https://doi.org/10.1145/146585.146609.
  43. Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, 41(2):303-332, 1999. URL: https://doi.org/10.1137/S0036144598347011.
  44. Daniel R. Simon. On the power of quantum computation. SIAM Journal on Computing, 26(5):1474-1483, 1997. URL: https://doi.org/10.1137/S0097539796298637.
  45. Michael Sipser. A complexity theoretic approach to randomness. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC '83, pages 330-335, New York, NY, USA, 1983. Association for Computing Machinery. URL: https://doi.org/10.1145/800061.808762.
  46. Larry Stockmeyer. The complexity of approximate counting. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC '83, pages 118-126, New York, NY, USA, 1983. Association for Computing Machinery. URL: https://doi.org/10.1145/800061.808740.
  47. Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865-877, 1991. URL: https://doi.org/10.1137/0220053.
  48. John Watrous. Succinct quantum proofs for properties of finite groups. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 537-546. IEEE, 2000. URL: https://doi.org/10.1109/SFCS.2000.892005.
  49. Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan. Quantum computational advantage using photons. Science, 370(6523):1460-1463, 2020. URL: https://doi.org/10.1126/science.abe8770.
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