Journal article · 2008 · Open access

Fault-Tolerant Quantum Computation with Constant Error Rate

Dorit Aharonov, Michael Ben-Or

SIAM Journal on Computing, 38(4), 1207–1282 · Published 1 January 2008 · DOI 10.1137/s0097539799359385

Open PDFView at the publisherCite this paper

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

YearCitationsShare of the best year
20172424
20182626
20192828
20203535
20216767
20228181
20237474
20248686
2025139139
2026154154

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

All highly cited Computer Science papers

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.