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


Your Answer

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