2026-07-22T11:37:07Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:16582 2024-03-12T12:00:49Z ddc:004 open_access
The Acrobatics of BQP Aaronson, Scott Ingram, DeVon Kretschmer, William BQP Forrelation oracle separations Polynomial Hierarchy query complexity 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. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Scott Aaronson and DeVon Ingram and William Kretschmer 2022 Is Part Of LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2022.20 urn:nbn:de:0030-drops-165820 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.20 eng https://creativecommons.org/licenses/by/4.0/legalcode