Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-164 | 19th November 2021 09:55

The Acrobatics of BQP


Authors: Scott Aaronson, DeVon Ingram, William Kretschmer
Publication: 19th November 2021 15:02
Downloads: 605


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.

ISSN 1433-8092 | Imprint