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?

  • 4
    $\begingroup$ No. See e.g. cstheory.stackexchange.com/questions/6154/…, cstheory.stackexchange.com/questions/3304/bqp-vs-qma. $\endgroup$ Commented Mar 19, 2023 at 10:15
  • 1
    $\begingroup$ It consistent with current knowledge that $P \subsetneq \textrm{RP} = \textrm{PSPACE}$, which would contradict the title. $\endgroup$
    – Yonatan N
    Commented Mar 25, 2023 at 4:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark S
    Commented May 21, 2023 at 14:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.