Computation

Quantum
Algorithms

Some problems that would take ordinary computers millions of years to solve can be cracked by a quantum computer in minutes. 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 threatens symmetric cryptography — it effectively halves the security of encryption key lengths. A 128-bit key becomes only as strong as a 64-bit key against a quantum adversary. It also appears as a subroutine inside many other quantum algorithms.

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 — roughly O(exp((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)³). A 2023 variant by Regev reduces the gate count further to O(n^(3/2) log n), with unconditional correctness proved by Pilatte in 2024.)

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. The threat is closer than it was: a March 2026 Caltech study projects RSA-2048 could be broken with as few as ~11,000–14,000 physical qubits using neutral-atom architectures, far below earlier estimates of ~1 million qubits. 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) — and is urging organizations to begin migrating immediately.

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. Centuries of classical work reduced to hours.
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: the complexity class BQP is believed to sit between P and NP but not contain all of NP. A quantum computer cannot solve NP-complete problems in polynomial time — at least no proof of this exists, and most researchers believe it is impossible.)
* 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.