Recognition: 1 theorem link
· Lean TheoremHow to factor 2048 bit RSA integers with less than a million noisy qubits
Pith reviewed 2026-05-13 04:17 UTC · model grok-4.3
The pith
A 2048-bit RSA integer can be factored using fewer than a million noisy qubits in under a week.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Using approximate residue arithmetic to cut the number of Toffoli gates, yoked surface codes to store idle logical qubits more compactly, and magic state cultivation to spend less space on state factories, the space-time cost of Shor's algorithm for 2048-bit RSA drops so that fewer than one million noisy qubits suffice to finish the factorization in less than a week, under the assumptions of a 0.1 percent gate error rate, one-microsecond surface-code cycle time, ten-microsecond reaction time, and square-grid nearest-neighbor connectivity.
What carries the argument
Approximate residue arithmetic combined with yoked surface codes for idle logical qubits and magic state cultivation for efficient factory allocation, applied inside the quantum circuit for Shor's algorithm.
If this is right
- The Toffoli gate count falls by more than a factor of 100 relative to the 2024 residue-arithmetic paper alone.
- Qubit requirements drop from the 20 million of the 2019 estimate to under one million.
- Runtime lengthens to under one week because more Toffoli gates are executed with fewer parallel magic-state factories.
- The same three techniques can be combined while keeping the original physical assumptions on connectivity and error rates.
Where Pith is reading between the lines
- If the techniques scale, quantum computers smaller than previously expected could threaten RSA security.
- Similar storage and factory optimizations may reduce resources for other quantum algorithms that use many idle qubits or magic states.
- The gap between current hardware and a cryptographically relevant machine narrows, tightening timelines for post-quantum cryptography migration.
Load-bearing premise
The uniform 0.1 percent gate error rate, 1-microsecond surface-code cycle time, 10-microsecond control reaction time, square-grid nearest-neighbor connectivity, and the claimed performance gains from approximate residue arithmetic, yoked surface codes, and magic state cultivation all hold simultaneously.
What would settle it
A physical demonstration of yoked surface codes that achieves the predicted space savings for idle logical qubits at 0.1 percent error, or a run of the full algorithm on a smaller RSA instance whose measured overhead deviates sharply from the extrapolated qubit and time figures.
read the original abstract
Planning the transition to quantum-safe cryptosystems requires understanding the cost of quantum attacks on vulnerable cryptosystems. In Gidney+Eker{\aa} 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{\aa} 2019. That said, I reduce the Toffoli count by over 100x compared to Chevignard+Fouque+Schrottenloher 2024.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript updates the 2019 Gidney-Ekerå resource estimate for factoring a 2048-bit RSA integer via Shor's algorithm on a surface-code quantum computer. It claims that incorporating approximate residue arithmetic (Chevignard et al. 2024), yoked surface codes for idle logical qubits (Gidney et al. 2023), and magic state cultivation (Gidney et al. 2024) reduces the required noisy qubits to under one million while increasing runtime to less than one week, under the same hardware model: square-grid nearest-neighbor connectivity, uniform 0.1% gate error rate, 1 μs surface-code cycle time, and 10 μs control reaction time. The qubit savings are attributed to the three cited techniques; the runtime increase stems from higher Toffoli counts and fewer magic-state factories, though the Toffoli count is reduced >100× relative to the 2024 residue-arithmetic paper.
Significance. If the composed estimates hold, the work meaningfully lowers the qubit threshold for a quantum attack on RSA-2048, which is directly relevant to timelines for post-quantum cryptography migration. It demonstrates how recent, independently published advances in arithmetic and error correction can be combined to alter practical resource projections without new foundational inventions. The explicit synthesis and the >100× Toffoli reduction versus the 2024 baseline are useful contributions to the quantum cryptanalysis literature.
major comments (2)
- [Resource Estimation] The central qubit-count claim rests on the three external techniques (approximate residue arithmetic, yoked surface codes, magic-state cultivation) composing without hidden overheads in the error budget or connectivity under the uniform 0.1% error model. The manuscript should add an explicit integration paragraph or table (e.g., in the resource-estimation section) showing the per-component qubit allocation and confirming that the yoked-code storage does not increase the logical error rate beyond the assumed budget when paired with the approximate arithmetic.
- [Comparison to Prior Work] The runtime estimate of 'less than a week' is driven by the increased Toffoli count and reduced number of magic-state factories. A sensitivity table or calculation showing how the wall-clock time scales if the Toffoli reduction is only 50× (rather than >100×) versus Chevignard et al. 2024 would clarify the robustness of the 'less than a week' bound.
minor comments (3)
- [Abstract] The abstract states the final numbers as inequalities ('less than a million', 'less than a week'); the main text or a summary table should report the concrete estimated values (e.g., 850 000 qubits, 5.2 days) for reproducibility.
- [Introduction] All hardware assumptions inherited from the 2019 paper (gate error rate, cycle time, reaction time, connectivity) should be restated verbatim in a dedicated 'Assumptions' subsection so that readers need not consult the earlier work.
- Figure captions or legends that break down qubit allocation among data, yoked storage, and magic-state factories would improve clarity of the claimed savings.
Simulated Author's Rebuttal
We thank the referee for their careful reading and constructive comments. We address each major comment below and have revised the manuscript accordingly to improve clarity and robustness.
read point-by-point responses
-
Referee: [Resource Estimation] The central qubit-count claim rests on the three external techniques (approximate residue arithmetic, yoked surface codes, magic-state cultivation) composing without hidden overheads in the error budget or connectivity under the uniform 0.1% error model. The manuscript should add an explicit integration paragraph or table (e.g., in the resource-estimation section) showing the per-component qubit allocation and confirming that the yoked-code storage does not increase the logical error rate beyond the assumed budget when paired with the approximate arithmetic.
Authors: We agree that an explicit breakdown of the integration improves transparency. In the revised manuscript we have added a paragraph and table in the resource-estimation section that lists the qubit allocations for the approximate-residue-arithmetic core, the yoked-surface-code storage of idle logical qubits, and the magic-state-cultivation factories, together with their sum under the stated hardware model. The paragraph notes that the yoked codes (Gidney et al. 2023) are used only for idle qubits whose logical error rate is already budgeted under the uniform 0.1 % physical error model; because they do not perform gates on those qubits, they introduce no additional logical-error overhead when combined with the approximate-arithmetic circuits of Chevignard et al. 2024. Nearest-neighbor connectivity on the square grid is preserved throughout. revision: yes
-
Referee: [Comparison to Prior Work] The runtime estimate of 'less than a week' is driven by the increased Toffoli count and reduced number of magic-state factories. A sensitivity table or calculation showing how the wall-clock time scales if the Toffoli reduction is only 50× (rather than >100×) versus Chevignard et al. 2024 would clarify the robustness of the 'less than a week' bound.
Authors: We thank the referee for highlighting the value of a sensitivity check. Although the >100× Toffoli reduction is the central quantitative result of the synthesis, we have added a short paragraph and accompanying table in the discussion section. The table shows that, holding all other parameters fixed, a 50× reduction would increase the wall-clock time to roughly 10–12 days. This remains well within the regime of practical interest for the estimate and confirms that the “less than a week” figure is robust under the full reduction while still providing context for possible variations in the arithmetic improvement. revision: yes
Circularity Check
No significant circularity
full rationale
The manuscript is a resource-estimation synthesis that explicitly combines results from independent prior publications (Chevignard et al. 2024 for approximate residue arithmetic, Gidney et al. 2023 for yoked surface codes, Gidney et al. 2024 for magic state cultivation) under the same hardware model as the 2019 baseline. All load-bearing performance claims are attributed to those external sources rather than re-derived or fitted within this paper. No self-definitional equations, fitted inputs renamed as predictions, uniqueness theorems imported from the author's own work, or ansatzes smuggled via citation appear in the derivation. The Toffoli-count reduction is presented as a comparison to the cited 2024 work, not as an internal redefinition. The estimate remains conditional on the cited techniques holding when composed, with no reduction of the central claim to its own inputs by construction.
Axiom & Free-Parameter Ledger
free parameters (3)
- gate error rate =
0.1%
- surface code cycle time =
1 microsecond
- control system reaction time =
10 microseconds
axioms (2)
- domain assumption Qubits arranged in a square grid with only nearest-neighbor connectivity
- domain assumption Surface code threshold and logical error rates behave as modeled at 0.1% physical error
Forward citations
Cited by 31 Pith papers
-
LightStim: A Framework for QEC Protocol Evaluation and Prototyping with Automated DEM Construction
LightStim automates DEM construction for QEC protocols via an augmented Pauli tableau during compilation, matching public tools on detector counts and error rates while enabling new cross-code designs.
-
Energy efficiency of quantum computers
A new definition of quantum computer energy efficiency is introduced and applied to five major qubit platforms, yielding concrete consumption estimates for current systems and a benchmarking framework for future archi...
-
Mitigating Classical Resource Costs in Quantum Error Correction via Generalized qLDPC Predecoding
An automated predecoder generator for arbitrary qLDPC codes cuts decoder utilization by up to 3963x and supports hardware scaling to tens or hundreds of thousands of logical qubits within power limits.
-
Efficient simulation of noisy IQP circuits with amplitude-damping noise
A classical polynomial-time sampler exists for the output distribution of amplitude-damped IQP circuits with logarithmic depth and arbitrary l-local diagonal gates.
-
Tour de gross: A modular quantum computer based on bivariate bicycle codes
Bivariate bicycle codes enable a modular architecture that supports an order of magnitude more logical circuit volume per physical qubit than surface-code designs under circuit noise.
-
Error Correction of Beamsplitter-Generated Entangled GKP States
Trapped-ion experiment generates all four Bell states of GKP qubits via beamsplitter interference of qunaught states and applies error correction to extend their lifetime.
-
The true cost of factoring: Linking magic and number-theoretic complexity in Shor's algorithm
Shor's algorithm generates and consumes magic resources in direct proportion to the difficulty of the underlying factoring problem.
-
Two Layers, No Swaps: Biplanar SPOQC Architecture Improves Runtime of Fermi-Hubbard Simulation
The biplanar architecture maps Fermi-Hubbard spin sectors to two planes, eliminating swaps and cutting each Trotter step depth to 4t_synth + 90 logical timesteps versus 6t_synth + 354 in single-plane methods, yielding...
-
FTPrimitiveBench: A Benchmark Suite For Logical Computation Under Hardware-Motivated and Biased Noise Models
FTPrimitiveBench is a new benchmark suite for testing surface-code logical primitives under Pauli-biased, measurement-biased, and spatially non-uniform noise models, revealing that noise structure interacts distinctly...
-
Factoring $2048$ bit RSA integers with a half-million-qubit modular atomic processor
A modular atomic processor with 500,000 qubits factors 2048-bit RSA numbers in roughly the same time as a single large module when inter-module Bell-pair communication runs at 10^5 per second.
-
High-fidelity entangling gates and nonlocal circuits with neutral atoms
Neutral-atom system delivers state-of-the-art CZ gate fidelity of 99.854% (99.941% postselected) and demonstrates coherent rearrangement for nonlocal quantum circuits.
-
Millikelvin digital-to-analog converter for superconducting quantum processors
A millikelvin superconducting DAC integrated with fluxonium qubits generates persistent flux tuning signals via SFQ pulses without measurable coherence degradation.
-
Assessing System Capabilities and Bottlenecks of an Early Fault-Tolerant Bicycle Architecture
Syn@fac optimization reduces estimated circuit failure probability by a factor of 9 on average across non-Clifford benchmarks for bivariate bicycle code modular FTQC architectures, with additional gains from transvect...
-
Fault-Tolerant Quantum Computing with Trapped Ions: The Walking Cat Architecture
A trapped-ion architecture based on LDPC codes and cat-state factories achieves 110 logical qubits and one million T gates per day using 2514 physical qubits, with estimates for Heisenberg model simulation on 100 site...
-
QLLVM: A Scalable Quantum-Classical Co-Compilation Framework based on LLVM
QLLVM delivers an LLVM-based end-to-end co-compiler that unifies classical HPC and quantum programs into one executable, with a three-stage quantum path via MLIR and QIR that reduces circuit depth and gate counts on M...
-
dqc_simulator: an easy-to-use distributed quantum computing simulator
dqc_simulator is a new Python toolkit for automating realistic simulations of both hardware and software in distributed quantum computing systems.
-
Fast measurement of neutral atoms with a multi-atom gate
A multi-atom Rydberg gate with N ancillae enables N-fold photon collection for fast neutral-atom measurement, achieving infidelity below 10^{-3} in 6 μs with N=5 in Cs-Rb simulations.
-
Demonstrating Record Fidelity for the Quantum Fourier Transform
Parity Architecture delivers record ~0.01 fidelity for 50-qubit QFT on IBM hardware with super-exponential scaling improvement.
-
Long-range tunable coupler for modular fluxonium quantum processors
A tunable coupler design enables sub-100 ns two-qubit gates with errors below 10^{-4} between fluxonium qubits over 1 cm distances for modular architectures.
-
Heterogeneous architectures enable a 138x reduction in physical qubit requirements for fault-tolerant quantum computing under detailed accounting
Heterogeneous quantum architectures with task-specific hardware and QEC encodings deliver up to 138x lower physical-qubit overhead than monolithic baselines for fault-tolerant algorithms, including RSA-2048 factoring ...
-
Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation
A space-efficient quantum ECDLP algorithm uses 5n + 4⌊log₂n⌋ + O(1) logical qubits and O(n³) Toffoli gates, lowering the 256-bit estimate from 2124 to 1333 qubits.
-
Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities: Resource Estimates and Mitigations
Resource estimates show Shor's algorithm can break 256-bit ECDLP with fewer than 1450 logical qubits and 90 million Toffoli gates on fast-clock quantum hardware, enabling on-spend attacks on cryptocurrency mempools.
-
Tolerating Device Failure in Distributed Quantum Computing
Distributed toric and hyperbolic Floquet codes maintain logical error suppression when entire nodes fail at low rates, with the toric code outperforming a monolithic device below 0.05% physical error rate for node fai...
-
FTPrimitiveBench: A Benchmark Suite For Logical Computation Under Hardware-Motivated and Biased Noise Models
FTPrimitiveBench is an open-source pipeline that connects parameterized hardware-motivated noise models to surface-code logical primitive circuits, enabling reproducible cross-primitive QEC benchmarking under Pauli bi...
-
ADaPT: Adaptive-window Decoding for Practical fault-Tolerance
Adaptive-window decoding that shrinks or expands based on decoder confidence cuts reaction-time overhead in quantum error correction without raising logical error rates.
-
Operational criteria for quantum advantage in latency-constrained nonlocal games
A framework with operational criteria and a trapped-atom hardware proposal for achieving statistically significant quantum advantage in latency-constrained nonlocal games.
-
Low Latency GNN Accelerator for Quantum Error Correction
An FPGA-accelerated GNN decoder for surface-code quantum error correction delivers sub-1us latency and lower error rates than state-of-the-art approaches for code distances up to 7.
-
Probing the Planck scale with quantum computation
A 500-logical-qubit quantum computer could reject laboratory-confined theories by surpassing the Planck-scale operation rate of 2^491 m^{-3} s^{-1}, with a 1600-qubit machine limited by the observable universe.
-
The Quantum-Cryptographic Co-evolution
A coordinate system is introduced to categorize stages of the transition to quantum-resilient cryptography, with the Quantum Gap defined as the highest-risk period requiring immediate crypto-agile adoption.
-
Cryogenic Systems for Quantum Photonic Technologies: A Practical Review
A practical review summarizing principles and requirements of modern cryogenic systems from flow cryostats to dilution refrigerators for solid-state quantum optical devices.
- The Pinnacle Architecture: Reducing the cost of breaking RSA-2048 to 100 000 physical qubits using quantum LDPC codes
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.