1
$\begingroup$

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?

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

1 Answer 1

-1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Oct 11, 2023 at 15:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.