<p>Pretty much the title. Is there any result that shows that <span class="math-container">$P \neq NP \Rightarrow BQP \neq NP$</span>. I think it's pretty clear that <span class="math-container">$BQP \neq NP \Rightarrow P \neq NP$</span>, as <span class="math-container">$P$</span> is a subclass of <span class="math-container">$BQP$</span>. But is anything know about the former problem?</p>

CC BY-SA 4.0
2023-03-19T10:15:16.013Z
No. See e.g. https://cstheory.stackexchange.com/questions/6154/consequences-of-sat-in-bqp, https://cstheory.stackexchange.com/questions/3304/bqp-vs-qma.
Emil Jeřábek
CC BY-SA 4.0
2023-03-25T04:29:25.787Z
It consistent with current knowledge that $P \subsetneq \textrm{RP} = \textrm{PSPACE}$, which would contradict the title.
Yonatan N
CC BY-SA 4.0
2023-05-21T14:15:58.803Z
It is also far from incontrovertible that BQP$\ne$NP$\Rightarrow$P$\ne$NP, at least because BQP likely contain problems *outside* of NP, e.g. problems without any polynomial-size witnesses, and the disjoint union of BQP and NP is likely non-empty.  What I think you meant is that BQP$\subsetneq$NP$\Rightarrow$P$\ne$NP, which does follow from the inclusion of P in BQP.
Mark S
<cc.complexity-theory><quantum-computing><p-vs-np>
Is it known that P $\neq$ NP implies BQP $\neq$ NP?
Loic Stoic
# Is it known that P $\neq$ NP implies BQP $\neq$ NP?

(Asked by: username_0 on 2023-03-19)

Pretty much the title. Is there any result that shows that $P \neq NP \Rightarrow BQP \neq NP$. I think it's pretty clear that $BQP \neq NP \Rightarrow P \neq NP$, as $P$ is a subclass of $BQP$. But is anything know about the former problem?

**Tags:** cc.complexity-theory, quantum-computing, p-vs-np
> **Comments:**
> **username_1**: No. See e.g. https://cstheory.stackexchange.com/questions/6154/consequences-of-sat-in-bqp, https://cstheory.stackexchange.com/questions/3304/bqp-vs-qma.  
> **username_2**: It consistent with current knowledge that $P \subsetneq \textrm{RP} = \textrm{PSPACE}$, which would contradict the title.  
> **username_3**: It is also far from incontrovertible that BQP$\ne$NP$\Rightarrow$P$\ne$NP, at least because BQP likely contain problems *outside* of NP, e.g. problems without any polynomial-size witnesses, and the disjoint union of BQP and NP is likely non-empty.  What I think you meant is that BQP$\subsetneq$NP$\Rightarrow$P$\ne$NP, which does follow from the inclusion of P in BQP.  

---

## 0 answers

