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$
11
  • $\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
    Commented Jul 14, 2015 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$ Commented Jul 14, 2015 at 10:36
  • $\begingroup$ @EmilJeřábek, maybe post your answer as an answer? $\endgroup$
    – usul
    Commented Jul 14, 2015 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$ Commented Jul 20, 2015 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$ Commented Jul 20, 2015 at 23:55

1 Answer 1

19
$\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 and acknowledge you have read our privacy policy.

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