Mental model
The effect of quantum computers on cryptography cannot be summed up in one sentence, because two different algorithms hit two different families of cryptography with very different force. Keeping this distinction clear is the basis of every explanation you will give in the rest of this course.
Shor’s algorithm (1994) solves factoring and discrete logarithms at a speed classical computers cannot reach. It runs in “polynomial time”: as the problem grows, the solving time does not explode the way it does for classical methods but rises far more gently, so it stays practical even for large RSA keys. The core of the mechanism is turning factoring into a period finding problem: instead of finding a number’s factors, it finds how often a certain function repeats (its period), and quantum computers can detect that period, thanks to the quantum Fourier transform, at a speed classical computers cannot match. These two problems (factoring and discrete logarithms) are the security foundation of RSA and ECC (and therefore ECDSA and ECDH) respectively. Once a large enough, stable quantum computer runs, Shor breaks these algorithms completely: not “weakens them a little”, but makes the private key directly computable. That is the single reason asymmetric cryptography has to move to PQC.
Grover’s algorithm (1996) does a different job: it gives a quadratic speedup over an unstructured search space (for example finding a symmetric key by brute force). Instead of scanning AES-128’s classical brute-force search space of 2^128DERIVED possibilities, Grover reduces the effective search space to 2^64DERIVED (idealized, ignoring parallelization; this is the equivalent of taking a square root, because that is exactly the quadratic speedup Grover gives). This does not “break” AES-128; it lowers the security margin. NIST’s first official assessment in 2016 (source 1) responded cautiously by recommending doubling symmetric key lengths.
Why “double the key” is overstated
Grover’s quadratic speedup is an idealized calculation that holds for a single quantum circuit. A real attacker would want many quantum circuits running in parallel to speed things up; but unlike classical parallelization (N times the hardware = N times faster), parallelization in Grover is not that generous. As Filippo Valsorda shows (source 2), once realistic parallelization costs are counted the effective attack cost rises to ~2^72SOURCED, clearly higher than the idealized 2^64. That is why NIST’s own current PQC security categories (Category 1, 3 and 5, which you will see when comparing ML-KEM and ML-DSA parameters) still treat AES-128 as a meaningful security level (Category 1) and do not require automatic doubling of key length.
This does not mean “the quantum threat should be taken lightly”: the Shor side is a real and certain break. But presenting the Grover side with the same urgency as Shor is both wrong and damaging to credibility. A bank architect knows this distinction and will not trust a consultant who acts as if they do not.
What “noisy qubit” means
When you read resource estimates you will keep seeing “noisy qubit”; without knowing what it means, the numbers are meaningless. Today’s quantum computers have unstable physical qubits: environmental vibration, temperature and electromagnetic noise make errors accumulate during computation. The qubit count Shor’s algorithm needs to break a real RSA key is not the bare (“physical”) qubit count but the count of logical qubits, reliable computing units protected against errors; and producing one logical qubit takes many physical (noisy) qubits tied together with error-correcting codes. The “fewer than a million qubits” figure below refers to this noisy, physical qubit count: a realistic estimate that includes error correction, not a purely theoretical “how many logical qubits” calculation. The distinction matters because the gap between the two can easily be several orders of magnitude.
Resource estimates: how big a quantum computer is needed
How large and how error-free a quantum computer must be for Shor’s algorithm to work in practice is an active research question, and the estimates change quickly. In 2025, Craig Gidney of Google Quantum AI published work showing that RSA-2048 could be factored with 1000000SOURCED noisy qubits in under a week (source 3). That is 20×DERIVED smaller than the earlier estimate the same author published with Martin Ekerå in 2019 (20000000SOURCED, source 4).
The drop does not come from hardware growing but from the algorithm itself becoming more efficient (three techniques: approximate residue arithmetic, “yoked” surface codes and “magic state cultivation”). That is an important distinction: “quantum computers are growing fast” and “quantum algorithms are getting more efficient fast” are different claims, and the second explains the real movement in this estimate. The next estimate may be lower still, so when you memorize this figure keep the frame “today’s best estimate, not a permanent fact”.
Commercial stake note: Google Quantum AI builds quantum computing hardware. Interestingly, a lower qubit estimate may help its own hardware roadmap look more reachable. That does not make the estimate wrong (the math is the math and can be checked independently), but it is important to read the source knowing its institutional position.
What we learned
When explaining the quantum threat, describe the two algorithms separately, with their two different levels of severity: Shor breaks asymmetric cryptography completely (the real source of urgency), Grover weakens symmetric cryptography moderately (no key doubling needed). Resource estimates (today fewer than a million qubits, under a week) are live figures that change quickly and should be re-checked periodically with the dogrula command, not constants to memorize once.