Shor & Grover's algorithms

For its first decade, quantum computing was a theoretical curiosity: an interesting way to think about physics with no obvious use. Two algorithms changed that, and both are still the reason governments fund the field.

Shor’s algorithm

In 1994 the mathematician Peter Shor showed that a sufficiently large quantum computer could find the prime factors of a huge number efficiently. That sounds academic. It is not, because the difficulty of exactly that problem is what keeps internet encryption standing up.

RSA encryption, which protects a large share of secure connections, banking and stored secrets, relies on the fact that multiplying two large primes is easy while working backwards from the product is effectively impossible. A classical computer needs longer than the age of the universe for a large key. Shor’s algorithm needs hours, given a machine large and stable enough to run it. A related version breaks elliptic curve cryptography, which secures most cryptocurrency wallets.

The speed-up is exponential, which is the strongest kind: as the numbers grow, the gap between classical and quantum effort widens without limit. No amount of extra key length rescues RSA, which is why the answer has been to replace the mathematics entirely with post-quantum cryptography.

Grover’s algorithm

Two years later Lov Grover found a general result: a quantum computer can search an unstructured list of N items in roughly √N steps, where a classical computer needs about N. For a list of a trillion items, that is a million steps instead of a trillion.

The speed-up is quadratic rather than exponential, which makes it far less alarming. Applied to symmetric encryption such as AES, Grover’s algorithm effectively halves the key length, so AES-128 offers roughly the security of a 64-bit key against a quantum attacker. The fix is unglamorous and entirely sufficient: use AES-256. This is why the post-quantum migration focuses almost entirely on public-key cryptography, not on the symmetric ciphers.

Why they still define the field

Neither has been run at a threatening scale. Factoring a 2048-bit RSA key with Shor’s algorithm was long estimated to need many millions of physical qubits once error correction is accounted for; the leading published estimate, from Google’s Craig Gidney in 2025, cut that to under a million noisy qubits running for under a week. Machines today count in the hundreds to low thousands of physical qubits. The gap is still enormous, and closing it is precisely what the hardware programmes are for.

What the two algorithms established is that quantum computers are not merely faster; they compute differently, and for a small set of problems the difference is total. Everything that follows, the Q-Day forecasts, the harvest-now-decrypt-later concern, the NIST standards and the migration deadlines, descends from Shor’s 1994 result.