An introduction to quantum error correction and fault-tolerant quantum computation
Open accessThe DOI matches its Crossref record; 64 of the 64 references it cites were found in a registry or an index.
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 errorcorrecting 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A single quantum cannot be cloned
Wootters, W. K., & Zurek, W. H. (1982) · Nature · doi:10.1038/299802a0 · Cited by 5,406 · cited 1×
“1 We might try a quantum repetition code: (3) However, no such code exists because of the No-Cloning theorem [ 17, 54 ]: Theorem 1 (No-Cloning) .”
MethodMixed-state entanglement and quantum error correction
Bennett, C. H., DiVincenzo, D. P., Smolin, J. A., & Wootters, W. K. (1996) · Physical Review A · doi:10.1103/physreva.54.3824 · Cited by 5,272
Scheme for reducing decoherence in quantum computer memory
Shor, P. W. (1995) · Physical Review A · doi:10.1103/physreva.52.r2493 · Cited by 4,479
Error Correcting Codes in Quantum Theory
Steane, A. M. (1996) · Physical Review Letters · doi:10.1103/physrevlett.77.793 · Cited by 2,677
Good quantum error-correcting codes exist
Calderbank, A. R., & Shor, P. W. (1996) · Physical Review A · doi:10.1103/physreva.54.1098 · Cited by 2,516 · cited 1×
“We could have used any two classical codes C 1 and C 2 [ 14, 47 ].”
MethodDynamical Decoupling of Open Quantum Systems
Viola, L., Knill, E., & Lloyd, S. (1999) · Physical Review Letters · doi:10.1103/physrevlett.82.2417 · Cited by 1,808 · cited 1×
“For instance, in dynamical decoupling [ 53 ], a series of quick operations is performed which cause the noise to cancel itself out.”
BackgroundDennis, E., Kitaev, A., Landahl, A., & Preskill, J. (2002) · Journal of Mathematical Physics · doi:10.1063/1.1499754 · Cited by 1,768
Theory of quantum error-correcting codes
Knill, E., & Laflamme, R. (1997) · Physical Review A · doi:10.1103/physreva.55.900 · Cited by 1,593
Universal quantum computation with ideal Clifford gates and noisy ancillas
Bravyi, S., & Kitaev, A. (2005) · Physical Review A · doi:10.1103/physreva.71.022316 · Cited by 1,525
Dennis, E., Kitaev, A., Landahl, A., & Preskill, J. (2001) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,485
Dieks, D. (1982) · Physics Letters A · doi:10.1016/0375-9601(82)90084-6 · Cited by 1,461
Classical and Quantum Computation
Kitaev, A., Shen, A., & Vyalyi, M. (2002) · Graduate Studies in Mathematics · doi:10.1090/gsm/047 · Cited by 1,387
Multiple-particle interference and quantum error correction
(1996) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1996.0136 · Cited by 1,284
Class of quantum error-correcting codes saturating the quantum Hamming bound
Gottesman, D. (1996) · Physical Review A · doi:10.1103/physreva.54.1862 · Cited by 1,227 · cited 1×
“The distance d of the code is the minimum weight of any operator in N ( S ) \ S [ 12, 20 ].”
BackgroundSelf-citationPerfect Quantum Error Correcting Code
Laflamme, R., Miquel, C., Paz, J. P., & Zurek, W. H. (1996) · Physical Review Letters · doi:10.1103/physrevlett.77.198 · Cited by 963
Theory of fault-tolerant quantum computation
Gottesman, D. (1998) · Physical Review A · doi:10.1103/physreva.57.127 · Cited by 947
Self-citationFault-tolerant quantum computation
Shor, P. W. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548464 · Cited by 892
Multiple particle interference and quantum error correction
Steane, A. M. (1996) · Cited by 871
Theory of Quantum Error Correction for General Noise
Knill, E., Laflamme, R., & Viola, L. (2000) · Physical Review Letters · doi:10.1103/physrevlett.84.2525 · Cited by 866 · cited 2×
“For large n , R = k/n and p = d/ 2 n fixed, the best nondegenerate quantum codes satisfy One further bound, known as the Knill-Laflamme bound [ 31 ] or the quantum Singleton bound, applies even to degenerate quantum codes.”
BackgroundFault-Tolerant Quantum Computation with High Threshold in Two Dimensions
Raussendorf, R., & Harrington, J. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.190504 · Cited by 812
Quantum Error Correction and Orthogonal Geometry
Calderbank, A. R., Rains, E. M., Shor, P. W., & Sloane, N. J. A. (1997) · Physical Review Letters · doi:10.1103/physrevlett.78.405 · Cited by 811 · cited 3×
“The distance d of the code is the minimum weight of any operator in N ( S ) \ S [ 12, 20 ].”
BackgroundKnill, E., Laflamme, R., & Zurek, W. H. (1998) · Science · doi:10.1126/science.279.5349.342 · Cited by 663
Fault-tolerant quantum computation with constant error
Aharonov, D., & Ben-Or, M. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258579 · Cited by 631
Nonbinary quantum stabilizer codes
Ashikhmin, A., & Knill, E. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.959288 · Cited by 625
Nonbinary Stabilizer Codes Over Finite Fields
Ketkar, A., Klappenecker, A., Kumar, S., & Sarvepalli, P. K. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.883612 · Cited by 623
Topological fault-tolerance in cluster state quantum computation
Raussendorf, R., Harrington, J., & Goyal, K. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/199 · Cited by 617
Fault-Tolerant Quantum Computation with Constant Error Rate
Aharonov, D., & Ben-Or, M. (2008) · SIAM Journal on Computing · doi:10.1137/s0097539799359385 · Cited by 513
The Heisenberg Representation of Quantum Computers
Gottesman, D. (1998) · arXiv · doi:10.48550/arxiv.quant-ph/9807006 · Cited by 489
Self-citationRestrictions on Transversal Encoded Quantum Gate Sets
Eastin, B., & Knill, E. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.110502 · Cited by 457 · cited 1×
“One might hope to avoid this by finding a better code, but in fact, no code allows a universal set of transversal gates [ 18 ].”
BackgroundQuantum accuracy threshold for concatenated distance-3 code
Aliferis, P., Gottesman, D., & Preskill, J. (2006) · Quantum Information and Computation · doi:10.26421/qic6.2-1 · Cited by 412
Self-citationThe Heisenberg Representation of Quantum ComputersPreprint
Gottesman, D. (1998) · arXiv (Cornell University) · Cited by 403
Self-citationCodes for the quantum erasure channel
Grassl, M., Beth, T., & Pellizzari, T. (1997) · Physical Review A · doi:10.1103/physreva.56.33 · Cited by 374 · cited 1×
“Thus, all products E † a E b in condition (30) have weight r or less, so this sort of error (an “erasure” error [ 25 ]) can be corrected by a code of distance r +1.”
BackgroundOverhead and noise threshold of fault-tolerant quantum error correction
Steane, A. M. (2003) · Physical Review A · doi:10.1103/physreva.68.042322 · Cited by 372
Methodology for quantum logic gate construction
Zhou, X., Leung, D. W., & Chuang, I. L. (2000) · Physical Review A · doi:10.1103/physreva.62.052316 · Cited by 355
Resilient quantum computation: error models and thresholds
Knill, E., Laflamme, R., & Zurek, W. H. (1998) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1998.0166 · Cited by 346
Stabilizer Formalism for Operator Quantum Error Correction
Poulin, D. (2005) · Physical Review Letters · doi:10.1103/physrevlett.95.230504 · Cited by 342
Active Stabilization, Quantum Computation, and Quantum State Synthesis
Steane, A. M. (1997) · Physical Review Letters · doi:10.1103/physrevlett.78.2252 · Cited by 323
Resilient Quantum Computation: Error Models and Thresholds
Knill, E. H., Laflamme, R., & Zurek, W. H. (1997) · CERN Document Server (European Organization for Nuclear Research) · Cited by 295
Decoherence-Free Subspaces and Subsystems
Lidar, D. A., & Birgitta Whaley, K. (2003) · Lecture Notes in Physics · doi:10.1007/3-540-44874-8_5 · Cited by 290
Quantum Error Correction with Imperfect Gates
Kitaev, A. Y. (1997) · Quantum Communication, Computing, and Measurement · doi:10.1007/978-1-4615-5923-8_19 · Cited by 214 · cited 1×
“…that, provided that the physical error rate per gate and per time step is below some constant threshold value, it is possible to make the logical quantum computation we wish to perform arbitrarily close to correct with overhead that is polylogarithmic in the length of the computation [ 1, 28, 32 ].”
BackgroundFault-tolerant quantum computation against biased noise
Aliferis, P., & Preskill, J. (2008) · Physical Review A · doi:10.1103/physreva.78.052331 · Cited by 204
A new universal and fault-tolerant quantum basis
Boykin, P. O., Mor, T., Pulver, M., Roychowdhury, V., & Vatan, F. (2000) · Information Processing Letters · doi:10.1016/s0020-0190(00)00084-3 · Cited by 194
Fault-tolerant quantum computation for local non-Markovian noise
Terhal, B. M., & Burkard, G. (2005) · Physical Review A · doi:10.1103/physreva.71.012336 · Cited by 181
Codeword Stabilized Quantum Codes
Cross, A. W., Smith, G., Smolin, J. A., & Zeng, B. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.2008136 · Cited by 156
Quantum Universality from Magic States Distillation Applied to CSS Codes
Reichardt, B. W. (2005) · Quantum Information Processing · doi:10.1007/s11128-005-7654-8 · Cited by 143
Non-binary unitary error bases and quantum codes
Knill, E. (1996) · doi:10.2172/373768 · Cited by 126
Fault-tolerant quantum computation with local gates
Gottesman, D. (2000) · Journal of Modern Optics · doi:10.1080/09500340008244046 · Cited by 124
Self-citationAn Introduction to Quantum Error CorrectionPreprint
Gottesman, D. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0004072 · Cited by 107
Self-citationOptimal and efficient decoding of concatenated quantum block codes
Poulin, D. (2006) · Physical Review A · doi:10.1103/physreva.74.052333 · Cited by 105 · cited 1×
“Recent work indicates that thresholds can be improved by not treating each level of concatenation separately, but by allowing the EC gadgets to use error information generated by the lower-level error correction procedures [ 6, 19, 37 ].”
MethodThreshold Accuracy for Quantum Computation
Knill, E., Laflamme, R., & Zurek, W. (1996) · arXiv · doi:10.48550/arxiv.quant-ph/9610011 · Cited by 99
Accuracy threshold for postselected quantum computation
Aliferis, P., Gottesman, D., & Preskill, J. (2008) · Quantum Information and Computation · doi:10.26421/qic8.3-4-1 · Cited by 96
Self-citationOperator quantum error correction
Kribs, D., & Poulin, D. (2013) · Quantum Error Correction · doi:10.1017/cbo9781139034807.008 · Cited by 92
On Universal and Fault-Tolerant Quantum Computing
Boykin, P. O., Mor, T., Pulver, M., Roychowdhury, V., & Vatan, F. (1999) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9906054 · Cited by 79
Noise Threshold for a Fault-Tolerant Two-Dimensional Lattice ArchitecturePreprint
Svore, K. M., Divincenzo, D. P., & Terhal, B. M. (2006) · Cited by 63
Universal quantum computation with ideal Clifford gates and noisy ancillas (14 pages)
Kitaev, A., & Bravyi, S. (2005) · Physical Review A · Cited by 56
Limitations of Noisy Reversible Computation
Aharonov, D., Ben-Or, M., Impagliazzo, R., & Nisan, N. (1996) · arXiv (Cornell University) · doi:10.4230/lipics.ccc.2026.38 · Cited by 53
A comparative code study for quantum fault tolerance
Cross, A. W., DiVincenzo, D. P., & Terhal, B. M. (2009) · Quantum Information and Computation · doi:10.26421/qic9.7-8-1 · Cited by 48
Fibonacci scheme for fault-tolerant quantum computation
Aliferis, P., & Preskill, J. (2009) · Physical Review A · doi:10.1103/physreva.79.012332 · Cited by 47
Universal fault tolerant quantum computation on bilinear nearest neighbor arrays
Stephens, A. M., Fowler, A. G., & Hollenberg, L. C. L. (2008) · Quantum Information and Computation · doi:10.26421/qic8.3-4-7 · Cited by 44
Error-detection-based quantum fault tolerance against discrete Pauli noisePreprint
Reichardt, B. W. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0612004 · Cited by 44
Improved ancilla preparation scheme increases fault-tolerant threshold
Reichardt, B. W. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0406025 · Cited by 34
Perfect Quantum Error Correction CodePreprint
Laflamme, R., Miquel, C., Paz, J. P., & Zurek, W. H. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9602019 · Cited by 34
Optimal correction of concatenated fault-tolerant quantum codes
Evans, Z. W. E., & Stephens, A. M. (2011) · Quantum Information Processing · doi:10.1007/s11128-011-0312-4 · Cited by 14
Optimal decoding in fault-tolerant concatenated quantum error correctionPreprint
Evans, Z. W. E., & Stephens, A. M. (2009) · arXiv (Cornell University) · Cited by 2
Cited by
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830
“materials and control and fabrication to get where we are now. Eventually we expect to be able to protect quantum systems and scale up quantum computers using the principle of quantum errorcorrection [10]. The essential idea of quantum error correction is that if we want to protect a quantum system from damage then we…”
BackgroundA quantum engineer's guide to superconducting qubits
Krantz, P., Kjaergaard, M., Yan, F., Orlando, T. P., Gustavsson, S., & Oliver, W. D. (2019) · Applied Physics Reviews · doi:10.1063/1.5089550 · Cited by 2,004
Quantum error correction for quantum memories
Terhal, B. M. (2015) · Reviews of Modern Physics · doi:10.1103/revmodphys.87.307 · Cited by 1,354
Parameterized quantum circuits as machine learning models
Benedetti, M., Lloyd, E., Sack, S., & Fiorentini, M. (2019) · Quantum Science and Technology · doi:10.1088/2058-9565/ab4eb5 · Cited by 1,144
Quantum error correction for beginners
Devitt, S. J., Munro, W. J., & Nemoto, K. (2013) · Reports on Progress in Physics · doi:10.1088/0034-4885/76/7/076001 · Cited by 759
Metadata
- Authors
- Gottesman, D.
- Venue
- Proceedings of Symposia in Applied Mathematics
- Publisher
- American Mathematical Society
- Published
- 2010
- Pages
- 13-58
- ISSN
- 0160-7634 (ISSN-L)
- 2324-7088
- OpenAlex
- W1675244148
- Cited by
- 370
- References
- 64
- Type
- other
- Language
- en
- Open access
- bronze
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.