The Acrobatics of BQP

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 $mathsf{BQP}$ can be remarkably decoupled from that of classical complexity classes like mathsf{NP}. Specifically: -There exists an oracle relative to which mathsf{NP^BQP}notsubsetmathsf{BQP^PH}, resolving a 2005 problem of Fortnow. As a corollary, there exists an oracle relative to which mathsf{P}=mathsf{NP} but mathsf{BQP}neqmathsf{QCMA}. -Conversely, there exists an oracle relative to which mathsf{BQP^NP}notsubsetmathsf{PH^BQP}. -Relative to a random oracle, mathsf{PP}=mathsf{PostBQP} is not contained in the "mathsf{QMA} hierarchy" mathsf{QMA}^{mathsf{QMA}^{mathsf{QMA}^cdots}}. -Relative to a random oracle, mathsfΣ_k+1^mathsf{P}notsubsetmathsf{BQP}^{mathsfΣ_k^mathsf{P}} for every k. -There exists an oracle relative to which mathsf{BQP}=mathsf{P^{\# P}} and yet mathsf{PH} is infinite. -There exists an oracle relative to which mathsf{P}=mathsf{NP}neqmathsf{BQP}=mathsf{P^{\# P}}. To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which mathsf{BQP}not subset mathsf{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 mathsf{AC⁰} circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.