3 ms·
Somebody finding that quantum computers can solve NP-hard problems would be very suspicious. Other than that it would need someone to find a flaw with quantum m
by adrianN 10y ago
Somebody finding that quantum computers can solve NP-hard problems would be very suspicious. Other than that it would need someone to find a flaw with quantum mechanics.
- Meegul 10y agoIt was to my understanding that some NP-complete problems - like factorization - are (theoretically) solvable in P time using quantum computing, all within (and indeed as a result of) the constraints of quantum mechanics, perhaps utilizing Shor's algorithm. And that this fact does not imply P=NP, but rather that we'd have a computer that could perform some exponential functions as if some logarithm were applied to them. I'm no expert, but at the very least I believe it's recognized that some subset of NP problems, perhaps not NP-hard, should be solvable as if they were polynomial, using quantum computers. That said, my knowledge of this subject starts and ends with things I've read on the internet, so I could be mistaken. Either way, this[1] was a very interesting introduction to some of the implications/concepts that are involved with this. 1: http://www.scottaaronson.com/papers/philos.pdf http://www.scottaaronson.com/papers/philos.pdf
- Ar-Curunir 10y agoFactorisation is very, very, very unlikely to be NP-complete. P is a separate class from the class of problems considered efficiently solvable; BQP is the class of problems that are efficiently solved by quantum computers, and it is believed that BQP is strictly larger than P.
- Meegul 10y agoAh alright. Looks like I have some more reading to do this morning.
- kleiba 10y agoSomebody finding that quantum computers can solve NP-hard problems [efficiently] would be very suspicious. The missing word here is "efficiently": all problems in NP are solvable.