The Threshold Theorem
The threshold theorem is the mathematical result that makes large-scale quantum computing possible even though every qubit is noisy. It proves that if the physical error rate per operation stays below a fixed constant, called the threshold, then error correction can drive the effective error rate as low as you like, which lets a computation run for as many steps as it needs without the errors overwhelming the answer. That single guarantee is what separates a machine that can run Shor’s algorithm to completion from one that dissolves into noise partway through. It also carries a heavy price, because staying below the threshold and pushing the error rate low enough for a deep computation costs a large multiple of physical qubits for every logical qubit, which is the direct reason a cryptographically relevant quantum computer needs millions of physical qubits rather than a few thousand.
Source: Dorit Aharonov and Michael Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate,” 1999, arXiv:quant-ph/9906129.
The short version:
- The theorem states that quantum computation can be made robust against errors whenever the physical error rate stays below a fixed constant threshold, and it fails when the error rate is above it.
- Below the threshold, adding more error-correction redundancy keeps driving the logical error rate down, so an arbitrarily long computation becomes possible.
- Above the threshold, adding more qubits just adds more noise, and no amount of encoding saves the computation. Quality gates capability, not raw count.
- The threshold is a property of the hardware quality, and the leading surface-code estimates put a workable threshold near 1% per gate, with today’s best hardware pushing gate error rates toward that region.
- The cost of staying safely below the threshold and driving errors low enough for a deep circuit is what makes one logical qubit cost hundreds to thousands of physical ones, which is why cryptographic attacks need millions of physical qubits.
Picture a leaky bucket brigade carrying water up a long hill. Each person spills a little every time they pass the pail along, and if the hill is long enough, a bucket handed off enough times arrives empty no matter how carefully anyone works. Now suppose you add helpers at every step who catch most of the spilled water and pour it back before the next handoff. If those helpers catch more than each person spills, the bucket stays nearly full all the way to the top, however long the hill. If they catch less than each person spills, adding more helpers only crowds the line and the water still runs out. The threshold theorem is the precise version of that tipping point. Below a certain spill rate the water gets home, and above it no crew size succeeds.
What is the threshold theorem?
The threshold theorem, also called the fault-tolerance theorem or the accuracy threshold theorem, states that there exists a constant error rate, the threshold, such that any ideal quantum computation of any length can be simulated with arbitrarily small error by a fault-tolerant quantum circuit, provided the physical error rate per operation stays below that threshold. The original constant-error-rate result was proved by Dorit Aharonov and Michael Ben-Or in the late 1990s, and its abstract states the guarantee directly: “quantum computation can be made robust against errors and inaccuracies, when the error rate, η, is smaller than a constant threshold, η_c.”
Source: Dorit Aharonov and Michael Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate,” 1999, arXiv:quant-ph/9906129.
The word “constant” is what makes the theorem powerful. It says the threshold does not shrink as the computation grows, so a single fixed hardware quality is enough for a computation of any size. Without that guarantee, longer computations would demand ever-cleaner qubits, and a factoring-scale circuit billions of operations deep would need hardware so perfect it could never be built. The theorem removes that trap. It tells engineers there is a fixed quality bar, and once the hardware clears it, scale becomes a matter of adding more qubits rather than making each one impossibly good.
Why is arbitrary-length computation possible below the threshold?
Below the threshold, error correction wins a race against error accumulation, and it keeps winning no matter how long the race runs. The mechanism is that each layer of encoding takes a block of physical qubits with some error rate and produces a logical qubit with a lower one. If the physical error rate is below the threshold, that reduction is real, so the logical qubit is cleaner than its parts. You can then treat those logical qubits as the new building blocks and encode again, and each round of encoding multiplies the improvement, pushing the effective error rate down as steeply as you need.
That compounding is why arbitrary length becomes possible. A computation that needs to run a billion operations without a single surviving error simply demands a lower target error rate, and below the threshold you reach any target by adding more redundancy. The surface code, the leading practical scheme, expresses this through its code distance: increasing the distance adds more physical qubits per logical qubit and suppresses the logical error rate exponentially, so a modest increase in redundancy buys a large increase in reliability.
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.
The key qualifier is that all of this depends on being below the threshold in the first place. The compounding only compounds in the right direction when each encoding layer improves things, and that improvement is exactly what the threshold condition guarantees. Cross the line and the whole mechanism reverses.
What happens above the threshold?
Above the threshold, error correction makes things worse instead of better, and no amount of hardware rescues the computation. When the physical error rate is too high, the extra qubits and extra operations that error correction adds introduce more new errors than the correction removes. Each encoding layer then produces a logical qubit noisier than its physical parts, so stacking more layers accelerates the failure rather than fixing it. The redundancy that helps below the line actively hurts above it.
This is the single most important reason raw qubit count is a poor gauge of quantum progress. A machine with an enormous number of low-quality physical qubits sits above the threshold and cannot build even one reliable logical qubit, while a smaller machine with cleaner qubits sits below it and can. The axis that decides whether a machine can ever run a cryptographic attack is gate fidelity, not qubit count, and the threshold is the exact line that fidelity has to clear. That is the technical foundation under the advice in How to Tell Real Quantum Progress From Hype to read error rates before headline qubit numbers.
Where does the threshold sit for real hardware?
The threshold is not a single universal number, because it depends on the error-correction code, the noise model, and the hardware assumptions, but the practically important figure for the leading surface code sits near 1% per gate. Numerical studies of the surface code place the threshold in a band roughly between 0.5% and 1.4% per gate depending on the assumptions, and the widely used engineering target is to keep two-qubit gate error rates comfortably below about 0.1% so the machine sits well under the threshold with margin to spare.
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.
The distinction between the theorem’s threshold and the engineering target matters. The threshold is the line above which error correction fails outright. The target is where you want to operate to make error correction cheap, because the closer the hardware gets to the threshold from below, the more physical qubits each logical qubit costs, and the further below it you sit, the fewer you need. A machine that barely clears the threshold can technically build logical qubits but pays a punishing overhead, while a machine well below it builds them affordably. Today’s best superconducting and trapped-ion hardware has pushed two-qubit gate error rates into the region near and below 0.1%, which is why the field crossed a real milestone when a below-threshold logical qubit was first demonstrated.
How was the threshold demonstrated on real hardware?
The threshold moved from theory to measured fact in 2024, when Google’s quantum team built a surface-code logical qubit and showed that adding more physical qubits actually lowered its error rate rather than raising it. That “below threshold” result, published in Nature, is the empirical confirmation that the hardware had finally crossed the line the theorem describes, because the defining behavior below the threshold is exactly that more redundancy yields a cleaner logical qubit.
Source: Rajeev Acharya et al. (Google Quantum AI), “Quantum error correction below the surface code threshold,” Nature 638, 920-926, 2025, arXiv:2408.13687.
The demonstration used 101 physical qubits to protect a single logical qubit, which is the overhead ratio in miniature and a sober reminder of the distance still to cover. Crossing the threshold for one logical qubit proves the approach scales the right way, but a cryptographic attack needs thousands of logical qubits held together at once, each driven to a far lower error rate than that first demonstration reached, which costs more physical qubits per logical qubit. Being below the threshold in principle is a genuine milestone, and it is a different thing from running error correction at the scale resource estimates demand.
Why does the threshold theorem force millions of physical qubits?
The theorem forces a huge physical count because clearing the threshold is only the entry ticket, and running a deep cryptographic circuit demands driving the logical error rate far below what a single encoding layer delivers. A factoring computation runs billions of operations in sequence, so the logical error rate has to be minuscule for the whole run to survive without a single uncorrected fault. Reaching that tiny error rate means increasing the code distance, and every increase adds more physical qubits per logical qubit, so the overhead balloons precisely because the computation is so long.
That is the through-line from this theorem to the resource estimates for breaking RSA. Under the surface code at realistic hardware quality, one logical qubit reliable enough for a factoring circuit costs on the order of a thousand or more physical qubits, and a Shor’s attack on RSA-2048 needs roughly 6,100 logical qubits, which is why the peer-reviewed estimates land in the range of hundreds of thousands to tens of millions of physical qubits.
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 theorem is therefore both the reason a code-breaking machine is possible and the reason it is so hard to build. It guarantees that no fundamental physics blocks the path, so the threat is real rather than science fiction. It also sets the price of admission so high, in clean qubits driven far below the threshold and multiplied by error-correction overhead, that the machine remains years of engineering away in 2026.
Common misconceptions
- “The threshold theorem means quantum error correction is basically solved.” It proves error correction can work below a fixed error rate, which is a guarantee of possibility, not of practicality. Running it at the scale a cryptographic attack needs, thousands of logical qubits held together, is still a large unsolved engineering problem.
- “Once you cross the threshold, error correction is cheap.” Crossing the threshold only makes error correction work at all. The overhead per logical qubit stays large until the hardware sits well below the threshold, and driving errors low enough for a deep circuit multiplies that cost further.
- “The threshold is one fixed number for all quantum computers.” It depends on the code and the noise model. The leading surface code has a threshold near 1% per gate in numerical studies, while other codes and assumptions give different values.
- “Above the threshold you just need more qubits.” Above the threshold, more qubits add more error than the correction removes, so the logical qubit gets worse, not better. Quality has to clear the line first, and only then does adding qubits help.
- “A below-threshold demonstration means a cryptographic machine is near.” The 2024 result crossed the threshold for a single logical qubit built from 101 physical ones. A CRQC needs thousands of logical qubits at a far lower error rate, which is millions of physical qubits away.
Questions people ask
What does the threshold theorem actually say? It says there is a constant physical error rate, the threshold, below which error correction can make a quantum computation of any length as accurate as you want. Below that rate, adding redundancy drives the logical error rate down without limit; above it, error correction fails (arXiv:quant-ph/9906129).
Why is it so important for the quantum threat? Because it is what makes a long computation like Shor’s algorithm survivable on noisy hardware at all. Without a threshold, longer computations would need ever-perfect qubits, and a factoring-scale circuit could never run. With one, scale becomes an engineering problem of adding qubits rather than perfecting each one.
What is the actual threshold value? It depends on the code and noise model. For the leading surface code, numerical studies put it near 1% per gate, in a band roughly from 0.5% to 1.4%, and engineers aim well below that, toward 0.1% two-qubit gate error, to keep the overhead affordable (arXiv:1208.0928).
Has any hardware actually crossed the threshold? Yes. In 2024 Google demonstrated a surface-code logical qubit built from 101 physical qubits whose error rate fell as more physical qubits were added, the defining below-threshold behavior (arXiv:2408.13687). That was one logical qubit, far short of a cryptographic machine.
Why does the theorem force millions of physical qubits? Because a deep cryptographic circuit needs the logical error rate driven far below what one encoding layer gives, which means a large code distance and many physical qubits per logical qubit. Multiply that by the thousands of logical qubits a Shor’s attack needs, and the physical total reaches the millions (arXiv:1905.09749).
Does the threshold theorem change my migration plan? Indirectly, by explaining why the threat is both real and still years off. It confirms no physics blocks a code-breaking machine, so the migration is necessary, and it shows why the machine is hard enough to build that lead-time planning through Mosca’s theorem is the sound approach rather than waiting.
Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.