CoChat
Sign Up
Cited by 242Quantum Computing Algorithms and ArchitectureCoding theory and cryptographyError Correcting Code Techniques

Almost-linear time decoding algorithm for topological codes

Open access
Delfosse, Nicolas, Nickerson, Naomi H.·2021·Quantum
DOI 10.22331/q-2021-12-02-595
Open this paper in CoChat — free accountOpen PDF

Abstract

In order to build a large scale quantum computer, one must be able to correct errors extremely fast. We design a fast decoding algorithm for topological codes to correct for Pauli errors and erasure and combination of both errors and erasure. Our algorithm has a worst case complexity of O ( n α ( n ) ) , where n is the number of physical qubits and α is the inverse of Ackermann's function, which is very slowly growing. For all practical purposes, α ( n ) ≤ 3 . We prove that our algorithm performs optimally for errors of weight up to ( d − 1 ) / 2 and for loss of up to d − 1 qubits, where d is the minimum distance of the code. Numerically, we obtain a threshold of 9.9 % for the 2d-toric code with perfect syndrome measurements and 2.6 % with faulty measurements.

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

Crossref · 10.22331/q-2021-12-02-595

Cites

3 of 3 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 UF decoder is a faster, nearly linear-time alternative to MWPM, making it a compelling candidate for real-time decoding on large-scale systems.

    “The UF decoder is a faster, nearly linear-time alternative to MWPM, making it a compelling candidate for real-time decoding on large-scale systems [188].”

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

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: 64

  1. Hussain Anwar, Benjamin J Brown, Earl T Campbell, and Dan E Browne. Fast decoders for qudit topological codes. New Journal of Physics, 16(6):063038, 2014. DOI: 10.1088/1367- 2630/16/6/063038. · DOI
  2. CJ Ballance, TP Harty, NM Linke, and DM Lu- cas. High-fidelity two-qubit quantum logic gates using trapped calcium-43 ions. arXiv preprint arXiv:1406.5473, 2014. DOI: 10.1103/Phys- RevLett.117.060504. · DOI · Paper page
  3. Sean D Barrett and Thomas M Stace. Fault tolerant quantum computation with very high threshold for loss errors. Physical review let- ters, 105(20):200502, 2010. DOI: 10.1103/Phys- RevLett.105.200502. · DOI
  4. Sean D Barrett and Thomas M Stace. Fault tolerant quantum computation with very high threshold for loss errors. Physical review let- ters, 105(20):200502, 2010. DOI: 10.1103/Phys- RevLett.105.200502. · DOI
  5. Hector Bombin and Miguel Angel Martin- Delgado. Topological quantum distillation. Phys- ical review letters, 97(18):180501, 2006. DOI: 10.1103/PhysRevLett.97.180501. · DOI · Paper page
  6. Hector Bombin, Guillaume Duclos-Cianci, and David Poulin. Universal topological phase of two-dimensional stabilizer codes. New Journal of Physics, 14(7):073048, 2012. DOI: 10.1088/1367- 2630/14/7/073048. · DOI
  7. S. B. Bravyi and A. Y. Kitaev. Quantum codes on a lattice with boundary. arXiv preprint arXiv:9811052, 1998.
  8. Sergey Bravyi and Jeongwan Haah. Quantum self-correction in the 3d cubic code model. Phys- ical review letters, 111(20):200501, 2013. DOI: 10.1103/PhysRevLett.111.200501. · DOI
  9. Sergey Bravyi, Martin Suchara, and Alexander Vargo. Efficient algorithms for maximum likeli- hood decoding in the surface code. Physical Re- view A, 90(3):032326, 2014. DOI: 10.1103/Phys- RevA.90.032326. · DOI · Paper page
  10. Nikolas P Breuckmann and Barbara M Terhal. Constructions and noise threshold of hyperbolic surface codes. IEEE Transactions on Infor- mation Theory, 62(6):3731-3744, 2016. DOI: 10.1109/TIT.2016.2555700. · DOI
  11. Nikolas P Breuckmann, Christophe Vuillot, Earl Campbell, Anirudh Krishna, and Barbara M Terhal. Hyperbolic and semi-hyperbolic sur- face codes for quantum storage. arXiv preprint arXiv:1703.00590, 2017. DOI: 10.1088/2058- 9565/aa7d3b. · DOI
  12. Jacques Carolan, Christopher Harrold, Chris Sparrow, Enrique Martín-López, Nicholas J Rus- sell, Joshua W Silverstone, Peter J Shadbolt, Nobuyuki Matsuda, Manabu Oguma, Mikitaka Itoh, et al. Universal linear optics. Science, 349(6249):711-716, 2015. DOI: 10.1126/sci- ence.aab3642. · DOI · Paper page
  13. S Debnath, NM Linke, C Figgatt, KA Landsman, K Wright, and C Monroe. Demonstration of a small programmable quantum computer with atomic qubits. Nature, 536(7614):63-66, 2016. DOI: 10.1038/nature18648. · DOI · Paper page
  14. Nicolas Delfosse. Tradeoffs for reliable quan- tum information storage in surface codes and color codes. In Information Theory Proceed- ings (ISIT), 2013 IEEE International Sympo- sium on, pages 917-921. IEEE, 2013. DOI: 10.1109/ISIT.2013.6620360. · DOI
  15. Nicolas Delfosse. Decoding color codes by pro- jection onto surface codes. Physical Review A, 89(1):012317, 2014. DOI: 10.1103/Phys- RevA.89.012317. · DOI
  16. Nicolas Delfosse and Gilles Zémor. Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel. arXiv preprint arXiv:1703.01517, 2017. DOI: 10.1103/Phys- RevResearch.2.033042. · DOI
  17. Eric Dennis. Purifying quantum states: Quan- tum and classical algorithms. arXiv preprint quant-ph/0503169, 2005. · arXiv
  18. Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum mem- ory. Journal of Mathematical Physics, 43(9): 4452-4505, 2002. DOI: 10.1063/1.1499754. · DOI · Paper page
  19. Guillaume Duclos-Cianci and David Poulin. Fast decoders for topological quantum codes. Phys- ical review letters, 104(5):050504, 2010. DOI: 10.1103/PhysRevLett.104.050504. · DOI
  20. Guillaume Duclos-Cianci and David Poulin. Ki- taev's z d-code threshold estimates. Physical Re- view A, 87(6):062338, 2013. DOI: 10.1103/Phys- RevA.87.062338. · DOI
  21. Guillaume Duclos-Cianci and David Poulin. Fault-tolerant renormalization group decoder for abelian topological codes. Quantum Info. Com- put., 14(9 & 10):721-740, jul 2014. ISSN 1533- 7146. DOI: 10.5555/2638670.2638671. · DOI
  22. Austin Fowler. Towards sufficiently fast quantum error correction. Conference QEC 2017, 2017.
  23. Austin G Fowler. Minimum weight perfect matching of fault-tolerant topological quan- tum error correction in average o(1) paral- lel time. Quantum Information and Com- putation, 15(1&2):0145-0158, 2015. DOI: 10.5555/2685188.2685197. · DOI
  24. Austin G Fowler, Adam C Whiteside, and Lloyd CL Hollenberg. Towards practical clas- sical processing for the surface code. Physi- cal review letters, 108(18):180501, 2012. DOI: 10.1103/PhysRevLett.108.180501. · DOI
  25. Austin G Fowler, Adam C Whiteside, An- gus L McInnes, and Alimohammad Rabbani. Topological code autotune. Physical Review X, 2(4):041003, 2012. DOI: 10.1103/Phys- RevX.2.041003. · DOI
  26. Michael Fredman and Michael Saks. The cell probe complexity of dynamic data structures. In Proceedings of the twenty-first annual ACM sym- posium on Theory of computing, pages 345-354. ACM, 1989. DOI: 10.1145/73007.73040. · DOI
  27. M. H. Freedman and D. A. Meyer. Projective plane and planar quantum codes. Foundations of Computational Mathematics, 1(3):325-332, 2001. DOI: 10.1007/s102080010013. · DOI
  28. M.H. Freedman, D.A. Meyer, F. Luo, and Com- puter Society (IEEE) Washington DC. Z(2)- Systolic Freedom and Quantum Codes. De- fense Technical Information Center, 2002. DOI: 10.2140/gtm.1999.2.113. URL https://books. google.com/books?id=KieaDAEACAAJ. · DOI
  29. Bernard A Galler and Michael J Fisher. An improved equivalence algorithm. Communica- tions of the ACM, 7(5):301-303, 1964. DOI: 10.1145/364099.364331. · DOI
  30. James William Harrington. Analysis of quantum error-correcting codes: symplectic lattice codes and toric codes. PhD thesis, California Institute of Technology, 2004.
  31. Reinier W Heeres, Philip Reinhold, Nissim Ofek, Luigi Frunzio, Liang Jiang, Michel H Devoret, and Robert J Schoelkopf. Implementing a univer- sal gate set on a logical qubit encoded in an os- cillator. Nature Communications, 8, 2017. DOI: 10.1038/s41467-017-00045-1. · DOI
  32. Michael Herold, Michael J Kastoryano, Earl T Campbell, and Jens Eisert. Fault tolerant dy- namical decoders for topological quantum mem- ories. arXiv preprint arXiv:1511.05579, 2015. DOI: 10.1088/1367-2630/aa7099. · DOI
  33. Charles D Hill, Eldad Peretz, Samuel J Hile, Matthew G House, Martin Fuechsle, Sven Rogge, Michelle Y Simmons, and Lloyd CL Hollenberg. A surface code quantum computer in silicon. Science advances, 1(9):e1500707, 2015. DOI: 10.1038/npjqi.2015.19. · DOI
  34. John Hopcroft and Robert Tarjan. Algorithm 447: efficient algorithms for graph manipula- tion. Communications of the ACM, 16(6):372- 378, 1973. DOI: 10.1145/362248.362272. · DOI
  35. Adrian Hutter, James R Wootton, and Daniel Loss. Efficient markov chain monte carlo al- gorithm for the surface code. Physical Re- view A, 89(2):022326, 2014. DOI: 10.1103/Phys- RevA.89.022326. · DOI
  36. Adrian Hutter, Daniel Loss, and James R Woot- ton. Improved hdrg decoders for qudit and non-abelian quantum error correction. New Journal of Physics, 17(3):035017, 2015. DOI: 10.1088/1367-2630/17/3/035017. · DOI
  37. Norbert Kalb, Andreas A Reiserer, Peter C Humphreys, Jacob JW Bakermans, Sten J Kamerling, Naomi H Nickerson, Simon C Ben- jamin, Daniel J Twitchen, Matthew Markham, and Ronald Hanson. Entanglement distil- lation between solid-state quantum network nodes. Science, 356(6341):928-932, 2017. DOI: 10.1126/science.aan0070. · DOI
  38. Konrad Kieling, Terry Rudolph, and Jens Eis- ert. Percolation, renormalization, and quantum computing with nondeterministic gates. Physi- cal Review Letters, 99(13):130501, 2007. DOI: 10.1103/PhysRevLett.99.130501. · DOI · Paper page
  39. A Yu Kitaev. Fault-tolerant quantum computa- tion by anyons. Annals of Physics, 303(1):2-30, 2003. DOI: 10.1016/S0003-4916(02)00018-0. · DOI · Paper page
  40. Vladimir Kolmogorov. Blossom v: a new imple- mentation of a minimum cost perfect matching algorithm. Mathematical Programming Compu- tation, 1(1):43-67, 2009. DOI: 10.1007/s12532- 009-0002-8. · DOI
  41. Aleksander Marek Kubica. The ABCs of the Color Code: A Study of Topological Quantum Codes as Toy Models for Fault-Tolerant Quan- tum Computation and Quantum Phases Of Mat- ter. PhD thesis, California Institute of Technol- ogy, 2018.
  42. Andrew J Landahl, Jonas T Anderson, and Patrick R Rice. Fault-tolerant quantum com- puting with color codes. arXiv preprint arXiv:1108.5738, 2011. · arXiv
  43. Bjoern Lekitsch, Sebastian Weidt, Austin G Fowler, Klaus Mølmer, Simon J Devitt, Christof Wunderlich, and Winfried K Hensinger. Blueprint for a microwave trapped ion quan- tum computer. Science Advances, 3(2):e1601540, 2017. DOI: 10.1126/sciadv.1601540. · DOI
  44. Thomas Monz, Daniel Nigg, Esteban A Mar- tinez, Matthias F Brandl, Philipp Schindler, Richard Rines, Shannon X Wang, Isaac L Chuang, and Rainer Blatt. Realization of a scal- able shor algorithm. Science, 351(6277):1068- 1070, 2016. DOI: 10.1126/science.aad9480. · DOI · Paper page
  45. Michael A Nielsen. Optical quantum computa- tion using cluster states. Physical review let- ters, 93(4):040503, 2004. DOI: 10.1103/Phys- RevLett.93.040503. · DOI · Paper page
  46. R. Raussendorf and J. Harrington. Fault- tolerant quantum computation with high thresh- old in two dimensions. Physical Review Let- ters, 98(19):190504, 2007. DOI: 10.1103/Phys- RevLett.98.190504. · DOI · Paper page
  47. R. Raussendorf, J. Harrington, and K. Goyal. Topological fault-tolerance in cluster state quan- tum computation. New Journal of Physics, 9: 199, 2007. DOI: 10.1088/1367-2630/9/6/199. · DOI · Paper page
  48. Robert Raussendorf, Jim Harrington, and Kovid Goyal. A fault-tolerant one-way quantum com- puter. Annals of physics, 321(9):2242-2270, 2006. DOI: 10.1016/j.aop.2006.01.012. · DOI · Paper page
  49. Pradeep Sarvepalli and Robert Raussendorf. Efficient decoding of topological color codes. Physical Review A, 85(2):022317, 2012. DOI: 10.1103/PhysRevA.85.022317. · DOI
  50. Thomas M Stace and Sean D Barrett. Error cor- rection and degeneracy in surface codes suffer- ing loss. Physical Review A, 81(2):022317, 2010. DOI: 10.1103/PhysRevA.81.022317. · DOI
  51. Thomas M Stace and Sean D Barrett. Error cor- rection and degeneracy in surface codes suffer- ing loss. Physical Review A, 81(2):022317, 2010. DOI: 10.1103/PhysRevA.81.022317. · DOI
  52. T.M. Stace, S.D. Barrett, and A.C. Doherty. Thresholds for topological codes in the presence of loss. Physical Review Letters, 102(20):200501, 2009. DOI: 10.1103/PhysRevLett.102.200501. · DOI
  53. Robert Endre Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM (JACM), 22(2):215-225, 1975. DOI: 10.1145/321879.321884. · DOI
  54. Robert Endre Tarjan. A class of algorithms which require nonlinear time to maintain dis- joint sets. Journal of computer and system sci- ences, 18(2):110-127, 1979. DOI: 10.1016/0022- 0000(79)90042-4. · DOI
  55. Giacomo Torlai and Roger G Melko. Neural de- coder for topological codes. Physical Review Let- ters, 119(3):030501, 2017. DOI: 10.1103/Phys- RevLett.119.030501. · DOI
  56. David K Tuckett, Stephen D Bartlett, and Steven T Flammia. Ultra-high error threshold for surface codes with biased noise. arXiv preprint arXiv:1708.08474, 2017. DOI: 10.1103/Phys- RevLett.120.050505. · DOI · Paper page
  57. Savvas Varsamopoulos, Ben Criger, and Koen Bertels. Decoding small surface codes with feedforward neural networks. arXiv preprint arXiv:1705.00857, 2017. DOI: 10.1088/2058- 9565/aa955a. · DOI
  58. Chenyang Wang, Jim Harrington, and John Preskill. Confinement-higgs transition in a dis- ordered gauge theory and the accuracy thresh- old for quantum memory. Annals of Physics, 303(1):31-58, 2003. DOI: 10.1016/S0003- 4916(02)00019-2. · DOI
  59. David S Wang, Austin G Fowler, Charles D Hill, and Lloyd Christopher L Hollenberg. Graphi- cal algorithms and threshold error rates for the 2d colour code. Quantum Info. Comput., 10 (9):780-802, sep 2009. ISSN 1533-7146. DOI: 10.5555/2011464.2011469. · DOI
  60. Fern HE Watson, Hussain Anwar, and Dan E Browne. Fast fault-tolerant decoder for qubit and qudit surface codes. Physical Review A, 92(3):032309, 2015. DOI: 10.1103/Phys- RevA.92.032309. · DOI
  61. Adam C. Whiteside and Austin G. Fowler. Upper bound for loss in practical topological- cluster-state quantum computing. Phys. Rev. A, 90:052316, Nov 2014. DOI: 10.1103/Phys- RevA.90.052316. · DOI
  62. James Wootton. A simple decoder for topologi- cal codes. Entropy, 17(4):1946-1957, 2015. DOI: 10.3390/e17041946. · DOI
  63. James R Wootton and Daniel Loss. High thresh- old error correction for the surface code. Phys- ical review letters, 109(16):160503, 2012. DOI: 10.1103/PhysRevLett.109.160503. · DOI
  64. Gilles Zémor. On cayley graphs, surface codes, and the limits of homological coding for quan- tum error correction. In IWCC, pages 259-273. Springer, 2009. DOI: 10.1007/978-3-642-01877- 0_21. · DOI

Cited by

Sorted by citations

Authors
Delfosse, N., & Nickerson, N. H.
Affiliations
  • University of California, Riverside (US)
  • Imperial College London (GB)
ORCID
Venue
Quantum
Publisher
Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften
Published
2021-12-02
Volume
5
Pages
595
ISSN
2521-327X (ISSN-L)
DOI
10.22331/q-2021-12-02-595
OpenAlex
W2755710612
Cited by
242
References
3
Citations by year
2026: 37 · 2025: 70 · 2024: 36 · 2023: 38 · 2022: 23 · 2021: 14 · 2020: 14 · 2019: 7 · 2018: 2 · 2017: 1
FWCI
9.72
Type
journal article
Language
en
Open access
Licence
Locations
  • Quantum (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • CaltechAUTHORS (California Institute of Technology) (submittedVersion, cc-by)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • arXiv (Cornell University) (cc-by)
Funders
  • National Science Foundation (1125565)
  • Gordon and Betty Moore Foundation (PHY-1125565, GBMF2644)
  • Institute for Quantum Information and Matter, California Institute of Technology (PHY-1125565)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
  • Physical Sciences › Computer Science › Computer Networks and Communications › Error Correcting Code Techniques
Keywords
topological codes, quantum error correction, decoding algorithms, erasure errors, toric code, threshold, Ackermann function, minimum distance

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