Algorithm Index

An algorithmic speedup is a statement about a specified task and access model. This index pairs each algorithm with its input assumptions and the output it actually produces. It is a selection guide to the explanatory pages, not a ranking of practical performance. Algorithmic Primitives and Lower Bounds and Limitations develop the common framework.

Oracle and search algorithms

In this table, one query means one use of the declared coherent oracle. Its reversible implementation, auxiliary qubits, and classical data loading are additional costs unless explicitly included.

Algorithm and task	Access, output, and limitations
Deutsch–Jozsa: constant versus balanced Boolean function	Promised oracle; Hadamard interference One exact quantum query versus exponential deterministic exact query cost; randomized bounded-error classical testing uses only a constant number for fixed error.
Bernstein–Vazirani: hidden binary string	Coherent oracle for a promised linear Boolean function; phase kickback One quantum query versus n classical queries to recover an n-bit string in this model.
Simon: hidden XOR period	Promised two-to-one oracle; Fourier sampling and linear algebra Polynomial quantum versus exponential classical randomized query cost; the promise is essential.
Grover Search: find a marked item	Reversible predicate, reflections, and a preparable search state $O(\sqrt{N/M})$ queries for M marked items among N under the usual promise; a quadratic black-box improvement.
Amplitude Amplification: amplify a success branch	Preparation A, its inverse, and a success reflection $O(1/\sqrt a)$ coherent uses for success weight a; requires access to the inverse and reflection.
Amplitude Estimation: estimate success weight	Coherent preparation and reflections in the standard formulation $O(1/\epsilon)$ queries for additive error ε at fixed confidence versus $O(1/\epsilon^2)$ independent sampling; coherent depth and oracle cost still matter.

Spectral, simulation, and optimization methods

Algorithm and task	Access, output, and limitations
Quantum Phase Estimation	Controlled powers of U and an input with eigenstate overlap An eigenphase sample; cost depends on total controlled evolution time and desired precision.
Shor Algorithm	Classical integer; reversible modular arithmetic and period finding Factors with bounded failure after classical processing; polynomial in input bit length, with an advantage over known general classical factoring algorithms rather than a proved classical lower bound.
Hamiltonian Simulation Algorithms	Structured access to H; product formulas or block-encoding methods Approximate evolution of an input state, not a list of all amplitudes; include evolution time, norm, access, and error in the cost.
Quantum Linear Algebra	Matrix access and preparation of the right-hand-side state A solution state or selected observables; condition number, success probability, precision, and readout can remove an apparent dimension advantage.
Block Encodings and QSVT	Unitary block encoding with declared normalization; polynomial singular-value transformation An algorithmic framework; polynomial degree, normalization, and block-encoding construction determine cost.
Quantum Walk Algorithms	Graph or Markov-chain access and implementable walk steps Task-dependent search or spectral information; graph promises and preparation costs determine any improvement.
VQE	Trial-state circuit, Hamiltonian measurements, and classical optimization Variational energy estimates; no generic efficiency or global-convergence guarantee.
QAOA	Cost and mixer evolutions with optimized angles Samples and objective estimates; performance depends on instance, depth, optimization, and comparator.

Montanaro surveys the established families and the distinction between query improvements and complete algorithms. Quantum learning and chemistry combine these primitives with additional modeling and data assumptions; use Quantum Machine Learning and Quantum Algorithms for Chemistry and Materials for the assumptions needed in those applications.

Fault tolerance and total cost

Fault tolerance is an implementation requirement determined by the circuit size, target accuracy, physical noise, and acceptable failure probability. It is not a mathematical yes/no attribute of an algorithm name. Small demonstrations of phase estimation or factoring can be unencoded; scalable instances can require long coherent circuits and protected operations. Variational circuits can be shallow while still requiring prohibitive measurement or optimization effort.

For sequential stages without overlap, a useful cost decomposition is

$$C_{\mathrm{total}}={}C_{\mathrm{input}}+C_{\mathrm{compile}} +C_{\mathrm{quantum}} +C_{\mathrm{measure}}+C_{\mathrm{classical}}.$$

Every term must use compatible resource units before addition. Time, logical gates, physical qubits, and energy should otherwise remain separate entries. Resource Estimation explains how physical qubits, operations, and execution time enter the estimate.

Check what the query count leaves out

Suppose Grover search makes approximately $\sqrt N$ oracle queries, but each query is implemented by scanning an unstructured classical table of N entries. The query bound remains valid, while that particular implementation costs on the order of $N^{3/2}$ table operations before other overheads. A coherent memory model or a cheaply computable predicate could change this conclusion. The example does not refute the query theorem; it identifies which cost the theorem left abstract.

Likewise, a linear-system algorithm returning $\lvert x\rangle$ has not printed every coordinate of x. Compare it against a classical algorithm for the same requested output, such as one expectation value, rather than against a stronger classical task.

References

• Montanaro, Ashley, “Quantum algorithms: an overview,” npj Quantum Information 2, 15023 (2016), doi:10.1038/npjqi.2015.23 — algorithm families and their access-dependent improvements.
• Nielsen, Michael A., and Isaac L. Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, Cambridge University Press, 2010, doi:10.1017/CBO9780511976667 — oracle, search, Fourier, and period-finding constructions.