Quantum algorithms: what they are, which ones matter, and what is proved

What makes an algorithm quantum?

A quantum algorithm is not a classical algorithm that has been given a new name. It is a procedure whose state is a vector of complex amplitudes, whose steps are unitary operations, and whose answer is read by a measurement. Superposition is the reason one circuit can touch many inputs at once. Interference is the reason the amplitudes for the wrong answers can cancel. Measurement is the reason the computer returns one outcome, not the list of amplitudes. Those three words are defined in the glossary, under superposition, quantum gate, and measurement. None of them, by itself, is a speedup.

The speedup, when there is one, is a statement in a named model. A gate-array bound counts elementary gates in a uniform family of circuits, with a small allowed probability of error. An oracle bound counts calls to a black box and says nothing about the cost of building that black box. A hybrid bound is often not a bound at all: it is a loop in which a quantum computer prepares a state and a classical computer chooses the next parameters. Mixing the three models is how a quadratic query result gets described as a break of a cryptosystem, and how a chemistry experiment on four qubits gets described as an algorithm for industry.

Two further distinctions sit underneath every row of the table. The first is the difference between a theorem and a resource estimate. Shor's 1997 paper proves a polynomial gate count. A later paper can estimate how many noisy qubits that circuit would take on a stated hardware model. The estimate is not the theorem, and the theorem is not a machine that has been built. The second distinction is the difference between the problem the algorithm solves and the problem a reader wishes it solved. HHL prepares a quantum state that encodes the solution of a linear system. It does not print the solution vector. VQE estimates an energy inside a family of states someone chose in advance. It does not prove that the family contains the ground state, or that the optimizer will find it.

The pages in this library are secondary. Each one points at the paper that states the claim. If a sentence here and a sentence in the paper disagree, the paper wins. The rest of this guide is a map of those claims: which families the published pages belong to, which speedups are theorems, which procedures are heuristics, and how to read a complexity line without importing a conclusion the line does not contain.

Five families

The families below are a reading order, not a partition that the papers agreed on. An algorithm can sit in more than one. Phase estimation is a Fourier method and also the subroutine inside HHL. Amplitude amplification is the general form of Grover's search and also the postselection booster inside HHL. The point of the grouping is to see which model the bound uses.

Oracle and query algorithms

An oracle answers a predicate and charges one query. It does not reveal how the answer was computed. Query complexity is the number of those calls. It is the right currency for Grover's algorithm, for Deutsch–Jozsa, for Bernstein–Vazirani, and for Simon's algorithm. It is the wrong currency for Shor's algorithm, which counts gates.

Deutsch and Jozsa (1992) give an exact one-query quantum algorithm for a promise problem: a Boolean function on n-bit strings is either constant or balanced, and the algorithm must say which. Any deterministic classical algorithm needs, in the worst case, one more than half the inputs, because that many equal answers are still consistent with a balanced function. The exponential comparison is that exact, deterministic one. Bounded-error classical sampling does not need exponentially many queries. The row in the table says so. This site does not yet have an algorithm page for Deutsch–Jozsa.

Bernstein and Vazirani (STOC 1993; the journal version is 1997) learn a hidden n-bit string s from the oracle that returns the mod-2 inner product of s with the query. The quantum algorithm uses one query. A classical algorithm uses n queries, one for each bit. That is a polynomial separation, linear versus constant, not an exponential one. The same paper studies a recursive version that is an oracle separation of a different strength. This guide does not restate that recursive bound. The basic algorithm is the row Bernstein–Vazirani.

Simon's algorithm is the exponential oracle separation that points toward Shor. The promise is that f(x) equals f(y) exactly when x plus y, bitwise, is either zero or a secret string s. The quantum algorithm uses a linear number of queries. A classical algorithm, even a bounded-error one, needs exponentially many. The 1997 journal version is the reference on the Simon row. The result is a promise problem relative to an oracle. It is not a factoring theorem. Shor's algorithm is the later construction that turns a related period-finding idea into gates for arithmetic.

Grover's algorithm is the query result with a matching lower bound. For t marked items in a space of N candidates, the cost is on the order of the square root of N/t queries, and Bennett, Bernstein, Brassard, and Vazirani show that unstructured search cannot be done with substantially fewer. The square root of an exponential is still exponential. The algorithm does not put NP into polynomial time. Exhaustive key search is the cryptographic reading: a quadratic reduction in the number of trials changes a security level and does not collapse it. The Grover page talks about symmetric keys in that sense. It does not analyze a named cipher. The oracle has to be the expensive step. If the list has to be loaded into the quantum computer one entry at a time, that loading can erase the quadratic improvement.

Fourier and period finding

The quantum Fourier transform is the discrete Fourier transform acting on amplitudes. On n qubits it uses on the order of n squared gates. Shor's 1997 paper writes the circuit and attributes the factorization to Coppersmith and to Deutsch. The classical fast Fourier transform writes out every coefficient of a vector of length 2 to the n. The quantum transform does not. A measurement returns one basis state. In Shor's algorithm the transform is applied to the exponent register after a periodic function has been computed, and continued fractions recover the period classically. The transform is not where the time goes. Modular exponentiation is.

Quantum phase estimation is the later packaging of the same idea: read the phase of an eigenvalue of a unitary, given an eigenstate and controlled powers of that unitary. Kitaev's 1995 lemma is the precision bound this library quotes. Cleve, Ekert, Macchiavello, and Mosca give the inverse-Fourier circuit usually taught under the name. Both bounds assume the eigenstate, or a state whose overlap with one is not exponentially small, and a unitary whose controlled powers the machine can run. They do not give a polynomial gate count for the ground state of an arbitrary molecule. The factoring bound this library quotes remains the one on the Shor page, not a replacement derived from the phase-estimation lemmas.

Shor's algorithm reduces factoring to order-finding by a classical argument, then finds the order with a quantum Fourier transform. The 1997 gate-array bound is polynomial in the number of bits of the integer. The procedure is randomized, and the paper accounts for the repetitions. Elliptic-curve groups are a later adaptation, and this library does not repeat the older qubit counts for that adaptation next to a 2048-bit RSA figure, because the models differ. The fault-tolerant resource estimates are a separate literature. Gidney and Ekerå (2021) estimate about 20 million noisy qubits and about 8 hours for a 2048-bit RSA integer under explicit superconducting-hardware assumptions. Gidney (2025) estimates fewer than one million noisy qubits and less than one week, and states that the physical assumptions match the earlier estimate: a square grid, nearest-neighbor connections, a 0.1 percent gate error, a 1 microsecond surface-code cycle, and a 10 microsecond reaction time. Both numbers are outputs of a cost model. Neither is a modulus that has been factored. Symmetric keys are not this algorithm's target.

Amplitude amplification, estimation, and counting

Amplitude amplification is Grover's idea with the uniform starting state removed. Brassard, Høyer, Mosca, and Tapp take a procedure that succeeds with probability a and a check that recognizes success. Using the procedure and its inverse on the order of 1 over the square root of a times raises the success probability to a constant. Repeating the procedure classically would take on the order of 1/a trials. The quadratic improvement does not beat the black-box lower bound already proved for search. It moves that improvement to any procedure that can be run forwards and backwards. HHL uses it on a postselection whose success probability is on the order of 1 over κ squared, so that on the order of κ repetitions replace on the order of κ squared naive repetitions. That count is a use of the subroutine. It is not a new search bound.

The same 2002 paper estimates the unknown probability a. After M iterations of the Grover iterate, the additive error is on the order of the square root of a times 1 minus a, divided by M, plus a term on the order of 1 over M squared. Classical sampling to additive error ε takes on the order of 1 over ε squared trials. The amplitude estimation row records that comparison and does not restate the paper's leading constants. The glossary page is the account this library has. There is not yet a separate algorithm page.

Quantum counting estimates how many items are marked, by phase estimation on the Grover iterate. Brassard, Høyer, and Tapp introduced it in 1998 and described it as an amplitude-estimation process. The error in the fraction of marked items is the 2002 bound. The speedup against sampling is quadratic. There is no algorithm page here yet. The counting row is the record, and it links the 1998 paper.

A discrete-time quantum walk can reproduce the same quadratic search exponent. Shenvi, Kempe, and Whaley (2003) give a walk on the hypercube that finds a marked item with on the order of the square root of N oracle calls. Their abstract describes a speedup similar to other quantum search algorithms. The row does not claim a better exponent than Grover. Walk-based algorithms for other problems, including element distinctness, are a later literature. This table does not fold those bounds into the search row.

Simulation and linear algebra

Hamiltonian simulation approximates the unitary given by evolving under a Hamiltonian H for a time t, to a stated error ε. What the circuit costs depends on how H is handed to the computer. A sum of local terms, a linear combination of unitaries, a sparse matrix given by an oracle, and a block encoding are different inputs. A bound proved in one of them is not a bound in the others.

Lloyd's 1996 paper is the first explicit quantum algorithm this library cites for local systems. The step counts on the simulation page are later theorems. Childs, Su, Tran, Wiebe, and Zhu bound product-formula error by nested commutators and give a step count this library quotes as their Corollary 12. Berry, Childs, Cleve, Kothari, and Somma truncate a Taylor series and obtain a cost that is the norm of the coefficients times t, multiplied by a factor logarithmic in 1/ε. Low and Chuang (2019) show that a block encoding of norm at most 1 can be simulated with a number of queries on the order of t plus the log of 1/ε. The simulation page keeps those four access models in one table, and it says the comparison is asymptotic. It is not a decision procedure that picks a winner for a molecule of practical size. A query bound becomes a gate count only after the oracle is a circuit.

The HHL algorithm calls that simulation, reads eigenvalues by phase estimation, and rotates an ancilla by a function of the reciprocal. The 2009 runtime this library quotes from the appendix prepares a quantum state for a sparse, well-conditioned system. The cost grows with the condition number. If that number grows as a power of the dimension, the advantage in the dimension is gone. If loading the right-hand side takes a polynomial in the dimension, the advantage is gone at the first step. The output is a state on the order of log N qubits. Learning one specific entry generally means repeating the algorithm on the order of N times. Childs, Kothari, and Somma later improve the dependence on the error for the state. They also record that sampling error alone rules out a polylogarithmic dependence on the error for expectation values, unless BQP equals PP. Gilyén, Lloyd, and Tang give a classical algorithm for a different input: a low-rank matrix offered through length-square sampling. That is not a classical solver for the sparse problem HHL reduce to a quantum circuit.

Quantum singular value transformation, due to Gilyén, Su, Low, and Wiebe (2019), is the framework that applies a polynomial to the singular values of a block of a unitary. The abstract presents it as a generalization of the optimal Hamiltonian simulation of Low and Chuang, usually with a constant number of ancilla qubits, and as a way to reproduce several existing quantum algorithms. It is a theorem about a supplied block encoding. It is not, by itself, one classical speedup for one named problem. The QSVT row says none-proved in the speedup column for that reason, and proved in the evidence column because the transformation is a theorem. There is no algorithm page here yet. The simulation page and the HHL page are where this library already uses the block-encoding and qubitization results QSVT generalizes.

Hybrid and variational algorithms

A hybrid algorithm splits the work. The quantum computer prepares a parameterized state and returns measurement outcomes. The classical computer updates the parameters. The split is a response to coherence: phase estimation asks for a long controlled evolution, and the devices of the last decade did not have it.

The variational quantum eigensolver estimates the lowest eigenvalue of a Hamiltonian inside an ansatz, a family of states chosen in advance. The variational principle says the expected energy cannot undershoot the ground state. It can stop far above it if the family is too small, if the optimizer fails, or if the energy estimate is too noisy to follow. Peruzzo and coauthors introduced the loop in 2014 and demonstrated it on HeH+ with a photonic processor. Kandala and coauthors, in 2017, ran a hardware-efficient ansatz on a superconducting processor for LiH, BeH2, and a four-qubit Heisenberg model. Those are real experiments on small systems. They are not calculations of reaction energies for the molecules industrial chemistry asks about, and the papers do not claim that they are. McClean, Romero, Babbush, and Aspuru-Guzik analyze the measurement cost of estimating a sum of Pauli expectations. That analysis is not a bound on the outer optimization. McClean, Boixo, Smelyanskiy, Babbush, and Neven show that for a wide class of random parameterized circuits the gradient is exponentially small in the number of qubits. A hardware-efficient ansatz of random gates is the example they warn against. No paper this library cites proves that the loop reaches the ground state in time polynomial in the number of orbitals.

QAOA is the same broad loop aimed at a combinatorial cost. Farhi, Goldstone, and Gutmann index the circuit by a depth p. For MaxCut on any connected 3-regular graph, the p = 1 circuit produces a cut whose expected size is at least 0.6924 times the optimal cut. They obtain the number by minimizing a small trigonometric expression over local subgraphs, and they write that the result is not as good as classical algorithms already known for the problem. Goemans and Williamson give a randomized polynomial-time algorithm with expected ratio at least 0.878, and that guarantee is not restricted to 3-regular graphs. A mapping of a scheduling problem onto a QAOA circuit is a mapping. The approximation result in the source paper is the 0.6924 ratio, and the authors say classical algorithms do better on that case. Hadfield and coauthors extend the mixer so that a constrained problem stays inside a feasible subspace. That paper is a design framework. It does not replace the 0.6924 calculation with a better worst-case ratio.

Quantum annealing is the analog relative of this family, and it is not the gate-array model. Kadowaki and Nishimori (1998) study a transverse-field Ising anneal as a numerical method. The annealing row records that there is no proved runtime that beats classical optimization on general instances. An adiabatic interpolation can be given a runtime that depends on the minimum spectral gap along the path. That dependence is not, by itself, a proof that the gap is large. This site does not yet compare annealing with QAOA on a shared benchmark, and it does not rank devices.

Which speedups are proved?

A speedup is proved, in the sense this table uses, when a theorem states the quantum cost and a theorem or a matching classical algorithm states the comparison, in the same model. The evidence column is about the quantum statement. The speedup column is about the comparison. They are allowed to differ. QAOA's 0.6924 ratio is a proved statement, and the comparison with Goemans and Williamson is that the quantum ratio does not win, so the speedup column says none-proved.

The exponential quantum statements this library treats as theorems are these. Shor's algorithm is polynomial time on a quantum gate array for factoring and for the discrete logarithm in the group the 1997 paper treats. Simon's algorithm is an exponential query separation for a promise problem. Deutsch–Jozsa is an exponential separation from deterministic classical algorithms, and not from bounded-error classical sampling. Hamiltonian simulation, in a named access model, approximates a unitary on a space whose dimension is exponential in the number of qubits. The qubitization bound is on the order of t plus log of 1/ε queries to a block encoding of norm at most 1. That is a query count. It becomes a gate count only after someone compiles the encoding.

The quadratic statements are Grover's search, amplitude amplification, amplitude estimation, quantum counting, and the hypercube quantum walk of Shenvi, Kempe, and Whaley. Each of them is optimal in the sense that the square-root exponent matches the black-box lower bound for unstructured search, or matches the quadratic gap between 1/ε and 1/ε squared for estimating a probability. None of them is an exponential speedup. The walk does not beat Grover's exponent.

HHL's logarithmic dependence on the dimension is a theorem under extra promises: sparsity, a condition number that is not too large, a right-hand side that is already a quantum state or can be prepared cheaply, and a measurement that is actually the quantity one wanted. The evidence column says conditional. Aaronson's commentary lists those caveats, and each one is already a hypothesis of the 2009 theorems. The dequantization result removes the quantum state for a different access model, low-rank sampling, and puts the rank in the cost. It does not classicalize every sparse linear system.

Phase estimation's precision bound is a theorem given an eigenstate and the controlled powers. The evidence column says conditional because those are extra promises, not part of an arbitrary matrix problem. The speedup column says none-proved because the routine is a subroutine. The end-to-end speedup, when there is one, is the speedup of the algorithm that spends it: Shor, or HHL, or a chemistry proposal that also has to prepare the eigenstate.

Which algorithms are still heuristics?

VQE has no proved convergence time. The inner estimate, given a state, is a sampling problem whose cost grows as the requested precision tightens. The outer loop is non-convex optimization. Barren plateaus are a proved failure mode for a class of random circuits, which is a limit, not a runtime. The small-molecule experiments are demonstrations. The evidence column says heuristic rather than demonstrated, because a demonstration on HeH+ is not evidence of a scaling advantage, and the column is about the complexity statement.

QAOA has a proved approximation ratio for one case and no proved advantage over the best classical algorithm for that case. Calling the whole method a heuristic would hide the 0.6924 theorem. The table marks the ratio proved and the speedup none-proved. For a generic cost function the angles come from a heuristic search, and the page says so.

Quantum annealing, as the 1998 paper uses it, is a numerical method. The table marks it heuristic and none-proved. A vendor's benchmark on a device is not a row in this table. This library does not rank machines.

The quantum Fourier transform is not a heuristic, and it is also not an end-to-end application. The gate count is a theorem. The useful speedup is the one in the algorithm that calls it. QSVT is in the same position: a proved transformation, and no single classical baseline that would justify an exponential or quadratic label.

How to read a complexity claim

Read the model before the big-O. A gate count, a query count, and a hybrid loop answer different questions. Shor's bound and Grover's bound are both correct and they are not interchangeable. The glossary entry on query complexity is the short form of that warning.

Read the input. Hamiltonian simulation changes its cost when the Hamiltonian is a sum of local terms, a sparse oracle, or a block encoding. HHL's runtime includes the cost of preparing the right-hand side, called T_B in the 2009 appendix, and the sparsity s, and the condition number κ, and the error ε. Dropping any of those and quoting only log N is not the theorem.

Read the output. A state, a sample, an expectation, and a classical list are different answers. HHL's state can be prepared with a cost polylogarithmic in the dimension under the promises above. Printing every entry of the vector cannot. Phase estimation returns an estimate of a phase, not the entries of an arbitrary matrix. The quantum Fourier transform returns a state, not the Fourier coefficients.

Read the error. Some bounds are polynomial in 1/ε, some are logarithmic, and some add a logarithm to a term that does not depend on ε. The simulation page keeps that distinction in a table because it decides which algorithm is even a candidate when the evolution is a subroutine of phase estimation. A logarithmic dependence on the error for preparing a state does not export itself to an expectation value. HHL's own theorem says a polylogarithmic dependence for a classical estimate of an observable would collapse BQP to PP.

Read the hypothesis that is doing the work. An overlap that is only inverse-polynomial, a spectral gap that is only inverse-polynomial, a condition number that is polylogarithmic, a block encoding someone else is assumed to have built: each of these can hide an exponential cost. The phase-estimation page states the overlap hypothesis of Abrams and Lloyd before it will call an eigenvalue problem a speedup. The annealing row refuses a runtime that depends on a gap nobody has estimated.

Read the date of a resource estimate as part of the claim. The 2021 and 2025 factoring estimates do not contradict each other until they are placed on the same assumptions. The 2025 preprint says it uses the same physical assumptions as the earlier estimate and changes the architecture of the arithmetic and the error correction. Quote both, with the assumptions, or quote neither.

A reading path

The five steps below are the order on the front page, with the table as the place to see the rows that do not yet have their own article.

1. Query complexity and gate complexity. Learn which unit a bound is counted in before comparing two algorithms.
2. Grover's algorithm. A quadratic query speedup with a matching lower bound, and a clear statement of what a quadratic speedup does not do.
3. Shor's algorithm. A polynomial gate-array algorithm for factoring and discrete logarithms, a fault-tolerant resource estimate from 2021, and the 2025 revision of that estimate.
4. Quantum phase estimation. The precision bound, the eigenstate it assumes, and the reason VQE was written to avoid the long coherent evolution.
5. VQE and then QAOA. Two hybrid procedures. One has demonstrations and no proved convergence time. One has a proved approximation ratio that does not beat the classical algorithm beside it.

After those, read Hamiltonian simulation before believing a simulation cost copied into a chemistry abstract, and read HHL before believing that linear systems are exponentially faster. The complexity table is the index of the claims, including the algorithms that are rows and not yet pages.

Further reading

The surveys below are not substitutes for the papers this library cites. They are the maps other people use, and linking them is part of saying where a claim came from.

Ashley Montanaro's 2016 overview, "Quantum algorithms: an overview" (npj Quantum Information; arXiv:1511.04206), is a short tour of the main families. Andrew Childs's lecture notes are at cs.umd.edu/~amchilds/qa. Ronald de Wolf's lecture notes are arXiv:1907.09415. Stephen Jordan's Quantum Algorithm Zoo is the long catalogue this table is not trying to replace; it is the place to see how many algorithms a catalogue can list. John Preskill's Physics 219 notes, chapter 6, are the course account of the early algorithms. "A typology of quantum algorithms" (arXiv:2407.05178) is a recent attempt to group the zoo by the kind of problem each algorithm solves.

Use those for orientation. Use the primary paper, linked from the reference record on each row, for the theorem. This page is a secondary source. It was written by QuantumAlgorithms.ai editorial. The text is AI-assisted and checked against the papers it cites. It does not have a named human reviewer.