Quantum accuracy threshold for concatenated distance-3 code
Abstract
We prove a new version of the quantum threshold theorem that applies to concatenation of a quantum code that corrects only one error, and we use this theorem to derive a rigorous lower bound on the quantum accuracy threshold $\varepsilon_0$. Our proof also applies to concatenation of higher-distance codes, and to noise models that allow faults to be correlated in space and in time. The proof uses new criteria for assessing the accuracy of fault-tolerant circuits, which are particularly conducive to the inductive analysis of recursive simulations. Our lower bound on the threshold, $\varepsilon_0 \ge 2.73\times 10^{-5}$ for an adversarial independent stochastic noise model, is derived from a computer-assisted combinatorial analysis; it is the best lower bound that has been rigorously proven so far.
Integrity signals
Registry
Cites
Statistics
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?
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 [62]
Cites
Fault-tolerant quantum computation by anyons
Kitaev, A. Y. (2003) · Annals of Physics · doi:10.1016/s0003-4916(02)00018-0 · Cited by 7,238 · see citing works
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 · see citing works
Error Correcting Codes in Quantum Theory
Steane, A. M. (1996) · Physical Review Letters · doi:10.1103/physrevlett.77.793 · Cited by 2,677 · see citing works
Good quantum error-correcting codes exist
Calderbank, A. R., & Shor, P. W. (1996) · Physical Review A · doi:10.1103/physreva.54.1098 · Cited by 2,516 · see citing works
Gottesman, D., & Chuang, I. L. (1999) · Nature · doi:10.1038/46503 · Cited by 1,860 · see citing works
Self-citationTheory of quantum error-correcting codes
Knill, E., & Laflamme, R. (1997) · Physical Review A · doi:10.1103/physreva.55.900 · Cited by 1,593 · see citing works
Universal quantum computation with ideal Clifford gates and noisy ancillas
Bravyi, S., & Kitaev, A. (2005) · Physical Review A · doi:10.1103/physreva.71.022316 · Cited by 1,525 · see citing works
Dennis, E., Kitaev, A., Landahl, A., & Preskill, J. (2001) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,485 · see citing works
Self-citationQuantum computations: algorithms and error correction
Kitaev, A. Y. (1997) · Russian Mathematical Surveys · doi:10.1070/rm1997v052n06abeh002155 · Cited by 1,424 · see citing works
Class of quantum error-correcting codes saturating the quantum Hamming bound
Gottesman, D. (1996) · Physical Review A · doi:10.1103/physreva.54.1862 · Cited by 1,227 · see citing works
Self-citationQuantum computing with realistically noisy devices
Knill, E. (2005) · Nature · doi:10.1038/nature03350 · Cited by 1,184 · see citing works
Preskill, J. (1998) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1998.0167 · Cited by 994 · see citing works
Self-citationTheory of fault-tolerant quantum computation
Gottesman, D. (1998) · Physical Review A · doi:10.1103/physreva.57.127 · Cited by 945 · see citing works
Self-citationFault-tolerant quantum computation
Shor, P. W. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1996.548464 · Cited by 943 · see citing works
Multiple particle interference and quantum error correction
Steane, A. M. (1996) · Cited by 871 · see citing works
Quantum Teleportation is a Universal Computational PrimitivePreprint
Gottesman, D., & Chuang, I. L. (1999) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9908010 · Cited by 846 · see citing works
Self-citationQuantum Error Correction and Orthogonal Geometry
Calderbank, A. R., Rains, E. M., Shor, P. W., & Sloane, N. J. A. (1997) · Physical Review Letters · doi:10.1103/physrevlett.78.405 · Cited by 811 · see citing works
Stabilizer Codes and Quantum Error Correction
Gottesman, D. (1997) · arXiv · doi:10.48550/arxiv.quant-ph/9705052 · Cited by 753 · see citing works
Self-citationFault-tolerant quantum computation with constant error
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 · Cited by 631 · see citing works
The Heisenberg Representation of Quantum Computers
Gottesman, D. (1998) · University of North Texas Digital Library (University of North Texas) · Cited by 385 · see citing works
Self-citationOverhead and noise threshold of fault-tolerant quantum error correction
Steane, A. M. (2003) · Physical Review A · doi:10.1103/physreva.68.042322 · Cited by 372 · see citing works
Methodology for quantum logic gate construction
Zhou, X., Leung, D. W., & Chuang, I. L. (2000) · Physical Review A · doi:10.1103/physreva.62.052316 · Cited by 355 · see citing works
Fault-Tolerant Error Correction with Efficient Quantum Codes
Divincenzo, D. P., & Shor, P. W. (1996) · Physical Review Letters · doi:10.1103/physrevlett.77.3260 · Cited by 333 · see citing works
Active Stabilization, Quantum Computation, and Quantum State Synthesis
Steane, A. M. (1997) · Physical Review Letters · doi:10.1103/physrevlett.78.2252 · Cited by 308 · see citing works
Resilient Quantum Computation: Error Models and Thresholds
Knill, E. H., Laflamme, R., & Zurek, W. H. (1997) · CERN Document Server (European Organization for Nuclear Research) · Cited by 299 · see citing works
Quantum Error Correction with Imperfect Gates
Kitaev, A. Y. (1997) · Quantum Communication, Computing, and Measurement · doi:10.1007/978-1-4615-5923-8_19 · Cited by 214 · see citing works
Fault-tolerant quantum computation for local non-Markovian noise
Terhal, B. M., & Burkard, G. (2005) · Physical Review A · doi:10.1103/physreva.71.012336 · Cited by 180 · see citing works
Fault-tolerant quantum computation with cluster states
Nielsen, M. A., & Dawson, C. M. (2005) · Physical Review A · doi:10.1103/physreva.71.042323 · Cited by 161 · see citing works
Secure multi-party quantum computation
Crépeau, C., Gottesman, D., & Smith, A. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.510000 · Cited by 155 · see citing works
Self-citationAnyon computers with smaller groups
Mochon, C. (2004) · Physical Review A · doi:10.1103/physreva.69.032306 · Cited by 136 · see citing works
Local fault-tolerant quantum computation
Svore, K. M., Terhal, B. M., & Divincenzo, D. P. (2005) · Physical Review A · doi:10.1103/physreva.72.022317 · Cited by 112 · see citing works
Concatenated Quantum CodesPreprint
Knill, E. H., & Laflamme, R. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9608012 · Cited by 64 · see citing works
Universal quantum computation with ideal Clifford gates and noisy ancillas (14 pages)
Kitaev, A., & Bravyi, S. (2005) · Physical Review A · Cited by 56 · see citing works
Limitations of Noisy Reversible ComputationPreprint
Aharonov, D., Ben-Or, M., Impagliazzo, R., & Nisan, N. (1996) · arXiv (Cornell University) · doi:10.4230/lipics.ccc.2026.38 · Cited by 54 · see citing works
Threshold Estimate for Fault Tolerant Quantum ComputationPreprint
Zalka, C. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9612028 · Cited by 37 · see citing works
Improved ancilla preparation scheme increases fault-tolerant thresholdPreprint
Reichardt, B. W. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0406025 · Cited by 36 · see citing works
Reliable computation with cellular automata
Gács, P. (1983) · doi:10.1145/800061.808730 · Cited by 17 · see citing works
Secure Multi-party Quantum ComputingPreprint
Crépeau, C., Gottesman, D., & Smith, A. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0206138 · Cited by 16 · see citing works
Self-citationThreshold for the distance three Steane quantum codePreprint
Reichardt, B. W. (2005) · arXiv (Cornell University) · Cited by 6 · see citing works
Fault-tolerant quantum computation in the graph-state modelPreprint
Aliferis, P., & Leung, D. (2005) · arXiv (Cornell University) · Cited by 3 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Quantum computation and quantum-state engineering driven by dissipation
Verstraete, F., Wolf, M. M., & Ignacio Cirac, J. (2009) · Nature Physics · doi:10.1038/nphys1342 · Cited by 1,570 · see citing works
Universal quantum computation with ideal Clifford gates and noisy ancillas
Bravyi, S., & Kitaev, A. (2005) · Physical Review A · doi:10.1103/physreva.71.022316 · Cited by 1,525 · see citing works
Quantum error correction for quantum memories
Terhal, B. M. (2015) · Reviews of Modern Physics · doi:10.1103/revmodphys.87.307 · Cited by 1,354 · see citing works
Measurement-based quantum computation
Briegel, H. J., Browne, D. E., Dür, W., Raussendorf, R., & Van den Nest, M. (2009) · Nature Physics · doi:10.1038/nphys1157 · Cited by 1,090 · see citing works
Fault-Tolerant Quantum Computation with High Threshold in Two Dimensions
Raussendorf, R., & Harrington, J. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.190504 · Cited by 812 · see citing works
Topological fault-tolerance in cluster state quantum computation
Raussendorf, R., Harrington, J., & Goyal, K. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/199 · Cited by 617 · see citing works
Demonstration of fault-tolerant universal quantum gate operations
Postler, L., Heuβen, S., Pogorelov, I., Rispler, M., Feldker, T., Meth, M., Marciniak, C. D., Stricker, R., Ringbauer, M., Blatt, R., et al. (2022) · Nature · doi:10.1038/s41586-022-04721-1 · Cited by 287 · see citing works
Building a Fault-Tolerant Quantum Computer Using Concatenated Cat Codes
Chamberland, C., Noh, K., Arrangoiz-Arriola, P., Campbell, E. T., Hann, C. T., Iverson, J., Putterman, H., Bohdanowicz, T. C., Flammia, S. T., Keller, A., et al. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.010329 · Cited by 281 · see citing works
Self-citationSubsystem Fault Tolerance with the Bacon-Shor Code
Aliferis, P., & Cross, A. W. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.220502 · Cited by 203 · see citing works
Self-citationFault-Tolerant quantum computation with constant overhead
Gottesman, D. (2014) · Quantum Information and Computation · doi:10.26421/qic14.15-16-5 · Cited by 172 · see citing works
Self-citationAlicki, R., Lidar, D. A., & Zanardi, P. (2006) · Physical Review A · doi:10.1103/physreva.73.052311 · Cited by 132 · see citing works
Early Fault-Tolerant Quantum Computing
Katabarwa, A., Gratsea, K., Caesura, A., & Johnson, P. D. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.020101 · Cited by 103 · see citing works
Noise thresholds for optical cluster-state quantum computation
Dawson, C. M., Haselgrove, H. L., & Nielsen, M. A. (2006) · Physical Review A · doi:10.1103/physreva.73.052306 · Cited by 79 · see citing works
Demonstration of Fault-Tolerant Steane Quantum Error Correction
Postler, L., Butt, F., Pogorelov, I., Marciniak, C. D., Heußen, S., Blatt, R., Schindler, P., Rispler, M., Müller, M., & Monz, T. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.030326 · Cited by 66 · see citing works
Coherence in logical quantum channels
Iverson, J. K., & Preskill, J. (2020) · New Journal of Physics · doi:10.1088/1367-2630/ab8e5c · Cited by 61 · see citing works
Self-citationMinimizing resource overheads for fault-tolerant preparation of encoded states of the Steane code
Goto, H. (2016) · Scientific Reports · doi:10.1038/srep19578 · Cited by 61 · see citing works
Clark, C. R., Metodi, T. S., Gasster, S. D., & Brown, K. R. (2009) · Physical Review A · doi:10.1103/physreva.79.062314 · Cited by 51 · see citing works
High-fidelity teleportation of a logical qubit using transversal gates and lattice surgery
Ryan-Anderson, C., Brown, N. C., Baldwin, C. H., Dreiling, J. M., Foltz, C., Gaebler, J. P., Gatterman, T. M., Hewitt, N., Holliman, C., Horst, C. V., et al. (2024) · Science · doi:10.1126/science.adp6016 · Cited by 52 · see citing works
Fault-Tolerant One-Bit Addition with the Smallest Interesting Colour Code
Wang, Y., Simsek, S., Gatterman, T. M., Gerber, J. A., Gilmore, K., Gresh, D., Hewitt, N., Horst, C. V., Matheny, M., Mengle, T., et al. (2023) · arXiv · doi:10.48550/arxiv.2309.09893 · Cited by 32 · see citing works
Quantum circuit engineering for correcting coherent noise
Ahsan, M., Naqvi, S. A. Z., & Anwer, H. (2022) · Physical Review A · doi:10.1103/physreva.105.022428 · Cited by 22 · see citing works
Improving Threshold for Fault-Tolerant Color-Code Quantum Computing by Flagged Weight Optimization
Takada, Y., & Fujii, K. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.030352 · Cited by 10 · see citing works
- Authors
- Aliferis, P., Gottesman, D., & Preskill, J.
- Affiliations
- California Institute of Technology (US)
- Perimeter Institute (CA)
- Venue
- Quantum Information and Computation
- Publisher
- Rinton Press
- Published
- 2006-03
- Volume
- 6
- Issue
- 2
- Pages
- 97-165
- ISSN
- 1533-7146 (ISSN-L)
- OpenAlex
- W1874981471
- Cited by
- 412
- References
- 40
- Citations by year
- 2026: 7 · 2025: 29 · 2024: 20 · 2023: 20 · 2022: 18 · 2021: 27 · 2020: 30 · 2019: 18 · 2018: 22 · 2017: 12 · 2016: 19 · 2015: 21 · 2014: 11 · 2013: 19 · 2012: 16
- FWCI
- 34.05
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Quantum Information and Computation (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- concatenated quantum codes, fault tolerance, lower bounds, correlated noise, stochastic noise model, fault-tolerant circuits, recursive simulation
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
