  Quantum Turing machines are discussed and reviewed in this paper. Most of the
paper is concerned with processes defined by a step operator $T$ that is used
to construct a Hamiltonian $H$ according to Feynman's prescription. Differences
between these models and the models of Deutsch are discussed and reviewed. It
is emphasized that the models with $H$ constructed from $T$ include fully
quantum mechanical processes that take computation basis states into linear
superpositions of these states. The requirement that $T$ be distinct path
generating is reviewed. The advantage of this requirement is that
Schr\"{o}dinger evolution under $H$ is one dimensional along distinct finite or
infinite paths of nonoverlapping states in some basis $B_{T}$. It is emphasized
that $B_{T}$ can be arbitrarily complex with extreme entanglements between
states of component systems. The new aspect of quantum Turing machines
introduced here is the emphasis on the structure of graphs obtained when the
states in the $B_{T}$ paths are expanded as linear superpositions of states in
a reference basis such as the computation basis $B_{C}$. Examples are discussed
that illustrate the main points of the paper. For one example the graph
structures of the paths in $B_{T}$ expanded as states in $B_{C}$ include finite
stage binary trees and concatenated finite stage binary trees with or without
terminal infinite binary trees. Other examples are discussed in which the graph
structures correspond to interferometers and iterations of interferometers.

Quantum Physics