Breaking encryption needs 20 times fewer qubits

In 2019, Craig Gidney and Martin Ekerå put a number on the attack everyone plans around: factoring a 2048-bit RSA key would take 20 million noisy qubits and eight hours. In May 2025, Gidney published a new estimate. Under a million noisy qubits, and under a week.

Same author. Same assumed machine: a square grid of qubits with nearest-neighbour connections, a uniform gate error rate of 0,1%, a surface code cycle time of one microsecond, a control system reaction time of 10 microseconds.

Nothing was built between the two papers. The requirement fell because the arithmetic and the error correction around it got cheaper.

That is the fact worth carrying into a planning meeting. Most of the coverage led with a different one.

What moved

Gidney's preprint, posted to arXiv on 21 May 2025, combines three results.

The first is approximate residue arithmetic, from Chevignard, Fouque and Schrottenloher in 2024. Their method computes approximate modular exponentiations without ever holding the full 2048-bit value in a quantum register, which destroys the assumption that factoring an n-bit number needs an n-qubit register. It cost them dearly in gates: roughly a thousand times more Toffoli gates for a sixfold saving in space. Gidney cuts that gate count by more than a factor of 100.

The second is yoked surface codes, published in Nature Communications in May 2025, which store idle logical qubits at roughly triple the density of ordinary surface code patches. In the 2048-bit layout, idle qubits cost 430 physical qubits each in cold storage against 1 352 for an active patch at code distance 25.

The third is magic state cultivation, which replaces the first stage of distillation and shrinks the factories that supply the non-Clifford gates. Six of them fit in the compute region, each covering a 3 × 4 area of hot patches against the 15 × 8 factories of the 2019 design.

The trade is time. The new design runs 12,07 hours per shot and expects 9,2 shots, which comes to 4,63 days, or 4,96 days once you divide by the 93,3% chance that a shot finishes without a logical error. Gidney rounds that up to a week for slack. The 2019 design finished in eight hours because it spent qubits to buy time.

The million is physical, and the thousand is logical

This is where most secondary coverage of the paper falls over, and where the number becomes usable or useless depending on which one you write down.

For a 2048-bit key, the algorithm holds 1 280 input logical qubits in dense cold storage and 131 in ordinary hot patches at its peak. Add a compute region of 126 patches and the total is 1 537 logical qubits. Wrapping those in enough surface code to survive a five-day run gives 897 864 physical qubits. Gidney reports the figure as one million, and says why: he wants slack in case cold storage behaves worse than modelled during the first loop of the algorithm.

So the headline is a physical qubit count and the algorithmic requirement is four digits. Any comparison with a vendor announcement has to be made on the same axis, and vendors mix the two constantly. Quantinuum's Helios, launched commercially on 6 November 2025, reports 94 logical qubits with error detection and 48 with error correction, which are two numbers describing one machine with 98 physical qubits.

What has not moved

The machines that ship today are smaller than the estimate by a factor of about nine thousand. Helios has 98 physical qubits. IBM's Nighthawk, announced on 12 November 2025, has 120. Neither is the largest chip anyone has fabricated, and neither is in the same region as 900 000.

The count is also the easier half of the requirement. The estimate assumes a machine holding a 0,1% gate error rate, a one-microsecond code cycle and a 10-microsecond control reaction, continuously, for five days. Nothing in the field runs a workload of that shape today.

Gidney says as much about his own direction of travel. Under the same physical assumptions, he sees no way to cut the qubit count by another order of magnitude, and he declines to claim that a hundred thousand noisy qubits would do it.

Why the estimate matters more than the machine

The useful signal is the derivative. Gidney leans on the cryptographic maxim, which he attributes to Bruce Schneier, that attacks always get better; for quantum factoring, that has held for a decade.

His own position follows, and he states it plainly: he would rather security did not depend on progress staying slow. He does not expect machines of the required size by 2030. He supports retiring vulnerable systems on that schedule anyway.

That argument survives being wrong about the hardware, which is what makes it usable by a planner. A forecast of when a cryptographically relevant quantum computer arrives can be off by a decade in either direction. A rule that says your 2036 secrets should not sit behind an algorithm whose attack cost fell twentyfold in six years does not depend on the forecast at all.

The dates that already exist

Two documents set the schedule that European and American organisations are measured against.

The EU Member States, through the NIS Cooperation Group, published a coordinated implementation roadmap on 23 June 2025, responding to the Commission's recommendation of 11 April 2024. It sets three milestones. By the end of 2026, every Member State should have started: a national transition strategy, a cryptographic inventory, and pilots for high and medium-risk use cases. By the end of 2030, high-risk use cases and critical infrastructure should be migrated. By the end of 2035, as much of the rest as is practically feasible.

The first of those dates is four months away.

In the United States, NIST IR 8547 sets out deprecation of quantum-vulnerable public-key algorithms after 2030 and disallowance after 2035. Worth knowing before you quote it in a board paper: that document was released as an initial public draft in November 2024, its comment period closed on 10 January 2025, and NIST's own migration pages still describe it as a draft. The 2030 and 2035 dates circulate widely as settled policy. They are a proposal that federal policy has since started treating as a deadline.

The arithmetic that decides your date

Three numbers, and none of them is a forecast about quantum hardware.

How long your data has to stay confidential. How long your migration takes, counting inventory, vendor dependencies, hardware security modules, certificate chains and everything embedded in a product you shipped years ago. And the year the attack becomes affordable to someone who wants your data.

A European bank with a ten-year confidentiality obligation is encrypting records today that must remain unreadable in 2036. The EU roadmap gives it until the end of 2030 for high-risk systems, which leaves about four years of migration for data already sitting in an archive. Anything captured today and stored by a patient adversary is protected by an assumption, and that assumption is the one Gidney moved by a factor of 20 without touching a chip.

Questions readers ask

How many qubits does it take to break RSA-2048?

Under a million noisy physical qubits, running for under a week, on the assumptions in Gidney's May 2025 preprint. The algorithm itself uses 1 537 logical qubits, and the rest is the surface code wrapped around them. The 2019 estimate by the same author, on the same assumed hardware, was 20 million physical qubits and eight hours.

Has a machine like this been built?

Nothing close to it. The largest commercially available machines announced in late 2025 count their physical qubits in the hundreds. The estimate is a resource calculation done on paper, and it describes a machine nobody has built.

Why did the number fall if no new hardware appeared?

Three algorithmic results. Approximate residue arithmetic removed the need to hold the full 2048-bit value in a quantum register. Yoked surface codes store idle logical qubits at roughly triple the density. Magic state cultivation shrank the factories that supply the non-Clifford gates. The saving in qubits was paid for in runtime, which rose from eight hours to nearly five days.

Does the difference between physical and logical qubits matter here?

It decides whether the comparison you are making means anything. The million is a physical count. Vendors quote both, sometimes in the same sentence, and in this design alone the two differ by a factor of several hundred.

When does a European organisation have to have migrated?

The EU roadmap asks every Member State to have started by the end of 2026, to have migrated high-risk use cases and critical infrastructure by the end of 2030, and to finish the rest by 2035 as far as is practically feasible. The American dates of 2030 and 2035 come from a NIST report that is still an initial public draft.

What to watch

Watch whether the estimate moves again. Gidney states that he sees no further order of magnitude under the same physical assumptions. A fourth revision that cut the requirement anyway would say that planning around slow progress is the wrong default, and it would arrive years before any hardware did.

Watch whether NIST finalises IR 8547, and whether 2030 and 2035 survive the process. Those two years are already quoted in procurement documents and board papers as though they were settled policy.

Watch the end of 2026. That milestone produces the first checkable output of the European roadmap: national strategies and cryptographic inventories, published or not published, country by country. The inventory is the slow part of every migration, and an organisation that has not started one has already spent part of the four years the roadmap leaves before 2030.

Sources

The resource estimate comes from Craig Gidney's preprint, How to factor 2048 bit RSA integers with less than a million noisy qubits, arXiv:2505.15917, posted on 21 May 2025. Every figure attributed to it here appears in that document, including the 2019 comparison, which the preprint takes from Gidney and Ekerå in Quantum, volume 5, page 433, 2021. The three component results are cited within it: approximate residue arithmetic from Chevignard, Fouque and Schrottenloher, IACR Cryptology ePrint Archive 2024/222; yoked surface codes from Gidney, Newman, Brooks and Jones in Nature Communications, May 2025; magic state cultivation from Gidney, Shutty and Jones, arXiv:2409.17595. The migration dates come from the coordinated implementation roadmap published by the NIS Cooperation Group on 23 June 2025, from Commission Recommendation (EU) 2024/1101 of 11 April 2024, and from NIST IR 8547, which remains an initial public draft. Machine specifications come from Quantinuum's and IBM's own announcements of 6 and 12 November 2025.

Where this article states a ratio the preprint does not print, the arithmetic is ours and is done on the preprint's own figures. No number on this page comes from a vendor summary or a research aggregator, and no projected specification is written as an achieved one.