I was going through the discussion on the question How to define quantum-turing-

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,

What are the differences between quantum TM and NDTM?
Is there any computation which a NDTM would do quicker than Quantum TM?
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?

Explanation / Answer

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.

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.

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

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.