# If BQP contains NP, does this mean that P=NP?

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?

• 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. – chazisop Jul 14 '15 at 9:25
• 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}$. – Emil Jeřábek supports Monica Jul 14 '15 at 10:36
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.)