Quantum Turing machine

Informal sketch

The quantum Turing machine generalizes the classical Turing machine in the same way that the quantum finite automaton generalizes the deterministic finite automaton. Internal states of a classical TM are replaced by pure or mixed states in a Hilbert space, and the transition function is replaced by a collection of unitary matrices that map the Hilbert space to itself. For a three-tape quantum Turing machine, the set of states is replaced by a Hilbert space, and the tape alphabet symbols are likewise replaced by a Hilbert space.

The blank symbol is an element of that Hilbert space. Input and output symbols are usually taken as a discrete set, so neither input nor output need be a quantum system. The transition function is a generalization of a semiautomaton and is understood as a collection of unitary matrices that are automorphisms of the Hilbert space. The initial state may be either a mixed state or a pure state, and the set of final or accepting states is a linear subspace of the Hilbert space.

This sketch leaves vague several important details, such as how often a measurement is performed, which affects how writes to the output tape are defined.

History

The idea of a quantum Turing machine was first introduced by physicist Paul Benioff in a pair of papers from the early 1980s. A few years later, David Deutsch expanded on this by proposing that quantum gates could work like the binary logic gates in classical computers. Later, Iriyama, Ohya, and Volovich created a linear quantum Turing machine model that generalizes the standard version by using mixed states and allowing irreversible transitions, which lets it represent quantum measurements without classical results. Scott Aaronson later defined a version with postselection, proving that the class of problems solvable in polynomial time on it, PostBQP, matches the classical complexity class PP.