Local, Unitary Description of a Reversible Turing Machine

2 Local, Unitary Description of a Reversible Turing Machine 

In this section, we describe a local, unitary evolution of the quantum computer and how it relates to the classical, reversible machine M that was introduced in Sect. 5.3. The unitary matrices are fundamental for the time-independent Hamiltonian of a universal quantum Turing machine that will be derived in the next section. 

Let the three tapes of M consist of a lattice of spin- variables, each representing a bit in our quantum computer. Each spin can be in the state up for a logical 1 and down for a logical 0. Thus, a 0-bit will correspond to the quantum state 0) and a 1-bit to 11), where [0) and 11) are the eigenstates of the Pauli matrix a/. 

To each field of the tapes are associated spins. The number required is 

To code a symbol a and a head state v, we write a,t ,/i, r). h and r stand for the head flag and for the reverse flag, respectively, a, v, h, and r are written as binaries. 

---