# Does finding an algorithm that solves an NP-Problem in Polynomial time in a Quantum Computer imply P = NP?

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

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}$$.
• 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. Aug 26 '20 at 22:47