Fault-Tolerance Threshold

The fault-tolerance threshold is one of the most important theoretical results in quantum computing. It establishes that reliable quantum computation is possible in principle, even with imperfect physical hardware, provided the error rate is below a specific bound.

The Threshold Theorem

The threshold theorem (proven independently by Aharonov and Ben-Or, Knill, Laflamme and Zurek, and others in the late 1990s) states:

If the physical error rate p per gate is below a threshold value p_th, there exists a fault-tolerant computation scheme that can simulate any ideal quantum circuit of length L using at most polylog(L) additional physical qubits and gates per logical operation, with the logical error rate decreasing as (p/p_th)^{2^k} for k rounds of error correction concatenation.

In simpler terms: below the threshold, adding more physical qubits per logical qubit makes logical errors exponentially rare. Above the threshold, adding more qubits makes things worse.

The Value of the Threshold

The threshold value depends on the error model, the quantum error correcting code, and the fault-tolerant protocol. Common values are:

• Concatenated codes (generic noise): roughly 10^(-4) to 10^(-3), depending on the code and noise model.
• Surface codes (local noise, 2D hardware): approximately 1% (10^(-2)). The surface code has an unusually high threshold because of its local syndrome measurements and high decoding efficiency.
• Color codes: thresholds similar to surface codes but with different trade-offs in gate implementation.

The surface code’s ~1% threshold is particularly significant because some current superconducting and trapped-ion hardware is approaching or reaching this level for two-qubit gate fidelities. This makes the surface code the leading candidate for near-future fault-tolerant quantum computers.

Below and Above the Threshold

Below the threshold: logical error rate decreases as the code distance d increases. For a surface code with physical error rate p < p_th, the logical error rate scales approximately as (p/p_th)^{(d+1)/2}. By choosing large enough d, the logical error rate can be made as small as desired.

Above the threshold: increasing code distance amplifies rather than suppresses errors. Each error correction cycle introduces more errors than it removes. Scaling up the hardware makes logical error rates worse.

Physical Reality

Most current hardware operates with two-qubit gate fidelities of 99% to 99.9%, placing physical error rates between 10^(-3) and 10^(-2). This is at or above the surface code threshold of ~1%, though fault-tolerant demonstrations with small surface codes have been achieved.

Crucially, reaching the threshold is necessary but not sufficient for practical fault-tolerant quantum computing. The overhead in physical qubits per logical qubit is still enormous: even at p = 0.1% (10x below threshold for the surface code), applications like Shor’s algorithm on a 2048-bit key would require millions of physical qubits. Reducing overhead while maintaining threshold levels is the central engineering challenge.

Threshold vs Pseudothreshold

A pseudothreshold is the error rate below which a single level of error correction reduces the error rate compared to the uncorrected case. It is always higher than the true threshold. The pseudothreshold is sometimes cited to make a code look better than it is; always verify whether a claimed threshold is the true asymptotic threshold or the pseudothreshold.

See also

• Fault-Tolerant Quantum Computing
• Logical Qubit
• Magic State
• Surface Code