News for hackers. Stuff that matters.
Re:Quantum computing device hints at powerful future by gjm11 on Tuesday March 22, 2011 @06:24AM (#2353747)
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.

Re:Quantum computing device hints at powerful future by vmind on Tuesday March 22, 2011 @07:01AM (#2353809)
Quantum 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)
Re:Quantum computing device hints at powerful future by sukuriant on Tuesday March 22, 2011 @12:39PM (#2355139)
Ah! 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?