§ Trackr.Live

Quantum Algorithms

A quantum algorithm is not a faster classical algorithm. It is a procedure designed specifically for quantum hardware, exploiting superposition, entanglement, and interference to solve problems that have specific mathematical structure. The set of known quantum algorithms with meaningful speedups over classical algorithms is small — perhaps a dozen genuinely useful algorithms in active study — and most of them target highly specific problem classes rather than general computation. Outside those classes, quantum computers offer no advantage over classical computers, and pretending otherwise has been one of the persistent failure modes of quantum computing communication.

This page is the deep-dive companion to the Quantum Computing umbrella page. The scope here is the algorithmic side: the building-block primitives that show up across multiple algorithms, the specific algorithms that matter, honest commentary on the hyped vs. genuinely promising parts of the landscape, and the resource estimates that determine when each algorithm becomes practically useful. The physical hardware side is covered in Qubit Architectures; the error correction layer that bridges physical to logical qubits is covered separately.

What makes an algorithm “quantum”

Most computational problems get no speedup from quantum computers. This is the single most important fact about quantum algorithms and the one that popular accounts most often elide.

A quantum algorithm provides a speedup when:

The problem has structure that quantum mechanics can exploit — typically periodicity, hidden subgroup structure, or specific algebraic properties.
The structure can be encoded into a quantum circuit of polynomial size.
The quantum circuit produces an output state where interference amplifies the amplitudes of correct answers and suppresses incorrect ones.
The measurement at the end yields the correct answer with non-trivial probability.

Problems without exploitable structure get at best a Grover-style quadratic speedup, which is real but modest. Problems with no structure at all get nothing — quantum sorting is not faster than classical sorting, quantum hashing is not faster than classical hashing, quantum encryption of bulk data is not faster than classical encryption.

The known quantum algorithms with exponential speedups all target a narrow set of problem types: integer factoring, discrete logarithms in various groups, certain instances of hidden subgroup problems, quantum simulation of physical systems, and (under specific conditions) solving certain linear systems. The structure that makes these problems amenable to exponential speedup is mathematical, not computational — the algorithms exist because the underlying problems have specific algebraic properties that map onto quantum operations, not because quantum computers are generically faster.

The known quantum algorithms with polynomial speedups apply more broadly, but the speedups are smaller — typically quadratic, occasionally cubic. Grover’s algorithm against unstructured search is the canonical example.

The rest of this page works through the specific algorithms in roughly that order: building blocks, exponential-speedup algorithms, polynomial-speedup algorithms, NISQ-era hybrid algorithms, and the honest accounting of what they actually deliver.

The algorithmic primitives

Three primitives appear repeatedly across the major quantum algorithms. Understanding them by name is useful even at the survey level because they are the recurring building blocks rather than self-contained algorithms.

Quantum Fourier Transform (QFT)

The Quantum Fourier Transform is the quantum analog of the classical discrete Fourier transform: it transforms a quantum state representation between “computational basis” and “frequency basis.” The classical discrete Fourier transform on N points requires O(N log N) operations using the Fast Fourier Transform; the QFT performs the analogous transformation on a 2^n-dimensional quantum state space using O(n²) quantum gates — an exponential improvement, but one that only matters if you can actually use the transformed state.

The QFT is the engine inside Shor’s algorithm and quantum phase estimation. It is also a useful illustration of a key point about quantum algorithms: the QFT runs exponentially faster than the classical DFT in some sense, but you cannot extract all 2^n amplitudes from the transformed state by measurement. The speedup only matters when the algorithm uses the structure of the transformed state to produce a specific answer at measurement, not when it needs the full transformed array.

Quantum Phase Estimation (QPE)

Quantum phase estimation is the algorithm for determining an eigenvalue of a unitary operator. Given a unitary U and one of its eigenstates |ψ⟩ such that U|ψ⟩ = e^(2πiφ)|ψ⟩, the QPE algorithm uses the QFT to produce an estimate of the phase φ with precision determined by the number of auxiliary qubits used.

QPE is the workhorse subroutine in many quantum algorithms. Shor’s algorithm uses QPE internally to extract the period of a modular exponentiation function. Quantum simulation algorithms use QPE to extract energy eigenvalues of physical Hamiltonians. The HHL algorithm uses QPE to extract eigenvalues of matrices. Many other algorithms reduce to “set up a unitary whose phases encode the answer, then run QPE.”

The resource requirements of QPE scale with the required precision: extracting φ to n bits of precision requires roughly n auxiliary qubits and a number of applications of U that grows exponentially in n. This is why QPE-based algorithms have specific structure — the unitaries chosen must be efficiently implementable and the precision required must be modest enough to keep the total cost polynomial.

Amplitude Amplification

Amplitude amplification is the generalization of Grover’s search algorithm into a reusable subroutine. Given a quantum algorithm that produces a correct answer with probability p, amplitude amplification produces a correct answer with probability close to 1 using roughly 1/√p applications of the underlying algorithm. The classical equivalent requires 1/p applications, so amplitude amplification provides a quadratic speedup over classical repetition.

The technique is genuinely useful as a building block: any classical algorithm that succeeds with some probability can be quantumly amplified, often providing a quadratic improvement in the overall query complexity. Quantum amplitude estimation is the related primitive for estimating success probabilities themselves with a quadratic speedup.

Shor’s algorithm — the one that matters for cryptography

Shor’s algorithm, published by Peter Shor in 1994 (proceedings) and 1997 (journal), solves the integer factoring problem and the discrete logarithm problem in polynomial time on a quantum computer. This is the most consequential quantum algorithm ever discovered, and it is the reason post-quantum cryptography exists.

What it does

Given a composite integer N = pq where p and q are large primes, Shor’s algorithm recovers p and q in time polynomial in log N. The best known classical algorithm — the general number field sieve — runs in time sub-exponential in log N, which is the foundation of RSA security. Shor’s quantum algorithm reduces the problem from “infeasible at 2048-bit inputs” to “polynomial-time on a sufficiently large quantum computer.”

The same algorithmic structure solves the discrete logarithm problem in finite cyclic groups: given g and h in such a group, find x such that g^x = h. This is the foundation of Diffie-Hellman key agreement, the Digital Signature Algorithm, and elliptic curve cryptography. All of them fall to Shor’s algorithm.

How it works

The high-level structure of Shor’s factoring algorithm:

Pick a random number a less than N.
Compute the period r of the function f(x) = a^x mod N. This is the step where quantum mechanics is essential — classical computers cannot find the period in polynomial time, but a quantum computer can using the QFT.
Use the period r and standard number-theoretic techniques to extract a factor of N.

Step 2 is the quantum core. The algorithm prepares a superposition over all values of x, computes f(x) into a second register, and then applies the QFT to extract the period. The output of the QFT, after measurement, gives information about r with high probability. Standard classical post-processing then completes the factoring.

The full quantum circuit requires roughly O((log N)³) quantum gates and similar numbers of qubits. For RSA-2048, this means thousands of logical qubits and billions of gate operations. The classical post-processing (continued fractions to extract r, standard factoring once r is known) is negligible.

Resource estimates

The most-cited resource estimate for breaking RSA-2048 with Shor’s algorithm comes from the 2019 paper by Craig Gidney and Martin Ekerå, which projected roughly 20 million noisy physical qubits running for about 8 hours. More recent estimates with improved algorithmic compilation (Litinski, 2023, and others) bring the count down to roughly 4,000 logical qubits at distance-25 surface code, which still implies several million physical qubits at typical 2026 error rates.

The honest summary: a quantum computer that can run Shor’s algorithm against RSA-2048 does not yet exist, and the gap between current capability (~1,000-1,500 noisy physical qubits) and what is needed is several orders of magnitude. The migration to post-quantum cryptography is being driven by the long planning horizons of cryptographic systems and by harvest-now-decrypt-later concerns, not by any imminent capability. The Post-Quantum Cryptography page covers the migration in detail.

Variants and extensions

Shor’s algorithm has been generalized to broader hidden subgroup problems, with quantum polynomial-time solutions for abelian hidden subgroup problems generally. The non-abelian hidden subgroup problem — which would have broader cryptographic implications — has resisted polynomial-time quantum solutions for thirty years. The graph isomorphism problem, sometimes mentioned as a potential quantum target, lacks known polynomial-time quantum algorithms.

Grover’s algorithm — the modest but broadly applicable speedup

Grover’s algorithm, published by Lov Grover in 1996, solves the unstructured search problem with a quadratic speedup over classical search. Given a function f that returns 1 on a single “marked” input and 0 on all other inputs in a database of N entries, Grover’s algorithm finds the marked input in O(√N) queries, versus O(N) classically.

What it does and doesn’t do

Grover’s algorithm applies to any problem that can be framed as “find the input where some predicate evaluates to true.” The speedup is quadratic — not exponential — which means it provides meaningful improvement on large problem instances but does not make classically-intractable problems quantumly tractable.

For cryptographic applications, Grover’s algorithm reduces the effective key length of symmetric ciphers by half. AES-128 has 128 bits of classical security and 64 bits of effective security against a Grover-capable quantum adversary. AES-256 has 128 bits of effective quantum security. The standard mitigation is to use larger symmetric keys, as covered in the Symmetric Cryptography page.

For optimization, search, and similar problems, Grover provides a quadratic speedup if the problem can be cast in the right form. For most realistic optimization problems, the quadratic speedup is modest enough that the constant factors and the overhead of running on quantum hardware eliminate the advantage on the problem sizes that are actually classically intractable.

Resource costs

Grover’s algorithm is structurally simpler than Shor’s but has a different resource profile. The algorithm requires only O(log N) qubits to represent the search space, but it requires O(√N) iterations of the “Grover operator,” each of which involves the oracle (the quantum circuit that computes f) and a diffusion step. For practical problem sizes — searching a 2^64 keyspace — this means 2^32 iterations, each involving the full oracle circuit. The total gate count is enormous for cryptographically-relevant problem sizes.

For a quantum computer to break AES-128 via Grover’s algorithm, the total runtime including error correction overhead is estimated at thousands of years on plausible near-future hardware. Quantum attacks on symmetric cryptography are far less urgent than the quantum attacks on asymmetric cryptography, even before considering the doubled-key-size mitigation.

Quantum simulation — the original motivation

Richard Feynman’s 1982 talk that effectively founded the quantum computing field proposed quantum computers specifically as a tool for simulating quantum-mechanical systems that are intractable for classical computers. The motivation remains the most credible near-to-medium-term application for the technology.

The problem

Many problems in physics, chemistry, and materials science reduce to simulating the behavior of quantum-mechanical systems: predicting how a molecule’s electrons arrange themselves, calculating reaction rates, simulating the behavior of strongly correlated electron systems in materials. Classical computers can simulate small quantum systems exactly but the cost grows exponentially with system size — a system with n quantum degrees of freedom requires O(2^n) classical memory to represent its state.

Quantum computers can simulate quantum systems with polynomial overhead in the simulated system size. A quantum computer with n qubits can naturally represent a quantum system with n degrees of freedom, and standard simulation algorithms can evolve that state under the system’s Hamiltonian in polynomial time.

Hamiltonian simulation

The core primitive is Hamiltonian simulation: given a description of a quantum system’s Hamiltonian H, evolve a quantum state under e^(-iHt). The standard approach is Trotter decomposition — approximating e^(-iHt) by a sequence of simpler unitaries, each implementable as a short quantum circuit. More sophisticated approaches (Quantum Signal Processing, Linear Combinations of Unitaries) provide better scaling for specific Hamiltonian structures.

The resource cost depends on the structure of the Hamiltonian. Local Hamiltonians (where each term acts on a bounded number of degrees of freedom) admit efficient simulation. General Hamiltonians can be more expensive but are still typically polynomial in the system size.

Realistic applications

The applications that quantum simulation might unlock fall into a few categories:

Quantum chemistry. Calculating ground-state energies and reaction pathways for molecules of interest in chemistry and pharmaceuticals. Current classical methods (density functional theory, coupled cluster) are accurate enough for many applications but become expensive for large or strongly-correlated systems. Quantum simulation might extend the practical envelope to molecules that classical methods cannot handle.

Materials simulation. Understanding the properties of materials with strong electron correlations — high-temperature superconductors, certain magnetic materials, quantum magnets. Classical methods struggle with these systems; quantum simulation is structurally well-suited.

Nitrogen fixation. A specific high-profile target: simulating the FeMo cofactor of nitrogenase, the enzyme that fixes atmospheric nitrogen. A quantum-mechanical understanding of this catalyst might enable more efficient industrial nitrogen fixation (currently done via the energy-intensive Haber-Bosch process). Resource estimates suggest this is on the order of a few thousand logical qubits — substantially less than Shor’s algorithm against RSA, but still beyond current hardware.

Drug discovery. Simulating drug-target interactions at quantum-mechanical accuracy. The economic potential is enormous, the resource requirements are similar to other quantum chemistry applications, and the timeline is genuinely uncertain.

The honest read on quantum simulation: it is the most credible near-term application for quantum computers but it requires substantial logical qubit counts to deliver clear advantage over classical methods. The “quantum advantage in chemistry” milestone has not yet been crossed but is plausibly within reach in the latter half of the 2020s if hardware progress continues at its current rate.

HHL and quantum linear algebra — the cautious entry

The Harrow-Hassidim-Lloyd (HHL) algorithm, published in 2009, is often cited as a quantum algorithm with exponential speedup for solving linear systems of equations. The reality is more nuanced.

What HHL actually does

HHL takes a system Ax = b and produces a quantum state |x⟩ proportional to the solution vector x, in time polynomial in log(N) where N is the dimension of the system. The classical analog requires time polynomial in N. So far, exponential speedup.

The caveats are substantial:

The output is a quantum state, not classical numbers. Reading out all N entries of x requires N measurements, which eliminates the exponential speedup.
The matrix A must be efficiently invertible. Specifically, A must be sparse and well-conditioned (have bounded condition number).
The right-hand side b must be efficiently preparable. Producing the initial quantum state |b⟩ must be achievable in time polynomial in log(N).
Useful applications require all three conditions to hold simultaneously. Finding real-world problems where this is the case has been substantially harder than the original paper implied.

The de-quantization argument

In 2018, Ewin Tang (then an undergraduate) published a classical algorithm that achieved similar speedups for several problems that had been claimed as HHL applications, particularly in quantum machine learning. The classical algorithm used a different representation of the input (low-rank sampling access) and matched the quantum algorithm’s complexity for these specific applications.

The Tang result triggered a substantial reassessment of which problems actually benefit from HHL. The honest summary in 2026: HHL provides exponential speedups for specific narrow problem classes (matrix inversion with sparsity and well-conditioning), but many of the originally-claimed applications have been “de-quantized” by improved classical algorithms.

This is a useful pattern to know: a quantum algorithm with an apparent exponential speedup needs to be evaluated against the best possible classical algorithm, not against the obvious classical algorithm. Several other quantum algorithms have undergone similar reassessment.

NISQ-era hybrid algorithms

The NISQ era — Noisy Intermediate-Scale Quantum — was the term coined by John Preskill in 2018 for the period of quantum computing where systems have 50-1000 qubits but no error correction. The dominant algorithmic approach in this era has been variational hybrid algorithms that combine quantum circuits with classical optimization.

The hybrid pattern

The general structure of a variational quantum algorithm:

Choose a parameterized quantum circuit (the ansatz) with parameters θ.
Prepare a quantum state |ψ(θ)⟩ using the circuit.
Measure an observable to estimate some cost function C(θ).
Use a classical optimizer to update θ to reduce C(θ).
Repeat until convergence.

The appeal of variational algorithms is that they can run on noisy quantum hardware — the optimization adapts to the actual hardware behavior, including its noise — and they can be made to fit within the limited coherence times of current systems. The challenge is that the optimization landscape is typically non-convex, the gradients become exponentially flat (barren plateaus) for many natural ansatz choices, and the achievable quality is bounded by the noise of the underlying hardware.

VQE — Variational Quantum Eigensolver

The Variational Quantum Eigensolver, introduced by Peruzzo et al. in 2014, applies the variational pattern to finding ground-state energies of quantum systems — particularly molecules. The cost function is the expectation value of the molecular Hamiltonian; the optimizer searches parameter space to find the minimum.

VQE has been the dominant NISQ algorithm for quantum chemistry. The published results have been mixed. Small molecules (hydrogen, lithium hydride, helium hydride) have been simulated successfully on small quantum systems, but the demonstrations have generally been on molecules where classical methods are already accurate, and the quantum results have not exceeded classical accuracy for any molecule of practical interest.

The honest assessment: VQE is a real algorithm that runs on current hardware and produces real outputs. Whether it will scale to molecules where it outperforms classical methods is an open question. The optimization difficulties (barren plateaus, noise-induced trainability issues) are real obstacles, and several papers have argued that VQE is structurally limited from achieving exponential advantage over classical methods.

QAOA — Quantum Approximate Optimization Algorithm

The Quantum Approximate Optimization Algorithm, introduced by Farhi, Goldstone, and Gutmann in 2014, applies the variational pattern to combinatorial optimization problems — particularly Max-Cut and its variants. The cost function is the optimization objective; the ansatz alternates between problem-specific and mixing unitaries.

QAOA has received enormous attention as a potential quantum advantage for optimization. The published results have been substantially less optimistic than the early excitement suggested. Multiple analyses have shown that classical algorithms, including simple heuristics, often match or exceed QAOA’s performance on the problem sizes accessible to current hardware. The theoretical analysis of QAOA’s asymptotic performance is unresolved.

The honest assessment: QAOA runs on current hardware but has not yet demonstrated clear advantage over the best classical heuristics for any problem of practical scale. Whether it will scale to provide useful advantage at fault-tolerant scale is an open research question.

Quantum Machine Learning

Quantum machine learning (QML) is a broad term covering several different lines of work:

Quantum-enhanced classical ML — using quantum subroutines (HHL-style linear algebra, Grover-style search) within otherwise classical machine learning pipelines.
Variational quantum classifiers — neural-network-like models implemented as parameterized quantum circuits.
Quantum data analysis — algorithms that operate on data that is itself in quantum form.

The QML literature has been particularly affected by the Tang de-quantization results: many of the early advantage claims have been matched or exceeded by classical algorithms that exploit similar mathematical structure. Several theoretical results suggest that variational quantum classifiers are unlikely to provide exponential advantages over classical neural networks.

The honest assessment: quantum machine learning is an active research area with real ongoing work, but the clear practical advantages over classical machine learning that the early literature claimed have not materialized. The field continues but with substantially more modest expectations than five years ago.

What’s hyped vs what’s genuinely promising

A direct accounting, because the gap between hype and reality matters:

Hyped beyond evidence: QAOA for general optimization, QML for general machine learning, HHL for general linear systems, the claim that quantum computers will revolutionize finance or logistics. These claims have been made repeatedly and have not been backed by rigorous demonstration of advantage over the best classical methods on relevant problem sizes.

Genuinely promising but not yet proven: Quantum simulation for chemistry and materials, particularly for systems with strong electron correlation. The mathematical structure is favorable and the resource estimates suggest practical advantage is within reach with continued hardware progress. The first clear demonstration of useful chemistry advantage has not happened; it remains plausible within the next 5-10 years.

Proven but for problems with no practical use: Random circuit sampling, boson sampling. The 2019 Google Sycamore demonstration and the USTC Jiuzhang demonstrations are genuine quantum advantage results on problems specifically designed to be hard for classical computers. They prove quantum computers can outperform classical computers on something; they do not prove that something is useful.

Proven and consequential: Shor’s algorithm at sufficient scale would break RSA, DH, and ECC. The capability does not yet exist, but the algorithm is rigorously established and the resource estimates are well-understood. This is the algorithm driving the post-quantum cryptography migration.

Proven and modestly consequential: Grover’s algorithm at sufficient scale provides quadratic speedup on unstructured search. The capability does not yet exist for cryptographically-relevant problem sizes, and the doubled-key-size mitigation handles the symmetric-cryptography concern at modest cost.

Quantum advantage demonstrations

A short catalog of the demonstrations that have produced verifiable quantum advantage, with honest commentary on what they proved:

Google Sycamore — Random Circuit Sampling (October 2019). Sycamore performed a random circuit sampling task in 200 seconds that Google claimed would take a classical supercomputer 10,000 years. Subsequent classical algorithm improvements reduced the classical cost substantially (IBM published an analysis bringing it down to roughly 2.5 days). The demonstration remains real — there was a measurable gap between quantum and classical capability — but the gap was substantially smaller than the headlines implied.

USTC Jiuzhang — Gaussian Boson Sampling (December 2020). A Chinese research group at the University of Science and Technology of China demonstrated photonic Gaussian boson sampling that produced verifiable quantum advantage. Subsequent demonstrations (Jiuzhang 2.0, Jiuzhang 3.0) have extended the result.

Xanadu Borealis — Gaussian Boson Sampling (June 2022). Xanadu’s photonic system demonstrated Gaussian boson sampling at scales beyond classical reach, with full cloud accessibility — anyone could log in and run the experiment.

USTC Zuchongzhi — Random Circuit Sampling (2021-2024). A series of demonstrations using superconducting quantum processors at USTC, extending the random circuit sampling results to larger systems.

Google Willow — Below-Threshold Error Correction (December 2024). While not a “quantum advantage” demonstration in the traditional sense, Willow’s demonstration that increasing the surface code distance reduces logical error rate is arguably the most important quantum computing milestone of 2024. The result moved error correction from theoretical to engineering reality.

The honest summary of the quantum advantage demonstrations: they prove that quantum computers can outperform classical computers on specific contrived problems. They do not prove that quantum computers can solve useful problems classically intractable problems. The leap from “demonstrated quantum advantage on a sampling task” to “demonstrated quantum advantage on a problem someone wants the answer to” has not yet been made.

Resource estimates for major applications

For the applications that matter, the resource estimates have converged on roughly the following numbers (all assuming fault-tolerant operation with surface code error correction):

Application	Logical qubits	Physical qubits (at current error rates)	Runtime
Break RSA-2048	4,000-10,000	5-20 million	Hours to days
Break ECC P-256	2,000-5,000	3-10 million	Hours
Simulate FeMoco (nitrogen fixation)	2,000-5,000	3-10 million	Hours to days
Useful materials simulation	1,000-3,000	2-6 million	Hours
Useful drug-discovery chemistry	1,000-10,000	2-20 million	Hours to days

The numbers in the “physical qubits” column assume physical error rates of ~10⁻³ and surface code overhead of ~1,000-5,000 physical per logical. Better error rates or better codes would reduce these numbers; worse error rates would increase them.

The capability frontier in 2026 is roughly 1,000-1,500 noisy physical qubits with active error correction development. The gap to all of these applications is several orders of magnitude. The trajectory is favorable but the timeline is genuinely uncertain.

Quantum complexity classes

A brief note on the complexity-theoretic framing. The class of problems efficiently solvable on a quantum computer is BQP (Bounded-error Quantum Polynomial time). The relationship between BQP and the classical complexity classes is:

BQP contains P — any problem efficiently solvable on a classical computer is efficiently solvable on a quantum computer.
BQP is believed to be strictly larger than P — there are problems in BQP (factoring, discrete log) not known to be in P, and most theoretical computer scientists believe these are genuinely outside P.
BQP is contained in PSPACE — quantum computers cannot solve anything outside polynomial space.
The relationship between BQP and NP is unresolved — there are problems in BQP not known to be in NP (some sampling problems) and problems in NP not known to be in BQP (most NP-complete problems).

The structural implication: quantum computers are not “infinitely faster” than classical computers in any meaningful sense. They are believed to be strictly more powerful for a specific class of problems, but most problems classical computers handle remain handled equally well or better classically.

Where to go next on this site

Adjacent material on this site:

Quantum Computing — the umbrella overview covering the fundamental concepts.
Qubit Architectures — how the quantum computers that run these algorithms are actually built.
Quantum Error Correction — the layer that bridges noisy physical qubits to the logical qubits these algorithms require.
Quantum Hardware: State of the Art — what current systems can and cannot run.
Post-Quantum Cryptography — the cryptographic response to Shor’s algorithm.

The algorithm side of quantum computing is the part of the field that has been most prone to overclaiming and most resistant to honest assessment. The page is structured around what is rigorously known: the algorithms that work, the speedups they actually provide, the conditions under which they apply, and the resource requirements they imply. The hype is its own ecosystem; the science is what this page tracks.