The computational process has long been an interesting and challenging subject of basic research in mathematics, physics, and computer sciences (see [1] for introduction and overview). One of the fundamental insights is that information is indeed physical [2, 3, 4, 5] and therefore subject to basic laws of physics.

In recent years it has become clear [6], that information theory, like many other branches in physics, expands into the quantum regime, and it is now customary to call this subject matter Quantum Information Theory (QIT). Recent branches of QIT include Quantum Computing [7, 8, 9], Quantum Encryption [10], and Quantum Teleportation [11].

In QIT the classical bit is replaced by a quantum-bit (a.k.a. qubit), which is a two-level quantum system, and can physically be implemented (e.g., as a spin-1/2). For further background information on fundamentals of QIT, see [12] and references therein. The actual availability of a (large scale) quantum computer might still be in the (far) future, but numerous projects are on their way to develop and deliver QIT simulation programs to study various aspects of quantum algorithms and other QIT topics. For an overview and review of several known QIT simulation programs, see [13].

Here, we present and discuss a Quantum Turing Machine Simulator (QTS), which enables one to construct and run Quantum Turing Machines, and to study some of their fundamental properties. Additional documentation and source code is available [14].

Similar to its classical counterpart, a Quantum Turing Machine (QTM) typically consists of a QTM head, living in an n-dimensional Hilbert space, and an infinite lattice of qubits, each qubit living in (at least) a two-dimensional Hilbert space.The QTM head scans the lattice and acts locally with only the qubit at the head's location. The computational details of a specific QTM are given by the local transition function (a.k.a. step operator) T and its adjoint .

In Deutsch's [15] architecture of a QTM, the step operator T is unitary and represents the finite time translation operator. The machine state then advances in time according to . Given U, it is generally not possible to construct a local Hamilton operator H that generates U, that is, . Benioff's [16] approach is based on a step operator T which is not associated with a time step but represents an individual step in the computation itself. In order to keep the quantum computation reversible, T must be distinct path generating [16, 17]. By construction, Benioff's T is local and need not be unitary nor self-adjoint. Taking T and its adjoint , Benioff then follows Feynman's [18] prescription for constructing a local self-adjoint Hamilton operator according to . With this H one can formally compute by using a power series expansion from which it is clear that this U is no longer local.

Our approach is based on the Quantum Turing Model and Benioff's local and distinct path-generating step operators. We are aware of the fact that any implementation of any quantum simulator eventually face the fact of unmanageable large resource consumption (both CPU time and main storage) due to the exponential size of the Hilbert space of composite quantum systems [19]. The QTS toolkit is coded and optimized for Mathematica [20] 4.0 but runs on Version 3 as well.

Besides building QTMs and gaining some educational quantum experience by running them, one can use the simulator to investigate the flow of coherence in quantum networks. This exciting new type of application for QTMs has recently been investigated by Mahler and Kim [21, 22] and is based on simulating a quantum gate circuit as a QTM where the Turing head rotates on a closed quantum tape. One can then compute the generalized Bloch vector [23] to obtain information about coherence and entanglement. Using our QTS one can perform such experiments. However, here we present an introductory calculation of the coherence vector of a Turing head only.