+94 votes
in Quantum Computing by
edited by

Your answer

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

If a quantum computer is found to solve a problem that is considered NP (nondeterministic polynomial time) in classical computing in polynomial time, it does not necessarily mean that the problem becomes P (solvable in deterministic polynomial time).

NP problems are those for which a solution can be verified in polynomial time. These problems are not necessarily solvable in polynomial time on classical computers. However, if a quantum computer could solve an NP problem in polynomial time, it would mean that the problem is in BQP (bounded error quantum polynomial time), the quantum analog of P.

BQP encompasses problems that can be solved by a quantum computer in polynomial time with a bounded probability of error. It is a superset of P, which includes problems that can be solved by classical computers in deterministic polynomial time.

While a quantum computer solving an NP problem in polynomial time would be a significant breakthrough, it does not imply that the problem becomes P. It would rather mean that the problem is efficiently solvable using quantum algorithms. The complexity class P, on the other hand, refers specifically to problems that are efficiently solvable in a classical deterministic fashion.

In summary, the relationship between NP and P is a fundamental question in computer science and remains unsolved. If a quantum computer were to solve an NP problem in polynomial time, it would demonstrate that the problem is in BQP, but it would not directly imply that the problem is in P.

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