Quantum Turing Machine

The quantum Turing machine (QTM) is the quantum mechanical generalization of the classical Turing machine, introduced by David Deutsch in 1985. Where a classical Turing machine manipulates bits on a tape according to deterministic or probabilistic transition rules, a QTM manipulates qubits according to unitary quantum evolution. The QTM provides the theoretical foundation for quantum computing and formalizes the Church-Turing-Deutsch principle: the claim that any physical process can be simulated by a universal quantum computing device.

Unlike the classical universal Turing machine, which became a physical reality in the von Neumann architecture, the QTM remains primarily a mathematical construction. Practical quantum computers implement the quantum circuit model rather than the tape-based QTM. However, the QTM remains essential for theoretical analysis: it defines the complexity class BQP and provides the reference point for asking whether quantum mechanics changes the fundamental limits of computation. The QTM does not compute functions outside the Turing-computable class — it does not enable hypercomputation — but it may compute certain functions efficiently that classical machines cannot.