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.



Posted by: metahacker (metahacker)
Posted at: June 3rd, 2010 10:56 pm (UTC)

Hunh. A major, major result that will probably go by the boards, since it's a non-result.

I must admit I was always skeptical about how, exactly, qomputers would cross the P/NP threshold--it felt like someone was hiding a division by infinity somewhere, likely in the measurable precision of readouts. I'm kind of amused that this turns out to be right, in that measuring that lowest gap they talk about looks like the infinite precision I feared.

Has it been theoretically proven, or simply demonstrated scientifically? The article isn't clear.

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