Quantum threshold theorem

Remarks

Proof idea: encode each qubit in a quantum error-correcting code and replace each operation by a fault-tolerant gadget that does not spread a single fault into an uncorrectable error. Then a level-$1$ logical operation fails with probability at most $c p^2$ for a constant $c$. Concatenating the code $k$ times gives logical failure probability at most $p_{\mathrm{th}} (p/p_{\mathrm{th}})^{2^k}$ with $p_{\mathrm{th}} = 1/c$. So the error falls doubly exponentially in $k$ while the size grows only exponentially in $k$, which gives the polylogarithmic overhead.

The hypothesis of fresh qubits is needed: error correction removes entropy from the computer, and without a supply of fresh qubits the entropy builds up and long computations fail. The parallelism is needed so that errors can be corrected on all qubits at every time step.

Example: with stabilizer codes such as surface codes, numerical studies estimate thresholds of the order of $1\%$ for some noise models.

Going deeper

For a student

The theorem was proved independently in the late 1990s by Aharonov and Ben-Or, by Kitaev, and by Knill, Laflamme and Zurek. It is the quantum analogue of von Neumann's theorem on reliable computation with unreliable components. The value of $p_{\mathrm{th}}$ depends on the noise model, the code and the gadgets, and the rigorous lower bounds are far below the numerical estimates. The theorem also holds for some correlated noise models with suitably decaying correlations.