4,099 Qubits: The Myth and Reality of Breaking RSA-2048 with Quantum Computers

Cookie policy

Post-Quantum, PQC, Quantum SecurityQ-Day

4,099 Qubits: The Myth and Reality of Breaking RSA-2048 with Quantum Computers

Marin Ivezic

Follow on X

Send an email

March 5, 2024 15 minutes read

Table of Contents

Update, June 2026: The resource trajectory in this article now extends three rows further. Gidney’s May 2025 surface-code preprint brought RSA-2048 to under one million physical qubits on the same hardware assumptions as the 2019 estimate, a twentyfold reduction from algorithms and error correction alone. By February 2026, the Pinnacle Architecture claimed under 100,000 physical qubits by replacing surface codes with qLDPC codes. A March 2026 neutral-atom study proposed as few as 10,000 atoms under different time-space assumptions. Both are preprints on unbuilt architectures. Only the 2019-to-2025 step is like-for-like (same hardware model, same code); the 2026 drops come from changing the architecture itself, so the five rows should not be read as one smooth trend line. They show that the estimate can move by orders of magnitude from mathematics before a single qubit is added to a real machine, which strengthens the migration case in this article rather than weakening it.

It’s a figure that crops up in countless discussions about quantum computing and cybersecurity: 4,099 qubits. That’s the widely cited number of quantum bits one would need to factor a 2048-bit RSA key using Shor’s algorithm – in other words, the notional threshold at which a quantum computer could crack one of today’s most common encryption standards. The claim has an alluring simplicity: if we could just build a quantum machine with a few thousand perfect qubits, decades of RSA-protected secrets would fall in seconds. But where does this “4,099 logical qubits” figure actually come from, and what does it really mean? The story behind it reveals both how far quantum algorithms have come and how much further quantum hardware needs to go.

The Origin of the “4,099 Logical Qubits” Figure

The magic number 4,099 has its roots in theoretical work from the early 2000s, as researchers began translating Peter Shor’s 1994 factoring algorithm into practical quantum circuit designs. In 2003, computer scientist Stéphane Beauregard showed how to implement Shor’s algorithm using as few qubits as possible. His paper, titled “Circuit for Shor’s algorithm using 2n+3 qubits,” gave a recipe for factoring an n-bit integer with only $$2n + 3$$ quantum bits. For an RSA modulus 2048 bits long, Beauregard’s circuit would need $$2·2048 + 3 = 4,099$$ logical qubits. This was a dramatic reduction from earlier, more naive constructions and quickly became a reference point. In theory, just over four thousand well-behaved qubits, running Shor’s algorithm, could find the prime factors of a 2048-bit number – a task that would take classical supercomputers longer than the age of the universe.

Crucially, Beauregard’s 4,099-qubit figure refers to logical qubits in an ideal quantum computer, essentially assuming qubits that are perfectly stable and error-free. In 2003, and even today, such qubits are purely hypothetical. Beauregard’s result was nonetheless significant: it distilled Shor’s algorithm down to its qubit minimum, showing that quantum factoring didn’t require extravagantly more memory than the size of the number being factored. The paper brought Shor’s factoring algorithm closer to implementation in principle. Ever since, “a few thousand qubits” has been the oft-quoted yardstick for the quantum threat to RSA.

Yet Beauregard’s minimalist approach achieved its low qubit count at the cost of a very large circuit depth (the number of sequential operations). His design requires a series of quantum modular multiplications, additions, and quantum Fourier transforms executed mostly in sequence. The gate count scales on the order of n³ (with some logarithmic factors) – meaning billions of quantum operations for $$n = 2048$$. In a noise-free world, one could carry out those operations given enough time. But real quantum hardware is highly error-prone and qubits can’t maintain quantum states indefinitely. As a result, researchers soon started asking: could we trade more qubits for a shorter runtime to make Shor’s algorithm easier to execute in practice?

Trading Qubits for Speed: Space–Time Optimizations

In the years after 2003, a series of research efforts explored different balances between the number of qubits and the time needed to run Shor’s algorithm. The motivation was simple: quantum error grows with circuit depth, because qubits gradually lose their delicate quantum states (a phenomenon known as decoherence) and each gate operation has some probability of error. If using a few extra qubits can cut the circuit depth significantly, the algorithm might finish before noise ruins the computation. The longer it takes to execute a circuit, the more noise will...