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 601–633 of 633
Unraveling an Exotic Electronic State for Error-free Quantum Computation
Muraki, K. (2012) · NTT technical review · doi:10.53829/ntr201210ra2
Balancing the minimum error rate and minimum copy consumption in quantum state discrimination
Tian, B., Hou, Z., Xiang, G., Li, C., & Guo, G. (2024) · JUSTC · doi:10.52396/justc-2023-0155
Foundations of Holographic Quantum Computation
Nye, L. (2025) · Journal of Applied Mathematics and Physics · doi:10.4236/jamp.2025.131002
Photon distillation with reduced resource costs for fault-tolerant quantum computation
Somhorst, F. H. B., Sauër, K., van den Hoven, S. N., & Renema, J. J. (2025) · Quantum Computing, Communication, and Simulation · doi:10.1117/12.3041144
Schmid, L., Peham, T., Berent, L., Müller, M., & Wille, R. (2025) · Design, Automation, and Test in Europe · doi:10.23919/date64628.2025.10992896
Resource-compact time-optimal quantum computation
Kim, T., Baek, K., Hwang, Y., & Bang, J. (2025) · Quantum Information Processing · doi:10.1007/s11128-025-04797-4
MITS: A Quantum Sorcerer’s Stone for Designing Surface Codes
Chatterjee, A., Kundu, D., & Ghosh, S. (2025) · Entropy · doi:10.3390/e27080812
273Chapter 11 Quantum security in 6G networks
Krishna, K., & Pathak, P. (2025) · De Gruyter eBooks · doi:10.1515/9783111264349-011
Method for 3D structure of measurement-free fault tolerant surface codePreprint
Min, G., & Heo, J. (2025) · Research Square · doi:10.21203/rs.3.rs-7596333/v1
The Theoretical Rationale for Using Quantum Computers to Crack Cryptosystems
Andrusenko, Y., Lukyanov, D., Dmitrienko, A., Kushchenko, A. A., & Fedash, D. (2025) · Lecture notes in networks and systems · doi:10.1007/978-3-032-07275-7_4
Quantitative logics for directed evolution of an asexual population
Park, K. (2026) · PLoS ONE · doi:10.1371/journal.pone.0354488
Qubits, Quantum Gates, and Quantum Circuits
Mishra, S. P., & Katakam, R. (2026) · Springer eBooks · doi:10.1007/978-3-032-10775-6_2
Connecting Quantum Computing with Classical Stochastic Simulation
Blanchet, J., Squillante, M. S., Szegedy, M., & Wang, G. (2025) · Winter Simulation Conference · doi:10.1109/wsc68292.2025.11339097
Fault-Tolerant Quantum Input/Output
Christandl, M., Fawzi, O., & Goswami, A. (2026) · IEEE Transactions on Information Theory · doi:10.1109/tit.2026.3672442 · Cited by 9
Reinforcement Learning for Enhanced Advanced QEC Architecture Decoding
Zhou, Y., Kong, L., Peng, Y., & Liang, Z. (2026) · Asia and South Pacific Design Automation Conference (ASP-DAC) · doi:10.1109/asp-dac66049.2026.11420491 · Cited by 1
Decoding of LDPC quantum codes
Grouès, L. (2022) · doi:10.70675/4405a9b9z4ce7z49bez9fc0z6b5a10ebf2d1
Quantum key distribution and quantum error correction with bosonic systems
Denys, A. (2024) · theses.fr (ABES) · doi:10.70675/c51a18fbz5b6fz4912zb5a1z470c35920675
Learning to Correct Errors in Quantum Circuits via Transformer-Predicted PQCs
Tiwari, A., Wang, Z., & Gupta, H. (2026) · International Conference on Quantum Communications, Networking, and Computing (QCNC) · doi:10.1109/qcnc69040.2026.00110
Expander quantum low density parity check codes against long-range correlated errors in memory
Kashtikar, Y. D., Mathur, P., Senthil, S., & Chatterjee, A. (2026) · Physical Review A · doi:10.1103/q4pw-zwcv
Wang, X., Huang, C., & Fan, X. (2026) · Applied Sciences · doi:10.3390/app16115409
Optimal Compilation of Syndrome Extraction Circuits for General Quantum LDPC Codes
Zhang, K., Gao, D., Yang, Z., Zhou, R., Liu, F., Ji, Z., & Chen, J. (2026) · Design, Automation, and Test in Europe · doi:10.23919/date69613.2026.11539585 · Cited by 7
Quantum computation as boundary stabilization in a mereotopological information model
Szmigielski, A. (2026) · Quantum Information Processing · doi:10.1007/s11128-026-05253-7
Recent Advances in Quantum Error Correction Codes for Superconducting Quantum Computing
Wang, Z., Gao, G., & 武光明 (2026) · International Symposium on Computer Technology and Information Science (ISCTIS) · doi:10.1109/isctis70043.2026.11572651
Error correction of a logical qubit encoded in a single atomic ion
DeBry, K., Meister, N., Martinez, A. V., Bruzewicz, C., Shi, X., Reens, D., McConnell, R., Chuang, I. L., & Chiaverini, J. (2026) · Nature Physics · doi:10.1038/s41567-026-03315-2 · Cited by 14
Distilling Magic States in the Bicycle Architecture
Xu, S., Liu, K., Rall, P., He, Z., & Ding, Y. (2026) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca66397.2026.00148
3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits
Caha, L., Coiteux-Roy, X., & König, R. (2026) · Nature Communications · doi:10.1038/s41467-026-76560-x · Cited by 4
Faster than MIP Decoding of Graph Codes with a Single Logical Qubit
Basak, N., & Paul, G. (2026) · IEEE International Conference on Quantum Control, Computing and Learning (qCCL) · doi:10.1109/qccl70331.2026.11668573
Babu, M. V., Kalpana, K., Prasanthi, Y., Kumaresan, D. M., & Satheesh, N. (2026) · International Conference on Trends in Quantum Computing and Emerging Business Technologies (TQCEBT) · doi:10.1109/tqcebt67648.2026.11681216
Sarvepalli, P. K., & Aly, S. A. (2007) · Chapman & Hall/CRC eBooks · doi:10.1201/9781584889007-18
Quantum computing and the entanglement frontier
Preskill, J. (2012) · arXiv · doi:10.48550/arxiv.1203.5813 · Cited by 308
Fault-tolerant quantum computing with color codes
Landahl, A. J., Anderson, J. T., & Rice, P. R. (2011) · arXiv · doi:10.48550/arxiv.1108.5738 · Cited by 79
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
