Log in

No account? Create an account
Who, me? [userpic]

Quantum computers do not help with NP-complete problems

June 3rd, 2010 (11:15 am)
Tags: ,

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

To put it approximately, NP-complete problems are ones where the time to solve the problem is an exponential amount function of the size of the input. The standard example is the traveling salesman problem: given a set of cities that the salesman has to visit, what's the shortest path?

To solve an NP-complete problem in less than exponential time, you'd need a computer that can consider all possible solutions at once. Ordinary computers can't do that; it had long been expected that quantum computers could. But new research shows that, no, they can't.

On the one hand, this means that we won't have quantum computers routing our Internet traffic (optimal routing is NP-complete); on the other hand, it also means that we don't have to worry about quantum computers breaking all known forms of cryptography.



(Deleted comment)
Posted by: Who, me? (metageek)
Posted at: June 4th, 2010 12:33 am (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.

Posted by: alessandro_bard (alessandro_bard)
Posted at: June 5th, 2010 07:13 pm (UTC)
rat's nest

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.

Posted by: Who, me? (metageek)
Posted at: June 5th, 2010 08:50 pm (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. :-)

4 Read Comments