Search Results

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.