Algorithms and benchmarks

Algorithms by hardware platform

A dash means that no source for that platform was verified for this release, not that it cannot work. Any marks families that are platform-independent.

Further algorithms (Zoo index)

Further notable quantum algorithms, found through the Quantum Algorithm Zoo and each checked against its original paper. They are mostly theoretical and need fault-tolerant machines; no resource estimate is given unless cited. Summaries and speedups are in the portal’s own words from the original papers; the Zoo category and speedup are given as the Zoo states them.

Index: the Quantum Algorithm Zoo by Stephen P. Jordan, last updated 2026-09-10, checked 2026-10-23. The portal links to it and copies no description from it. Browse the full Quantum Algorithm Zoo (external site)

• Element distinctness by quantum walk

  Finds two equal items among N items with a quantum walk; the method extends to finding k equal items.

  Problem class

  Oracle and query problems

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  O(N^(2/3)) queries, matching a known lower bound; the earlier quantum algorithm needed O(N^(3/4)).

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  A. Ambainis 2007, SIAM Journal on Computing 37, 210 (2007); arXiv:quant-ph/0311001

  Zoo entry

  Collision Finding and Element Distinctness (Quantum Algorithm Zoo, external site) (Oracular Algorithms; speedup as the Zoo states it: Polynomial)

• Collision finding

  Finds two inputs with the same output in a many-to-one black-box function by using Grover search in a new way; also finds claws between two functions.

  Problem class

  Oracle and query problems

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  O((N/r)^(1/3)) expected evaluations for r-to-one functions, fewer than any classical algorithm in the black-box setting.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  G. Brassard et al. 1998, LATIN 1998, LNCS 1380, 163; arXiv:quant-ph/9705002

  Zoo entry

  Collision Finding and Element Distinctness (Quantum Algorithm Zoo, external site) (Oracular Algorithms; speedup as the Zoo states it: Polynomial)

• Welded tree traversal by quantum walk

  A continuous-time quantum walk crosses a specially built graph from one end to the other, an oracle problem constructed to separate quantum and classical computers.

  Problem class

  Oracle and query problems

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Exponential: the paper proves no classical algorithm succeeds with high probability in subexponential time.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  A. M. Childs et al. 2003, Proceedings of STOC 2003, 59; arXiv:quant-ph/0209131

  Zoo entry

  Welded Tree (Quantum Algorithm Zoo, external site) (Oracular Algorithms; speedup as the Zoo states it: Superpolynomial)

• NAND tree evaluation

  Evaluates a binary NAND formula tree, a basic game-tree problem, with a continuous-time quantum walk in the Hamiltonian oracle model.

  Problem class

  Oracle and query problems

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Run time proportional to the square root of N, with a matching lower bound in that model.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  E. Farhi et al. 2007, arXiv:quant-ph/0702144 (2007)

  Zoo entry

  Formula Evaluation (Quantum Algorithm Zoo, external site) (Oracular Algorithms; speedup as the Zoo states it: Polynomial)

• Hidden shift problems

  Uses the quantum Fourier transform to recover an unknown shift between two functions, and defines the hidden coset problem that generalises shifts and subgroups.

  Problem class

  Oracle and query problems

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Efficient quantum algorithms for three shift problems; the abstract does not quantify the classical cost.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  W. van Dam et al. 2003, Proceedings of SODA 2003, 489; arXiv:quant-ph/0211140

  Zoo entry

  Hidden Shift (Quantum Algorithm Zoo, external site) (Oracular Algorithms; speedup as the Zoo states it: Superpolynomial)

• Hidden subgroups of any finite group (query complexity)

  Identifies a hidden subgroup of any finite group with few oracle calls; the computation itself remains slow.

  Problem class

  Oracle and query problems

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Polynomially many oracle calls in log of the group order, exponentially fewer than classically, but exponential running time.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  M. Ettinger et al. 2004, Information Processing Letters 91, 43 (2004); arXiv:quant-ph/0401083

  Zoo entry

  Non-Abelian Hidden Subgroup (Quantum Algorithm Zoo, external site) (Oracular Algorithms; speedup as the Zoo states it: Superpolynomial)

• Dihedral hidden subgroup problem

  Finds a hidden reflection in the dihedral group by combining representations of the group and state tomography; the method also applies to hidden shifts in abelian groups.

  Problem class

  Oracle and query problems

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Time and queries exp(C times the square root of log N), against O(square root of N) classical queries.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  G. Kuperberg 2005, SIAM Journal on Computing 35, 170 (2005); arXiv:quant-ph/0302112

  Zoo entry

  Non-Abelian Hidden Subgroup (Quantum Algorithm Zoo, external site) (Oracular Algorithms; speedup as the Zoo states it: Superpolynomial)

• Approximating the Jones polynomial

  Gives an explicit polynomial-time quantum algorithm for an additive approximation of the Jones polynomial, a knot invariant, at roots of unity.

  Problem class

  Algebra, number theory and topology

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Polynomial in the strands, crossings and k; by results of Freedman et al. it solves a BQP-complete problem.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  D. Aharonov et al. 2006, Proceedings of STOC 2006; arXiv:quant-ph/0511096

  Zoo entry

  Knot Invariants (Quantum Algorithm Zoo, external site) (Approximation and Simulation Algorithms; speedup as the Zoo states it: Superpolynomial)

• Quantum simulation of classical annealing

  Speeds up classical simulated annealing for combinatorial optimisation with quantum walks and evolution randomisation.

  Problem class

  Optimisation

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Quadratic: order 1 over the square root of the spectral gap steps instead of order 1 over the gap.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  R. D. Somma et al. 2008, Phys. Rev. Lett. 101, 130504 (2008); arXiv:0804.1571

  Zoo entry

  Simulated Annealing (Quantum Algorithm Zoo, external site) (Approximation and Simulation Algorithms; speedup as the Zoo states it: Polynomial)

  Related family

  Quantum annealing and adiabatic optimisation

• Quantised Markov chain search

  Turns a classical random-walk search for marked elements into a quantum walk with memory, generalising Grover and Ambainis.

  Problem class

  Search

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Cost scales with 1 over the square root of gap times marked fraction, instead of 1 over their product classically.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  M. Szegedy 2004, arXiv:quant-ph/0401053 (2004)

  Zoo entry

  Simulated Annealing (Quantum Algorithm Zoo, external site) (Approximation and Simulation Algorithms; speedup as the Zoo states it: Polynomial)

  Related family

  Grover search and amplitude amplification

• Verifying matrix products

  Checks whether the product of two n by n matrices over any field equals a third matrix, with bounded error.

  Problem class

  Oracle and query problems

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Worst-case time n^(5/3), improving the previous best quantum algorithm at n^(7/4).

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  H. Buhrman et al. 2004, arXiv:quant-ph/0409035 (2004)

  Zoo entry

  Verifying Matrix Products (Quantum Algorithm Zoo, external site) (Algebraic and Number Theoretic Algorithms; speedup as the Zoo states it: Polynomial)

• Triangle finding in graphs

  Decides whether an undirected graph contains a triangle, combining Grover search with quantum walks.

  Problem class

  Oracle and query problems

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  About n^(13/10) queries up to logarithmic factors with O(n) qubits, or n^(10/7) with O(log n) qubits.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  F. Magniez et al. 2003, arXiv:quant-ph/0310134 (2003)

  Zoo entry

  Graph Properties in the Adjacency Matrix Model (Quantum Algorithm Zoo, external site) (Oracular Algorithms; speedup as the Zoo states it: Polynomial)

• Semidefinite programming

  Solves semidefinite programs with quantum Gibbs sampling inside the multiplicative weights method.

  Problem class

  Optimisation

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Square-root speedup in dimension and number of constraints over any classical method, with a matching lower bound.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  F. G. S. L. Brandão et al. 2016, arXiv:1609.05537 (2016)

  Zoo entry

  Semidefinite Programming (Quantum Algorithm Zoo, external site) (Optimization, Numerics, and Machine Learning; speedup as the Zoo states it: Polynomial (with some exceptions))

• Convex optimisation with quantum oracles

  Studies how quantum queries reduce the cost of optimising over a convex set given by a membership oracle.

  Problem class

  Optimisation

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Optimisation with about n quantum membership queries, against a best known classical bound that is quadratic.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  J. van Apeldoorn et al. 2020, Quantum 4, 220 (2020); arXiv:1809.00643

  Zoo entry

  Convex Optimization (Quantum Algorithm Zoo, external site) (Optimization, Numerics, and Machine Learning; speedup as the Zoo states it: Polynomial)

• Linear differential equations

  Extends quantum simulation methods to general inhomogeneous sparse linear differential equations; the solution is encoded in amplitudes.

  Problem class

  Linear algebra and eigenvalues

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Close to quadratic scaling in evolution time with high-order methods; global features of the solution can be extracted.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  D. W. Berry 2014, J. Phys. A 47, 105301 (2014); arXiv:1010.2745

  Zoo entry

  Solving Linear Differential Equations (Quantum Algorithm Zoo, external site) (Optimization, Numerics, and Machine Learning; speedup as the Zoo states it: Superpolynomial)

  Related family

  Linear systems of equations (HHL and successors)

• Dissipative nonlinear differential equations

  Solves dissipative quadratic differential equations by Carleman linearisation and a quantum linear system solver.

  Problem class

  Linear algebra and eigenvalues

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Exponential improvement in evolution time over earlier quantum algorithms when the nonlinearity ratio R is below 1; hard for R of at least root 2.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  J.-P. Liu et al. 2021, PNAS 118, e2026805118 (2021); arXiv:2011.03185

  Zoo entry

  Solving Nonlinear Differential Equations (Quantum Algorithm Zoo, external site) (Optimization, Numerics, and Machine Learning; speedup as the Zoo states it: Superpolynomial)

  Related family

  Linear systems of equations (HHL and successors)

• Numerical gradient estimation

  Estimates the gradient of a smooth function of d variables given as a black box.

  Problem class

  Estimation and Monte Carlo

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  One query regardless of d, against at least d + 1 queries classically.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  S. P. Jordan 2005, Phys. Rev. Lett. 95, 050501 (2005); arXiv:quant-ph/0405146

  Zoo entry

  Gradient Estimation and Learning Polynomials (Quantum Algorithm Zoo, external site) (Optimization, Numerics, and Machine Learning; speedup as the Zoo states it: Polynomial)

• Decoded quantum interferometry (DQI)

  Uses the quantum Fourier transform to turn optimisation problems into decoding problems, which known decoders then solve.

  Problem class

  Optimisation

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Superpolynomial over known classical algorithms for optimal polynomial fits over finite fields; on a max-XORSAT case a tailored classical solver still wins.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  S. P. Jordan et al. 2025, Nature 646, 831 (2025); arXiv:2408.08292

  Zoo entry

  Optimization by Decoded Quantum Interferometry (Quantum Algorithm Zoo, external site) (Optimization, Numerics, and Machine Learning; speedup as the Zoo states it: Superpolynomial)

  Related family

  Quantum approximate optimisation algorithm (QAOA)

• Tensor principal component analysis

  Spectral classical and quantum algorithms to recover a planted signal from a noisy tensor.

  Problem class

  Machine learning

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Quartic over the fastest classical spectral algorithm with exponentially less space; superpolynomial over classical methods limited to polynomial space.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  M. B. Hastings 2020, Quantum 4, 237 (2020); arXiv:1907.12724

  Zoo entry

  Tensor Principal Component Analysis (Quantum Algorithm Zoo, external site) (Optimization, Numerics, and Machine Learning; speedup as the Zoo states it: Polynomial (quartic))

• Quantum principal component analysis

  Uses many copies of an unknown quantum state to reveal the eigenvectors of its largest eigenvalues.

  Problem class

  Machine learning

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Exponentially faster than existing algorithms, according to the abstract, given copies of the state.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  S. Lloyd et al. 2014, Nature Physics 10, 631 (2014); arXiv:1307.0401

  Zoo entry

  Machine Learning (Quantum Algorithm Zoo, external site) (Optimization, Numerics, and Machine Learning; speedup as the Zoo states it: Varies)

  Related family

  Quantum kernel methods for machine learning

  Assumes access to many copies of the state; loading classical data is a separate cost.

• Quantum recommendation systems

  Samples recommendations from a low-rank approximation of a preference matrix without reconstructing the matrix.

  Problem class

  Machine learning

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Time poly(k) polylog(mn), against classical methods polynomial in the matrix size known at the time.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  I. Kerenidis et al. 2016, arXiv:1603.08675 (2016)

  Zoo entry

  Machine Learning (Quantum Algorithm Zoo, external site) (Optimization, Numerics, and Machine Learning; speedup as the Zoo states it: Varies)

  Related family

  Linear systems of equations (HHL and successors)

  A quantum-inspired classical algorithm later came within a polynomial slowdown of this one (Tang 2019).

• Quantum speedup of backtracking

  Speeds up classical backtracking for constraint satisfaction, including the DPLL method behind many SAT solvers, with a quantum walk on the search tree.

  Problem class

  Optimisation

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  About the square root of T tests times n^(3/2) log n, for a classical tree of T vertices.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  A. Montanaro 2015, arXiv:1509.02374 (2015)

  Zoo entry

  Polynomial Quantum Speedups for Constraint Satisfaction Problems (Quantum Algorithm Zoo, external site) (Optimization, Numerics, and Machine Learning; speedup as the Zoo states it: Polynomial)

• Estimating Gauss sums

  Estimates Gauss sums over finite fields and rings, using the interplay of Fourier and multiplicative characters.

  Problem class

  Algebra, number theory and topology

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Efficient quantum algorithm; a reduction from discrete logarithms gives evidence that the problem is classically hard.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  W. van Dam et al. 2002, arXiv:quant-ph/0207131 (2002)

  Zoo entry

  Gauss Sums (Quantum Algorithm Zoo, external site) (Algebraic and Number Theoretic Algorithms; speedup as the Zoo states it: Superpolynomial)

• Quantum counting

  Combines ideas of the Grover and Shor algorithms to approximate the number of solutions of a search problem.

  Problem class

  Estimation and Monte Carlo

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Keeps the quadratic speedup of quantum search, also for search problems with good classical heuristics.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  G. Brassard et al. 1998, ICALP 1998, LNCS 1443, 820; arXiv:quant-ph/9805082

  Zoo entry

  Searching (Quantum Algorithm Zoo, external site) (Oracular Algorithms; speedup as the Zoo states it: Polynomial)

  Related family

  Amplitude estimation and quantum Monte Carlo integration

• Spatial search by quantum walk

  Searches a database laid out on a lattice with a continuous-time quantum walk on the graph.

  Problem class

  Search

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Full square-root speedup on lattices of more than 4 dimensions, with logarithmic factors in 4 and little speedup below.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  A. M. Childs et al. 2004, Phys. Rev. A 70, 022314 (2004); arXiv:quant-ph/0306054

  Zoo entry

  Searching (Quantum Algorithm Zoo, external site) (Oracular Algorithms; speedup as the Zoo states it: Polynomial)

  Related family

  Grover search and amplitude amplification

• Quantum Metropolis sampling

  A quantum version of the Metropolis algorithm that samples eigenstates of a Hamiltonian, for equilibrium properties.

  Problem class

  Simulation of physical systems

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Avoids the sign problem of classical simulations; the abstract gives no asymptotic speedup.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  K. Temme et al. 2011, Nature 471, 87 (2011); arXiv:0911.3635

  Zoo entry

  Preparing Eigenstates and Thermal States (Quantum Algorithm Zoo, external site) (Approximation and Simulation Algorithms; speedup as the Zoo states it: Superpolynomial)

  Related family

  Electronic structure on fault-tolerant computers (catalysts such as FeMoco)

• Insertion into an ordered list

  Finds where a new item goes in a sorted list of N items using translation-invariant quantum algorithms.

  Problem class

  Search

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Fewer than 0.53 log N queries for large N, against the classical lower bound of log N: a constant factor.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  E. Farhi et al. 1999, arXiv:quant-ph/9901059 (1999)

  Zoo entry

  Ordered Search (Quantum Algorithm Zoo, external site) (Oracular Algorithms; speedup as the Zoo states it: Constant factor)

• Zeta functions of curves

  Determines the zeta function of a curve over a finite field by producing random elements of its class group.

  Problem class

  Algebra, number theory and topology

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Polynomial in the genus g and in log q.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  K. S. Kedlaya 2006, Computational Complexity 15, 1 (2006); arXiv:math/0411623

  Zoo entry

  Zeta Functions (Quantum Algorithm Zoo, external site) (Approximation and Simulation Algorithms; speedup as the Zoo states it: Superpolynomial)

• Hidden nonlinear structures

  Recovers hidden nonlinear structures over finite fields, an alternative generalisation of the problems solved by Shor.

  Problem class

  Algebra, number theory and topology

  Era

  Fault-tolerant, theoretical

  Speedup stated in the paper

  Two example problems solved efficiently by a quantum computer but not by a classical computer.

  Platforms

  Any gate-based quantum computer; the paper names no hardware platform.

  Original paper

  A. M. Childs et al. 2007, Proceedings of FOCS 2007, 395; arXiv:0705.2784

  Zoo entry

  Hidden Nonlinear Structures (Quantum Algorithm Zoo, external site) (Oracular Algorithms; speedup as the Zoo states it: Superpolynomial)