Skip to content

Basics of fault tolerance

Rough overview (in words)

The error rates of all known realizations of physical qubits and basic operations are too high to enable implementation of the majority of quantum algorithms considered in this survey. Even if the probability \(p\) for each basic operation to malfunction was minute, we would nevertheless expect an error to occur in any quantum circuit comprising more than \(\mathcal{O}\left( 1/p \right)\) operations. One may optimistically assume that in the foreseeable future \(p= 10^{-6}\) might be achieved by certain quantum architectures, such as trapped ions [1, 2]. This, in turn, limits the size of any quantum circuit that one may hope to reliably execute to roughly one million basic operations. Such a bound places a severe restriction on the algorithms that could be run and is orders of magnitude smaller than the resources needed to implement the quantum algorithms described in the other parts of this survey.

The theory of quantum fault tolerance [3] and quantum error correction [4, 5, 6] provides a collection of techniques to deal with imperfect operations and unavoidable noise afflicting the physical hardware, at the expense of moderately increased resource overheads. In the basic model for fault tolerance one assumes that each elementary component of a quantum circuit (including the identity gate) may fail with some small but nonzero probability, independently of the other components, and classical information processing is noiseless. For concreteness and simplicity, one may choose to model any noisy component as an ideal component followed by (or, in the case of measurements, preceded by) some Pauli channel acting on the same subset of qubits. Let \(\mathcal C\) be a quantum circuit (possibly with classical input and output) describing a desired quantum algorithm. Since each component of \(\mathcal C\) may fail, one should not implement \(\mathcal C\) directly; rather, one needs to implement a different quantum circuit \(\mathcal F(\mathcal C)\), which is fault-tolerant (FT) version of \(\mathcal C\). This, in turn, can be achieved by replacing each qubit in \(\mathcal C\) with a logical qubit encoded in some quantum error-correcting (QEC) code and each elementary component of \(\mathcal C\) with a corresponding FT gadget; see Fig. 1. The desired quantum computation will then be realized on the logical level of \(\mathcal F(\mathcal C)\) without leaving the protective encoding guaranteed by the QEC code.

Figure 1(a): A quantum circuit \(\mathcal C\) consists of state preparation, unitary gates, and measurements.

1(b): An FT realization of \(\mathcal C\) is a quantum circuit \(\mathcal F(\mathcal C)\) obtained by replacing each qubit in \(\mathcal C\) with a logical qubit encoded in some QEC code and using appropriate FT gadgets interspersed with QEC gadgets in place of each basic component of \(\mathcal C\). Note that some gadgets may require considerable resources (not shown in the picture); see logical gates and QEC gadgets with the surface code for more details.

To realize universal FT quantum computation, it suffices to have state preparation gadgets (for at least one type of state), measurement gadgets (for at least one type of measurement), gate gadgets (for a universal set of gates) and QEC gadgets. One requires that all these gadgets satisfy certain FT conditions; see, for instance, [7, 8]. Although the asymptotic scaling of resource overheads associated with FT gadgets is manageable (for instance, polylogarithmic in the inverse of the target logical error rate), the constant prefactors tend to be large, resulting in the qubit and time overheads that currently constitute one of the main bottlenecks to practical FT quantum computation. We will discuss this point in more detail for the implementation of logical gates and QEC gadgets with the planar architecture based on the surface code [9, 10].

Rough overview (in math)

Designing FT gadgets is a challenging task for several reasons. First, FT gadgets are usually developed and optimized for a specific QEC code. Second, even though they comprise imperfect basic components, they are required to work reliably as long as a number of malfunctioning components is limited. Third, FT gadgets may spread errors, however they must not do so in an uncontrollable way.

Given a set of FT gadgets, one can reliably perform an arbitrarily long quantum computation as long as the physical error rate of each basic component is below some constant value, often referred to as the FT threshold. This result is established by the celebrated threshold theorem [11, 12, 13, 7]. To be more precise, consider the basic model for FT. The threshold theorem asserts that there exists a constant \(p_\text{FT}>0\), such that for any \(\epsilon>0\) and any quantum circuit \(\mathcal C\) there exists a quantum circuit \(\widetilde{\mathcal C}\) that produces an output with statistical distance at most \(\epsilon\) from the output of \(\mathcal C\), provided the physical error rate \(p\) is below \(p_\text{FT}\). Moreover, \(\widetilde{\mathcal C}\) uses a number of qubits and timesteps that are at most \(\mathrm{polylog}(|\mathcal C|/\epsilon)\) times bigger than the number of qubits and timesteps in \(\mathcal C\), where \(|\mathcal C|\) denotes the number of basic components in \(\mathcal C\).

The basic idea behind the proof of the threshold theorem proceeds as follows. Consider a quantum circuit \(\mathcal F(\mathcal C)\), which is an FT implementation of \(\mathcal C\). Assuming the basic model for fault tolerance described above, for sufficiently small physical error rate \(p\), the logical error rate for \(\mathcal F(\mathcal C)\) should be smaller than \(p\), since \(\mathcal F(\mathcal C)\) is an FT implementation of \(\mathcal C\). One can then consider a quantum circuit \(\mathcal F\circ \mathcal F(\mathcal C)\), which is an FT implementation of \(\mathcal F(\mathcal C)\), reducing the logical error rate even further. By repeating this process, one eventually obtains a quantum circuit \(\widetilde{\mathcal C} = \mathcal F\circ\ldots \circ \mathcal F(\mathcal C)\) with the logical error rate below \(\epsilon\). The resulting FT protocol is based on concatenated QEC codes.

One may improve the scaling of the resource overheads from the threshold theorem with concatenated QEC codes. In particular, in the asymptotic limit of large quantum circuits, the ratio of qubits in \(\mathcal C\) and \(\widetilde{\mathcal C}\) can be a constant [14]. In this construction, the FT protocol requires a family of QEC codes that satisfies certain properties, including the desired scaling of code parameters, computationally efficient decoding algorithms and constant-weight parity checks. Such a family of QEC codes was first provided in [15].

Dominant resource cost (gates/qubits)

At the heart of FT quantum computation, there is usually some QEC code. Since the choice of a QEC code affects the resource overheads, we would like to choose one for which the encoding rate (defined as the ratio \(k/n\), where \(k\) and \(n\) are the number of logical and physical qubits, respectively) as well as the relative code distance (defined as the ratio \(d/n\), where \(d\) is the minimum weight of any nontrivial logical operator) are as high as possible. Although for concatenated QEC codes (that feature in the threshold theorem), both \(k/n\) and \(d/n\) go to zero as \(n\) goes to infinity, we know that there exist QEC codes with good parameters, i.e, for which \(k/n\) and \(d/n\) are asymptotically constant [16]. Moreover, recent groundbreaking results [17, 18, 19, 20] provided constructions of QEC codes that not only have good parameters but also constant-weight parity checks (thus their name—quantum low-density parity check codes). The latter property is particularly important from the perspective of fault tolerance. However, experimental realization of these constructions (in contrast to the surface code) seems extremely challenging, at least within the realm of solid-state qubits constrained by geometric locality of their physical entangling gates.

Another aspect of FT quantum computation that affects the resource overheads are the FT gadgets that are being used. One of the easiest ways to implement FT gadgets for gates is via transversal gates. By definition, transversal gates are implemented via a tensor product of single-qubit unitaries (or, more generally, via a depth-one quantum circuit) and therefore do not spread errors in an uncontrollable way. Unfortunately, transversal gates are limited by the Eastin–Knill theorem [21, 22, 23, 24], which rules out the existence of a (finite-dimensional) QEC code with a universal set of transversal logical gates. One strategy to circumvent this limitation is to prepare certain magic states and use them to realize FT gates [25]; see the section on implementing logical gates for more details and a discussion of other strategies.

To realize FT gadgets for state preparation, QEC, and measurement, one typically chooses among three standard FT schemes: Shor's [3], Steane's [26], or Knill's [27]. Roughly speaking, Shor's scheme uses simple states (verified cat states) of the ancilla qubits at the expense of implementing many gates on the data qubits, whereas Steane's and Knill's schemes trade highly complex states of the ancilla qubits (logical states encoded in the underlying QEC code) for minimizing the number of gates on the data qubits. To determine the best choice, one needs to consider the underlying QEC code (e.g., Steane's scheme is applicable only to CSS codes [16, 5]) and the quantum hardware restrictions (e.g., lack of extra ancilla qubits). For an illuminating and detailed discussion of FT schemes, see, e.g., [8]. We remark that for QEC codes with additional structure, such as quantum low-density parity check codes, one may pursue different approaches toward FT quantum computation; see the section on QEC with the surface code.

Caveats

Rigorous proofs provide lower bounds on the FT threshold \(p_\text{FT}\). For instance, for an FT scheme based on the \(7\)-qubit code, one finds \(p_\text{FT} > 2.73\times 10^{-5}\) [7]. For an FT scheme by Knill [27] that relies on complex ancilla preparation techniques, one finds \(p_\text{FT} > 1.04\times 10^{-3}\) [28]. However, these values can differ by orders of magnitude from the values estimated in numerical simulations. For instance, the FT scheme by Knill is estimated to have an FT threshold \(p_\text{FT}\) as high as \(5\times 10^{-2}\), constituting one of the highest known FT thresholds. We remark that these values depend sensitively on the details of the FT schemes and the assumptions about noise. In particular, to obtain the aforementioned values we assume the ability to implement gates between any qubits. On the other hand, if we arrange qubits on some geometric lattice and restrict gates to be local, then FT thresholds still exist, however their values are significantly reduced.

One can expand the threshold theorem in many ways. Even using the basic model for fault tolerance, one may choose the failure probabilities for each elementary component of a quantum circuit differently, e.g., the failure probability of a measurement to be ten times higher than that of a gate. One can consider more general noise (which includes systematic errors, such as overrotations) arising due to a weak interaction between the system and a non-Markovian environment [7, 29]. In general, although experimental realizations of quantum computation may not satisfy exactly the assumptions of the threshold theorem, we expect the main conclusions to hold as long as the assumptions are not violated too much.

To simplify the analysis of FT schemes, we often assume unlimited classical computational power that one needs to, e.g., process the error syndrome and infer an appropriate recovery operator in a QEC gadget; a number of such decoding algorithms have been developed for QEC with the surface code. It is important not to abuse this assumption by, for instance, solving the initial problem with an inefficient classical algorithm. At some point, however, one needs to take into account the finite speed of classical information processing. If the classical unit that processes the error syndrome is unable to keep pace with the rate at which this syndrome is being produced, then the error syndrome will start to accumulate and one will suffer from the so-called backlog problem [30]. Subsequently, the speed of quantum computing will be exponentially reduced and the computational advantage of quantum computing will be annulled. This issue will be especially prominent for polynomial speedup quantum algorithms.

Further reading

  • An accessible introduction to quantum error correction and the theory of fault tolerance can be found in [31].
  • A detailed introduction to quantum error correction and fault-tolerant quantum computation can be found in [8].
  • A fairly recent perspective on roads towards fault-tolerant universal quantum computation can be found in [32].
  • The error correction zoo provides a useful compilation of error correcting codes.

Bibliography

  1. A. Bermudez, X. Xu, R. Nigmatullin, J. O'Gorman, V. Negnevitsky, P. Schindler, T. Monz, U. G. Poschinger, C. Hempel, J. Home, F. Schmidt-Kaler, M. Biercuk, R. Blatt, S. Benjamin, and M. Müller. Assessing the progress of trapped-ion processors towards fault-tolerant quantum computation. Physical Review X, 7(4):041061, 12 2017. arXiv: https://arxiv.org/abs/1705.02771. doi:10.1103/physrevx.7.041061.

  2. Colin D. Bruzewicz, John Chiaverini, Robert McConnell, and Jeremy M. Sage. Trapped-ion quantum computing: progress and challenges. Applied Physics Reviews, 6(2):021314, 6 2019. arXiv: https://arxiv.org/abs/1904.04178. doi:10.1063/1.5088164.

  3. Peter W. Shor. Fault-tolerant quantum computation. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS), 56–65. IEEE Comput. Soc. Press, 1996. arXiv: https://arxiv.org/abs/quant-ph/9605011. doi:10.1109/SFCS.1996.548464.

  4. Peter W. Shor. Scheme for reducing decoherence in quantum computer memory. Physical Review A, 52:R2493–R2496, 1995. doi:10.1103/PhysRevA.52.R2493.

  5. A. M. Steane. Error correcting codes in quantum theory. Physical Review Letters, 77:793–797, 1996. doi:10.1103/PhysRevLett.77.793.

  6. Daniel Gottesman. Class of quantum error-correcting codes saturating the quantum hamming bound. Physical Review A, 54(3):1862–1868, 1996. arXiv: https://arxiv.org/abs/quant-ph/9604038. doi:10.1103/PhysRevA.54.1862.

  7. Panos Aliferis, Daniel Gottesman, and John Preskill. Quantum accuracy threshold for concatenated distance-3 codes. Quantum Information and Computation, 6(2):97–165, 2006. arXiv: https://arxiv.org/abs/quant-ph/0504218. doi:10.26421/QIC6.2-1.

  8. Daniel Gottesman. An introduction to quantum error correction and fault-tolerant quantum computation. In Proceedings of Symposia in Applied Mathematics, volume 68, 13–58. 2010. arXiv: https://arxiv.org/abs/0904.2557.

  9. A. Yu. Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2–30, 2003. arXiv: https://arxiv.org/abs/quant-ph/9707021. doi:10.1016/S0003-4916(02)00018-0.

  10. Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43(9):4452–4505, 2002. arXiv: https://arxiv.org/abs/quant-ph/0110143. doi:10.1063/1.1499754.

  11. Dorit Aharonov and Michael Ben-Or. Fault-tolerant quantum computation with constant error rate. SIAM Journal on Computing, 38(4):1207–1282, 7 2008. Earlier version in STOC'97, arXiv: https://arxiv.org/abs/quant-ph/9906129. URL: https://doi.org/10.1137/S0097539799359385, doi:10.1137/S0097539799359385.

  12. A Yu Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191, 1997. doi:10.1070/RM1997v052n06ABEH002155.

  13. Emanuel Knill, Raymond Laflamme, and Wojciech H Zurek. Resilient quantum computation: error models and thresholds. Proceedings of the Royal Society A, 454(1969):365–384, 1998. arXiv: https://arxiv.org/abs/quant-ph/9702058. doi:10.1098/rspa.1998.0166.

  14. Daniel Gottesman. Fault-tolerant quantum computation with constant overhead. Quantum Information and Computation, 14(15–16):1338–1372, 2014. arXiv: https://arxiv.org/abs/1310.2984. doi:10.26421/QIC14.15-16-5.

  15. Omar Fawzi, Antoine Grospellier, and Anthony Leverrier. Constant overhead quantum fault-tolerance with quantum expander codes. In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS). 2018. arXiv: https://arxiv.org/abs/1808.03821. doi:10.1109/focs.2018.00076.

  16. A. R. Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Physical Review A, 54(2):1098–1105, 1996. arXiv: https://arxiv.org/abs/quant-ph/9512032. doi:10.1103/physreva.54.1098.

  17. Nikolas P. Breuckmann and Jens N. Eberhardt. Balanced product quantum codes. IEEE Transactions on Information Theory, 67(10):6653–6674, 2021. arXiv: https://arxiv.org/abs/2012.09271. doi:10.1109/tit.2021.3097347.

  18. Pavel Panteleev and Gleb Kalachev. Asymptotically good quantum and locally testable classical ldpc codes. In Proceedings of the 54th ACM Symposium on the Theory of Computing (STOC), 375–388. 2022. arXiv: https://arxiv.org/abs/2111.03654. doi:10.1145/3519935.3520017.

  19. Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes. Locally testable codes with constant rate, distance, and locality. In Proceedings of the 54th ACM Symposium on the Theory of Computing (STOC), 357–374. 2022. arXiv: https://arxiv.org/abs/2111.04808. doi:10.1145/3519935.3520024.

  20. Anthony Leverrier and Gilles Zémor. Quantum tanner codes. In Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS), 872–883. IEEE, 2022. arXiv: https://arxiv.org/abs/2202.13641. doi:10.1109/FOCS54457.2022.00117.

  21. Bryan Eastin and Emanuel Knill. Restrictions on transversal encoded quantum gate sets. Physical Review Letters, 102(11):110502, 2009. arXiv: https://arxiv.org/abs/0811.4262. doi:10.1103/physrevlett.102.110502.

  22. Bei Zeng, Andrew Cross, and Isaac L. Chuang. Transversality versus universality for additive quantum codes. IEEE Transactions on Information Theory, 57(9):6272–6284, 2011. arXiv: https://arxiv.org/abs/0706.1382. doi:10.1109/tit.2011.2161917.

  23. Tomas Jochym-O'Connor, Aleksander Kubica, and Theodore J. Yoder. Disjointness of stabilizer codes and limitations on fault-tolerant logical gates. Physical Review X, 8(2):021047, 2018. arXiv: https://arxiv.org/abs/1710.07256. doi:10.1103/physrevx.8.021047.

  24. Aleksander Kubica and Rafał Demkowicz-Dobrzański. Using quantum metrological bounds in quantum error correction: a simple proof of the approximate eastin–knill theorem. Physical Review Letters, 126(15):150503, 2021. arXiv: https://arxiv.org/abs/2004.11893. doi:10.1103/physrevlett.126.150503.

  25. Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal clifford gates and noisy ancillas. Physical Review A, 71(2):022316, 2005. arXiv: https://arxiv.org/abs/quant-ph/0403025. doi:10.1103/physreva.71.022316.

  26. A. M. Steane. Active stabilization, quantum computation, and quantum state synthesis. Physical Review Letters, 78(11):2252–2255, 1997. arXiv: https://arxiv.org/abs/quant-ph/9611027. doi:10.1103/physrevlett.78.2252.

  27. E. Knill. Quantum computing with realistically noisy devices. Nature, 434(7029):39–44, 2005. arXiv: https://arxiv.org/abs/quant-ph/0410199. doi:10.1038/nature03350.

  28. Panos Aliferis, Daniel Gottesman, and John Preskill. Accuracy threshold for postselected quantum computation. Quantum Information and Computation, 8(3&4):181–244, 2008. arXiv: https://arxiv.org/abs/quant-ph/0703264. doi:10.26421/QIC8.3-4-1.

  29. Barbara M. Terhal and Guido Burkard. Fault-tolerant quantum computation for local non-markovian noise. Physical Review A, 71(1):012336, 2005. arXiv: https://arxiv.org/abs/quant-ph/0402104. doi:10.1103/physreva.71.012336.

  30. Barbara M. Terhal. Quantum error correction for quantum memories. Reviews of Modern Physics, 87(2):307–346, 2015. arXiv: https://arxiv.org/abs/1302.3428. doi:10.1103/revmodphys.87.307.

  31. Robert Raussendorf. Key ideas in quantum error correction. Philosophical Transactions of the Royal Society A, 370(1975):4541–4565, 2012. doi:10.1098/rsta.2011.0494.

  32. Earl T. Campbell, Barbara M. Terhal, and Christophe Vuillot. Roads towards fault-tolerant universal quantum computation. Nature, 549(7671):172–179, 2017. arXiv: https://arxiv.org/abs/1612.07330. doi:10.1038/nature23460.