Quantum Turing MachinesNotations and Basic PropertiesThe laws of quantum physics are reversible in time [24]. 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). Following Benioff [16, 17, 27], a QTM can be described by a step operator T and its adjoint , which in turn are defined as the sum of elementary step operators : with 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 [18] as with . Copyright © 2002 Wolfram Media, Inc. All rights reserved. |