CoChat
Sign Up
PreprintCited by 79Quantum Computing Algorithms and ArchitectureQuantum many-body systemsQuantum Information and Cryptography

Fault-tolerant quantum computing with color codes

Open access
Landahl, Andrew J., Anderson, Jonas T., Rice, Patrick R.·2011·arXiv
DOI 10.48550/arxiv.1108.5738arXiv 1108.5738
Open this paper in CoChat — free accountOpen PDF

Abstract

We present and analyze protocols for fault-tolerant quantum computing using color codes. We present circuit-level schemes for extracting the error syndrome of these codes fault-tolerantly. We further present an integer-program-based decoding algorithm for identifying the most likely error given the syndrome. We simulated our syndrome extraction and decoding algorithms against three physically-motivated noise models using Monte Carlo methods, and used the simulations to estimate the corresponding accuracy thresholds for fault-tolerant quantum error correction. We also used a self-avoiding walk analysis to lower-bound the accuracy threshold for two of these noise models. We present and analyze two architectures for fault-tolerantly computing with these codes: one with 2D arrays of qubits are stacked atop each other and one in a single 2D substrate. Our analysis demonstrates that color codes perform slightly better than Kitaev's surface codes when circuit details are ignored. When these details are considered, we estimate that color codes achieve a threshold of 0.082(3)%, which is higher than the threshold of $1.3 \times 10^{-5}$ achieved by concatenated coding schemes restricted to nearest-neighbor gates in two dimensions but lower than the threshold of 0.75% to 1.1% reported for the Kitaev codes subject to the same restrictions. Finally, because the behavior of our decoder's performance for two of the noise models we consider maps onto an order-disorder phase transition in the three-body random-bond Ising model in 2D and the corresponding random-plaquette gauge model in 3D, our results also answer the Nishimori conjecture for these models in the negative: the statistical-mechanical classical spin systems associated to the 4.8.8 color codes are counterintuitively more ordered at positive temperature than at zero temperature.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1108.5738

Cites

7 of 7 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

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?

  • The MLE problem can be formulated as a mixed-integer program (MIP), or for specific choices of error probabilities as an integer program.

    “In general, the MLE problem in Eq. (9.10) can be formulated as a mixed-integer program (MIP), or for specific choices of error probabilities pi as an integer program [96].”

    From Quantum error correction and fault tolerance: A comprehensive tutorial (2026) · cites this paper as [96]

    The Introduction (p. 2) and “Code capacity MLE decoder” (p. 8) formulate maximum-likelihood decoding for the color codes studied as a binary integer program. Our copy does not establish the broader claim that the MLE problem is generally a mixed-integer program, or specify which choices of error probabilities pi yield an integer program. (LLM, conf=0.85)

    Experimental — accuracy not yet measured

  • Colour codes allow for more efficient logical operations and require fewer qubits than the surface code to encode a logical qubit at a fixed code distance.

    “Colour codes10,35 allow for more efficient logical operations and require fewer qubits than the surface code to encode a logical qubit at a fixed code distance36.”

    From Scaling and logic in the colour code on a superconducting quantum processor (2025) · cites this paper as [35]

    The Code family section (p. 4) says that 4.8.8 color codes implement Clifford gates transversally, making fault-tolerant gate protocols generally simpler. It also says they use the fewest qubits per code distance among three color-code lattices, but does not establish the claimed qubit-count advantage over surface codes at fixed distance. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

  • Colour codes have a stricter error threshold than surface codes because of their higher weight stabilizer measurements.

    “However, colour codes have a stricter error threshold than surface codes because of their higher weight stabilizer measurements35.”

    From Scaling and logic in the colour code on a superconducting quantum processor (2025) · cites this paper as [35]

    In C. Circuit-level noise model (p. 14), the paper reports a lower threshold for 4.8.8 color codes than for 4.4.4.4 surface codes and says it believes the difference arises from higher-weight stabilizers and their larger measurement circuits. The claim omits that noise-model restriction and presents the proposed explanation as certain. In A. Code capacity noise model (p. 11), the color-code threshold is instead slightly higher. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

  • Conventional colour code syndrome extraction circuits require higher connectivity than four-nearest-neighbour architectures.

    “Moreover, these colour codes require more elaborate decoding strategies, and conventional colour code syndrome extraction circuits require higher connectivity than four-nearest-neighbour architectures35,44, which is difficult to realize on superconducting devices.”

    From Scaling and logic in the colour code on a superconducting quantum processor (2025) · cites this paper as [35]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 51

  1. [12]E. Knill, Fault-tolerant postselected quantum computation: Threshold analysis (2004), arXiv:quant-ph/0404104 . · arXiv
  2. [13]F. M. Spedalieri and V. P. Roychowdhury, Latency in local, two-dimensional, fault-tolerant quantum computing , Quant. Inf. Comp. 9 , 666 (2009), arXiv:0805.4213 , URL http://www.rinton.net/xxqic9/qic-9-78/ 0666-0682.pdf . · arXiv
  3. [14]D. Bacon, Operator quantum error-correcting subsystems for self-correcting quantum memories , Phys. Rev. A 73 , 012340 (2006), doi:10.1103/PhysRevA.73.012340 , arXiv:quant-ph/0506023v4 . · DOI · Paper page
  4. [15]A. Y. Kitaev, Quantum error correction with imperfect gates , in Proceedings of the Third International Conference on Quantum Communication, Computing and Measurement , edited by O. Hirota, A. S. Holevo, and C. M. Caves (Plenum Press, New York, 1997).
  5. [16]E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topological quantum memory , J. Math. Phys. 43 , 4452 (2002), doi:10.1063/1.1499754 , arXiv:quant-ph/0110143 . · DOI · Paper page
  6. [17]R. Raussendorf and J. Harrington, Fault-tolerant quantum computation with high threshold in two dimensions , Phys. Rev. Lett. 98 , 190504 (2007), doi:10.1103/PhysRevLett.98.190504 , arXiv:quant-ph/0610082 . · DOI · Paper page
  7. [19]D. S. Wang, A. G. Fowler, and L. C. L. Hollenberg, Surface code quantum computing with error rates over 1% , Phys. Rev. A 83 , 020302(R) (2011), doi:10.1103/PhysRevA.83.020302 , arXiv:1009.3686 . · DOI
  8. [20]H. Bombin and M. A. Martin-Delgado, Topological quantum distillation , Phys. Rev. Lett. 97 , 180501 (2006), doi:10.1103/PhysRevLett.97.180501 , arXiv:quant-ph/0605138 . · DOI · Paper page
  9. [22]D. S. Wang, A. G. Fowler, C. D. Hill, and L. C. L. Hollenberg, Graphical algorithms and threshold error rates for the 2d color code , Quant. Inf. Comp. 10 , 780 (2010), arXiv:0907.1708 , URL http://www.rintonpress.com/ xxqic10/qic-10-910/0780-0802.pdf . · arXiv
  10. [23]H. G. Katzgraber, H. Bombin, and M. A. MartinDelgado, Error threshold for color codes and random three-body ising models , Phys. Rev. Lett. 103 , 090501 (2009), doi:10.1103/PhysRevLett.103.090501 , arXiv:0902.4845 . · DOI
  11. [25]M. Ohzeki, Accuracy thresholds of topological color codes on the hexagonal and squareoctagonal lattices , Phys. Rev. E 80 , 011141 (2009), doi:10.1103/PhysRevE.80.011141 , arXiv:0903.2102 . · DOI
  12. [26]R. S. Andrist, H. G. Katzgraber, H. Bombin, and M. A. Martin-Delgado, Tricolored lattice gauge theory with randomness: Fault-tolerance in topological color codes (2010), arXiv:1005.0777 . · arXiv
  13. [27]C. Wang, J. Harrington, and J. Preskill, ConfinementHiggs transition in a disordered gauge theory and the accuracy threshold for quantum memory , Ann. Phys. 303 , 31 (2003), doi:10.1016/S0003-4916(02)00019-2 , arXiv:quant-ph/0207088 . · DOI
  14. [28]M. Ohzeki, Locations of multicritical points for spin glasses on regular lattices , Phys. Rev. E 79 , 021129 (2009), doi:10.1103/PhysRevE.79.021129 , arXiv:0811.0464 . · DOI
  15. [29]T. Ohno, G. Arakawa, I. Ichinose, and T. Matsui, Phase structure of the random-plaquette z 2 gauge model: accuracy threshold for a toric quantum memory , Nucl. Phys. B 697 , 462 (2004), doi:10.1016/j.nuclphysb.2004.07.003 , arXiv:quant-ph/0401101 . · DOI
  16. [30]S. L. A. de Queiroz, Location and properties of the multicritical point in the Gaussian and ± j Ising spin glasses , Phys. Rev. B 79 , 174408 (2009), doi:10.1103/PhysRevB.79.174408 , arXiv:0902.4153 . · DOI
  17. [31]M. Suchara, S. Bravyi, and B. Terhal, Constructions and noise threshold of topological subsystem codes (2010), arXiv:1012.0425 . · arXiv
  18. [32]H. Bombin, Topological subsystem codes , Phys. Rev. A 81 , 032301 (2010), doi:10.1103/PhysRevA.81.032301 , arXiv:0908.4246 . · DOI
  19. [33]E. Berlekamp, R. J. McEliece, and H. van Tilborg, On the inherent intractability of certain coding problems , IEEE Trans. Info. Theo. 24 , 384 (1978), doi:10.1109/TIT.1978.1055873 . · DOI
  20. [34]J. E. Levy, A. Ganti, C. A. Phillips, B. R. Hamlet, A. J. Landahl, T. M. Gurrieri, R. D. Carr, and M. S. Carroll, Brief announcement: the impact of classical electronics constraints on a solid-state logical qubit memory , in Proceedings of the Twenty-First Annual ACM Symposium on Parallelism in Algorithms and Architectures , edited by F. Meyer auf der Heide and M. A. Bender (ACM Press, New York, 11-13 August, 2009, Calgary, AB, Canada, 2009), ISBN 978-1-60558-606-9, doi:10.1145/1583991.1584039 , arXiv:0904.0003 . · DOI
  21. [35]J. E. Levy, M. S. Carroll, A. Ganti, C. A. Phillips, A. J. Landahl, T. M. Gurrieri, R. D. Carr, H. L. Stalford, and E. Nielsen, Implications of electronics constraints for solid-state quantum error correction and quantum circuit failure probability (2011), arXiv:1105.0682 . · arXiv
  22. [36]M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, 2000), ISBN 0-521-63235-8 (Hardback), 0521-63503-9 (Paperback).
  23. [38]P. Aliferis, D. Gottesman, and J. Preskill, Quantum accuracy threshold for concatenated distance-3 codes , Quant. Inf. Comp. 6 , 97 (2006), arXiv:quant-ph/0504218 , URL http://www.rinton.net/xqic6/qic-6-2/097-165.pdf . · arXiv
  24. [40]P. Aliferis, D. Gottesman, and J. Preskill, Accuracy threshold for postselected quantum computation , Quant. Inf. Comp. 8 , 0181 (2008), arXiv:quant-ph/0703264 , URL http://www.rintonpress.com/xxqic8/qic-8-34/ 0181-0244.pdf . · arXiv
  25. 79 , 012332 (2009), doi:10.1103/PhysRevA.79.012332 , arXiv:0809.5063 . · DOI
  26. [42]A. W. Cross, D. P. DiVincenzo, and B. M. Terhal, Comparative code study for quantum fault tolerance , Quant. Inf. Comp. 9 , 541 (2009), arXiv:0711.1556 , URL http: //www.rinton.net/xxqic9/qic-9-78/0541-0572.pdf . · arXiv
  27. [43]P. Aliferis and J. Preskill, Fault-tolerant quantum computation against biased noise , Phys. Rev. A 78 , 052331 (2008), doi:10.1103/PhysRevA.78.052331 , arXiv:0710.1301 . · DOI · Paper page
  28. [44]D. Gottesman, The Heisenberg representation of quantum computers , in Group22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics , edited by S. P. Corney, R. Delbourgo, and P. D. Jarvis (International Press, Cambridge, MA, 13-17 Jul. 1998, Hobart, Australia, 1999), pp. 32-43, arXiv:quant-ph/9807006 . · arXiv
  29. [45]A. M. Steane, Error correcting codes in quantum theory , Phys. Rev. Lett. 77 , 793 (1996), doi:10.1103/PhysRevLett.77.793 . · DOI · Paper page
  30. [46]A. M. Steane, Space, time, parallelism and noise requirements for reliable quantum computing , Fortschr. Phys. 46 , 443 (1998), arXiv:quant-ph/9708021 , URL http://onlinelibrary.wiley.com/doi/10.1002/ %28SICI%291521-3978%28199806%2946:4/5%3C443:: AID-PROP443%3E3.0.CO;2-8/abstract . · arXiv
  31. [48]A. Steane, Multiple particle interference and quantum error correction , Proc. Roy. Soc. London A 452 , 2551 (1996), arXiv:quant-ph/9601029 , URL http://www. jstor.org/stable/52827 . · arXiv
  32. [49]A. G. Fowler, Two-dimensional color-code quantum computation , Phys. Rev. A 83 , 042310 (2011), doi:10.1103/PhysRevA.83.042310 , arXiv:0806.4827v3 . · DOI
  33. [50]D. Gottesman, Stabilizer codes and quantum error correction , Ph.D. thesis, Caltech (1997), arXiv:quant-ph/9705052 . · arXiv
  34. [51]A. G. Fowler, D. S. Wang, and L. C. L. Hollenberg, Surface code quantum error correction incorporating accurate error propagation , Quant. Inf. Comp. 11 , 8 (2011), arXiv:1004.0255 . · arXiv
  35. [53]H. Nishimori, Internal energy, specific-heat and correlation-function of the bond-random Isingmodel , Prog. Theor. Phys. 66 , 1169 (1981), doi:10.1143/PTP.66.1169 . · DOI
  36. [54]H. Nishimori, Geometry-induced phase transition in the ± j Ising model , J. Phys. Soc. Japan 55 , 3305 (1986), doi:10.1143/JPSJ.55.3305 . · DOI
  37. [56]I. Jensen and A. J. G. and, Self-avoiding walks, neighbour-avoiding walks and trails on semiregular lattices , J. Phys. A: Math. Gen. 31 , 8137 (1998), doi:10.1088/0305-4470/31/40/008 . · DOI
  38. [57]I. Jensen, Improved lower bounds on the connective constants for two-dimensional self-avoiding walks , J. Phys. A: Math. Gen. 37 , 11521 (2004), doi:10.1088/0305-4470/37/48/001 . http://dx.doi.org/10.1088/0305-4470/37/48/001 · DOI
  39. [58]S. E. Alm, Upper and lower bounds for the connective constants of self-avoiding walks on the Archimedean and Laves lattices , J. Phys. A: Math. Gen. 38 , 2055 (2005), doi:10.1088/0305-4470/38/10/001 . · DOI
  40. [59]B. Eastin, Error channels and the threshold for faulttolerant quantum computation , Ph.D. thesis, University of New Mexico (2007), arXiv:0710.2560 . · arXiv
  41. [60]E. Knill, R. Laflamme, and W. H. Zurek, Threshold accuracy for quantum computation (1996), arXiv:quant-ph/9610011 . · arXiv
  42. [62]B. Eastin and E. Knill, Restrictions on transversal encoded quantum gate sets , Phys. Rev. Lett. 102 , 110502 (2009), doi:10.1103/PhysRevLett.102.110502 , arXiv:0811.4262 . · DOI · Paper page
  43. [63]H. Bombin and M. A. Martin-Delgado, Topological computation without braiding , Phys. Rev. Lett. 98 , 160502 (2007), doi:10.1103/PhysRevLett.98.160502 , arXiv:quant-ph/0610024 . · DOI
  44. [64]B. W. Reichardt, Quantum universality by state distillation (2006), arXiv:quant-ph/0608085 . · arXiv
  45. [65]H. Buhrman, R. Cleve, M. Laurent, N. Linden, A. Schrijver, and F. Unger, New limits on fault-tolerant quantum computation , in Proceedings of the 47th IEEE Symposium on Foundations of Computer Science , edited by B. Werner, IEEE (IEEE Press, Los Alamitos, CA, Oct. 21-24, Berkeley, CA, USA, 2006), pp. 411419, ISBN 0-7695-2720-5, doi:10.1109/FOCS.2006.50 , arXiv:quant-ph/0604141 . · DOI
  46. [66]S. Virmani, S. F. Huelga, and M. B. Plenio, Classical simulability, entanglement breaking, and quantum computation thresholds , Phys. Rev. A 71 , 042328 (2005), doi:10.1103/PhysRevA.71.042328 , arXiv:quant-ph/0408076 . · DOI · Paper page
  47. [67]R. Raussendorf, J. Harrington, and K. Goyal, Topological fault-tolerance in cluster state quantum computation , New J. Phys. 9 , 199 (2007), doi:10.1088/1367-2630/9/6/199 , arXiv:quant-ph/0703143 . · DOI · Paper page
  48. [68]D. Poulin, Stabilizer formalism for operator quantum error correction , Phys. Rev. Lett 95 , 230504 (2005), doi:10.1103/PhysRevLett.95.230504 , arXiv:quant-ph/0508131 . · DOI
  49. [69]R. Raussendorf, J. Harrington, and K. Goyal, A fault-tolerant one-way quantum computer , Ann. Phys. 321 , 2242 (2006), doi:10.1016/j.aop.2006.01.012 , arXiv:quant-ph/0510135 . · DOI · Paper page
  50. [70]G. Duclos-Cianci and D. Poulin, Fast decoders for topological quantum codes , Phys. Rev. Lett. 104 , 050504 (2010), doi:10.1103/PhysRevLett.104.050504 , arXiv:0911.0581 . · DOI
  51. [71]J. Feldman, M. J. Wainwright, and D. R. Karger, Using linear programming to decode binary linear codes , IEE Trans. Info. Theo. 51 , 954 (2005), doi:10.1109/TIT.2004.842696 . · DOI

Cited by

Sorted by citations

Authors
Landahl, A. J., Anderson, J. T., & Rice, P. R.
Affiliations
  • Sandia National Laboratories California (US)
  • University of New Mexico (US)
ORCID
Anderson, Jonas T.
Venue
arXiv
Publisher
arXiv
Published
2011
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1108.5738
arXiv
1108.5738
OpenAlex
W1599677646
Cited by
79
References
7
Citations by year
2025: 3 · 2024: 6 · 2023: 9 · 2022: 13 · 2021: 3 · 2020: 7 · 2019: 8 · 2018: 7 · 2017: 6 · 2016: 2 · 2015: 5 · 2014: 3 · 2013: 3 · 2012: 4
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (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 many-body systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
color codes, fault-tolerant quantum computing, quantum error correction, accuracy threshold, surface code, self-avoiding walks, random bond Ising model, order-disorder transition, concatenated codes, noise models

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