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 (344)
Paper 2 has significantly higher potential impact due to its profound real-world implications for cryptography and cybersecurity. While Paper 1 provides a valuable theoretical contribution to mitigating barren plateaus in near-term quantum circuits, Paper 2 radically reduces the hardware requirements for running a fault-tolerant Shor's algorithm from millions to just 10,000 physical qubits. By leveraging recent advances in high-rate quantum error correction and neutral-atom architectures, Paper 2 dramatically accelerates the projected timeline for cryptographically relevant quantum computing, ensuring massive cross-disciplinary impact across physics, computer science, and global security.
Paper 1 offers a paradigm-shifting resource estimate for Shor's algorithm, reducing required physical qubits from millions to 10,000 using neutral-atom architectures. This drastically accelerates the timeline for cryptographically relevant quantum computers. While Paper 2 presents an impressive experimental advancement in fundamental quantum optics, Paper 1 has vastly broader real-world applications, directly impacting global cybersecurity, cryptography, and the strategic direction of quantum hardware development. Its timeliness and cross-disciplinary relevance give it a significantly higher potential for widespread scientific and societal impact.
Paper 2 achieves a dramatic reduction in physical qubit requirements for Shor's algorithm (from millions to ~10,000), directly impacting cryptography, quantum computing roadmaps, and post-quantum security timelines. Its results are timely, grounded in demonstrated neutral-atom experiments, and have broad technological and societal implications. Paper 1 offers a valuable, rigorous analytical framework for correlated coherent errors with a novel encoding insight, but its impact is more specialized within QEC theory. Paper 2's breadth, real-world relevance, and potential to reshape practical quantum computing give it higher estimated impact.
Paper 2 likely has higher scientific impact due to its broad, timely implications for fault-tolerant quantum computing and cryptography. Reducing Shor’s algorithm resource estimates from millions to ~10,000–26,000 physical qubits—linked to an experimentally advancing neutral-atom platform—could strongly influence research directions, funding, and security planning across multiple fields (quantum architecture, QEC, cryptography). Paper 1 is experimentally novel and impactful for integrated masers and sensing, but its immediate cross-domain societal impact is narrower than a credible pathway to cryptographically relevant quantum computation.
Paper 2 dramatically reduces the qubit requirement for cryptographically relevant Shor's algorithm from millions to ~10,000, a transformative result with immediate implications for cryptography, security policy, and quantum architecture design. It combines advances in error-correcting codes, logical instruction sets, and circuit design. While Paper 1 is an impressive experimental milestone (11,000 atoms via metasurface), it addresses only trapping/loading without demonstrated coherent qubit control or computation. Paper 2's broader cross-field impact, timeliness for post-quantum cryptography, and its potential to reshape roadmaps give it higher estimated scientific impact.
Paper 2 dramatically lowers the physical qubit requirement for cryptographically relevant Shor's algorithm from millions to just 10,000. This architectural breakthrough has profound, urgent real-world implications for global cybersecurity, cryptography, and computer science. Its breadth of impact and immediate practical relevance far exceed the foundational physics advance presented in Paper 1.
Paper 1 drastically accelerates the timeline for cryptographically relevant quantum computing by reducing the physical qubit requirement for Shor's algorithm from millions to just 10,000. This breakthrough has profound, immediate implications for global cybersecurity, cryptography, and quantum hardware development. While Paper 2 offers a significant fundamental advance in physical chemistry and polaritonics, Paper 1's monumental impact on national security, computer science, and physics gives it a much broader and more urgent real-world scientific impact.
Paper 2 drastically reduces the physical qubit requirements for cryptographically relevant Shor's algorithm from millions to 10,000. This breakthrough dramatically accelerates the timeline for practical quantum computing and the potential breaking of standard encryption. While Paper 1 presents an elegant advancement in quantum metrology with practical sensing applications, Paper 2 has far wider-reaching implications for global cybersecurity, computer science, and quantum hardware development. The urgency and transformative nature of realizing scalable, fault-tolerant quantum computation give Paper 2 a significantly higher potential scientific and technological impact.
Paper 1 addresses Shor's algorithm at cryptographically relevant scales with a dramatic reduction in qubit requirements (10,000 vs millions), directly impacting cryptography, cybersecurity, and post-quantum standards with broad societal relevance. Its results, tied to demonstrated neutral-atom experiments, are timely and highly visible. While Paper 2 provides rigorous quantum-classical crossover analysis for many-body dynamics—an important scientific contribution—its impact is more specialized to condensed matter physics. Paper 1's implications for breaking widely-used encryption give it far broader real-world consequence and public attention.
Paper 2 dramatically reduces the physical qubit requirement for cryptographically relevant Shor's algorithm from millions to ~10,000, with direct implications for cryptography, national security, and the timeline for post-quantum transition. Its breadth of impact spans quantum computing hardware, error correction, and cybersecurity, and is highly timely given the neutral-atom platform's rapid progress. Paper 1 is elegant and novel, bridging attosecond metrology and quantum optics, but its impact is confined to a specialized ultrafast/quantum-optics niche with narrower near-term applications.