Loading field map
Can quantum mechanics be harnessed to compute things that classical machines cannot, and if so, how should we formalize and protect that advantage? This question has driven quantum computation from a speculative idea in the 1980s into a rich subfield of the theory of computation. The story of the subfield is not a single triumphant march but a series of frameworks that each reframed what a quantum computer is, what it can do, and how to build it reliably.
The first rigorous framework for quantum computation was the Quantum Turing Machine, introduced by David Deutsch in 1985. Deutsch adapted the classical Turing machine—the canonical model of general-purpose computation—by allowing its internal state to be a superposition of basis states and its transition function to be a unitary operation. This model proved that quantum mechanics could, in principle, support universal computation. Yet the Quantum Turing Machine was cumbersome for designing algorithms. Specifying a quantum program as a sequence of tape-head moves and state transitions was as awkward as programming a classical computer at the level of individual Turing machine instructions.
By the late 1980s and early 1990s, researchers began to replace the Turing-machine formalism with a more practical one: the Quantum Circuit Model. In this framework, a computation is a sequence of quantum gates—unitary operations acting on a small number of qubits—applied to an initial state, followed by a measurement. The circuit model is the direct quantum analogue of the classical Boolean circuit, and it quickly became the working language of the field. Peter Shor's 1994 factoring algorithm and 1995 error-correction codes were both expressed in the circuit model, cementing its dominance. The Quantum Turing Machine and the Quantum Circuit Model were soon shown to be polynomially equivalent, but the circuit model won out because it made algorithm design and analysis far more tractable.
Once a computational model was in place, the next natural question was: what problems can a quantum computer solve efficiently? Quantum Complexity Theory emerged in the early 1990s to answer this. The central class is BQP (Bounded-Error Quantum Polynomial Time), the set of decision problems solvable by a quantum circuit with at most polynomial size and bounded error probability. BQP sits in a web of classical complexity classes: it contains P, is contained in PSPACE, and is believed to be incomparable with NP. A landmark result showed that BQP contains the problem of factoring integers, which is not known to be in P and is widely believed not to be in BPP (classical randomized polynomial time). This separation—factoring is in BQP but not known to be in BPP—is the strongest concrete evidence that quantum computers can outperform classical ones.
Quantum Complexity Theory depends on the circuit model as its underlying computational model: BQP is defined in terms of circuit size and depth. The framework also introduced quantum analogues of classical complexity concepts, such as QMA (the quantum version of NP), and explored the power of quantum interactive proofs. These classes gave researchers a precise language for asking which problems admit a quantum speedup and which do not.
Early quantum algorithms assumed perfect qubits and noise-free operations. Real physical systems, however, suffer from decoherence and gate errors. By the mid-1990s, it was clear that without some form of protection, quantum computation would be impossible at scale. The response came in two tightly linked frameworks.
Quantum Error Correction (1995 onward) showed that quantum information could be protected by encoding a single logical qubit into multiple physical qubits. Shor's 9-qubit code and the later stabilizer formalism demonstrated that errors could be detected and corrected without collapsing the quantum state. This was a non-trivial extension of classical error correction: quantum codes must handle phase errors as well as bit flips, and they cannot simply copy the state to detect errors.
Error correction alone, however, is not enough. The physical gates used to perform the correction themselves introduce errors. Fault-Tolerant Quantum Computing (1996 onward) addressed this by showing how to perform quantum gates directly on encoded data in a way that prevents errors from cascading. The key result is the threshold theorem: if the physical error rate is below a certain threshold (typically around 10⁻⁴ to 10⁻², depending on the code), then arbitrarily long quantum computations can be performed reliably by using a layered architecture of concatenated codes. Fault-tolerant computing thus turned error correction from a theoretical curiosity into a scalable blueprint. The circuit model, error correction, and fault tolerance together form the dominant stack in quantum computation today: circuits describe the logical computation, error-correcting codes protect the qubits, and fault-tolerant protocols ensure that the protection itself does not fail.
Not all quantum computation frameworks rely on active error correction. Several alternative paradigms emerged in the late 1990s and early 2000s, each offering a different philosophy for dealing with noise and for performing computation.
Topological Quantum Computation (1997 onward), proposed by Alexei Kitaev, encodes information in the global topological properties of a physical system—for example, the braiding of anyons in a two-dimensional medium. Because local perturbations cannot change the global topology, the computation is inherently protected from decoherence. This is a form of passive error correction: the physics of the system itself suppresses errors, rather than requiring active syndrome measurements and corrective gates. Topological quantum computation is not just a variant of the circuit model; it is a fundamentally different way of thinking about quantum information, though it has been shown to be polynomially equivalent to the circuit model under perfect implementation. Its practical challenge is that no one has yet built a controllable anyonic system.
Adiabatic Quantum Computation (2000 onward) takes a different approach. Instead of applying a sequence of gates, it encodes the solution to a problem in the ground state of a Hamiltonian. The system starts in an easy-to-prepare ground state of a simple Hamiltonian, and the Hamiltonian is slowly deformed into the one whose ground state encodes the answer. If the deformation is slow enough (adiabatic), the system remains in the ground state throughout, and a final measurement reveals the solution. Adiabatic computation was shown to be polynomially equivalent to the circuit model, but it removes the need for coherent gate-by-gate control. Instead, it relies on continuous-time evolution, which may be easier to implement in some physical platforms. The tradeoff is that the required evolution time depends on the minimum energy gap, which is hard to compute in advance.
Measurement-Based Quantum Computation (2001 onward), also called the one-way quantum computer, inverts the usual relationship between gates and measurements. In the circuit model, measurements are typically the final step. In the measurement-based model, the computation begins by preparing a large entangled state (a cluster state). The computation then proceeds by performing a sequence of single-qubit measurements on this state; the measurement outcomes determine which subsequent measurements to perform, and the final output is read from the measurement record. This framework shifts the burden from coherent gate operations to entanglement generation and feed-forward measurement. It has been shown equivalent to the circuit model, but it offers practical advantages: once the cluster state is prepared, the computation is driven entirely by measurements, which are often easier to perform with high fidelity than two-qubit gates.
Today, the leading framework for quantum computation is the combination of the Quantum Circuit Model, Quantum Error Correction, and Fault-Tolerant Quantum Computing. This stack is the default language for algorithm design, complexity analysis, and hardware roadmaps. Researchers agree that any scalable quantum computer will need some form of error correction and fault tolerance, and that the circuit model provides a clean abstraction for reasoning about logical operations.
Yet there is no consensus on which physical implementation will ultimately realize this stack, and the alternative paradigms remain active research directions. Topological quantum computation is pursued for its promise of passive protection; adiabatic computation is explored for optimization problems and for its natural fit with analog hardware; measurement-based computation is studied for its potential to simplify gate operations. All three alternatives have been shown equivalent to the circuit model under ideal conditions, but the equivalence may break down when realistic noise and resource constraints are considered. A key open question is whether any alternative paradigm can achieve a lower overhead for error correction or a higher threshold for fault tolerance than the circuit-model approach.
What the leading frameworks disagree on is the best division of labor between active and passive error protection, and whether the circuit model's gate-by-gate control is a feature or a limitation. The circuit model plus active error correction is the most developed path, but it demands extremely low physical error rates. Topological and adiabatic approaches aim to relax that demand by making the physics do more of the work. Measurement-based computation asks whether shifting complexity from gates to entanglement can yield practical advantages. These are not settled debates; they are the living tensions that define the subfield today.