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?
3
-
4$\begingroup$ No. See e.g. cstheory.stackexchange.com/questions/6154/…, cstheory.stackexchange.com/questions/3304/bqp-vs-qma. $\endgroup$– Emil JeřábekMar 19 at 10:15
-
$\begingroup$ It consistent with current knowledge that $P \subsetneq \textrm{RP} = \textrm{PSPACE}$, which would contradict the title. $\endgroup$– Yonatan NMar 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 SMay 21 at 14:15
Add a comment
|