# QuantumAlgorithms.ai

> A citable library of quantum algorithms: definitions, the complexity claims in the source papers, and the limits of those claims.

This is a secondary source for researchers, engineers, and students. Pages state what an algorithm is, which complexity claim the source papers prove, and where that claim stops. Cite the primary papers for theorems. Bibliographic records live under References. The text is AI-assisted. Unpublished drafts are not listed.

## Start here

- [Quantum algorithms](https://quantumalgorithms.ai/quantum-algorithms): What quantum algorithms are, which speedups are proved, and where a complexity claim stops.
- [Complexity table](https://quantumalgorithms.ai/quantum-algorithms/table): Algorithm, problem, model, quantum and classical cost, speedup, and evidence, with one primary reference per row.
- [Dataset (CSV)](https://quantumalgorithms.ai/data/quantum-algorithms.csv): The same table as CSV, CC BY 4.0.
- [Dataset (JSON)](https://quantumalgorithms.ai/data/quantum-algorithms.json): The same table as JSON, CC BY 4.0.

## Algorithms

- [Shor's algorithm](https://quantumalgorithms.ai/algorithms/shor): A quantum algorithm that factors integers and computes discrete logarithms in polynomial time on a quantum gate array.
- [Quantum phase estimation](https://quantumalgorithms.ai/algorithms/phase-estimation): A quantum routine that estimates the phase of an eigenvalue of a unitary, given an eigenstate and controlled powers of that unitary.
- [Grover's algorithm](https://quantumalgorithms.ai/algorithms/grover): A quantum query algorithm that finds a marked item in an unstructured list with quadratically fewer oracle calls than classical search.
- [Hamiltonian simulation](https://quantumalgorithms.ai/algorithms/hamiltonian-simulation): Approximates 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.
- [HHL algorithm](https://quantumalgorithms.ai/algorithms/hhl): Prepares 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.
- [Variational quantum eigensolver](https://quantumalgorithms.ai/algorithms/vqe): A hybrid algorithm that estimates molecular and spin-model energies by preparing a parameterized state and optimizing it with a classical computer.
- [Quantum approximate optimization algorithm](https://quantumalgorithms.ai/algorithms/qaoa): A parameterized quantum circuit for combinatorial optimization, with a proved approximation ratio for one case of MaxCut that does not beat the best classical algorithm.

## Topics

- [Chemistry](https://quantumalgorithms.ai/topics/chemistry): Electronic ground-state energies as a quantum-computing problem: phase estimation in theory, VQE in short-depth experiments, and the costs the papers analyze.
- [Cryptography](https://quantumalgorithms.ai/topics/cryptography): Which cryptosystems Shor's algorithm and Grover's algorithm actually speak to, and which conclusions a complexity bound does not license.
- [Linear systems](https://quantumalgorithms.ai/topics/linear-systems): Sparse linear systems as they appear in this library: a quantum state from HHL, a later logarithmic dependence on precision, and a classical algorithm for a different low-rank access model.
- [Optimization](https://quantumalgorithms.ai/topics/optimization): Combinatorial optimization as it appears in this library: an approximation ratio for QAOA, a quadratic black-box search, and the classical algorithms beside them.

## Glossary

- [Amplitude amplification](https://quantumalgorithms.ai/glossary/amplitude-amplification): A quadratic boost to the success probability of a quantum procedure, generalizing Grover's search beyond a uniform starting state.
- [Ansatz](https://quantumalgorithms.ai/glossary/ansatz): A parameterized family of quantum states, chosen in advance, inside which a hybrid algorithm searches for a good solution.
- [Condition number](https://quantumalgorithms.ai/glossary/condition-number): The ratio of the largest singular value of a matrix to the smallest. HHL's runtime grows with it, and a large value removes the advantage in the dimension.
- [Decoherence](https://quantumalgorithms.ai/glossary/decoherence): Unwanted entanglement with the environment that turns a pure quantum evolution into noise on the device you meant to compute with.
- [Entanglement](https://quantumalgorithms.ai/glossary/entanglement): Correlation between qubits that cannot be written as a product of single-qubit states, and that measurement on one side constrains the other.
- [Fault tolerance](https://quantumalgorithms.ai/glossary/fault-tolerance): Computation that keeps a logical circuit reliable by correcting errors often enough that they do not accumulate.
- [Hamiltonian](https://quantumalgorithms.ai/glossary/hamiltonian): The Hermitian operator whose eigenvalues are the energies, or, in combinatorial problems, the costs of bit-string solutions.
- [Measurement](https://quantumalgorithms.ai/glossary/measurement): The step that turns amplitudes into a classical outcome, one shot at a time, and the reason expectation values are estimated by repetition.
- [NISQ](https://quantumalgorithms.ai/glossary/nisq): Preskill's name for quantum devices that are too noisy for long fault-tolerant circuits and large enough that the noise is the main constraint.
- [Oracle](https://quantumalgorithms.ai/glossary/oracle): A black-box subroutine that answers a predicate, charged as one query, without revealing how the answer was computed.
- [Phase estimation](https://quantumalgorithms.ai/glossary/phase-estimation): A quantum routine that estimates the eigenvalue phase of a unitary applied to an eigenstate, given coherent controlled powers of that unitary.
- [Quantum Fourier transform](https://quantumalgorithms.ai/glossary/quantum-fourier-transform): The discrete Fourier transform applied to amplitudes, used by Shor's algorithm to turn a periodic superposition into samples near multiples of the frequency.
- [Quantum gate](https://quantumalgorithms.ai/glossary/quantum-gate): A reversible operation on qubits, represented by a unitary matrix, and the step that gate-complexity statements count.
- [Qubit](https://quantumalgorithms.ai/glossary/qubit): A quantum two-level system, used as the basic carrier of information in the gate-array model.
- [Query complexity](https://quantumalgorithms.ai/glossary/query-complexity): The number of calls to an oracle, rather than the number of elementary gates, required to solve a problem.
- [Superposition](https://quantumalgorithms.ai/glossary/superposition): A state that is a linear combination of basis states, with complex amplitudes, until a measurement returns one outcome.
- [Variational quantum algorithm](https://quantumalgorithms.ai/glossary/variational-quantum-algorithm): A hybrid loop: a parameterized quantum state, an estimate of a cost, and a classical optimizer updating the parameters.

## Research digests

- [Sublinear-depth Trotter steps for electrons in atomic orbitals](https://quantumalgorithms.ai/digests/atomic-orbital-simulation): Günther and Harrow implement one Trotter stage for a localized atomic-orbital Hamiltonian in polylogarithmic depth, and prove a three-dimensional gate count of N to the 5/3 times t, up to a sub-power factor.
- [Learning halfspaces with logarithmically many quantum queries](https://quantumalgorithms.ai/digests/halfspace-query-separation): Krivcenko, Nguyen, and de Wolf learn a linear threshold function to Gaussian error ε with O(log(n/ε)) quantum membership queries. The other gates are still linear in the dimension.
- [A noise threshold for Shor's Fourier transform](https://quantumalgorithms.ai/digests/shor-qft-noise-threshold): Cai and Young prove a sharp threshold for relative Gaussian noise on the small controlled rotations in Shor's quantum Fourier transform. Below it, expected polynomial time; above it, failure on a positive-density set of primes.
- [What the source papers claim](https://quantumalgorithms.ai/digests/reading-the-source-papers): The opening note of this library: four algorithms, four different kinds of claim, and the sentence in each source paper that should travel with the result.

## References

- [Suzuki, M. (1991). General theory of fractal path integrals with applications to many-body theories and statistical physics. Journal of Mathematical Physics, 32(2), 400–407.](https://quantumalgorithms.ai/references/suzuki-1991): General theory of fractal path integrals with applications to many-body theories and statistical physics
- [Deutsch, D., & Jozsa, R. (1992). Rapid solution of problems by quantum computation. Proceedings of the Royal Society A, 439, 553–558.](https://quantumalgorithms.ai/references/deutsch-jozsa-1992): Rapid solution of problems by quantum computation
- [Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (pp. 124–134). IEEE.](https://quantumalgorithms.ai/references/shor-1994): Algorithms for quantum computation: discrete logarithms and factoring
- [Goemans, M. X., & Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6), 1115–1145.](https://quantumalgorithms.ai/references/goemans-1995): Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- [Kitaev, A. Yu. (1995). Quantum measurements and the Abelian stabilizer problem. arXiv:quant-ph/9511026.](https://quantumalgorithms.ai/references/kitaev-1995): Quantum measurements and the Abelian stabilizer problem
- [Shor, P. W. (1995). Scheme for reducing decoherence in quantum computer memory. Physical Review A, 52(4), R2493–R2496.](https://quantumalgorithms.ai/references/shor-1995): Scheme for reducing decoherence in quantum computer memory
- [Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (pp. 212–219). ACM.](https://quantumalgorithms.ai/references/grover-1996): A fast quantum mechanical algorithm for database search
- [Lloyd, S. (1996). Universal quantum simulators. Science, 273(5278), 1073–1078.](https://quantumalgorithms.ai/references/lloyd-1996): Universal quantum simulators
- [Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997). Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5), 1510–1523.](https://quantumalgorithms.ai/references/bennett-1997): Strengths and weaknesses of quantum computing
- [Bernstein, E., & Vazirani, U. (1997). Quantum complexity theory. SIAM Journal on Computing, 26(5), 1411–1473.](https://quantumalgorithms.ai/references/bernstein-vazirani-1997): Quantum complexity theory
- [Grover, L. K. (1997). Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 79(2), 325–328.](https://quantumalgorithms.ai/references/grover-1997): Quantum mechanics helps in searching for a needle in a haystack
- [Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484–1509.](https://quantumalgorithms.ai/references/shor-1997): Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
- [Simon, D. R. (1997). On the power of quantum computation. SIAM Journal on Computing, 26(5), 1474–1483.](https://quantumalgorithms.ai/references/simon-1997): On the power of quantum computation
- [Boyer, M., Brassard, G., Høyer, P., & Tapp, A. (1998). Tight bounds on quantum searching. Fortschritte der Physik, 46(4–5), 493–505.](https://quantumalgorithms.ai/references/boyer-1998): Tight bounds on quantum searching
- [Brassard, G., Høyer, P., & Tapp, A. (1998). Quantum counting. In Automata, Languages and Programming (ICALP 1998), Lecture Notes in Computer Science (Vol. 1443, pp. 820–831).](https://quantumalgorithms.ai/references/brassard-hoyer-tapp-1998): Quantum counting
- [Cleve, R., Ekert, A., Macchiavello, C., & Mosca, M. (1998). Quantum algorithms revisited. Proceedings of the Royal Society A, 454, 339–354.](https://quantumalgorithms.ai/references/cleve-1998): Quantum algorithms revisited
- [Kadowaki, T., & Nishimori, H. (1998). Quantum annealing in the transverse Ising model. Physical Review E, 58, 5355.](https://quantumalgorithms.ai/references/kadowaki-nishimori-1998): Quantum annealing in the transverse Ising model
- [Abrams, D. S., & Lloyd, S. (1999). A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors. Physical Review Letters, 83, 5162–5165.](https://quantumalgorithms.ai/references/abrams-lloyd-1999): A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
- [Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002). Quantum amplitude amplification and estimation. In Quantum Computation and Information, Contemporary Mathematics (Vol. 305, pp. 53–74). American Mathematical Society.](https://quantumalgorithms.ai/references/brassard-2002): Quantum amplitude amplification and estimation
- [Proos, J., & Zalka, C. (2003). Shor's discrete logarithm quantum algorithm for elliptic curves. Quantum Information and Computation, 3(4), 317–344.](https://quantumalgorithms.ai/references/proos-2003): Shor's discrete logarithm quantum algorithm for elliptic curves
- [Shenvi, N., Kempe, J., & Whaley, K. B. (2003). Quantum random-walk search algorithm. Physical Review A, 67, 052307.](https://quantumalgorithms.ai/references/shenvi-kempe-whaley-2003): Quantum random-walk search algorithm
- [Aspuru-Guzik, A., Dutoi, A. D., Love, P. J., & Head-Gordon, M. (2005). Simulated quantum computation of molecular energies. Science, 309(5741), 1704–1707.](https://quantumalgorithms.ai/references/aspuru-guzik-2005): Simulated quantum computation of molecular energies
- [Harrow, A. W., Hassidim, A., & Lloyd, S. (2009). Quantum algorithm for linear systems of equations. Physical Review Letters, 103(15), 150502.](https://quantumalgorithms.ai/references/harrow-2009): Quantum algorithm for linear systems of equations
- [Nielsen, M. A., & Chuang, I. L. (2010). Quantum computation and quantum information (10th anniversary ed.). Cambridge University Press.](https://quantumalgorithms.ai/references/nielsen-2010): Quantum computation and quantum information
- [Belovs, A. (2013). Quantum algorithms for learning symmetric juntas via the adversary bound. arXiv:1311.6777.](https://quantumalgorithms.ai/references/belovs-2013): Quantum algorithms for learning symmetric juntas via the adversary bound
- [Farhi, E., Goldstone, J., & Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv:1411.4028.](https://quantumalgorithms.ai/references/farhi-2014): A quantum approximate optimization algorithm
- [Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., & O'Brien, J. L. (2014). A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5, 4213.](https://quantumalgorithms.ai/references/peruzzo-2014): A variational eigenvalue solver on a photonic quantum processor
- [Aaronson, S. (2015). Read the fine print. Nature Physics, 11(4), 291–293.](https://quantumalgorithms.ai/references/aaronson-2015): Read the fine print
- [Berry, D. W., Childs, A. M., Cleve, R., Kothari, R., & Somma, R. D. (2015). Simulating Hamiltonian dynamics with a truncated Taylor series. Physical Review Letters, 114, 090502.](https://quantumalgorithms.ai/references/berry-childs-cleve-kothari-somma-2015): Simulating Hamiltonian dynamics with a truncated Taylor series
- [McClean, J. R., Romero, J., Babbush, R., & Aspuru-Guzik, A. (2016). The theory of variational hybrid quantum-classical algorithms. New Journal of Physics, 18, 023023.](https://quantumalgorithms.ai/references/mcclean-2016): The theory of variational hybrid quantum-classical algorithms
- [Childs, A. M., Kothari, R., & Somma, R. D. (2017). Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 46(6), 1920–1950.](https://quantumalgorithms.ai/references/childs-kothari-somma-2017): Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- [Kandala, A., Mezzacapo, A., Temme, K., Takita, M., Brink, M., Chow, J. M., & Gambetta, J. M. (2017). Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549, 242–246.](https://quantumalgorithms.ai/references/kandala-2017): Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets
- [Low, G. H., & Chuang, I. L. (2017). Optimal Hamiltonian simulation by quantum signal processing. Physical Review Letters, 118, 010501.](https://quantumalgorithms.ai/references/low-chuang-2017): Optimal Hamiltonian simulation by quantum signal processing
- [Gilyén, A., Lloyd, S., & Tang, E. (2018). Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. arXiv:1811.04909.](https://quantumalgorithms.ai/references/gilyen-lloyd-tang-2018): Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
- [McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R., & Neven, H. (2018). Barren plateaus in quantum neural network training landscapes. Nature Communications, 9, 4812.](https://quantumalgorithms.ai/references/mcclean-2018): Barren plateaus in quantum neural network training landscapes
- [Preskill, J. (2018). Quantum computing in the NISQ era and beyond. Quantum, 2, 79.](https://quantumalgorithms.ai/references/preskill-2018): Quantum computing in the NISQ era and beyond
- [Gilyén, A., Su, Y., Low, G. H., & Wiebe, N. (2019). Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (pp. 193–204).](https://quantumalgorithms.ai/references/gilyen-su-low-wiebe-2019): Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- [Hadfield, S., Wang, Z., O'Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2019). From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12(2), 34.](https://quantumalgorithms.ai/references/hadfield-2019): From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- [Low, G. H., & Chuang, I. L. (2019). Hamiltonian simulation by qubitization. Quantum, 3, 163.](https://quantumalgorithms.ai/references/low-chuang-2019): Hamiltonian simulation by qubitization
- [Childs, A. M., Su, Y., Tran, M. C., Wiebe, N., & Zhu, S. (2021). Theory of Trotter error with commutator scaling. Physical Review X, 11, 011020.](https://quantumalgorithms.ai/references/childs-su-tran-wiebe-zhu-2021): Theory of Trotter error with commutator scaling
- [Gidney, C., & Ekerå, M. (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5, 433.](https://quantumalgorithms.ai/references/gidney-2021): How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- [Berry, D. W., Wan, K., Baczewski, A. D., Eklund, E. C., Tikku, A., & Babbush, R. (2025). Quantum simulation of electronic structure via quantum fast multipole method. arXiv:2510.07380.](https://quantumalgorithms.ai/references/berry-wan-baczewski-2025): Quantum simulation of electronic structure via quantum fast multipole method
- [Gidney, C. (2025). How to factor 2048 bit RSA integers with less than a million noisy qubits. arXiv:2505.15917.](https://quantumalgorithms.ai/references/gidney-2025): How to factor 2048 bit RSA integers with less than a million noisy qubits
- [Cai, J.-Y., & Young, B. (2026). A sharp noise threshold for Shor's quantum factoring and discrete log algorithms. arXiv:2609.24316.](https://quantumalgorithms.ai/references/cai-young-2026): A sharp noise threshold for Shor's quantum factoring and discrete log algorithms
- [Günther, J., & Harrow, A. W. (2026). Sublinear-depth quantum simulation of electrons with atomic orbitals. arXiv:2610.00950.](https://quantumalgorithms.ai/references/gunther-harrow-2026): Sublinear-depth quantum simulation of electrons with atomic orbitals
- [Krivcenko, A., Nguyen, T., & de Wolf, R. (2026). Fast quantum algorithms for learning linear threshold functions. arXiv:2609.40331.](https://quantumalgorithms.ai/references/krivcenko-nguyen-dewolf-2026): Fast quantum algorithms for learning linear threshold functions

## Optional

- [About](https://quantumalgorithms.ai/about): Scope, editorial standard, and how to cite a page.
- [Corrections](https://quantumalgorithms.ai/corrections): Changelog for claims that were wrong or incomplete.
- [Quantum algorithms guide](https://quantumalgorithms.ai/quantum-algorithms): The pillar page for the head term.
- [Research digest feed](https://quantumalgorithms.ai/feed.xml): RSS for research digests.