What the source papers claim

This library opens with four algorithms because they are the ones people cite when they mean "quantum algorithms" in general, and because the citations are not interchangeable. Each source paper is proving, or demonstrating, a different kind of thing. Putting them in one table is the point of a digest. The algorithm pages are where the arguments live.

Algorithm	Kind of claim	Sentence worth keeping
Shor	Polynomial gate complexity	The 1997 paper gives O((log n)^2 (log log n) (log log log n)) steps for factoring an integer n, plus classical post-processing polynomial in log n.
Grover	Optimal query complexity	On the order of square-root-of-N oracle queries for one marked item, and not asymptotically fewer: the black-box lower bound matches.
VQE	Experiment and estimator	A photonic demonstration on HeH+, and a measurement theory for Pauli decompositions. No proved time to the ground state.
QAOA	Approximation ratio at fixed depth	At p = 1, at least 0.6924 times the optimal MaxCut on connected 3-regular graphs — and the authors say classical algorithms do better.

Polynomial, quadratic, heuristic

Shor's result is a change in the complexity of two specific number-theoretic problems, in the quantum gate-array model, with a small probability of error. The cryptographic reading is real and narrow: factoring, and discrete logarithms in the group the paper treats. Resource estimates such as Gidney and Ekerå's 2048-bit RSA calculation are part of that reading. They are calculations under hardware assumptions, and the digest would be worse if it promoted them to a laboratory result.

Grover's result is a change in query cost for unstructured search. Bennett, Bernstein, Brassard, and Vazirani show the square-root scaling is optimal against a black box. The failure mode in popular accounts is to treat that quadratic as if it were Shor's polynomial, and then to conclude that every brute-force problem falls. The square root of an exponential search remains exponential. The oracle result also does not, by itself, decide whether NP is contained in BQP with no oracle. Bennett and coauthors say so. The digest should not say less carefully than they did.

VQE and QAOA were both proposed in 2014, and they share a shape: a parameterized circuit, a classical optimizer, a short depth relative to phase estimation. The resemblance stops at the claim. Peruzzo and coauthors demonstrate an energy estimate for a small molecule and argue that the coherence requirement drops. They do not prove a scaling advantage over classical chemistry. Farhi, Goldstone, and Gutmann prove a numerical approximation ratio for one family of graphs at depth 1. Goemans and Williamson's classical 0.878 guarantee for MaxCut is older and stronger. A digest that lists QAOA under "optimization speedups" has skipped the paragraph where the inventors compare themselves to classical algorithms.

McClean and coauthors' barren-plateau result belongs in the same note. Hybrid algorithms are not automatically saved by adding qubits. For a wide class of random parameterized circuits, gradients are exponentially unlikely to be visible at fixed precision. That is a theorem about a family of ansatzes, and it is why this library refuses to treat "variational" as a synonym for "scalable."

How to use the table

If you need a theorem, leave this page and open the paper named in the row. If you need to know which page of this library restates the theorem, follow the link, then follow that page's references. The table is a map of claim types. It is not a ranking of importance, and it is not a forecast.