Cryptographically Relevant Quantum Computing — RSA Factorisation

Peter Shor publishes a polynomial-time quantum algorithm for integer factorisation and discrete logarithms. This establishes the algorithmic basis for a future quantum attack on RSA, conditional on a sufficiently capable quantum computer. Shor's 1994 result does not itself provide a physical-resource estimate for factoring RSA-2048; later engineering estimates are recorded separately. This instance therefore establishes the theoretical basis of the tracked claim, not practical cryptographic capability.

Gidney and Ekerå estimate that a surface-code quantum computer could factor an RSA-2048 integer in about eight hours using approximately 20 million noisy physical qubits under specified hardware assumptions, including a physical gate error rate of 10^-3, a one-microsecond surface-code cycle and a ten-microsecond reaction time. The work was first posted in 2019 and published in Quantum in 2021. It is a resource estimate, not an experimental factorisation result, and it quantifies the engineering gap rather than demonstrating that the required machine exists.

The error-correction results tracked in FR-QE-0003 and FR-QE-0004 provide relevant substrate evidence for cryptographically relevant quantum computation. In particular, Google's Willow work demonstrates below-threshold surface-code memories with logical error suppression as code distance increases from d=3 to d=5 to d=7, while Microsoft and Quantinuum reported four logical qubits with substantial logical-error suppression on trapped-ion hardware in 2024. These results support a credible engineering trajectory for fault-tolerant computation, but neither demonstrates RSA-scale resources, and the Microsoft/Quantinuum announcement must not be represented as a generic 10^-4 error rate per two-qubit logical gate. The gap to cryptographically relevant factorisation remains large.

On 13 August 2024 NIST finalises FIPS 203, FIPS 204 and FIPS 205: ML-KEM, ML-DSA and SLH-DSA, derived respectively from the CRYSTALS-Kyber, CRYSTALS-Dilithium and SPHINCS+ submissions. The standards are designed to resist future quantum-computer attacks on current public-key cryptography. This is anticipatory institutional evidence rather than evidence that a quantum computer can presently factor RSA-2048: it demonstrates migration planning in response to the prospective quantum threat, not satisfaction of the tracked technical claim.

Yan et al. post a preprint in December 2022 proposing a hybrid classical–quantum integer-factorisation method based on lattice reduction and QAOA. They experimentally factor integers up to 48 bits using ten superconducting qubits and estimate that a 372-qubit circuit could challenge RSA-2048; they do not factor RSA-2048 experimentally. Khattar and Yosri subsequently implement the proposed approach and report that, even with an idealised quantum optimiser, the claimed sublinear scaling fails to generate enough factoring relations for random 80-bit integers and beyond. The episode is therefore contesting evidence against the proposal's claimed scaling, not a failed experimental RSA-2048 factorisation.

Craig Gidney publishes a revised RSA-2048 resource estimate in May 2025. Under the same headline hardware assumptions used in the earlier Gidney–Ekerå estimate, the analysis estimates that RSA-2048 could be factored in less than a week using fewer than one million noisy physical qubits, compared with the earlier approximately 20-million-qubit estimate. The reduction comes from algorithmic and fault-tolerance improvements, including approximate residue arithmetic, denser storage of idle logical qubits and reduced magic-state-factory overhead. This is a theoretical resource estimate, not an experimental factorisation result, and therefore re-quantifies the engineering gap without demonstrating cryptographically relevant quantum capability.

Webster et al. introduce the Pinnacle Architecture, a fault-tolerant architecture based on quantum low-density parity-check codes, and estimate that RSA-2048 factorisation can be performed with fewer than 100,000 physical qubits under stated assumptions of a 10^-3 physical error rate, one-microsecond code cycles and ten-microsecond reaction time. The estimate obtains lower qubit overhead by changing the fault-tolerant architecture relative to the surface-code analyses in IN-002 and IN-006. It is a preprint resource estimate on an unbuilt architecture, not an experimental factorisation result or a like-for-like continuation of the surface-code trend. It materially lowers one modelled resource boundary while shifting weight onto QLDPC implementation, connectivity, decoding and sustained fault-tolerant operation assumptions.

Mundada et al. present a heterogeneous fault-tolerant architecture and detailed compiler-level resource accounting. For RSA-2048, their configuration using an experimentally demonstrated grid-coupling topology requires approximately 381,000 physical qubits and 9.2 days; adding an algorithm-specific adder accelerator changes the trade-off to approximately 439,000 qubits and 4.9 days. Under a separate hypothetical long-range-coupling assumption with QLDPC quantum memory, the estimate falls to approximately 190,000 physical qubits and under ten days. These are theoretical architecture and compilation estimates rather than an experimental RSA factorisation. The grid-connectivity case is particularly relevant because it provides an independent resource estimate with a more hardware-grounded connectivity assumption than the lowest headline QLDPC figures.