4
$\begingroup$

  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?$$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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)

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$
    – Turbo
    Commented Sep 26, 2019 at 10:49
  • $\begingroup$ Also doesn't the recent paper on Raz and Tal provide $PH$ is infinite also? $\endgroup$
    – Turbo
    Commented Sep 26, 2019 at 19:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Lieuwe Vinkhuijzen
    Commented Sep 26, 2019 at 19:54
  • $\begingroup$ Sorry I will clarify further. $\endgroup$
    – Turbo
    Commented Sep 27, 2019 at 0:26
  • 5
    $\begingroup$ For many extreme oracles (including the uncited one), look here: blog.computationalcomplexity.org/2005/08/extreme-oracles.html $\endgroup$
    – Ryan Williams
    Commented Sep 27, 2019 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.