1

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?

Loic Stoic
  • 111
  • 2
  • 4
    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 Mar 19 '23 at 10:15
  • 1
    It consistent with current knowledge that $P \subsetneq \textrm{RP} = \textrm{PSPACE}$, which would contradict the title. – Yonatan N Mar 25 '23 at 04:29
  • 1
    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 May 21 '23 at 14:15

0 Answers0