Why quantum error correction — not qubit count — decides when RSA and ECC fall

Quantum computing is usually discussed in terms of a single number: how many qubits a machine has. For cryptanalysis, that number is misleading. The security of RSA and elliptic-curve cryptography (ECC) will not be broken by raw qubit count, but by how efficiently an algorithm can be compiled into fault-tolerant operations, and how much overhead quantum error correction (QEC) adds on top. The distance between a headline logical-qubit figure and a working attack machine is measured almost entirely in error-correction overhead — and that overhead has been falling fast.

This note traces the chain from Shor’s algorithm to a physical chip, shows why the T-gate and magic-state bottleneck dominates the cost, and reviews the sharply declining resource estimates for breaking RSA-2048 and 256-bit ECC.

Shor’s algorithm put public-key cryptography on a clock

The security of today’s digital infrastructure rests largely on public-key cryptography, whose hardness assumptions are integer factorisation (RSA) and the discrete-logarithm problem on elliptic curves (ECC). On classical hardware these are intractable at the key sizes in use. Peter Shor showed in 1994 that a sufficiently capable quantum computer solves both efficiently.

Germany’s Federal Office for Information Security (BSI) tracks this threat in its recurring study Entwicklungsstand Quantencomputer. Version 2.2, published in December 2025, concludes that a cryptographically relevant quantum computer (CRQC) appears realistic by 2040 — a conservative estimate, with the caveat that a disruptive result in hardware or error correction could bring that date inside a decade. The “store now, decrypt later” risk is why the migration cannot wait for the machine to exist: data encrypted today can be harvested and decrypted once a CRQC is available. The BSI has since translated this into hard deadlines — RSA and ECC for key establishment and encryption phased out by the end of 2031, classical signatures permitted until the end of 2035. BSI President Claudia Plattner has called the migration “alternativlos” — without alternative.

An efficient encoding is not a fast algorithm

It is tempting to assume that a small logical-qubit count means a near-term machine. A business risk model, for instance, encodes very compactly — one risk item to one qubit, one probability to one rotation gate, one correlation to one CNOT — so a real instance might look like only 100–200 qubits and a few hundred gates. That is almost within reach of today’s noisy hardware. But without a genuine quantum algorithm on top, this compact encoding offers no speedup over classical methods. Only when Quantum Amplitude Estimation is applied does the machine actually run faster — and it buys that quadratic advantage by adding gates. Accuracy translates directly into gate count, and gate count translates directly into the need for error correction.

The same logic governs cryptanalysis, only more severely. Shor’s algorithm is not gate-cheap. Its arithmetic — modular multiplication, exponentiation, elliptic-curve point addition — decomposes into enormous numbers of high-precision rotations and Toffoli gates. Those gates cannot survive on bare hardware.

Native gates run out of runway without error correction

Every processor has its own native gate set — the operations the hardware performs directly. IBM’s Heron devices expose Pauli-X, √X, Z-rotation and CNOT/CZ; IQM’s architecture exposes X, Y and CZ. Run uncorrected, these gates limit depth brutally. Current one- and two-qubit gate and SPAM fidelities sit around 99.9%. Even at that 0.1% error rate, a circuit of roughly 1,000 gates succeeds only about 37% of the time (0.999^1000 ≈ 0.37). Shor’s algorithm against RSA-2048 or ECC-256 needs billions of Toffoli gates. Bare hardware cannot execute it — at any qubit count. For cryptanalysis, fault-tolerant error correction is not optional; it is the entire game.

The T-gate and magic-state bottleneck

The standard universal fault-tolerant gate set combines Clifford gates with the T-gate. Clifford gates are comparatively easy to make error-resilient. The T-gate is not: it requires magic states — a name that signals the difficulty.

There is no way around fault-tolerant T-gates. Any arbitrary rotation must be decomposed into a sequence of Clifford and T-gates, and precision has a price. The Solovay–Kitaev theorem shows that approximating a rotation to error ε requires a number of T-gates scaling as O(log(1/ε)). Higher precision means longer sequences, more magic states, more physical qubits, and lower tolerable error rates.

Producing those magic states is the dominant cost. Magic-state distillation refines many low-fidelity states into fewer high-fidelity ones, consuming large numbers of physical qubits and many operation cycles. In modern estimates, the memory dedicated to magic-state production is a substantial fraction of the entire machine. The full chain runs:

1. Cryptographic problem — factor an RSA modulus, or solve the elliptic-curve discrete logarithm.
2. Quantum algorithm (Shor) — expressed as reversible arithmetic: Toffoli gates and high-precision rotations.
3. Compiler & gate-set decomposition — arbitrary rotations broken into fault-tolerant Clifford + T sequences.
4. Magic-state distillation / cultivation — significant hardware dedicated to producing the T-states.
5. Hardware control & execution — control electronics drive the physical gates at a fixed cycle rate.

Nearly every recent reduction in the cost of attacking RSA and ECC comes from this stage — not from better qubits.

RSA-2048: from 20 million qubits to under one million

The most-cited estimate for factoring RSA-2048 came from Gidney and Ekerå in 2019: roughly 20 million noisy physical qubits and about 8 hours of runtime, assuming a square grid of nearest-neighbour qubits, a uniform 0.1% gate error rate, a 1-microsecond surface-code cycle and a 10-microsecond control reaction time. The BSI study uses this figure as its reference for the scale of the required machine.

In May 2025, Gidney revised his own estimate down by more than an order of magnitude. How to factor 2048-bit RSA integers with less than a million noisy qubits estimates RSA-2048 factored in under one week using fewer than one million noisy qubits — roughly a 20× reduction, on identical hardware assumptions. Nothing about the hardware improved. The reduction is purely algorithmic and error-correction engineering:

The Toffoli count alone dropped more than 100× relative to the Chevignard et al. circuit. The longer runtime is a deliberate space–time trade: fewer factories, more sequential gates. The BSI study notes the same trade explicitly — at a robust 1:10,000 error rate, RSA-2048 needs on the order of a million physical qubits to break in 100 days, but around a billion to break in one hour. Qubits and time are interchangeable through the error-correction layer.

ECC is the easier target — and the estimates are falling faster

At comparable classical security levels, ECC requires fewer qubits than RSA. Roetteler, Naehrig, Svore and Lauter set the reference logical estimate in 2017: solving the discrete logarithm on NIST P-256 needs about 2,330 logical qubits and on the order of 10¹¹ Toffoli gates. Their conclusion was blunt — ECC is an easier target than RSA.

The physical estimates have since collapsed. Litinski (2023) showed 256-bit ECDLP in roughly 50 million Toffoli gates on an active-volume, photonics-inspired architecture — equivalent to several million physical qubits. Then, on 30 March 2026, Google Quantum AI, the Ethereum Foundation and Stanford published Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities. It presents two optimised Shor circuits for the secp256k1 curve behind Bitcoin and Ethereum:

Compiled onto a superconducting surface-code architecture at a 10⁻³ physical error rate, planar degree-four connectivity, a 1-microsecond cycle and a 10-microsecond reaction time, these circuits run in under 500,000 physical qubits and complete in about nine minutes — roughly a 20× reduction over the prior best physical estimate. Executing 70 million Toffolis in nine minutes demands the generation of about half a million T-states per second, which underlines the point: the machine is, in large part, a magic-state factory with some arithmetic attached.

The same paper introduces a distinction that matters for hardware strategy — fast-clock architectures (superconducting, photonic) versus slow-clock ones (neutral atom, ion trap). Two machines with identical logical requirements can differ by orders of magnitude in wall-clock attack time depending on cycle rate. A resource estimate is meaningless unless bound to a specific hardware profile.

The gap between estimate and machine

These falling numbers should not be read as an imminent break. No CRQC exists. As of 2026 the largest devices offer roughly 1,000–1,200 physical qubits (IBM’s 1,121-qubit Condor; Atom Computing’s 1,180-qubit array), and demonstrated logical-qubit counts sit in the tens to around a hundred — Google’s below-threshold 105-qubit Willow chip, 48 logical qubits on Quantinuum’s Helios, up to 96 logical qubits in a Harvard–MIT–QuEra system. Every serious 2026 source, including the Google whitepaper, states plainly that a cryptographically relevant machine does not yet exist.

What has changed is the shape of the target. The requirement is no longer “twenty million near-perfect qubits.” It is “a few hundred thousand physical qubits, wired for fast surface-code cycles, feeding a very large magic-state factory.” That is a materially different — and more concrete — engineering brief, and it is why the timeline compresses even when hardware stands still.

Where the real work is

Two conclusions follow. First, the fall in resource estimates is driven overwhelmingly by the error-correction and compilation layers — approximate arithmetic, compact idle-qubit storage, cheaper magic states — not by qubit count. Second, every estimate is conditional on a specific hardware profile, code choice and space–time trade-off. A single headline number obscures more than it reveals.

This is where our work at JoS QUANTUM sits. The path from a cryptographic or financial problem to a running chip passes through the compiler and the QEC layer, and each step must be optimised against real device characteristics — decomposing circuits into fault-tolerant gate sets including magic-state overhead, and producing realistic, per-device figures for physical qubit count, T-count, T-depth, logical error rate and runtime. Resource estimation is not bookkeeping. It is the discipline that determines when a threat becomes real and what hardware makes it real — for cryptanalysis, and equally for quantum finance.