<p>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.)</p>

CC BY-SA 3.0
2015-07-15T14:09:40.123Z
2015-07-15T14:09:40.123Z
Emil Jeřábek
<p>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.</p>

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

<p>[1] <a href="http://www.scottaaronson.com/papers/bqpph.pdf" rel="nofollow">http://www.scottaaronson.com/papers/bqpph.pdf</a></p>

CC BY-SA 3.0
2015-07-14T09:25:08.457Z
Can you give a specific source for the statement on the collapse of $\mathbb{PH}$. Is it in this [2009 paper](http://www.scottaaronson.com/papers/bqpph.pdf) 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
CC BY-SA 3.0
2015-07-14T10:36:20.020Z
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
CC BY-SA 3.0
2015-07-14T15:44:39.260Z
@EmilJeřábek, maybe post your answer as an answer?
usul
CC BY-SA 3.0
2015-07-15T14:10:16.143Z
@usul: OK, I’ve converted the comment to an answer.
Emil Jeřábek
CC BY-SA 3.0
2015-07-20T02:12:14.487Z
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.
Scott Aaronson
CC BY-SA 3.0
2015-07-20T23:55:36.440Z
This question is a bit worrying given the sequence of recent Younes "NP in BQP" preprints: http://arxiv.org/abs/1507.05061.
Huck Bennett
CC BY-SA 3.0
2015-07-29T13:25:46.070Z
@ScottAaronson. Many thanks for your comment. I was just assuming a positive answer for a question you asked in one of your papers:
"Fourth, a major challenge for quantum computing research is to get better evidence that quantum computers cannot solve NP-complete problems in polynomial time. As an example, could we show that if NP ⊆ BQP, then the polynomial hierarchy collapses? At ﬁrst glance, this seems like a wild hope; certainly we have no idea at present how to prove anything of the kind."

http://www.scottaaronson.com/papers/bqpph.pdf
Ahmed Younes
CC BY-SA 3.0
2015-07-29T13:29:56.363Z
@HuckBennett. Many Thanks for your comment. I didn't make that claim in the preprint.
Ahmed Younes
CC BY-SA 3.0
2015-07-29T14:13:41.297Z
@AhmedYounes: The second sentence of the abstract of the paper I linked to says "The paper shows that BQP contains NP." Are you saying that that's not correct?
Huck Bennett
CC BY-SA 3.0
2015-07-29T14:25:15.083Z
@HuckBennett. No, I mean that I didn't mention in the paper neither P=NP nor PH will collapse if BQP contains NP.
Ahmed Younes
CC BY-SA 3.0
2015-07-29T19:48:44.873Z
@ScottAaronson. The question has been edited to show that it is a question not a statement.
Ahmed Younes
<cc.complexity-theory><np-hardness><quantum-computing><np>
If BQP contains NP, does this mean that P=NP?
Ahmed Younes
# If BQP contains NP, does this mean that P=NP?

(Asked by: username_0 on 2015-07-14)

There is a question raised by username_4 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>

**Tags:** cc.complexity-theory, np-hardness, quantum-computing, np

> **Comments:**
> **username_1**: Can you give a specific source for the statement on the collapse of $\mathbb{PH}$. Is it in this [2009 paper](http://www.scottaaronson.com/papers/bqpph.pdf) 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.  
> **username_2**: 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}$.  
> **username_3**: @EmilJeřábek, maybe post your answer as an answer?  
> **username_2**: @username_3: OK, I’ve converted the comment to an answer.  
> **username_4**: 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.  
> **username_5**: This question is a bit worrying given the sequence of recent Younes "NP in BQP" preprints: http://arxiv.org/abs/1507.05061.  
> **username_0**: @ScottAaronson. Many thanks for your comment. I was just assuming a positive answer for a question you asked in one of your papers: "Fourth, a major challenge for quantum computing research is to get better evidence that quantum computers cannot solve NP-complete problems in polynomial time. As an example, could we show that if NP ⊆ BQP, then the polynomial hierarchy collapses? At ﬁrst glance, this seems like a wild hope; certainly we have no idea at present how to prove anything of the kind."  http://www.scottaaronson.com/papers/bqpph.pdf  
> **username_0**: @HuckBennett. Many Thanks for your comment. I didn't make that claim in the preprint.  
> **username_5**: @AhmedYounes: The second sentence of the abstract of the paper I linked to says "The paper shows that BQP contains NP." Are you saying that that's not correct?  
> **username_0**: @HuckBennett. No, I mean that I didn't mention in the paper neither P=NP nor PH will collapse if BQP contains NP.  
> **username_0**: @ScottAaronson. The question has been edited to show that it is a question not a statement.  

---

## 1 answers

### Answer by username_2 on 2015-07-15. Score: 19 | Accepted answer

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.)


---

