CoChat
Sign Up
PreprintCited by 129Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyCoding theory and cryptography

An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation

Open access
Gottesman, Daniel·2009·arXiv
DOI 10.48550/arxiv.0904.2557arXiv 0904.2557
Open this paper in CoChat — free accountOpen PDF

Abstract

Quantum states are very delicate, so it is likely some sort of quantum error correction will be necessary to build reliable quantum computers. The theory of quantum error-correcting codes has some close ties to and some striking differences from the theory of classical error-correcting codes. Many quantum codes can be described in terms of the stabilizer of the codewords. The stabilizer is a finite Abelian group, and allows a straightforward characterization of the error-correcting properties of the code. The stabilizer formalism for quantum codes also illustrates the relationships to classical coding theory, particularly classical codes over GF(4), the finite field with four elements. To build a quantum computer which behaves correctly in the presence of errors, we also need a theory of fault-tolerant quantum computation, instructing us how to perform quantum gates on qubits which are encoded in a quantum error-correcting code. The threshold theorem states that it is possible to create a quantum computer to perform an arbitrary quantum computation provided the error rate per physical gate or time step is below some constant threshold value.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.0904.2557

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Eventually we expect to be able to protect quantum systems and scale up quantum computers using the principle of quantum error correction.

    “Eventually we expect to be able to protect quantum systems and scale up quantum computers using the principle of quantum error correction [10].”

    From Quantum Computing in the NISQ era and beyond (2018) · cites this paper as [10]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Still being checked.

Research works printed but not linked: 53

  1. [1][1] D. Aharonov and M. Ben-Or, Fault-tolerant quantum computation with constant error , Proc. 29th Ann. ACM Symp. on Theory of Computation (ACM, New York, 1998), 176-188; arXiv:quant-ph/9611025; D. Aharonov and M. Ben-Or, Fault-tolerant quantum computation with constant error rate , SIAM J. Comput. 38 (2008), 1207-1282; arXiv:quant-ph/9906129. - · arXiv
  2. [2][2] D. Aharonov, M. Ben-Or, R. Impagliazzo, N. Nisan, Limitations of Noisy Reversible Computation , arXiv:quant-ph/9611028 (1996). - · arXiv
  3. [3][3] P. Aliferis, D. Gottesman, and J. Preskill, Quantum accuracy threshold for concatenated distance3 codes , Quant. Info. Comp. 6 (2006), 97-165; arXiv:quant-ph/0504218. - · arXiv
  4. [4][4] , Accuracy threshold for postselected quantum computation , Quant. Info. Comp. 8 (2008), 181-244; arXiv:quant-ph/0703264. - · arXiv
  5. [5][5] P. Aliferis and J. Preskill, Fault-tolerant quantum computation against biased noise , Phys. Rev. A 78 (2008), 052331; arXiv:0710.1301 [quant-ph]. - · arXiv
  6. [6][6] , The Fibonacci scheme for fault-tolerant quantum computation , Phys. Rev. A 79 (2009), 012332; arXiv:0809.5063 [quant-ph]. - · arXiv
  7. [7][7] A. Ashikhmin, E. Knill, Nonbinary Quantum Stabilizer Codes , IEEE Trans. Info. Theory 47 (2001), 3065-3072; arXiv:quant-ph/0005008. - · arXiv
  8. [8][8] C. Bennett, D. DiVincenzo, J. Smolin, and W. Wootters, Mixed state entanglement and quantum error correction , Phys. Rev. A 54 (1996), 3824-3851; arXiv:quant-ph/9604024. - · arXiv
  9. [9][9] P. O. Boykin, T. Mor, M. Pulver, V. Roychowdhury, and F. Vatan, On Universal and FaultTolerant Quantum Computing , Proc. 40th Ann. Symp. on Found. of Comp. Sci. (IEEE, New York, 1999), 486-494; arXiv:quant-ph/9906054. - · arXiv
  10. [10][10] S. Bravyi, A. Kitaev, Universal Quantum Computation with ideal Clifford gates and noisy ancillas , Phys. Rev. A 71 (2005), 022316; arXiv:quant-ph/0403025. - · arXiv
  11. [11][11] A. W. Cross, D. P. DiVincenzo, B. M. Terhal, A comparative code study for quantum faulttolerance , arXiv:0711.1556 [quant-ph] (2007). - · arXiv
  12. [12][12] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane, Quantum error correction and orthogonal geometry , Phys. Rev. Lett. 78 (1997), 405-408; arXiv:quant-ph/9605005. - · arXiv
  13. [13][13] , Quantum error correction via codes over GF(4), IEEE Trans. Inform. Theory 44 (1998), 1369-1387; arXiv:quant-ph/9605005. - · arXiv
  14. [14][14] A. R. Calderbank and P. W. Shor, Good quantum error-correcting codes exist , Phys. Rev. A 54 (1996), 1098-1105; arXiv:quant-ph/9512032. - · arXiv
  15. [15][15] A. Cross, G. Smith, J. A. Smolin, B. Zeng, Codeword Stabilized Quantum Codes , IEEE Trans. Info. Theory 55 (2009), 433-438; arXiv:0708.1021 [quant-ph]. - · arXiv
  16. [16][16] E. Dennis, A. Kitaev, A. Landahl, J. Preskill, Topological quantum memory , J. Math. Phys. 43 (2002), 4452-4505; arXiv:quant-ph/0110143. - · arXiv
  17. [17][17] D. Dieks, Communication by EPR devices , Phys. Lett. A 92 (1982), 271-272. -
  18. [18][18] B. Eastin, E. Knill, Restrictions on Transversal Encoded Quantum Gate Sets , arXiv: 0811.4262 [quant-ph] (2008). - · arXiv
  19. [19][19] Z. W. E. Evans, A. M. Stephens, Optimal decoding in fault-tolerant concatenated quantum error correction , arXiv:0902.4506v1 [quant-ph] (2009). - · arXiv
  20. [20][20] D. Gottesman, Class of quantum error-correcting codes saturating the quantum Hamming bound , Phys. Rev. A 54 (1996), 1862-1868; arXiv:quant-ph/9604038. - · arXiv
  21. [21][21] , Theory of fault-tolerant quantum computation , Phys. Rev. A 57 (1998), 127-137; arXiv:quant-ph/9702029. - · arXiv
  22. [22][22] , The Heisenberg Representation of Quantum Computers, in Group22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics (International Press, Cambridge, MA, 1999), eds. S. P. Corney, R. Delbourgo, and P. D. Jarvis, 32-43; arXiv:quant-ph/9807006. - · arXiv
  23. [23][23] , Fault-Tolerant Quantum Computation with Local Gates , J. Modern Optics 47 (2000), 333-345; arXiv:quant-ph/9903099. - · arXiv
  24. [24][24] , An Introduction to Quantum Error Correction , in Quantum Computation: A Grand Mathematical Challenge for the Twenty-First Century and the Millennium , ed. S. J. Lomonaco, Jr. (American Mathematical Society, Providence, Rhode Island, 2002), 221235; arXiv:quant-ph/0004072. - · arXiv
  25. [25][25] M. Grassl, T. Beth, and T. Pellizzari, Codes for the quantum erasure channel , Phys. Rev. A 56 (1997), 33-38; arXiv:quant-ph/9610042. - · arXiv
  26. [26][26] A. Ketkar, A. Klappenecker, S. Kumar, P. K. Sarvepalli, Nonbinary stabilizer codes over finite fields , IEEE Trans. Info. Theory 52 (2006), 4892-4914; arXiv:quant-ph/0508070. - · arXiv
  27. [28][28] A. Y. Kitaev, Quantum error correction with imperfect gates , Quantum Communication, Computing, and Measurement (Proc. 3rd Int. Conf. of Quantum Communication and Measurement) (Plenum Press, New York, 1997), p. 181-188. -
  28. [29][29] E. Knill, Non-binary Unitary Error Bases and Quantum Codes , arXiv:quant-ph/9608048 (1996). - · arXiv
  29. [30][30] , Quantum Computing with Realistically Noisy Devices , Nature 434 (2005), 39-44; E. Knill, Fault-tolerant Postselected Quantum Computation: Schemes , arXiv: quant-ph/0402171. - · arXiv
  30. [31][31] E. Knill and R. Laflamme, A theory of quantum error-correcting codes , Phys. Rev. A 55 (1997), 900-911; arXiv:quant-ph/9604034. - · arXiv
  31. [32][32] E. Knill, R. Laflamme, and W. H. Zurek, Threshold accuracy for quantum computation , arXiv:quant-ph/9610011; E. Knill, R. Laflamme, and W. H. Zurek, Resilient quantum computation , Science 279 (1998), 342-345; E. Knill, R. Laflamme, and W. H. Zurek, Resilient - quantum computation: error models and thresholds , Proc. Royal Soc. London A 454 (1998), 365-384, arXiv:quant-ph/9702058. - · arXiv
  32. [33][33] D. W. Kribs, R. Laflamme, D. Poulin, M. Lesosky, Operator quantum error correction , Quant. Inf. Comp. 6 (2006), 383-399; arXiv:quant-ph/0504189. - · arXiv
  33. [34][34] R. Laflamme, C. Miquel, J. P. Paz, and W. Zurek, Perfect quantum error correction code , Phys. Rev. Lett. 77 (1996), 198-201; arXiv:quant-ph/9602019. - · arXiv
  34. [35][35] D. A. Lidar and K. B. Whaley, Decoherence-Free Subspaces and Subsystems , in Irreversible Quantum Dynamics (Springer Lecture Notes in Physics 622 , Berlin, 2003), eds. F. Benatti and R. Floreanini, 83-120; arXiv:quant-ph/0301032. - · arXiv
  35. [36][36] D. Poulin, Stabilizer Formalism for Operator Quantum Error Correction , Phys. Rev. Lett. 95 (2005), 230504; arXiv:quant-ph/0508131. - · arXiv
  36. [37][37] , Optimal and Efficient Decoding of Concatenated Quantum Block Codes , Phys. Rev. A 74 (2006), 052333; arXiv:quant-ph/0606126. - · arXiv
  37. [38][38] R. Raussendorf, J. Harrington, Fault-tolerant quantum computation with high threshold in two dimensions , Phys. Rev. Lett. 98 (2007), 190504; arXiv:quant-ph/0610082; R. Raussendorf, J. Harrington, K. Goyal, Topological fault-tolerance in cluster state quantum computation , New J. Phys. 9 (2007), 199; arXiv: quant-ph/0703143. - · arXiv
  38. [39][39] B. W. Reichardt, Improved ancilla preparation scheme increases fault-tolerant threshold , arXiv:quant-ph/0406025. - · arXiv
  39. [40][40] , Improved magic states distillation for quantum universality , Quant. Inf. Proc. 4 (2005), 251-264; arXiv:quant-ph/0411036. - · arXiv
  40. [41][41] , Fault-tolerance threshold for a distance-three quantum code , arXiv:quant-ph/0509203 (2005). - · arXiv
  41. [42][42] , Error-Detection-Based Quantum Fault Tolerance Against Discrete Pauli Noise , Berkeley Ph.D. thesis (1996); arXiv:quant-ph/0612004. - · arXiv
  42. [43][43] P. W. Shor, Scheme for reducing decoherence in quantum memory , Phys. Rev. A 52 (1995), 2493-2496. -
  43. [44][44] , Fault-tolerant quantum computation , Proc. 35th Ann. Symp. on Foundations of Computer Science (IEEE Press, Los Alamitos, 1996), pp. 56-65; arXiv:quant-ph/9605011. - · arXiv
  44. [46][46] A. M. Steane, Error correcting codes in quantum theory , Phys. Rev. Lett. 77 (1996), 793-797. -
  45. [47][47] , Multiple particle interference and quantum error correction , Proc. Roy. Soc. London A 452 (1996), 2551-2577; arXiv:quant-ph/9601029. - · arXiv
  46. [48][48] , Active stabilization, quantum computation, and quantum state synthesis , Phys. Rev. Lett. 78 (1997), 2252; arXiv:quan-ph/9611027. -
  47. [49][49] , Overhead and noise threshold of fault-tolerant quantum error correction , Phys. Rev. A 68 (2003), 042322 [19 pages]; arXiv:quant-ph/0207119. - · arXiv
  48. [50][50] A. M. Stephens, A. G. Fowler, L. C. L. Hollenberg, Universal fault tolerant quantum computation on bilinear nearest neighbor arrays , Quant. Info. Comp. 8 (2008), 330; arXiv:quant-ph/0702201. - · arXiv
  49. [51][51] K. M. Svore, D. P. DiVincenzo, B. M. Terhal, Noise Threshold for a FaultTolerant Two-Dimensional Lattice Architecture , Quant. Inf. Comp. 7 (2007), 297-318; arXiv:quant-ph/0604090. - · arXiv
  50. [52][52] B. M. Terhal and G. Burkard, Fault-tolerant quantum computation for local non-Markovian noise , Phys. Rev. A 71 (2005), 012336; arXiv:quant-ph/0402104. - · arXiv
  51. [53][53] L. Viola, E. Knill, S. Lloyd, Dynamical Decoupling of Open Quantum Systems , Phys. Rev. Lett. 82 (1999), 2417-2421; arXiv:quant-ph/9809071. - · arXiv
  52. [54][54] W. K. Wooters and W. H. Zurek, A single quantum cannot be cloned , Nature 299 (1982), 802-803. -
  53. [55][55] X. Zhou, D. W. Leung, I. L. Chuang, Methodology for quantum logic gate constructions , Phys. Rev. A 62 (2000), 052316; arXiv:quant-ph/0002039. ``` Perimeter Institute for Theoretical Physics, Waterloo, ON N2L 2Y5, Canada E-mail address : dgottesman@perimeterinstitute.ca URL : http://www.perimeterinstitute.ca/personal/dgottesman/ ``` · arXiv

Cited by

Sorted by citations

Related

Authors
Gottesman, D.
Corresponding author
Gottesman, Daniel
ORCID
Gottesman, Daniel
Venue
arXiv
Publisher
arXiv
Published
2009
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.0904.2557
arXiv
0904.2557
OpenAlex
W4394642796
Cited by
129
References
0
Citations by year
2026: 1 · 2025: 6 · 2024: 18 · 2023: 9 · 2022: 17 · 2021: 20 · 2020: 16 · 2019: 8 · 2018: 6 · 2017: 4 · 2016: 3 · 2015: 4 · 2014: 5 · 2013: 4 · 2012: 2
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
  • Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
Keywords
quantum error correction, fault-tolerant quantum computing, quantum error-correcting codes, stabilizer formalism, finite abelian groups, threshold theorem, qubit encoding, quantum gates

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review