Case Study 1: Pricing RSA-2048

DataField.Dev

Case Study 1: Pricing RSA-2048

The question everyone asks

When will a quantum computer break RSA?

It is the most-asked question in the field and the worst-answered. The usual replies are a year ("2030"), a qubit count ("4,000 qubits"), or a shrug. All three are wrong in the same way: they answer with a single number a question whose answer is a trade-off surface.

The resource estimator turns it into something you can compute. This case study does that, and then finds something in the output that contradicts the lesson §15.8 just taught.

Setting up the input

The estimator takes logical counts, not code. For Shor's algorithm on an $n$-bit modulus, the standard resource scaling is roughly

$$\text{Toffolis} \approx 0.3\,n^3, \qquad \text{logical qubits} \approx 3n, \qquad \text{1 Toffoli} = 4\ T\ \text{gates}$$

Chapter 23 derives where these come from; for now they are inputs.

def shor_counts(n):
    toffoli = 0.3 * n**3 + 0.0005 * n**3 * math.log2(n)
    return {"numQubits": int(3*n + 0.002 * n * math.log2(n)),
            "tCount": int(4 * toffoli),
            "measurementCount": int(3*n), ...}

The estimator is only as good as the counts you feed it. That caveat is the whole reason this case study ends where it does.

The answer

   RSA bits   logical qubits          T count   physical qubits        runtime
        256              772       20,401,094         2,429,840        3.4 min
        512            1,545      163,477,192         5,069,814       29.4 min
       1024            3,092    1,309,965,025        11,168,726       4.2 hours
       2048            6,189   10,496,900,071        24,937,084       1.5 days

RSA-2048: about 25 million physical qubits, running for a day and a half.

Three things are worth extracting before the interesting part.

The T count is astronomical. Ten billion T gates. Chapter 11 §11.4 established that T gates are what make a circuit classically hard; here is what "hard" costs when you have to actually build it. Every one of those ten billion gates consumes a distilled magic state.

The scaling is brutal but not hopeless. Going from 1024 to 2048 bits roughly doubles the qubit count and multiplies the runtime by about 8. Doubling your key length does not double the attacker's problem; it multiplies it by roughly eight in time.

"4,000 qubits" was never the right number. The logical qubit count for RSA-2048 is 6,189 — close to the figure people quote. The physical count is four thousand times larger. Quoting the logical number as though it were a hardware requirement is the single most common error in public discussion of this question.

The cross-check

An estimate you cannot check against anything is a number, not a result.

Gidney and Ekerå (2021), "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits," arXiv:1905.09749.

20 million qubits, 8 hours. Against our 24.9 million qubits, 1.5 days.

Same order of magnitude on both axes, from a completely independent code path — their hand analysis versus this estimator's model — which is about as good as agreement gets in this business. The residual difference is real and explicable: their construction uses optimizations this crude Toffoli-count model does not capture, and they assume a somewhat different error rate.

The agreement validates the method, not the number. What we have established is that the estimator produces figures consistent with careful published analysis, so it can be trusted for the comparative work in the rest of this case study.

The result that reverses §15.8

Now the same circuit across four assumed qubit technologies:

  qubit technology         physical qubits      runtime    % T factories
  qubit_gate_ns_e3              24,937,084     1.5 days              3%
  qubit_gate_ns_e4               5,894,900    17.5 hours             4%
  qubit_maj_ns_e4               41,013,716     6.6 days             55%
  qubit_maj_ns_e6                3,124,564     2.7 days              2%

Look at the last column.

§15.8 measured that T factories were 93% of a small circuit's machine, and 98.6% at ten T gates. The lesson drawn was that magic state distillation dominates fault-tolerant cost.

Here, at ten billion T gates, factories are 3%.

That is not a contradiction, and working out why is the most useful thing in this chapter.

Why the fraction inverts

A T factory is a fixed-size piece of hardware that produces magic states at some rate. Whether it dominates your qubit budget depends on the ratio of two things: how many factories you need running in parallel, and how big your algorithm's own footprint is.

Small circuit: 2 logical qubits → 882 physical qubits of algorithm. Even one factory (2,000 qubits) is more than twice the entire algorithm. Factories dominate at 93%.

RSA-2048: 6,189 logical qubits → roughly 24 million physical qubits of algorithm. The T gates arrive over a day and a half, so a modest number of factories, reused continuously, keeps up. Factories are 3%.

$$\text{factory fraction} \;\sim\; \frac{(\text{factories needed in parallel}) \times (\text{factory size})} {\text{algorithm footprint}}$$

Long runtimes amortize factories; large registers dwarf them. RSA-2048 has both.

The generalizable error: §15.8's table measured a real effect at one scale and invited a conclusion that does not survive extrapolation. "T factories dominate" is true for small circuits and false for large ones, and nothing in the small-circuit data announces which regime you are in.

A measurement taken at one scale is evidence about that scale. This book has now hit that three times — Chapter 10's routing overhead that grew nonlinearly, Chapter 11's MPS timing that reversed with entanglement, and now this.

The technology comparison, read properly

qubit_maj_ns_e4 is the outlier: 41 million qubits, 6.6 days, and 55% factories. Worse on every axis than the superconducting-style e3 assumption despite Majorana qubits having attractive properties in principle.

The reason is in that 55%. At a $10^{-4}$ Majorana error rate the distillation is expensive enough that factories become a large fraction again — the small-circuit regime, reached from a different direction. Improve to e6 and the factory fraction collapses to 2% and the machine shrinks by 13×.

The physical error rate remains the dominant parameter — §15.8's conclusion survives intact, and it is the one that generalizes.

What this means for the original question

When will a quantum computer break RSA?

The honest answer is a surface, not a date, and here is its shape:

~25 million physical qubits at today's better error rates ($10^{-3}$), running a day and a half.
~6 million at $10^{-4}$ — a factor of four from one order of magnitude in hardware quality.
Largest devices today: ~1,000 physical qubits, with no error correction at scale.

That is a gap of four to five orders of magnitude in qubit count, and closing it is a manufacturing and fidelity problem rather than an algorithmic one. Shor's algorithm has been known since 1994; what is missing is the machine.

And the leverage is clear from the table: improving the physical error rate is worth more than adding qubits, because code distance enters the qubit count quadratically. A hardware roadmap that promises a million qubits at $10^{-3}$ is a worse road to RSA than one promising a hundred thousand at $10^{-5}$.

🔬 What this case study does not establish. That RSA is safe for any particular number of years. The estimate assumes today's error-correction schemes and a textbook Shor construction; both improve. Gidney and Ekerå's own figure dropped by more than an order of magnitude from earlier estimates, entirely through better constructions rather than better hardware.

The number to watch is not the calendar. It is the physical error rate, and secondarily the published logical-cost constructions. Both move, and one of them moves the answer quadratically.

For what to actually do about it, see Chapter 38 on post-quantum cryptography — where the operative fact is that data captured today can be decrypted later, which makes the migration deadline earlier than the machine.

The lessons

Answer resource questions with a surface, not a number. Physical qubits, runtime, and error rate trade against each other, and any single figure has silently fixed two of the three.

Distinguish logical from physical qubit counts, always. 6,189 versus 25 million for the same algorithm. The public conversation about this question is mostly people quoting the first number and hearing the second.

Cross-check estimates against independent analysis. Our 24.9M/1.5 days against a published 20M/8 hours validates the method, which is what licenses the comparative work.

A measurement at one scale is evidence about that scale. T factories are 93% of a small machine and 3% of a large one. Both measurements are correct; the conclusion "factories dominate" is not.

And the parameter that dominates is fidelity, not size. It survives every scale in this chapter, which is exactly what makes it worth acting on.

Reproduce it: code/example-05-resource-estimation.py and the t_count_sweep function in code/project-checkpoint.py.