2 ms·
If such a result were proved, what would happen to the field of quantum computing?
by amichail 16y ago
If such a result were proved, what would happen to the field of quantum computing?
- michael_nielsen 16y agoHard 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 agoQuantum 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.