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?
[ Parent
| on HN ]
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.