Fault-Tolerant quantum computation with constant overhead
The DOI matches its Crossref record; 44 of the 44 references it cites were found in a registry or an index.
Abstract
What is the minimum number of extra qubits needed to perform a large fault-tolerant quantum circuit? Working in a common model of fault-tolerance, I show that in the asymptotic limit of large circuits, the ratio of physical qubits to logical qubits can be a constant. The construction makes use of quantum low-density parity check codes, and the asymptotic overhead of the protocol is equal to that of the family of quantum error-correcting codes underlying the fault-tolerant protocol.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Low-density parity-check codes
Gallager, R. (1962) · IEEE Transactions on Information Theory · doi:10.1109/tit.1962.1057683 · Cited by 10,602
Gottesman, D., & Chuang, I. L. (1999) · Nature · doi:10.1038/46503 · Cited by 1,860
Self-citationMaximum matching and a polyhedron with 0,1-vertices
Edmonds, J. (1965) · Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics · doi:10.6028/jres.069b.013 · Cited by 1,712 · cited 1×
“The advantage of the 2-D hyperbolic surface codes is that there are standard algorithms for efficiently decoding surface codes, such as Edmonds’ maximum matching algorithm [9].”
MethodDennis, E., Kitaev, A., Landahl, A., & Preskill, J. (2001) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,485
Quantum computations: algorithms and error correction
Kitaev, A. Y. (1997) · Russian Mathematical Surveys · doi:10.1070/rm1997v052n06abeh002155 · Cited by 1,424
Quantum computing with realistically noisy devices
Knill, E. (2005) · Nature · doi:10.1038/nature03350 · Cited by 1,184 · cited 1×
“Asymptotically, this is a very favorable scaling of overhead (ratio of physical qubits to logical qubits), but in practice the constant factors hidden by the big-O notation are quite large, ranging from hundreds or thousands for the most efficient known protocols to billions for protocols maximally optimized for high…”
BackgroundTheory of fault-tolerant quantum computation
Gottesman, D. (1998) · Physical Review A · doi:10.1103/physreva.57.127 · Cited by 947 · cited 2×
“[13] showed that fault-tolerant protocols exist for stabilizer codes encoding multiple qubits per block, with further improvements in [34].”
BackgroundMethodSelf-citationSipser, M., & Spielman, D. A. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556667 · Cited by 931
Fault-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
Fault-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 · cited 1×
“Indeed, the same arguments used in this paper can also show the existence of a threshold for the toric code, yet simulations suggest that the threshold for fault-tolerant protocols for the toric code is much better than would be implied by the proofs used here [27].”
BackgroundFault-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 · cited 3×
“Using concatenated codes, we can perform a universal set of gates provided the physical error rate per location is below a threshold value [1, 19, 23].”
BackgroundMethodFault-Tolerant Quantum Computation with Constant Error Rate
Aharonov, D., & Ben-Or, M. (2008) · SIAM Journal on Computing · doi:10.1137/s0097539799359385 · Cited by 513 · cited 2×
“It is possible to prove a threshold theorem with gates that only interact nearest-neighbor qubits in one or two dimensions [2, 7, 14], but this requires codes for which most of the stabilizer generators are physically local.”
BackgroundMethodFAULT-TOLERANT QUANTUM COMPUTATION
PRESKILL, J. (1998) · Introduction to Quantum Computation and Information · doi:10.1142/9789812385253_0008 · Cited by 466
Restrictions on Transversal Encoded Quantum Gate Sets
Eastin, B., & Knill, E. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.110502 · Cited by 457 · cited 2×
“However, transversal gates can never be universal [8].”
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-citationAn introduction to quantum error correction and fault-tolerant quantum computation
Gottesman, D. (2010) · Proceedings of Symposia in Applied Mathematics · doi:10.1090/psapm/068/2762145 · Cited by 370
Self-citationResilient 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 · cited 2×
“Using concatenated codes, we can perform a universal set of gates provided the physical error rate per location is below a threshold value [1, 19, 23].”
BackgroundMethodActive Stabilization, Quantum Computation, and Quantum State Synthesis
Steane, A. M. (1997) · Physical Review Letters · doi:10.1103/physrevlett.78.2252 · Cited by 323 · cited 1×
“One of the primary components of any fault-tolerant protocol is error correction. There are three main methods of fault-tolerant error correction — Shor error correction [31], Steane error correction [33], and Knill error correction [22]. Steane and Knill EC require large ancilla blocks, consisting of specific states e…”
MethodResilient 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 296
Tillich, J.-P., & Zemor, G. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2292061 · Cited by 288
Lab., N. (. S. L. A. N., Knill, E., USDOE, W., & Laflamme, R. (1996) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · doi:10.2172/369608 · Cited by 239 · cited 1×
“The procedure results in a physical error rate per physical qubit of |Ψ〉 which is bounded by some constant value [22].”
BackgroundTradeoffs for Reliable Quantum Information Storage in 2D Systems
Bravyi, S., Poulin, D., & Terhal, B. (2010) · Physical Review Letters · doi:10.1103/physrevlett.104.050503 · Cited by 191 · cited 1×
“Codes for which all syndrome bits can be locally measured do not seem capable of encoding qubits without an overhead that grows as the system size grows [6], but there may be some possibility of a result comparable to Thm.”
ResultFault-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 · cited 2×
“The assumption of stochastic noise can largely be relaxed, and a threshold exists for noise caused by fairly general interactions with a non-Markovian environment [3, 35].”
BackgroundParallel Quantum Computation and Quantum Codes
Moore, C., & Nilsson, M. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539799355053 · Cited by 173 · cited 1×
“Every stabilizer code can be encoded using a parallel circuit [26], so the overall depth of the ancilla preparation procedure is just O(polylog(|D|/ǫ0)).”
BackgroundFault-tolerant quantum computation with local gates
Gottesman, D. (2000) · Journal of Modern Optics · doi:10.1080/09500340008244046 · Cited by 136 · cited 1×
“It is possible to prove a threshold theorem with gates that only interact nearest-neighbor qubits in one or two dimensions [2, 7, 14], but this requires codes for which most of the stabilizer generators are physically local.”
BackgroundSelf-citationAn Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation
Gottesman, D. (2009) · arXiv · doi:10.48550/arxiv.0904.2557 · Cited by 129
Self-citationEfficient fault-tolerant quantum computing
Steane, A. M. (1998) · RePEc: Research Papers in Economics · Cited by 128
Fault-tolerant quantum computationPreprint
Preskill, J. P. (1997) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9712048 · Cited by 124
Fault tolerance of quantum low-density parity check codes with sublinear distance scaling
Kovalev, A. A., & Pryadko, L. P. (2013) · Physical Review A · doi:10.1103/physreva.87.020304 · Cited by 107
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 · cited 2×
“In [4], the lemma is stated to provide a bound on the number of connected sets of size s containing S, but the proof also provides a bound (as stated above) on the number of collections of clusters, each of which contains an element of S.”
BackgroundSelf-citationZ2-systolic freedom and quantum codes
Freedman, M. H., Meyer, D., & Luo, F. (2002) · Chapman & Hall/CRC eBooks · doi:10.1201/9781420035377-13 · Cited by 95
Quantum accuracy threshold for concatenated distance-3 codes
Aliferis, P., Gottesman, D., & Preskill, J. P. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0504218 · Cited by 86 · cited 3×
“The argument I have described above uses a somewhat different approach from the threshold proof in [4]; in terms of the tools from that paper, one could phrase the argument here as a process that replaces”
BackgroundInfluentialSelf-citationImproved quantum hypergraph-product LDPC codes
Kovalev, A. A., & Pryadko, L. P. (2012) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2012.6284206 · Cited by 83
Lower bounds for the complexity of reliable Boolean circuits with noisy gates
Gács, P., & Gál, A. (1994) · IEEE Transactions on Information Theory · doi:10.1109/18.312190 · Cited by 80 · cited 1×
“The most common model of classical fault-tolerant computation, where the input must first be encoded, requires logarithmic overhead [11, 28].”
BackgroundQUANTUM ERROR CORRECTING CODES AND 4-DIMENSIONAL ARITHMETIC HYPERBOLIC MANIFOLDSPreprint
Guth, L., & Lubotzky, A. (2013) · Cited by 77
Concatenated Quantum CodesPreprint
Knill, E. H., & Laflamme, R. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9608012 · Cited by 64 · cited 1×
“The procedure results in a physical error rate per physical qubit of |Ψ〉 which is bounded by some constant value [22].”
BackgroundQuantum RefrigeratorPreprint
Ben-Or, M., Gottesman, D., & Hassidim, A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.1995 · Cited by 60 · cited 1×
“The fresh ancilla qubits can be prepared by hand, or could be created via a suitable noise process that has the effect of cooling some qubits [5].”
BackgroundSelf-citationReliable computation with noisy circuits and decision trees-a general n log n lower bound
Reischuk, R., & Schmeltz, B. (2002) · doi:10.1109/sfcs.1991.185425 · Cited by 52 · cited 1×
“The most common model of classical fault-tolerant computation, where the input must first be encoded, requires logarithmic overhead [11, 28].”
BackgroundFault-tolerant logical gate networks for Calderbank-Shor-Steane codes
Steane, A. M., & Ibinson, B. (2005) · Physical Review A · doi:10.1103/physreva.72.052335 · Cited by 44
Fault-tolerant quantum computation with local gates
Gottesman, D. (2000) · Journal of Modern Optics · doi:10.1080/095003400148240 · Cited by 31
Self-citationDecoding in Hyperbolic Spaces: LDPC Codes With Linear Rate and Efficient Error CorrectionPreprint
Hastings, M. B. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1312.2546 · Cited by 13 · cited 5×
“However, while the main result of this paper applies to various known code families [10, 17, 18, 36], none of the families is quite satisfactory.”
BackgroundInfluentialScalable Quantum Computation in the Presence of Large Detected-Error RatesPreprint
Knill, E. H. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0312190 · Cited by 12 · cited 2×
“The most systematic approach is Knill’s method [21], which uses a particular logical state encoded in two blocks of the same stabilizer code used for the data.”
MethodReliable Computations Based on Locally Decodable Codes
Romashchenko, A. (2006) · Lecture notes in computer science · doi:10.1007/11672142_44 · Cited by 11 · cited 1×
“In a model where the inputs and outputs are provided in some suitable classical error-correcting code, the best known classical fault-tolerant protocol achieves O(log n/ log log n) overhead [29], and it is unknown if constant overhead is possible.”
BackgroundLow Density Parity Check Codes
Ball, S. (2020) · Compact textbooks in mathematics · doi:10.1007/978-3-030-41153-4_8 · Cited by 9
Cited by
Quantum error correction for quantum memories
Terhal, B. M. (2015) · Reviews of Modern Physics · doi:10.1103/revmodphys.87.307 · Cited by 1,354
“This question was analyzed and answered in the affirmative by Gottesman (2014).”
InfluentialMaterial platforms for spin-based photonic quantum technologies
Atatüre, M., Englund, D., Vamivakas, N., Lee, S.-Y., & Wrachtrup, J. (2018) · Nature Reviews Materials · doi:10.1038/s41578-018-0008-9 · Cited by 766
Cai, Z., Babbush, R., Benjamin, S. C., Endo, S., Huggins, W. J., Li, Y., McClean, J. R., & O’Brien, T. E. (2023) · Reviews of Modern Physics · doi:10.1103/revmodphys.95.045005 · Cited by 591
“There is ongoing theoretical research to find alternative codes with a more favourable overhead, and recent progress gives reasons to be optimistic (Breuckmann and Eberhardt, 2021; Dinur et al. , 2022; Gottesman, 2014; Panteleev and Kalachev, 2022).”
BackgroundHigh-threshold and low-overhead fault-tolerant quantum memory
Bravyi, S., Cross, A. W., Gambetta, J. M., Maslov, D., Rall, P., & Yoder, T. J. (2024) · Nature · doi:10.1038/s41586-024-07107-7 · Cited by 456
“This spurred interest in more general quantum codes known as low-density parity-check (LDPC) codes 6 .”
BackgroundMethodQuantum advantage with shallow circuits
Bravyi, S., Gosset, D., & König, R. (2018) · Science · doi:10.1126/science.aar3106 · Cited by 406
Metadata
- Authors
- Gottesman, D.
- Affiliations
- Perimeter Institute (CA)
- Corresponding author
- Gottesman, Daniel
- ORCID
- Gottesman, Daniel
- Venue
- Quantum Information and Computation
- Publisher
- Rinton Press
- Published
- 2014-11
- Volume
- 14
- Issue
- 15&16
- Pages
- 1339-1371
- ISSN
- 1533-7146 (ISSN-L)
- OpenAlex
- W1959392488
- Cited by
- 172
- References
- 40
- Citations by year
- 2026: 15 · 2025: 36 · 2024: 25 · 2023: 16 · 2022: 14 · 2021: 15 · 2020: 11 · 2019: 13 · 2018: 8 · 2017: 5 · 2016: 6 · 2015: 7 · 2014: 1
- FWCI
- 6.26
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Quantum Information and Computation (publishedVersion)
- Funders
- Government of Canada
- Industry Canada
- Institut Périmètre de physique théorique
- Division of Mathematical Sciences
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- fault-tolerant quantum computing, quantum low-density parity-check codes, quantum error-correcting codes, quantum circuits
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.