Quantum Turing Machines

The previous section describes a Turing machine in which the basic computational steps are all reversible. Furthermore, the basic steps take place in a local region of the three tapes. Therefore it is easy to obtain local, unitary transformations Uj for any step i that might occur during a computation. This has already been done in Sect. 5.2 for the Fredkin-Toffoli gate as a simple example. 

To construct a quantum Turing machine, we then have to find the Hamiltonians Hj from the Uj and to alter the energy couplings following the switching scheme (see Sect. 5.2). 

Clearly, this requires exhaustive invasion into the computation by the experimentalist. Note another problem It will in general depend on the outcome of intermediate measurements after a step i which unitary matrix Ui+i is to apply. 

In Sect. 5.10 we introduce a universal quantum Turing machine that does not require the experimentalist. Its overall Hamiltonian is local and time independent. 

---

First, one might suspect that a quantum Turing machine is more powerful than a classical Turing machine in the sense of complexity theory. Feynman [1] raised this question. He conjectured that it might be difficult to simulate a finite-size quantum system (for example, a quantum cellular automaton) by classical means without an exponential slowdown. 

In [2-5], the concept of a quantum Turing machine is developed. A rigorous definition can be found in [4]. 

In this contribution to Non-standard computation we review the most important ideas about quantum Turing machines, quantum complexity theory, the Feynman idea, and concepts for the realization of quantum computers. 

How to obtain a quantum Turing machine from a classical reversible Turing machine is outlined in Sect. 5.4. 

Sect. 5.9 reviews and discusses the prospects of actually realizing quantum computers. This subject is outlined more rigorously in this book by Thomas Pellizzari. In Sect. 5.10 an important generalization of Feynman s and Margolus idea is described It is possible to construct quantum Turing machines with time-independent and local Hamiltonians. This has very general consequences for the decidability of certain questions about the time evolution of a quantum system. 

Here, we will not review the problems of switching the Hamiltonians. A discussion can be found in [15], where an estimation of the heat dissipation per computational step can also be found. The result of [15] is essentially that heat dissipation is not a fundamental obstacle to quantum computation according to the switching scheme. However, the process of changing the energy function after each step - if it can be done at all - will certainly slow down the computation considerably. In Sects. 5.3 and 5.4 we review ways of designing quantum Turing machines based on this scheme. 

The concept of a quantum Turing machine is based on the classical, reversible Turing machine. This is because every quantum Turing computer works in a reversible way since its dynamics obey the Schrodinger equation. 

Only recently Bernstein and Vazirani [6] proved the existence of a quantum Turing machine whose simulation overhead is polynomial bounded. This is what computer scientists call an efficient simulation. The result is of crucial importance for quantum complexity theory Only machines that can efficiently simulate any other Turing machine are called universal. To be called universal, it is not sufficient that the machine is simply able to simulate other Turing machines. 

Consider a Turing computable function f(i) that maps the positive integers IN onto a subspace of IN. Then we know from the previous section that there is a quantum Turing machine based on a reversible, classical machine M on which this function can be evaluated. The overall computation of / is described by the unitary operator Uf which is the product of local, unitary transformations Ui. To abbreviate the notation, we will only consider the subspace of the input and output data of the quantum machine. Furthermore, we will write i) to denote a part of the memory in which the number i is stored. For example, using the binary number system,... 

Universal Quantum Turing Machines with Local Hamiltonians... 

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. 

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. 

A summary and certain remarks with an emphasis on the universal quantum Turing machines that have been analyzed in the last three sections are in order ... 

Gramss, T. (1994) A Quantum Turing Machine with a local Hamiltonian. Santa Fe Institute Working Paper Series 94-08-047. 

---