PaperlayerView exact revision on arXiv

Source-linked AI summary

How to factor 2048 bit RSA integers with less than a million noisy qubits

Craig Gidney

arXiv:2505.15917v1quant-ph

TL;DR

Quantum factoring threatens RSA, creating a need to estimate the resources required for attacks when planning migration to quantum-safe cryptosystems. This paper combines and streamlines recent arithmetic, storage, and magic-state techniques to reduce the qubit cost of factoring. It estimates that a 2048-bit RSA integer can be factored in less than a week with less than a million noisy qubits under specified physical assumptions.

  • Problem

    Quantum computers can efficiently factor integers, making RSA vulnerable and motivating estimates of quantum factoring costs for transition planning.

  • Method

    The paper combines and streamlines approximate residue arithmetic, yoked surface-code storage, magic-state cultivation, and arithmetic optimizations.

  • Results

    Less than a million noisy qubits and less than a week are estimated to suffice for factoring a 2048-bit RSA integer.

  • Takeaways & Limitations

    The estimate informs how quickly quantum-safe cryptosystems should be deployed and provides a signpost for the current state of quantum factoring.

  • Takeaways & Limitations

    The estimate assumes a specific surface-code architecture, connectivity, timing, and uniform depolarizing noise model, with detailed cold-storage analysis left for future work.

Abstract

from arXiv · show

Planning the transition to quantum-safe cryptosystems requires understanding the cost of quantum attacks on vulnerable cryptosystems. In Gidney+Ekerå 2019, I co-published an estimate stating that 2048 bit RSA integers could be factored in eight hours by a quantum computer with 20 million noisy qubits. In this paper, I substantially reduce the number of qubits required. I estimate that a 2048 bit RSA integer could be factored in less than a week by a quantum computer with less than a million noisy qubits. I make the same assumptions as in 2019: a square grid of qubits with nearest neighbor connections, a uniform gate error rate of $0.1\%$, a surface code cycle time of 1 microsecond, and a control system reaction time of $10$ microseconds. The qubit count reduction comes mainly from using approximate residue arithmetic (Chevignard+Fouque+Schrottenloher 2024), from storing idle logical qubits with yoked surface codes (Gidney+Newman+Brooks+Jones 2023), and from allocating less space to magic state distillation by using magic state cultivation (Gidney+Shutty+Jones 2024). The longer runtime is mainly due to performing more Toffoli gates and using fewer magic state factories compared to Gidney+Ekerå 2019. That said, I reduce the Toffoli count by over 100x compared to Chevignard+Fouque+Schrottenloher 2024.

1 Introduction

Quantum computers can efficiently factor integers, making RSA vulnerable and motivating cost estimates for transitioning to quantum-safe cryptosystems. This paper addresses the space–time trade-off in quantum factoring by targeting substantially lower qubit requirements while optimizing gate costs.

  • Motivation: Quantum computers can efficiently factor integers, so RSA is not secure against quantum computers.Estimating quantum factoring costs supports planning the transition away from RSA and other vulnerable cryptosystems.
  • Prior work: 1.5n logical qubits was historically the smallest known requirement for factoring an n-bit number.This reflected the assumption that arithmetic modulo an n-bit number required an n-qubit register.
  • Prior work: 2 trillion Toffoli gates and slightly more than 0.5n logical qubits characterize CFS24, versus 3 billion Toffoli gates and slightly more than 3n logical qubits in GE21.CFS24 trades roughly 1000x more Toffolis for a 6x reduction in space.
  • Paper scope: The paper describes a streamlined CFS algorithm, estimates its Toffoli and logical-qubit counts, and converts them into fault-tolerant physical-cost estimates.Appendix A provides more detailed mock-ups of the algorithm and its physical implementation.

2 Methods

The paper combines approximate residue arithmetic with masked period finding and arithmetic optimizations to reduce space while controlling accumulated approximation error. It also uses implementation choices that improve the spacetime trade-off of the low-qubit approach.

  • 2.1 Approximate Residue Arithmetic: Approximate residue arithmetic represents operations modulo a product L of small primes, enabling exponentially more space-efficient arithmetic than storing log L bits directly.Residues are combined using the Chinese remainder theorem; prime lengths can be ℓ = Θ(log log L).
  • 2.1 Approximate Residue Arithmetic: O(2^-f) modular deviation per truncated addition accumulates to at most O(A·2^-f) over A additions.The error comes from omitted carries and slightly early wraparound after truncation.
  • 2.1 Approximate Residue Arithmetic: Choosing L so that L mod N has negligible modular deviation controls wraparound errors when accumulating modulo L before reducing modulo N.The residue-system primes can be selected to make this condition hold for the relevant multipliers.
  • 2.1 Approximate Residue Arithmetic: A constant total modular deviation, such as 10%, is sufficient for period finding, which determines the required number of kept bits f.The bound follows by solving |P|·ℓ·2^-f = O(1).
  • 2.2 Approximate Period Finding: Masking avoids measuring approximation errors, while randomized analysis predicts a w/P failure probability and an otherwise usual period-finding outcome.Numerics suggest the deterministic case is close enough to this randomized model for cost estimation; masking and approximation contribute an upper-bound error S + ε/S.
  • 2.3 Ekerå-Håstad Period Finding: Increasing s reduces input qubits and multiplications, which reduces the required residue-system size and can make the computation both smaller and faster despite additional shots.The paper gives s = 3 versus s = 1 as an example of this compounded benefit.
  • 2.4 Arithmetic Optimizations: The paper introduces orders-of-magnitude cost reductions beyond its simple example through arithmetic optimizations, including replacing modular additions with underflow-detectable subtractions.The subtraction form uses an extra qubit that flips exactly when underflow occurs.

3 Results

The results estimate logical and physical costs for an optimized factoring algorithm, using addition, lookup, and phaseup tallies together with fault-tolerant layout assumptions. For RSA2048, the estimate is fewer than one million noisy qubits and less than one week of runtime.

  • Logical Costs: Addition, lookup, and phaseup operations provide the basic cost model for estimating total logical resources.Their symbolic counts are converted to numerical estimates using selected parameter values.
  • Logical Costs: Grid-scanned parameter combinations are evaluated through Pareto frontiers, with q^3t used to favor qubit savings over time savings.The parameter ranges include residue-prime bit length, window sizes, and truncated-accumulator length.
  • Physical Costs: 1409 logical qubits are active at peak for RSA2048, with cold storage holding 1280 input qubits and hot storage holding 131 additional logical qubits.The chosen parameters are s = 8, ℓ = 21, w1 = 6, w3 = 3, w4 = 5, f = 33, and m = 1280.
  • Physical Costs: 897864 physical qubits are estimated before slack, including 1537 total logical qubits and cultivated magic-state compute resources.The report rounds the physical count to one million.
  • Physical Costs: 12.07 hours per shot and 9.2 expected shots produce a 4.96-day factoring estimate after accounting for the 93.3% no-logical-error shot rate.The paper rounds this estimate up to one week for slack.
  • Physical Costs: Less than one million noisy qubits and less than one week are estimated for factoring a 2048-bit RSA integer under the stated surface-code assumptions.The assumptions include a 1-microsecond surface-code cycle, 10-microsecond control reaction time, nearest-neighbor square-grid connectivity, and 0.1% gate error.

4 Conclusion

The paper combines recent algorithmic and fault-tolerance techniques to reduce the estimated qubit requirement for breaking RSA2048. It presents the estimate as a state-of-the-art reference relevant to quantum-safe deployment planning, while identifying a remaining order-of-magnitude boundary under unchanged physical assumptions.

  • 4 Conclusion: The expected qubit requirement for breaking RSA2048 is reduced from 20 million to 1 million by combining and streamlining three recent results.The combined sources are CFS24, Gid+25, and GSJ24.
  • 4 Conclusion: The estimate is intended to indicate the current state of quantum factoring and inform how quickly quantum-safe cryptosystems should be deployed.The author supports deprecation after 2030 and disallowance after 2035 as a security preference, not as a prediction of quantum-computer availability.
  • 4 Conclusion: Without changing the paper’s physical assumptions, the author sees no way to reduce the qubit count by another order of magnitude.The paper therefore does not claim that RSA2048 factoring is plausible with one hundred thousand noisy qubits.

A.1 Reference Python Implementation of Algorithm

The reference implementation expresses the optimized algorithm through quantum integer registers, modular exponentiation, lookups, approximate accumulation, compression, and measurement-based uncomputation. It also verifies clean termination while explicitly limiting what the simulator can validate.

  • Reference Python Implementation of Algorithm: Quantum values are represented as variable-length superposed unsigned integers called quints, allocated and cleared through QPU operations.The implementation uses Q_ prefixes and supports slicing quints as views of register subsections.
  • Reference Python Implementation of Algorithm: The simulator checks that registers and kickback phases are uncomputed before completion, but sampled classical trajectories cannot verify interference or masking correctness.It instead fuzzes classical output correctness and phase-kickback fixes from measurement-based uncomputation.
  • Reference Python Implementation of Algorithm: Lookups are uncomputed by measurement-based uncomputation, with resulting phase corrections recorded in lookup vents for later handling.The code uses operations such as mx_rz and del_measure_x to measure X-basis qubits and clear or deallocate them.
  • Reference Python Implementation of Algorithm: GHZ lookups use one address qubit and a [0, k] table, enabling efficient lattice-surgery implementation through Z-splitting and Z-merging.A corrective Z gate is applied when required after merging.
  • Reference Python Implementation of Algorithm: The implementation computes modular exponentiation across residue-system periods, then compresses and later uncompresses the discrete-log register.Windowed lookups and modular subtraction implement the exponentiation subroutine.

A.2 Addition Operation

The addition operation is designed around a parity-product identity that maps naturally to lattice surgery. Its circuit and layout use deferred corrections, optimized routing, and measurement-based uncomputation to leave only the desired accumulator value.

  • Addition Operation: The adder computes each sum bit using a three-parity-product identity built from Z parity products.The identity is interesting for lattice surgery because Z parity products are relatively cheap to access.
  • Addition Operation: The circuit performs an out-of-place addition and then uncomputes an input using the relation b = s − a.Corrections from teleported gates are represented through multi-qubit Pauli products and deferred phase corrections.
  • Addition Operation: The optimized ZX graph changes the adder calling convention by attaching input registers through Z ports rather than ordinary input and output ports.The graph is optimized into an efficient lattice-surgery layout.
  • Addition Operation: The physical layout places input registers on opposite sides of compute-region hallways whose pitch matches both the adder block and magic-state factories.Figures 10 and 11 provide lattice-surgery mock-ups of the compute and uncompute steps and a 35-qubit in-place addition.
  • Addition Operation: After addition, the previous accumulator is uncomputed directly while lookup values are removed by measurement-based uncomputation, leaving the new accumulator value.The resulting phase corrections are handled by a later phaseup operation.

A.3 Phaseup Operation

The paper implements phaseups by splitting the address register, expanding each half into power products, applying masked phase flips, and uncomputing the products. Wandering AND gates move corrections into classical control, reducing reaction depth.

  • Phaseup definition: A phaseup flips amplitudes selected by a classical 2^n-bit table acting on an n-qubit address register.Phaseups appear when table lookups are uncomputed using measurement-based uncomputation.
  • Construction: The address register is split into low and high halves, each expanded into a power-product register before applying data-driven Z and CZ gates.The table is reshaped into a matrix indexed by the two halves, enabling masked phase flips.
  • Implementation: Grouped multi-target CZ gates reduce marginal lattice-surgery cost when targeting larger Pauli products.The circuit diagram groups many individual CZ gates into a few multi-target operations.
  • Optimization: Wandering AND gates replace quantum CNOT corrections with a correction-matrix rewrite in the classical control system.The same correction also modifies phase corrections during power-product uncomputation.
  • Optimization: The phaseup’s overall reaction depth is n/2 ± O(1), because corrections from power-product computation merge into one change to the Z and CZ gate set.Only uncomputation remains corrected layer by layer.

A.4 Lookup Operation

The lookup operation initializes table-selected output qubits using power products of split address halves and wandering multi-target Toffoli gates. Measurement-based uncomputation converts the resulting phase corrections into a deferred phaseup.

  • Lookup definition: A lookup initializes w output qubits from a classical table of 2^n w-bit integers indexed by an n-qubit address.
  • Construction: The address is split into two halves, whose power products control multi-target Toffoli gates that initialize the outputs.Both the power-product AND gates and the multi-target Toffolis are allowed to wander.
  • Uncomputation: Measuring all ancillary qubits in the X basis creates phase corrections that can be merged into a later phaseup during lookup uncomputation.Each correction corresponds to phase flipping a subset of address values.
  • Implementation: The lattice-surgery mock-ups illustrate the lookup layout, including 21 of the 63 multi-target CX gates for a six-qubit address.The computation of the two power products is omitted from the mock-up.

A.5 Frequency Basis Measurement

The frequency-basis measurement uses adaptive phase gates obtained by kickback from additions into a phase-gradient state. The state is approximately prepared with Clifford+T sequences, while rounding and preparation introduce bounded failure probabilities.

  • Measurement: Frequency-basis measurement applies an inverse QFT, then uses deferred measurement to replace quadratically many controlled phase gates with n−1 adaptive phase gates.The adaptive angles are determined by measurement outcomes.
  • Phase implementation: Phase kickback from adding a rounded classical constant C into a g-qubit phase-gradient state applies the desired phase approximately to a control qubit.C is chosen as the nearest multiple of 2π/2^g to the target angle.
  • Error sources: Rounding phase angles causes a maximum over- or under-rotation of π/2^g radians per rotation.The resulting shot-failure bound applies across the n−1 rotations in the frequency-basis measurement.
  • Error sources: Phase-gradient preparation contributes a shot-failure probability no larger than the state infidelity, regardless of how many additions use the prepared state.The state is an eigenstate of addition and can be projected into a perfect state with probability equal to its fidelity.
  • State preparation: The example preparation uses 159 T gates for the first 11 qubits, approximates later qubits with |+⟩ states, and contributes less than 10^-5 total algorithm-failure probability.This estimate combines 5·10^-6 preparation infidelity with 4·10^-6 from inaccurate cultivated T gates.
Loading 2505.15917v1…