Simple Algorithm
Quantum Computing · Ground State · 18 min

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 2n2^n 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 ≈π4N\approx\frac{\pi}{4}\sqrt N, 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 nn qubits in superposition, a single call to a circuit for ff produces

12n∑x∣x⟩∣f(x)⟩,\frac{1}{\sqrt{2^n}}\sum_{x} \ket{x}\ket{f(x)},

a state that involves all 2n2^n values of ff. This is called quantum parallelism.

The circuit below does exactly that for f(x0,x1)=x0 AND x1f(x_0,x_1) = x_0 \text{ AND } x_1. Two Hadamards spread qubits 0 and 1 over all four inputs, and a Toffoli gate writes ff 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 ff 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:

  1. Spread. Hadamard gates put the register into an equal superposition of all inputs.
  2. Mark. A call to the oracle, the black box computing ff, tags each input, usually by flipping the sign of its amplitude.
  3. Interfere. More gates make the amplitudes of wrong answers cancel and those of right answers add up (interference).
  4. 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 f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}, 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 2n2^n 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.

Predict before you look

With n=10n = 10 input bits there are 210=10242^{10} = 1024 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

29+1=5132^{9}+1 = 513. 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 nn.

The Deutsch–Jozsa algorithm spreads the input register with Hadamards, calls the oracle once so that each amplitude picks up a sign (−1)f(x)(-1)^{f(x)} (a trick called phase kickback), and applies Hadamards again. The amplitude of the all-zeros outcome then equals the average of the signs:

amp(0⋯0)=12n∑x(−1)f(x)={±1constant,0balanced.\text{amp}(0\cdots0) = \frac{1}{2^n}\sum_x (-1)^{f(x)} = \begin{cases} \pm1 & \text{constant}, \\ 0 & \text{balanced}. \end{cases}

For a constant ff all signs agree and add up. For a balanced ff they cancel exactly.

Think first One query versus 513 for n=10n=10. 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 2⋅2−20≈2×10−62\cdot2^{-20}\approx 2\times10^{-6}, for any nn. 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 ∣−⟩\ket{-}.

Grover: a needle in √N steps

Now a problem everyone has: search. Among NN items exactly one is marked, and the only way to learn anything is to ask the oracle "is item xx the one?". With no structure to exploit (no sorting, no hints), a classical computer must check items one by one: about N/2N/2 checks on average, NN in the worst case.

Grover's algorithm needs only about π4N\frac{\pi}{4}\sqrt{N} queries. It repeats two moves:

  • Oracle: flip the sign of the marked item's amplitude.
  • Diffusion: reflect every amplitude about the mean, a↦2aˉ−aa \mapsto 2\bar a - a.

The sign flip pushes the marked amplitude below the mean, so the reflection throws it far above the mean. Each round adds roughly 2/N2/\sqrt N to the marked amplitude.

Predict before you look

A list of N=1,000,000N = 1{,}000{,}000 items has one marked item. About how many Grover iterations give the highest success probability?

Show the answer

785 iterations

π4106=π4×1000≈785\frac{\pi}{4}\sqrt{10^6} = \frac{\pi}{4}\times 1000 \approx 785, versus about 500,000500{,}000 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 sin⁡2((2k+1)θ)\sin^2((2k+1)\theta), 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 rr steps, like ∣x0⟩+∣x0+r⟩+∣x0+2r⟩+⋯\ket{x_0}+\ket{x_0+r}+\ket{x_0+2r}+\cdots. The quantum Fourier transform (QFT) turns it into a superposition concentrated on multiples of N/rN/r. Measure, and you learn about the period rr.

On nn qubits (N=2nN = 2^n amplitudes) the QFT uses only about n2/2n^2/2 gates, while the classical fast Fourier transform of 2n2^n numbers takes about n 2nn\,2^n 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 ec n1/3(log⁡n)2/3e^{c\,n^{1/3}(\log n)^{2/3}} for an nn-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 n3n^3 gates. Shor's algorithm reduces factoring to period finding:

  1. Pick a random aa and consider the sequence a1,a2,a3,… mod Na^1, a^2, a^3,\ldots \bmod N. It repeats with some period rr.
  2. Find rr with the QFT. This is the quantum part.
  3. If rr is even and ar/2≢−1(modN)a^{r/2}\not\equiv -1 \pmod N, then gcd⁡(ar/2±1, N)\gcd(a^{r/2}\pm1,\,N) are factors of NN. This is ordinary arithmetic.
Think first Why can't a classical computer find the period by computing a1,a2,a3,… mod Na^1, a^2, a^3, \ldots \bmod N until the sequence repeats?

The period can be almost as large as NN itself. For a 2048-bit RSA modulus that is up to about 220482^{2048} steps. The quantum computer evaluates axa^x 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 nn interacting spins carry 2n2^n amplitudes. His proposal: build computers out of quantum parts. A quantum computer can reproduce the time evolution e−iHte^{-iHt} 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 HH 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

ProblemBest known classicalQuantumSpeedup
Factoring, discrete logarithmssub-exponential (number field sieve)polynomial (Shor)super-polynomial
Simulating quantum dynamicsexponential in general (believed)polynomialexponential (believed)
Unstructured search, NN itemsNN queriesN\sqrt N (Grover)quadratic, provably optimal
Estimating an average to error ε\varepsilon1/ε21/\varepsilon^2 samples1/ε1/\varepsilon (amplitude estimation)quadratic
NP-complete problems (e.g. SAT)exponential (believed)still exponential: square root of brute forceat most quadratic known
Sorting NN items by comparisonsNlog⁡NN\log NNlog⁡NN\log N (proven lower bound)none beyond constants
Parity of NN bits (queries)NNN/2N/2a factor of 2 only
Costs up to constants and polynomial factors. "Believed" means no proof is known either way.
Check your understanding

Which of these problems has a known quantum algorithm that is super-polynomially faster than the best known classical algorithm?

  1. Searching an unsorted list
  2. Sorting a list of numbers
  3. Factoring large integers
  4. 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:

LessonWhat you will do
Oracles & Phase Kickback: Deutsch–JozsaDerive phase kickback, Deutsch–Jozsa and Bernstein–Vazirani exactly
Grover's Search & Amplitude AmplificationProve the rotation picture and the π4N\frac{\pi}{4}\sqrt{N} iteration count
The Quantum Fourier Transform & Phase EstimationBuild the QFT circuit and estimate eigenphases
Shor's Factoring AlgorithmTurn a period into factors with continued fractions and gcds
Quantum SimulationApproximate e−iHte^{-iHt} with product formulas and bound the error
Quantum Complexity: BQP & BeyondDefine BQP and place it among P, NP, PP and PSPACE

Key takeaways

  • Quantum speedups come from interference, not from "trying everything": measuring nn qubits yields only nn bits.
  • Deutsch–Jozsa answers a global question about ff with one query, but its exponential edge vanishes against randomized classical algorithms.
  • Grover searches NN unstructured items in about π4N\frac{\pi}{4}\sqrt N 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.

Question 1

You prepare 12n∑x∣x⟩∣f(x)⟩\frac{1}{\sqrt{2^n}}\sum_x\ket{x}\ket{f(x)} with one call to ff, then measure both registers. What do you learn?

  1. All 2n2^n values of ff at once
  2. The input xx with the largest f(x)f(x)
  3. One random input xx together with f(x)f(x)
  4. Nothing: the measurement destroys the state before recording a result
Show the answer

C. One random input xx together with f(x)f(x)

The measurement returns a single basis state ∣x⟩∣f(x)⟩\ket{x}\ket{f(x)}, with xx uniformly random. That is no better than evaluating ff on a random input classically. Speedups need interference before the measurement.

Question 2

Compare Deutsch–Jozsa with a classical algorithm that is allowed to be wrong with probability 0.1%0.1\%. How big is the quantum advantage?

  1. Modest: about 11 random classical queries suffice, for any nn
  2. Exponential: the classical algorithm still needs 2n−1+12^{n-1}+1 queries
  3. Unbounded: no classical algorithm can solve the problem
  4. None: one classical query is enough too
Show the answer

A. Modest: about 11 random classical queries suffice, for any nn

Query kk random inputs and answer "constant" if all agree. This fails only for a balanced ff whose kk answers happen to agree, with probability 2⋅2−k2\cdot 2^{-k}. For k=11k=11 that is 2−10<0.1%2^{-10}<0.1\%, independent of nn. So against randomized algorithms the advantage is 1 query versus about 11.

Question 3

You run Grover's algorithm on N=8N = 8 items but do 3 iterations instead of the optimal 2. What happens to the probability of finding the marked item?

  1. It keeps rising, to about 99%
  2. It stays at about 94.5%: extra iterations do nothing
  3. It drops to exactly 0%
  4. It drops to about 33%
Show the answer

D. It drops to about 33%

Each iteration rotates the state by the same angle 2θ2\theta toward the marked item, with sin⁡θ=1/8\sin\theta = 1/\sqrt8. After 2 iterations it is nearly there (94.5%); a third carries it past, and the probability falls to sin⁡2(7θ)≈33%\sin^2(7\theta)\approx 33\%.

Question 4

What is the quantum computer's job inside Shor's factoring algorithm?

  1. Trying all possible divisors of NN in parallel
  2. Finding the period rr of the sequence ax mod Na^x \bmod N
  3. Computing gcd⁡(ar/2±1,N)\gcd(a^{r/2}\pm 1, N)
  4. Searching for a factor with Grover's algorithm
Show the answer

B. Finding the period rr of the sequence ax mod Na^x \bmod N

Shor's algorithm reduces factoring to period finding. The quantum part finds the period rr of ax mod Na^x \bmod N using the QFT; the gcd step is fast classical arithmetic.

Question 5

What do quantum computers offer for NP-complete problems such as SAT, as far as anyone knows?

  1. A polynomial-time algorithm, via Shor's algorithm
  2. Nothing at all: no speedup of any kind
  3. No polynomial-time algorithm is known; Grover-style search gives up to a quadratic speedup over brute force
  4. 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 2n2^n to 2n/22^{n/2}, which is still exponential.

Go deeper

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).