Part I, Foundations · Lesson 5
Grover's algorithm: why AES survives
The short version
Imagine hunting for one marked card in a huge shuffled deck. Normally you'd check about half the deck. A quantum computer running Grover's algorithm needs only about the square root of the deck size, which sounds dramatic, but a square root of an astronomically large number is still astronomically large. That's why a quantum computer only dents AES encryption instead of breaking it.
You'll learn to
- Explain what unstructured search is and why it normally takes about N/2 guesses.
- Describe Grover's oracle and diffusion steps and watch amplitude amplification work.
- Explain why Grover "halves" key strength in theory but much less in practice.
- Choose sensible symmetric key and hash sizes for a post-quantum world.
Shor's algorithm is the quantum algorithm that breaks things. Grover's algorithm is the one that merely makes things a bit uncomfortable. Understanding the difference is how you avoid spending money on the wrong problem.
The problem: finding a needle with no clues
In 1996, Lov Grover, then at Bell Labs, described his algorithm with a phone-book puzzle. Imagine a phone directory of N names in random order (Grover’s own example), and you want to find the entry for a given phone number. There's no shortcut: the book isn't sorted by number. You have to check entries one by one. On average you'll check about half the book, N/2 entries, before you find it.
This is unstructured search: you can recognize the right answer when you see it, but nothing about wrong answers points you toward the right one.
Brute-forcing an encryption key is exactly this problem. Each candidate key can be tested (does it decrypt the data to something sensible?), but a wrong key gives no hint about the right one. That's what the avalanche effect guarantees.
Grover's trick: amplify the right answer
Grover showed that a quantum computer can solve unstructured search in about √N steps instead of N/2. For a million items, that's on the order of a thousand steps instead of half a million.
It works by amplitude amplification. Start with every item in equal superposition, so each has the same small amplitude. Then repeat two moves:
- The oracle flips the sign of the marked item's amplitude. The oracle doesn't tell you where the answer is. It's a circuit that recognizes the answer, such as "encrypt with this key and check the result." Flipping the sign doesn't change any probabilities yet, because a negative amplitude squared is still positive.
- Diffusion reflects every amplitude about the average. Because the marked item is now far below the average, reflecting it sends it far above. Everyone else shrinks slightly.
Each round grows the marked amplitude a little more. Try it:
With 16 items, three rounds take the marked item from a 6.3% chance to over 96%. A classical search would need about 8 guesses on average. Now press "Full step" a few more times.
Overshooting: the algorithm that must know when to stop
Keep going past the best point and the probability of the marked item falls. Grover's algorithm is really a rotation: each round turns the quantum state a fixed angle toward the answer. Turn too far and you rotate past it.
The best number of rounds is about π/4 × √N, roughly 0.785 × √N. You need to know (or estimate) N and the number of marked items to stop at the right moment. That's a small but real difference from the "just let it run" image many people have.
Grover's paper also points out that his algorithm is within a small constant factor of the fastest possible quantum algorithm for this problem. There's no hidden Shor-style shortcut for unstructured search. The square root is the speedup, full stop.
What it means for keys, in theory
A 128-bit key has N = 2128 possibilities. The square root of 2128 is 264. So in theory, Grover's algorithm needs about 264 rounds to find an AES-128 key, the same count as a classical brute-force search of a 64-bit key. That's the origin of the rule of thumb that Grover "halves" the effective bit strength of symmetric keys.
If that were the whole story, AES-128 would be in trouble. It isn't the whole story.
Why AES-128 survives in practice
Three practical facts make Grover far weaker than the "halving" headline suggests.
1. The steps must run one after another
Classical brute force splits beautifully across many machines: give each one a slice of the key space. Grover's algorithm doesn't. As NIST's post-quantum FAQ notes, Zalka proved in 1997 that getting the full quadratic speedup requires running all of Grover's steps in series. Split the search across many quantum computers and the total speedup shrinks: with M machines, each searching 1/M of the keys, you only gain a factor of √M in time, not M.
2. Each step is a whole AES computation
Each Grover round includes running AES itself as a quantum circuit, on error-corrected qubits. That's a deep, slow operation. 264 of them, strictly one after another, is an extremely long time even for an optimistic future machine.
3. Quantum hardware is expensive
NIST also points out that quantum hardware will likely be more expensive to build and use than classical hardware, which further narrows any practical advantage.
NIST's conclusion: it's quite likely Grover's algorithm will provide little or no advantage in attacking AES, AES-128 will remain secure for decades to come, and applications can continue to use AES with 128-, 192- or 256-bit keys.
And hash functions?
Grover's algorithm also speeds up finding an input that matches a given hash (a "preimage"), in the same square-root way. SHA-256's 256-bit output keeps a comfortable margin under that attack. As with AES, the practical limits above apply, and as with AES, conservative suites like CNSA 2.0 choose larger hashes for national security systems.
This resilience of hashes is good news later in the course: one family of post-quantum signatures, SLH-DSA, is built entirely from hash functions.
Shor versus Grover, side by side
| Shor's algorithm | Grover's algorithm | |
|---|---|---|
| Year | 1994 | 1996 |
| Problem | Factoring and discrete logarithms (structured) | Unstructured search |
| Speedup | From infeasible to efficient (polynomial time) | Quadratic: about √N instead of N |
| Targets | RSA, Diffie-Hellman, DSA, ECDH, ECDSA, Ed25519 | Symmetric keys (AES), hash preimages |
| Does a bigger key help? | Not meaningfully | Yes; a larger key restores the margin |
| Response | Replace the algorithm | Keep AES; prefer 256-bit keys for long-lived data |
The bottom row is the practical lesson. Public-key cryptography needs replacing. Symmetric cryptography at most needs a bigger dial setting. Don't let a vendor sell you a symmetric-encryption overhaul as the answer to the quantum threat.
What to remember
Grover's algorithm is real and elegant, and its √N speedup is provably the best possible for unstructured search. But it's a quadratic speedup on a serial machine, which against well-sized keys is a dent, not a breach. The real quantum emergency is in public-key cryptography, and the clock on that one may already be running. That's the final lesson of this track.
Go deeper: Grover as a rotation
Picture the quantum state as an arrow in a flat plane. One axis is "the marked item"; the other is "an even blend of all the unmarked items." At the start the arrow sits almost along the unmarked axis, tilted toward the marked axis by a small angle θ, where sin θ = 1/√N.
The oracle reflects the arrow across the unmarked axis. Diffusion reflects it across the starting direction. Two reflections make a rotation, so each round turns the arrow by 2θ toward the marked axis. After k rounds the marked item's amplitude is sin((2k + 1)θ).
The best k brings (2k + 1)θ closest to 90°, which works out to about π/4 × √N when N is large. For N = 16, θ ≈ 14.5°, and three rounds give 7θ ≈ 101°, a success probability of sin²(101°) ≈ 96%. That's exactly what the widget shows. A fourth round reaches about 130°, and the probability drops to about 58%: the overshoot.
Summary
- Grover's algorithm (1996) searches N unsorted items in about √N steps instead of about N/2.
- It works by amplitude amplification: an oracle flips the answer's sign, and diffusion reflects everything about the average.
- Running too many rounds overshoots; the best is about π/4 × √N.
- In theory it halves effective symmetric key strength, but its steps must run in series and each step is costly.
- NIST says AES-128 will remain secure for decades; CNSA 2.0 requires AES-256 and SHA-384/512 for national security systems.
- Shor demands replacing public-key algorithms; Grover at most calls for larger symmetric keys.
Questions
Get five of six right to mark the lesson complete. They also feed the final exam.
Sources
- Grover (1996), A fast quantum mechanical algorithm for database search
- NIST PQC FAQs: Grover's algorithm, Zalka (1997) and AES key sizes
- NIST FIPS 197: Advanced Encryption Standard (AES)
- NSA, Announcing the Commercial National Security Algorithm Suite 2.0 (CNSA 2.0)
