# Explicit Construction of Classical Rules in Quantum Turing Machine

I knew that we usually use circuit instead of Turing machine in Quantum computation.

In a deterministic Turing machine one has transition rules, $$\delta: Q\times\Gamma\rightarrow Q\times\Gamma\times\{\pm 1, 0\},$$ where $$Q, \Gamma$$ are set of states and symbols respectively. In the quantum Turing machine, we instead have, $$\delta:Q\times\Gamma\rightarrow\mathbb{C}^{Q\times\Gamma\times\{\pm1,0\}}.$$ Suppose all that needed for the induced evolution $$U_\delta$$ being unitary. However, I feel tremendously obstructed when trying to construct even a toy example. Then I realize one difference between quantum circuit family and Turing machine when manipulating the computation is the following.

When constructing a quantum circuit, one could decide which qubit to act on, this decision is a classical advice that is precomputed before the quantum computating even started. When constructing a quantum Turing machine, we need to make sure that even the arrangement of gates must obeys the unitary property.

For instance, if we would like to apply $$2$$-local $$U$$ on a tape. Say, suppose the configuration in computational basis after truncated infinitely long tape is $$|n,q\rangle|x_0,x_1\rangle$$ where $$n,q,x_i$$ represents the current pointer location, state, and value of 2 cells on the tape. We would like to maps it to $$|n,q\rangle U|x_0,x_1\rangle$$, but unfortunately we could only apply our basic gate on $$n,q, x_n$$. In the circuit paradigm, we might use a trick that swaps information between $$q$$ and $$x_0$$ to perform multi-qubit gates. So we might say,

1. Let $$(q,s)\in Q=Q_L\times \Gamma$$ composed of "logical state" and a dummy register state. Write computational basis as $$|n,q,s,x_0,x_1\rangle$$ and we starts at $$|0,q,s,x_0,x_1\rangle$$
2. Interchange $$s,x_n$$, so $$|0,q,s,x_0,x_1\rangle\mapsto|n,q,x_0,s,x_1\rangle$$.
3. Logical flip the pointer bit, $$|n,q,s,x_0,x_1\rangle\mapsto|\lnot n,q,s,x_0,x_1\rangle$$.
4. Perform $$2$$-local operator $$U$$ on $$s,x_n$$, so $$|1,q,s,x_0,x_1\rangle\mapsto|1,q\rangle U|s,x_1\rangle|x_0\rangle.$$
5. Swap back everything as prevously done, $$|1,q,s,x_0,x_1\rangle\mapsto|0,q,x_0,s,x_1\rangle$$.

But we cannot do this directly on quantum Turing machine, it is because we must also guarantee that the way we arrange these rules mentioned above should induce a unitary evolution. Even to simulate a classical Turing machine is non-trivial because though without superposition, in order to preserve unitary property, you need to permute classical states instead of making straight transition logic. I understand that quantum circuit is usually more used in the context of quantum computation, but at this stage even manipulating really simple rules are quite painful, in the above example, I even have to construct the states to transition cyclicly just to preserve unitary property.

If we would like to instantiate classical arrangements of quantum gates in a quantum Turing machine, is there better ways, perhaps more expressive, to constuct them explicitly?