# Quantum computers do not help with NP-complete problems

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.

Probably.

metahacker)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.