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

Fault-tolerant quantum computation with constant error

Open access
Aharonov, D., Ben-Or, M.·1997·Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97
DOI 10.1145/258533.258579
Open this paper in CoChat — free accountOpen PDF

Abstract

In the past year many developments have taken place in the area of quantum error corrections. Recently Shor showed how to perform fault tolerant quantum computation when, , the probability for a fault in one time step per qubit or per gate, is polylogarithmically small. This paper closes the gap and shows how to perform fault tolerant quantum computation when the error probability, , is smaller than some constant threshold, 0 . The cost is polylogarithmic in time and space, and no measurements are used during the quantum computation. The same result is shown also for quantum circuits which operate on nearest neighbors only.

Integrity signals

Registry

Crossref · 10.1145/258533.258579

Cites

61 of 61 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

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?

  • Sequential quantum computation, such as quantum Turing machines, cannot be noise resistant because error corrections cannot be applied fast enough to prevent accumulation of errors.

    “First, the choice to work with circuits which allow parallelism is necessary, because sequential quantum computation, such as quantum Turing machines, cannot be noise resistant[3], since error corrections cannot be applied fast enough to prevent accumulation of errors.”

    From Fault-Tolerant Quantum Computation with Constant Error Rate (2008) · cites this paper as [3]

  • In a previous paper, the authors showed that quantum systems can be simulated efficiently by a classical Turing machine if the noise is large.

    “In a previous paper, we have shown that quantum systems can be simulated efficiently by a classical Turing machine if the noise is large[3].”

    From Fault-Tolerant Quantum Computation with Constant Error Rate (2008) · cites this paper as [3]

  • For a very high noise rate, the quantum circuit behaves in a classical way.

    “In [3] it was shown that for a very high noise rate, the quantum circuit behaves in a classical way.”

    From Fault-Tolerant Quantum Computation with Constant Error Rate (2008) · cites this paper as [3]

  • By considering more favorable schemes for Hamiltonian decomposition, most modern-day simulation algorithms scale in terms of τ_max = t||H||_max instead of τ.

    “Second, by considering more favorable schemes for Hamiltonian decomposition 256,257 , most modern-day simulation algorithms scale in terms of τ max = t ‖ H ‖ max instead of τ , where ‖ H ‖ max is the absolute value of the largest entry of H as a matrix in the computational basis.”

    From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [256]

  • Arbitrarily large quantum computations can be performed with arbitrary accuracy, provided the error level of elementary components is below a certain threshold (threshold theorem).

    “In fact, arbitrarily large quantum computations can be performed with arbitrary accuracy, provided the error level of the elementary components of the quantum computer is below a certain threshold. This important result is called the threshold theorem of quantum computation 59-62”

    From Measurement-based quantum computation (2009) · cites this paper as [60]

Cites

Flagged first, then by citations

Cited by

Sorted by citations

Related

Authors
Aharonov, D., & Ben-Or, M.
Affiliations
Hebrew University of Jerusalem (IL)
ORCID
Venue
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97
Publisher
ACM Press
Published
1997
Pages
176-188
DOI
10.1145/258533.258579
OpenAlex
W2052169397
Cited by
631
References
61
Citations by year
2026: 25 · 2025: 44 · 2024: 29 · 2023: 18 · 2022: 17 · 2021: 26 · 2020: 29 · 2019: 21 · 2018: 18 · 2017: 19 · 2016: 19 · 2015: 23 · 2014: 19 · 2013: 16 · 2012: 20
FWCI
16.52
Type
conference paper
Language
en
Open access
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Locations
  • ACM Symposium on Theory of Computing (STOC) (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
  • Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
Keywords
fault-tolerant quantum computing, quantum error correction, concatenated quantum codes, secret sharing

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