QuantumAlgorithms.aiA citable library

Table

Quantum algorithms list: complexity, speedup, and evidence

By QuantumAlgorithms.ai editorial. This page is AI-assisted and sourced from the primary papers cited on it. It is not a named expert review. First published . Updated .

Each row is one algorithm, one problem, and one comparison. Evidence rates the quantum statement: proved, conditional on an extra promise, heuristic, or a reported experiment. Speedup is the comparison with the classical column. “none-proved” means that comparison is not a theorem, even when the quantum statement itself is. QAOA’s 0.6924 ratio is proved, and it does not beat the classical ratio beside it, so the speedup column says none-proved.

A cell links to a page on this site only when that page exists. 7 rows link to algorithm pages. The quantum Fourier transform and amplitude amplification link to glossary entries. The other rows link only to the primary reference. Counts and formulas are the ones already stated on those pages, or the sentence of the paper named in the reference column.

The dataset is CSV and JSON, under CC BY 4.0. The guide is quantum algorithms.

All 17 rows are in the HTML. The evidence filter is a radio group and works without JavaScript. Sorting reorders those same rows when JavaScript is available.

AlgorithmProblemModelQuantum complexityClassical comparisonSpeedupEvidenceYearPrimary referenceOur page
Shor's algorithmInteger factorization and discrete logarithmsGate arrayO((log n)^2 (log log n) (log log log n)) gate-array steps for an integer n, plus classical post-processing polynomial in log n (Shor 1997). Resource estimates for a 2048-bit RSA integer are separate: about 20 million noisy qubits and about 8 hours under the assumptions in Gidney and Ekerå 2021, and fewer than one million noisy qubits and less than one week under the assumptions in Gidney 2025.Shor 1997 does not prove a classical lower bound. The polynomial quantum runtime is not a theorem that factoring is classically hard.exponentialproved1994Shor 1997Page
Grover's algorithmUnstructured searchOracleΘ(√(N/t)) queries when t items are marked. Optimal in the black-box model up to a small constant (Grover 1996; Boyer et al. 1998; Bennett et al. 1997).Θ(N/t) queries to the same oracle in the worst case.quadraticproved1996Grover 1996Page
Quantum phase estimationEigenphase of a unitaryGate array, given an eigenstatePrecision 2^(−l−2) with error probability at most ε, using the powered unitary O(l log(l/ε)) times plus a term polynomial in l (Kitaev 1995, Lemma 10).No single classical counterpart. The bound assumes an eigenstate, or a state whose overlap is not exponentially small, and controlled powers the machine can apply.none-provedconditional1995Kitaev 1995Page
HHL algorithmSparse linear systemsGate array with sparse row accessÕ(κ T_B + κ² s² log(N)/ε) to prepare a state within vector distance ε of the normalized solution, for an s-sparse matrix of norm at most 1 (Harrow, Hassidim, and Lloyd 2009, Appendix A.1). The output is a quantum state, not the list of solution entries.Conjugate gradient, as that paper compares it, uses on the order of N s √κ log(1/ε) operations for the classical vector when A is positive definite. The two algorithms do not return the same kind of answer. A low-rank matrix with sampling access has a different classical algorithm (Gilyén, Lloyd, and Tang 2018).exponentialconditional2009Harrow, Hassidim, and Lloyd 2009Page
Variational quantum eigensolverApproximate ground-state energyHybridNo proved convergence time. Prepare an ansatz, estimate the energy by measurement, and update the parameters classically (Peruzzo et al. 2014). Reported runs include HeH+ on a photonic processor and LiH, BeH2, and a four-qubit Heisenberg model on a superconducting processor (Kandala et al. 2017).No theorem in the papers this library cites says the loop beats classical quantum-chemistry methods. The published demonstrations are on very small systems.none-provedheuristic2014Peruzzo et al. 2014Page
QAOAApproximate combinatorial optimizationHybridFor p = 1, a worst-case approximation ratio of 0.6924 on MaxCut for connected 3-regular graphs (Farhi, Goldstone, and Gutmann 2014).Goemans and Williamson (1995) give an expected approximation ratio of at least 0.878 for MaxCut, and that guarantee is not restricted to 3-regular graphs. The QAOA authors say the p = 1 result is weaker than known classical algorithms for the same case.none-provedproved2014Farhi, Goldstone, and Gutmann 2014Page
Hamiltonian simulationApproximate e^{−iHt}Gate array with Hamiltonian accessFor a block encoding of norm at most 1, O(t + log(1/ε)) queries to simulate the exponential to spectral-norm error ε (Low and Chuang 2019, Theorem 1). Product formulas and the truncated Taylor series are different access models, with a polynomial and a logarithmic dependence on 1/ε respectively.The query bound is not a gate count until the oracle is a circuit. It is not one complexity that can be copied onto an arbitrary molecule.exponentialproved2019Low and Chuang 2019Page
Quantum Fourier transformDiscrete Fourier transform on amplitudesGate arrayOn n qubits the transform uses on the order of n² gates (Shor 1997, attributing the gate array to Coppersmith and to Deutsch).The classical fast Fourier transform writes all N = 2^n coefficients. The quantum transform does not return that list. A measurement yields one basis state. In Shor's algorithm the transform is not the bottleneck; modular exponentiation is.exponentialproved1994Shor 1997Page
Deutsch–Jozsa algorithmConstant versus balanced Boolean function, under a promiseOracleOne query, exactly (Deutsch and Jozsa 1992).Any deterministic classical algorithm needs 2^{n−1}+1 queries in the worst case on n-bit inputs. The exponential gap is that exact, deterministic comparison. It is not an exponential separation from bounded-error classical sampling.exponentialproved1992Deutsch and Jozsa 1992—
Bernstein–Vazirani algorithmHidden string s, given f(x) = s·x mod 2OracleOne query. The algorithm was introduced at STOC 1993; this row cites the 1997 journal version (Bernstein and Vazirani).n queries to learn an n-bit string. The separation is polynomial (linear versus constant), not exponential.polynomialproved1997Bernstein and Vazirani 1997—
Simon's algorithmHidden xor period, under a promiseOracleO(n) queries to find the hidden string s, for the promise that f(x) = f(y) exactly when x ⊕ y is 0 or s (Simon 1997; FOCS 1994).Ω(2^{n/2}) queries, including for bounded-error classical algorithms. The separation is an oracle promise problem. It is not, by itself, a factoring algorithm.exponentialproved1997Simon 1997—
Amplitude amplificationBoost the success probability of a quantum procedureOracle (a procedure and its inverse)On the order of 1/√a uses of a procedure that succeeds with probability a, to reach a constant success probability (Brassard, Høyer, Mosca, and Tapp 2002).On the order of 1/a repetitions of the same procedure.quadraticproved2002Brassard, Høyer, Mosca, and Tapp 2002Page
Amplitude estimationEstimate an unknown success probabilityOraclePhase estimation on the Grover iterate. After M iterations the additive error in the success probability is on the order of √(a(1−a))/M plus 1/M², with constant probability (Brassard, Høyer, Mosca, and Tapp 2002). This row does not restate the paper's leading constants.Sampling to additive error ε takes on the order of 1/ε² trials.quadraticproved2002Brassard, Høyer, Mosca, and Tapp 2002Page
Quantum countingEstimate the number of marked itemsOracleApproximate counting by phase estimation on the Grover iterate (Brassard, Høyer, and Tapp 1998). The error in the fraction of marked items is the amplitude-estimation bound: on the order of √(a(1−a))/M plus 1/M² after M iterations (Brassard, Høyer, Mosca, and Tapp 2002).Sampling to additive error ε in that fraction takes on the order of 1/ε² trials.quadraticproved1998Brassard, Høyer, and Tapp 1998—
Quantum singular value transformationPolynomial transformation of singular valuesBlock encodingApplies a polynomial to the singular values of a block of a unitary, generalizing optimal Hamiltonian simulation, usually with a constant number of ancilla qubits (Gilyén, Su, Low, and Wiebe 2019). The abstract does not state a single end-to-end classical speedup, and this row does not add a degree-to-query leading constant.No single classical baseline. The comparison depends on the polynomial and on how the matrix is given.none-provedproved2019Gilyén, Su, Low, and Wiebe 2019—
Quantum annealingHeuristic optimization of an Ising costAnalog annealing, not the gate-array modelNo proved runtime that beats classical optimization on general instances. Kadowaki and Nishimori (1998) introduce quantum annealing as a numerical method for the transverse Ising model.This row does not claim a classical lower bound. Simulated annealing is a different heuristic, not a theorem being compared.none-provedheuristic1998Kadowaki and Nishimori 1998—

Cite this table

QuantumAlgorithms.ai editorial. The text is AI-assisted and sourced from the primary papers named in each row. It is not a named expert review.

@misc{quantumalgorithms2026table,
  author = {{QuantumAlgorithms.ai editorial}},
  title = {Quantum algorithms list: complexity, speedup, and evidence},
  year = {2026},
  howpublished = {https://quantumalgorithms.ai/quantum-algorithms/table},
  note = {Compiled 2026-10-28. AI-assisted compilation from the primary papers named in each row. License: CC BY 4.0.}
}