Library
Quantum algorithms, with the claim and the citation
This library records quantum algorithms with the complexity statement the papers prove, and the sentence where that statement stops. The complexity table is the comparison. It is written for people who need to cite a source.
Researchers
A page to hand someone before they open the paper. The theorem, the model, and the sentence the paper does not contain are kept apart.
Engineers
What would have to be true before an algorithm changes a cryptosystem, a solver, or a chemistry code — and what the demonstrations have actually run.
Students
A reading order that starts from the problem and the bound, with the primary papers linked from the page rather than summarized away.
Algorithms
Quantum algorithms guide- Shor's algorithm1994 · Quantum gate arrayA quantum algorithm that factors integers and computes discrete logarithms in polynomial time on a quantum gate array.Gate complexity. O((log n)^2 (log log n) (log log log n)) steps on a quantum gate array for an integer n, plus classical post-processing polynomial in log n (Shor 1997).
- Quantum phase estimation1995 · Quantum gate arrayA quantum routine that estimates the phase of an eigenvalue of a unitary, given an eigenstate and controlled powers of that unitary.Gate complexity. Precision 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).
- Grover's algorithm1996 · Oracle / query complexityA quantum query algorithm that finds a marked item in an unstructured list with quadratically fewer oracle calls than classical search.Query complexity. Θ(√(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).
- Hamiltonian simulation1996 · Quantum gate array with Hamiltonian accessApproximates the time-evolution operator of a Hamiltonian. The proved cost depends on the access model: a product formula, a truncated Taylor series, or qubitization of a block encoding.Depends on the access model. Product formulas need a step count set by nested commutators (Childs et al. 2021, Corollary 12). Qubitization of a block encoding uses O(t + log(1/ε)) queries (Low and Chuang 2019, Theorem 1).
- HHL algorithm2009 · Quantum gate array with sparse row accessPrepares a quantum state encoding the solution of a sparse, well-conditioned linear system. The cost is polylogarithmic in the dimension and polynomial in the condition number and the error.Gate complexity. Õ(κ T_B + κ² s² log(N)/ε) to prepare a state within vector distance ε of the normalized solution, for s-sparse A with norm at most 1 and inverse-norm at most κ (Harrow, Hassidim, and Lloyd, Appendix A.1).
- Variational quantum eigensolver2014 · Hybrid quantum-classicalA hybrid algorithm that estimates molecular and spin-model energies by preparing a parameterized state and optimizing it with a classical computer.Heuristic. No proved convergence time. Prepare an ansatz, estimate the energy by measurement, and update the parameters classically (Peruzzo et al. 2014).
- Quantum approximate optimization algorithm2014 · Hybrid quantum-classicalA parameterized quantum circuit for combinatorial optimization, with a proved approximation ratio for one case of MaxCut that does not beat the best classical algorithm.Approximation ratio. For p = 1, a worst-case ratio of 0.6924 on MaxCut for connected 3-regular graphs. The authors note that this is weaker than known classical algorithms (Farhi, Goldstone, and Gutmann 2014).
Start here
- 1Query complexity and gate complexityShor's bound counts steps of a quantum gate array. Grover's bound counts calls to an oracle. They are not interchangeable.
- 2Grover's algorithmA quadratic query speedup, with a matching lower bound. Useful precisely because the limit is sharp.
- 3Shor's algorithmA polynomial-time quantum algorithm for factoring and discrete logarithms, and a resource estimate that is still an estimate.
- 4Quantum phase estimationThe eigenvalue routine behind the usual retelling of Shor, and the coherence cost VQE was written to avoid. The precision bound assumes an eigenstate.
- 5VQE, then QAOAHybrid heuristics. One is a chemistry experiment on small molecules. One has a proved approximation ratio that does not beat the best classical algorithm for the case it analyzes.