# 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?

-
This lecture note from Berkeley gives an answer. www.eecs.berkeley.edu/~vazirani/f97qcom/lec19.ps –  Mohammad Al-Turkistany Mar 8 '12 at 7:28
@MohammadAl-Turkistany If you're comfortable with the material, you might convert this into an answer if you get the chance. Besides the reputation you'd no doubt receive, it would add a lot of value to a budding site. If you're too busy, I could give it a shot, but I don't know how good I'd be at explaining this kind of stuff. –  Patrick87 Mar 8 '12 at 14:30
I'm not an expert in QC. If it is fine, I'll just post my comment. –  Mohammad Al-Turkistany Mar 8 '12 at 15:44
Actually quantum circuits model and quantum turing machine are equivalent, which have been proved by A.C.Yao. –  Strin Apr 2 '12 at 15:33

(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=\{q_0,q_1,..\}$ - a finite set of states. Let $q_0$ be an initial state.
2. $\Sigma=\{\sigma_0,\sigma_1,...\}$, $\Gamma=\{\gamma_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 $q\in Q$, the tape contains $T\in \Gamma^*$ and the head points to the $i$th 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 $\mathcal{H}$ generated by the configuration space $Q\times\Sigma^*\times \mathrm{Z}$. The specific configuration $C=(q,T,i)$ is represented as the state $$|C\rangle = |q\rangle |T\rangle |i\rangle.$$ (remark: Therefore, every cell in the tape isa $\Gamma$-dimensional Hilbert space.)

The QTM is initialized to the state $|\psi(0)\rangle = |q_0\rangle |T_0\rangle |1\rangle$, where $T_0\in \Gamma^*$ is concatenation of the input $x\in\Sigma^*$ 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$ $$|\psi(i+1)\rangle = U|\psi(i)\rangle$$

Note that the state at any time $n$ is given by $|\psi(n)\rangle = U^n|\psi(0)\rangle$. $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, $\langle q',T',i'|U|q,T,i\rangle$ is zero unless $i'= i \pm 1$ and $T'$ differs from $T$ only at position $i$.

At the end of the computation (when the QTM reaches a state $q_f$) 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.

-
I'm not sure David Deutsch's original definition gets everything correct ... this was the first time anybody tried to define it, and it took some refinements to figure out the right mathematically precise definition. –  Peter Shor Mar 13 '12 at 15:21

As the notes indicate, the way to define a QTM is to define the transition function as a unitary transform of state and letter. So in each step, you imagine multiplying the (state,letter) vector by a transformation to get a new (state, letter). It's not particularly convenient, but it can be defined.

-