# How are quantum computers different from non-deterministic Turing machines?

I was reading about non deterministic Turing machines and I thought that they were the same as quantum computers. However I was told they were not, therefore I am curious to know the difference.

They are two entirely different models.

For one, a non-deterministic Turing machine is a model for a magical "theoretical machine" that is useful to prove statements, but that cannot be built in the real world.

A quantum computer, on the other hand, is something that is fully compatible with the laws of quantum mechanics, and therefore can be built in the real world. It is not just an abstract theoretical model, but rather a model of how the information is handled at the quantum level.

At a more formal level, the functioning of a quantum computer can be modelled via a quantum Turing machine, and you can tell from the way this is defined that it is a different beast than the non-deterministic TM.

A practical difference between the two models is that a non-deterministic TM can always "magically" find the computational branch that leads to the answer to the given problem. Quantum mechanics does not in any way allow for something like this. What quantum mechanics does allow is to obtain a result that depends on the outputs of a set of different computational branches, by exploiting the possibility of building superpositions of different states. This "dependence" is however very restrictive and must obey the laws of quantum interference, so it cannot be used to simply figure out which branch leads to the sought answer.

This said, figuring out in what ways exactly a non-deterministic TM is differently powerful than a quantum computer is a tricky business, and I'll remind you to the answers to this related question on quantumcomputing.SE for that.

Informally, a non-deterministic Turing machine is basically a probabilistic Turing machine that always magically gets lucky guesses, and can find the answer to any problem by "guessing" the correct answer and then checking that it is indeed an answer. However, if checking whether something an answer can't be sped up with lucky guesses, the check itself cannot be shortened.

A quantum Turing machine on the other hand, is more like a (very much non-magical) probablistic turing machine, where classical probabilities are replaced by quantum amplitudes (or more generally density matrices). This does make it slightly more suited than a classical probabilistic turing machine at simulating a nondeterministic turing machine because unlike classical probabilities, quantum amplitudes (or elements of density matrices) can cancel out, which lets you write algorithms in some cases where informally, the probabilities correct guesses add up while the probabilities of wrong guesses cancel out, and in some cases this leads to algorithmic speedups vs classical computers. For example, finding an element in an array would take linear time for a classical computer, O(sqrt(N)) time for a quantum computer, and O(1) time for a nondeterministic computer.

However, while it is clear that they both give speedups for classical CS problems the two are very different in terms of power. First, determining whether a nondeterministic turning machine can express strictly more algorithms in polynomial time is a very hard problem (P ?= NP). Secondly, it turns out that quantum information does let you do a few things that even a nondeterministic Turing machine cannot, if instead of looking at computer-sciencey problems, you consider more physics-y problems. The seminal example of this is known as Boson Sampling, which a quantum computer can do in polynomial time, while a nondeterministic turing machine apparently cannot.

(furthermore, quantum computers in the absence of measurements or impure states (density matrices) also have to be reversible. So you can in fact "undo" a guess, and pure state amplitudes still has zero entropy despite being in a superposition of multiple classical states. Information theory in general is different, and most strikingly due to entanglement the entropy of a set of qbits can be lower than the entropy of each individual qbit)