From Logical to Physical Qubits: The Surface-Code Cost of a Real RSA Break

The unnerving thing about the quantum threat to public-key cryptography is that the hard part is already solved on paper. The algorithm that factors integers is short and proven. What does not yet exist is a machine that can run it, and the reason is entirely about errors. Physical qubits decohere and misfire at rates that would derail a cryptographic computation long before it produced an answer, so the algorithm must be run not on physical qubits but on logical qubits — abstractions built from many physical ones and continuously repaired by quantum error correction. This article follows that construction from the noisy hardware up to a concrete resource figure, so the threat can be read as an engineering target with a measurable distance to go, rather than as an open question.

Why the raw circuit cannot run

Start with the obstacle. A physical qubit in a leading platform fails — decoheres or applies a gate incorrectly — with a probability on the order of one in a thousand per operation, a figure that has improved slowly and is unlikely to reach the vanishing rates a long computation would need. A cryptographically relevant factoring run involves on the order of ten billion elementary quantum operations across thousands of qubits. If each operation independently has even a one-in-a-thousand chance of error, the probability that the whole computation completes without a single fault is effectively zero.

The arithmetic is unforgiving and worth making explicit. The chance that a computation of G gate operations, each with error probability p, suffers no error at all is approximately one minus p times G when p times G is small — but here p times G is enormous, so a fault is a certainty many times over. No amount of clever scheduling repairs this; a computation that must be exact cannot be run on components that are individually unreliable at this scale.

This is precisely the situation classical computing faced and solved with error-correcting codes and reliable-from-unreliable design. The quantum version is harder — you cannot copy an unknown quantum state, and measuring it destroys it — but it exists, and it is the entire bridge between the algorithm and the attack.

The threshold theorem: reliability from unreliability

Quantum error correction encodes one logical qubit — the abstraction the algorithm manipulates — into an entangled block of many physical qubits, in such a way that the most likely small errors can be detected and corrected without ever measuring, and thereby destroying, the encoded information. Detection works by repeatedly measuring carefully chosen joint parities (stabilizers) that reveal that an error occurred and where, while leaving the logical state untouched.

The pivotal result is the threshold theorem: there exists a critical physical error rate, the threshold, below which increasing the size of the code drives the logical error rate down as fast as you like. If your physical qubits are better than the threshold, you buy reliability by adding qubits; if they are worse, adding qubits makes things worse, because you are correcting slower than you are erring. Everything therefore hinges on being on the right side of one number.

This reframes the entire quantum-threat question. It is not 'will the algorithm work' — it will — but 'are the physical qubits below the threshold, and by how much,' because that margin sets how many physical qubits each logical qubit costs.

The surface code, and what a distance buys

The leading practical code is the surface code of Fowler and colleagues (2012). It arranges physical qubits on a two-dimensional grid and uses only nearest-neighbour interactions — a decisive engineering advantage, since long-range connectivity is exactly what physical hardware struggles to provide. Its threshold is comparatively high, near one percent, which real devices are beginning to approach, and its correction procedure is a well-understood classical decoding problem run in real time.

The key knob is the code distance, written d: loosely, the number of physical errors that must conspire to cause an undetected logical error. A distance-d surface code suppresses the logical error rate exponentially in d — each increase of the distance by two multiplies the logical error rate by a factor set by how far below threshold you operate. To run a computation of ten billion operations without a logical fault, you need a logical error rate below roughly one in ten billion, which in turn fixes the distance you must build.

The cost of that distance is quadratic in physical qubits. A distance-d surface code patch uses on the order of two d-squared physical qubits to encode a single logical qubit, plus the ancillary qubits and time that the repeated stabilizer measurements consume. Distance and overhead are therefore the two dials, and they are coupled: the worse your physical qubits relative to threshold, the larger the distance you need, and the overhead grows as its square.

Magic-state distillation: the hidden majority of the cost

A surface code natively and cheaply performs only a restricted set of operations (the Clifford gates), which by themselves are not universal and, in fact, are classically simulable. To run Shor's algorithm you need a non-Clifford gate — conventionally the T gate — and the surface code cannot apply it directly. The standard route is magic-state distillation: prepare many noisy copies of a special resource state, then consume them in a protocol that outputs a smaller number of much cleaner copies, which are then teleported into the computation to enact the T gate.

Distillation is expensive, and in realistic estimates it dominates the qubit and time budget. A cryptographic run consumes on the order of billions of T gates, each requiring a distilled magic state, so the machine must contain many parallel distillation factories occupying a large fraction of the total qubits. The lesson is that the headline logical-qubit count of the algorithm understates the machine, because most of the hardware is not holding the computation's data — it is manufacturing the magic states that make the computation universal.

This is why a naive count 'Shor needs a few thousand logical qubits' is misleading about the physical machine. The physical overhead is dominated not by the data qubits but by error-correction distance and distillation throughput together.

Composing the pieces: a concrete RSA-2048 figure

Putting the machinery together gives a concrete, if hardware-dependent, number. The resource study of Gidney and Ekerå (2021) estimates that factoring a 2048-bit RSA modulus would require on the order of twenty million noisy physical qubits, assuming a physical error rate somewhat below the surface-code threshold, running for on the order of eight hours. The estimate composes exactly the elements above: a few thousand logical qubits for the algorithm, a code distance large enough to survive ten-billion-operation circuits, the two-d-squared overhead per logical qubit, and extensive magic-state distillation for the non-Clifford gates.

Two features of that figure matter more than its precise value. First, it is an engineering estimate under stated assumptions, not a law — better physical qubits shrink the distance and therefore the overhead superlinearly, while worse qubits inflate it. Second, twenty million high-quality physical qubits is far beyond current devices, which number in the hundreds to low thousands, so the estimate encodes a large but finite gap that hardware progress is steadily narrowing.

The honest reading is that the attack is a matter of scaling and error rates, not of undiscovered mathematics. That is the difference between a threat you can plan against and one you cannot: the variables are physical qubit count and error rate, both measurable and both improving on a trajectory that can be watched.

What to actually watch

For anyone tracking the threat rather than building the machine, the composition above tells you which quantities are load-bearing. The single most important is the physical two-qubit gate error rate relative to the surface-code threshold, because it sets the required distance and therefore the qubit overhead nonlinearly. A device that pushes its error rate further below threshold does not just improve linearly; it lowers the distance, and the overhead falls as the square. Progress on error rate is therefore worth more than an equivalent-looking increase in qubit count.

The second quantity is the total count of high-quality physical qubits with the connectivity and speed the surface code assumes — not qubits in isolation, but qubits good enough and numerous enough to sustain the distance and the distillation throughput simultaneously. Headlines counting physical qubits without their error rates and connectivity are close to meaningless for this purpose; the meaningful metric is logical qubits sustained at a given logical error rate.

None of this changes the algorithm, which is why the threat is best understood as a moving engineering frontier. The prudent response is to treat the crossover — when a machine of sufficient scale and quality is plausible within the shelf-life of your secrets — as the planning horizon, and to migrate long-lived protections before that horizon rather than after.

• Physical two-qubit error rate vs the ~1% surface-code threshold (sets distance, overhead ~ its square).
• Sustained logical qubits at a target logical error rate (not raw physical qubit headlines).
• Magic-state distillation throughput (dominates the qubit budget for non-Clifford gates).
• Cycle time and decoder latency (set wall-clock time for a fixed circuit depth).

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

quantum_watch:
  track:
    - physical_2q_error_rate
    - ratio_to_surface_code_threshold
    - sustained_logical_qubits
  migration_trigger:
    logical_qubits_plausible_within: data_shelf_life_years
  action_when_triggered: migrate_long_lived_secrets_to_pqc
audit:
  data_shelf_life_years: required

Glossary

Physical qubit

A real, noisy two-level quantum system on hardware, failing at a nonzero rate per operation.

Logical qubit

An error-corrected qubit encoded across many physical qubits, on which the algorithm actually runs.

Threshold theorem

The result that below a critical physical error rate, larger codes drive the logical error rate arbitrarily low.

Surface code

A 2D nearest-neighbour stabilizer code with a high (~1%) threshold and logical error suppressed exponentially in the code distance.

Code distance (d)

The number of physical errors that must combine to cause an undetected logical error; sets both suppression and ~2d^2 overhead.

Magic-state distillation

A protocol producing clean resource states from many noisy ones to enact non-Clifford (T) gates a surface code cannot apply directly.

References

1. Fowler, Mariantoni, Martinis & Cleland, Surface codes: Towards practical large-scale quantum computation (Phys. Rev. A, 2012; arXiv:1208.0928)
2. Gidney & Ekerå, How to factor 2048-bit RSA integers in 8 hours using 20 million noisy qubits (Quantum, 2021; arXiv:1905.09749)
3. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (SIAM J. Comput., 1997)
4. Grover, A Fast Quantum Mechanical Algorithm for Database Search (STOC, 1996)
5. Mosca, Cybersecurity in an era with quantum computers: will we be ready? (IEEE Security & Privacy, 2018; arXiv:1512.06466)