Computation

Quantum
Algorithms

Some problems that would take ordinary computers millions of years to solve could be cracked by a large quantum computer in days. This page explores the key algorithms that make that possible — what they do, how they work, and why it matters right now.

Shor's Algorithm Grover's Algorithm Quantum Fourier Transform Amplitude Amplification Complexity Theory BQP

What Makes a Quantum Algorithm?

Quantum Advantage and Where It Comes From

A classical computer works through possibilities one at a time — or in parallel batches, but still checking each candidate. A quantum computer can hold all possible answers in play simultaneously and then use the physics of waves to make wrong answers cancel out and correct answers reinforce each other. The result is that some problems can be solved with far fewer steps. (Formally: by exploiting superposition, entanglement, and interference — wrong-answer amplitudes interfere destructively, correct-answer amplitudes interfere constructively.)

This does not mean quantum computers are faster at everything. The advantage only appears for problems with a specific mathematical structure that quantum mechanics can exploit. For most everyday computing tasks, a classical machine is just as good — or better. (The complexity class BQP — Bounded-error Quantum Polynomial time — captures exactly which problems a quantum computer can solve efficiently. It is widely believed BQP does not contain all of NP, so quantum computers are not a general solution to hard combinatorial problems like the travelling salesman problem.)

Grover's Search Algorithm

A schematic circuit representation illustrating the key stages of GSA. The process includes initialization, where the qubits are prepared in a superposition state; marking, where the target item (items) in the database are identified and marked by the oracle; amplification, where the amplitude(s) of the marked item(s) are increased; and measurement, where the final result is obtained. Here, |0⟩, H, and X represent the initialization of the qubit to the |0⟩ state, the Hadamard gate, and Pauli's X gate, respectively. Source

Grover's Search Algorithm

Unstructured Database Search

Problem: You have a large pile of unsorted items and need to find one specific item. There is no index, no shortcut — just raw search.

Classical approach: On average you have to look through half the pile before finding it. Double the pile size, double the work. (Cost: O(N) — linear in the number of items.)

Quantum approach: Grover's algorithm finds the item in roughly the square root of the number of steps a classical search would need. A database of one million items requires about 1,000 quantum steps instead of 500,000 classical ones. This speedup is mathematically proven to be the best any quantum algorithm can do for this type of problem. (Cost: O(√N) — quadratic speedup, provably optimal for unstructured search.)

How it works: The algorithm starts by putting all possible answers into play at once. It then repeatedly runs two operations — one that marks the correct answer by flipping its sign (the oracle Uf: |x⟩ → −|x⟩), and one that boosts the marked answer's probability at the expense of all others (the diffusion operator, inversion about the mean). After roughly (π/4)√N repetitions, measuring the system returns the correct answer with high probability.

Why it matters: Grover's algorithm weakens the kind of encryption that uses one shared secret key (such as AES). On paper it cuts the effective strength of a key in half — a 128-bit key behaves like a 64-bit key. In practice the attack is far harder than that sounds: Grover's steps must run one after another and don't split efficiently across many machines, so standards bodies still treat 128-bit keys as acceptable and recommend 256-bit keys where data must stay secret for decades. (Grover gives a quadratic speedup on brute-force key search, 2ⁿ → 2^(n/2), but parallelising across M machines only gains √M; NIST's post-quantum guidance keeps AES-128, -192 and -256 approved.) Grover's idea, amplitude amplification, also appears as a building block inside many other quantum algorithms.

Grover's Algorithm in Five Steps

1. H⊗ⁿ|0⟩ → uniform superposition
2. Apply oracle Uf (phase flip target)
3. Apply diffusion: 2|s⟩⟨s| − I
4. Repeat ≈ (π/4)√N times
5. Measure → target with high probability

Shor's Factoring Algorithm

Integer Factorisation

Problem: Given a large number, find the two prime numbers that multiply together to produce it. This sounds simple, but it is the mathematical foundation of most internet encryption — and classical computers cannot do it at scale.

Classical approach: For the key sizes used in real encryption (such as RSA-2048, a roughly 600-digit number), the best classical algorithms would take longer than the age of the universe to factor. This intractability is what makes RSA secure today. (Best known classical algorithm: the General Number Field Sieve, running in sub-exponential time — exp(O((log N)^⅓ (log log N)^⅔)).)

Quantum approach: Shor's algorithm factors the same numbers in polynomial time — meaning the work grows manageably with the size of the number, not astronomically. (Cost: O((log N)³) gates. A variant by Regev — published in the Journal of the ACM in 2025 — reduces the gate count per run to about O(n^(3/2) log n) at the cost of more runs and qubits; Pilatte proved it works unconditionally, published in 2026.)

How it works: Rather than trying factors directly, Shor's algorithm transforms the factoring problem into finding a repeating pattern — specifically, the period of a mathematical function built from the number being factored. Finding that period on a classical computer is just as hard as factoring itself, but a quantum computer can extract it efficiently using the Quantum Fourier Transform, which detects periodicities in quantum superposition the same way a prism splits light into its component frequencies. Once the period is known, the prime factors follow from standard arithmetic. (The QFT extracts the period r of f(x) = aˣ mod N; the factors then follow via GCD computations using Euclid's algorithm.)

Cryptographic significance: A working large-scale quantum computer running Shor's algorithm would break RSA, Diffie-Hellman, and elliptic curve cryptography — the protocols securing virtually all internet traffic, banking, and private communications today. No machine that can do this exists yet, but the estimated size of one has shrunk fast. In 2019 the best estimate was about 20 million physical qubits; by 2025 it was under 1 million. Two 2026 proposals cut it again — to under 100,000 qubits using more efficient error-correcting codes, and to as few as about 10,000 atom-based qubits, though a machine that small would need months to factor a single RSA-2048 key. (Gidney & Ekerå 2019 → Gidney 2025, ~1,400 logical qubits, <1 week; Webster et al. "Pinnacle", Feb 2026, qLDPC codes, ~1 month; Cain et al., Mar 2026, reconfigurable neutral atoms. The 2026 papers are preprints and all assume hardware not yet built, with ~0.1% physical error rates.) Elliptic curve keys are shorter, so they are likely to fall before RSA. In response, NIST finalized the first three post-quantum cryptography standards in August 2024 — FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), and FIPS 205 (SLH-DSA) — with more following, and is urging organizations to migrate now.

The Quantum Fourier Transform

Classical Fourier Transform decomposing a composite wave into its component frequencies. The classical version processes a single signal sequentially. The Quantum Fourier Transform performs the same decomposition but on quantum amplitudes in superposition — where interference between all possible inputs happens simultaneously, rather than one frequency at a time. This interference mechanism is the foundation of algorithms like Shor's, in the same way Grover's relies on amplitude amplification. Source

Quantum vs Classical Complexity

Problem Best Classical Quantum Speedup Type What This Means
Integer factorisation Sub-exponential O((log N)³) Exponential Breaks RSA encryption. Work beyond any classical computer reduced to days or weeks on a future machine.
Discrete logarithm Sub-exponential O((log N)³) Exponential Breaks Diffie-Hellman and elliptic curve cryptography.
Unstructured search O(N) O(√N) Quadratic Search a million items in ~1,000 steps instead of ~500,000.
Quantum system simulation Exponential Polynomial Exponential Simulating molecules for drug discovery — classically intractable at scale.
Linear systems (HHL) O(N) O(log N) * Exponential * Theoretically powerful, but practical conditions are extremely restrictive. See caveat below.
Sorting O(N log N) No proven speedup None Quantum computers offer no advantage here. Classical sorting is already optimal.
NP-complete problems Exponential No proven polynomial speedup Unknown Quantum computers are not a magic solution to hard combinatorial problems.
Quantum computers are not universally faster. They offer provable advantages only for problems with the right mathematical structure. Most problems people care about — scheduling, logistics, AI training, general search — do not have that structure. (Formally: BQP contains P and is widely believed not to contain the NP-complete problems; it may also contain some problems outside NP. No efficient quantum algorithm for an NP-complete problem is known, and most researchers believe none exists — though this is unproven.)
* HHL caveat: The O(log N) quantum speedup for linear systems applies only under highly restrictive conditions: the matrix must be sparse and well-conditioned, quantum RAM (qRAM) is assumed for input loading, and the output is a quantum state — not directly readable classical data. Extracting classical results eliminates most of the speedup. Several researchers consider the practical advantage largely illusory for real-world problem instances.