Quantum Turing machine

Definition

Let $\tilde{\C}$ be the set of complex numbers $\alpha$ whose real and imaginary parts are efficiently computable. This means they can be computed to precision $2^{-n}$ in time polynomial in $n$. A quantum Turing machine is a tuple $M = (\Sigma, Q, \delta, q_0, q_f)$ with these parts.

1. $\Sigma$ is a finite tape alphabet with a blank symbol, and $Q$ is a finite set of states with $q_0, q_f \in Q$.
2. $\delta$ is a quantum transition function $\delta \colon Q \times \Sigma \times \Sigma \times Q \times \set{L, R} \to \tilde{\C}$.
3. The value $\delta(p, \sigma, \tau, q, d)$ is the amplitude of this move: in state $p$ reading $\sigma$, write $\tau$, enter $q$ and move in direction $d$.

A configuration is a state, a tape content with finitely many non-blank cells, and a head position, as for a Turing machine. Let $\mathcal H$ be the Hilbert space with orthonormal basis indexed by the configurations. The function $\delta$ defines a linear operator $U_\delta$ on $\mathcal H$ that sends each configuration to the superposition of its successors, weighted by their amplitudes. The condition on $M$ is that $U_\delta$ is a unitary operator.