+314 votes
in Quantum Information by
edited by

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
+301 votes
by

If a quantum computer is able to solve an NP problem in polynomial time (P-time), it would not automatically imply that the problem is in the complexity class P. The complexity classes P and NP are defined with respect to classical computation, and the existence of efficient quantum algorithms for solving NP problems does not directly change the classification of the problem in terms of classical complexity.

The complexity class P consists of decision problems that can be solved in polynomial time on a classical computer. This means that for any given instance of a problem in P, there exists a deterministic classical algorithm that can solve it in polynomial time.

On the other hand, the complexity class NP (nondeterministic polynomial time) consists of decision problems for which a "yes" answer can be efficiently verified by a classical computer in polynomial time. It does not imply that the problem can be solved in polynomial time itself.

If a quantum computer were to solve an NP problem in polynomial time, it would imply that the problem has a quantum algorithm that runs in polynomial time. This would fall under the complexity class BQP (bounded-error quantum polynomial time), which represents problems that can be efficiently solved by a quantum computer with a bounded probability of error.

To summarize, the existence of a quantum algorithm that solves an NP problem in polynomial time would not directly change the classification of the problem itself. It would imply that the problem has a quantum algorithm running in polynomial time, falling under the complexity class BQP, but it would not imply that the problem is in the classical complexity class P.

Welcome to Physicsgurus Q&A, where you can ask questions and receive answers from other members of the community.
...