Part 9: Grover and the Honest Speedup
Table of Contents
(Updated: July 2026)
This is Part 9 of Quantum Computing for Cybersecurity Professionals, an 11-part series that builds quantum computing from the ground up for security and IT professionals who know classical crypto but have no physics background. No lies-to-children, no hype, every claim checkable with arithmetic. Read the full series online or download the free ebook.
Every time I walk a security team through Shor’s algorithm, the same hand goes up before I finish. If quantum computers eat RSA and elliptic curves, what do they do to AES, and do we need 512-bit keys?
Most textbooks give the same one-line answer. Grover’s algorithm searches an unstructured space quadratically faster, so a 128-bit key offers 64 bits of security against a quantum attacker and a 256-bit key offers 128. The usual advice is to double your key lengths and stop worrying.
Now read what the US National Security Agency (NSA) actually mandates. In its Commercial National Security Algorithm Suite 2.0 (CNSA 2.0), which applies to US national security systems, the NSA requires the highest parameters on offer for every other primitive: ML-KEM-1024, ML-DSA-87, SHA-384 or better. For symmetric encryption it asks for AES-256 and names no larger variant. Even on the textbook accounting, an attacker still faces a notional $$2^{128}$$ of work against AES-256, which is ample. I see nothing in CNSA 2.0 to suggest that the NSA considers the halving an operational problem.
The halving figure is a count of ideal oracle queries, with no allowance for the time, hardware, or error correction an attacker needs to run them. This part covers how Grover’s algorithm works, the proof that its quadratic speedup is the maximum, why almost no attacker could collect even that speedup, and which symmetric key length to use.
What Grover actually does
Grover’s algorithm, published by Lov Grover in 1996, solves the problem Shor’s algorithm cannot address: finding a needle in an unstructured haystack. Given a function that says yes to exactly one input out of $$N$$ and no to everything else, find the yes. Key search is the canonical instance, and the haystack is every key in the space. The function reversibly tests a candidate key $$k$$ against several known plaintext-ciphertext pairs. A single pair is not enough, because far too many AES-256 keys map a given 128-bit plaintext block to the same ciphertext.
Classically, you have no shortcut. The right key relates to the wrong keys by nothing except being right, so you try candidates until one works, averaging $$N/2$$ attempts. In Part 7 I explained why a quantum computer cannot do to this problem what it does to factoring: with no global structure to imprint, there is no closing transform that concentrates amplitude onto the answer in one shot. AES is a highly structured algorithm, but cipher designers have spent fifty years making sure an attacker cannot use its structure to beat generic search. Grover’s algorithm is therefore the best attack anyone has against AES.
Grover’s algorithm takes a slower route. It uses the four moves from the earlier parts of this series and repeats the third one in a loop. Prepare the uniform superposition over all $$N$$ keys, each with amplitude $$1/\sqrt{N}$$. Imprint by flipping the sign of the correct key’s amplitude, which the oracle does without anyone knowing which key it flipped. Then interfere, using an operation called inversion about the mean: compute the average of all amplitudes and reflect every amplitude through it. The flipped amplitude is below the average, so reflecting it through the mean raises it; the other amplitudes are slightly above the average, and the same reflection lowers each of them a little. Repeat. With each pass, the answer’s amplitude grows and every wrong key’s amplitude shrinks. After about $$\sqrt{N}$$ passes, the answer’s amplitude is close to one, and you measure to read out the key.
Instead of trying every key at once, the algorithm rotates amplitude onto the answer one small step per iteration, until the correct key’s measurement probability, the square of its amplitude under the Born rule, is close to one.
THE ARITHMETIC: One Grover iteration, by hand.
Four keys, one correct, say key number four. Start uniform: every amplitude is $$1/2$$, since $$4 \times (1/2)^2 = 1$$.$\left(\tfrac{1}{2},\ \tfrac{1}{2},\ \tfrac{1}{2},\ \tfrac{1}{2}\right)$
Imprint. Flip the sign on key four: $$(1/2,\ 1/2,\ 1/2,\ -1/2)$$.
Interfere. The mean of those four numbers is $$(0.5 + 0.5 + 0.5 – 0.5)/4 = 1/4$$. Reflect each amplitude through the mean, using $$a \rightarrow 2(\text{mean}) – a$$:
Keys one to three: $$2(1/4) – 1/2 = 0$$. Key four: $$2(1/4) – (-1/2) = 1$$.
Final state $$(0, 0, 0, 1)$$. After one iteration the wrong keys have amplitude zero and the right key has amplitude one, so a measurement returns key four with certainty.
Why $$\sqrt{N}$$ in general: each iteration rotates the state by a small fixed angle of roughly $$2/\sqrt{N}$$, and reaching the answer takes a quarter turn, $$\pi/2$$. Dividing $$\pi/2$$ by $$2/\sqrt{N}$$ gives about $$0.79\sqrt{N}$$ iterations. For a 128-bit key, $$\sqrt{N} = 2^{64}$$.
Quadratic is the ceiling, and that is a theorem
Nobody is going to find a better generic quantum search algorithm, because the quadratic limit is a theorem. In 1997, Bennett, Bernstein, Brassard, and Vazirani showed that no quantum algorithm can search an unstructured space in fewer than about $$\sqrt{N}$$ queries. Christof Zalka tightened the result in 1999 and showed that Grover’s algorithm meets that bound exactly. Anyone who dismisses quantum attacks altogether has to concede this much: the quadratic speedup is real and optimal.
The same bound is a ceiling. A quantum computer cannot search a structureless space faster than the square root of its size, so against symmetric cryptography the machine that breaks RSA is only a modestly better key-guessing engine. How modest depends on a detail most textbooks omit: Grover’s iterations have to run one after another.
Why Grover’s iterations must run one after another
The $$2^{64}$$ figure counts iterations that one coherent machine has to run in strict sequence, without interruption, so you cannot spread the work across a data center.
Each iteration transforms the amplitudes produced by the previous one, and, as I showed in Part 3, you cannot checkpoint the intermediate state: reading it destroys it, and copying it is forbidden. There is no save file and no map-reduce. If you split the keyspace across $$M$$ quantum computers, each one searches a smaller haystack but still needs $$\sqrt{N/M}$$ iterations. The wall-clock speedup is therefore $$\sqrt{M}$$, against $$M$$ for classical brute force. In total the $$M$$ machines make $$\sqrt{NM}$$ oracle calls, more than the $$\sqrt{N}$$ a single machine would. A thousand machines cut the wall-clock time by a factor of about thirty-two; a million machines cut it by a factor of a thousand. Classical brute force speeds up in proportion to the machines you add, but a quantum attacker gets only the square root of that benefit.
The attack therefore needs a single error-corrected quantum computer to execute $$2^{64}$$ iterations back to back. Each iteration contains a full AES circuit in superposition. Each logical operation in that circuit is built from many physical operations under continuous error correction (the subject of Part 10), and the machine must maintain coherence through all of them. With plausible numbers on the clock, as in the box below, the wall time for AES-128 comes out in the billions of years.
NIST built this serial-time limit into the post-quantum standardization criteria as a parameter called MAXDEPTH: a cap on how long a serial quantum computation any real attacker could plausibly run. An attacker who cannot finish within that cap has to split the search across machines, and Grover’s quadratic advantage shrinks with every split. NIST wrote the cap into its security categories and stated plainly that its reference primitives give substantially more quantum security than a naive reading suggests. Grassl, Langenberg, Roetteler, and Steinwandt built the first detailed quantum circuits for AES to make these estimates concrete. Jaques, Naehrig, Roetteler, and Virdia later costed depth-limited attacks properly and found that an attacker held to a depth limit has to parallelize, and the parallel attack needs more gates in total.
The halving figure counts ideal oracle queries, which is a different quantity from the cost of any attack anyone knows how to mount. People who quote it as the cost of an attack make a conservative number look frightening. Cryptographer Filippo Valsorda made the same argument this year and concluded that quantum computers are not a practical threat to 128-bit symmetric keys.
THE ARITHMETIC: One illustrative wall clock.
AES-128 under Grover needs about $$2^{64} \approx 1.8 \times 10^{19}$$ iterations, in sequence. Each iteration includes at least one AES-128 encryption implemented as a reversible quantum circuit. Published circuits are thousands of layers deep, so I assume $$10^4$$ sequential logical operations per iteration, which is generous to the attacker.
Total serial depth: $$1.8 \times 10^{19} \times 10^4 \approx 1.8 \times 10^{23}$$ logical operations, strictly one after another.
For the clock, I take Part 8’s hardware assumption of a one-microsecond surface-code cycle and grant the attacker a full logical operation per microsecond, which is wildly optimistic. Then:$1.8 \times 10^{23}\ \mu s = 1.8 \times 10^{17}\ \text{seconds} \approx 5.7 \times 10^{9}\ \text{years}$
Under these stated assumptions, that is roughly six billion years of uninterrupted, coherent, error-corrected computation. The universe is 13.8 billion years old. With a logical clock a thousand times faster, the attack still takes six million years. An attacker who parallelizes to finish inside a year needs a wall-clock speedup of about $$5.7 \times 10^{9}$$, which under the $$\sqrt{M}$$ rule means on the order of $$10^{19}$$ separate fault-tolerant machines. If you change the oracle depth or the clock speed, you get a different figure, so do not quote six billion years as the answer. Under any set of assumptions, the iterations stay serial and each one is a full cipher circuit. Extra machines barely shorten the run.
AES-256 needs $$2^{128}$$ iterations, which multiplies the six billion years by a further $$2^{64}$$.
(These are order-of-magnitude figures meant to be checkable, not a published resource estimate. The authors of the circuit-level analyses cited above reach the same conclusion with more rigorous methods.)
WHERE THIS BREAKS: Two burglars, two methods.
I have used a lock analogy since Part 1, and with Grover explained, both of its burglars now have a mechanism. Shor is the burglar who studies the lock’s blueprint and machines a key from the design. Adding pins does not stop him, because the flaw he exploits is in the design itself. Grover is the burglar who tries keys faster than you thought possible. Locksmiths have always answered that kind of burglar by adding pins until trying every key is hopeless.
The analogy stops at the size of the speedup. Grover’s “faster” is a square root, which a defender can outrun cheaply. Every bit you add to the key doubles the classical attacker’s work and multiplies the quantum attacker’s work by about 1.4, so every two bits add a full bit of quantum security; a 256-bit key restores what a 128-bit key would notionally lose. On paper, defenders win that arms race permanently, even before you account for the sequential-depth limit above. The open question for AES is therefore whether anyone can run Grover at all.
Why AES-256 is the conservative answer
In CNSA 2.0, the NSA demands maximum parameters for the primitives it considers exposed and leaves AES-256 alone. An agency protecting material for fifty years is not treating symmetric encryption as an emergency. I cannot read the NSA’s mind about how much of Grover’s asymptotic advantage it thinks is collectible, and neither can anyone else. What I can read is NIST’s published costing model, in which NIST prices attacks under a depth limit and treats the query count and the attack cost as separate quantities.
My recommendation matches CNSA 2.0: use AES-256, and defend that choice in a meeting with the arithmetic above. AES-128 is nowhere near falling. Move to AES-256 anyway, because the larger key costs you almost nothing, the guidance is unambiguous, and people who cut cryptographic margins to the theoretical minimum have regretted it before. If the data you encrypt with AES-128 loses its value quickly and your key hierarchy is mature, schedule the upgrade with routine maintenance. Reserve your emergency budget for the public-key migration.
Tell your next steering committee that AES remains secure against quantum attack.
What Grover does to hashes
Inverting a hash is also unstructured search, so Grover’s algorithm works against it: SHA-256 preimage resistance drops from $$2^{256}$$ to a notional $$2^{128}$$, and the sequential-depth limits above apply in full. Even $$2^{128}$$ is a comfortable margin.
Collision resistance is the subtler case, and here many commentators overstate the quantum threat. Brassard, Høyer, and Tapp published an algorithm that finds collisions in roughly the cube root of the search space, but it needs quantum memory on the order of that same cube root. For SHA-256, that means storing and querying something like $$2^{85}$$ quantum-accessible records, in a quantum memory no more buildable than a quantum computer the size of Belgium. The practical collision attack is still classical: parallel collision search on ordinary hardware, as van Oorschot and Wiener worked it out in the 1990s. The quantum “speedup” on collisions is an artifact of counting queries and ignoring memory. SHA-256 holds. The NSA asks for SHA-384 in CNSA 2.0 for extra margin.
MYTH AUTOPSY: “Quantum computers will break all encryption.”
Vendors have put this headline in a thousand decks. With the mechanisms from this series, you can now check it against the actual casualty list. Public-key cryptography built on factoring or discrete logs falls completely, because Shor’s algorithm uses interference to extract the periodic structure hidden in those problems. Symmetric ciphers and hash functions hold, because nobody has found structure in them that allows a Shor-style shortcut. Against them an attacker has only Grover, which moves amplitude onto the answer one sequential iteration at a time while the haystack doubles with every key bit you add.
The fix is also already standardized: NIST’s post-quantum standards define new classical algorithms, running on the hardware you own today, to replace the broken public-key ones. AES stays in use, unchanged, through the transition.
Say instead: quantum computers break the public-key algorithms that depend on factoring and discrete logs. Symmetric ciphers and hashes hold, with larger parameters as a margin.
ATTACKER’S-EYE VIEW: Nobody will Grover your AES key.
In a TLS handshake, the two endpoints agree an AES-256 session key using elliptic-curve Diffie-Hellman and then use it to encrypt the session. A quantum attacker with a recorded transcript leaves the AES alone and runs Shor’s algorithm against the handshake. Solving the recorded elliptic-curve relation gives the attacker the session key, and with it the plaintext, without any attack on the cipher. How long that takes depends on the machine and its architecture, and nobody can give an honest number yet. Because the traffic is already recorded, the attack does not need to finish in hours. Grover cannot touch your AES key, but the attacker recovers it from the key exchange that delivered it. The same applies to a file encrypted under AES-256 whose data key is wrapped with RSA-2048: an attacker who breaks the RSA wrapping with Shor’s algorithm gets the data key. Sessions that use hybrid post-quantum key establishment are not exposed this way, so you have to record in your inventory which key-exchange mode each TLS connection uses.
The migration is therefore about key establishment and signatures. If your team catalogues cipher suites without cataloguing key exchange and certificate chains, it has inventoried the wrong thing. Harvest now, decrypt later attacks work against traffic encrypted with ciphers no quantum computer will ever break, because the adversary records the handshake along with the ciphertext and breaks it later.
The Grover exposure that does belong in your risk register is narrower and duller: legacy 64-bit and 80-bit symmetric keys and short MAC tags in embedded, industrial, and telecom estates. Those keyspaces were already marginal against classical attackers, and Grover’s algorithm reduces an 80-bit key to a notional 40 bits of quantum security. Those keys need a remediation plan. AES-256 does not.
What to remember
Grover’s algorithm attacks the problems Shor’s algorithm cannot. It moves amplitude toward the answer over about $$\sqrt{N}$$ sequential iterations, for a quadratic speedup that is proved optimal. The iterations must run in strict sequence on one coherent machine, because nobody can save or copy the intermediate states. Spreading the search across $$M$$ machines speeds it up by only $$\sqrt{M}$$. With realistic hardware assumptions, the notional attack on AES-128 needs billions of years of uninterrupted error-corrected computation. NIST caps serial attack depth with MAXDEPTH in its standardization criteria. The NSA asks for nothing larger than AES-256. Hashes hold on the same arithmetic, and the quantum collision advantage disappears once you count the quantum memory it needs. An attacker after your AES-256 traffic will use Shor’s algorithm against the key exchange that delivered the key.
Next, in Part 10, “The Machine Itself”: so far in this series I have assumed a machine that does not exist, and now we build it. Decoherence as the environment measuring your qubits uninvited, error correction that checks integrity without ever reading the data, and why a raw physical-qubit count tells you almost nothing about a machine’s cryptanalytic capability.
