Quantum Turing Machines
Notations and Basic Properties
The laws of quantum physics are reversible in time . One of the earliest proposals of a quantum Hamiltonian model of reversible computation is due to Benioff [25, 26]. The physical model of a QTM, as considered by Benioff, corresponds to a one-tape machine. The finite state head moves along an (infinite) lattice of finite dimensional qubits. The computational basis , which spans a Hilbert space is given by the set of states. Here
To keep separable, we choose for a finite number of lattice sites only (zero tail condition).
The operators w, v, and u must be unitary and are defined as follows.
To ensure reversibility of the QTM computational process, the step operator T and its adjoint must be distinct path generating. That means iterations of T and on any state either annihilate that state or generate a finite or infinite set of states which do not join, branch, or intersect. Each such set of states is called a computational path . For a given distinct path generating step operator T with adjoint , we define the associated Hamiltonian operator following the prescription of Feynman  as
Copyright © 2002 Wolfram Media, Inc. All rights reserved.