Journal article · 2008 · Open access
Fault-Tolerant Quantum Computation with Constant Error Rate
SIAM Journal on Computing, 38(4), 1207–1282 · Published 1 January 2008 · DOI 10.1137/s0097539799359385
In brief
“Fault-Tolerant Quantum Computation with Constant Error Rate” is a 2008 journal article by Dorit Aharonov and Michael Ben-Or, published in SIAM Journal on Computing. OpenAlex counts 967 citations as of 20 November 2026, which puts it in the top 1% of works published in 2008 by citations. It is open access: the full text is free to read at arXiv (Cornell University).
- Citations
- 967
- Most cited in
- 2026 (154)
- Field-weighted impact
- 18.82
- References
- 124
- Authors
- 2
Abstract
This paper shows that quantum computation can be made fault-tolerant against errors and inaccuracies when $\eta$, the probability for an error in a qubit or a gate, is smaller than a constant threshold $\eta_c$. This result improves on Shor's result [Proceedings of the 37th Symposium on the Foundations of Computer Science, IEEE, Los Alamitos, CA, 1996, pp. 56–65], which shows how to perform fault-tolerant quantum computation when the error rate $\eta$ decays polylogarithmically with the size of the computation, an assumption which is physically unreasonable. The cost of making the quantum circuit fault-tolerant in our construction is polylogarithmic in time and space. Our result holds for a very general local noise model, which includes probabilistic errors, decoherence, amplitude damping, depolarization, and systematic inaccuracies in the gates. Moreover, we allow exponentially decaying correlations between the errors both in space and in time. Fault-tolerant computation can be performed with any universal set of gates. The result also holds for quantum particles with $p>2$ states, namely, p-qudits, and is also generalized to one-dimensional quantum computers with only nearest-neighbor interactions. No measurements, or classical operations, are required during the quantum computation. We estimate the threshold of our construction to be $\eta_c\simeq 10^{-6}$, in the best case. By this we show that local noise is in principle not an obstacle for scalable quantum computation. The main ingredient of our proof is the computation on states encoded by a quantum error correcting code (QECC). To this end we introduce a special class of Calderbank–Shor–Steane (CSS) codes, called polynomial codes (the quantum analogue of Reed–Solomon codes). Their nice algebraic structure allows all of the encoded gates to be transversal. We also provide another version of the proof which uses more general CSS codes, but its encoded gates are slightly less elegant. To achieve fault tolerance, we encode the quantum circuit by another circuit by using one of these QECCs. This step is repeated polyloglog many times, each step slightly improving the effective error rate, to achieve the desired reliability. The resulting circuit exhibits a hierarchical structure, and for the analysis of its robustness we borrow terminology from Khalfin and Tsirelson [Found. Phys., 22 (1992), pp. 879–948] and Gács [Advances in Computing Research: A Research Annual: Randomness and Computation, JAI Press, Greenwich, CT, 1989]. The paper is to a large extent self-contained. In particular, we provide simpler proofs for many of the known results we use, such as the fact that it suffices to correct for bit-flips and phase-flips, the correctness of CSS codes, and the fact that…
Cite this paper
Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.
APA 7
Aharonov, D., & Ben-Or, M. (2008). Fault-Tolerant Quantum Computation with Constant Error Rate. SIAM Journal on Computing, 38(4), 1207–1282. https://doi.org/10.1137/s0097539799359385
MLA 9
Aharonov, Dorit, and Michael Ben-Or. “Fault-Tolerant Quantum Computation with Constant Error Rate.” SIAM Journal on Computing, vol. 38, no. 4, 2008, pp. 1207–1282. https://doi.org/10.1137/s0097539799359385.
Chicago
Aharonov, Dorit and Michael Ben-Or. 2008. “Fault-Tolerant Quantum Computation with Constant Error Rate.” SIAM Journal on Computing 38 (4): 1207–1282. https://doi.org/10.1137/s0097539799359385.
Harvard
Aharonov, D. and Ben-Or, M. (2008) ‘Fault-Tolerant Quantum Computation with Constant Error Rate’, SIAM Journal on Computing, 38(4), pp. 1207–1282. doi:10.1137/s0097539799359385.
IEEE
D. Aharonov and M. Ben-Or, “Fault-Tolerant Quantum Computation with Constant Error Rate,” SIAM Journal on Computing, vol. 38, no. 4, pp. 1207–1282, 2008, doi: 10.1137/s0097539799359385.
BibTeX
@article{aharonov2008fault,
title = {{Fault-Tolerant Quantum Computation with Constant Error Rate}},
author = {Aharonov, Dorit and Ben-Or, Michael},
journal = {SIAM Journal on Computing},
year = {2008},
volume = {38},
number = {4},
pages = {1207--1282},
doi = {10.1137/s0097539799359385},
url = {https://doi.org/10.1137/s0097539799359385}
}
Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)
Citations by year
| Year | Citations | Share of the best year |
|---|---|---|
| 2017 | 24 | |
| 2018 | 26 | |
| 2019 | 28 | |
| 2020 | 35 | |
| 2021 | 67 | |
| 2022 | 81 | |
| 2023 | 74 | |
| 2024 | 86 | |
| 2025 | 139 | |
| 2026 | 154 |
Its field-weighted citation impact is 18.82: it has been cited 18.82 times as often as the average work of the same field, type and year (1.00 is the world average).
Topic and keywords
Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- fault-tolerant quantum computing
- quantum error-correcting codes
- CSS codes
- polynomial codes
- Reed-Solomon codes
- transversal gates
- decoherence
- amplitude damping
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?
Aharonov, D., & Ben-Or, M. (2008). Fault-Tolerant Quantum Computation with Constant Error Rate. SIAM Journal on Computing, 38(4), 1207–1282. https://doi.org/10.1137/s0097539799359385
How many times has this paper been cited?
967 times, according to OpenAlex on 20 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?
Dorit Aharonov, Michael Ben-Or.
What is the DOI of this paper?
10.1137/s0097539799359385, permanently at https://doi.org/10.1137/s0097539799359385. Sign in and open it from this page.
Bibliographic data from OpenAlex (CC0), last checked 20 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.