3 ms·
There is a myth that quantum computers are known to be able to solve NP-complete problems in polynomial time by trying all possibilities at once using quantum s
by bdr 16y ago
There is a myth that quantum computers are known to be able to solve NP-complete problems in polynomial time by trying all possibilities at once using quantum superposition. For example, by simultaneously trying all possible variable assignments in a SAT problem.
In general, you're confusing decidability and running-time. Just because two models of computing are Turing equivalent (are capable of deciding the same problems) does not mean that they have the same running time on those problems.
- baddox 16y agoI didn't intend to imply decidability at all. I just meant that since a quantum computer is equivalent to a Turing machine, and complexity classes are often (and I think were originally) formally described and proven in terms of Turing machines.
- bdr 16y agoMaybe decidability was the wrong word to use. There are two separate questions: 1) Can model of computation X recognize language Y? 2) How fast can it do so? When someone says quantum computers are "equivalent" to Turing machines, that's referring only to question 1. In other words, any given language can be recognized by a quantum computer if and only if it can be recognized by a Turing machine. Just because they are equivalent in this sense doesn't imply anything about question 2. For a concrete example, see http://en.wikipedia.org/wiki/Shors_algorithm http://en.wikipedia.org/wiki/Shors_algorithm -- if factorization takes polynomial time on a quantum computer but exponential time on a Turing machine, it must be reasonable to ask whether quantum computers can be that much faster for a whole class of problems. Edit: also note that a complexity class is just a set of languages. We can talk about those languages in different contexts, even if they are specified in terms of a particular model of computation.