Symptom
Your TLS termination uses ECDHE for key agreement, RSA-2048 in the certificate chain, and AES-256 for the session. A compliance document arrives with a migration deadline for “post-quantum readiness” and a list of algorithms to replace.
You read the list and it is asymmetric. Every public-key primitive is on it. Not one symmetric primitive is. AES-256 and SHA-256 are untouched; AES-128 gets a note recommending 256.
That asymmetry is not a policy preference. It is the difference between two numbers — an exponential speedup and a square-root one — and those two numbers are the entire practical content of quantum computing for a working engineer.
Statement
Shor (1994). There is a quantum algorithm factoring an $n$-bit integer in $O(n^2 \log n \log\log n)$ gates, polynomial in $n$. The same machinery solves discrete logarithm in $\mathbb{Z}_p^*$ and on elliptic curves. The best known classical factoring algorithm, the general number field sieve, runs in $\exp(O(n^{1/3}\log^{2/3} n))$ — sub-exponential but super-polynomial.
Grover (1996). Given a black-box predicate $f$ on $N$ items with exactly one satisfying input, a quantum algorithm finds it with $\Theta(\sqrt{N})$ queries.
BBBV optimality (Bennett, Bernstein, Brassard, Vazirani 1997). $\Omega(\sqrt{N})$ queries are necessary. Grover is optimal for unstructured search, so the square root is the end of the road, not the current best.
Consequences, in one table:
| Primitive | Classical security | Quantum security | Verdict |
|---|---|---|---|
| RSA-2048 | ~112 bits | broken | replace |
| ECC P-256 | ~128 bits | broken | replace |
| AES-128 | 128 bits | ~64 bits (Grover) | upgrade |
| AES-256 | 256 bits | ~128 bits | fine |
| SHA-256 | 128-bit collision | ~128 bits | fine |
Symmetric crypto survives by doubling key length. Asymmetric crypto does not survive at all, because you cannot double your way out of a polynomial-time attack.
Argument
Both algorithms are long; here is the load-bearing sketch, with FIPS 203 carrying the engineering consequences.
Proof sketch.
(Shor.) Factoring $N$ reduces to order finding: pick random $a$ coprime to $N$, find the least $r$ with $a^r \equiv 1 \pmod N$. If $r$ is even and $a^{r/2} \not\equiv -1$, then $\gcd(a^{r/2} \pm 1, N)$ is a nontrivial factor, and a random $a$ works with probability $\ge 1/2$. The quantum part finds $r$. Prepare a uniform superposition over exponents $x$, compute $a^x \bmod N$ into a second register, and measure it. The first register collapses to a superposition supported on an arithmetic progression of period $r$. Apply the quantum Fourier transform: a periodic function’s transform concentrates on multiples of $1/r$, so measurement yields $c/r$ for random $c$, and continued fractions recover $r$. The QFT on $2^n$ amplitudes costs $O(n^2)$ gates while the classical FFT costs $O(n2^n)$ — that exponential gap is the whole speedup, and it works because the answer is a global property of the function.
(Grover.) Start in the uniform superposition, amplitude $1/\sqrt{N}$ each. Repeat: the oracle flips the sign of the marked item’s amplitude; then reflect all amplitudes about their mean. Geometrically this is a rotation by $\theta \approx 2/\sqrt{N}$ per iteration in the two-dimensional plane spanned by the marked state and the uniform superposition of the rest. Reaching the marked state needs $\theta k \approx \pi/2$, so $k \approx (\pi/4)\sqrt{N}$. Iterating past that rotates back out, which is why the count must be right.
(BBBV.) A hybrid argument: each query can change the final state by only $O(1/\sqrt{N})$ in the worst case, so $o(\sqrt{N})$ queries cannot distinguish the $N$ possible marked items.
Why the gap between the two is structural, not incidental. Shor exploits periodicity — hidden structure in the group underlying RSA and ECC. Grover exploits nothing, because there is nothing: an unstructured predicate offers no handle, and amplitude amplification is a generic $\sqrt{}$ that any search gets for free. Cryptosystems built on structured hard problems are vulnerable because the structure is what the quantum computer sees. AES is designed to have no exploitable structure, so it presents Grover with the worst case and Grover delivers only its generic square root.
Grover on AES-128 in practice, with numbers. The naive reading is $2^{64}$ operations, alarmingly feasible. But each Grover iteration must evaluate AES coherently — a reversible circuit of roughly $2^{16}$ gates — and the iterations are inherently sequential, since each depends on the last. At a generous $10^9$ quantum gate operations per second, $2^{64} \times 2^{16}$ gates takes about $2^{80}/10^9$ seconds, roughly $4\times10^{13}$ years. And Grover parallelises badly: $m$ machines give only a $\sqrt{m}$ speedup, so a thousand machines buy a factor of 32. NIST’s own analysis concludes AES-128 remains practically secure against Grover; the recommendation to move to AES-256 is prudence, not urgency.
Shor in practice, contrasted. RSA-2048 needs roughly 4,000 logical qubits. Error correction inflates that to millions of physical qubits at current error rates; the best recent estimate (Gidney 2025) is under a million noisy qubits for under a week of runtime, down from 20 million in the 2019 estimate. Current hardware is at hundreds to low thousands of physical qubits with error rates still short of what is needed. The trend in the estimates is the thing to watch, and it has moved a factor of 20 in six years, in the wrong direction for defenders.
Harvest now, decrypt later, which is why the deadline is today. An adversary recording encrypted traffic now can decrypt it whenever a machine exists. Any secret whose confidentiality must outlive the arrival of quantum computers is already exposed. This is the entire argument for migrating before the hardware exists, and it is correct.
What replaces them. NIST standardised three in 2024: ML-KEM (FIPS 203, Kyber, lattice-based key encapsulation), ML-DSA (FIPS 204, Dilithium signatures), and SLH-DSA (FIPS 205, SPHINCS+, hash-based signatures whose security rests only on the hash function). These rest on problems — module lattices, hash preimages — with no known quantum algorithm doing better than Grover. Deployment is already underway: hybrid X25519+ML-KEM key agreement is live in Chrome and in OpenSSH since 9.0.
Forbids
RSA, Diffie–Hellman, DSA, and ECC surviving a cryptographically relevant quantum computer. All reduce to period finding in an abelian group. This is not a weakness to patch; the mathematical foundation is the target.
Escaping Shor by increasing key size. Polynomial time in $n$ means doubling the key roughly quadruples the work. RSA-4096 buys a small constant factor.
A better-than-$\sqrt{N}$ quantum algorithm for unstructured search. BBBV proves the lower bound. Any claimed improvement is using structure the black-box model excludes.
Ignoring the migration because the hardware does not exist. Recorded traffic is decrypted later. For long-lived secrets the exposure has already happened.
Does not forbid
It does not mean quantum computers break all cryptography, which is the misreading that produces both panic and paralysis. Symmetric encryption, hash functions, and MACs are essentially fine. The break is confined to public-key primitives based on factoring and discrete log — a large and critical class, and not everything.
It does not mean exponential speedups are general. Quantum computers are not faster computers. The known exponential speedups all exploit specific algebraic structure via the hidden subgroup problem. For most problems, including NP-complete ones, the best known quantum improvement is Grover’s square root, and it is widely believed BQP does not contain NP.
It does not mean AES-128 is broken today. See the runtime above. The recommendation to move to 256 is cheap insurance against future algorithmic improvement, not a response to a live attack.
It does not mean post-quantum algorithms are proven secure. They are secure against known quantum algorithms. Rainbow and SIKE were both NIST candidates and both were broken — SIKE by a classical attack in 2022, on a laptop, in about an hour. The new foundations are younger and less tested than the ones being replaced, which is the strongest argument for hybrid deployment.
It does not require a working quantum computer for the migration to be rational. The decision rests on secret lifetime plus migration time versus time to a capable machine — Mosca’s inequality — and for many organisations that sum already exceeds any plausible estimate.
Boundary
- Gate counts assume error-corrected logical qubits. Every resource estimate depends on assumed physical error rates and code overhead, and these estimates have moved by more than an order of magnitude within a decade.
- Grover’s oracle must be a reversible circuit for the function, and building it is not free. Query complexity is not gate complexity, and the difference is where the practical infeasibility lives.
- The hidden subgroup framing covers abelian groups. The non-abelian case, which would cover graph isomorphism and some lattice problems, remains open, and this is precisely why lattice-based schemes are the leading candidates.
- No proof that factoring is classically hard exists. A classical polynomial-time factoring algorithm would break RSA without any quantum computer, and nothing rules it out.
- Timelines are unreliable in both directions. Predictions have been wrong optimistically for thirty years, and the resource estimates have fallen sharply. Treat any specific year as unsupported.
The framing to keep: quantum computing is not a general speedup, it is a specific attack on specific mathematical structure. Knowing which of your primitives are built on that structure tells you exactly what to migrate, and the answer is smaller than the headlines and larger than zero.