Grover's Search

Find one marked item among 16 by flipping a sign and reflecting about the mean. Stop too late, and the answer slips away again.

Quantum algorithmsKey searchdemo

Objectives

Trace one Grover iteration as an oracle step and a diffusion step, and say what each does to the amplitudes.
Find the best iteration count, about (π/4)√N, and explain why more iterations lower the chance.
Explain why Grover's algorithm halves the security bits of a key search but leaves AES-256 strong.

25%

Find one marked item among N with about √N tests, one iteration at a time.

oracle: a_marked → −a_marked diffusion: a_new = 2a-bar − a_old best count ≈ (π/4)√N

The task: find the one item that passes a test

There are N = 2^n items, numbered 0 to N − 1. A test f(x) returns 1 for one item and 0 for all others. For a key search, f(k) = 1 when key k turns known plaintexts into their ciphertexts; with enough known pairs, only the right key passes. Nothing about the items says where the marked one is, so a classical search tries items one by one: about N/2 tries on average when the answer is equally likely to be anywhere.

number of qubits n

n = 4, N = 16

the marked item (the test's secret)

items N

classical tries, average

Grover iterations, (π/4)√N

marked item

One iteration: flip the sign, then reflect about the mean

Start: H on every qubit gives all 16 items the same amplitude, 1/sqrt(16) = 0.250.

iterations done

marked amplitude

0.250

P(marked)

6.3%

P(any other item)

93.8%

More iterations is not always better

Each iteration turns the state by the same small angle toward the marked item. Past the best count it turns past it, and the probability falls again. Grover's algorithm must stop at about (π/4)√N iterations. The row with a rule at the left is that count.

Probability of measuring the marked item after each number of iterations, for N = 16.
Iterations	P(marked)	Classical, same number of tries
0	6.3%	0.0%
1	47.3%	6.3%
2	90.8%	12.5%
3 (best)	96.1%	18.8%
4	58.2%	25.0%
5	12.5%	31.3%
6	2.0%	37.5%
7	36.5%	43.8%

The classical column assumes k different guesses, so it reaches certainty only after N tries. With N = 16, Grover needs 3 iterations for 96.1%; 3 classical guesses give 18.8%.

What this means for a real key

For a k-bit key, N = 2^k. The counts below are idealized: they count evaluations of the test, and each Grover iteration must run a whole AES circuit on the quantum computer. The iterations also run one after another. Splitting the keys over p machines gives each machine N/p keys, so it saves only a factor of √p.

key size k, in bits

128

machines p = 2^j

2^0

average classical tries

2^127

Grover iterations in sequence on each machine, (π/4)·√(2^k / p)

about 2^63.7

For AES-128 on one machine that is about 2^63.7 AES evaluations in sequence. NIST still rates AES-128 at its lowest post-quantum security category, and AES-256 at its highest. Doubling the key length restores the margin, which is why symmetric cryptography survives.

Grover's query count is the best possible for a search with no structure (Bennett, Bernstein, Brassard and Vazirani, 1997). For a block cipher treated as a black box, no quantum algorithm does better, and no better quantum attack on full AES is known. Shor's algorithm is different: factoring has a period, and that structure gives a far larger speedup.

step 1/4

CPE 645 / CS 685

Grover's Search

Shor's Quantum Step

Mosca's Inequality