The Acrobatics of BQP
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914769031659520 |
|---|---|
| author | Aaronson, Scott Ingram, DeVon Kretschmer, William |
| author_facet | Aaronson, Scott Ingram, DeVon Kretschmer, William |
| contents | 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 ($\mathsf{BQP}$) can be remarkably decoupled from that of classical complexity classes like $\mathsf{NP}$. Specifically:
-There exists an oracle relative to which $\mathsf{NP^{BQP}}\not\subset\mathsf{BQP^{PH}}$, resolving a 2005 problem of Fortnow. As a corollary, there exists an oracle relative to which $\mathsf{P}=\mathsf{NP}$ but $\mathsf{BQP}\neq\mathsf{QCMA}$.
-Conversely, there exists an oracle relative to which $\mathsf{BQP^{NP}}\not\subset\mathsf{PH^{BQP}}$.
-Relative to a random oracle, $\mathsf{PP}=\mathsf{PostBQP}$ is not contained in the "$\mathsf{QMA}$ hierarchy" $\mathsf{QMA}^{\mathsf{QMA}^{\mathsf{QMA}^{\cdots}}}$.
-Relative to a random oracle, $\mathsfΣ_{k+1}^\mathsf{P}\not\subset\mathsf{BQP}^{\mathsfΣ_{k}^\mathsf{P}}$ for every $k$.
-There exists an oracle relative to which $\mathsf{BQP}=\mathsf{P^{\# P}}$ and yet $\mathsf{PH}$ is infinite.
-There exists an oracle relative to which $\mathsf{P}=\mathsf{NP}\neq\mathsf{BQP}=\mathsf{P^{\# P}}$.
To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which $\mathsf{BQP}\not \subset \mathsf{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 $\mathsf{AC^0}$ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_10409 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The Acrobatics of BQP Aaronson, Scott Ingram, DeVon Kretschmer, William Computational Complexity Quantum Physics 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 ($\mathsf{BQP}$) can be remarkably decoupled from that of classical complexity classes like $\mathsf{NP}$. Specifically: -There exists an oracle relative to which $\mathsf{NP^{BQP}}\not\subset\mathsf{BQP^{PH}}$, resolving a 2005 problem of Fortnow. As a corollary, there exists an oracle relative to which $\mathsf{P}=\mathsf{NP}$ but $\mathsf{BQP}\neq\mathsf{QCMA}$. -Conversely, there exists an oracle relative to which $\mathsf{BQP^{NP}}\not\subset\mathsf{PH^{BQP}}$. -Relative to a random oracle, $\mathsf{PP}=\mathsf{PostBQP}$ is not contained in the "$\mathsf{QMA}$ hierarchy" $\mathsf{QMA}^{\mathsf{QMA}^{\mathsf{QMA}^{\cdots}}}$. -Relative to a random oracle, $\mathsfΣ_{k+1}^\mathsf{P}\not\subset\mathsf{BQP}^{\mathsfΣ_{k}^\mathsf{P}}$ for every $k$. -There exists an oracle relative to which $\mathsf{BQP}=\mathsf{P^{\# P}}$ and yet $\mathsf{PH}$ is infinite. -There exists an oracle relative to which $\mathsf{P}=\mathsf{NP}\neq\mathsf{BQP}=\mathsf{P^{\# P}}$. To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which $\mathsf{BQP}\not \subset \mathsf{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 $\mathsf{AC^0}$ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles. |
| title | The Acrobatics of BQP |
| topic | Computational Complexity Quantum Physics |
| url | https://arxiv.org/abs/2111.10409 |