The DOI matches its Crossref record; 61 of the 61 references it cites were found in a registry or an index.
Fault-tolerant quantum computation with constant error
Open accessAbstract
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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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?
In the citing paper
“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 the citing paper
“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]
In the citing paper
“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]
In the citing paper
“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]
In the citing paper
“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]
Citations
Cites
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
Quantum computation with quantum dots
Loss, D., & DiVincenzo, D. P. (1998) · Physical Review A · doi:10.1103/physreva.57.120 · Cited by 6,840
A single quantum cannot be cloned
Wootters, W. K., & Zurek, W. H. (1982) · Nature · doi:10.1038/299802a0 · Cited by 5,406 · cited 1×
“It was argued by scientists that due to the continuity of quantum states, and to the fact that quantum states cannot be cloned[ 74 ], it will be impossible to protect quantum information from noise[72, 47].”
BackgroundMixed-state entanglement and quantum error correction
Bennett, C. H., DiVincenzo, D. P., Smolin, J. A., & Wootters, W. K. (1996) · Physical Review A · doi:10.1103/physreva.54.3824 · Cited by 5,272
Quantum theory, the Church–Turing principle and the universal quantum computer
Deutsch, D. (1985) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1985.0070 · Cited by 4,597
Scheme for reducing decoherence in quantum computer memory
Shor, P. W. (1995) · Physical Review A · doi:10.1103/physreva.52.r2493 · Cited by 4,479
Elementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306 · cited 1×
“10, 11] and quantum algorithms[25, 65, 36 ], in particular Shor’s factorization algorithm [62].”
Background
Cited by
Sorted by citations
Items 501–600 of 633
Approximate Quantum Error Correction with 1D Log-Depth Circuits
Liu, G., Du, Z., Liu, Z.-W., & Ma, X. (2026) · PRX Quantum · doi:10.1103/7rzk-2jyh · Cited by 8
QUITS: A modular Qldpc code circUIT Simulator
Kang, M., Lin, Y., Yao, H., Gökduman, M., Meinking, A., & Brown, K. R. (2025) · Quantum · doi:10.22331/q-2025-12-05-1931 · Cited by 11
A Short Introduction to Quantum Error Correction
Guedes, T. (2026) · Brazilian Journal of Physics · doi:10.1007/s13538-026-02007-9 · Cited by 2
Utility-Scale Quantum Computational Chemistry
Castaldo, D., & Reiher, M. (2026) · The Journal of Physical Chemistry Letters · doi:10.1021/acs.jpclett.6c00888 · Cited by 3
Aharonov, D., Arad, I., Eban, E., & Landau, Z. A. (2008) · Cited by 1
Self-citationSome classes of concatenated quantum codes: constructions and lower bounds
Fujita, H. (2015) · Quantum Information and Computation · doi:10.26421/qic15.5-6-2 · Cited by 1
Symmetry and control in spin-based quantum computing
Stepanenko, D. (2005) · Cited by 1
QuL: Programming Library for Computational Cooling of Qubits
Difranco, G., & Oftelie, L. B. (2025) · ACM Transactions on Quantum Computing · doi:10.1145/3737887 · Cited by 1
Dai, S., & Li, R. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718113 · Cited by 8
Quantum memories and Landauer's principle
Alicki, R. (2010) · doi:10.1142/9789814317443_0001 · Cited by 1
Entangling Qubits by Heisenberg Spin Exchange and Anyon Braiding
Zeuch, D. (2016) · Cited by 1
Efficient decoding of random errors for quantum expander codes
Fawzi, O., Grospellier, A., & Leverrier, A. (2018) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3188745.3188886 · Cited by 1
Quantum era challenges for classical computers
Regazzoni, F., Fowler, A. G., & Polian, I. (2018) · International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation · doi:10.1145/3229631.3264737 · Cited by 4
Quantum walks as mathematical foundation for quantum gates
Solenov, D. (2020) · Quantum Information and Computation · doi:10.26421/qic20.3-4-4 · Cited by 3
Asymmetric quantum codes from skew cyclic codes over B1
Muchtadi-Alamsyah, I., & Irwansyah, I. (2019) · AIP conference proceedings · doi:10.1063/1.5139134 · Cited by 1
Oscillator-to-Oscillator Codes Do Not Have a Threshold
Hänggli, L., & König, R. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3126881 · Cited by 17
On fixed-gap adiabatic quantum computationPreprint
Mizel, A. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1002.0846 · Cited by 1
Prospects for Quantum ComputingPreprint
Kak, S. C. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0902.4884 · Cited by 1
Rounds vs queries trade-off in noisy computation
Goyal, N., & Saks, M. (2005) · doi:10.5555/1070432.1070520 · Cited by 1
A dependability perspective on emerging technologies
Prodan, L., Udrescu, M., & Vlăduţiu, M. (2006) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/1128022.1128049 · Cited by 1
Computation and Fundamental Physics
Bacon, D. (2012) · The Computer Journal · doi:10.1093/comjnl/bxs072 · Cited by 1
Two phase simulation-based assessment of quantum error correction codes
Boncalo, O., Vlăduţiu, M., & Amaricăi, A. (2009) · International Conference Mixed Design of Integrated Circuits and Systems · Cited by 1
Continuous time quantum walks performing quantum gates via higher energy statesPreprint
Solenov, D. (2015) · arXiv (Cornell University) · Cited by 1
Coherent control of nuclear and electron spins for quantum information processing
Park, K. (2015) · UWSpace (University of Waterloo) · Cited by 1
Dennis, E., Kitaev, A., Landahl, A. J., & Preskill, J. P. (2003) · Cited by 1
Long distance quantum communication over noisy networksPreprint
Grudka, A., & Pankowski, Ë. (2012) · arXiv (Cornell University) · Cited by 1
de Jong, J. (2019) · Research Repository (Delft University of Technology) · Cited by 1
Characterization and implementation of robust quantum information processing
Fernandez, D. (2020) · Cronfa (Swansea University) · doi:10.23889/suthesis.56913 · Cited by 1
The XZZX surface codePreprint
Ataides, J. P. B., Tuckett, D. K., Bartlett, S. D., Flammia, S. T., & Brown, B. J. (2020) · doi:10.21203/rs.3.rs-90087/v1 · Cited by 1
Quantum error correction and fault tolerance: A comprehensive tutorial
Spencer, D. J., Jain, S. P., Tanggara, A., Sun, Z., Haug, T., Khu, D., & Bharti, K. (2026) · arXiv
Distinguishing Quantum and Classical Many-Body SystemsPreprint
Kafri, D., & Taylor, J. M. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1504.01187 · Cited by 1
Morten, A. J. (2005) · DSpace@MIT (Massachusetts Institute of Technology)
Ohya, M., & Volovich, I. V. (2011) · Theoretical and mathematical physics · doi:10.1007/978-94-007-0171-7_15
A new approach to codeword stabilized quantum codes using the algebraic structure of modulesPreprint
Santiago, D. F. G., & Otoni, G. S. S. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1505.00283
Decoherence in semiconductor solid-state quantum computers
Valente, D. C. B. (2009) · Journal of International Crisis and Risk Communication Research
Decoherence and Measurement of Charge Qubits in Double Quantum Dots
Hartmann, U. (2005) · doi:10.5282/edoc.4415
Nuevos algoritmos cuánticos para tomografía de procesos y estados
Bendersky, A. (2011) · Repositorio Digital Institucional de la Universidad de Buenos Aires (Universidad de Buenos Aires)
Extracting Entropy from Quantum Computers
Steane, A. M. (2003) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-7907-1_63
Practical quantum fault tolerance
Gilbert, G. N., Weinstein, Y. S., Aggarwal, V., & Calderbank, A. R. (2009) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.818683
Quantum computing and quantum complexity theory
Vazirani, U. V. (2000) · IEEE International Symposium on Circuits and Systems proceedings · doi:10.1109/iscas.2000.857201
Fault-tolerance in two-dimensional topological systems
Anderson, J. T. (2012) · UNM’s Digital Repository (University of New Mexico)
Computing the Exit Complexity of Knowledge in Distributed Quantum Computers
A, M. (2012) · International Journal of Advanced Computer Science and Applications · doi:10.14569/ijacsa.2012.031215
Design-space exploration of fault-tolerant building blocks for large-scale quantum computing
Metodi, T. S., Cross, A. W., Thaker, D., Chuang, I. L., & Chong, F. T. (2007) · IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH) · doi:10.1109/nanoarch.2007.4400851
Noise in quantum and classical computation & non-locality
Unger, F. (2008) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands
Protection of information in quantum databases
Ozhigov, Y. (1997) · CERN Document Server (European Organization for Nuclear Research)
A Theory of Physical Quantum Computation: The Quantum Computer ConditionPreprint
Gilbert, G. N., Hamrick, M., & Thayer, F. J. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0507141
FAULT TOLERANT QUANTUM COMPUTATION ON ISOLATED LOGICAL CELLS
Stephens, A. M., & Hollenberg, L. C. L. (2006)
A classof quantumLDPC codes: construction and performancesunder iterative
Ollivier, H., & Tillich, J. (2007)
Quantum Computers - How Can They Fail?
Kalai, G. (2006)
Lower Bounds for the Noisy Broadcast Problem Extended Abstract
Goyal, N., Kindler, G., & Saks, M. (2005)
Error Models for Quantum State and Parameter Estimation
Schwarz, L. (2014) · Scholars' Bank (University of Oregon)
Polyestimate: a library for near-instantaneous surface code analysis
Fowler, A. G. (2015) · Quantum Information and Computation · doi:10.26421/qic15.1-2-8
Park, J. (2015) · UWSpace (University of Waterloo)
Large Sample Superradiance and Fault-Tolerant Quantum ComputationPreprint
Yavuz, D. D., & Lemberger, B. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.06336
Fast post processing algorithms for fault tolerant quantum computation using surface codes
Zaribafiyan, A. (2014) · cIRcle (University of British Columbia) · doi:10.14288/1.0166069
Operator Quantum Fault Tolerance
Gilbert, G. N., Hamrick, M., Weinstein, Y. S., Aggarwal, V., & Calderbank, A. R. (2008) · International Conference on Quantum Information · doi:10.1364/icqi.2008.jmb46
Layered Architectures for Quantum Computers and Quantum Repeaters
Jones, N. C. (2015) · Lecture notes in physics · doi:10.1007/978-4-431-55756-2_18
On Steane's enlargement of Calderbank-Shor-Steane codes
Fujita, H. (2010) · Quantum Information and Computation · doi:10.26421/qic10.11-12-8
Gaitan, F. (2008) · CRC Press eBooks · doi:10.1201/b15868-7
Fault tolerance and ultimate physical limits of nanocomputation
Sadek, A., Nikolić, K., & Forshaw, M. R. B. (2004) · Series in materials science and engineering · doi:10.1201/9781420034783.ch12
(2008) · CRC Press eBooks · doi:10.1201/b15868-4
Novel Methods in Quantum Error Correction
Jochym-O’Connor, T. (2016) · UWSpace (University of Waterloo)
Accurate modeling of noise in quantum error correcting circuits
Arguedas, M. G. (2015) · SMARTech Repository (Georgia Institute of Technology)
Jackson, C. S. (2017) · Scholars' Bank (University of Oregon)
Threshold analysis with fault-tolerant operations for nonbinary quantum error correcting codes
Kanungo, A. (2005) · OakTrust (Texas A&M University Libraries)
Quantum recovery protocols for stabilizer codes: Deterministic Monte-Carlo simulation
Prousalis, K. P., Iliadis, A. A., & Konofaos, N. (2018) · AIP Advances · doi:10.1063/1.5024661
Quantum Computation Beyond the Unitary Circuit Model
Usher, N. (2017) · UCL Discovery (University College London)
Dür, W., Briegel, H. J., & Zoller, P. (2006) · doi:10.1002/9783527618637.ch26
Qubit as a Polarization Division Multiplexed Quadrature Amplitude Modulated Symbol of LightPreprint
Ohta, M. (2018) · viXra
Classical Control of Large-Scale Quantum ComputersPreprint
Devitt, S. J. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1405.4943
Lo, H., & Chau, H. F. (1998) · IACR Cryptology ePrint Archive
Robustness of QMA against witness noise
Dziemba, F. A. (2017) · Quantum Information and Computation · doi:10.26421/qic17.13-14-6 · Cited by 4
Silva, M. P. D., & Johnson, B. (2019)
Holographic Code RatePreprint
Bray-Ali, N., Chester, D., Hammock, D., Amaral, M. M., Irwin, K., & Rios, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.09253
Quantum algorithmic techniques for fault-tolerant quantum computers
Kieferová, M. (2020) · UWSpace (University of Waterloo) · doi:10.25949/19431368
Quantum Algorithms with Applications to Simulating Physical Systems
Chowdhury, A. C. N. (2019) · UNM’s Digital Repository (University of New Mexico)
Bera, R. K. (2020) · Undergraduate lecture notes in physics · doi:10.1007/978-981-15-2471-4_11
Quantum Error Source and Channel CodingPreprint
Lucarelli, D. G. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.09479
Parameter Estimation, Model Reduction and Quantum FilteringPreprint
Chase, B. A. (2009) · arXiv (Cornell University)
On Realistic Errors in Quantum Computers
Skanes-Norman, J. (2021) · UWSpace (University of Waterloo)
Fault-Tolerant Logical Operators in Quantum Error-Correcting Codes
Webster, P. (2021) · The Sydney eScholarship Repository (The University of Sydney)
Concepts and methods for benchmarking quantum computers
Boone, K. (2021) · UWSpace (University of Waterloo)
Tansuwannont, T. (2021) · UWSpace (University of Waterloo)
Reif, J. H. (2009) · Wiley eBooks · doi:10.1002/9780470429983.ch3
Distinctions with a Difference
Hangleiter, D., Carolan, J., & Thébault, K. P. Y. (2022) · Springer eBooks · doi:10.1007/978-3-030-87216-8_2
Imre, S., & Gyöngyösi, L. (2012) · Wiley eBooks · doi:10.1002/9781118337462.refs
Else, D. V. (2013) · UPT. Syiah Kuala University Library (Syiah Kuala University)
Kendon, V. M. (2009) · Springer eBooks · doi:10.1007/978-0-387-30440-3_429
Brun, T. A. (2011) · Springer eBooks · doi:10.1007/978-1-4614-1168-0_14
Error Correction of Quantum Channels
Miardan, M. M. (2014) · doi:10.22215/etd/2014-10598
Minoli, D. (2005) · Wiley eBooks · doi:10.1002/0471736600.refs
Development of the Quantum Bitcoin (BTC)
Dhuriya, G., Saini, A., & Johari, P. (2022) · Wiley eBooks · doi:10.1002/9781119836728.ch4
Simplifying errors by symmetry and randomisationPreprint
Mills, J. K., Sadhukhan, D., & Kashefi, E. (2023) · HAL · doi:10.48550/arxiv.2303.02712 · Cited by 2
Solving Graph Problems with Single-Photons and Linear Optics
Mezher, R., Carvalho, A. F., & Mansfield, S. (2023) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce57702.2023.10239 · Cited by 1
Quantum Computation and UniversePreprint
Kumar.S, S. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4655575
Best-of-Both-Worlds Multiparty Quantum Computation with Publicly Verifiable Identifiable Abort
Chung, K.-M., Huang, M.-Y., Tang, E.-C., & Zhang, J. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-58751-1_5
Metadata
- Authors
- Aharonov, D., & Ben-Or, M.
- Affiliations
- Hebrew University of Jerusalem (IL)
- Venue
- Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97
- Publisher
- ACM Press
- Published
- 1997
- Pages
- 176-188
- 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
- green
- arxiv.org
- 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 › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › 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
