Algorithms for quantum computers, from Shor's factoring and Grover's search to quantum simulation, and the evidence about which speedups are real, provable or only heuristic.
Shor's algorithm is the reason the world is migrating public-key cryptography to post-quantum standards, and the case for building fault-tolerant quantum computers rests on a short list of algorithms with proven speedups.
Step-by-step methods for quantum computers, and the careful question of which speedups over ordinary computers are real.
1Quantum rules allow interference
2Arrange for wrong answers to cancel
3Shor: factoring made fast
4Grover: only a modest speedup
5Many claimed speedups later matched by classical
Model and classes. A quantum algorithm is a sequence of unitary operations (gates) on qubits followed by measurement. BQP is the class of problems solvable with bounded error by a polynomial-size quantum circuit family. It contains BPP (ordinary randomised polynomial time) and is contained in PSPACE. Whether BQP is strictly bigger than BPP is open, so no speedup over all classical algorithms is proven unconditionally. Evidence comes from oracle (query) separations, reductions to problems believed hard, and decades of failed classical attempts.
The established core.
Shor's algorithm (1994) factors an n-bit integer and computes discrete logarithms in time polynomial in n, by finding the period of a function with the quantum Fourier transform. It is a special case of the hidden subgroup problem for abelian groups and is the best known superpolynomial speedup for a practically important problem.
Grover's algorithm (1996) searches N unstructured items with queries, a quadratic speedup provably optimal in the query model. It applies to many brute-force searches, but the overhead of error correction can eat the advantage.
Go deeper
The full technical text.
Model and classes
A quantum algorithm is a sequence of unitary gates on qubits followed by measurement. The class BQP contains problems solvable with bounded error by a polynomial-size quantum circuit family; it contains BPP and is contained in PP⊆. Whether is strictly larger than is open, so no quantum speedup over classical algorithms is proven unconditionally; evidence comes from oracle (query) separations, reductions to problems believed hard, and the absence of good classical algorithms after sustained effort.
Quantum simulation (Feynman; Lloyd) of physical systems is the most natural application; chemistry and materials are the main targets.
Caveats that shape the field. The Harrow–Hassidim–Lloyd algorithm (2008) solves a sparse linear system in time polylogarithmic in its size, but it outputs a quantum state rather than the full solution, assumes state preparation is cheap, and depends on the condition number. Tang (2018) showed that for a related recommendation-systems problem, an ordinary algorithm with comparable access could do almost as well, removing a claimed exponential speedup ("dequantization").
Benchmarks. Several experiments have claimed to beat classical computers on contrived sampling tasks. Many have then been matched or approached by improved classical simulations. A strong, easily checkable demonstration of quantum advantage on a task that anyone can verify remains an active goal.
Open questions. Are there superpolynomial speedups for problems beyond algebraic structure, such as optimisation? Which quantum-chemistry tasks give an advantage after counting error-correction costs? Can the structure of lattice problems be exploited by a quantum algorithm (see lattice cryptography)?
The topic links deep theory (query complexity, Fourier analysis) with practical engineering questions about how many error-corrected qubits are needed.
PSPACE
BQP
BPP
all
The established core
Shor's algorithm (1994) factors an n-bit integer and computes discrete logarithms in time polynomial in n, by finding the period of a function with the quantum Fourier transform. It is a special case of the abelian hidden subgroup problem and is the best-known superpolynomial speedup for a problem of practical importance. Grover's algorithm (1996) searches an unstructured space of N items with O(N) queries, a quadratic speedup that is provably optimal in the query model; it applies to many exhaustive-search problems but its advantage is easily eaten by the overhead of error correction. Quantum simulation of physical Hamiltonians, proposed by Feynman and made rigorous by Lloyd, is the most natural application, with chemistry and materials as the main targets.
Caveats that shape the field
The Harrow–Hassidim–Lloyd algorithm (2008) solves a sparse linear system Ax=b in time polylogarithmic in the dimension, but it outputs a quantum state, not the vector x, assumes efficient state preparation, and its cost depends on the condition number. Tang (2018) showed that for the related recommendation-systems problem, a classical algorithm with comparable sample-and-query access to the data runs in polynomial time, removing the exponential speedup; this "dequantization" programme has since reduced several claimed exponential speedups to polynomial ones. Treat any claimed speedup as conditional on the input and output model.
Resource estimates
Running Shor's algorithm on a 2048-bit RSA modulus needs error-corrected logical qubits. Gidney (2025) estimated that fewer than one million noisy physical qubits and less than a week would suffice, assuming a 0.1% gate error rate, a two-dimensional grid with nearest-neighbour connectivity, a 1 microsecond surface-code cycle and a 10 microsecond control reaction time. Regev (2023) proposed a factoring circuit with O~(n3/2) gates, run about n times, under a number-theoretic heuristic. These are paper estimates for machines that have not been built. Separately, an AI-generated manuscript in OpenAI's openai/math collection (family 279, dated 25 September 2026, with a Lean formalisation of the statement) claims a polynomial-size uniform circuit family over a fixed finite gate set that factors every integer with probability exactly one; it is unrefereed and has not been assessed by experts.
Optimisation and verifiability
Decoded Quantum Interferometry (Jordan, Shutty, Wootters, Zalcman and coauthors; Nature 2025) turns optimisation problems into decoding problems and claims a superpolynomial speedup for an algebraic problem (optimal polynomial intersection, OPI) against known classical algorithms. It has drawn both strengthening and weakening work: Parekh (arXiv September 2025; TQC 2026) showed that the MaxCut instances on which it attains a nontrivial asymptotic guarantee are solvable exactly in classical polynomial time, while Kramer, Gil-Fuster, Jones, Eisert and Schreiber (arXiv October 2026, preprint) claim a provable gap in approximation ratio for a variant of OPI whose constraint sets are accessed through membership oracles. Yamakawa and Zhandry (FOCS 2022; J. ACM 2024) proved a separation between quantum and classical search problems relative to a random oracle, with classically verifiable answers and no structure in the oracle.
Experiments
Sampling experiments since 2019 have claimed "beyond-classical" computation, and nearly every one has been followed by tensor-network or Pauli-path classical simulations that narrow or close the gap. Which of these claims still stand, and whether any computation is both useful and verifiable, is the subject of the open problem on useful quantum advantage.
Encoding information redundantly across many physical qubits so errors can be detected and fixed.
RSA-2048 under one million noisy qubits (estimate)
Gidney estimated that factoring a 2048-bit RSA integer needs under one million physical qubits and under a week, under stated hardware assumptions; a preprint, and no such machine exists.
Shor's factoring and discrete-logarithm algorithms were announced at FOCS 1994; the arXiv version is dated 30 August 1995 and the journal version appeared in SIAM J. Comput. in 1997.
What to read before Quantum algorithms (left), and what builds on it: entries that depend on it and the open problems it hosts (right). Every box links to its page.