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

• URL: http://arxiv.org/abs/2603.28627v1
• Date: Mon, 30 Mar 2026 16:10:08 GMT
• Title: Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits
• Abstract summary: We show that Shor's algorithm can be executed at cryptographically relevant scales with as few as 10,000 reconfigurable atomic qubits.<n>Recent neutral-atom experiments have demonstrated universal fault-tolerant operations below the error-correction threshold.
• Score: 2.7317289681348993
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• Heterogeneous architectures enable a 138x reduction in physical qubit requirements for fault-tolerant quantum computing under detailed accounting [0.0]
  Quantum computer hardware is predicted to scale over hundreds of thousands of qubits coming online in the next decade.<n>Despite significant theoretical and experimental QEC progress, quantum computer architecture has suffered a significant gap.<n>We present a complete heterogeneous quantum computing architecture incorporating task-specific hardware selection and QEC encoding, and agnostic to code selection or physical qubit parameters.
  arXiv  Detail & Related papers  (2026-04-07T18:00:11Z)
• Practical Challenges in Executing Shor's Algorithm on Existing Quantum Platforms [17.64694402591544]
  Quantum computers pose a fundamental threat to widely deployed public-key cryptosystems, such as RSA and ECC.<n>We experimentally investigate Shor's algorithm on several cloud-based quantum computers using publicly available implementations.
  arXiv  Detail & Related papers  (2025-12-17T11:26:17Z)
• Quantum Error Correction Exploiting Degeneracy to Approach the Hashing Bound [0.0]
  We show that explicitly exploiting the degeneracy of quantum errors can significantly enhance the decoding performance.<n>The proposed method achieves a frame error rate as low as $10-4$ at a physical error rate of 9.45% for a code with 104,000 logical qubits and 312,000 physical qubits.
  arXiv  Detail & Related papers  (2025-06-18T17:07:04Z)
• Quantum Error Correction near the Coding Theoretical Bound [0.0]
  We present quantum error-correcting codes with efficient decoding.<n>This breakthrough paves the way for large-scale, fault-tolerant quantum computation.
  arXiv  Detail & Related papers  (2024-12-30T18:48:54Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Supervised binary classification of small-scale digit images and weighted graphs with a trapped-ion quantum processor [56.089799129458875]
  We present the results of benchmarking a quantum processor based on trapped $171$Yb$+$ ions.<n>We perform a supervised binary classification on two types of datasets: small binary digit images and weighted graphs with a ring topology.
  arXiv  Detail & Related papers  (2024-06-17T18:20:51Z)
• Optimizing quantum gates towards the scale of logical qubits [78.55133994211627]
  A foundational assumption of quantum gates theory is that quantum gates can be scaled to large processors without exceeding the error-threshold for fault tolerance. Here we report on a strategy that can overcome such problems. We demonstrate it by choreographing the frequency trajectories of 68 frequency-tunablebits to execute single qubit while superconducting errors.
  arXiv  Detail & Related papers  (2023-08-04T13:39:46Z)
• Factoring integers with sublinear resources on a superconducting quantum processor [11.96383198580683]
  Shor's algorithm has seriously challenged information security based on public key cryptosystems. To break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities. We report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm.
  arXiv  Detail & Related papers  (2022-12-23T14:45:02Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.