Threshold Theorem

Definition

The threshold theorem is the reason large quantum computers are possible in principle. It says that there is a critical level of noise, the threshold, and that if every gate and measurement is more accurate than that level, then errors can be suppressed as much as you like by using more qubits for error correction. Below the threshold, adding redundancy helps. Above it, adding redundancy makes things worse.

In depth

Early in the 1990s many physicists doubted that quantum computers could work at scale, because quantum states cannot be copied and every operation introduces new errors. The threshold theorem, proved independently by Aharonov and Ben-Or, by Kitaev, and by Knill, Laflamme, and Zurek in 1996 to 1998, answered that objection. Its proofs use concatenated codes, in which each qubit is encoded in a code whose qubits are themselves encoded, repeated over several levels, with fault-tolerant gadgets that prevent errors from spreading.

The exact threshold value depends on the code, the noise model, and the assumptions. Rigorous early bounds were extremely small, around 10 to the minus 5 or 10 to the minus 6, while numerical studies show that the surface code has a threshold near 1 percent for circuit-level noise with fast decoding. Hardware has crossed this line: modern superconducting and ion devices have two-qubit error rates of 0.1 to 0.5 percent, which is why experiments such as Google's Willow can show logical error falling as the code grows.

The theorem comes with assumptions that matter in practice. Noise should be local or weakly correlated, operations must be parallel so that idle qubits do not accumulate errors, fresh qubits must be supplied continuously, and classical processing for decoding must be fast and reliable. Correlated errors from crosstalk, leakage, or cosmic rays can violate the assumptions, and handling them is an active research area.

Technical Definition

The quantum accuracy threshold theorem states that there exists a constant p_th such that, for any quantum circuit of size N and any target accuracy epsilon, if the physical error rate per operation is below p_th and noise satisfies suitable locality conditions, the circuit can be simulated by a fault-tolerant circuit with polylogarithmic overhead in N over epsilon. For concatenated codes, the logical error after k levels scales as p_th times (p over p_th) to the power 2^k.

Visual Explanation: An Analogy

Think of bailing water out of a leaky boat. If the leak is slower than you can bail, you stay afloat indefinitely. If the leak is faster, no amount of effort will save you. The threshold is the leak rate at which bailing exactly keeps pace.

Key facts

Where the idea comes from

After Shor's 1995 code showed error correction was possible, the next question was whether it could be done with imperfect gates. The threshold theorems of 1996 to 1998 settled it theoretically, and Raussendorf, Harrington, and Fowler's work on the surface code in the 2000s and 2010s produced much more optimistic numerical thresholds.

Real-World Use Cases

• Justifying that scalable, fault-tolerant quantum computing is possible.
• Setting hardware targets: physical error rates must be well below the threshold of the chosen code.
• Comparing codes by threshold and overhead.
• Interpreting experiments that show logical errors decreasing with code size.

How it differs from related ideas

• The threshold is a property of a code, a noise model, and a decoder together, not of hardware alone.
• Being below threshold is necessary but not sufficient: the overhead can still be huge if the error rate is just under it.
• Classical computers also use error correction, but they rarely need it for logic because transistors are reliable.

Common Misconceptions

• There is not a single universal threshold. Different codes and noise models have different thresholds.
• Reaching the threshold does not mean a quantum computer is ready. It means scaling up will improve things.
• The theorem does not guarantee success under all noise, only under assumptions about locality and independence.

Frequently asked questions

Related Terms

• Fault Tolerance
• Code Distance
• Surface Code
• Logical Qubit

Keep exploring

• Algorithm: Quantum Error-Correcting Codes (Shor Code, Surface Code)
• Hardware: Google Willow

← Back to the dictionary