# 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.

(Deleted comment)