7 ms·
Quantum computers are not known to be able to solve NP-complete problems in polynomial time. (Assuming for the sake of argument that we can actually build them.
by gjm11 16y ago
Quantum computers are not known to be able to solve NP-complete problems in polynomial time. (Assuming for the sake of argument that we can actually build them.)
There are problems -- factorization, as others have already said, is the commonest example -- that (1) are not known to be solvable classically in a reasonable amount of time and (2) are known to be solvable by a quantum computer in a reasonable amount of time. But they aren't NP-complete problems.
- vmind 16y agoQuantum Computers are able to solve problems of complexity BQP in polynomial time. BQP is suspected to cover all problems in P, some in NP (but not NP-complete), and some outside of NP but in PSPACE. (http://en.wikipedia.org/wiki/BQP http://en.wikipedia.org/wiki/BQP)
- sukuriant 16y agoAh! That clears things up quite a bit. I'm surprised they're not able to work at the NP-C set. Is it because the probability of a right answer is so small?