Case Study: Costing Grover Against AES-128

Executive Summary

"Grover halves your key length" is the standard one-line summary, and it produces the standard conclusion: AES-128 offers 64 bits of quantum security, which sounds alarmingly close to breakable.

The one-liner is correct about the query count and badly misleading about the cost. This case study performs the full resource estimate — reversible AES circuit, iteration count, error correction, wall-clock time — and arrives at a number that explains why NIST's guidance is "use AES-256," a recommendation carrying roughly zero urgency, rather than "abandon symmetric cryptography."

Skills applied

• Applying Grover to a concrete cryptographic search (§13.14).
• Estimating reversible circuit cost for a real cipher (§13.15).
• Combining query count, gate cost, and error-correction overhead into an end-to-end estimate.
• Reasoning about parallelism asymmetries between classical and quantum attacks.

Phase 1: The naive estimate

Key space $N = 2^{128}$, one correct key, so $M = 1$:

$$k_{\text{opt}} = \frac{\pi}{4}\sqrt{2^{128}} = \frac{\pi}{4}\cdot 2^{64} \approx 1.4\times10^{19}$$

About $2^{64}$ Grover iterations. Compared to $2^{127}$ expected classical trials, that is a factor of $2^{63}$ — genuinely enormous.

If an iteration took one nanosecond, the attack would finish in about 460 years. Already not "instant," and we have not yet counted what an iteration costs.

Phase 2: What one iteration actually contains

Each Grover iteration must evaluate AES reversibly, in superposition: the oracle encrypts a known plaintext under the superposed key and checks the result against the known ciphertext.

Published resource estimates for reversible AES-128 (Grassl et al. and successors) put one encryption at roughly:

And each Grover iteration needs the encryption twice — once forward, once to uncompute — plus the diffusion operator.

$$\text{Total } T \text{ gates} \approx 2 \times 10^{6} \times 1.4\times10^{19} \approx 3\times10^{25}$$

Thirty septillion $T$ gates, all of which must execute coherently in sequence.

Phase 3: Error correction

A circuit of $3\times10^{25}$ operations requires a logical error rate well below $10^{-26}$ for the computation to survive. That drives everything.

Surface-code distance. Logical error per cycle scales roughly as $(p/p_{\text{th}})^{(d+1)/2}$. At a physical error rate $p = 10^{-3}$ against threshold $p_{\text{th}} \approx 10^{-2}$, reaching $10^{-26}$ needs roughly $d \approx 51$, i.e. about $2d^2 \approx 5{,}200$ physical qubits per logical qubit.

Physical qubits. 3,000 logical qubits × 5,200 ≈ $1.6\times10^{7}$, plus magic-state factories. Those factories dominate area in $T$-heavy circuits; a realistic total is on the order of $10^{8}$ physical qubits.

Time. Logical gates take many surface-code cycles — roughly $d$ cycles of ~1 μs each, so ~50 μs per logical operation, and $T$ gates additionally wait on magic-state supply. Even at an optimistic $10^{-7}$ s per $T$ gate with heavy parallelism across factories:

$$3\times10^{25} \times 10^{-7}\,\text{s} = 3\times10^{18}\,\text{s} \approx 10^{11}\,\text{years}$$

About ten times the age of the universe, on a hundred-million-qubit machine.

Phase 4: The parallelism asymmetry

The comparison gets worse for the attacker when you consider scaling out.

Classical brute force parallelizes perfectly. A million machines give a million-fold speedup, exactly. Bitcoin's network demonstrates the point at $10^{20}$ hashes per second sustained.

Grover parallelizes terribly. Split the key space across $p$ quantum computers and each searches $N/p$ items in $\sqrt{N/p}$ iterations — a speedup of $\sqrt p$, not $p$. To gain a factor of 1,000 you need a million machines.

This asymmetry erodes the quadratic advantage precisely in the regime where an attacker would have resources. Against a well-funded adversary running $10^6$ classical machines, the effective quantum advantage falls from $2^{63}$ to roughly $2^{53}$ — still large, and still nowhere near enough to make a $10^{11}$-year computation feasible.

Phase 5: What this means for practice

The recommendation is simply "prefer AES-256." Doubling the key length costs a negligible amount of performance and restores the pre-quantum margin permanently, because Grover's exponent is fixed at ½ and no better quantum algorithm exists — BBBV proves it.

Contrast the situation for public-key cryptography: Shor is exponential, so no key-size increase rescues RSA. Doubling RSA's key length adds a few bits of quantum security at enormous performance cost. That is why the migration story is urgent for RSA and ECC and relaxed for AES.

The asymmetry to remember. Grover is a quadratic speedup that key-lengthening defeats. Shor is an exponential speedup that key-lengthening cannot defeat. Triage accordingly.

Phase 6: Where Grover is worth taking seriously

Not on 128-bit key spaces. But the algorithm remains valuable where $N$ is modest and structure is absent:

• Small search spaces inside larger algorithms — amplitude amplification as a subroutine, boosting a heuristic's success probability from $p$ to near 1 in $O(1/\sqrt p)$ rounds.
• Constraint satisfaction with cheap predicates, where the oracle is a handful of clauses rather than a block cipher.
• Quantum counting / mean estimation, where the same machinery estimates quantities quadratically faster.

The pattern: Grover pays when the oracle is cheap and $N$ is small enough that $\sqrt N$ iterations fit inside a coherence or error-correction budget. A block cipher fails both tests.

Discussion Questions

1. Grover reduces $2^{128}$ to $2^{64}$ queries and the attack still takes $10^{11}$ years. Identify each factor between "query count" and "wall clock."
2. Classical brute force parallelizes linearly, Grover as $\sqrt p$. Derive the second claim and explain its strategic significance.
3. Doubling the key defeats Grover but not Shor. Explain from the structure of each speedup.
4. Where in the estimate is the greatest uncertainty? If reversible AES were 10× cheaper, would the conclusion change?

Your Turn: Extensions

• Implement Grover for a toy 8-bit "cipher" and confirm $\frac{\pi}{4}\sqrt{256} = 12$ iterations.
• Look up a reversible AES resource-estimate paper and compare its $T$-count against the figure used here.
• Compute the surface-code distance needed for a $10^{20}$-gate circuit at $p=10^{-4}$ and compare to $p=10^{-3}$.
• Derive the $\sqrt p$ parallel scaling formally.

Key Takeaways

• Grover's $2^{64}$ iterations against AES-128 each require a full reversible AES circuit, pushing the total to ~$3\times10^{25}$ $T$ gates.
• Error correction at that scale implies ~$10^{8}$ physical qubits and runtimes on the order of $10^{11}$ years.
• Grover parallelizes as $\sqrt p$ while classical brute force parallelizes as $p$, eroding the advantage exactly where an attacker has resources.
• Doubling the symmetric key length permanently defeats Grover, because BBBV forbids anything better than quadratic.
• Grover pays only when the oracle is cheap and $N$ is small. Block ciphers fail both conditions; Shor against RSA is the threat that actually matters.