Universal Quantum Turing Machines with Local Hamiltonians

10 Universal Quantum Turing Machines with Local Hamiltonians 

Not every computation can be performed by the computers with local Hamiltonians described so far. Neither the Feynman computer nor the one-dimensional cellular automaton is universal in the sense of complexity theory. In [21], Feynman s ideas are used to describe a two-dimensional quantum cellular automaton, where the classical version of the automaton is universal. As for the one-dimensional automaton, it is most likely to measme a state where part of the automaton has done more computational steps than another. It is not possible to obtain global synchrony as in the classical case since there is no global synchronous updating which can be performed by local means [32]. Thus, it is not clear whether one should apply the term universal to those automata. 

Furthermore, it must be emphasized that even the commonly adopted definition of universality for classical cellular automata differs substantially from the definition that is usually used in complexity theory. For example, for an infinitely large cellular automaton, as described in [21], the initial conditions also have to be coded on an infinite number of sites. Clearly, that is not necessary for a Turing machine with an infinitely long tape. Finite-size machines on the other hand cannot be universal. 

An excellent introduction to the theory of computability and universality can be found in [51]. 

In the next section, the ideas of Feynman and Peres will be generalized. This is necessary for the description of the quantum Turing machine. In Sect. 5.3, a classical, reversible Turing machine M was described. Based on this concept, a local, unitary description is given for M in Sect. 5.10.2. In Sect. 5.10.3, a local Hamiltonian for the corresponding quantum Turing machine is derived. 

---