3 ms·

This has almost certainly only been shown for a restricted class of adiabatic quantum computers. The full adiabatic quantum computing model is equivalent to or

This has almost certainly only been shown for a restricted class of adiabatic quantum computers. The full adiabatic quantum computing model is equivalent to ordinary quantum computing (http://arxiv.org/abs/quant-ph/0405098 http://arxiv.org/abs/quant-ph/0405098 ). If the linked article is literally correct, then that means quantum computers can efficiently solve NP-complete problems if and only if classical computers can efficiently solve NP-complete problems. That may be true, but I'd be very surprised if someone has proved it. My guess: the paper under discussion probably shows that some particular adiabatic approach to solving NP-complete problems fails - most likely, some variant on the ideas in http://arxiv.org/abs/quant-ph/0001106 http://arxiv.org/abs/quant-ph/0001106. That's well and good, but a long way from proving that quantum computers are no better than classical at solving NP-complete problems. Variants on this result have been floating around for years - I first heard of one in 2000. This is probably an improvement on those early results. Unfortunately, the link to the original paper is broken at present, so that's just a guess.

amichail 16y ago
If such a result were proved, what would happen to the field of quantum computing?
- michael_nielsen 16y ago
  Hard to say. My first instinct is probably not a whole lot. It's more or less conventional wisdom in the field that quantum computers are unlikely to be able to solve NP-complete problems in polynomial time. The argument for this conventional wisdom is heuristic (and certainly open to doubt, maybe most people are wrong), and it's in this paper: http://arxiv.org/abs/quant-ph/9701001 http://arxiv.org/abs/quant-ph/9701001 But in any case, it's one thing for something to be widely believed, and another thing to have hard evidence. People might respond quite dramatically to such evidence.
- edanm 16y ago
  Quantum computers are known to solve some problems faster than classical computers. For example, see Shor's Algoroithm (http://en.wikipedia.org/wiki/Shors_algorithm http://en.wikipedia.org/wiki/Shors_algorithm) for factorization, which finds factors of a number in polynomial time on a quantum computer. This alone is an enormous breakthrough. The question is whether Quantum Computer can solve NP problems in Polynomial time, which no one knows yet.

amichail 16y ago

If such a result were proved, what would happen to the field of quantum computing?

michael_nielsen 16y ago
Hard to say. My first instinct is probably not a whole lot. It's more or less conventional wisdom in the field that quantum computers are unlikely to be able to solve NP-complete problems in polynomial time. The argument for this conventional wisdom is heuristic (and certainly open to doubt, maybe most people are wrong), and it's in this paper: http://arxiv.org/abs/quant-ph/9701001 http://arxiv.org/abs/quant-ph/9701001 But in any case, it's one thing for something to be widely believed, and another thing to have hard evidence. People might respond quite dramatically to such evidence.
edanm 16y ago
Quantum computers are known to solve some problems faster than classical computers. For example, see Shor's Algoroithm (http://en.wikipedia.org/wiki/Shors_algorithm http://en.wikipedia.org/wiki/Shors_algorithm) for factorization, which finds factors of a number in polynomial time on a quantum computer. This alone is an enormous breakthrough. The question is whether Quantum Computer can solve NP problems in Polynomial time, which no one knows yet.