01 The algorithm index

Speedup types

Exponential, Quadratic, Polynomial, Heuristic, Qualitative. Qualitative means a security advantage (QKD / error correction), not a computational speedup over classical.

Showing all 32 algorithms

  • Search Quadratic

    Grover's Algorithm

    Searches an unstructured database of N items in O(sqrt(N)) steps, providing a provable quadratic speedup over any classical algorithm.

    Problem type
    Unstructured Search
    Key reference
    Grover, L. (1996). A fast quantum mechanical algorithm for database search.

    Tutorial: Grover's Algorithm

  • Search Quadratic

    Amplitude Amplification

    Generalises Grover's algorithm to amplify the probability of measuring a 'good' outcome for any quantum subroutine, not just oracle-based search.

    Problem type
    Probability Amplification
    Key reference
    Brassard et al. (2002). Quantum amplitude amplification and estimation.

    Explore tutorials

  • Search Quadratic

    Quantum Counting

    Estimates the number of solutions to a search problem by combining Grover's algorithm with Quantum Phase Estimation.

    Problem type
    Solution Counting
    Key reference
    Brassard, Hoyer, Tapp (1998). Quantum counting.

    Glossary entry

  • Search Linear

    Bernstein-Vazirani Algorithm

    Finds a hidden n-bit string using a single quantum query to a linear oracle, versus n classical queries. Demonstrates phase kickback and Hadamard-based interference in their simplest form.

    Problem type
    Hidden String Recovery
    Key reference
    Bernstein and Vazirani (1997). Quantum complexity theory.

    Tutorial: Bernstein-Vazirani in Qiskit

  • Search Exponential

    Simon's Algorithm

    Finds the period of a function with a hidden XOR structure using O(n) quantum queries versus exponentially many classical queries; the inspiration for Shor's algorithm.

    Problem type
    Hidden XOR Period Finding
    Key reference
    Simon, D. (1994). On the power of quantum computation.

    Tutorial: Simon's Algorithm

  • Factoring Exponential

    Shor's Algorithm

    Factors an N-digit integer in polynomial time using the quantum Fourier transform, breaking RSA-2048 on a sufficiently large fault-tolerant quantum computer.

    Problem type
    Integer Factorisation
    Key reference
    Shor, P. (1994). Algorithms for quantum computation: Discrete logarithms and factoring.

    Tutorial: Shor's Algorithm

  • Factoring Exponential

    Quantum Period Finding

    Finds the period of a modular exponentiation function exponentially faster than any classical method; this is the core subroutine inside Shor's algorithm.

    Problem type
    Period Finding
    Key reference
    Shor, P. (1994). Algorithms for quantum computation.

    Tutorial: Shor's Algorithm

  • Factoring Exponential

    Discrete Log Algorithm

    Solves the discrete logarithm problem exponentially faster than classical methods, breaking Diffie-Hellman and elliptic curve cryptography.

    Problem type
    Discrete Logarithm
    Key reference
    Shor, P. (1994). Algorithms for quantum computation (Shor's variant).

    Glossary entry

  • Simulation Heuristic

    Variational Quantum Eigensolver (VQE)

    Estimates the ground-state energy of a molecule using a hybrid classical-quantum loop, making it one of the most promising near-term quantum chemistry algorithms.

    Problem type
    Quantum Chemistry
    Key reference
    Peruzzo et al. (2014). A variational eigenvalue solver on a photonic quantum processor.

    Tutorial: VQE

  • Simulation Exponential

    Quantum Phase Estimation (QPE)

    Estimates the eigenvalue (phase) of a unitary operator with exponential precision; it is a core building block for Shor's algorithm, HHL, and quantum chemistry.

    Problem type
    Eigenvalue Estimation
    Key reference
    Kitaev, A. (1995). Quantum measurements and the Abelian stabilizer problem.

    Tutorial: QPE in Qiskit

  • Simulation Polynomial

    Trotter-Suzuki Simulation

    Simulates the time evolution of a quantum Hamiltonian by decomposing it into a product of short-time evolution operators, each easy to implement as a quantum circuit.

    Problem type
    Hamiltonian Simulation
    Key reference
    Lloyd, S. (1996). Universal quantum simulators.

    Tutorial: Hamiltonian Simulation in Qiskit

  • Simulation Polynomial

    Qubitization

    An alternative to Trotterization for Hamiltonian simulation that achieves better asymptotic gate counts by encoding the Hamiltonian as a quantum walk.

    Problem type
    Hamiltonian Simulation
    Key reference
    Low and Chuang (2019). Hamiltonian simulation by qubitization.

    Glossary entry

  • Optimisation Heuristic

    QAOA

    The Quantum Approximate Optimisation Algorithm uses alternating layers of problem and mixing unitaries to find approximate solutions to combinatorial optimisation problems.

    Problem type
    Combinatorial Optimisation
    Key reference
    Farhi, Goldstone, Gutmann (2014). A quantum approximate optimization algorithm.

    Tutorial: QAOA with PennyLane

  • Optimisation Heuristic

    Quantum Annealing

    Uses quantum tunneling to escape local minima in an energy landscape, finding low-energy solutions to QUBO problems on D-Wave hardware.

    Problem type
    QUBO Optimisation
    Key reference
    Kadowaki and Nishimori (1998). Quantum annealing in the transverse Ising model.

    Tutorial: D-Wave Ocean

  • Optimisation Quadratic

    Quantum Branch and Bound

    Applies a quantum speedup to the classical branch-and-bound optimisation framework using Grover-style search to prune the solution tree faster.

    Problem type
    Exact Combinatorial Optimisation
    Key reference
    Montanaro, A. (2020). Quantum speedup of branch-and-bound algorithms.

    Glossary entry

  • Linear Algebra Exponential

    HHL Algorithm

    Solves linear systems Ax=b in time O(log N) under certain conditions, offering an exponential speedup over classical solvers, with important caveats about output access.

    Problem type
    Linear Systems
    Key reference
    Harrow, Hassidim, Lloyd (2009). Quantum algorithm for linear systems of equations.

    Glossary entry

  • Linear Algebra Exponential

    Quantum PCA

    Performs principal component analysis on a quantum-encoded density matrix, potentially achieving exponential speedup over classical PCA with QRAM-loaded data.

    Problem type
    Dimensionality Reduction
    Key reference
    Lloyd, Mohseni, Rebentrost (2014). Quantum principal component analysis.

    Glossary entry

  • Linear Algebra Heuristic

    Quantum Recommendation Systems

    A quantum algorithm for sampling from low-rank approximations of matrices, now a famous cautionary case after Tang (2019) produced a matching classical dequantisation.

    Problem type
    Low-Rank Matrix Sampling
    Key reference
    Kerenidis and Prakash (2016); Tang (2019) classical dequantisation.

    Glossary entry

  • Linear Algebra Polynomial

    QSVT

    Quantum Singular Value Transformation is a unifying framework that subsumes most known quantum speedups, including HHL, Grover, and QPE, via polynomial transformations of matrix singular values.

    Problem type
    Quantum Linear Algebra
    Key reference
    Gilyen et al. (2019). Quantum singular value transformation.

    Glossary entry

  • Machine Learning Heuristic

    Quantum SVM

    Uses a quantum circuit to estimate a kernel function for classification, potentially accessing feature spaces that are hard to compute classically.

    Problem type
    Binary Classification
    Key reference
    Havlicek et al. (2019). Supervised learning with quantum-enhanced feature spaces.

    Tutorial: Quantum SVM in PennyLane

  • Machine Learning Heuristic

    Quantum Neural Networks

    Parameterised quantum circuits trained via gradient descent act as quantum analogues of neural networks for classification, regression, and generative tasks.

    Problem type
    Parameterised Circuit Learning
    Key reference
    Benedetti et al. (2019). Parameterized quantum circuits as machine learning models.

    Explore tutorials

  • Machine Learning Heuristic

    Quantum GAN

    A quantum generative adversarial network pairs a quantum generator circuit with a discriminator to learn probability distributions over quantum or classical data.

    Problem type
    Generative Modelling
    Key reference
    Dallaire-Demers and Killoran (2018). Quantum generative adversarial networks.

    Tutorial: Quantum GAN with PennyLane

  • Machine Learning Heuristic

    Quantum Boltzmann Machines

    Uses quantum sampling from a Boltzmann distribution to train a generative model, with quantum tunneling potentially escaping local minima in the energy landscape.

    Problem type
    Generative Modelling
    Key reference
    Amin et al. (2018). Quantum Boltzmann machine.

    Glossary entry

  • Machine Learning Exponential

    QRAM-based ML Algorithms

    Classical ML algorithms (k-means, k-nearest neighbours, linear regression) reformulated with quantum random access memory for potentially exponential speedup in data loading.

    Problem type
    Classical ML with Quantum Data Access
    Key reference
    Biamonte et al. (2017). Quantum machine learning.

    Glossary entry

  • Graph Algorithms Quadratic

    Quantum Walk Search

    Uses quantum walks on graphs to achieve quadratic speedup for problems such as element distinctness and triangle finding in large graphs.

    Problem type
    Graph Search
    Key reference
    Ambainis, A. (2007). Quantum walk algorithm for element distinctness.

    Glossary entry

  • Graph Algorithms Heuristic

    QAOA for Max-Cut

    Applies the Quantum Approximate Optimisation Algorithm specifically to the Max-Cut graph partitioning problem, one of the canonical QAOA benchmarks.

    Problem type
    Graph Partitioning
    Key reference
    Farhi, Goldstone, Gutmann (2014). A quantum approximate optimization algorithm.

    Tutorial: QAOA Max-Cut in Qiskit

  • Graph Algorithms Quadratic

    Quantum Minimum Finding

    Finds the minimum value in an unstructured list of N items in O(sqrt(N)) evaluations using repeated Grover iterations.

    Problem type
    Unstructured Minimum Search
    Key reference
    Durr and Hoyer (1996). A quantum algorithm for finding the minimum.

    Glossary entry

  • Cryptography Qualitative

    BB84

    The first quantum key distribution protocol, using the no-cloning theorem to distribute secret keys with information-theoretic security provable from quantum mechanics.

    Problem type
    Key Distribution
    Key reference
    Bennett and Brassard (1984). Quantum cryptography: Public key distribution and coin tossing.

    Tutorial: QKD in Python

  • Cryptography Qualitative

    E91

    An entanglement-based QKD protocol that uses Bell inequality violations to certify that no eavesdropper has intercepted the shared key.

    Problem type
    Key Distribution
    Key reference
    Ekert, A. (1991). Quantum cryptography based on Bell's theorem.

    Tutorial: QKD in Python

  • Cryptography Qualitative

    Quantum Digital Signatures

    A quantum analogue of classical digital signatures that provides unconditional security against forgery, based on quantum one-way functions rather than computational hardness.

    Problem type
    Message Authentication
    Key reference
    Gottesman and Chuang (2001). Quantum digital signatures.

    Glossary entry

  • Cryptography Qualitative

    Quantum Secret Sharing

    Splits a secret quantum state among multiple parties using entanglement so that only an authorised subset can reconstruct it.

    Problem type
    Distributed Secret Storage
    Key reference
    Hillery, Buzek, Berthiaume (1999). Quantum secret sharing.

    Glossary entry

  • Error Correction Qualitative

    Quantum Error Correction

    Encodes one logical qubit into multiple physical qubits (Steane code: 7 qubits; surface code: ~1000 qubits) so that errors can be detected and corrected without measuring the logical state.

    Problem type
    Fault-Tolerant Computation
    Key reference
    Steane (1996); Fowler et al. (2012). Surface codes: Towards practical large-scale quantum computation.

    Glossary entry

02 All algorithms at a glance

Algorithm Category Speedup Problem type Learn more
Grover's Algorithm Search Quadratic Unstructured Search Tutorial: Grover's Algorithm
Amplitude Amplification Search Quadratic Probability Amplification Explore tutorials
Quantum Counting Search Quadratic Solution Counting Glossary entry
Bernstein-Vazirani Algorithm Search Linear Hidden String Recovery Tutorial: Bernstein-Vazirani in Qiskit
Simon's Algorithm Search Exponential Hidden XOR Period Finding Tutorial: Simon's Algorithm
Shor's Algorithm Factoring Exponential Integer Factorisation Tutorial: Shor's Algorithm
Quantum Period Finding Factoring Exponential Period Finding Tutorial: Shor's Algorithm
Discrete Log Algorithm Factoring Exponential Discrete Logarithm Glossary entry
Variational Quantum Eigensolver (VQE) Simulation Heuristic Quantum Chemistry Tutorial: VQE
Quantum Phase Estimation (QPE) Simulation Exponential Eigenvalue Estimation Tutorial: QPE in Qiskit
Trotter-Suzuki Simulation Simulation Polynomial Hamiltonian Simulation Tutorial: Hamiltonian Simulation in Qiskit
Qubitization Simulation Polynomial Hamiltonian Simulation Glossary entry
QAOA Optimisation Heuristic Combinatorial Optimisation Tutorial: QAOA with PennyLane
Quantum Annealing Optimisation Heuristic QUBO Optimisation Tutorial: D-Wave Ocean
Quantum Branch and Bound Optimisation Quadratic Exact Combinatorial Optimisation Glossary entry
HHL Algorithm Linear Algebra Exponential Linear Systems Glossary entry
Quantum PCA Linear Algebra Exponential Dimensionality Reduction Glossary entry
Quantum Recommendation Systems Linear Algebra Heuristic Low-Rank Matrix Sampling Glossary entry
QSVT Linear Algebra Polynomial Quantum Linear Algebra Glossary entry
Quantum SVM Machine Learning Heuristic Binary Classification Tutorial: Quantum SVM in PennyLane
Quantum Neural Networks Machine Learning Heuristic Parameterised Circuit Learning Explore tutorials
Quantum GAN Machine Learning Heuristic Generative Modelling Tutorial: Quantum GAN with PennyLane
Quantum Boltzmann Machines Machine Learning Heuristic Generative Modelling Glossary entry
QRAM-based ML Algorithms Machine Learning Exponential Classical ML with Quantum Data Access Glossary entry
Quantum Walk Search Graph Algorithms Quadratic Graph Search Glossary entry
QAOA for Max-Cut Graph Algorithms Heuristic Graph Partitioning Tutorial: QAOA Max-Cut in Qiskit
Quantum Minimum Finding Graph Algorithms Quadratic Unstructured Minimum Search Glossary entry
BB84 Cryptography Qualitative Key Distribution Tutorial: QKD in Python
E91 Cryptography Qualitative Key Distribution Tutorial: QKD in Python
Quantum Digital Signatures Cryptography Qualitative Message Authentication Glossary entry
Quantum Secret Sharing Cryptography Qualitative Distributed Secret Storage Glossary entry
Quantum Error Correction Error Correction Qualitative Fault-Tolerant Computation Glossary entry

03 Continue learning

Practice

Step-by-step Tutorials

Implement Grover, Shor, VQE, QAOA, and more in Qiskit and PennyLane.

Machines

Hardware Guide

Match each algorithm class to the right quantum hardware platform.

Study

Quantum Courses

Structured courses covering quantum algorithms from foundations to research level.

Reference

Glossary

Plain-language definitions for every algorithm, gate, and concept on this page.