Independent registry
Quantum Algorithm Zoo
Every quantum algorithm side by side. Classical baseline, quantum complexity, advantage status, code, key papers — and a verdict that says plainly whether it beats classical, where it doesn't, and what was dequantized along the way. The page IBM's blog cannot publish.
- Algorithms
- 25
- Proven advantage
- 16
- Heuristic
- 3
- Dequantized
- 1
- Disputed
- 3
- Last verified
- 2026-05-24
Why this page exists
Vendors who sell quantum compute have an enormous structural incentive to elide the cases where their algorithms underperform classical baselines. We don't sell compute — we teach. Every entry here lists the classical baseline plainly and gives an editorial verdict on whether the quantum algorithm beats it. More on our editorial stance →
Status legend
- Proven Provable asymptotic separation against classical.
- Oracle separation Provable in the oracle model only.
- Conjectured Believed but not proven; classical chase may yet succeed.
- Heuristic No theoretical bound; performance is empirical.
- Dequantized A classical algorithm now matches the quantum asymptotic.
- Disputed Claimed advantage challenged by improved classical methods.
Search
5| Algorithm | Classical | Quantum | Speedup | Status | Maturity |
|---|---|---|---|---|---|
| Grover's Algorithm Find x with f(x)=1 in an unstructured database of size N. Lov Grover · 1996 | O(N) queries | O(√N) queries, O(√N · cost(f)) gates | Quadratic | Proven | Demonstrated |
| Amplitude Amplification Boost the success probability of a randomized quantum procedure from p to ≈1 in O(1/√p) iterations. Brassard, Høyer (later Mosca, Tapp) · 1997 | O(1/p) repetitions | O(1/√p) calls to A and A† | Quadratic | Proven | Production primitive |
| Deutsch-Jozsa Determine whether a Boolean function f : {0,1}^n → {0,1} is constant or balanced (promised one of the two). Deutsch, Jozsa · 1992 | Deterministic: 2^{n-1}+1 queries. Randomized: O(1) queries (just sample). | 1 query. | Exponential (in deterministic-query model only) | Oracle separation | Demonstrated |
| Bernstein-Vazirani Recover a hidden n-bit string s given oracle access to f(x) = s · x mod 2. Bernstein, Vazirani · 1993 | n queries (deterministic or randomized). | 1 query. | Linear (n→1) | Oracle separation | Demonstrated |
| Simon's Algorithm Given f : {0,1}^n → {0,1}^n with the promise f(x) = f(x ⊕ s) for some hidden s, find s. Daniel Simon · 1994 | Θ(2^{n/2}) queries (birthday bound). | O(n) queries. | Exponential | Oracle separation | Demonstrated |
Factoring & cryptanalysis
2| Algorithm | Classical | Quantum | Speedup | Status | Maturity |
|---|---|---|---|---|---|
| Shor's Algorithm (Factoring) Factor an n-bit integer N. Peter Shor · 1994 | Sub-exponential O(exp(c · n^{1/3} · (log n)^{2/3})) (GNFS) | Õ(n^3) gates, with Õ(n^2) depth using log-depth adders | Exponential (superpolynomial) | Proven | Demonstrated |
| Shor's Algorithm (Discrete Log) Given g, h, p, find x such that g^x ≡ h (mod p). Peter Shor · 1994 | Sub-exponential for prime fields; sub-exponential to exponential for elliptic curves | Õ(n^3) for n-bit groups; ECC over n-bit curves slightly cheaper | Exponential | Proven | Theoretical only |
Simulation
2| Algorithm | Classical | Quantum | Speedup | Status | Maturity |
|---|---|---|---|---|---|
| Trotterized Hamiltonian Simulation Implement e^{-iHt} for a local Hamiltonian H. Seth Lloyd (universal); Suzuki (higher-order) · 1996 | Exponential in number of particles for fermionic / many-body systems | Õ(L·t² /ε) for first-order; Õ(L·t·(t/ε)^{o(1)}) for high-order | Exponential (vs exact classical diagonalization) | Proven | Demonstrated |
| Qubitization / Quantum Signal Processing Implement e^{-iHt} with optimal query complexity in t and ε. Low, Chuang (qubitization); Gilyén, Su, Low, Wiebe (QSVT framework) · 2017 | Exponential | Õ(t · ||H|| + log(1/ε)) queries to block encoding | Exponential | Proven | Theoretical only |
Linear algebra
1| Algorithm | Classical | Quantum | Speedup | Status | Maturity |
|---|---|---|---|---|---|
| HHL Algorithm Given a sparse, well-conditioned matrix A and vector b, output a state |x⟩ proportional to A^{-1}|b⟩. Harrow, Hassidim, Lloyd · 2009 | Õ(N · √κ) for Krylov-based sparse solvers (e.g. conjugate gradient) | Õ(log(N) · κ · s · 1/ε) (sparsity s, condition number κ) | Exponential in N (with caveats) | Conjectured | Theoretical only |
Optimization
3| Algorithm | Classical | Quantum | Speedup | Status | Maturity |
|---|---|---|---|---|---|
| QAOA Heuristically find good solutions to combinatorial optimization problems (MaxCut, MaxSAT, ...). Farhi, Goldstone, Gutmann · 2014 | Goemans-Williamson (≈0.878 for MaxCut), SDPs, simulated annealing, branch-and-bound. Strong. | O(p · m) gates per call for an m-edge graph; classical optimization layer on top. | None proven | Heuristic | Demonstrated |
| VQE Estimate the ground-state energy of a Hamiltonian H using a parameterized ansatz |ψ(θ)⟩ and classical optimization. Peruzzo, McClean, Shadbolt, Yung, Zhou, Love, Aspuru-Guzik, O'Brien · 2014 | DMRG (1D, weakly entangled 2D), CCSD(T) (small molecules), tensor networks, neural-network states. | Depends on ansatz; UCCSD scales as O(N^4) parameters with N orbitals. | None proven | Heuristic | Demonstrated |
| Adiabatic Quantum Optimization Find low-energy states of an Ising Hamiltonian by slowly interpolating from a trivial Hamiltonian. Farhi, Goldstone, Gutmann, Sipser (theory); D-Wave (hardware) · 2000 | Simulated annealing, SDPs, MILP solvers — generally strong. | t_f scaling depends on the minimum gap; can be exponential for hard instances. | Heuristic — none proven for problems of practical interest | Disputed | Demonstrated |
Machine learning
3| Algorithm | Classical | Quantum | Speedup | Status | Maturity |
|---|---|---|---|---|---|
| Quantum Kernel Methods Classify data using a kernel computed by a quantum feature map. Havlíček et al.; Schuld, Killoran · 2018 | RBF kernels, polynomial kernels — extremely well understood and strong. | O(D) shots per kernel entry for D-bit precision; O(N²) entries for N data points. | None proven on real data | Conjectured | Demonstrated |
| Tang's Dequantization Solve quantum-machine-learning problems classically with poly(log N) sampling instead of full O(N) reads. Ewin Tang · 2018 | Tang's algorithm itself — was the quantum algorithm before Tang. | n/a (this dequantizes quantum algorithms) | Dequantizes (proves no exponential speedup) | Dequantized | Production primitive |
| Quantum Generative Adversarial Networks Train a parameterized quantum circuit to generate samples from a target distribution. Dallaire-Demers, Killoran; Lloyd, Weedbrook · 2018 | Diffusion models, normalizing flows, classical GANs — extremely strong on real data. | O(L·N) gates per generator call for L-layer N-qubit ansatz; many calls per training step. | None proven | Heuristic | Demonstrated |
Sampling
2| Algorithm | Classical | Quantum | Speedup | Status | Maturity |
|---|---|---|---|---|---|
| Random Circuit Sampling Sample from the output distribution of a random quantum circuit. Boixo et al. (theory); Google Quantum AI (Sycamore experiment) · 2019 | Tensor-network simulation, with several efficient variants developed since 2019. | O(1) per sample on hardware (a single circuit run). | Exponential (conjectured) for the sampling task itself | Disputed | Demonstrated |
| Boson Sampling Sample from the output distribution of indistinguishable bosons (photons) passing through a linear interferometer. Aaronson, Arkhipov · 2011 | Tensor-network and matrix-permanent estimation methods — actively improving. | O(n) modes; depth bounded by interferometer. | Exponential (conjectured) for the sampling task | Disputed | Demonstrated |
Primitives
7| Algorithm | Classical | Quantum | Speedup | Status | Maturity |
|---|---|---|---|---|---|
| Block Encoding Encode an arbitrary matrix A into the top-left block of a unitary U. Low, Chuang (concept); Gilyén et al. (framework) · 2017 | n/a (this is an input model, not an algorithm) | Depends on construction. For s-sparse N×N matrices with row-oracle access: 2 row queries plus O(log N) gates. | n/a | Proven | Production primitive |
| Quantum Singular Value Transformation (QSVT) Apply a polynomial f to the singular values of a block-encoded matrix A. Gilyén, Su, Low, Wiebe · 2018 | n/a (primitive) | O(d) queries to the block encoding for a degree-d polynomial | Exponential (vs full diagonalization to extract singular values) | Proven | Production primitive |
| Linear Combination of Unitaries (LCU) Implement a non-unitary linear combination A = Σ αi Ui of unitaries. Childs, Wiebe · 2012 | n/a (primitive) | O(log L) ancillas + cost(PREP) + cost(SELECT) for L unitaries | n/a | Proven | Production primitive |
| Quantum Fourier Transform Apply the discrete Fourier transform to a quantum state's amplitude vector. Coppersmith (1994), used by Shor (1994), Kitaev (1995) · 1994 | O(N log N) classical FFT — extremely fast and used everywhere. | O(n²) gates (exact), O(n log n) (approximate to constant ε) | Exponential in N (with caveats — see verdict) | Proven | Production primitive |
| Quantum Phase Estimation (QPE) Given a unitary U and an eigenvector |ψ⟩ with U|ψ⟩ = e^{2πiφ}|ψ⟩, estimate φ to t bits of precision. Kitaev · 1995 | O(N) for the underlying eigenvalue problem (e.g. Lanczos); QPE wins in the structured-Hamiltonian regime. | Õ(1/ε) calls to controlled-U for ε precision (Heisenberg-limited). | Polynomial-to-exponential (depending on alternative) | Proven | Production primitive |
| Amplitude Estimation Estimate the probability p that a quantum algorithm A outputs 'success'. Brassard, Høyer, Mosca, Tapp · 2002 | O(1/ε²) Monte Carlo sampling. | O(1/ε) queries to A. | Quadratic | Proven | Demonstrated |
| Quantum Walks Walk on a graph quantumly — used as a primitive for search, element-distinctness, and matrix algorithms. Aharonov, Ambainis, Kempe, Vazirani (continuous); Ambainis (discrete) · 2003 | Random walks, label-propagation, eigenvector-centrality computation. | O(√N) hitting time on regular graphs vs O(N) classical for many graph families. | Polynomial (quadratic typically) | Oracle separation | Demonstrated |
Methodology
Every row links to a deep-dive page with key papers, classical baseline detail, hardware-resource estimates, and an editorial verdict. Classical complexities cite the best known algorithm we could verify, not the textbook baseline — that's the relevant comparison.
"Speedup" is the asymptotic separation in the relevant input model. We mark "None proven" where the asymptotic question is open. We mark "Dequantized" where a classical algorithm with comparable input access has matched the quantum complexity.
Maturity is operational: a "production primitive" is something used inside other algorithms today (block encoding, LCU, QSVT, QFT, QPE). A "demonstrated" algorithm has at least one hardware run; a "theoretical only" algorithm has never been executed at meaningful scale.
What this is and isn't
- Is: an editorial registry with a verdict on every algorithm we cover.
- Isn't: a complete catalog. The canonical Quantum Algorithm Zoo by Stephen Jordan is the more exhaustive index — but it doesn't render verdicts.
- Isn't: investment advice. We don't recommend or disrecommend hardware vendors based on which algorithms they prioritize.