- Atlas
- Computer Science
- Quantum Computation
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
- Physics of Computation 1961-1985
- Quantum cryptography 1984-Present
- Quantum Turing machine 1985-Present
- Quantum circuit 1989-Present
- Quantum Complexity Theory 1993-Present
- Quantum algorithm 1994-Present
- Quantum error correction 1995-Present
- Trapped-ion quantum computer 1995-Present
- Topological quantum computer 1997-Present
- Superconducting quantum computing 1999-Present
- Adiabatic Quantum Computation 2000-Present
- Noisy intermediate-scale quantum computing 2018-Present
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
- Quantum computing (introduction, Quantum information processing, History, Quantum information, Cryptography, Search problems, Complexity, Quantum supremacy), Wikipedia
- Quantum Turing machine (History, introduction), Wikipedia
- Quantum circuit, Wikipedia
- Quantum logic gate, Wikipedia
- Grover's algorithm, Wikipedia
- Trapped-ion quantum computer, Wikipedia
- Superconducting quantum computing (introduction, History), Wikipedia
- Topological quantum computer, Wikipedia
- 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.
- 1961-1985
Physics of Computation
Can physics be simulated efficiently by computers?
- 1984-Present
Quantum cryptography
How can two parties communicate securely using quantum mechanics?
- 1985-Present
- 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:- 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 .
- 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 qubits can be approximated to arbitrary accuracy by a sequence of gates from this set.
- 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.
- 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.
- Quantum parallelism and quantum algorithm — The ability to place a register into a superposition of all 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.
- 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.
- 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.
- 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
- 1993-Present
Quantum Complexity Theory
What problems can quantum computers solve efficiently?
- 1994-Present
- 1995-Present
Quantum error correction
How can quantum information be protected from noise?
- 1995-Present
Trapped-ion quantum computer
How can ions be used to build a quantum computer?
- 1997-Present
Topological quantum computer
Can topology protect quantum information from errors?
- 1999-Present
Superconducting quantum computing
How can superconducting circuits be used as qubits?
- 2000-Present
Adiabatic Quantum Computation
Can quantum computation be done by adiabatic evolution?
- 2018-Present
Noisy intermediate-scale quantum computing
What can noisy quantum computers do before fault tolerance?
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.
Quantum Turing machine influenced by Physics of Computation
Deutsch's quantum Turing machine formalized the idea that quantum mechanics could be used for computation, building on Feynman's and Benioff's arguments that quantum systems can simulate physics efficiently.
Carried by David Deutsch; Richard Feynman; Paul Benioff.
Quantum circuit grew out of Quantum Turing machine
The quantum circuit model emerged as a practical alternative to the quantum Turing machine, with Deutsch and DiVincenzo showing that a small set of gates is universal for quantum computation.
Carried by David Deutsch; David DiVincenzo.
Quantum Complexity Theory grew out of Quantum Turing machine
Quantum complexity theory grew directly from Deutsch's definition of quantum Turing machines and the complexity classes they define, such as BQP.
Carried by David Deutsch.
Quantum algorithm influenced by Quantum circuit
Shor's factoring algorithm and Grover's search algorithm were formulated in the quantum circuit model, which provided the standard language for expressing quantum algorithms.
Carried by Peter Shor; Lov Grover.
Quantum error correction influenced by Quantum algorithm
The realization that quantum algorithms like Shor's would require error correction to be feasible on noisy hardware drove the development of quantum error-correcting codes by Shor and Steane.
Carried by Peter Shor; Andrew Steane.
Quantum algorithm influenced by Quantum Turing machine
The quantum Turing machine provided the formal model in which quantum algorithms like Shor's were first analyzed, though the circuit model later became standard.
Carried by Peter Shor.
Quantum algorithm influenced by Quantum Complexity Theory
Quantum complexity theory framed the question of which problems quantum computers can solve efficiently, motivating the search for explicit quantum algorithms like Shor's and Grover's.
Carried by Peter Shor.
Topological quantum computer influenced by Quantum error correction
Kitaev's topological quantum computing proposal was motivated by the goal of intrinsic error protection, building on ideas from quantum error correction.
Carried by Alexei Kitaev.
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.
Physics of Computation influenced Quantum computing in Quantum Information
Feynman's 1981-82 lectures on simulating physics with computers, building on earlier work by Benioff and others on reversible computation, posed the question of computational models of quantum systems that launched quantum computing.
Carried by Richard Feynman; Simulating Physics with Computers (1982).
Physics of Computation influenced by Quantum mechanics in Physics
The physics of computation took quantum mechanics as its physical substrate: Landauer's 1961 analysis of erasure and Bennett's reversible computation were framed in quantum-mechanical terms, and Feynman's 1982 argument that classical computers cannot efficiently simulate quantum systems made quantum mechanics the central constraint on computation.
Carried by Rolf Landauer; Charles H. Bennett; Richard Feynman.
Physics of Computation influenced Quantum Computation Theory in Theory Of Computation
Landauer's and Bennett's work on the thermodynamics of computation, reversible computing and the physical cost of erasure gave quantum computation its framing of information as a physical quantity. Feynman and Deutsch drew on this physics-of-computation tradition when proposing computation at the quantum level.
Carried by Rolf Landauer; Charles H. Bennett; Richard Feynman.
Quantum Turing machine influenced Quantum Complexity Theory in Complexity Theory
Deutsch's quantum Turing machine of 1985 gave quantum complexity theory its basic machine model, on which classes such as BQP were later defined. The complexity framework is built on this model.
Carried by David Deutsch.
Quantum Turing machine influenced by Turing machine in Computability
Deutsch's 1985 quantum Turing machine was defined by generalizing Turing's classical machine model to quantum states and unitary transitions. The classical Turing machine supplied the architecture and the notion of computability that the quantum version extended.
Carried by David Deutsch.
Quantum Turing machine influenced by Turing machine computability in Automata
Turing machine computability supplied the notion of a computable function and the halting-style analysis that Deutsch generalized to quantum machines. The quantum Turing machine is defined as a quantum-mechanical analogue of Turing's computability model.
Carried by David Deutsch.
Quantum Complexity Theory influenced by Computational Complexity Theory in Theory Of Computation
Computational complexity theory supplied the class-based framework, reductions and resource bounds that quantum complexity theory adapted to quantum models. BQP and related classes were defined by analogy with P and BPP from that classical tradition.
Carried by Ethan Bernstein; Umesh Vazirani.
Quantum algorithm influenced Post-quantum cryptography in Applied Cryptography
Quantum algorithms, notably Shor's factoring and discrete-log algorithms of 1994, supplied the concrete threat that post-quantum cryptography was created to address. The influence is defining.
Carried by Peter Shor.
Quantum error correction influenced by Error detection and correction in Reliability Fault Tolerance
Quantum error correction took the classical scheme of encoding, syndrome measurement and recovery from error-correcting codes and adapted it to the no-cloning constraint of quantum states. Shor's 1995 nine-qubit code and Steane's CSS construction built directly on classical coding theory.
Carried by Peter Shor; Andrew Steane.
Trapped-ion quantum computer influenced by Quantum computing in Quantum Information
The trapped-ion proposal by Cirac and Zoller in 1995 was offered explicitly as a physical realization of a quantum computer, taking the circuit model and its requirements from quantum computing theory.
Carried by Juan Ignacio Cirac; Peter Zoller.
Topological quantum computer influenced by Quantum computing in Quantum Information
The topological quantum computer was proposed as a way of realizing quantum computation with intrinsic fault tolerance, taking the goal and circuit model from quantum computing. Kitaev's 1997 anyon model framed it as a hardware route to the same computation.
Carried by Alexei Kitaev.
Superconducting quantum computing influenced by Quantum computing in Quantum Information
Superconducting qubits were developed as a physical implementation of the quantum computer, adopting the circuit model, gate requirements and algorithm targets of quantum computing. The first charge-qubit coherence demonstrations in 1999 were framed this way.
Carried by Yasunobu Nakamura; Jaw-Shen Tsai.

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 ComputationRelated fields
Fields its ideas are linked to
- Quantum Information 12 links
- Complexity Theory 5 links
- Cryptography 5 links
- Theory Of Computation 5 links
- Computational Number Theory 2 links
- Computational Physics 2 links
- Physics 2 links
- Computability 2 links
- Topology 1 link
- Philosophy Of Physics 1 link
- Atomic Molecular Physics 1 link
- Mathematical Physics 1 link
More in Theory Of Computation
- Algorithmic Game Theory
- Automata
- Complexity Theory
- Computability
- Computational Learning Theory
- Computational Logic
- Cryptography
- Proof Complexity
- Theory Of Computation
See where Quantum Computation sits on the Map of Human Knowledge