Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR21-164 | 19th November 2021 09:55

#### The Acrobatics of BQP

TR21-164
Authors: Scott Aaronson, DeVon Ingram, William Kretschmer
Publication: 19th November 2021 15:02
Keywords:

Abstract:

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