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?
The textbook answer takes one line. 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. Double your keys and sleep soundly.
Now read what the NSA actually mandates. CNSA 2.0, the requirement set for US national security systems, holds every other primitive to the highest parameters on the menu: ML-KEM-1024, ML-DSA-87, SHA-384 or better. For symmetric encryption it asks for AES-256 and nothing more. No larger variant is demanded, no asterisk, no urgency. Notice that this is entirely consistent: even on the textbook accounting, AES-256 leaves a notional $$2^{128}$$ of work, which is a fine place to stand. What is missing is any sign that the agency treats the halving as a live operational problem, and the reason is that the halving figure was never an attack estimate in the first place.
It is a query count. This part is about the difference: what Grover does, why its speedup provably stops where it does, why almost no attacker can collect even that, and what your symmetric keys should actually be.
What Grover actually does
Grover’s algorithm, published by Lov Grover in 1996, answers the question Shor cannot touch: 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: the function reversibly tests a candidate key $$k$$ against known plaintext-ciphertext pairs, enough of them to pin down one key (a single 128-bit block leaves far too many AES-256 keys consistent with it), and the haystack is every key in the space.
Classically, you have no traction. The right key relates to the wrong keys by nothing except being right, so you try candidates until one works, averaging $$N/2$$ attempts. Part 7 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. What it lacks, by fifty years of deliberate design, is structure an attacker can exploit to beat generic search, and that absence is the whole reason Grover is the best anyone has against it.
What Grover does instead is patient. The four moves are there, and the third one runs in a loop. Prepare the uniform superposition over all $$N$$ keys, each carrying 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 one sits below the average, so reflection kicks it up; the rest sit slightly above, so reflection nudges them down. Repeat. Each pass, a little more amplitude migrates to the answer and a little more drains from everything else. Do this about $$\sqrt{N}$$ times and the answer’s amplitude is close to one. Measure, and you get the key.
Nothing was tried at once. Amplitude was pumped, one careful rotation per iteration, until the Born rule had no choice.
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)$$. One iteration, and the wrong keys have cancelled to nothing while the right key carries all the amplitude. Measure and the answer is certain.
Why $$\sqrt{N}$$ in general: each iteration rotates the state by a small fixed angle of roughly $$2/\sqrt{N}$$, and you need to travel a quarter turn to swing the state onto the answer. Divide $$\pi/2$$ by $$2/\sqrt{N}$$ and you get about $$0.79\sqrt{N}$$ iterations. For a 128-bit key, $$\sqrt{N} = 2^{64}$$. Hold that number.
Quadratic is the ceiling, and that is a theorem
Before the good news, the bad. Nobody is going to find a better generic search algorithm, because the quadratic limit is proved rather than assumed. In 1997, Bennett, Bernstein, Brassard, and Vazirani showed that no quantum algorithm can search an unstructured space in fewer than about $$\sqrt{N}$$ queries, and Christof Zalka tightened it in 1999 to show Grover already hits the bound exactly. This is the anti-denialism half of the ledger: the quadratic speedup is real, it is optimal, and it is not going away.
It is also the ceiling. A quantum computer cannot search a structureless space faster than the square root of its size, which means that against symmetric cryptography, the machine that eviscerates RSA is reduced to a modestly better key-guessing engine. Everything hangs on the word “modestly,” and on a detail the textbook line drops.
Two to the sixty-four, one after another
That $$2^{64}$$ is not a count of operations you can spread across a data center. It is a count of iterations that must run in strict sequence, on one coherent machine, without interruption.
The reason traces to Part 3. Each iteration transforms the amplitudes produced by the previous one, and you cannot checkpoint the intermediate state, because reading it destroys it and copying it is forbidden. There is no save file, no map-reduce, no “throw a thousand machines at it.” Split the keyspace across $$M$$ quantum computers and each searches a smaller haystack, which sounds like a win until you do the arithmetic: each machine still needs $$\sqrt{N/M}$$ iterations, so the speedup scales as $$\sqrt{M}$$ rather than $$M$$, while the aggregate oracle work goes up. A thousand machines buy you a factor of thirty-two in wall-clock time. A million buy you a thousand. Parallelism, the resource that makes classical brute force frightening, is precisely the resource quantum search cannot use efficiently.
So the attack is a single quantum computer, error-corrected, running $$2^{64}$$ iterations back to back, each iteration executing a full AES circuit in superposition. Every one of those logical operations is built from a mountain of error-corrected physical ones (Part 10‘s subject), and the machine must hold coherence through all of them. Put plausible numbers on the clock, as the box below does, and the wall time for AES-128 comes out in the billions of years.
This is not my private skepticism. It is the reason NIST introduced a parameter called MAXDEPTH into the post-quantum standardization criteria: a cap on how long a serial quantum computation any real attacker could plausibly run. Impose that cap and the attacker must parallelize, and parallelizing surrenders the quadratic advantage. NIST’s own security categories bake this in, and the agency 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, and Jaques, Naehrig, Roetteler, and Virdia later costed depth-limited attacks properly, finding that the required parallelization drives the gate cost up rather than down.
To put it bluntly: the halving figure counts ideal oracle queries, not the cost of an attack anyone knows how to mount, and repeating it as though the two were the same is how a conservative number turns into a frightening one. Cryptographer Filippo Valsorda made the same argument this year, and reached the same place: 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 runs at least one AES-128 encryption as a reversible quantum circuit; published circuits are thousands of logical layers deep, so call it $$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.
Now the clock. Take Part 8’s hardware assumptions, 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, roughly six billion years of uninterrupted, coherent, error-corrected computation. The universe is 13.8 billion years old. Grant a logical clock a thousand times faster and you still need six million years. Try to escape with parallelism and the $$\sqrt{M}$$ penalty demands on the order of $$10^{19}$$ separate fault-tolerant machines to finish inside a year. Change the oracle depth or the clock and the figure moves, so do not quote six billion years as the answer. The durable lesson is the shape of the problem: the iterations are serial, each one is a full cipher circuit, and buying more machines barely helps.
AES-256 needs $$2^{128}$$ iterations. There is no point continuing the arithmetic.
(These are order-of-magnitude figures meant to be checkable, not a published resource estimate. The careful circuit-level analyses cited above reach the same verdict by more rigorous routes.)
WHERE THIS BREAKS: Two burglars, two methods.
This series has used a lock analogy since Part 1; both halves now have their mechanisms. Shor is the burglar who studied the lock’s blueprint and machines a key from the design; no amount of adding pins helps, because the exposure is in the mechanism. Grover is the burglar who tries keys faster than you thought possible, which you answer the way locksmiths always have, by adding pins until trying is hopeless.
Where the analogy stops: Grover’s “faster” is a square root, and square roots have the inconvenient property of being cheap to outrun. Every bit you add to the key doubles the classical attacker’s work and adds a full bit back against the quantum one; a 256-bit key restores what a 128-bit key would notionally lose. Defense wins that arms race permanently, on paper, before the sequential-depth argument above even enters the room. Which is why the honest question was never whether Grover threatens AES. It was whether anyone can run Grover at all.
Why AES-256 is the conservative answer
Return to the opening. CNSA 2.0 demands maximum parameters for the primitives it considers exposed and leaves AES-256 alone, which tells you the agency protecting material for fifty years is not treating symmetric encryption as a fire. I cannot read 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, which prices depth-limited attacks and makes the same point in the open: the query count is not the attack.
So here is the recommendation, and it is the same one you would get from CNSA 2.0, arrived at by a route that lets you defend it in a meeting. Use AES-256. Not because AES-128 is on the verge of falling, since the arithmetic above says it plainly is not, but because the margin costs you almost nothing, the guidance is unambiguous, and cryptographic history punishes people who cut margins to the theoretical minimum. Where AES-128 already protects short-lived data with a mature key hierarchy, treat the upgrade as hygiene rather than emergency. Reserve your emergency budget for the public-key migration, which is the actual fire.
Then take the sentence you now own into your next steering committee. AES comes through intact.
What Grover does to hashes
The same logic, one step sideways. Finding a preimage of a hash is unstructured search, so Grover applies: SHA-256 preimage resistance drops from $$2^{256}$$ to a notional $$2^{128}$$, with all the sequential-depth caveats above still attached. Comfortable.
Collision resistance is the subtler case, and it is where a piece of quantum folklore deserves puncturing. Yes, an algorithm published by Brassard, Høyer, and Tapp finds collisions in roughly the cube root of the search space, which sounds alarming until you notice it demands 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, an object no more buildable than a quantum computer the size of Belgium. Meanwhile classical collision search, parallelized across ordinary hardware in the way van Oorschot and Wiener worked out in the 1990s, remains the practical attack. The quantum “speedup” on collisions is an artifact of counting queries and ignoring memory. SHA-256 holds. SHA-384 gives margin, which is why CNSA 2.0 asks for it.
MYTH AUTOPSY: “Quantum computers will break all encryption.”
The headline that launched a thousand vendor decks dies on the casualty list, which you can now derive rather than memorize. Public-key cryptography built on factoring or discrete logs falls, completely, because periodic structure is exactly what interference can concentrate. Symmetric ciphers and hash functions hold, because no known structure in them yields a Shor-style shortcut, which leaves Grover pumping amplitude one sequential iteration at a time against a haystack that grows exponentially with every key bit you add. The threat is precise, and precision is the opposite of what “all encryption” implies.
The claim also fails a simpler test: the fix is already standardized. NIST’s post-quantum standards replace the broken public-key algorithms with new classical ones that run on the hardware you own today, and AES rides through the transition untouched.
Say instead: quantum computers break the public-key algorithms that rest 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.
Here is the operational lesson to take upstairs, and it reframes the whole question that opened this article. Consider how that AES-256 session key came to exist. In a TLS handshake, it was agreed using elliptic-curve Diffie-Hellman, then used to encrypt the session. A quantum attacker with a recorded transcript does not attack the AES. They attack the handshake with Shor, solve the recorded elliptic-curve relation, derive the session key, and read the plaintext without ever touching the cipher. How long that takes depends on the machine and the architecture, and no honest number exists yet. It does not need to be hours. Your symmetric key is unbreakable and irrelevant, because the wrapper it arrived in is made of glass. The same holds for the file encrypted under AES-256 whose data key sits in an envelope sealed with RSA-2048. Hybrid post-quantum key establishment closes this exposure, which is exactly why your inventory has to record the handshake mode rather than assume every TLS session is alike.
That is why the migration is a key-establishment problem and a signature problem, and why an inventory that catalogues cipher suites without cataloguing key-exchange and certificate chains has inventoried the wrong thing. It is also why harvest now, decrypt later works on traffic protected by ciphers no quantum computer will ever break: the adversary is not harvesting your AES, they are harvesting the handshake in front of it.
The residual Grover risk worth a line 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, where a square-root speedup meets a keyspace that was already marginal. Those deserve attention. AES-256 does not.
What to remember
Grover’s algorithm attacks the problems Shor cannot, and it does so by pumping amplitude toward the answer through about $$\sqrt{N}$$ sequential iterations, giving a quadratic speedup that is provably optimal and provably capped. Those iterations must run in strict sequence on one coherent machine, because intermediate states cannot be saved or copied, and parallelism buys only a square root of what it buys classically. Priced honestly, the notional attack on AES-128 needs billions of years of uninterrupted error-corrected computation, which is why NIST wrote MAXDEPTH into its standards and why NSA asks for AES-256 rather than AES-512. Hashes hold on the same reasoning, with the quantum collision advantage gone once you account for quantum memory. And the practical threat to your AES-256 traffic is not Grover at all: it is Shor, breaking the key exchange that delivered the key.
Next, in Part 10, “The Machine Itself”: every threat in this series has 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.
