Quantum computers do not help with NP-complete problems

Jun 03, 2010 11:15

Just seen at Ars Technica: it's now been proven that quantum computers are no better than ordinary computers at NP-complete problems ( Read more... )

cs, geekery

Leave a comment

Comments 3

(The comment has been removed)

metageek June 4 2010, 00:33:37 UTC
It sounded to me as if it's been proven. Of course, I'm not qualified to judge the proof.

It also relies on a previous result that proved that adiabatic quantum computers were exactly as capable as, er, the other kind. The current paper is a proof about the limits of adiabatic quantum computers, so, if the previous result fell, this one wouldn't apply.

But, yeah, I had had the same sort of suspicions you did.

Reply

alessandro_bard June 5 2010, 19:13:47 UTC
The theory of quantum computers sounds too good to be true, but there are many other such things that have seemed so as well but turned out to be real (superconductivity, say, or Halbach arrays). TAANSTAAFL.

Maybe we need to adjust the quantum error correction unit. It's over there in the corner next to the Heisenberg compensator.

Reply

metageek June 5 2010, 20:50:24 UTC
but there are many other such things that have seemed so as well but turned out to be real

True, true. Those are the exceptions, though. :-)

Reply


Leave a comment

Up