The DOI matches its Crossref record; 27 of the 28 references it cites were found in a registry or an index.
Constant overhead quantum fault tolerance with quantum expander codes
Open accessAbstract
The threshold theorem is a seminal result in the field of quantum computing asserting that arbitrarily long quantum computations can be performed on a faulty quantum computer provided that the noise level is below some constant threshold. This remarkable result comes at the price of increasing the number of qubits (quantum bits) by a large factor that scales polylogarithmically with the size of the quantum computation we wish to realize. Minimizing the space overhead for fault-tolerant quantum computation is a pressing challenge that is crucial to benefit from the computational potential of quantum devices. In this paper, we study the asymptotic scaling of the space overhead needed for fault-tolerant quantum computation. We show that the polylogarithmic factor in the standard threshold theorem is in fact not needed and that there is a fault-tolerant construction that uses a number of qubits that is only a constant factor more than the number of qubits of the ideal computation. This result was conjectured by Gottesman who suggested to replace the concatenated codes from the standard threshold theorem by quantum error-correcting codes with a constant encoding rate. The main challenge was then to find an appropriate family of quantum codes together with an efficient classical decoding algorithm working even with a noisy syndrome. The efficiency constraint is crucial here: bear in mind that qubits are inherently noisy and that faults keep accumulating during the decoding process. The role of the decoder is therefore to keep the number of errors under control during the whole computation. On a technical level, our main contribution is the analysis of the SMALL-SET-FLIP decoding algorithm applied to the family of quantum expander codes . We show that it can be parallelized to run in constant time while correcting sufficiently many errors on both the qubits and the syndrome to keep the error under control. These tools can be seen as a quantum generalization of the BIT-FLIP algorithm applied to the (classical) expander codes of Sipser and Spielman.
Overview
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.
Integrity signals
Registry
Cites
Statistics
Verification
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.
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?
The cited source says what the claim attributes to it.
In the citing paper
“The quantum expander code family has a parameter of”
From Quantum error correction and fault tolerance: A comprehensive tutorial (2026) · cites this paper as Fawzi et al. [273]
The cited source says what the claim attributes to it.
In the citing paper
“This was solved first in the work by Fawzi et al. [273], where the general Gottesman FTQC scheme is instantiated using quantum expander code (which is a hypergraph product code [232] with classical expander codes as seed codes).”
From Quantum error correction and fault tolerance: A comprehensive tutorial (2026) · cites this paper as Fawzi et al. [273]
In the citing paper
“Whereas recently, it has been shown that only a constant overhead is necessary (i.e. the number of logical qubits is proportional to the number of physical ones) [117] and one may therefore generally see no fundamental obstacle to building a perfect digital quantum simulator in the future”
From Quantum Computing for Molecular Biology** (2023) · cites this paper as [117]
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 Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb01338.x · Cited by 88,486
Low-density parity-check codes
Gallager, R. G. (1962) · IEEE Transactions on Information Theory · doi:10.1109/tit.1962.1057683 · Cited by 10,727
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
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
Maximum 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,738
Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable Components
von Neumann, J. (1956) · Princeton University Press eBooks · doi:10.1515/9781400882618-003 · Cited by 1,463
Fault-tolerant quantum computation
Shor, P. W. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1996.548464 · Cited by 1,108
Sipser, M., & Spielman, D. A. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556667 · Cited by 945
Flagged first, then by citations
1 of the 28 references couldn’t be matched to a known paper.
Research works printed but not linked: 6
- 10.1109/FOCS.2018.00076 · DOI · Paper page
- 10.1145/3188745.3188886 · DOI
- Fowler , A.G. , Mariantoni , M. , Martinis , J.M. , Cleland , A.N. Surface codes : Towards practical large-scale quantum computation . Phys. Rev. A 3 , 86 ( 2012 ), 032324. Fowler, A.G., Mariantoni, M., Martinis, J.M., Cleland, A.N. Surface codes: Towards practical large-scale quantum computation. Phys. Rev. A 3, 86 (2012), 032324.
- Gidney , C. , Ekerå , M. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. arXiv preprint arXiv:1905.09749 ( 2019 ). Gidney, C., Ekerå, M. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. arXiv preprint arXiv:1905.09749 (2019). · arXiv
- 10.5555/2685179.2685184 · DOI
- Grouès , L. , Grospellier , A. , Krishna , A. , Leverrier , A. Combining hard and soft decoding for hypergraph product codes. arXiv preprint arXiv:2004.11199 ( 2020 ). Grouès, L., Grospellier, A., Krishna, A., Leverrier, A. Combining hard and soft decoding for hypergraph product codes. arXiv preprint arXiv:2004.11199 (2020). · arXiv
Cited by
Sorted by citations
Items 101–111 of 111
Quantum LDPC Codes Based on Cocyclic Block Matrices
Cai, Y., & Guo, Y. (2023) · Entropy · doi:10.3390/e25091309
Shiraishi, K., Yamasaki, H., & Murao, M. (2024) · Physical Review A · doi:10.1103/physreva.110.052617
Mean Estimation in High-Dimensional Binary Timeinhomogeneous Markov Gaussian Mixture Models
Kadry, A. E. L., Zhang, Y., & Weinberger, N. (2025) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit63088.2025.11195426
Improved energy barrier in higher-dimensional hypergraph product codes
Zhao, G. (2025) · Physical Review A · doi:10.1103/b9r5-xhcp · Cited by 1
Enhancing decoding performance using efficient error learning
Iyer, P. S., Jain, A., Bartlett, S. D., & Emerson, J. (2026) · Physical Review Applied · doi:10.1103/vtj7-nh6l · Cited by 6
Decoding of LDPC quantum codes
Grouès, L. (2022) · doi:10.70675/4405a9b9z4ce7z49bez9fc0z6b5a10ebf2d1
BiBiEQ: Bivariate Bicycle Codes on Erasure Qubits
Bhave, A., Choudhury, N., Nemec, A., & Basu, K. (2026) · International Conference on Quantum Communications, Networking, and Computing (QCNC) · doi:10.1109/qcnc69040.2026.00101
Expander quantum low density parity check codes against long-range correlated errors in memory
Kashtikar, Y. D., Mathur, P., Senthil, S., & Chatterjee, A. (2026) · Physical Review A · doi:10.1103/q4pw-zwcv
Coset Ensemble Decoder for Quantum Error Correction with Algorithm-Hardware Co-Design
Liang, S., Xu, J., Bassanino, G., Wang, Q., Zhou, Y., Lu, Y., Mo, Z., Kelly, P. H. J., Yuan, B., Luk, W. W., et al. (2026) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca66397.2026.00070
Metadata
- Authors
- Fawzi, O., Grospellier, A., & Leverrier, A.
- Affiliations
- Lyon 1 Université (FR)
- Institut national de recherche en sciences et technologies du numérique (FR)
- Venue
- Communications of the ACM
- Published
- 2020-12-17
- Volume
- 64
- Issue
- 1
- Pages
- 106-114
- ISSN
- 0272-5428 (ISSN-L)
- 0001-0782
- 1557-7317
- OpenAlex
- W2886337778
- Cited by
- 111
- References
- 28
- Citations by year
- 2026: 7 · 2025: 25 · 2024: 20 · 2023: 15 · 2022: 12 · 2021: 17 · 2020: 5
- FWCI
- 3.27
- Type
- conference paper
- Language
- en
- Open access
- green
- inria.hal.science
- Locations
- Annual Symposium on Foundations of Computer Science (publishedVersion)
- Communications of the ACM (publishedVersion)
- HAL (publishedVersion, other-oa)
- arXiv (Cornell University) (submittedVersion)
- HAL (submittedVersion)
- HAL (submittedVersion, cc-by)
- arXiv (Cornell University)
- Funders
- Agence Nationale de la Recherche (QuantERA project QCDA)
- 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 › Mathematics › Discrete Mathematics and Combinatorics › Coding theory and cryptography
- Keywords
- quantum fault tolerance, threshold theorem, space overhead, quantum error-correcting codes, syndrome decoding
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
