4
$\begingroup$

There is a question raised by Scott Aaronson in one of his papers [1]: "Could we show that if NP ⊆ BQP, then the polynomial hierarchy collapses?". Assuming the answer is yes, and it is also know that if P=NP then PH collapses to the 0th level.

Based on the above two statements, I would like to ask if BQP contains NP, does this imply that P=NP?

[1] http://www.scottaaronson.com/papers/bqpph.pdf

$\endgroup$
  • $\begingroup$ Can you give a specific source for the statement on the collapse of $\mathbb{PH}$. Is it in this 2009 paper by Aaronson? I could only find the result that $\mathbb{PH}$ collapses to the second level provided that $\mathbb{NP} \subseteq \mathbb{BQP} \subseteq \mathbb{AM}$. Trivially $\mathbb{P} = \mathbb{NP} \implies \mathbb{NP} \subseteq \mathbb{BQP}$. This is the opposite direction of what you're asking, which from a quick search seems to me as an open problem. $\endgroup$ – chazisop Jul 14 '15 at 9:25
  • 8
    $\begingroup$ No. Even the stronger assumption $\mathrm{NP}\subseteq\mathrm{BPP}$ is not known to imply lower collapse than $\mathrm{NP}=\mathrm{RP}$ (and $\mathrm{PH}=\mathrm{BPP}$). In particular, it is not known to imply $\mathrm{NP}=\mathrm{coNP}$. $\endgroup$ – Emil Jeřábek Jul 14 '15 at 10:36
  • $\begingroup$ @EmilJeřábek, maybe post your answer as an answer? $\endgroup$ – usul Jul 14 '15 at 15:44
  • 5
    $\begingroup$ Unfortunately, no such result is known, and I never said it was! Maybe I said it would be great to have such a result, or something like that. $\endgroup$ – Scott Aaronson Jul 20 '15 at 2:12
  • 1
    $\begingroup$ This question is a bit worrying given the sequence of recent Younes "NP in BQP" preprints: arxiv.org/abs/1507.05061. $\endgroup$ – Huck Bennett Jul 20 '15 at 23:55
17
$\begingroup$

No, $\mathrm{NP}\subseteq\mathrm{BQP}$ is not known to imply $\mathrm P=\mathrm{NP}$. Even the stronger assumption $\mathrm{NP}\subseteq\mathrm{BPP}$ is not known to yield a deeper collapse than $\mathrm{NP}=\mathrm{RP}$ and $\mathrm{PH}=\mathrm{ZPP^{RP}}=\mathrm{BPP}$; in particular, it is not even known to imply $\mathrm{NP}=\mathrm{coNP}$. (However, all these implications are likely true by virtue of their premises being false.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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