Shor's algorithm compiled on cat qubits: 22 593 qubits for RSA-2048 in 3.14 days
Abstract
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.
Related
- Ground-state energy estimation compiled on cat qubits: 7 164 qubits for FeMoco-54 in 23.5 hours
- Resonance Breaking in Noisy Shor's Algorithm
- Imaginarity as a resource in Shor's algorithm
- ECDSA.Fail: Open Autoresearch for Optimizing Elliptic-Curve Point Addition in Shor's Algorithm
- Computing 256-bit elliptic curve discrete logarithms in 26 days on a fault-tolerant trapped-ion quantum computer with 20,000 qubits
BibTeX
@misc{pappalardo2026shors,
title = {{Shor's algorithm compiled on cat qubits: 22 593 qubits for RSA-2048 in 3.14 days}},
author = {Axel Pappalardo and Dahmun Goudarzi and Victor Hertz and Hugo Jacinto and Larissa Kroell and André Schrottenloher and Peter Shanahan and Élie Gouzien and Rémi de la Vieuville and Vivien Londe},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37839},
eprint = {2610.37839},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37839},
}
RIS
TY - UNPB
TI - Shor's algorithm compiled on cat qubits: 22 593 qubits for RSA-2048 in 3.14 days
AU - Axel Pappalardo
AU - Dahmun Goudarzi
AU - Victor Hertz
AU - Hugo Jacinto
AU - Larissa Kroell
AU - André Schrottenloher
AU - Peter Shanahan
AU - Élie Gouzien
AU - Rémi de la Vieuville
AU - Vivien Londe
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.37839
UR - https://arxiv.org/abs/2610.37839
AB - 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 × 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.
ER -