Re:Quantum computers no better than classical ones for NP-co...
by amichail on Thursday June 03, 2010 @09:20PM
(#1403207)
If such a result were proved, what would happen to the field of quantum computing?
Re:Quantum computers no better than classical ones for NP-co...
by michael_nielsen on Thursday June 03, 2010 @09:27PM
(#1403218)
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 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.
Re:Quantum computers no better than classical ones for NP-co...
by edanm on Friday June 04, 2010 @06:00AM
(#1403909)
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) 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.
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. 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.