Conference paper · 2025 · Open access
Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads
ACM Symposium on Theory of Computing (STOC), 730–737 · Published 15 June 2025 · DOI 10.1145/3717823.3718318
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
- ImageNet classification with deep convolutional neural networksAlex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton · Communications of the ACM · 2017 · 114,726 citations
- Long Short-Term MemorySepp Hochreiter, Jürgen Schmidhuber · Neural Computation · 1997 · 109,097 citations
- A Mathematical Theory of CommunicationClaude E. Shannon · Bell System Technical Journal · 1948 · 91,736 citations
- Deep learningYann LeCun, Yoshua Bengio, Geoffrey E. Hinton · Nature · 2015 · 90,226 citations
- Faster R-CNN: Towards Real-Time Object Detection with Region Proposal NetworksShaoqing Ren, Kaiming He, Ross Girshick and 1 more · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2016 · 74,143 citations
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.