CoChat
Sign Up
Cited by 111Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyCoding theory and cryptography

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 access
Fawzi, Omar, Grospellier, Antoine, Leverrier, Anthony·2021·Communications of the ACM
DOI 10.1145/3434163
Open this paper in CoChat — free account

Abstract

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.

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

Integrity signals

Registry

Crossref · 10.1145/3434163

Cites

27 of 27 references verified0 citation errors · 0 not checkable

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.

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?

  • The quantum expander code family has parameters [Θ(ki), ki, Θ(√ki)] and enables a single-shot decoder with O(log(ki)) runtime even with noisy syndrome measurements.

    “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]

  • Fawzi et al. [273] instantiated the general Gottesman FTQC scheme using quantum expander code, which is a hypergraph product code [232] with classical expander codes as seed codes.

    “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]

  • Recent work shows only constant overhead is necessary, with logical qubits proportional to physical ones, suggesting no fundamental obstacle to a perfect digital quantum simulator.

    “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

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

  1. 10.1109/FOCS.2018.00076 · DOI · Paper page
  2. 10.1145/3188745.3188886 · DOI
  3. 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.
  4. 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
  5. 10.5555/2685179.2685184 · DOI
  6. 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

Related

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)
ORCID
Venue
Communications of the ACM
Publisher
Association for Computing Machinery (ACM)
Published
2020-12-17
Volume
64
Issue
1
Pages
106-114
ISSN
  • 0272-5428 (ISSN-L)
  • 0001-0782
  • 1557-7317
DOI
10.1145/3434163
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
Licence
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