Grover's Algorithm | mysimulator.uk

A haystack with N straws

Searching an unsorted list of N items for the one that satisfies some condition is, classically, an O(N) problem: with no structure to exploit, you check items one at a time and on average need about N/2 tries. Lov Grover showed in 1996 that a quantum computer can do the same job with roughly √N calls to a black-box oracle - a quadratic speed-up. It is not the exponential jump that Shor's algorithm gives against factoring, but it is provably the best any quantum algorithm can do for unstructured search, and it is general enough to accelerate any problem that can be phrased as "check this candidate against a yes/no test."

Superposition first: asking every question at once

The algorithm starts by putting n qubits (N = 2^n) into an equal superposition of every possible index, using a layer of Hadamard gates on the all-zero state. Every one of the N basis states now carries the same amplitude, 1/√N, so the probability of measuring any particular state is 1/N - exactly the odds of a single classical guess. The trick is not to guess yet, but to reshape this flat landscape of amplitudes so that the marked state's amplitude grows at the expense of the rest, before ever measuring.

live demo · amplitudes climbing toward the marked state● LIVE

The oracle: a sign flip nobody can see

The oracle U_f is a unitary operator that recognises the marked item without revealing it: it leaves every non-marked basis state untouched and multiplies the marked state's amplitude by -1. Measured immediately, this phase flip would be invisible - the probability of any outcome is the amplitude squared, and squaring erases the sign. The whole algorithm is a way of turning that invisible phase difference into a visible probability difference before the qubits are ever measured.

Diffusion: inversion about the mean

The second operator, the diffusion operator, reflects every amplitude about their average value. Because the oracle just made one amplitude negative while leaving the rest positive and equal, the average dips slightly below the common value. Reflecting about that lowered average pushes the marked amplitude up by roughly 2/√N while nudging every other amplitude down by a tiny amount. One oracle call plus one diffusion is called a Grover iteration, and geometrically it is a fixed-angle rotation of the state vector within the two-dimensional plane spanned by the marked and unmarked subspaces.

|s⟩ = H^⊗n |0⟩                    every state gets amplitude 1/√N

repeat k ≈ (π/4)·√(N/M) times:
  |s⟩ ← Uf |s⟩                    oracle: flip the sign of marked states
  |s⟩ ← (2|s⟩⟨s| − I) |s⟩         diffusion: reflect about the mean amplitude

measure |s⟩                        marked state now dominates
P(marked after k steps) = sin²( (2k+1)·θ ),   θ = arcsin(√(M/N))

Why the square root, and not more

Each iteration rotates the state by the same small angle θ ≈ 2/√N (for one marked item among N), so the number of iterations needed to rotate roughly a quarter turn - the point where the marked amplitude is largest - is about (π/4)·√N. Run more iterations and the state keeps rotating past that point, so the success probability falls again and then rises, oscillating with a period of about π√N steps: this is the well-known overshoot problem, and it is why real implementations need at least a rough estimate of N (or the number of marked items M) beforehand. Bennett, Bernstein, Brassard and Vazirani proved in 1997 that no quantum algorithm treating the oracle as a black box can beat Ω(√N) queries, so Grover's algorithm is not just fast, it is optimal.

Breaking keys, and why AES-256 still holds

The most quoted application treats a symmetric cipher's key space as the unsorted list: given a plaintext/ciphertext pair, "is this key the right one" is an oracle, and Grover finds the key in about 2^(n/2) tries instead of 2^n. That halves the effective security of an n-bit key rather than breaking it outright, which is why the standard defence against a future large-scale quantum computer is simply to double the key length - AES-256 under Grover behaves like AES-128 does today, and AES-128 is still considered safe against classical attackers. This is a much gentler threat than Shor's algorithm poses to RSA and elliptic-curve cryptography, which it breaks completely and efficiently rather than merely weakening.

Frequently asked questions

Does Grover's algorithm work on any unsorted list?

Only if you can turn membership testing into a quantum oracle - a unitary circuit that flips the sign of the marked state without reading it classically first. Grover does not scan raw data; it amplifies the amplitude of whichever basis state the oracle recognises, so the speed-up only exists where such an oracle can be built.

What happens if you run too many Grover iterations?

The state vector keeps rotating by a fixed angle every iteration, so past the optimal step count it rotates past the marked axis and the success probability falls again, eventually returning almost to zero before climbing back up. Overshooting is a real bug, not a theoretical curiosity - you must know N (or M) reasonably well to pick the iteration count.

Does Grover's algorithm break AES encryption?

It weakens it but does not break it. Brute-forcing an n-bit key classically takes about 2^n tries; Grover's algorithm needs about 2^(n/2), which is the same work as brute-forcing a key half the length. AES-256 under a Grover attack behaves roughly like AES-128 does today, which is still considered secure, so the standard response is simply to use longer keys.

Try it live

Everything above runs in your browser — open Grover's Algorithm and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Grover's Algorithm simulation

Grover's Algorithm: Searching in the Square Root of Time