Shor's algorithm compiled on cat qubits: 22 593 qubits for RSA-2048 in 3.14 days
Axel Pappalardo, Dahmun Goudarzi, Victor Hertz, Hugo Jacinto, Larissa Kroell, André Schrottenloher, Peter Shanahan, Élie Gouzien, Rémi de la Vieuville, Vivien Londe
quant-phSubmitted Oct 27, 2026• Announced Oct 29, 2026• 0 citations
We present an end-to-end resource estimation of Shor's algorithm on superconducting cat qubits, from its mathematical description to the allocation and scheduling of physical qubits on a chip layout. We review modern versions of Shor's algorithm for RSA, ECDLP and FFDLP, and make their logical circuits and trade-offs explicit. We compile the dominant subroutines down to physical-qubit operations on two architectures: one based on repetition cat codes and one on LDPC cat codes. We design a parity-Cnot gate for cat qubits, extend a multi-target Cnot gate to the LDPC-cat architecture, and adapt an active injection procedure to cat qubits. Building on these primitives, we adapt to cat qubits the adder from Gidney's 2025 resource estimate for factoring RSA-2048. We combine our adder compilation and a coarser estimate for the phaseup with the factory designs and lookup compilation from the FeMoco resource estimation of Kroell et al. Together, these lead to chip layouts and schedules for factoring RSA-2048.
Assuming a 1$μ$s error-correction cycle time, a 10$μ$s reaction time, circuit-level phase-flip noise with probability $p_Z = 5 \times 10^{-4}$ and no bit-flips, factoring RSA-2048, the configuration we compile in full, requires about 23 000 cat qubits and 3.14 days. Reusing the compiled operations, solving ECDLP on secp256k1 requires at most 30 000 cat qubits and 1 hour, and FFDLP-512, which we propose as an intermediate benchmark, about 6 700 cat qubits and 21 minutes. Trading space for time, RSA-2048 runs in 1.25 hours on about 611 000 cat qubits. The no-bit-flip requirement (a bit-flip time of about 100 years) can be relaxed to a bit-flip time of about one hour by adding a concatenation layer with a distance-3 bit-flip code, in which case RSA-2048 needs about 45 000 cat qubits.
AI Summary
The paper estimates the physical resources for modern Shor algorithms on superconducting cat-qubit architectures, connecting algorithmic descriptions and logical circuits to chip layouts and schedules. It considers repetition-cat codes and an LDPC-cat architecture with dense storage coupled to a repetition-code access layer.
The physical compilation introduces a parity-CNOT taking $d$ error-correction cycles independently of the number of controls, extends multi-target CNOTs to LDPC-cat codes, and adapts active injection. These primitives support a redesigned adder using auto-AND and delayed-CZ resource states. The RSA estimate combines its layout and schedule with existing factory and lookup constructions and a coarser phaseup estimate. Explicit logical circuits and profiling tables also cover finite-field and elliptic-curve discrete logarithms.
Assuming a $1\,\mu\mathrm{s}$ correction cycle, $10\,\mu\mathrm{s}$ reaction time, circuit-level phase-flip probability $p_Z=5\times10^{-4}$, and negligible bit flips, RSA-2048 requires 22,593 cat qubits and 3.14 days, including an expected 9.60 shots. Derived estimates give 29,588 qubits and 61.8 minutes for secp256k1 ECDLP, and 6,656 qubits and 21.2 minutes for the proposed FFDLP-512 benchmark. An extrapolated space–time trade-off gives RSA-2048 in 1.25 hours using 610,530 qubits.
Only the balanced RSA configuration receives the full physical compilation; ECDLP estimates reuse RSA primitives and are presented as upper bounds. Negligible bit flips require lifetimes of roughly a century, far beyond measured values. An additional distance-3 bit-flip-protection layer is estimated to relax this to about one hour at approximately 45,000 qubits and at least 3.14 days.
Little sign of AI-generated textStrong assumptions
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
We present an end-to-end resource estimation of Shor's algorithm on superconducting cat qubits, from its mathematical description to the allocation and scheduling of physical qubits on a chip layout. We review modern versions of Shor's algorithm for RSA, ECDLP and FFDLP, and make their logical circuits and trade-offs explicit. We compile the dominant subroutines down to physical-qubit operations on two architectures: one based on repetition cat codes and one on LDPC cat codes. We design a parity-Cnot gate for cat qubits, extend a multi-target Cnot gate to the LDPC-cat architecture, and adapt an active injection procedure to cat qubits. Building on these primitives, we adapt to cat qubits the adder from Gidney's 2025 resource estimate for factoring RSA-2048. We combine our adder compilation and a coarser estimate for the phaseup with the factory designs and lookup compilation from the FeMoco resource estimation of Kroell et al. Together, these lead to chip layouts and schedules for factoring RSA-2048.
Assuming a 1μs error-correction cycle time, a 10μs reaction time, circuit-level phase-flip noise with probability pZ=5×10−4 and no bit-flips, factoring RSA-2048, the configuration we compile in full, requires about 23 000 cat qubits and 3.14 days. Reusing the compiled operations, solving ECDLP on secp256k1 requires at most 30 000 cat qubits and 1 hour, and FFDLP-512, which we propose as an intermediate benchmark, about 6 700 cat qubits and 21 minutes. Trading space for time, RSA-2048 runs in 1.25 hours on about 611 000 cat qubits. The no-bit-flip requirement (a bit-flip time of about 100 years) can be relaxed to a bit-flip time of about one hour by adding a concatenation layer with a distance-3 bit-flip code, in which case RSA-2048 needs about 45 000 cat qubits.
The paper estimates the physical resources for modern Shor algorithms on superconducting cat-qubit architectures, connecting algorithmic descriptions and logical circuits to chip layouts and schedules. It considers repetition-cat codes and an LDPC-cat architecture with dense storage coupled to a repetition-code access layer.
The physical compilation introduces a parity-CNOT taking d error-correction cycles independently of the number of controls, extends multi-target CNOTs to LDPC-cat codes, and adapts active injection. These primitives support a redesigned adder using auto-AND and delayed-CZ resource states. The RSA estimate combines its layout and schedule with existing factory and lookup constructions and a coarser phaseup estimate. Explicit logical circuits and profiling tables also cover finite-field and elliptic-curve discrete logarithms.
Assuming a 1μs correction cycle, 10μs reaction time, circuit-level phase-flip probability pZ=5×10−4, and negligible bit flips, RSA-2048 requires 22,593 cat qubits and 3.14 days, including an expected 9.60 shots. Derived estimates give 29,588 qubits and 61.8 minutes for secp256k1 ECDLP, and 6,656 qubits and 21.2 minutes for the proposed FFDLP-512 benchmark. An extrapolated space–time trade-off gives RSA-2048 in 1.25 hours using 610,530 qubits.
Only the balanced RSA configuration receives the full physical compilation; ECDLP estimates reuse RSA primitives and are presented as upper bounds. Negligible bit flips require lifetimes of roughly a century, far beyond measured values. An additional distance-3 bit-flip-protection layer is estimated to relax this to about one hour at approximately 45,000 qubits and at least 3.14 days.
We significantly reduce the cost of factoring integers and computing discrete logarithms in finite fields on a quantum computer by combining techniques from Shor 1994, Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Ekerå-Håstad 2017, Ekerå 2017, Ekerå 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of our construction using plausible physical assumptions for large-scale superconducting qubit platforms: a planar grid of qubits with nearest-neighbor connectivity, a characteristic physical gate error rate of 10 − 3 , a surface code cycle time of 1 microsecond, and a reaction time of 10 microseconds. We account for factors that are normally ignored such as noise, the need to make repeated attempts, and the spacetime layout of the computation. When factoring 2048 bit RSA integers, our construction's spacetime volume is a hundredfold less than comparable estimates from earlier works (Van Meter et al. 2009, Jones et al. 2010, Fowler et al. 2012, Gheorghiu et al. 2019). In the abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses 3 n + 0.002 n lg n logical qubits, 0.3 n 3 + 0.0005 n 3 lg n Toffolis, and 500 n 2 + n 2 lg n measurement depth to factor n -bit RSA integers. We quantify the cryptographic implications of our work, both for RSA and for schemes based on the DLP in finite fields.
Cat qubits provide appealing building blocks for quantum computing. They exhibit a tunable noise bias yielding an exponential suppression of bit-flips with the average photon number and a protection against the remaining phase errors can be ensured by a simple repetition code. We here quantify the cost of a repetition code and provide a valuable guidance for the choice of a large scale architecture using cat qubits by realizing a performance analysis based on the computation of discrete logarithms on an elliptic curve with Shor's algorithm. By focusing on a 2D grid of cat qubits with neighboring connectivity, we propose to implement two-qubit gates via lattice surgery and Toffoli gates with off-line fault-tolerant preparation of magic states through projective measurements and subsequent gate teleportations. All-to-all connectivity between logical qubits is ensured by routing qubits. Assuming a ratio between single-photon and two-photon losses of 10−5 and a cycle time of 500 nanoseconds, we show concretely that such an architecture can compute 256-bit elliptic curve logarithm in 9 hours with 126133 cat qubits. We give the details of the realization of Shor's algorithm so that the proposed performance analysis can be easily reused to guide the choice of architecture for others platforms.
Shor's algorithm is one of the most promising applications of quantum computers. However, since ∼106 physical qubits are believed to be required for established approaches, the algorithm will need to be distributed across many modules. In this paper, we provide a distributed compilation of Shor's algorithm on a modular atomic processor. We present an end-to-end compilation and optimization strategy that focuses on the interplay between the inter-module communication and the intra-module clock rate. With a half-million-qubit modular atomic processor with a communication rate of 105 Bell pairs per second and a measurement time of 1 ms in a CPU-inspired architecture, we demonstrate that 2048-bit RSA integers can be factored in only 16\% more time than a single-module architecture. Our work presents the first end-to-end analysis and simulation of large-scale integer factorization on modular atomic hardware and it provides a blueprint for the future design of other large-scale modular algorithms.
One of the strengths of our recently proposed Walking Cat Architecture for a trapped-ion quantum computer is that it is straightforward to extend and optimize for a specific application. As a proof-of-concept, here we present such optimizations for solving the 256-bit elliptic curve discrete logarithm problem (ECDLP) on secp256k1, which is the elliptic curve used by blockchain technologies such as Bitcoin, using Shor's algorithm. We optimize the circuits from Schrottenloher's recent work and arrive at a logical quantum circuit for solving the ECDLP using about 1450 qubits and 40⋅106 Toffoli gates, with a rigorous lower bound on the logical-level success probability that holds with confidence at least 1−2−128. Using our compilation toolchain with manual optimization of the logical layout and integrated routing, we produce estimates for the logical measurement depth and the required number of physical qubits by compiling all components to measurement schedules that obey the architectural constraints. A key ingredient is a fast CCZ magic-state factory and a depth-one CCZ state injection, reducing the execution time of CCZ gates by a factor of 31. We increase the logical-measurement parallelism using non-overlapping cat-based measurements in parallel, and we leverage the recently proposed logical CliNR protocol to speed up Clifford operations. To reduce the qubit overhead, we introduce a more efficient loss correction protocol, design a layout that allows us to recycle the CliNR ancilla qubits, and provision reusable cat-state resources according to the circuit's peak measurement parallelism. All results and optimizations combined, we conclude that a trapped-ion quantum computer based on our architecture can solve the ECDLP on secp256k1 in approximately 25.7 days using 19,397 physical qubits with an estimated success probability of 63%.
Planning the transition to quantum-safe cryptosystems requires understanding the cost of quantum attacks on vulnerable cryptosystems. In Gidney+Ekerå 2019, I co-published an estimate stating that 2048 bit RSA integers could be factored in eight hours by a quantum computer with 20 million noisy qubits. In this paper, I substantially reduce the number of qubits required. I estimate that a 2048 bit RSA integer could be factored in less than a week by a quantum computer with less than a million noisy qubits. I make the same assumptions as in 2019: a square grid of qubits with nearest neighbor connections, a uniform gate error rate of 0.1%, a surface code cycle time of 1 microsecond, and a control system reaction time of 10 microseconds. The qubit count reduction comes mainly from using approximate residue arithmetic (Chevignard+Fouque+Schrottenloher 2024), from storing idle logical qubits with yoked surface codes (Gidney+Newman+Brooks+Jones 2023), and from allocating less space to magic state distillation by using magic state cultivation (Gidney+Shutty+Jones 2024). The longer runtime is mainly due to performing more Toffoli gates and using fewer magic state factories compared to Gidney+Ekerå 2019. That said, I reduce the Toffoli count by over 100x compared to Chevignard+Fouque+Schrottenloher 2024.
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.