Loading field map
Quantum computation is the study of information processing that is governed by the laws of quantum mechanics. It is a subfield of the theory of computation, but it is also deeply intertwined with physics, mathematics, and computer engineering. The central question is not merely "Can we build a quantum computer?" but rather "What can be computed, and how efficiently, if the underlying physical substrate behaves quantum mechanically?" This reframing of computation changes the fundamental resources—information, time, and energy—that define the limits of what is solvable.
Classical computation, whether performed by a Turing machine or a modern laptop, is built on the bit: a unit of information that is either 0 or 1. A classical computer manipulates these bits through logical operations (gates) that are deterministic or, in the case of probabilistic algorithms, governed by classical probability distributions.
Quantum computation replaces the bit with the qubit. A qubit is a two-level quantum system, such as the spin of an electron or the polarization of a photon. Unlike a classical bit, a qubit can exist in a superposition of its two basis states, |0⟩ and |1⟩. Mathematically, a qubit's state is a unit vector in a two-dimensional complex vector space, written as α|0⟩ + β|1⟩, where α and β are complex numbers and |α|² + |β|² = 1. When measured, the qubit collapses to |0⟩ with probability |α|² and |1⟩ with probability |β|².
The power of quantum computation does not come from superposition alone. A classical probabilistic computer also uses superpositions of states, but with real, non-negative probabilities. The crucial difference is interference. In quantum mechanics, the complex amplitudes α and β can have relative phases. When multiple computational paths are combined, these amplitudes can add constructively (reinforcing a desired outcome) or destructively (canceling an unwanted one). This is the quantum analogue of wave interference, and it is the engine behind quantum algorithms.
The second essential resource is entanglement. When two or more qubits are entangled, their states cannot be described independently. Measuring one instantly determines the state of the other, even if they are far apart. Entanglement is not just a curiosity; it is a computational resource that allows a quantum computer to process correlations between qubits in ways that have no classical analogue. A quantum computer with n qubits operates in a Hilbert space of dimension 2ⁿ, but entanglement means that the information is not simply stored in each qubit individually—it is distributed across the joint state.
The most common way to describe a quantum computation is the quantum circuit model. Here, a computation starts with a set of qubits in a known initial state (usually all |0⟩). A sequence of quantum gates—unitary transformations acting on one or two qubits—is then applied. Each gate is reversible, meaning that the computation can be run backward. The final step is a measurement of all or some of the qubits, which yields a classical bit string as the output.
This model is the direct quantum analogue of the classical circuit model. It is universal in the sense that any unitary transformation on n qubits can be approximated to arbitrary accuracy by a finite set of one- and two-qubit gates (the Solovay–Kitaev theorem). This universality is important because it means that the circuit model is not an arbitrary choice; it captures the full power of quantum mechanics for computation.
However, the circuit model has limitations. It assumes that the qubits are perfectly isolated from their environment, which is never true in practice. Real qubits suffer from decoherence—the gradual loss of quantum information due to interactions with the environment. This is the central obstacle to building a working quantum computer. The theory of quantum error correction addresses this by encoding a logical qubit into many physical qubits, using redundancy to detect and correct errors without measuring the quantum state directly. The threshold theorem states that if the error rate per gate is below a certain threshold, arbitrarily long computations can be performed reliably. This is a theoretical result; achieving the required error rates in hardware is an ongoing engineering challenge.
The deepest questions in quantum computation belong to computational complexity theory. The central class is BQP (Bounded-error Quantum Polynomial time), which contains all decision problems that can be solved efficiently (in polynomial time) by a quantum computer with a probability of error less than 1/3. The relationship between BQP and classical complexity classes is the core open question.
It is known that BQP contains P (classical polynomial time) and is contained in PSPACE (polynomial space). It is also known that BQP is not contained in the polynomial hierarchy unless the polynomial hierarchy collapses, which is considered unlikely. This suggests that quantum computers are strictly more powerful than classical computers for some problems, but the proof is conditional on a widely believed conjecture.
The most famous problem in BQP is integer factorization. Shor's algorithm, discovered by Peter Shor in 1994, factors an n-bit integer in polynomial time on a quantum computer. The best-known classical algorithm runs in sub-exponential time. This result is not just a theoretical curiosity; it threatens the security of RSA encryption, which relies on the difficulty of factoring. Shor's algorithm works by using the quantum Fourier transform to find the period of a function, a task that is exponentially hard classically but efficient quantumly.
Another important problem is unstructured search. Grover's algorithm, discovered by Lov Grover in 1996, searches an unsorted database of N items in O(√N) time, compared to O(N) classically. This is a quadratic speedup, which is less dramatic than Shor's exponential speedup but applies to a much broader class of problems. Grover's algorithm is optimal: no quantum algorithm can do better than O(√N) for unstructured search.
The existence of these algorithms raises a fundamental question: what is the precise boundary of BQP? Are there problems that are not in BQP but are still easier than PSPACE? The answer is unknown. The study of quantum query complexity provides a partial answer. In this model, the cost of an algorithm is the number of times it queries an oracle (a black box that returns the value of a function). Here, quantum algorithms can be provably faster than classical ones, but the speedups are often limited. For example, the quantum query complexity of a function is at most the cube root of its classical query complexity, and for many functions, the speedup is only polynomial.
The circuit model is not the only way to formalize quantum computation. Two other models are theoretically important and have influenced both algorithm design and hardware development.
Measurement-based quantum computation (also called one-way quantum computation) starts with a highly entangled state, typically a cluster state, and performs the computation by a sequence of single-qubit measurements. The choice of measurement basis at each step depends on the outcomes of previous measurements, which makes the computation adaptive. This model is equivalent in power to the circuit model, but it highlights the role of entanglement as a resource. It has been influential in photonic quantum computing, where creating and measuring entangled photons is more natural than applying two-qubit gates.
Adiabatic quantum computation is based on the adiabatic theorem of quantum mechanics. The idea is to encode the solution to a problem in the ground state (the lowest-energy state) of a Hamiltonian (the operator that describes the system's energy). The computation starts with a simple Hamiltonian whose ground state is easy to prepare, and then slowly interpolates to the target Hamiltonian. If the evolution is slow enough, the system remains in its ground state, and the final state encodes the solution. This model is also equivalent to the circuit model in power, but it is particularly natural for optimization problems. It is the basis for quantum annealing, a heuristic approach used by some commercial quantum computers. However, adiabatic quantum computation is not a magic bullet: the time required to maintain adiabaticity can be exponentially long if the energy gap between the ground state and the first excited state becomes small.
These models are not rivals to the circuit model in the sense of being fundamentally different in power; they are all computationally equivalent. Their importance lies in the different physical resources they emphasize and the different algorithmic insights they provide.
The idea that computation could be quantum mechanical dates back to the 1980s, when Richard Feynman and Yuri Manin independently suggested that a quantum system could simulate another quantum system more efficiently than a classical computer. Feynman's insight was that classical simulation of quantum mechanics suffers from an exponential overhead, so a quantum simulator would be a natural tool. This motivated the search for a general theory of quantum computation.
The field took its modern form in the mid-1990s with two key developments. First, Shor's algorithm showed that a quantum computer could solve a problem of practical importance (factoring) exponentially faster than any known classical algorithm. This transformed quantum computation from a philosophical curiosity into a potential technology. Second, the development of quantum error correction showed that decoherence was not an insurmountable barrier. Before this, many researchers believed that quantum computers were impossible in principle because any real system would be too noisy. The threshold theorem changed this view, making quantum computation a realistic engineering goal.
Since then, the field has grown in two directions. On the theory side, researchers have explored the complexity-theoretic foundations, developed new algorithms (such as those for solving linear systems and simulating quantum systems), and studied the power of restricted models. On the experimental side, researchers have built increasingly large and reliable quantum processors using a variety of physical platforms, including superconducting circuits, trapped ions, and photonic systems. The current state of the art is the noisy intermediate-scale quantum (NISQ) era, in which devices have tens to hundreds of qubits but are not yet error-corrected. These devices are too small and too noisy to run Shor's algorithm, but they are large enough to explore quantum phenomena and to test small quantum algorithms.
The field of quantum computation is currently defined by a gap between theory and practice. The theory is mature: we have a clear model of computation, a rich complexity-theoretic framework, and a set of algorithms that demonstrate quantum advantage. The practice is still developing: no one has yet built a quantum computer that can solve a problem of practical interest faster than a classical computer, although small demonstrations of quantum advantage have been claimed for contrived problems.
The central open questions are both theoretical and practical. On the theory side, the most important question is whether BQP is strictly larger than P. This is not just a question about algorithms; it is a question about the nature of computation itself. If $BQP = P$, then quantum mechanics does not offer any fundamental speedup for decision problems, which would be a profound and surprising result. If BQP ≠ P, then the physical laws of our universe allow for computations that are intrinsically more efficient than classical ones.
A related question is the relationship between quantum computation and other areas of physics. For example, the quantum PCP conjecture (a quantum analogue of the classical PCP theorem) asks whether it is possible to verify quantum computations with a small number of measurements. This has deep connections to the study of entanglement and to the foundations of quantum mechanics.
On the practical side, the main challenge is building a fault-tolerant quantum computer. This requires not only improving the fidelity of quantum gates but also developing efficient methods for quantum error correction and for compiling algorithms into the physical gates available on a given device. The field is also exploring hybrid algorithms, such as the variational quantum eigensolver, which use a classical computer to optimize the parameters of a quantum circuit. These algorithms are not guaranteed to provide a speedup, but they are the most promising candidates for near-term quantum advantage.
The relationship between quantum computation and classical computation is not one of replacement. Classical computers are not going away; they are essential for controlling quantum devices, for error correction, and for post-processing the results of quantum measurements. The likely future is a hybrid one, in which quantum computers are used as accelerators for specific tasks, much as GPUs are used for graphics and machine learning today. The theoretical framework for this hybrid model is still being developed, and it is one of the most active areas of research in the field.
Quantum computation is a young field, but it has already reshaped our understanding of what computation is. It has shown that the limits of computation are not set by mathematics alone but by the physical laws that govern the universe. Whether or not a large-scale quantum computer is ever built, the theory has already provided deep insights into the nature of information, complexity, and the relationship between the two.