up:: Quantum Computing MOC

Quantum Resource Estimation

Quantum resource estimation is the engineering work of counting exactly what a quantum computer would need, in physical qubits, runtime, and gate operations, to break a specific piece of cryptography at a real key size. It is the proof under the quantum threat timeline, because it turns “a quantum computer will break RSA someday” into concrete, peer-reviewed numbers that move as the engineering improves. The headline figures for RSA-2048 have fallen fast: a 2019 construction put the cost at about 20 million noisy physical qubits running for 8 hours, and a 2025 optimization by the same lead author brought it down to under a million noisy qubits running for under a week. Both estimates assume a machine that does not exist yet, which is why the cryptographically relevant quantum computer is still a research target rather than a threat you can point at today.

Source: Craig Gidney and Martin Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum 5, 433, 2021, arXiv:1905.09749.

The short version:

• Resource estimation answers a precise question: how many physical qubits, how many gate operations, and how much wall-clock time does it take to run Shor’s algorithm against a given key size.
• The most-cited estimate for RSA-2048 is Gidney and Ekerå 2021: about 20 million noisy physical qubits, roughly 6,100 logical qubits, and 8 hours of runtime, assuming a 0.1% gate error rate.
• A 2025 follow-up by Gidney cut that to under a million noisy physical qubits in under a week, using better arithmetic and cheaper error-correction layouts, under the same hardware assumptions.
• A 256-bit elliptic curve needs fewer logical qubits than RSA-2048, so ECDH and ECDSA fall to a smaller quantum machine than RSA of comparable classical strength.
• The physical count matters because these are error-corrected estimates. Breaking cryptography needs logical qubits, and each logical qubit costs a large multiple of physical ones, which is why the physical numbers land in the millions.

Picture the difference between a rough guess and a builder’s bill of materials. Someone can wave a hand and say a bridge across the bay is “possible,” and that tells you almost nothing about when it gets built or what it costs. A structural engineer instead counts the tons of steel, the number of cables, the pour schedule for the concrete, and the months of labor, and that bill of materials is what turns a vision into a plan with a price and a date. Quantum resource estimation is that bill of materials for a quantum attack. It counts the qubits, the gates, and the hours, and because it is grounded in real hardware assumptions, the total tells you honestly how far off the machine is and how fast the distance is closing.

What is quantum resource estimation?

Quantum resource estimation is the practice of computing the concrete cost of running a quantum algorithm on a fault-tolerant machine, expressed in the resources that actually gate feasibility. For a cryptographic attack those resources are the number of physical qubits the machine must hold at once, the number of logical operations in the circuit, the physical error rate the hardware must achieve, and the runtime the whole computation takes end to end. The estimate is not a philosophical claim that an attack is possible in principle. It is a specific accounting of what the hardware has to deliver, tied to stated assumptions you can check.

Source: Craig Gidney and Martin Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum 5, 433, 2021, arXiv:1905.09749.

The reason this discipline exists is that a raw algorithm complexity, the kind Peter Shor published, tells you the attack scales politely with key size but says nothing about the engineering reality. Shor’s algorithm needs error correction to survive a computation deep enough to factor a 2048-bit number, and error correction multiplies the qubit count enormously. A serious estimate has to fold in the error-correction overhead, the magic-state cost of the non-Clifford gates, the layout of qubits on a real chip with limited connectivity, and the reaction time of the classical control system. Those engineering details are the whole difference between a napkin sketch and a number a security team can plan around.

How many qubits does it take to break RSA-2048?

Breaking RSA-2048 takes roughly 6,100 error-corrected logical qubits, and the physical-qubit count that this implies has dropped sharply as the constructions improved. The two anchor estimates, from the same lead author six years apart, bracket the honest current range and both assume a hardware quality that is genuinely hard but not physically impossible.

Estimate	Logical qubits	Physical qubits	Runtime	Gate-error assumption	Source
Gidney and Ekerå, 2021	~6,100	~20 million noisy	8 hours	0.1%	arXiv:1905.09749
Gidney, 2025	not stated	under 1 million noisy	under 1 week	0.1%	arXiv:2505.15917

The 2021 paper is the one most people cite, and its full title carries the headline: “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits.” It assumes a square grid of superconducting qubits with nearest-neighbor connections, a uniform physical gate error rate of 0.1%, a surface-code cycle time of one microsecond, and it costs the factoring at about 0.3 n^3 Toffoli gates for an n-bit modulus. Those are the details that make the 20-million figure a defensible number rather than a guess.

Source: Craig Gidney and Martin Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum 5, 433, 2021, arXiv:1905.09749.

The 2025 paper keeps every one of those hardware assumptions identical and still cuts the qubit count by more than twenty times. Its abstract states the result plainly: “I estimate that a 2048 bit RSA integer could be factored in less than a week by a quantum computer with less than a million noisy qubits,” under “the same assumptions as in 2019: a square grid of qubits with nearest neighbor connections, a uniform gate error rate of 0.1%, a surface code cycle time of 1 microsecond, and a control system reaction time of 10 microseconds.” The reduction came from algorithmic and error-correction advances, not from assuming better hardware, which is the point worth reading carefully.

Source: Craig Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits,” 2025, arXiv:2505.15917.

Why did the estimate drop from 20 million to under a million qubits?

The estimate fell because researchers found cheaper ways to do the same computation, not because anyone built better qubits. The 2025 paper credits three specific advances that each attacked a different part of the cost. Approximate residue arithmetic, from Chevignard, Fouque, and Schrottenloher in 2024, reduced the number of logical operations the factoring circuit needs. Yoked surface codes, from Gidney, Newman, Brooks, and Jones in 2023, packed idle logical qubits into far less space while they wait their turn. And magic state cultivation, from Gidney, Shutty, and Jones in 2024, shrank the footprint of the magic-state machinery that supplies the non-Clifford gates, which had dominated the earlier space budget.

Source: Craig Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits,” 2025, arXiv:2505.15917.

This is the single most important thing to understand about resource estimation, and it cuts in a direction that surprises people. Bigger keys do not save vulnerable cryptography, because the estimates keep shrinking on the attacker’s side even while the hardware stays fixed. A security team cannot bank on the 20-million figure as a comfortable buffer, because the number that mattered in 2019 was already stale by 2025, and the same class of improvements will keep arriving. The moving target belongs in the risk model as a trend, which is exactly why Mosca’s theorem plans around lead time rather than a single forecast date.

What did Regev’s 2023 factoring algorithm change?

Regev’s 2023 result was the first asymptotic improvement to the quantum circuit for factoring since Shor published in 1994, and it reinforces the lesson that the estimate is a moving research target rather than a fixed wall. Oded Regev showed that an n-bit integer can be factored by running a quantum circuit of about Õ(n^{3/2}) gates roughly √n + 4 times, followed by classical post-processing, which lowers the asymptotic gate count per run compared to Shor’s circuit at the cost of many more circuit repetitions. A space-efficiency follow-up by Seyoon Ragavan and Vinod Vaikuntanathan then gave a variant that uses about O(n log n) qubits and O(n^{3/2} log n) gates and tolerates a constant fraction of the runs being corrupted by noise, combining Regev’s gate efficiency with roughly Shor-like space.

Source: Oded Regev, “An Efficient Quantum Factoring Algorithm,” 2023, arXiv:2308.06572.

Source: Seyoon Ragavan and Vinod Vaikuntanathan, “Space-Efficient and Noise-Robust Quantum Factoring,” CRYPTO 2024, 2023, arXiv:2310.00899.

The honest reading matters as much as the result. These are asymptotic improvements in the big-O sense, and Regev himself notes it isn’t yet clear whether the algorithm leads to better physical implementations in practice, so this line of work is not a near-term threat multiplier that moves the arrival date closer. The concrete resource numbers a security team should plan around still come from the error-corrected engineering estimates in the Gidney and Ekerå tradition, where the fixed hardware assumptions and full error-correction accounting live. What Regev’s family of results adds is direction rather than a new headline figure: the theoretical frontier of factoring is still moving after three decades, which is exactly why the responsible plan treats the estimate as a trend to track rather than a settled number.

How many qubits does it take to break elliptic-curve cryptography?

Breaking a 256-bit elliptic curve takes roughly 2,330 logical qubits, which is fewer than RSA-2048 needs, so elliptic-curve cryptography falls to a smaller quantum machine even though its keys are shorter. The most-cited peer-reviewed estimate for the elliptic-curve discrete logarithm comes from Roetteler, Naehrig, Svore, and Lauter in 2017, and it counts the logical qubits and the Toffoli-gate depth for computing discrete logarithms on curves of cryptographic size.

Source: Martin Roetteler, Michael Naehrig, Krysta M. Svore, Kristin Lauter, “Quantum resource estimates for computing elliptic curve discrete logarithms,” 2017, arXiv:1706.06752.

The lesson for a migration plan is that shorter keys are not the safer bet against a quantum attacker. Elliptic-curve systems earned their short keys by resisting the classical index-calculus attacks that force finite-field cryptography to use large moduli, but that classical advantage gives no protection against Shor’s algorithm. Because the elliptic-curve group is smaller, the quantum circuit that solves its discrete logarithm is smaller too, so ECDH and ECDSA are cracked by a machine that could not yet touch RSA-2048. A team that migrated from RSA to elliptic curves for the efficiency and assumed it bought quantum headroom has the ordering exactly backward.

Why do these estimates count physical qubits in the millions?

The estimates land in the millions of physical qubits because every one of the few thousand logical qubits in the attack is itself built from a large block of physical qubits running error correction. A logical qubit is not one especially good piece of hardware. It is one reliable qubit assembled by spreading a single quantum state across a grid of physical qubits and constantly measuring most of them to catch and fix errors before they accumulate. The full treatment of that gap lives in Logical vs Physical Qubits, and it is the reason a “6,100 logical qubit” requirement becomes a “20 million physical qubit” machine.

The overhead is steep because a factoring computation is enormously deep, running billions of operations in sequence, and a single uncorrected error partway through corrupts the whole result. To survive that depth, the error correction has to drive the logical error rate far below the physical one, which the threshold theorem says is possible only when the hardware is already good enough and only at the cost of heavy redundancy. Under the leading surface-code scheme, one logical qubit reliable enough for a hard algorithm takes on the order of a thousand or more physical qubits, and the deeper the computation, the more you pay per logical qubit.

Source: Austin G. Fowler, Matteo Mariantoni, John M. Martinis, Andrew N. Cleland, “Surface codes: Towards practical large-scale quantum computation,” Physical Review A 86, 032324, 2012, arXiv:1208.0928.

How does resource estimation relate to the threat timeline?

Resource estimation is the raw material that the threat timeline and Mosca’s theorem are built on, because it is what converts hardware progress into a statement about cryptographic risk. A qubit-count press release tells you a machine got wider. A resource estimate tells you how wide and how clean the machine has to be before the attack actually runs, so comparing the two is how you judge whether a headline moved the clock at all. As of 2026 the largest processors hold roughly a thousand or a few thousand noisy physical qubits, while the estimates call for hundreds of thousands to millions of clean ones organized into thousands of logical qubits, so the distance is still vast and every axis of it is an open engineering problem.

The practical consequence is that resource estimation drives a planning decision. Because the numbers keep falling and the hardware keeps improving, the responsible read is to plan around lead time. Encrypted data captured today under harvest now, decrypt later is exposed the moment a CRQC exists, a full migration across a large estate takes years, and there is no patch for data already collected. The estimates tell you the machine is not here in 2026, and the same estimates, by dropping so fast, tell you not to treat that as a reason to wait.

Common misconceptions

• “The 20-million-qubit estimate is the current number.” It is the 2019 construction and has already been superseded. The same lead author’s 2025 optimization brought it under a million physical qubits under identical hardware assumptions, and the trend is downward.
• “Bigger keys buy safety because they push the qubit count up.” Larger keys defend against classical attacks, not against Shor’s algorithm, whose cost grows only polynomially. Meanwhile the estimates for a fixed key size keep shrinking as the algorithms improve, so a bigger key is not a durable hedge.
• “Elliptic-curve crypto is safer against quantum because its keys are shorter.” The opposite is true. A 256-bit curve needs fewer logical qubits than RSA-2048, so ECDH and ECDSA fall to a smaller quantum machine than RSA of comparable classical strength.
• “A million-qubit chip would break RSA.” Only if those are error-corrected logical qubits or clean enough physical qubits to build thousands of logical ones. Today’s qubits are noisy physical qubits, and a million of them at current error rates could not run the attack.
• “Resource estimates are just guesses.” They are peer-reviewed engineering with stated assumptions you can audit: a specific gate error rate, a specific chip layout, a specific cycle time, and a specific gate count. That is what separates them from a hand-waved timeline.

Questions people ask

How many qubits does it take to break RSA-2048? Roughly 6,100 logical qubits in the most-cited peer-reviewed estimate, realized as about 20 million noisy physical qubits in a 2021 construction (arXiv:1905.09749) and under a million noisy physical qubits in a 2025 optimization (arXiv:2505.15917). The physical number depends heavily on the construction and keeps falling.

How long would the attack take? The 2021 estimate put the runtime at 8 hours; the 2025 estimate, with far fewer qubits, put it at under a week. Both assume a surface-code cycle time of one microsecond and a machine running the full deep circuit end to end.

Why is the physical-qubit number so much larger than the logical one? Because each logical qubit is an error-corrected assembly of many physical qubits. Under the surface code, one logical qubit reliable enough for a factoring circuit costs on the order of a thousand or more physical qubits, so a few thousand logical qubits becomes millions of physical ones (arXiv:1208.0928).

Does breaking elliptic-curve cryptography take fewer qubits than RSA? Yes. A 256-bit elliptic curve needs about 2,330 logical qubits (arXiv:1706.06752), fewer than RSA-2048, so ECDH and ECDSA fall to a smaller quantum machine despite using shorter keys.

If the estimate keeps dropping, does that mean the attack is close? It means the distance is closing from the software side even while the hardware lags, so the arrival date is uncertain rather than near. As of 2026 no machine has the millions of clean qubits the estimates require, which is why Mosca’s theorem plans around lead time instead of a single date.

Should I trust one estimate as the definitive number? No. Treat the estimates as a moving range with stated assumptions, and track the trend rather than any single figure. The honest planning input is that RSA-2048 sits somewhere between the 2021 and 2025 constructions today, and the number will keep falling as the engineering improves.

Last verified 2026-07-14 · Maintained by Addie LaMarr, LaMarr Labs.