Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits
Madelyn Cain, Qian Xu, Robbie King, Lewis R. B. Picard, Harry Levine, Manuel Endres, John Preskill, Hsin-Yuan Huang
Abstract
Quantum computers have the potential to perform computational tasks beyond the reach of classical machines. A prominent example is Shor's algorithm for integer factorization and discrete logarithms, which is of both fundamental importance and practical relevance to cryptography. However, due to the high overhead of quantum error correction, optimized resource estimates for cryptographically relevant instances of Shor's algorithm require millions of physical qubits. Here, by leveraging advances in high-rate quantum error-correcting codes, efficient logical instruction sets, and circuit design, we show that Shor's algorithm can be executed at cryptographically relevant scales with as few as 10,000 reconfigurable atomic qubits. Increasing the number of physical qubits improves time efficiency by enabling greater parallelism; under plausible assumptions, the runtime for discrete logarithms on the P-256 elliptic curve could be just a few days for a system with 26,000 physical qubits, while the runtime for factoring RSA-2048 integers is one to two orders of magnitude longer. Recent neutral-atom experiments have demonstrated universal fault-tolerant operations below the error-correction threshold, computation on arrays of hundreds of qubits, and trapping arrays with more than 6,000 highly coherent qubits. Although substantial engineering challenges remain, our theoretical analysis indicates that an appropriately designed neutral-atom architecture could support quantum computation at cryptographically relevant scales. More broadly, these results highlight the capability of neutral atoms for fault-tolerant quantum computing with wide-ranging scientific and technological applications.
AI Impact Assessments
(3 models)Scientific Impact Assessment
Core Contribution
This paper presents a dramatic reduction in the physical qubit requirements for running Shor's algorithm at cryptographically relevant scales — from millions of qubits (prior estimates) down to approximately 10,000–26,000 reconfigurable atomic qubits. The key insight is the systematic co-optimization of three layers: (1) high-rate quantum LDPC codes with ~30% encoding rates (versus ~4% for surface codes), (2) efficient logical instruction sets based on code surgery with verifiable compilation, and (3) circuit-level design leveraging the reconfigurable connectivity of neutral-atom platforms. The paper targets two cryptographic benchmarks: RSA-2048 factoring and ECC-256 discrete logarithms, finding that ECC-256 could be solved in ~10 days with ~26,000 qubits, while RSA-2048 requires ~97 days with ~102,000 qubits in the most time-efficient configuration.
Methodological Rigor
The paper builds on a technically sound foundation but requires careful scrutiny of several assumptions:
Strengths in rigor:
Areas of concern:
Potential Impact
Cryptographic implications: This is potentially the most consequential aspect. If these estimates are even approximately correct, the timeline for quantum threats to deployed cryptographic systems (RSA, ECC) is substantially compressed. The paper strengthens the urgency for post-quantum cryptographic migration, a process already underway with NIST standards (FIPS 203-205). The finding that ECC-256 is significantly easier to break than RSA-2048 is particularly relevant given the widespread adoption of elliptic curve cryptography.
Quantum computing architecture: The paper establishes a concrete architecture for neutral-atom fault-tolerant quantum computing that could influence hardware roadmaps across the industry. The five-order-of-magnitude reduction in qubit requirements over two decades (Fig. 1b) demonstrates that resource estimates can change dramatically with algorithmic and coding-theoretic advances.
Broader FTQC applications: While focused on Shor's algorithm, the architectural framework — high-rate qLDPC memory, smaller processor blocks, magic state factories — is general-purpose and applicable to quantum chemistry, optimization, and machine learning workloads.
Timeliness & Relevance
This paper arrives at a critical juncture. Neutral-atom platforms have recently demonstrated below-threshold fault-tolerant operations (Bluvstein et al., Nature 2026), arrays of 6,100+ qubits, and continuous operation of large systems. The gap between demonstrated capabilities (~500 computational qubits) and the ~10,000 qubits proposed here, while still significant, is far more tractable than the million-qubit gap of prior estimates. The paper leverages very recent advances in qLDPC codes, decoders (BP-LSD), and logical operations (high-rate surgery, cultivation) that have matured only in 2024-2026.
Strengths & Limitations
Key strengths:
Notable limitations:
Overall Assessment
This is a high-impact theoretical analysis that substantially recalibrates expectations for the feasibility of cryptographically relevant quantum computation. While the most optimistic estimates require assumptions that remain unvalidated, even the conservative (space-efficient) architecture at ~10,000 qubits represents a paradigm shift in resource estimation. The paper is well-structured and technically detailed, though the gap between theoretical projections and experimental demonstration remains significant. Its primary impact will be in shaping quantum computing hardware roadmaps, informing cryptographic migration timelines, and motivating further development of high-rate qLDPC codes and parallel logical operations.
Generated Mar 31, 2026
Comparison History (310)
Paper 2 likely has higher impact: it targets a universally recognized benchmark (cryptographically relevant Shor), offers a striking reduction in required physical qubits (to ~10k) tied to a specific scalable platform (neutral atoms), and is highly timely for fault-tolerant quantum computing roadmaps and security planning. Its applications span cryptography, national security, and hardware architecture, with broad cross-field relevance. Paper 1 is innovative and rigorous for open-system quantum simulation in battery materials, but it is more niche and its resource estimates still imply very large T-counts, limiting near-term influence.
Paper 2 likely has higher impact due to its direct, timely relevance to fault-tolerant quantum computing and cryptographically relevant Shor implementations, with clear real-world implications for security and hardware roadmaps. It translates coding/circuit advances into concrete qubit-count and runtime estimates tied to an experimentally advancing platform (neutral atoms), influencing both industry and policy. Paper 1 is highly rigorous and novel in quantum learning theory with broad theoretical applications, but its near-term practical impact is more indirect compared to a credible path to breaking widely used cryptosystems.
Paper 2 dramatically reduces the resource requirements for cryptographically relevant quantum computing from millions to 10,000 qubits. This breakthrough significantly accelerates the timeline for practical quantum threats to classical cryptography, ensuring massive interdisciplinary impact across physics, computer science, and global cybersecurity. While Paper 1 presents a valuable hardware advancement, Paper 2's implications for the feasibility of Shor's algorithm offer far broader and more urgent real-world consequences.
Paper 2 drastically reduces the physical qubit requirements for Shor's algorithm from millions to 10,000. This significantly accelerates the timeline for cryptographically relevant quantum computers, creating a massive and urgent global impact on cybersecurity, cryptography, and quantum hardware roadmaps. While Paper 1 presents a strong practical advancement, Paper 2 has a much broader and paradigm-shifting technological impact.
While Paper 1 offers profound theoretical insights into quantum foundations, Paper 2 has massive and immediate real-world implications. Demonstrating that Shor's algorithm can run on just 10,000 qubits drastically accelerates the timeline for quantum computers to break standard encryption. This urgent threat will significantly impact cryptography, cybersecurity, and quantum hardware engineering, making it exceptionally timely and widely relevant.
Paper 1 demonstrates that Shor's algorithm can be run with ~10,000 physical qubits rather than millions, representing a dramatic reduction with immediate implications for cryptography, national security, and the quantum computing industry timeline. It leverages multiple recent advances (high-rate QEC codes, neutral-atom architectures) and directly addresses one of the most consequential problems in quantum computing. Paper 2 makes a solid contribution to quantum network sensing security, but its scope and transformative potential are narrower. Paper 1's result fundamentally changes the practical timeline for cryptographically relevant quantum computing, ensuring broader and more urgent impact.
Paper 2 likely has higher impact: it presents a timely, field-shaping resource analysis suggesting cryptographically relevant Shor computations could be feasible with ~10k–26k neutral-atom qubits—far below prior million-qubit estimates—directly affecting quantum architectures, error-correction research, and cybersecurity planning. Its breadth spans theory, hardware roadmap, and cryptography, with clear real-world implications. Paper 1 is a strong experimental milestone for surface-code lattice surgery and logical non-Clifford gates, but at distance-3 it is a narrower, incremental step toward scalability compared to Paper 2’s potentially paradigm-shifting feasibility claims.
Paper 2 likely has higher impact: it directly targets cryptographically relevant Shor/discrete-log resource estimates with a concrete hardware platform (neutral atoms) and qubit counts (10k–26k), which is timely for policy, security, and engineering roadmaps. The applications (breaking RSA/ECC) are immediately consequential and cross-cut quantum architecture, error correction, and cryptography, broadening impact beyond a subfield. Paper 1 is novel and rigorous (provable separations in CV QRC with Kerr feedback) but is more specialized and its real-world uptake depends on narrower reservoir-computing use cases and experimental feasibility.
Paper 2 demonstrates that Shor's algorithm could be run at cryptographically relevant scales with only ~10,000 physical qubits—orders of magnitude fewer than previous estimates of millions. This dramatic reduction has enormous implications for cryptography, national security, and the quantum computing roadmap, making it relevant far beyond the quantum error correction community. While Paper 1 makes important technical contributions to logical processing in QLDPC codes, Paper 2's result is more immediately transformative, broadly accessible, and likely to attract attention across computer science, cryptography, physics, and policy communities.
Paper 2 demonstrates that Shor's algorithm could be run at cryptographically relevant scales with only ~10,000 physical qubits—orders of magnitude fewer than previous estimates of millions. This has enormous practical implications for cryptography, national security, and the quantum computing hardware roadmap, generating broad interdisciplinary impact. While Paper 1 makes valuable technical contributions to Clifford+T synthesis with strong implications for fault-tolerant compilation, Paper 2's dramatic reduction in resource requirements fundamentally reshapes timelines for practical quantum computing and will attract far wider attention across scientific, industrial, and policy communities.