The Mathematica Journal
Current Issue
Tricks of the Trade
In and Out
Riemann Surfaces IIc
The Mathematica Programmer
New Products
New Publications
News Bulletins
Editor's Pick
Write Us
About the Journal
Staff and Contributors
Back Issues
Download This Issue

Quantum Turing Machines

Notations and Basic Properties

The 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 :


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.

[Article Index][Prev Page][Next Page]