Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 39 ยท Quantum Algorithms

Grover's Search Algorithm

Learn how Grover's algorithm finds a marked item among N in about sqrt(N) steps. Build the oracle and diffusion operator in a NumPy simulator.

Searching an unsorted list of N items takes about N/2 checks on average for a classical computer. Grover's algorithm (1996) finds the marked item with about (pi/4) * sqrt(N) oracle calls. For a million items, that is roughly 800 calls instead of 500,000. The speed-up is quadratic, not exponential, and it is provably the best any quantum algorithm can do for unstructured search.

Grover's algorithm is a template: any problem where you can check a candidate answer quickly (a puzzle, a hash, a constraint) can be wrapped into an oracle and searched this way. In this lesson you build it, watch the amplitudes move, and learn why running it too long makes it worse.

The idea: rotate toward the answer

Start with an equal superposition over all N = 2^n states. Each has amplitude 1/sqrt(N), so the marked state w is found with probability only 1/N. Grover repeats two steps, called one Grover iteration:

  1. Oracle. Flip the sign of the amplitude of the marked state: |w> -> -|w>. This is a phase flip, built from the same phase-kickback trick as in Deutsch-Jozsa.
  2. Diffusion. Reflect every amplitude about the average amplitude. In matrix form this is D = 2|s><s| - I, where |s> is the equal superposition.

The oracle makes the marked amplitude negative, which pulls the average slightly below the other amplitudes. Reflecting about the average then lifts the marked amplitude by roughly twice the distance to that average, while the others shrink a little. Each iteration grows the marked amplitude by a fixed angle.

The geometric picture

Two vectors span the whole story: the marked state |w> and the equal superposition of all unmarked states |r>. The state starts almost parallel to |r>, at a small angle theta from it, where sin(theta) = 1/sqrt(N). Each Grover iteration rotates the state by 2*theta toward |w>. After k iterations the success probability is

Text
P(k) = sin^2((2k + 1) * theta)

This is maximal when (2k + 1) * theta is close to pi/2, giving k ~ (pi/4) * sqrt(N).

flowchart LR
    A["Superposition<br/>P(w) = 1/N"] --> B["Oracle<br/>flip sign of w"]
    B --> C["Diffusion<br/>reflect about average"]
    C -->|"repeat ~ (pi/4) sqrt(N) times"| B
    C --> D["Measure<br/>w with high probability"]

One Grover iteration is oracle plus diffusion; repeat, then measure.

Watch it work

The simulator below keeps the full state vector. The oracle negates the marked entry and the diffusion computes 2 * mean - amplitude for every entry.

Python Grover on 16 items

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The probability climbs to about 96% after three iterations, then falls again. Grover's algorithm is a rotation, so overshooting rotates you past the target. Always compute the iteration count in advance.

Gate-level circuit for 3 qubits

The reflection 2|s><s| - I can be written with gates: Hadamards on every qubit, X on every qubit, a multi-controlled Z, then X and Hadamards again (up to a global sign). The oracle for a marked state is the same multi-controlled Z, sandwiched by X gates on the qubits whose marked bit is 0.

Python Grover built from H, X and multi-controlled Z

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For N = 8 two iterations are optimal (about 94.5%); a third one lowers the probability.

More than one solution

If there are M marked items, the angle becomes sin(theta) = sqrt(M/N) and the optimal iteration count is about (pi/4) * sqrt(N/M). You may not know M in advance. Two remedies exist: quantum counting estimates M with phase estimation (see Quantum Phase Estimation), and a randomized schedule of iteration counts finds a solution without knowing M.

Python Success probability formula vs simulation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simulation matches the closed formula exactly.

What Grover does and does not give you

  • Quadratic, not exponential. Brute-force problems stay exponential: searching a 128-bit key space still needs about 2^64 iterations. That is why symmetric keys are simply doubled in size for the post-quantum era, rather than abandoned.
  • The oracle is the real cost. Building a reversible circuit that checks a candidate (a hash, a Sudoku) can dominate everything. You also need it to run fault-tolerantly, which is far beyond today's hardware.
  • Amplitude amplification. Grover's loop generalizes: any algorithm A that finds a solution with probability p can be boosted to near certainty with about 1/sqrt(p) rounds, instead of 1/p classical repetitions. This powers many other quantum speed-ups.
  • No loading of data for free. Searching a classical database would require loading it into quantum memory, which costs at least as much as searching it.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Roughly how many Grover iterations are optimal for N = 1,000,000 items and one marked item?

    The count is (pi/4) * sqrt(N) = 0.785 * 1000, about 785.
  2. 2. What does the diffusion step do?

    Diffusion is the reflection 2|s><s| - I, which maps each amplitude a to 2*mean - a.
  3. 3. What happens if you run far too many Grover iterations?

    Each iteration rotates the state by a fixed angle, so P(k) = sin^2((2k+1)*theta) oscillates.
  4. 4. What kind of speed-up does Grover's algorithm give for unstructured search?

    From O(N) to O(sqrt N) oracle calls, and that is optimal for this problem.
  5. 5. With M marked items among N, how does the optimal iteration count change?

    More solutions mean a larger starting angle, so fewer rotations are needed.

Summary

  • Grover's algorithm alternates an oracle phase flip with a reflection about the average (diffusion).
  • Each iteration rotates the state by 2*theta; success probability is sin^2((2k+1)*theta).
  • About (pi/4) * sqrt(N/M) iterations are optimal; more is worse.
  • The speed-up is quadratic, optimal, and works for any problem with a checkable answer.
  • Amplitude amplification generalizes the loop to boost any success probability.

Next: The Quantum Fourier Transform