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].”
Background
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Fault-Tolerant quantum computation with constant overhead. https://app.cochat.ai/papers/10.26421/qic14.15-16-5
- The paper
- Gottesman, D. (2014). Fault-Tolerant quantum computation with constant overhead. Quantum Information and Computation. https://doi.org/10.26421/qic14.15-16-5
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.