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}}\not \subset {BQP}^{{PH}}$, resolving a 2005 problem of Fortnow. Interpreted another way, we show that ${AC^0}$ circuits cannot perform useful homomorphic encryption on instances of the Forrelation problem. As a corollary, there exists an oracle relative to which ${P} = {NP}$ but ${BQP} \neq {QCMA}$.
-Conversely, there exists an oracle relative to which ${BQP}^{{NP}}\not \subset {PH}^{{BQP}}$.
-Relative to a random oracle, ${PP} = {PostBQP}$ is not contained in the "${QMA}$ hierarchy" ${QMA}^{{QMA}^{{QMA}^{\cdots}}}$, and more generally ${PP} \not\subset ({MIP}^*)^{({MIP}^*)^{({MIP}^*)^{\cdots}}}$ (!), despite the fact that ${MIP}^{\ast}={RE}$ in the unrelativized world. This result shows that there is no black-box quantum analogue of Stockmeyer's approximate counting algorithm.
-Relative to a random oracle, ${\Sigma}_{k+1}^{P} \not\subset {BQP}^{{\Sigma}_{k}^{P}}$ for every $k$.
-There exists an oracle relative to which ${BQP} = {P^{\# P}}$ and yet ${PH}$ is infinite. (By contrast, if ${NP}\subseteq{BPP}$, then ${PH}$ collapses relative to all oracles.)
-There exists an oracle relative to which ${P}={NP} \neq {BQP}={P}^{{\#P}}$.

To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which ${BQP}\not \subset {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^0}$ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.

Corrected an error in what is now Lemma 53

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}}\not \subset {BQP}^{{PH}}$, resolving a 2005 problem of Fortnow. Interpreted another way, we show that ${AC^0}$ circuits cannot perform useful homomorphic encryption on instances of the Forrelation problem. As a corollary, there exists an oracle relative to which ${P} = {NP}$ but ${BQP} \neq {QCMA}$.
-Conversely, there exists an oracle relative to which ${BQP}^{{NP}}\not \subset {PH}^{{BQP}}$.
-Relative to a random oracle, ${PP} = {PostBQP}$ is not contained in the "${QMA}$ hierarchy" ${QMA}^{{QMA}^{{QMA}^{\cdots}}}$, and more generally ${PP} \not\subset ({MIP}^*)^{({MIP}^*)^{({MIP}^*)^{\cdots}}}$ (!), despite the fact that ${MIP}^{\ast}={RE}$ in the unrelativized world. This result shows that there is no black-box quantum analogue of Stockmeyer's approximate counting algorithm.
-Relative to a random oracle, ${\Sigma}_{k+1}^{P} \not\subset {BQP}^{{\Sigma}_{k}^{P}}$ for every $k$.
-There exists an oracle relative to which ${BQP} = {P^{\# P}}$ and yet ${PH}$ is infinite. (By contrast, if ${NP}\subseteq{BPP}$, then ${PH}$ collapses relative to all oracles.)
-There exists an oracle relative to which ${P}={NP} \neq {BQP}={P}^{{\#P}}$.

To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which ${BQP}\not \subset {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^0}$ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.

Minor fixes to spelling and references

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}}\not \subset {BQP}^{{PH}}$, resolving a 2005 problem of Fortnow. As a corollary, there exists an oracle relative to which ${P} = {NP}$ but ${BQP} \neq {QCMA}$.
-Conversely, there exists an oracle relative to which ${BQP}^{{NP}}\not \subset {PH}^{{BQP}}$.
-Relative to a random oracle, ${PP} = {PostBQP}$ is not contained in the "${QMA}$ hierarchy" ${QMA}^{{QMA}^{{QMA}^{\cdots}}}$.
-Relative to a random oracle, ${\Sigma}_{k+1}^{P} \not\subset {BQP}^{{\Sigma}_{k}^{P}}$ 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}\subseteq{BPP}$, then ${PH}$ collapses.)
-There exists an oracle relative to which ${P}={NP} \neq {BQP}={P}^{{\#P}}$.

To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which ${BQP}\not \subset {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^0}$ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.

Various writing improvements

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}}\not \subset {BQP}^{{PH}}$, resolving a 2005 problem of Fortnow. Interpreted another way, we show that ${AC^0}$ circuits cannot perform useful homomorphic encryption on instances of the Forrelation problem. As a corollary, there exists an oracle relative to which ${P} = {NP}$ but ${BQP} \neq {QCMA}$.
-Conversely, there exists an oracle relative to which ${BQP}^{{NP}}\not \subset {PH}^{{BQP}}$.
-Relative to a random oracle, ${PP} = {PostBQP}$ is not contained in the "${QMA}$ hierarchy" ${QMA}^{{QMA}^{{QMA}^{\cdots}}}$, and more generally ${PP} \not\subset ({MIP}^*)^{({MIP}^*)^{({MIP}^*)^{\cdots}}}$ (!), despite the fact that ${MIP}^{\ast}={RE}$ in the unrelativized world. This result shows that there is no black-box quantum analogue of Stockmeyer's approximate counting algorithm.
-Relative to a random oracle, ${\Sigma}_{k+1}^{P} \not\subset {BQP}^{{\Sigma}_{k}^{P}}$ for every $k$.
-There exists an oracle relative to which ${BQP} = {P^{\# P}}$ and yet ${PH}$ is infinite. (By contrast, if ${NP}\subseteq{BPP}$, then ${PH}$ collapses relative to all oracles.)
-There exists an oracle relative to which ${P}={NP} \neq {BQP}={P}^{{\#P}}$.

To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which ${BQP}\not \subset {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^0}$ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.