Quantum Algorithms
Where the speedups come from, and where they don’t.
A quantum computer does not try every answer at once and hand you the best one. It runs a carefully choreographed interference experiment on amplitudes so that wrong answers cancel. That trick gives dramatic speedups for a few special problems, modest ones for many, and none at all for others.
What you’ll learn
- Explain why "quantum parallelism" alone gives no speedup, and what role interference plays.
- Describe the oracle (query) model and how Deutsch–Jozsa answers a global question with one query.
- Run Grover's search, predict its iteration count , and explain why overshooting fails.
- Outline how period finding with the quantum Fourier transform lets Shor's algorithm factor integers.
- Sort problems by the quantum speedup known for them: super-polynomial, polynomial, or none.
The myth of trying everything at once
A popular story says a quantum computer "tries every answer in parallel". There is a grain of truth in it. With qubits in superposition, a single call to a circuit for produces
a state that involves all values of . This is called quantum parallelism.
The circuit below does exactly that for . Two Hadamards spread qubits 0 and 1 over all four inputs, and a Toffoli gate writes into qubit 2. Run it.
Think first Each shot handed you one input and one output. Could a classical computer have done as well?
Yes: pick a random input and evaluate once. Measuring the superposition gives one random sample and destroys the rest. Quantum parallelism by itself buys nothing. Speedups appear only when the amplitudes are made to interfere before you look.
Almost every quantum algorithm follows the same four moves:
- Spread. Hadamard gates put the register into an equal superposition of all inputs.
- Mark. A call to the oracle, the black box computing , tags each input, usually by flipping the sign of its amplitude.
- Interfere. More gates make the amplitudes of wrong answers cancel and those of right answers add up (interference).
- Measure. Read out the answer, which is now likely.
Deutsch–Jozsa: one question instead of half the inputs
Here is a puzzle with a promise. A box computes , and you are told it is either constant (the same output for every input) or balanced (0 on exactly half the inputs, 1 on the other half). Which is it?
Classically, even if half of the inputs all give the same answer, the box could still be balanced. To be certain in the worst case you must look at one more than half.
With input bits there are inputs. In the worst case, how many queries does a classical algorithm need to be certain whether the box is constant or balanced?
Show the answer
513 queries
. After 512 equal answers the box might still be balanced, with all 512 unseen outputs different. The 513th answer settles it. The quantum algorithm below needs one query, for any .
The Deutsch–Jozsa algorithm spreads the input register with Hadamards, calls the oracle once so that each amplitude picks up a sign (a trick called phase kickback), and applies Hadamards again. The amplitude of the all-zeros outcome then equals the average of the signs:
For a constant all signs agree and add up. For a balanced they cancel exactly.
Think first One query versus 513 for . Is this an exponential speedup in practice?
Not really. Let the classical algorithm make a tiny error: query 20 random inputs and answer "constant" if they all agree. It is always right on constant boxes, and wrong on balanced ones only with probability , for any . The exponential gap holds only against classical algorithms that must be certain. Gaps that survive randomness (Bernstein–Vazirani, Simon) come in the Excited State lesson Oracles & Phase Kickback: Deutsch–Jozsa, where you will also derive why the helper qubit must start in .
Grover: a needle in √N steps
Now a problem everyone has: search. Among items exactly one is marked, and the only way to learn anything is to ask the oracle "is item the one?". With no structure to exploit (no sorting, no hints), a classical computer must check items one by one: about checks on average, in the worst case.
Grover's algorithm needs only about queries. It repeats two moves:
- Oracle: flip the sign of the marked item's amplitude.
- Diffusion: reflect every amplitude about the mean, .
The sign flip pushes the marked amplitude below the mean, so the reflection throws it far above the mean. Each round adds roughly to the marked amplitude.
A list of items has one marked item. About how many Grover iterations give the highest success probability?
Show the answer
785 iterations
, versus about classical checks on average. A big win, but notice it is a square root, not a logarithm.
The Excited State lesson Grover's Search & Amplitude Amplification shows that the two reflections form a rotation, derives the success probability , and turns the trick into a tool that boosts any algorithm's success probability: amplitude amplification.
Hidden periods: the quantum Fourier transform
The most dramatic speedups exploit a different structure: hidden repetition. Suppose a superposition repeats every steps, like . The quantum Fourier transform (QFT) turns it into a superposition concentrated on multiples of . Measure, and you learn about the period .
On qubits ( amplitudes) the QFT uses only about gates, while the classical fast Fourier transform of numbers takes about steps. The catch: the output lives in amplitudes you cannot read out. The QFT pays off only inside an algorithm that needs just a few samples from its peaks.
In The Quantum Fourier Transform & Phase Estimation you will build the QFT from Hadamards and controlled phase gates and use it for phase estimation: reading out the eigenvalue of an operation. That subroutine sits inside Shor's algorithm and much of quantum chemistry.
Shor: factoring via period finding
Multiplying two large primes is easy; recovering them from their product is believed to be hard, and the security of RSA encryption rests on that belief. The best known classical method, the number field sieve, takes time growing roughly like for an -bit number: faster than exponential, but far slower than any polynomial.
In 1994 Peter Shor showed that a quantum computer can factor in polynomial time, roughly gates. Shor's algorithm reduces factoring to period finding:
- Pick a random and consider the sequence . It repeats with some period .
- Find with the QFT. This is the quantum part.
- If is even and , then are factors of . This is ordinary arithmetic.
Think first Why can't a classical computer find the period by computing until the sequence repeats?
The period can be almost as large as itself. For a 2048-bit RSA modulus that is up to about steps. The quantum computer evaluates on a superposition of all exponents and lets the QFT make the period show up in a few measurements.
Simulating nature
In 1982 Richard Feynman pointed out that simulating quantum systems on classical computers seems to need exponential effort, since interacting spins carry amplitudes. His proposal: build computers out of quantum parts. A quantum computer can reproduce the time evolution generated by a hamiltonian using a number of gates that grows only polynomially with the system size and the time (Lloyd, 1996).
The simplest method, trotterization, chops the evolution into many short steps, each applying one simple piece of at a time. More steps means less error.
Think first If simulating quantum physics is so natural, why not simply run the molecule itself and watch?
You can, and experiments do. But a real molecule gives you only the measurements nature allows, under the conditions you can create. A programmable quantum computer can simulate any Hamiltonian you write down, including hypothetical molecules and materials, and run algorithms such as phase estimation to read out energies precisely.
The map: where speedups do and don’t exist
| Problem | Best known classical | Quantum | Speedup |
|---|---|---|---|
| Factoring, discrete logarithms | sub-exponential (number field sieve) | polynomial (Shor) | super-polynomial |
| Simulating quantum dynamics | exponential in general (believed) | polynomial | exponential (believed) |
| Unstructured search, items | queries | (Grover) | quadratic, provably optimal |
| Estimating an average to error | samples | (amplitude estimation) | quadratic |
| NP-complete problems (e.g. SAT) | exponential (believed) | still exponential: square root of brute force | at most quadratic known |
| Sorting items by comparisons | (proven lower bound) | none beyond constants | |
| Parity of bits (queries) | a factor of 2 only |
Which of these problems has a known quantum algorithm that is super-polynomially faster than the best known classical algorithm?
- Searching an unsorted list
- Sorting a list of numbers
- Factoring large integers
- Solving SAT, an NP-complete problem
Show the answer
C. Factoring large integers
Shor's algorithm factors in polynomial time, while the best known classical algorithm is super-polynomial. Search gets only a quadratic speedup, sorting none, and no efficient quantum algorithm is known for NP-complete problems.
Your roadmap through the Excited State level of this topic:
| Lesson | What you will do |
|---|---|
| Oracles & Phase Kickback: Deutsch–Jozsa | Derive phase kickback, Deutsch–Jozsa and Bernstein–Vazirani exactly |
| Grover's Search & Amplitude Amplification | Prove the rotation picture and the iteration count |
| The Quantum Fourier Transform & Phase Estimation | Build the QFT circuit and estimate eigenphases |
| Shor's Factoring Algorithm | Turn a period into factors with continued fractions and gcds |
| Quantum Simulation | Approximate with product formulas and bound the error |
| Quantum Complexity: BQP & Beyond | Define BQP and place it among P, NP, PP and PSPACE |
Key takeaways
- Quantum speedups come from interference, not from "trying everything": measuring qubits yields only bits.
- Deutsch–Jozsa answers a global question about with one query, but its exponential edge vanishes against randomized classical algorithms.
- Grover searches unstructured items in about queries: a quadratic speedup that is provably optimal. Iterating too long makes it worse.
- The QFT exposes hidden periods; Shor's algorithm uses it to factor in polynomial time, which threatens RSA and elliptic-curve cryptography.
- Simulating quantum systems is the most natural application. For NP-complete problems only modest (at most quadratic) speedups are known.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
You prepare with one call to , then measure both registers. What do you learn?
- All values of at once
- The input with the largest
- One random input together with
- Nothing: the measurement destroys the state before recording a result
Show the answer
C. One random input together with
The measurement returns a single basis state , with uniformly random. That is no better than evaluating on a random input classically. Speedups need interference before the measurement.
Compare Deutsch–Jozsa with a classical algorithm that is allowed to be wrong with probability . How big is the quantum advantage?
- Modest: about 11 random classical queries suffice, for any
- Exponential: the classical algorithm still needs queries
- Unbounded: no classical algorithm can solve the problem
- None: one classical query is enough too
Show the answer
A. Modest: about 11 random classical queries suffice, for any
Query random inputs and answer "constant" if all agree. This fails only for a balanced whose answers happen to agree, with probability . For that is , independent of . So against randomized algorithms the advantage is 1 query versus about 11.
You run Grover's algorithm on items but do 3 iterations instead of the optimal 2. What happens to the probability of finding the marked item?
- It keeps rising, to about 99%
- It stays at about 94.5%: extra iterations do nothing
- It drops to exactly 0%
- It drops to about 33%
Show the answer
D. It drops to about 33%
Each iteration rotates the state by the same angle toward the marked item, with . After 2 iterations it is nearly there (94.5%); a third carries it past, and the probability falls to .
What is the quantum computer's job inside Shor's factoring algorithm?
- Trying all possible divisors of in parallel
- Finding the period of the sequence
- Computing
- Searching for a factor with Grover's algorithm
Show the answer
B. Finding the period of the sequence
Shor's algorithm reduces factoring to period finding. The quantum part finds the period of using the QFT; the gcd step is fast classical arithmetic.
What do quantum computers offer for NP-complete problems such as SAT, as far as anyone knows?
- A polynomial-time algorithm, via Shor's algorithm
- Nothing at all: no speedup of any kind
- No polynomial-time algorithm is known; Grover-style search gives up to a quadratic speedup over brute force
- An exponential speedup, because they try all assignments at once
Show the answer
C. No polynomial-time algorithm is known; Grover-style search gives up to a quadratic speedup over brute force
No efficient quantum algorithm for NP-complete problems is known, and most researchers believe none exists. Grover's algorithm square-roots the cost of brute-force search, from about to , which is still exponential.
Go deeper
- Oracles & Phase Kickback: Deutsch–Jozsa · The first quantum speedups, and the trick behind them.
- Grover's Search & Amplitude Amplification · Finding a needle in √N steps by rotating amplitude.
- The Quantum Fourier Transform & Phase Estimation · An exponentially fast Fourier transform, and how to use it.
- Shor's Factoring Algorithm · Factoring reduces to period finding, and period finding is quantum-easy.
- Quantum Simulation · Simulating nature with nature: Hamiltonian simulation.
- Quantum Complexity: BQP & Beyond · What quantum computers can efficiently solve, formally.
Further reading
- M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §1.4 and chs. 5–6 (Cambridge, 10th anniv. ed., 2010).
- A. Montanaro, "Quantum algorithms: an overview", npj Quantum Information 2, 15023 (2016).