Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits

2026/03/30 by Madelyn Cain, Qian Xu, Robbie King +6 · 17 voices · 16 citations
#quant-ph

paper · pdf

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.

Cited by

• Remote entanglement need not be the bottleneck for modular trapped-ion quantum computing
• Blind Transpiler: An open-source library for universally blind and homomorphic quantum computations
• Quantum-classical crossover in fault-tolerant quantum dynamics simulation
• Fast logical operations in quantum LDPC codes using simple resource states
• Full Extractors for Logical Processing in Hypergraph Product Codes
• Towards Ultra-High-Rate Quantum Error Correction with Reconfigurable Atom Arrays
• Metasurfaces for neutral-atom trapping
• Probing the Planck scale with quantum computation
• Architecting Early Fault Tolerant Neutral Atoms Systems with Quantum Advantage
• Practical Post-Quantum Cryptography for Bandwidth Constrained or Non-Terrestrial Networks, and Power Constrained Devices
• Practical advantage beyond the quadratic speedup limit with fully-quantum walks
• Hardware-Tailored Resource Estimation for Magic-State Distillation on Silicon Spin Qubits
• PIQC: Scalable Distributed Quantum Computing via Photonic Integration of Designed Molecular Quantum Nodes
• Space-Time Tradeoffs of Pauli-Based Computation in Distributed qLDPC Architectures
• Quantum simulation of chemistry via quantum fast multipole method
• Pair-Partition Constructions for CPM-Based Quantum LDPC Codes
• Efficient atom rearrangements for quantum error correction primitives with a single AOD
• Efficient QKD in Non-Ideal Scenarios with User-Defined Output Length Requirements

Discussions

• We're making such good progress at reducing the number of qubits needed for factoring that we might accidentally overshoot and bring it down to zero, at which point we would have a classical factoring [bsky, 26 points, 1 comments]
• Are we having fun yet? https://arxiv.org/abs/2603.28627 [bsky, 13 points, 2 comments]
• Shor's algorithm is possible with as few as 10k reconfigurable atomic qubits [hn, 13 points, 6 comments]
• Maybe I live long enough to see actual cryptographic breakage of internet relevant encryption by a quantum computer. arxiv.org/abs/2603.28627 [bsky, 12 points, 2 comments]
• "our most time-efficient architectures can potentially enable runtimes of 10 days for ECC–256 with ≈ 26,000 qubits, and 97 days for RSA–2048 with ≈ 102,000 qubits" arxiv.org/pdf/2603.28627 [bsky, 9 points, 0 comments]
• ...we show that Shor's algorithm can be executed at cryptographically relevant scales with as few as 10,000 reconfigurable atomic qubits. ... the runtime for discrete logarithms on the P-256 elliptic [bsky, 8 points, 1 comments]
• Their claimed attack circuit works independent of architecture, but this work also published yesterday by Caltech implements their circuit on a reconfigurable neutral-atom arch w/ only 10K physical qu [bsky, 6 points, 1 comments]
• Shor's algorithm is possible with as few as 10k reconfigurable atomic qubits [hn, 4 points, 0 comments]
• Quantencomputer Neue Ansätze brechen Verschlüsselung mit weniger Qubits [lemmy, 4 points, 0 comments]
• arxiv.org/abs/2603.286... [bsky, 1 points, 0 comments]
• Couple of papers, actually. The Google one and this one: arxiv.org/abs/2603.28627 [bsky, 1 points, 0 comments]
• The paper. arxiv.org/pdf/2603.28627 [bsky, 0 points, 1 comments]
• Shor’s algorithm is possible with as few as 10,000 reconfigurable atomic qubits arxiv.org/abs/2603.28627 [bsky, 0 points, 0 comments]
• A mi me están grabando arxiv.org/abs/2603.28627 Se que al 99% esto os suena a chino, pero es MUY importante. Si logran ejecutar el algoritmo de Shor en tan "pocos" qubits acaban de ponerle fin a la cr [bsky, 0 points, 0 comments]
• A recent study indicates that Shor's algorithm, key for breaking classic cryptography, can run on just 10,000 atomic qubits. This substantially lowers the physical qubit needs for fault-tolerant quant [bsky, 0 points, 0 comments]
• Shor's Algorithm is possible with as few as 10,000 reconfigurable Atomic Qubits - #Research Paper available on arXiv #QuantumComputing #Cryptography arxiv.org/abs/2603.28627 [bsky, 0 points, 0 comments]
• [2603.28627v1] Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits https://arxiv.org/abs/2603.28627 [bsky, 0 points, 0 comments]

Related

• Practical Challenges in Executing Shor's Algorithm on Existing Quantum Platforms
• Fault-tolerant quantum computation with a neutral atom processor
• Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays
• Architectural mechanisms of a universal fault-tolerant quantum computer
• The Pinnacle Architecture: Reducing the cost of breaking RSA-2048 to 100 000 physical qubits using quantum LDPC codes