Quantum Error Correction and Fault Tolerant Quantum Computing
- Markus Grassl ,
- Martin Roetteler
in R. A. Meyers, editor, Encyclopedia of Complexity and Systems Science, Springer
2009
In the early days of quantum computing, Haroche and Raimond asked the poignant question whether the dream of quantum computing could ever be realized in a real physical system or if “the large-scale quantum machine … is the experimenter’s nightmare”. At the time the article was written, the first quantum error-correcting code had just been proposed. However, Haroche and Raimond argued that “the implementation of error-correcting codes will become exceedingly difficult” given any detection efficiency less than 100%. It was only later that it was shown that even with imperfect quantum memory and imperfect quantum operations it is possible to implement arbitrary long quantum computation, provided that the failure probability of each element is below a certain threshold. Here we provide an overview of the ingredients leading to fault tolerant quantum computation (FTQC). In the first part, we present the theory of quantum error-correcting codes (QECCs) and in particular two important classes of QECCs, namely the so-called CSS codes and stabilizer codes. Both are related to classical error-correcting codes, so we start with some basics from this area. In the second part of the article, we present a high-level view of the main ideas of FTQC and the threshold theorem.