2
$\begingroup$

I was wondering if the complexity of a quantum circuit that solves a problem that is in NP implies P=NP?

$\endgroup$
4
$\begingroup$

In short, no — as things stand, if there were a polynomial-time algorithm to solve an $\mathsf{NP}$-complete problem on a(n idealised) quantum computer (with reasonably low error probabilities), this would not imply that $\mathsf{P} = \mathsf{NP}$. The question of "what problems are in $\mathsf{P}$" is a very different one from "what problems can you efficiently solve in principle on an idealised quantum computer".

The problems that are in $\mathsf{P}$, are not actually "the problems that can be solved in practise"; it is the set of decision problems that can be solved, in polynomial time, very specifically on a classical computer (more precisely: a deterministic Turing machine, or any model of computation which is polynomial-time equivalent to a deterministic Turing machine).

It is, perhaps, possible that there is a classical algorithm to efficiently simulate an idealised quantum computer, i.e., to simulate polynomial-time uniform quantum circuit families which produce outcomes in {0,1}. But we have no particular evidence that this is the case, and certainly no proof. So, if we discovered an $\mathsf{NP}$-complete problem L which happened to be solvable efficiently (and with low enough probability of error) by quantum computers — that is, if we discovered such a problem L, which belonged to the class $\mathsf{BQP}$ of problems solvable by a quantum computer in that sense — this would not necessarily provide us with any way to solve the problem in polynomial time using deterministic Turing machines (or in other words to show that L is also in $\mathsf{P}$), nor even any evidence in that direction.

More generally, there are no other formal results or other evidence to the effect that $\mathsf{NP} \subseteq \mathsf{BQP}$ only if $\mathsf{NP} = \mathsf{P}$. So, even if we could solve $\mathsf{NP}$-complete problems on a quantum computer, this wouldn't provide us with any proof (or formal reason to believe) that $\mathsf{P} = \mathsf{NP}$.

(It would, however, be an extremely exciting and surprising result.)

$\endgroup$
2
  • 1
    $\begingroup$ Pedantically, although this excellent answer directly answers the question of whether "a quantum circuit that solves a problem that is NP-complete implies P=NP?" (it does not), to the OP's original question about whether "a quantum circuit that solves a problem that is merely in NP" has any bearing on whether P=NP, this also does not, if only because $\mathsf{P}\subseteq\mathsf{NP}$, and thus the OP's considered problem in NP could also have been in P. $\endgroup$
    – Mark S
    Aug 26 '20 at 22:47
  • $\begingroup$ @MarkS: that is also quite correct. $\endgroup$ Aug 26 '20 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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