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 blackbox setting, the behavior of quantum polynomialtime (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 "quantumaware" version of the random restriction method, a concentration theorem for the block sensitivity of AC⁰ circuits, and a (provable) analogue of the AaronsonAmbainis Conjecture for sparse oracles.
BibTeX  Entry
@InProceedings{aaronson_et_al:LIPIcs.CCC.2022.20,
author = {Aaronson, Scott and Ingram, DeVon and Kretschmer, William},
title = {{The Acrobatics of BQP}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {20:120:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772419},
ISSN = {18688969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16582},
URN = {urn:nbn:de:0030drops165820},
doi = {10.4230/LIPIcs.CCC.2022.20},
annote = {Keywords: BQP, Forrelation, oracle separations, Polynomial Hierarchy, query complexity}
}
Keywords: 

BQP, Forrelation, oracle separations, Polynomial Hierarchy, query complexity 
Collection: 

37th Computational Complexity Conference (CCC 2022) 
Issue Date: 

2022 
Date of publication: 

11.07.2022 