Shor's algorithm compiled on cat qubits: 22 593 qubits for RSA-2048 in 3.14 days

AI summary

Overview

Research area: Quantum computing — resource estimation and fault-tolerant architecture compilation for cryptanalytically relevant quantum algorithms (Shor's algorithm) on superconducting cat qubits.

Technical level: Advanced. The abstract assumes familiarity with Shor's algorithm variants, error-correcting codes (repetition cat codes, LDPC cat codes), magic-state/lookup factories, and physical qubit scheduling on chip layouts.

Scope (one sentence): The paper performs an end-to-end resource estimation — from the mathematical description of Shor's algorithm through logical circuit compilation down to physical-qubit allocation and scheduling on a chip — for factoring RSA-2048, solving ECDLP on secp256k1, and a proposed FFDLP-512 benchmark, using superconducting cat-qubit architectures.

What This Paper Is About

Building a quantum computer large enough to run Shor's algorithm against real cryptographic keys requires knowing, concretely, how many physical qubits are needed, how long the computation would take, and how those qubits would be laid out and operated on an actual chip. The authors take modern versions of Shor's algorithm for three hard problems (factoring, elliptic-curve discrete logs, and finite-field discrete logs) and compile their dominant subroutines all the way down to physical operations on cat-qubit hardware. The goal is a realistic, architecture-aware estimate — including chip layouts and schedules — rather than an abstract qubit count.

Key Contributions

1. End-to-end compilation pipeline for cat qubits. The authors compile Shor's algorithm from its mathematical description down to physical-qubit operations, including qubit allocation and scheduling on a chip layout, for two architectures: one based on repetition cat codes and one based on LDPC cat codes.

2. New and adapted physical primitives for cat qubits. They design a parity-Cnot gate, extend a multi-target Cnot gate to the LDPC-cat architecture, and adapt an active injection procedure to cat qubits.

3. A cat-qubit adaptation of Gidney's 2025 adder. They adapt the adder used in Gidney's 2025 RSA-2048 resource estimate to cat qubits, and combine this with a coarser estimate for the phaseup subroutine plus the factory designs and lookup compilation from the FeMoco resource estimation of Kroell et al.

4. A proposed intermediate benchmark. They introduce FFDLP-512 (finite-field discrete logarithm over a 512-bit field) as a stepping-stone benchmark below the difficulty of RSA-2048 and ECDLP on secp256k1, and give its resource cost.

Main Findings

• RSA-2048 baseline: Factoring RSA-2048 — the configuration compiled in full — requires about 23 000 cat qubits and 3.14 days (the title states 22 593 qubits). This assumes a 1 μs error-correction cycle time, a 10 μs reaction time, circuit-level phase-flip noise with probability p_Z = 5 × 10⁻⁴, and no bit-flips.

• ECDLP on secp256k1: Reusing the compiled operations, solving the elliptic-curve discrete logarithm problem on secp256k1 requires at most 30 000 cat qubits and 1 hour.

• FFDLP-512 benchmark: The proposed intermediate benchmark requires about 6 700 cat qubits and 21 minutes.

• Space–time trade-off: Trading more space for less time, RSA-2048 can be run in 1.25 hours using about 611 000 cat qubits.

• Relaxing the no-bit-flip assumption: The requirement of effectively no bit-flips (a bit-flip time of about 100 years) can be softened to a bit-flip time of about one hour by adding a concatenation layer with a distance-3 bit-flip code — at the cost of RSA-2048 needing about 45 000 cat qubits.

Methodology in Plain English

The authors work as compilers and architects rather than as experimentalists. They start with the textbook-level description of Shor's algorithm for three different cryptographic problems, write out the logical circuits explicitly, and make the trade-offs between circuit variants visible. They then take the most expensive subroutines — the modular adder, the phaseup step, and the magic-state or lookup factories that supply the non-Clifford resources — and translate each into physical operations that a cat-qubit chip can actually perform. Because cat qubits behave differently from transmons, several standard building blocks had to be redesigned: the team invents a parity-Cnot gate, generalizes a multi-target Cnot gate to the LDPC-cat setting, and adjusts an active injection routine. For the adder, they port a recent design from Gidney's 2025 factoring estimate; for the factories and lookup compilation, they borrow from the FeMoco resource estimate of Kroell et al. and treat the phaseup with a coarser estimate. Finally, they place and schedule the resulting physical operations onto concrete chip layouts and read off qubit counts and runtimes under a stated noise model.

Why This Matters

Resource estimates determine whether a cryptographic threat from quantum computers is a decade away or a generation away, and they also determine what hardware has to be built. This paper is distinctive because it goes beyond counting logical qubits: it produces chip layouts and schedules for a specific superconducting technology (cat qubits) and states the noise assumptions explicitly, including what happens when the bit-flip assumption is weakened.

Real-world applications:

• Cryptographic migration planning. Organizations deciding when to retire RSA-2048 and secp256k1 need concrete hardware and time estimates, not just asymptotic claims.

• Hardware architecture roadmap. The comparison between repetition cat codes and LDPC cat codes, and the space–time trade-off (3.14 days at ~23 000 qubits versus 1.25 hours at ~611 000 qubits), informs how a machine would be sized for a given mission.

• Benchmarking intermediate milestones. FFDLP-512 gives the field a smaller, checkable target between today's devices and full RSA-2048.

• Compiler and control-stack development. The gate primitives introduced (parity-Cnot, multi-target Cnot, active injection) are components that experimental groups can attempt to realize.

Industry relevance: cat qubits are pursued by commercial superconducting efforts, and the paper's assumptions — 1 μs error-correction cycles, 10 μs reaction times, phase-flip-dominated noise — are the kind of parameters hardware teams can target or measure against.

Future Directions

• Closing the gap between the full compilation and the estimate. Only the RSA-2048 configuration is compiled in full; the phaseup is handled with a coarser estimate. A fully compiled phaseup, and full compilation of the ECDLP and FFDLP circuits rather than reuse of compiled operations, is the natural next step.

• Validating the new primitives experimentally. The parity-Cnot gate, the LDPC-cat multi-target Cnot extension, and the cat-qubit active injection procedure are proposals whose physical performance under realistic noise remains to be demonstrated.

• Refining the noise model. The main result assumes zero bit-flips; the paper offers one relaxation (distance-3 concatenation at ~45 000 qubits), leaving room to explore other bit-flip regimes and different code concatenations.

• Analogous estimates for other architectures and algorithms. The pipeline of compiling to layouts and schedules could be repeated for other qubit modalities or other cryptanalytic targets, and the FFDLP-512 proposal invites the community to adopt and compare against a common intermediate benchmark.

Target Audience

Researchers and engineers working on fault-tolerant quantum computing architectures, particularly superconducting cat qubits and LDPC codes; quantum-algorithm and compiler specialists interested in end-to-end resource estimation; and cryptographers and security policymakers who need concrete qubit-and-time figures for post-quantum migration planning. Readers without a background in quantum error correction will find the technical sections difficult, though the headline resource numbers are accessible.

Authors’ 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 $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.