# Is it known that P $\neq$ NP implies BQP $\neq$ NP?

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?

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

I guess you are wondering if:

Statement-I: $$P \subset NP \implies BQP \subset NP$$. [Strict containment of P in NP implies strict containment of BQP in NP.]

Or,

Statement-II: $$P \subset NP \implies BQP \neq NP$$. [Strict containment of P in NP implies incomparabilty of sets BQP and NP]

Regarding statement-I:

$$\bullet$$ $$BQP\subset NP$$ could have been easily inferred if $$BQP\subseteq P$$. (Just visualize BQP, P and NP as three non-intersecting sets.)

But, it has been conjectured that $$BQP\subset P$$. The basis of conjecture is existence of an oracle. [See Simon's Oracle/problem]. Hence, resolution of 'Statement-I' requires resolution of P vs BQP problem.

Regarding statement-II:

It is known that P and BQP is comparable sets. They can't intersect each other (implied by their definitions). Same holds for P and NP.

But, BQP and NP (or even PH) is conjectured to be incomparable. (See Raz-Tal, 2018 Result).

Incomparabilty of sets BQP and NP can't be inferred by comparing the P and NP sets (Unless BQP collapses to P).

Conclusion: $$P\neq NP$$ doesn't give you much insight into BQP and NP, unless relationship between BQP and P is known.

Recently, a new development happens in relating quantum and classical complexity classes (due to Scott Aaronson-Ingram-Kretschmer, 2022). This would give you some insight why relating BQP to other complexity class is currently percieved to be challenging.