Conference paper · 2025 · Open access

Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads

Quynh T. Nguyen, Christopher A. Pattison

ACM Symposium on Theory of Computing (STOC), 730–737 · Published 15 June 2025 · DOI 10.1145/3717823.3718318

Open PDFView at the publisherCite this paper

In brief

“Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads” is a 2025 conference paper by Quynh T. Nguyen and Christopher A. Pattison, published in ACM Symposium on Theory of Computing (STOC). OpenAlex counts 66 citations as of 21 November 2026, which puts it in the top 1% of works published in 2025 by citations. It is open access: the full text is free to read at arXiv (Cornell University).

Citations
66
Most cited in
2026 (42)
Field-weighted impact
11.75
References
69
Authors
2

Abstract

In a model of fault-tolerant quantum computation with quick and noiseless polyloglog-time auxiliary classical computation, we construct a fault tolerance protocol with constant-space and $\widetilde{O}(\log N)$-time overhead, where $\widetilde{O}(\cdot)$ hides sub-polylog factors. Our construction utilizes constant-rate quantum locally testable codes (qLTC), new fault-tolerant gadgets on qLTCs and qLDPC codes, and a new analysis framework. In particular, 1) we develop a new simple and self-contained construction of magic state distillation for qubits using qudit quantum Reed-Solomon codes with $(\log \frac{1}{\varepsilon})^γ$ spacetime overhead, where $γ\rightarrow 0$. 2) We prove that the recent family of almost-good qLTCs of Dinur-Lin-Vidick admit parallel single-shot decoders against adversarial errors of weight scaling with the code distance. 3) We develop logical state preparation and logical gate procedures with $\widetilde{O}(1)$-spacetime overhead on qLTCs. 4) To combine these ingredients, we introduce a new framework of fault tolerance analysis called the weight enumerator formalism. The framework permits easy formal composition of fault-tolerant gadgets, so we expect it to be of independent interest. Our work gives the lowest spacetime overhead to date, which, for the first time, matches that of classical fault tolerance up to sub-polylog factors. We conjecture this is optimal up to sub-polylog factors.

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Nguyen, Q. T., & Pattison, C. A. (2025). Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads. ACM Symposium on Theory of Computing (STOC), 730–737. https://doi.org/10.1145/3717823.3718318

MLA 9

Nguyen, Quynh T., and Christopher A. Pattison. “Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads.” ACM Symposium on Theory of Computing (STOC), 2025, pp. 730–737. https://doi.org/10.1145/3717823.3718318.

Chicago

Nguyen, Quynh T. and Christopher A. Pattison. 2025. “Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads.” ACM Symposium on Theory of Computing (STOC): 730–737. https://doi.org/10.1145/3717823.3718318.

Harvard

Nguyen, Q. T. and Pattison, C. A. (2025) ‘Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads’, ACM Symposium on Theory of Computing (STOC), pp. 730–737. doi:10.1145/3717823.3718318.

IEEE

Q. T. Nguyen and C. A. Pattison, “Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads,” ACM Symposium on Theory of Computing (STOC), pp. 730–737, 2025, doi: 10.1145/3717823.3718318.

BibTeX

@inproceedings{nguyen2025quantum,
  title     = {{Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads}},
  author    = {Nguyen, Quynh T. and Pattison, Christopher A.},
  booktitle = {ACM Symposium on Theory of Computing (STOC)},
  year      = {2025},
  pages     = {730--737},
  doi       = {10.1145/3717823.3718318},
  url       = {https://doi.org/10.1145/3717823.3718318}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Topic and keywords

Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture

  • fault-tolerant quantum computing
  • magic state distillation
  • qLDPC codes
  • logic gates

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

Nguyen, Q. T., & Pattison, C. A. (2025). Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads. ACM Symposium on Theory of Computing (STOC), 730–737. https://doi.org/10.1145/3717823.3718318

How many times has this paper been cited?

66 times, according to OpenAlex on 21 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access at arXiv (Cornell University): sign in and open the PDF from this page.

Who wrote this paper?

Quynh T. Nguyen, Christopher A. Pattison.

What is the DOI of this paper?

10.1145/3717823.3718318, permanently at https://doi.org/10.1145/3717823.3718318. Sign in and open it from this page.

Bibliographic data from OpenAlex (CC0), last checked 21 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.