nLab error threshold theorem

Idea

In the theory of computation, a threshold theorem (short for error threshold) states that when the error-rates of realistic logic gate-components are below a given threshold, then error correction can achieve an arbitrarily error-free computation.

For classical computation, where an early version of this statement is due to von Neumman 1956, the reality of virtually error-free (digitial) computing machines has become commonplace and threshold theorems are rarely discussed anymore these days.

This situation is different for quantum computing, where threshold theorems (proven by Knill, Laflamme & Zurek 1998) and Aharonov and Ben-Or 2008 are the basis for ongoing hopes that quantum error correction technology can achieve scalable useful quantum computers even with near-term available noisy qbits and noisy quantum logic gates (cf. NISQ).

References

For classical computing

• John von Neumann (notes by R. S. Pierce): Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable Components, in: Automata Studies, Princeton University Press (1956) 329-378 [doi;10.1515/9781400882618-003, pdf, pdf]

For quantum comuting

For more see here at quantum error correction.

Original proofs of threshold theorems for various error-models in quantum computing:

• Emanuel Knill, Raymond Laflamme, Wojciech Zurek: Resilient Quantum Computation: Error Models and Thresholds, Science 279 5349 (1998) 342-345 [doi;10.1126/science.279.5349.342, arXiv:quant-ph/9702058]

• Dorit Aharonov, Michael Ben-Or: Fault-Tolerant Quantum Computation with Constant Error Rate, SIAM Journal on Computing 38 4 (2008) [doi:10.1137/S0097539799359385, arXiv:quant-ph/9906129]

following

• Peter Shor: Fault-tolerant quantum computation, Proceedings of 37th Conference on Foundations of Computer Science (1996) 56-65 [doi:10.1109/SFCS.1996.548464]

Review:

• Daniel Gottesman, §5 in: An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation, in: Quantum Information Science and Its Contributions to Mathematics, Proceedings of Symposia in Applied Mathematics 68 (2010) [arXiv:0904.2557, doi:10.1090/psapm/068]

Lecture notes:

• Seth Lloyd: Fault Tolerant Quantum Computing, Lecture 14 in Quantum Computing (CST Part II) [pdf]

See also:

• Wikipedia: Threshold theorem