Editing Nondeterministic Turing machine (section)

==Comparison with quantum computers==
[[File:BQP complexity class diagram.svg|thumb|The suspected shape of the range of problems [[BQP|solvable by quantum computers in polynomial time]] (BQP). Note that the figure suggests <math>\mathsf P \neq \mathsf{NP}</math> and <math>\mathsf{NP} \neq \mathsf{PSPACE}</math>. If this is not true then the figure should look different.]]

Because [[quantum computer]]s use [[quantum bit]]s, which can be in [[Quantum superposition|superposition]]s of states, rather than conventional bits, there is sometimes a misconception that [[quantum computer]]s are NTMs.<ref>[http://www.scottaaronson.com/blog/?p=198 The Orion Quantum Computer Anti-Hype FAQ], [[Scott Aaronson]].</ref> However, it is believed by experts (but has not been proven) that the power of quantum computers is, in fact, incomparable to that of NTMs; that is, problems likely exist that an NTM could efficiently solve that a quantum computer cannot and vice versa.<ref>{{cite arXiv|first=Tereza|last=Tušarová|title=Quantum complexity classes|year=2004|eprint=cs/0409051}}.</ref>{{better source needed|date=September 2017}} In particular, it is likely that [[NP-complete]] problems are solvable by NTMs but not by quantum computers in polynomial time.

Intuitively speaking, while a quantum computer can indeed be in a superposition state corresponding to all possible computational branches having been executed at the same time (similar to an NTM), the final measurement will collapse the quantum computer into a randomly selected branch. This branch then does not, in general, represent the sought-for solution, unlike the NTM, which is allowed to pick the right solution among the exponentially many branches.