Other meanings of Turing machine
COMPUTATIONAL MODEL
A Quantum Turing machine is an abstract model of computation in which a machine’s configuration can occupy a quantum superposition, allowing computational paths to interfere before measurement. Introduced by David Deutsch as a quantum generalization of the classical Turing machine, it provides a mathematically precise framework for studying quantum computation rather than a literal blueprint for a practical computer.1 Quantum Turing machines are closely related in computational power to uniform families of quantum circuits, although the machine model is often more convenient for defining algorithms, simulation, and complexity classes.2
A quantum Turing machine extends the classical tape-and-head arrangement by assigning complex amplitudes to configurations. Instead of occupying one definite state, the machine can evolve as a superposition of tape contents, head positions, and internal states; the amplitudes determine interference and the probabilities observed when a measurement is made.1
The transition rule must preserve total probability, normally by acting as a unitary transformation on the machine’s Hilbert space. A separate measurement process converts amplitudes into classical outcomes, so the model distinguishes reversible quantum evolution from irreversible observation. The tape may contain quantum cells, while the control state and transition operators specify which quantum gate-like transformations occur at each step. Definitions differ in technical details, especially concerning measurement timing, tape alphabets, and how halting is represented.
Quantum Turing machines and quantum circuits describe essentially the same feasible computations when appropriate uniformity and resource conventions are imposed. A machine’s successive local transitions can be compiled into a circuit, while a circuit can be executed by a machine that stores qubits and applies gates according to a program.2
The circuit model is usually clearer for algorithm design, whereas the Turing-machine formulation is valuable for complexity theory because it makes input representation, running time, space, and uniform generation explicit. This equivalence supports the class BQP, which contains decision problems solvable with bounded error by polynomial-size, uniformly generated quantum circuits and therefore also by corresponding polynomial-time quantum machines.3 Neither model permits unrestricted copying of an unknown qubit, and both rely on controlled interactions rather than classical branching over independently readable copies.
The model arose from the observation that classical universal machines may simulate quantum systems inefficiently, while a machine governed by quantum mechanics could represent their dynamics more naturally. David Deutsch’s 1985 formulation supplied a universal quantum computer model and connected physical law with the theory of computation.1 Earlier proposals by Richard Feynman had emphasized the difficulty of efficiently simulating quantum physics on classical computers and motivated quantum simulation as a central application.4
Subsequent work by Ethan Bernstein and Umesh Vazirani formalized quantum complexity classes and established rigorous relationships between quantum and classical computation.2 Algorithms such as Shor’s factoring algorithm and the quantum Fourier transform are normally presented as circuits, but their computational behavior can be encoded within a quantum Turing-machine framework.
The hardest technical issue is often not superposition itself but the treatment of halting and observation. A machine that measures after every step loses the interference effects that make quantum computation distinct, while a machine that never measures must still provide a well-defined final output. Some formulations use a halting qubit or designate subspaces for accepting and rejecting outcomes; others impose conditions ensuring that halting states do not interfere with later evolution.
Quantum Turing machines also illuminate why physical realizability matters in quantum complexity theory. Their transition amplitudes must be specified with enough precision to be computable or efficiently approximable; arbitrary real or complex numbers would otherwise hide unlimited information in the machine description.2 In practice, universal gate sets and fault-tolerant constructions make circuit-based models more operational, while the Turing formulation remains a foundational reference point for comparing computational resources.
The term “quantum Turing machine” refers here to the formal computational model, not to a particular physical quantum computer.
Help improve the encyclopedia. Reports go straight to the site manager.