ECCC-Report TR21-164https://eccc.weizmann.ac.il/report/2021/164Comments and Revisions published for TR21-164en-usWed, 24 Apr 2024 23:02:02 +0300
Revision 3
| The Acrobatics of BQP |
Scott Aaronson,
DeVon Ingram,
William Kretschmer
https://eccc.weizmann.ac.il/report/2021/164#revision3We 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.Wed, 24 Apr 2024 23:02:02 +0300https://eccc.weizmann.ac.il/report/2021/164#revision3
Revision 2
| The Acrobatics of BQP |
Scott Aaronson,
DeVon Ingram,
William Kretschmer
https://eccc.weizmann.ac.il/report/2021/164#revision2We 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.Fri, 07 Oct 2022 21:30:24 +0300https://eccc.weizmann.ac.il/report/2021/164#revision2
Revision 1
| The Acrobatics of BQP |
Scott Aaronson,
DeVon Ingram,
William Kretschmer
https://eccc.weizmann.ac.il/report/2021/164#revision1One 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.Wed, 02 Mar 2022 20:21:31 +0200https://eccc.weizmann.ac.il/report/2021/164#revision1
Paper TR21-164
| The Acrobatics of BQP |
Scott Aaronson,
DeVon Ingram,
William Kretschmer
https://eccc.weizmann.ac.il/report/2021/164We 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.Fri, 19 Nov 2021 15:02:40 +0200https://eccc.weizmann.ac.il/report/2021/164