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

Improve this question
$\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
    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$
    – Emil Jeřábek
    Jul 14, 2015 at 10:36
  • $\begingroup$ @EmilJeřábek, maybe post your answer as an answer? $\endgroup$
    – usul
    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$
    – Scott Aaronson
    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$
    – Huck Bennett
    Jul 20, 2015 at 23:55

1 Answer 1

Reset to default
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.)

Improve this answer
$\endgroup$

Your Answer

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

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