A Classical, Reversible Turing Machine

Mathematically speaking, the switching process corresponds to a system with a time-dependent Hamiltonian, while with Feynman s idea a time-independent Hamiltonian can be constructed. 

For both, the switching scheme and Feynman s idea, it is possible to construct universal Turing machines. We will therefore now review an important concept from classical complexity theory concerning universal Turing machines. 

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. 

In this section we describe a reversible Turing machine M which simulates a normal non-reversible Turing machine M. It is assumed that the reader has some basic knowledge about the concept of the usual, non-reversible Turing machine. An excellent introduction to the theory of Turing machines, computability, and undecidability can be found in [51]. 

We will also review the main result of [16] that no essential additional expenditure in space and time is necessary to solve problems on a reversible machine. More precisely Each M running in time T and space S can be simulated by M in time 0 T) and space 0 S + T). Based on Bennett s ideas it was later shown in [18] that M can be simulated by more complex reversible means in time and 

---

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

All the approaches can be summarized under the keyword quantum parallelism. This term was introduced by Deutsch in [4], Generally speaking, quantum parallelism is a method to compute in parallel on a serial computer. The main idea is to prepare the initial state of a quantum computer as a superposition of n states where each state corresponds to the initial state of a classical, reversible Turing machine. Then it is in principle possible to perform n computations in parallel as will be explained below. Of course, eventually a measurement has to be performed in order to read out a final result. This will lead to a collapse of the wave function, discarding most of the information about the superimposed states. The problem is how to read out a result and thereby gain more information than is available in a state that corresponds to the final state of one classical machine. We will now be more specific. 

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. 

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,... 

---