How to define quantum Turing machines?

In quantum computation, what is the equivalent model of a Turing machine?
It is quite clear to me how quantum circuits can be constructed out of quantum gates, but how can we define a quantum Turing machine (QTM) that can actually benefit from quantum effects, namely, perform on high-dimensional systems?


(note: the full desciption is a bit complex, and has several subtleties which I prefered to ignore. The following is merely the high-level ideas for the QTM model)

When defining a Quantum Turing machine (QTM), one would like to have a simple model, similar to the classical TM (that is, a finite state machine plus an infinite tape), but allow the new model the advantage of quantum mechanics.

Similarly to the classical model, QTM has:

  1. Q={q0,q1,..} – a finite set of states. Let q0 be an initial state.
  2. Σ={σ0,σ1,...}, Γ={γ0,..} – set of input/working alphabet
  3. an infinite tape and a single “head”.

However, when defining the transition function, one should recall that any quantum computation must be reversible.
Recall that a configuration of TM is the tuple C=(q,T,i) denoting that the TM is at state qQ, the tape contains TΓ and the head points to the ith cell of the tape.

Since, at any given time, the tape consist only a finite amount of non-blank cells, we define the (quantum) state of the QTM as
a unit vector in the Hilbert space H generated by the configuration space Q×Σ×Z. The specific configuration C=(q,T,i) is represented as the state |C=|q|T|i.
(remark: Therefore, every cell in the tape isa Γ-dimensional Hilbert space.)

The QTM is initialized to the state |ψ(0)=|q0|T0|1, where T0Γ is concatenation of the input xΣ with many “blanks” as needed (there is a subtlety here to determine the maximal length, but I ignore it).

At each time step, the state of the QTM evolves according to some unitary U

Note that the state at any time n is given by |ψ(n)=Un|ψ(0). U can be any unitary that “changes” the tape only where the head is located and moves the head one step to the right or left. That is, q,T,i|U|q,T,i is zero unless i=i±1 and T differs from T only at position i.

At the end of the computation (when the QTM reaches a state qf) the tape is being measured (using, say, the computational basis).

The interesting thing to notice, is that each “step” the QTM’s state is a superposition of possible configurations, which gives the QTM the “quantum” advantage.

The answer is based on Masanao Ozawa, On the Halting Problem for Quantum Turing Machines.
See also David Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer.

Source : Link , Question Author : Ran G. , Answer Author : Ran G.

Leave a Comment