The authors define a quantum Turing machine (QTM) analogously to the classic Turing machine as a triplet ( &Sgr; , Q , &dgr; ), where &Sgr; is a finite alphabet with an identified blank symbol #, Q is a finite set of states with an identified initial state q0 and a final state qf ≠ q0, and &dgr;, the quantum transition function, is a function from Q × &Sgr; into the set of functions from &Sgr; × Q × { L, R } to &Ctilde;, where &Ctilde; is a subset of complex numbers whose real and imaginary parts can be deterministically calculated to within 2-n in time polynomial in n. The QTM operates on a two-way infinite tape of cells with a single read/write head. Configurations, initial configurations, and final configurations are defined as for classic deterministic Turing machines. A superposition is an element of a set of finite complex linear combinations of configurations, which forms an inner-product space using the Euclidean norm. The QTM defines a linear operator, called the time evolution operator, on the set of superpositions S. A QTM is well-formed if and only if its time evolution operator is unitary. A QTM is in normal form if the machine steps right and leaves the tape unchanged in moving from state qf to q0. Well-behaved normal form QTMs can be dovetailed to form a normal-form QTM that carries out the computation of the first followed by the computation of the second. The authors provide a construction of a universal QTM in Theorem 7.1. “There is a normal form QTM M such that for any well-formed QTM, any &egr; > 0, and any T, M can simulate the QTM with accuracy &egr; for T steps with slowdown polynomial in T and 1 &slash; &egr;.”
The remainder of the paper defines languages accepted by QTMs and classes of languages accepted by some deterministic polynomial-time QTM. In particular, the class P of languages accepted by polynomial-time Turing machines is in the class EQP of languages accepted by error-free quantum polynomial time QTMs, and the class BPP is contained in the class BQP of languages that are accepted with probability ⅔ by some polynomial-time QTM.
