Skip to content

Peter Shor

Abstract

Peter Shor (born 1959) wrote two papers in the mid-1990s that turned quantum computing from a philosophical curiosity into a funded engineering programme and a cryptographic emergency. The first, in 1994, showed that a quantum computer could factor large integers in polynomial time, which would break RSA and the rest of public-key cryptography if such a machine were ever built. The second, in 1995, showed that quantum information could be error-corrected at all, which most physicists had assumed impossible. He was a combinatorial optimisation researcher at Bell Labs at the time, working on bin packing and network design; he had been paying attention to quantum computing for about a year.

Bin Packing

Shor was born in New York City on August 14, 1959, and grew up in Washington, D.C. and California. He took his bachelor’s degree in mathematics at Caltech in 1981 and a Ph.D. in applied mathematics at MIT in 1985 under F. Thomson Leighton, with a thesis on the probabilistic analysis of bin-packing algorithms: given items of random sizes, how much space does a good packing waste?

After a postdoctoral year at Berkeley’s Mathematical Sciences Research Institute he joined AT&T Bell Labs in New Providence, New Jersey, and stayed until 2003. His work there was combinatorics, probability, and algorithms, the ordinary business of a strong theory group at Bell Labs. Quantum computation was not his field.

The Path to Factoring

Richard Feynman had proposed in 1981 that quantum systems might be simulated efficiently only by other quantum systems, and David Deutsch had formalised a quantum Turing machine in 1985, but by the early 1990s the field had no problem of practical interest that a quantum computer could solve faster than a classical one. It looked like an elegant dead end.

Two things changed that for Shor. Umesh Vazirani visited Bell Labs to speak on the quantum complexity work he had done with Ethan Bernstein. Then Shor read Dan Simon’s paper describing a problem, now called Simon’s problem, that a quantum computer solves exponentially faster than any classical one.

Simon’s problem is artificial: it exists to demonstrate a separation. What Shor saw in it was the mechanism. The quantum advantage came from finding a hidden period using interference, and periodicity is exactly what connects to two problems everyone cared about. Discrete logarithm is a period-finding problem. And factoring reduces to finding the period of a modular exponential.

He worked out the discrete-log case first, then factoring, and presented Algorithms for Quantum Computation: Discrete Logarithms and Factoring at the 35th Symposium on Foundations of Computer Science in 1994. The expanded version ran in SIAM Journal on Computing in October 1997.

The result: an ideal quantum computer factors an n-bit integer in time polynomial in n, against the sub-exponential general number field sieve, the best classical method known. Every widely deployed public-key system, RSA, Diffie-Hellman, and elliptic-curve cryptography, rests on one of the two problems Shor had just broken in principle. The consequences for cryptography, including the “harvest now, decrypt later” problem and the NIST post-quantum standards published in 2024, are covered in Quantum Computing and Cryptography: The Secret Science.

What the algorithm does not do

Shor’s algorithm is not a general speedup. It attacks problems with hidden periodic structure; it does nothing for NP-complete problems, and there is no evidence quantum computers solve those efficiently. Its power is narrow and, for the particular narrow target it hits, total.

Error Correction

The obvious objection to Shor’s result was that a quantum computer could not be built. Qubits decohere: any stray interaction with the environment destroys the superposition, and the computation with it. Classical computers handle noise by copying bits and voting, but the no-cloning theorem forbids copying an unknown quantum state. Several physicists argued that this made fault-tolerant quantum computation impossible in principle, so the factoring result was a theorem about a machine that could not exist.

In 1995 Shor answered it. His nine-qubit code encodes one logical qubit across nine physical ones and corrects an arbitrary single-qubit error, by nesting a three-qubit repetition code against bit flips inside a three-qubit code against phase flips. The trick is that the error can be detected and reversed by measuring parities without ever measuring, and thus collapsing, the encoded state.

Andrew Steane published a seven-qubit code independently in 1996, and Robert Calderbank, Shor, and Steane generalised both into the CSS codes that fault-tolerant architectures still use. Together with the threshold theorem that followed, this converted quantum computing from a question of physics into a question of engineering budget: build the qubits good enough, and enough of them, and the errors can be beaten.

MIT

Shor left Bell Labs for MIT in 2003 and is Henry Adams Morss and Henry Adams Morss, Jr. Professor of Applied Mathematics there. He has continued to work on quantum information theory, channel capacities, and the additivity conjecture (which he showed connected several open problems in quantum information, and which was later disproved by Matthew Hastings).

He was awarded the Nevanlinna Prize in 1998, the Gödel Prize in 1999, a MacArthur Fellowship in 1999, the Breakthrough Prize in Fundamental Physics in 2023, and the Claude E. Shannon Award in 2025.

The Gap

Thirty years after the algorithm, no quantum computer has factored a number large enough to matter. The published demonstrations, up to the factoring of 21 with photonic qubits in 2012, used prior knowledge of the answer to simplify the circuits, so they do not run the algorithm as specified. Estimates for breaking RSA-2048 have fallen as the compilation improved, from Gidney and Ekerå’s 20 million noisy qubits in 2019 to under a million in Gidney’s 2025 revision, and both numbers assume error rates and qubit counts far beyond current hardware, whose largest gate-based machines run on the order of a thousand noisy qubits.

The algorithm changed the world anyway. It is the reason quantum computing receives national-laboratory budgets, the reason NIST spent eight years standardising lattice-based replacements for RSA, and the reason organisations with long-lived secrets are already migrating. A theorem about a machine nobody has built has forced the replacement of the cryptography the internet runs on.

📚 Sources