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
If BQP contains NP, does this mean that P=NP?
cc.complexity theory;np hardness;quantum computing;np
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.)