What is the difference between quantum TM and nondetermistic TM?

Question

I was going through the discussion on the question How to define quantum Turing machines? and I feel that quantum TM and nondetermistic TM are one and the same. The answers to the other question do not touch on that. Are these two models one and the same?

If no,

1. What are the differences between quantum TM and NDTM?
2. Is there any computation which a NDTM would do quicker than Quantum TM?
3. If this is the case then quantum TM is a DTM, then why is there so much fuzz about this technology, we already have so many DTM. Why to design a new DTM in the end?

Answer 1

As a general preamble, QTMs, TMs and NTMs are all different things (taking huge liberties with a bunch of unspoken assumptions).

I'll assume you know what a Turing Machine is.

1. A NTM is a TM where, at any state, with any symbol, the transition function is allowed to have a number of choices of action that is not precisely $1$, i.e. $0$ or more than $1$ (a deterministic TM must have exactly one action for each symbol at each state, though the $0$ case is easy to deal with). When faced with a situation where there are several choices of transition a NTM will make the choice that will ultimately take it to an accepting state, if such an option exists.
   
   In contrast a QTM is a model of quantum computation, as detailed in the thread you linked. It is not nondeterministic, not all. Probably the key high level differences between a QTM and a TM is that a QTM has as its state a linear combination of the basis states (again, it's all in that other thread) and that it's probabilistic, that is, the accuracy of its ouput is bounded by some probability less than $1$ (broadly speaking).
   
   Just to be really really clear on a point that catches many people, nondeterminism is not randomness, it's not parallelism, it's a theoretical construct that has nothing to do with either of those.
2. The full answer to this depends on some complexity theoretic assumptions. Taking a particular standpoint (that $QMA \supset BQP$ and $NP \supset P$), the answer is yes. $NP$-complete problems can be solved by a NTM in polynomial time, and it also seems that $NP\text{-complete} \cap BQP = \emptyset$, so they can't be solved by a QTM in polynomial time.
   
   Again, this is all dependent on which way the cards fall with a variety of complexity classes. If it turns out that $QMA = BQP$ then the answer is no, for example.
3. The first thing to say here is to be careful about confusing TMs (of any kind) and computers. A TM is not a computer, a QTM is not a quantum computer. TMs (of any kind) model computation. What a given computer can do is governed by this, but this is quite different to saying that the thing I'm typing this on is a TM.
   
   Having said that, if we speak loosely and lazily identify QTMs with quantum computers and TMs with standard computers, then (again under certain complexity assumptions) it seems that quantum computers can quickly do certain tasks that seem hard for standard computers (factoring, discrete logs, a really particular type of searching, and a couple of others). However these problems aren't known to be hard in the $NP$-complete sense either, it seems quantum computers offer capabilities that extend a standard computer, but in a different direction to what would be needed to solve $NP$-complete problems quickly.

Again just to be really clear, I've glossed over a lot of computational complexity here, if you really want to understand how everything fits together, you'll need start digging in to the literature.

Answer 2

On the meaning of nondeterminism

There are two different meanings of 'nondeterminism' at issue here. Quantum mechanics is usually described as being "not deterministic", but the word "nondeterministic" is used in a specialized way in theoretical computer science.

1. One meaning, which applies to quantum mechanics, is just 'not deterministic'. This is usually a reasonable way to interpret the word, and in point of fact, neither quantum Turing machines nor even probabilistic Turing machines are deterministic in the way that they solve decision problems.

2. However, when describing models of computation, nondeterministic is used specifically to mean that the machine can (in a sense) make choices which are not determined by its state or its input, to obtain a particular objective. This meaning is used elsewhere in describing models of computation, such as Nondeterministic Finite Automata.

So, quantum Turing machines are a model of computation which is not deterministic, but which is different from a "nondeterministic Turing machine".

Nondeterministic Turing Machines

A nondeterministic Turing machine is a machine which may explore multiple possible transitions. The transition that it makes at a given step depends, but is not determined, by the state that it is in and the symbol that it is reading. There are two ways this is commonly presented:

• Especially for the purposes of defining the complexity class NP, one may describe the machine as making choices (or guesses) at each step in order to try to reach an accepting state. If you think of what the nondeterministic machine is doing as exploring a decision tree, it is searching for an accepting path in the tree. While no mechanism which is described to suggest how such a path should be found, we imagine that it will find an accepting path if even just one exists.

• It is also quite common to say that a nondeterministic machine explores all possible paths in the decision tree in parallel, and gives a "yes" answer if any of them turn out to be an accepting path.

More modern treatments of nondeterminism also consider not just the existence, but the number of accepting paths; and this is well-suited to the description of exploring all paths in parallel. We can impose extra constraints, for instance that all computational paths have the same length (that the machine always takes the same amount of time to perform a computation) and that each path performs a guess at each step, or every second step, even if the guess is not used. If we do this, we can formulate probabilistic models of computation, such as random Turing machines (motivating complexity classes such as BPP), in terms of the number of accepting paths of a nondeterministic Turing machine. We can also turn this around, and describe nondeterministic Turing machines in terms of randomized computers which can somehow distinguish between outcomes which have zero probability from ones which have non-zero probability.

Quantum Turing machines

The main difference between a quantum Turing machine and a nondeterministic one is this: instead of nondeterministically 'choosing' a single transition out of two or more at each step, a quantum Turing machine makes a transition to a superposition of one or more possible transitions. The complete state of the machine is defined as a unit vector in a complex vector space, defined by linear combinations of basis states described by classical states of the tape, the position of the machine head, and the "internal state" of the machine head. (See e.g. page 9, Definition 3.2.2, of Quantum Complexity Theory for the complete description of how quantum Turing machines make transitions.) The condition under which the quantum Turing machine accepts an input is also more restrictive, and inherently involves probability, requiring a substantial probability of observing the correct outcome in order to succeed.

As a result, quantum Turing machines differ from nondeterministic machines in that the way they make their transitions are not completely unspecified. Even if the transition "seems mysterious", it's also the same sorts of evolution with time that our best theory of matter indicates happens in the real world. While it is common to describe quantum computers as "exploring different computational paths in parallel", it's not particularly useful to do: the amplitudes on the different paths mean that they don't all have the same importance, and unlike nondeterministic Turing machines, it isn't enough to have non-zero amplitude on some outcome; it has to be possible to obtain a very large probability of obtaining the correct outcome, such as 2/3. (The class of problems BQP which a quantum Turing machine can efficiently solve requires a probability gap of the same sort as BPP has for randomized computation.) Furthermore, very much in contrast to nondeterministic Turing machines, a quantum Turing machine can interfere those with one another after they have split, which is simply impossible in the typical formulation of a nondeterministic Turing machine (and it makes the description in terms of a decision tree less useful in the first place).

Comparing the two models

We don't know whether one of these machines is more powerful than the other; the different ways in which they are not-deterministic seem different from one another, and hard to compare.

As for the problems that each machine can quickly do, that the other cannot (so far as we know):

• We don't know any way that a quantum Turing machine could quickly solve the SATISFIABILITY problem. A nondeterministic Turing machine can, easily.
• Work by Aaronson and Archipov (The Computational Complexity of Linear Optics) suggests that nondeterministic Turing machines are unlikely to be able to efficiently simulate certain experiments of linear optics which could be simulated by a quantum Turing machine.

But even if someone shows how to relate the two sorts of machine to one another — and even in the extremely unlikely scenario that someone shows that BQP = NP (the problems that a quantum Turing machine, and a nondeterministic Turing machine, can respectively solve quickly) — the two machines which define these models of computation are quite different from one another.