3 ms·
If quantum computers could solve NP-complete problems efficiently, the entire community would astounded. As it stands, quantum computers can solve some problem
by Ar-Curunir 10y ago
If quantum computers could solve NP-complete problems efficiently, the entire community would astounded.
As it stands, quantum computers can solve some problems faster than classical computers currently can; factorisation, discrete log and other problems with a particular kind of repeated structure are some such problems. However, we do not know for certain that these problems are not efficiently solvable using classical computers (I'd bet that factorisation will be put in P within my lifetime).
A big goal of the QC community is to demonstrate quantum supremacy: to unconditionally show that quantum computers can solve a problem with fewer resources than classical computers. We've made progress on this (check out Scott Aaronson's blog for more info), but still haven't achieved it.
Lastly, a small nitpick. "P time" is not a meaningful phrase; P is a complexity class consisting of problems solvable efficiently (i.e., in polynomial time) on classical computers.
The class of efficiently solvable problems on quantum computers is BQP: Bounded-error Quantum Polynomial-time, which means that BQP is the class of problems that are efficiently solved by a quantum computer, but only with some probability bounded away from 1/2. This means the QC can return incorrect answers, but there are techniques to reduce the error probability to extremely small values.
The classical analogue of this class is BPP, which is Bounded-error probabilistic poly-time. There's a conjecture that BPP=P, and if we have any sort of crypto then the conjecture is true.