<p>The oracle you ask for has <span class="math-container">$P=NP\ne BQP=NEXP$</span>, and therefore it has <span class="math-container">$BQP\ne PH$</span>. Finding <em>any</em> oracle relative to which <span class="math-container">$BQP\ne PH$</span> was an open problem for twenty years until Raz and Tal [1] found such an oracle last year. In summary, the oracle you ask for currently is not known to exist, but people are looking. There are oracles relative to which <span class="math-container">$P\ne BPP=PH=BQP=NEXP$</span>, but these lack your constraint <span class="math-container">$P=NP$</span>. [3]*</p>

<p>(The second oracle you ask for exists, namely take <span class="math-container">$O=PSPACE$</span>, then <span class="math-container">$P=NP=BQP=PSPACE\ne NEXP$</span>).</p>

<p>There is currently no quantum PCP Theorem, though again, people are looking. Aharonov et al. [2] provide a readable introduction to the Quantum PCP Conjecture. In this context, as in the classical PCP, there are two equivalent versions, one talking about verifying a quantum proof, the other talking about hardness-of-approximation. One major step that has been accomplished is that we know that the two versions are equivalent, that is, they imply each other. Many other questions remain open.</p>

<p>[1] Raz, Ran, and Avishay Tal. "Oracle Separation of BQP and PH." Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. ACM, 2019.</p>

<p>[2] Aharonov, Dorit, Itai Arad, and Thomas Vidick. "Guest column: the quantum PCP conjecture." Acm sigact news 44.2 (2013): 47-79.</p>

<p>[3] Williams, Ryan. "Towards NEXP versus BPP?." International Computer Science Symposium in Russia. Springer, Berlin, Heidelberg, 2013. (Section 4, Conclusion)</p>

<p>[4] Kitaev, Alexei Yu, et al. Classical and quantum computation. No. 47. American Mathematical Soc., 2002.</p>

<p>(*) (Actually I cannot find a reference for such an oracle, but [3] <em>mentions</em> such an oracle) </p>

CC BY-SA 4.0
2019-09-26T10:49:14.047Z
Wouldn't the quantum PCP theorem deal with $QMA$ (quantum analog of $NP$)? I am just asking if there is a PCP containment of $BQP$ better than that of $NEXP$.
Turbo
CC BY-SA 4.0
2019-09-26T19:23:11.460Z
Also doesn't the recent paper on Raz and Tal provide $PH$ is infinite also?
Turbo
CC BY-SA 4.0
2019-09-26T19:54:23.633Z
Will the quantum PCP deal with $QMA$? I certainly hope so! I would read it. :) Currently, unfortunately, no theorem along these lines is known, so no characterization of $QMA$, no characterization of $BQP$, and no hardness of approximation result. The Quantum PCP Conjecture is sometimes stated in terms of hardness of approximation of the Local Hamiltonian (quantum analog of SAT). In that context, the challenge is to improve the "promise gap" from $O(1/n^2)$ to $O(1)$, but currently no improvement whatsoever has occurred since Kitaev gave the reduction, wtih $O(1/n^2)$, afaik.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2019-09-27T00:26:27.893Z
Sorry I will clarify further.
Turbo
CC BY-SA 4.0
2019-09-27T02:11:43.143Z
For many extreme oracles (including the uncited one), look here: https://blog.computationalcomplexity.org/2005/08/extreme-oracles.html
Ryan Williams
CC BY-SA 4.0
2019-09-26T09:36:15.060Z
2019-09-26T20:34:41.967Z
2019-09-26T20:34:41.967Z
Lieuwe Vinkhuijzen
<ol>
<li><p>Are there oracle results with <span class="math-container">$$P=NP\neq BQP=NEXP\mbox{ and }P=NP\neq BQP\neq NEXP?$$</span></p></li>
<li><p>Also is there a <span class="math-container">$PCP$</span> characterization of <span class="math-container">$BQP$</span> like <span class="math-container">$$PCP(O(poly(n)),1)=PCP(O(poly(n)),O(poly(n)))=NEXP?$$</span></p></li>
</ol>

<cc.complexity-theory><quantum-computing><oracles><pcp><nexp>
Results comparing BQP and NEXP
Turbo
# Results comparing BQP and NEXP

(Asked by: username_0 on 2019-09-26)

1. Are there oracle results with $$P=NP\neq BQP=NEXP\mbox{ and }P=NP\neq BQP\neq NEXP?$$
2. Also is there a $PCP$ characterization of $BQP$ like $$PCP(O(poly(n)),1)=PCP(O(poly(n)),O(poly(n)))=NEXP?$$

**Tags:** cc.complexity-theory, quantum-computing, oracles, pcp, nexp

---

## 1 answers

### Answer by username_1 on 2019-09-26. Score: 6

The oracle you ask for has $P=NP\ne BQP=NEXP$, and therefore it has $BQP\ne PH$. Finding *any* oracle relative to which $BQP\ne PH$ was an open problem for twenty years until Raz and Tal [1] found such an oracle last year. In summary, the oracle you ask for currently is not known to exist, but people are looking. There are oracles relative to which $P\ne BPP=PH=BQP=NEXP$, but these lack your constraint $P=NP$. [3]\*

(The second oracle you ask for exists, namely take $O=PSPACE$, then $P=NP=BQP=PSPACE\ne NEXP$).

There is currently no quantum PCP Theorem, though again, people are looking. Aharonov et al. [2] provide a readable introduction to the Quantum PCP Conjecture. In this context, as in the classical PCP, there are two equivalent versions, one talking about verifying a quantum proof, the other talking about hardness-of-approximation. One major step that has been accomplished is that we know that the two versions are equivalent, that is, they imply each other. Many other questions remain open.

[1] Raz, Ran, and Avishay Tal. "Oracle Separation of BQP and PH." Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. ACM, 2019.

[2] Aharonov, Dorit, Itai Arad, and Thomas Vidick. "Guest column: the quantum PCP conjecture." Acm sigact news 44.2 (2013): 47-79.

[3] Williams, Ryan. "Towards NEXP versus BPP?." International Computer Science Symposium in Russia. Springer, Berlin, Heidelberg, 2013. (Section 4, Conclusion)

[4] Kitaev, Alexei Yu, et al. Classical and quantum computation. No. 47. American Mathematical Soc., 2002.

(\*) (Actually I cannot find a reference for such an oracle, but [3] *mentions* such an oracle)

> **Comments:**
> **username_0**: Wouldn't the quantum PCP theorem deal with $QMA$ (quantum analog of $NP$)? I am just asking if there is a PCP containment of $BQP$ better than that of $NEXP$.  
> **username_0**: Also doesn't the recent paper on Raz and Tal provide $PH$ is infinite also?  
> **username_1**: Will the quantum PCP deal with $QMA$? I certainly hope so! I would read it. :) Currently, unfortunately, no theorem along these lines is known, so no characterization of $QMA$, no characterization of $BQP$, and no hardness of approximation result. The Quantum PCP Conjecture is sometimes stated in terms of hardness of approximation of the Local Hamiltonian (quantum analog of SAT). In that context, the challenge is to improve the "promise gap" from $O(1/n^2)$ to $O(1)$, but currently no improvement whatsoever has occurred since Kitaev gave the reduction, wtih $O(1/n^2)$, afaik.  
> **username_0**: Sorry I will clarify further.  
> **username_2**: For many extreme oracles (including the uncited one), look here: https://blog.computationalcomplexity.org/2005/08/extreme-oracles.html  

---

