Reading the 2025 estimate for factoring RSA-2048 with under a million qubits

Start with what kind of result this is

In May 2025 Craig Gidney of Google Quantum AI posted "How to factor 2048 bit RSA integers with less than a million noisy qubits" to arXiv. It is a resource estimate: a calculation of how large a hypothetical fault-tolerant quantum computer would need to be, and how long it would run, to factor an RSA-2048 modulus under stated assumptions. It is external research, not a QuantumSoftware experiment, and no device of that size exists.

What the paper estimates

The headline estimate: a 2048-bit RSA integer could be factored in less than a week by a quantum computer with less than a million noisy qubits. The figures behind it come from the results section:

• At the algorithm level, about 1,400 logical qubits (Table 5 lists 1,399) and an expected 6.5 billion Toffoli gates per factoring.
• A physical layout of 897,864 physical qubits, reported as one million for slack, partly because cold storage was not simulated under the algorithm's workload.
• About 12 hours per run (shot) and 9.2 expected shots. Allowing for shots lost to logical errors gives 4.96 days, rounded up to a week.

The assumptions

The paper keeps the physical assumptions of the 2019 estimate:

• a square grid of qubits with nearest-neighbour connections;
• a uniform gate error rate of 0.1%, modelled as depolarizing noise;
• a surface code cycle time of 1 microsecond;
• a control-system reaction time of 10 microseconds.

Change any of them and the code distances, layout and runtime change too.

Key concepts and techniques

A physical qubit is a hardware component. A logical qubit is information protected by error correction across many physical qubits. Here, active "hot" logical qubits are distance-25 surface code patches of 2(d+1)² = 1,352 physical qubits each, chosen for a target logical error rate of 10⁻¹⁵ per qubit per round.

The abstract names three main sources of the qubit reduction:

• approximate residue arithmetic (Chevignard, Fouque and Schrottenloher, 2024), which avoids holding full 2048-bit intermediate values;
• yoked surface codes (Gidney, Newman, Brooks and Jones, 2023), which store idle logical qubits at about 430 physical qubits each instead of 1,352;
• magic state cultivation (Gidney, Shutty and Jones, 2024), which shrinks the space needed to prepare the states that power Toffoli gates; the layout uses six small factories.

Comparison with the 2019 estimate

Gidney and Ekerå's 2019 paper, published in Quantum in 2021, estimated eight hours with 20 million noisy qubits under the same assumptions. The 2025 paper trades time for space: about a twentieth of the qubits, but days instead of hours. It attributes the longer runtime to more Toffoli gates (6.5 billion against about 3 billion) and fewer magic state factories.

The 2024 approach by Chevignard, Fouque and Schrottenloher had already cut logical qubits to a little over half the key length, but needed about 2 trillion Toffoli gates. Gidney reduces that count by more than 100 times.

What the paper does not show

• It does not report a measurement. No machine with a million physical qubits at these error rates exists.
• It does not give a date. NIST's explainer says no one knows when a cryptographically relevant quantum computer will appear; estimates vary, and some suggest it could be possible in less than ten years.
• It does not cover every public-key system. The estimate is for RSA-2048; other cryptographic cases are left to future work.

The author also sees no way, without changing the physical assumptions, to cut the qubit count by another order of magnitude.

What it means for cryptography

On 13 August 2024 NIST released its first three finalized post-quantum cryptography standards:

• FIPS 203, ML-KEM (from CRYSTALS-Kyber), the primary standard for general encryption;
• FIPS 204, ML-DSA (from CRYSTALS-Dilithium), the primary standard for digital signatures;
• FIPS 205, SLH-DSA (from SPHINCS+), a hash-based signature backup in case ML-DSA proves vulnerable.

NIST encourages starting the transition now, noting that past migrations have taken 10 to 20 years. A second reason is "harvest now, decrypt later": encrypted data captured today can be stored until a future quantum computer breaks it, so long-lived secrets carry risk before any such machine exists.

Gidney agrees with the initial public draft of a NIST transition report that vulnerable systems should be deprecated after 2030 and disallowed after 2035. Not, he writes, because he expects large enough quantum computers by 2030, but because he prefers security not to depend on progress being slow.

Questions for your research notes

• Which physical assumptions does the estimate use, and how sensitive is it to each?
• Which numbers are logical counts, and which include fault-tolerance overhead?
• Which parts were simulated, and which are left as future work?
• How does the space–time trade-off compare with the 2019 and 2024 estimates?
• Which of your systems use RSA, and how long must their data stay confidential?

Sources

• Craig Gidney (2025): How to factor 2048 bit RSA integers with less than a million noisy qubits, arXiv.
• Craig Gidney and Martin Ekerå: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits, arXiv; Quantum 5, 433 (2021).
• NIST Releases First 3 Finalized Post-Quantum Encryption Standards, 13 August 2024.
• NIST: What Is Post-Quantum Cryptography?: timelines and "harvest now, decrypt later".
• What a below-threshold surface-code result actually means: physical versus logical errors.

This post summarises published external research and standards; it reports no QuantumSoftware hardware experiment or measurement.