PaperlayerView exact revision on arXiv

Source-linked AI summary

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, Dolev Bluvstein

arXiv:2603.28627v1quant-ph

TL;DR

The paper addresses the resource demands of cryptographically relevant Shor computation by designing fault-tolerant architectures based on reconfigurable atom arrays and high-rate codes. It finds that these architectures could support Shor’s algorithm with as few as 10,000 atomic qubits, while larger systems reduce runtime through parallelism.

  • Problem

    Large-scale logical algorithms face substantial resource demands from magic-state generation and the construction of low-overhead fault-tolerant operations.

  • Method

    The authors combine reconfigurable atom arrays with high-rate quantum error-correcting codes, low-overhead logical operations, decoders, and parallelized circuit constructions.

  • Results

    Shor’s algorithm can be implemented at cryptographically relevant scales using as few as 10,000 atomic qubits, with potential runtimes of 10 days for ECC–256 and 97 days for RSA–2048 at the stated qubit counts.

  • Takeaways & Limitations

    The analysis suggests that a neutral-atom system capable of implementing Shor’s algorithm could be constructed and underscores the importance of transitioning cryptographic systems toward post-quantum standards.

  • Takeaways & Limitations

    The architecture remains a theoretical existence proof whose practical construction and optimization are technically challenging, and some hardware speedup approaches require additional work for a complete architecture.

Abstract

from arXiv · show

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.

Neutral-atom architecture

Reconfigurable neutral-atom arrays combine dynamic connectivity, parallel control, and distinct functional zones to support the architectures analyzed for cryptographically relevant Shor computations. The proposed scale is motivated by demonstrated arrays, fault-tolerant operations, and hardware-development paths, while runtime estimates depend on assumed cycle speeds.

  • Architecture: Dynamic tweezer rearrangement enables massively parallel operations and nonlocal connectivity for neutral-atom error correction.Identical qubits and global parallel control also simplify error-correction protocols on redundant qubits.
  • Architecture: 11,961 qubits are organized into memory, processor, operation, resource, and reservoir/reloading zones.The operation zone supports Pauli product measurements, while the resource zone generates magic states for universal computation.
  • Experimental basis: 6,100 coherent atomic qubits have been trapped, and optical tweezer arrays with 360,000 traps have been demonstrated.These demonstrations address system-size feasibility, although the 6,100-qubit arrays had not yet realized quantum computation.
  • Experimental basis: Fault-tolerant architectures have operated 2× below threshold, with a demonstrated path to 10× below threshold.High-fidelity entangling operations have so far been realized only on regions of a few hundred qubits, while increased laser power is proposed for larger regions.
  • Operating assumptions: The analysis assumes a 1 ms stabilizer measurement cycle, although achieving this rate may require technological development.Readout and motion currently range from 100 µs to several milliseconds depending on implementation.
  • Resource examples: 13,255 qubits are used for the illustrated RSA–2048 architecture and 11,961 qubits for ECC–256.The resource estimates compare these neutral-atom designs with prior cryptographic resource estimates.

Codes, logic, and compilation

The paper combines high-rate qLDPC codes, low-overhead logical operations, code surgery, and compilation to reduce the space and time costs of Shor’s algorithm. The resulting constructions achieve low projected logical error rates and substantial qubit savings, but large-code surgery remains technically challenging.

  • Codes: High-rate qLDPC codes densely pack logical qubits into nonlocal code blocks, reducing error-correction overhead relative to surface-code architectures.Their main implementation challenge is addressing individual logical qubits and executing logic within large blocks.
  • Codes: Approximately 30% encoding-rate lifted-product codes are analyzed with parameters [[2610, 744, ≤16]], [[4350, 1224, ≤20]], and [[5278, 1480, ≤24]].Here [[n, k, d]] denotes physical qubits, logical qubits, and code distance.
  • Code performance: 10^-11 is the extrapolated per-cycle block failure rate achieved by the lp3,7 24 code at p = 0.1%.Block failure denotes the probability that any logical qubit fails during a cycle.
  • Code performance: 161× fewer physical qubits are used than surface codes with the same distance and number of logical qubits, while achieving comparable block error rates.The analysis uses a circuit-level depolarizing-noise model and a customized belief-propagation decoder.
  • Limitations: A theoretical existence-proof architecture uses smaller high-rate processor codes because practical construction and optimization of large-code surgeries remain technically challenging.The authors note that this construction may not be optimal in resource costs.
  • Magic states: A |CCZ⟩ resource state has logical error rate ≲10^-10 at p = 0.1% and is generated in less than one surgery cycle on average.High-rate 8T-to-CCZ distillation is performed in parallel using cultivated |T⟩ states.
  • Logic and compilation: The compilation strategy decomposes circuits into processor-sized subcircuits, teleports logical qubits between memory and processor, and performs Pauli-based computation with |CCZ⟩ states.Teleportation and computation are implemented through Pauli product measurements and code surgery.
  • Logic and compilation: Each subcircuit uses 4m_i + 4β_i + γ_i Pauli product measurements, and its time cost scales with processor distance and these measurement counts.The amortized Toffoli cost is minimized when subcircuits contain many Toffoli gates relative to communication and mid-circuit measurements.

Resource estimates

Resource estimates show that reconfigurable neutral-atom architectures can reach cryptographically relevant Shor instances with far fewer qubits than earlier approaches. Increasing physical-qubit count enables parallel operations and substantially reduces runtime, with the estimates remaining preliminary and assumption-dependent.

  • Resource accounting: 90% total success probability is used to bound executable Toffoli counts for RSA–2048, DH–2048, and ECC–256 in the balanced architecture.Figure 3 compares prior circuits by logical-qubit count and Toffoli count with the architecture’s executable Toffoli capacity.
  • Error-rate requirements: ECC–256 requires p = 0.093% with the lp3,7 24 memory, while compilation (1) can use p = 0.070% with the smaller lp3,7 20 memory.RSA–2048 and DH–2048 require slightly reduced physical error rates.
  • Runtime variation: Balanced-architecture runtimes for RSA–2048 and ECC–256 vary by nearly two orders of magnitude across logical architectures, circuits, and algorithms.The space-efficient and balanced designs execute Toffoli gates and Pauli product measurements sequentially.
  • Parallelism: Parallelized carry-lookahead adders reduce Toffoli depth from approximately linear in key size to ≈4 log(n), enabling time-efficient compilation.The speedup estimate assumes parallel surgery operations and replaces serial ripple-carry adders in core subroutines.
  • Time-efficient architectures: 26,000 physical qubits are estimated for ECC–256 and 102,000 for RSA–2048 in time-efficient architectures.These preliminary estimates assume surgery systems scale with the codes undergoing parallel operation and use parallel magic-state generation.
  • Comparison with prior work: 98,000 qubits and 1 month were previously estimated for one RSA–2048 small-block architecture, whereas the proposed designs reduce qubit counts by one order of magnitude.The comparison concerns architectures leveraging long-range, reconfigurable neutral-atom connectivity.

Conclusion and outlook

The proposed neutral-atom architectures could implement Shor’s algorithm at cryptographically relevant scales, while additional hardware and algorithmic improvements may reduce space and runtime overheads. The analysis also connects this feasibility result to the need for post-quantum cryptographic migration.

  • Conclusion and outlook: 10,000 atomic qubits could support Shor’s algorithm at cryptographically relevant scales.The architectures use reconfigurable atom arrays and optimize high-rate codes, decoders, and low-overhead logical operations.
  • Conclusion and outlook: 10 days is a projected ECC–256 runtime for the most time-efficient architecture using ≈26,000 qubits.The estimate incorporates improvements to quantum algorithms, parallel logical operations, and circuits.
  • Conclusion and outlook: 97 days is a projected RSA–2048 runtime for the most time-efficient architecture using ≈102,000 qubits.The space and time overheads for these problems are expected to improve further.
  • Conclusion and outlook: ∼100,000 available qubits could enable space-time tradeoffs that reduce computation time by factors of up to 6–10 ×.The text also identifies faster readout and qubit motion as potential hardware-level speed improvements.
  • Conclusion and outlook: The theoretical analysis suggests that a neutral-atom system capable of implementing Shor’s algorithm could be constructed.The authors emphasize that substantial expertise, experimental development effort, and architectural design remain necessary.
  • Conclusion and outlook: The findings underscore ongoing efforts to transition widely deployed cryptographic systems toward post-quantum standards.These standards are designed to remain secure against quantum attacks.

METHODS

The methods describe high-rate quantum error-correcting codes and their roles, including optimized lifted-product and bivariate bicycle constructions. Their parameters determine practical tradeoffs in encoding, error suppression, and stabilizer measurement costs.

  • METHODS: The work uses optimized lifted-product codes and prior bivariate bicycle code constructions.These are the high-rate quantum error-correcting codes analyzed in the paper.
  • METHODS: Block size, encoding rate, distance, and stabilizer weight define the codes’ practical tradeoffs.The constructions offer different combinations of these parameters.
  • METHODS: Code distance bounds logical-error scaling as physical error rates decrease.This makes distance relevant to the codes’ practical performance.
  • METHODS: Stabilizer weight is related to the number of entangling gates needed for stabilizer measurements.Thus, stabilizer weight contributes directly to measurement resource costs.

1. Lifted-product codes

The paper develops lifted-product codes by combining classical codes over a polynomial ring, then numerically estimates their parameters and block-error performance. The studied processor and memory instances provide high encoding rates and low extrapolated block error rates.

  • Code construction: The LP code family forms a quantum code from two classical codes with check matrices A and B over R := F2[x]/(x^ℓ+1), choosing B = A†.A† transposes A and replaces each polynomial entry p(x) with p(x^-1) modulo x^ℓ+1.
  • Code instances: The studied LP instances are new constructions obtained using an LLM-assisted heuristic computer search, alongside numerical distance estimation and code-parameter analysis.Extended Data Table II summarizes the code parameters, stabilizer weights, and encoding rates.
  • Processor code: The LP processor code lp3,5 achieves k = 148 logical qubits, rate k/n ≈0.132, stabilizer weight 8, and extrapolated block error rate ≲10^-11 at p = 0.1%.Its smaller block size and lower stabilizer weight make it suited to processor use, where logical-gate overhead scales with code size.
  • Memory codes: The lp3,7 memory codes achieve k = 744, k = 1224, and k = 1480 logical qubits, with rates k/n ≈0.285, ≈0.281, and ≈0.280, respectively.Their corresponding extrapolated block error rates per cycle are ≈10^-7, ≲10^-10, and ≲10^-11 at p = 0.1%.

2. Bivariate bicycle codes

Bivariate bicycle codes are a subfamily of lifted-product codes defined by two bivariate polynomials. The bb18 instance offers low block cost and error rates but encodes relatively few logical qubits.

  • BB codes are a special subfamily of lifted-product codes defined by two elements in a bivariate polynomial ring.
  • bb18 uses parameters [[248, 10, ≤18]] and is defined by the stated polynomials a and b with l = 31 and m = 4.
  • A rate of k/n = 10/248 ≈0.04 and stabilizer weight 6 characterize bb18.
  • bb18 achieves an extrapolated block error rate per code cycle of ≲10−11 at p = 0.1%.
  • Compared with lp3,5 20, bb18 has a smaller block size and comparable distance but encodes fewer logical qubits per block, creating a resource tradeoff.

Appendix B: Surgery

Code surgery extends lattice-surgery ideas to general qLDPC codes and provides a framework for fault-tolerant logical Pauli-product measurements. The paper adapts these techniques to its architecture and analyzes their resource costs and limitations.

  • Code surgery implements addressable logical Pauli-product measurements on general qLDPC codes.
  • The method generalizes lattice surgery from topological codes to general qLDPC codes.
  • This work adapts existing code-surgery techniques to its architecture and analyzes their concrete resource costs, limitations, and improvement opportunities.

1. Description

Surgery measures selected logical Pauli operators by coupling a qLDPC data code to an ancilla system, merging the codes, measuring checks, and then detaching the ancilla. Low-rate and high-rate gadgets differ in how many logical operators they measure in parallel.

  • A surgery gadget couples a qLDPC code to an ancilla system to extract selected logical Pauli eigenvalues nondestructively.
  • The procedure initializes the ancilla, merges it with the data code, measures merged-code checks for τs cycles, and detaches it with adaptive Pauli corrections.
  • During merging, target logical operators become X-checks whose measurements extract the desired information.
  • The ancilla is designed so the kernel of H′T_X maps exactly to the target logical operators of the data code.
  • Fault tolerance requires merged-code distance ˜d = Θ(d), qLDPC structure, and τs = Θ(d).
  • Low-rate surgery measures one logical operator per gadget, whereas high-rate surgery can measure up to t logical operators in parallel.

2. Concrete construction and benchmarking

The architecture combines dynamically reconfigured surgery ancillas across memory, processor, and factory zones with parallel magic-state distillation. Resource estimates quantify ancilla space and show fault-tolerant operation, while larger constructions remain incompletely benchmarked.

  • The architecture uses memory, processor, and factory codes with dedicated ancillas and bridge systems for logical Pauli-product measurements.
  • Reconfigurable connectivity reduces hardware needs by reserving space for only the largest dynamically generated ancilla configuration.
  • Representative ancilla systems are benchmarked for memory, processor, and factory operations, including logical-operator weight and code-specific constructions.
  • Detailed simulations remain future work for larger surgery gadgets, limiting validation beyond the representative benchmark.
  • NA = 894 and NA = 1,874 qubits are estimated for the space-efficient and balanced architectures, respectively, with the lp3,7 24 memory code.
  • Each surgery gadget is assumed to use τs ≈2d/3 code cycles, balancing space-like and time-like logical error rates.
  • High-fidelity |CCZ⟩ states are produced from cultivated |T⟩ states through parallel 8T-to-CCZ distillation and used to implement Toffoli gates.
  • The distillation protocol has p_CCZ ≈28(2pT )2, while the studied implementation achieves p_CCZ ≈10−10 using 2,565 total qubits.

Appendix D: Numerical simulations

The simulations assess code performance under circuit-level depolarizing noise, using repeated stabilizer measurements and surgery gadgets with belief-propagation-based decoding.

  • Noise model: Circuit-level simulations use a single physical error rate p for two-qubit gates, state preparation, and measurements.CNOT errors apply uniformly over 15 nontrivial two-qubit Pauli operators; preparation and measurement use single-qubit depolarizing noise.
  • Syndrome extraction: Syndrome extraction separately measures X-type and Z-type stabilizers, scheduling CNOTs by edge coloring of the Tanner graph.The schedule prevents any data qubit from participating in more than one gate per time step.
  • Memory experiment: Memory experiments run d/2 stabilizer cycles and define detectors from initial syndromes, consecutive-syndrome differences, and final data measurements.Logical observables are defined by the code’s logical X operators.
  • Surgery experiment: Surgery experiments initialize and measure ancillas in the Z basis while measuring data in either the X or Z basis.The protocol measures merged-code stabilizers for τs cycles and evaluates logical observables from final data and target-operator outcomes.
  • Decoding and logical error rate: Decoding uses ensemble BP-LSD instances with 100 min-sum belief-propagation iterations and exhaustive localized-statistics searches of order 5.A logical failure is recorded when the selected correction combined with the true error acts nontrivially on any logical observable.

Appendix E: Space-efficient and balanced architectures

The space-efficient and balanced architectures compile Clifford+Toffoli circuits into processor-sized subcircuits, using teleportation, Pauli-based computation, and code-surgery operations to estimate resource costs.

  • Architecture: The architecture combines a memory code, processor code, three |CCZ⟩ factory codes, and ancillary codes for distillation and cultivation.The memory code stores the algorithm’s logical footprint, while the processor code executes each subcircuit.
  • Compilation strategy: A general Clifford+Toffoli circuit is serialized into subcircuits Ci, each containing mi qubits, βi Toffoli gates, γi mid-circuit measurements, and arbitrary Clifford gates.Each subcircuit must satisfy mi ≤ kp so it fits inside the processor code block.
  • Compilation strategy: Each computation unit teleports qubits from memory to the processor, performs Pauli-based computation, and teleports them back.Toffoli gates use |CCZ⟩ teleportation, while mid-circuit Pauli measurements become sequential high-weight PPMs.
  • Time cost: Partial I/O operations reduce the computation-unit cost to τ(Ci) = (2m(in)i + 4βi + γi)τs when qubits remain in the processor across units.This replaces the full input-output count with an amortized count when consecutive subcircuits overlap in qubit support.
  • Adder costs: Ripple-carry adders are divided into processor-sized units, with kadd = floor((kp − 1)/3) and amortized input-output count mi = 2.5kadd.Downward units use βi = kadd Toffolis; upward units use γi = kadd mid-circuit measurements.

4. Time cost for RSA–2048 and ECC–256

The estimated amortized time per Toffoli differs substantially across algorithms and architectures because lookup costs depend strongly on processor capacity, while balanced architectures reduce these costs.

  • RSA–2048: RSA–2048 allocates approximately 50% of Toffolis to lookups and 50% to adders, with lookup word sizes at most 33.This workload split determines the architecture-dependent time-per-Toffoli estimates.
  • RSA–2048: The space-efficient RSA–2048 estimate uses approximately 25τs for adders and 71τs for lookups when kp = 10.The cited passages introduce the resulting RSA–2048 space-efficient estimate but do not include its completed numerical equation.
  • RSA–2048: The balanced architecture reduces RSA–2048 time-per-Toffoli to 13τs for adders and approximately 7τs for lookups when kp = 148.Both subroutines fit inside the processor in this architecture.
  • ECC–256: 72τs is the estimated ECC–256 time per Toffoli in the space-efficient architecture.The estimate combines controlled-adders, adders, and lookups, with lookups costing approximately 550τs.
  • ECC–256: 19τs is the estimated ECC–256 time per Toffoli in the balanced architecture.The lookup contribution falls to approximately 11τs when kp = 148.

Appendix F: Time-efficient architecture

The time-efficient architecture replaces serial ripple-carry operations with parallel carry-lookahead primitives and estimates space-time trade-offs across parallelism levels for ECC–256 and RSA–2048.

  • Parallel computation: The architecture generates and consumes |CCZ⟩ states in parallel and assumes parallel measurements of logically disjoint PPMs.These capabilities are intended to reduce time costs through high-rate distillation and surgery.
  • Parallel computation: Carry-lookahead adders use approximately 4 log(n) parallel Toffoli layers, versus approximately n or 2n layers for ripple-carry addition.The comparison covers uncontrolled and controlled addition, respectively.
  • Parallel computation: Each carry-lookahead layer uses magic-state generation, parallel teleportation, and CZ fix-ups, with a stated gate-teleportation and fix-up cost of 3τs.The estimate takes d = 20 and assumes parallel two-body PPM layers.
  • Resource costs: Processor size is estimated from stored logical qubits plus n − 2 log(n) carry-lookahead ancillas, divided by the encoding rate r.The analysis assumes r = 20% for P < 600 and r = 30% for P ≥ 600.
  • Resource costs: The resource zone uses five factory blocks encoding P logical qubits and P/nbatch surface codes for |T⟩ cultivation.Factory blocks can be assembled from smaller independent code blocks.
  • Resource costs: Ancilla size is estimated as γ(6P/r), with γ = 2 used for plotted results and γ = 1–3 considered for uncertainty.The parameter γ represents the relative ancilla size for measuring a layer of parallel PPMs.
  • Resource costs: Space-time estimates consider RSA–2048 at P = 100 and 1,160, and ECC–256 at P = 20 and 130, with uncertainty from surgery-system fluctuations.The speedup is computed relative to ripple-carry addition using carry-lookahead depth estimates.
Loading 2603.28627v1…