The Most Expensive Way to Factor Fifteen

In December 2001 a team at IBM and Stanford published, in Nature, the result of a computation that had consumed years of preparatory work and one of the most exotic machines in any laboratory: the prime factors of fifteen. The answer, three times five, was confirmed. The machine was a custom-synthesized molecule whose seven atomic nuclei served as qubits, manipulated by nuclear magnetic resonance, and it was the first physical execution of Peter Shor's factoring algorithm, the procedure that had given quantum computing its reputation for menace seven years earlier. Nobody involved pretended otherwise: the number was chosen because it was the smallest composite that shows the algorithm working, and the demonstration was a proof of principle. A schoolchild checks the arithmetic in seconds. The apparatus could factor nothing else. As a piece of engineering honesty, it remains one of the field's better moments, because the authors said exactly what had been done and no more.

The original dream was a quieter one. When Richard Feynman proposed the quantum computer in 1981, his argument was that nature is not classical, so a machine built to simulate nature should not be classical either. He wanted an instrument for physics: a device that could model molecules and materials by running on the same rules they do. Shor's 1994 algorithm added a second dream with a different temperature. A sufficiently large quantum computer could factor the enormous numbers behind RSA encryption, which meant it could read most of the world's secure traffic. Quantum computing has lived between these two dreams ever since, and the gap between them is the whole practical story. Feynman's instrument needs hundreds of well-behaved qubits. Shor's codebreaker needs something closer to millions. Thirty years in, the honest ledger of the field reads as follows.

The record for the largest general semiprime factored by Shor’s algorithm on a quantum device is still twenty-one, set in 2012 by a team at the University of Bristol using recycled photons, and even that leaned on compiled shortcuts that smuggled prior knowledge of the answer into the circuit. In October 2026 a hardware baseline on IBM processors ran the order-finding arithmetic explicitly for numbers as large as 771, a genuine milestone that chose its targets for their convenient structure rather than their difficulty. Before that, fifteen had been demonstrated four separate times in a decade. In 2019 Google announced quantum supremacy: its 53-qubit Sycamore processor had sampled the output of a random quantum circuit in about two hundred seconds, and its paper estimated that a state-of-the-art supercomputer would need roughly ten thousand years to do the same. IBM answered within days. Using disk storage Google had left out of its accounting, a classical machine could do it in two and a half days, at higher fidelity. The task, it is worth adding, produces nothing anyone wants. Random circuit sampling is a steeplechase built specifically to be hard for classical hardware, which is precisely what makes it a useful benchmark and precisely what makes it useless as work. The supremacy claim was technically interesting and rhetorically catastrophic, because it taught the press a word the field has spent six years trying to live down.

The more respectable progress has come without fanfare. In December 2024 Google published Willow, a 105-qubit processor that crossed the line the field calls below threshold. Quantum error correction bundles many physical qubits into one logical qubit, on the theory that a big enough bundle suppresses errors faster than the extra hardware adds them. For thirty years, making the bundle bigger had always made things worse. Willow reversed that: moving from a 3x3 to a 5x5 to a 7x7 lattice, the encoded error rate halved at each step, with real-time correction and logical qubits that outlive their own components. It is the first convincing evidence that the central trick of the field actually works. In June 2025 IBM committed to the next step in public: a machine called Starling, due in 2029 in Poughkeepsie, planned at two hundred logical qubits running one hundred million operations. Note the unit of account. After three decades the industry announces its ambitions in logical qubits, and it announces them in the hundreds. For scale, the best current estimate for breaking RSA-2048 has fallen twentyfold in six years: the 2019 blueprint from Gidney and Ekera called for twenty million noisy physical qubits running for eight hours, and Gidney’s 2025 revision of his own estimate brings it below one million noisy qubits and less than a week of runtime.

What, then, has quantum computing done for anyone? Essentially one thing so far, and it is genuinely large. (A second entry belongs in the margin: in 2025 a trapped-ion processor produced certified randomness, random numbers that carry a proof of their quantum origin, a genuine if narrow service.) Because a future machine could read today's intercepted traffic, the world's standards bodies have had to act on Shor's algorithm before Shor's machine exists. On August 13, 2024, NIST published the first three finalized post-quantum encryption standards, classical algorithms designed to resist a quantum attack, and told system administrators to begin migrating immediately. Intelligence agencies call the underlying threat harvest now, decrypt later: adversaries record ciphertext today to read it the year the hardware arrives. The largest concrete effect of the quantum computer on ordinary life to date is that the classical internet is being re-encrypted against it. The most consequential quantum computer yet built is a set of documents published in Gaithersburg.

None of this is an argument that the machines will not arrive. Willow's result is real, IBM's roadmap is sober, and Feynman's instrument is coming into being the way instruments do, slowly and then suddenly. The failure worth naming is not in the hardware. It is in the adverbs. Quantum computing has been almost ready for thirty years, and the people who kept saying so were not lying exactly; they were just always describing a machine one order of magnitude away, and the order kept moving. The record of the field is a long demonstration that protecting fragile quantum information is among the hardest engineering problems humans have taken up, measured against press releases that describe it as a product launch. Feynman asked for a tool to understand nature. Shor showed the tool could pick a lock. The tool is coming. The lock is already being changed.

Sources:

• L. Vandersypen et al., "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance", Nature 414, 883-887 (2001). (https://www.nature.com/articles/414883a)

• R. Feynman, "Simulating Physics with Computers", International Journal of Theoretical Physics 21 (1982), for the original proposal.

• P. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", FOCS 1994.

• E. Martin-Lopez et al., "Experimental realization of Shor's quantum factoring algorithm using qubit recycling", Nature Photonics (2012), and New Scientist's report that 21 remains the Shor record. (https://www.newscientist.com/article/1976382-recycled-photons-set-fresh-quantum-computing-record/)

• Google, "Quantum Supremacy Using a Programmable Superconducting Processor" (October 2019). (https://research.google/blog/quantum-supremacy-using-a-programmable-superconducting-processor/)

• IBM, "On 'Quantum Supremacy'" (October 2019), for the 2.5-day classical rebuttal. (https://www.ibm.com/quantum/blog/on-quantum-supremacy)

• Google Quantum AI, "Meet Willow" and the Willow spec sheet (December 9, 2024), for 105 qubits and below-threshold error correction; companion Nature paper s41586-024-08449-y. (https://blog.google/innovation-and-ai/technology/research/google-willow-quantum-chip/) (https://quantumai.google/site-assets/downloads/willow-spec-sheet.pdf)

• IBM Newsroom, "IBM Sets the Course to Build World's First Large-Scale, Fault-Tolerant Quantum Computer" (June 10, 2025), for Starling: 200 logical qubits, 100 million operations, by 2029. (https://newsroom.ibm.com/2025-06-10-IBM-Sets-the-Course-to-Build-Worlds-First-Large-Scale,-Fault-Tolerant-Quantum-Computer-at-New-IBM-Quantum-Data-Center)

• C. Gidney and M. Ekera, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", Quantum 3, 433 (2021). (https://quantum-journal.org/papers/q-2021-04-15-433/)

• NIST, "NIST Releases First 3 Finalized Post-Quantum Encryption Standards" (August 13, 2024). (https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-

finalized-post-quantum-encryption-standards)

• C. Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits” (2025). (https://arxiv.org/abs/2505.15917)

• F. Gomes dos Santos et al., “Factoring some integers using Shor’s algorithm on real quantum hardware”, Scientific Reports (October 2026). (https://www.nature.com/articles/s41598-026-69823-6)

• M. Liu et al., “Certified randomness using a trapped-ion quantum processor”, Nature (March 2025). (https://www.nature.com/articles/s41586-025-08737-1)