Quantum Computation

Quantum computation is the study of what machines could do if they obeyed quantum mechanics rather than ordinary classical physics.

12 frameworks, from 1961 to today · Theory Of Computation · Computer Science

still a working view ended · each leads to its entry below

Overview

Quantum computation is the study of what machines could do if they obeyed quantum mechanics rather than ordinary classical physics1. The stakes are not merely engineering. In the 1980s theorists realized that certain problems — factoring large numbers, simulating quantum systems — might be solvable dramatically faster on a quantum machine than on any known classical one, and that quantum mechanics itself might allow communication and cryptography impossible in a classical world. The field's history is a long conversation between physics and the theory of computation: physicists supplied the strange laws, computer scientists asked what those laws imply for what can be computed and at what cost.

Simulating Physics and the First Quantum Ideas

The founding question was practical. In the early 1980s, physicists wanted to simulate quantum systems — molecules, magnets, fields — and found that the state of a quantum system grows exponentially in the number of its parts, so classical simulation becomes hopeless1. Richard Feynman argued in 1982 that a computer built from quantum elements could simulate quantum physics efficiently, precisely because it would use the same exponential state space rather than fight it. Around the same time Paul Benioff described a quantum-mechanical model of a Turing machine, showing that reversible quantum dynamics could in principle carry out computation. These were existence arguments, not designs.

The decisive theoretical step came from David Deutsch in 19852. He defined the quantum Turing machine — a Turing machine whose tape and head obey quantum mechanics, so that it can be in a superposition of configurations and its computation is a single unitary evolution2. This gave the field its first rigorous model and, crucially, a definition of quantum complexity classes: the set of problems solvable by such a machine within given resources. Deutsch also exhibited a problem — later called the Deutsch–Jozsa problem — that a quantum machine solves with certainty in one query where any classical machine needs several. The result was tiny, but it proved that quantum machines are not merely faster versions of classical ones; they compute differently.

The Circuit Model and the First Real Algorithms

The Turing machine is a theorist's convenience; the model practitioners actually use is the quantum circuit. A quantum circuit is a sequence of elementary operations — gates — applied to a register of qubits, the quantum analogue of bits34. A qubit can be in a superposition of 0 and 1, and gates can entangle qubits so their joint state cannot be described by describing each separately. Measurement at the end yields probabilistic outcomes1. Deutsch, and later David DiVincenzo, showed that a small set of gates is universal: any quantum computation can be built from them. This made the circuit model the lingua franca of the field.

The turning point that convinced the world came in 1994, when Peter Shor, at Bell Labs, gave quantum algorithms for factoring integers and for the discrete logarithm problem. Factoring is believed to be hard for classical computers, and much of the public-key cryptography of the era — RSA above all — rested on that belief1. Shor's algorithm runs in polynomial time on a quantum computer, using a quantum Fourier transform to find the period of a modular function. It was the first result that made quantum computation a matter of urgent practical concern, and it launched a wave of work on quantum algorithms. In 1996 Lov Grover added a second landmark: a search algorithm that finds a marked item among N possibilities in about √N steps, a quadratic speedup that applies to a broad class of unstructured search problems51. Together these established the pattern of the field: find a mathematical structure (periodicity, search) that quantum interference can exploit.

Complexity, Error, and the Question of Feasibility

A quantum computer is useless if its state is destroyed by noise. The early 1990s saw a crisis of confidence on exactly this point: quantum states are fragile, and any realistic device would decohere. The answer was quantum error correction. In 1995–96, Shor and Andrew Steane independently constructed quantum error-correcting codes, and later work by Alexei Kitaev and others developed the theory of fault tolerance: if physical error rates are below a threshold, arbitrarily long computations can be made reliable by encoding logical qubits in many physical ones. This was a conceptual breakthrough — it showed that quantum computation is not ruled out by noise — and it remains the central engineering challenge.

In parallel, theorists mapped the complexity landscape. Quantum complexity theory asks how quantum machines compare with classical ones: the class BQP (bounded-error quantum polynomial time) is the quantum analogue of BPP, and it is known that BQP contains problems believed outside classical polynomial time, while it is not known to contain NP-complete problems1. The field also developed quantum versions of interactive proofs, and the study of entanglement as a computational resource. This work gave the field its theoretical backbone and its most important open questions.

Physical Implementations: Ions, Superconductors, and Topology

Theory needed hardware, and several distinct approaches emerged, each with its own physics and its own advocates.

Trapped-ion quantum computing uses individual ions held in electromagnetic traps and manipulated with lasers6. The approach is among the oldest and most mature: David Wineland's group demonstrated quantum logic gates on trapped ions in the mid-1990s, and ion traps have produced some of the highest-fidelity qubits and longest coherence times. Its weakness is speed — gates are relatively slow — and scaling to many ions is hard.

Superconducting quantum computing builds qubits from tiny circuits cooled to millikelvin temperatures, exploiting Josephson junctions. It became the dominant industrial approach: Google, IBM, and others built ever-larger superconducting processors, and in 2019 Google claimed "quantum supremacy" — a computation performed on a superconducting chip that would be impractical for a classical supercomputer17. Superconducting qubits are fast and fabricable with semiconductor-style techniques, but coherence times are short and error rates remain above the fault-tolerance threshold.

Topological quantum computing, proposed by Kitaev in 1997, takes a different route: encode information in the topology of exotic quasiparticles (anyons), so that local noise cannot corrupt it8. The appeal is intrinsic protection; the difficulty is that the required anyons have not been convincingly demonstrated. It remains a major research program, especially in the form of Majorana-based approaches9.

The NISQ Era and the Present

By the late 2010s the field had a new framing. John Preskill coined the term NISQ — noisy intermediate-scale quantum — in 2018 to describe the machines then being built: tens to hundreds of qubits, too noisy for fault-tolerant algorithms like Shor's, but potentially useful for specialized tasks. The NISQ program shifted attention to variational algorithms, quantum simulation of chemistry and materials, and "quantum advantage" demonstrations. Whether NISQ devices will deliver practical value remains contested.

Alongside computation, quantum cryptography and communication developed its own trajectory. Bennett and Brassard's 1984 protocol (BB84) showed that quantum mechanics allows provably secure key distribution, and later work extended this to quantum networks and, in principle, quantum money and blind computation. Experimental quantum key distribution now spans hundreds of kilometres, and satellite-based demonstrations have been reported.

Today the field is split between the fault-tolerant dream — building error-corrected machines capable of running Shor's algorithm — and the nearer-term NISQ program. The open questions are sharp: Can error rates be pushed below threshold at scale? Which algorithms will show genuine advantage? And what is the true power of quantum computers relative to classical ones — a question that quantum complexity theory has clarified but not settled. The history that began with Feynman's question about simulating nature has become one of the most active frontiers of both physics and the theory of computation7.

References

  1. Quantum computing (introduction, Quantum information processing, History, Quantum information, Cryptography, Search problems, Complexity, Quantum supremacy), Wikipedia
  2. Quantum Turing machine (History, introduction), Wikipedia
  3. Quantum circuit, Wikipedia
  4. Quantum logic gate, Wikipedia
  5. Grover's algorithm, Wikipedia
  6. Trapped-ion quantum computer, Wikipedia
  7. Superconducting quantum computing (introduction, History), Wikipedia
  8. Topological quantum computer, Wikipedia
  9. Majorana 1, Wikipedia

The frameworks of Quantum Computation

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1961-1985

    Physics of Computation

    Can physics be simulated efficiently by computers?

    Fly to its tower in Nousfarer

  2. 1984-Present

    Quantum cryptography

    How can two parties communicate securely using quantum mechanics?

    Fly to its tower in Nousfarer

  3. 1985-Present

    Quantum Turing machine

    What is a rigorous model of a quantum computer?

    Fly to its tower in Nousfarer

  4. 1989-Present

    Quantum circuit

    How can quantum operations be composed to perform computation?

    About Quantum circuit
    The quantum circuit model is the working language of quantum computing. It answers a pressing practical question: given a handful of quantum bits (qubits) that obey the strange rules of superposition and entanglement, how do you actually orchestrate them to solve a problem? The model replaces the abstract tape-head of the Quantum Turing Machine with a concrete, clocked sequence of quantum gates—unitary transformations applied to a small number of qubits—followed by a final measurement. This makes algorithm design and analysis as straightforward as classical circuit design, and it rapidly became the default framework for expressing quantum algorithms, error-correction protocols, and complexity-theoretic arguments.
    The core curriculum for the quantum circuit model builds from the bottom up, starting with the basic constituents and ending with the model's power:
    1. Qubit, quantum register, and initial state preparation — A qubit is the fundamental unit of quantum information, a two-level system whose state is a unit vector in a two-dimensional Hilbert space. A quantum register is a collection of qubits; its state lives in the tensor product space. Computation begins by preparing the register in a known initial state, typically ∣0⟩⊗n|0\rangle^{\otimes n}.
    2. Quantum gate and unitary operation — A quantum gate is a unitary operation applied to a small number of qubits. Unitarity ensures that the evolution is reversible and preserves probability. The set of allowed gates is finite and universal: any unitary on nn qubits can be approximated to arbitrary accuracy by a sequence of gates from this set.
    3. Measurement — The output of a quantum circuit is obtained by measuring some or all qubits in the computational basis. Measurement is probabilistic; the probability of each outcome is given by the Born rule. The circuit model treats measurement as the final step, after all unitary gates have been applied.
    4. Quantum gate decomposition and quantum circuit equivalence — A quantum algorithm expressed as a high-level unitary must be decomposed into the allowed elementary gates. Two circuits are equivalent if they implement the same unitary transformation (up to a global phase). Decomposition strategies—such as using the Solovay-Kitaev theorem—are a core design skill.
    5. Quantum parallelism and quantum algorithm — The ability to place a register into a superposition of all 2n2^n basis states and then apply a single unitary operation that acts on all terms simultaneously is called quantum parallelism. This is the engine behind quantum algorithms such as Shor's factoring algorithm and Grover's search algorithm, but the model itself is agnostic to any particular algorithm; it provides the formal framework in which any quantum algorithm is expressed.
    6. Quantum circuit complexity and polynomial-time quantum computation — The size (number of gates) and depth (number of time steps) of a circuit measure its resource cost. A problem is solvable in polynomial time on a quantum computer if there exists a family of quantum circuits, one for each input size, with polynomially bounded size. This defines the complexity class BQP.
    7. Quantum circuit simulation — Classical computers can simulate quantum circuits, but the cost scales exponentially with the number of qubits, motivating the search for quantum advantage. Small circuits are routinely simulated to verify small-scale quantum experiments.
    8. Quantum circuit model of computation — Taken together, these elements define the model: a family of circuits parameterized by input size, each built from a fixed finite gate set, with the output given by measurement. This model is polynomially equivalent to the Quantum Turing Machine, but far more practical for design and analysis.
    Intellectual history. The quantum circuit model emerged in the late 1980s as a natural response to the awkwardness of the Quantum Turing Machine (QTM), introduced by David Deutsch in 1985. In the QTM, a quantum program is a sequence of tape-head moves and state transitions—as cumbersome as programming a classical computer at the level of Turing-machine instructions. By 1989, Deutsch and others began to explore a more practical model: a quantum analogue of the classical Boolean circuit, where computation is a sequence of gates acting on a fixed set of qubits. The key insight was that any quantum computation could be decomposed into a sequence of two-qubit gates, making the model both universal and modular.
    The framework solidified in the early 1990s. Richard Feynman had earlier (1982) sketched a quantum simulator using a network of gates, but the canonical formulation is usually credited to Deutsch in a series of papers culminating in his 1989 paper "Quantum Computational Networks" (Proceedings of the Royal Society of London A, 425, 73–90). Deutsch showed that quantum gates could be composed to form circuits, and that these circuits are universal for quantum computation. Around the same time, David P. DiVincenzo (1995) and others proved that two-qubit gates (specifically, the CNOT gate plus arbitrary single-qubit rotations) form a universal set, giving practitioners a concrete and finite toolkit.
    Peter Shor's 1994 factoring algorithm was expressed in the circuit model, cementing its dominance. His 1995 quantum error-correction codes also used the circuit language, showing that the model could handle noise and fault tolerance. The circuit model quickly became the lingua franca for algorithm design, complexity theory (BQP was defined in terms of circuits), and experimental roadmaps. By the late 1990s, the Quantum Turing Machine and the circuit model were proven polynomially equivalent (by Andrew Yao in 1993), but the circuit model had won because it made algorithm design and resource estimation far more tractable.
    The circuit model coexists with other frameworks such as adiabatic quantum computation (2000), measurement-based quantum computation (2001), and topological quantum computation (1997), which are equivalent in power but differ in their physical implementations and error-resilience strategies. The circuit model remains the default conceptual and pedagogical entry point for quantum computation.
    The 13 concepts its tower teaches
    • Initial state preparation
    • Measurement
    • Polynomial-time quantum computation
    • Quantum algorithm
    • Quantum circuit complexity
    • Quantum circuit equivalence
    • Quantum circuit model of computation
    • Quantum gate
    • Quantum gate decomposition
    • Quantum parallelism
    • Quantum register
    • Qubit
    • Unitary operation

    Fly to its tower in Nousfarer

  5. 1993-Present

    Quantum Complexity Theory

    What problems can quantum computers solve efficiently?

    Fly to its tower in Nousfarer

  6. 1994-Present
  7. 1995-Present

    Quantum error correction

    How can quantum information be protected from noise?

    Fly to its tower in Nousfarer

  8. 1995-Present

    Trapped-ion quantum computer

    How can ions be used to build a quantum computer?

    Fly to its tower in Nousfarer

  9. 1997-Present

    Topological quantum computer

    Can topology protect quantum information from errors?

    Fly to its tower in Nousfarer

  10. 1999-Present

    Superconducting quantum computing

    How can superconducting circuits be used as qubits?

    Fly to its tower in Nousfarer

  11. 2000-Present

    Adiabatic Quantum Computation

    Can quantum computation be done by adiabatic evolution?

    Fly to its tower in Nousfarer

  12. 2018-Present

    Noisy intermediate-scale quantum computing

    What can noisy quantum computers do before fault tolerance?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Physics of ComputationQuantum cryptographyQuantum Turing machineQuantum circuitQuantum Complexity TheoryQuantum algorithmQuantum error correctionTrapped-ion quantum computerTopological quantum computerSuperconducting quantum computingAdiabatic Quantum ComputationNoisy intermediate-scale quantum comp…

Beyond the field

Where Quantum Computation's ideas came from in other fields, and what they led to there: the strongest 12 of 45 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Quantum Computation is a planet in Nousfarer

Its city has a tower for each of these 12 frameworks. Land, walk in, and climb one concept at a time.

Land on Quantum Computation

Related fields

Fields its ideas are linked to

More in Theory Of Computation

See where Quantum Computation sits on the Map of Human Knowledge