Efficient color code decoders in $d\geq 2$ dimensions from toric code decoders

Aleksander Kubica; Nicolas Delfosse

doi:10.22331/q-2023-02-21-929

Efficient color code decoders in $d\geq 2$ dimensions from toric code decoders

Aleksander Kubica^1,2 and Nicolas Delfosse³

¹Perimeter Institute for Theoretical Physics, Waterloo, ON N2L 2Y5, Canada
²Institute for Quantum Computing, University of Waterloo, Waterloo, ON N2L 3G1, Canada
³Station Q Quantum Architectures and Computation Group, Microsoft Research, Redmond, WA 98052, USA

Published:	2023-02-21, volume 7, page 929
Eprint:	arXiv:1905.07393v3
Doi:	https://doi.org/10.22331/q-2023-02-21-929
Citation:	Quantum 7, 929 (2023).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We introduce an efficient decoder of the color code in $d\geq 2$ dimensions, the Restriction Decoder, which uses any $d$-dimensional toric code decoder combined with a local lifting procedure to find a recovery operation. We prove that the Restriction Decoder successfully corrects errors in the color code if and only if the corresponding toric code decoding succeeds. We also numerically estimate the Restriction Decoder threshold for the color code in two and three dimensions against the bit-flip and phase-flip noise with perfect syndrome extraction. We report that the 2D color code threshold $p_{\textrm{2D}} \approx 10.2\%$ on the square-octagon lattice is on a par with the toric code threshold on the square lattice.

Featured image: The Restriction Decoder combines a toric code decoder with a local lifting procedure in oder to find a recovery operator for the color code.

Conference Talk: Error correction with the color code

► BibTeX data

@article{Kubica2023efficientcolorcode,
  doi = {10.22331/q-2023-02-21-929},
  url = {https://doi.org/10.22331/q-2023-02-21-929},
  title = {Efficient color code decoders in {$d\geq 2$} dimensions from toric code decoders},
  author = {Kubica, Aleksander and Delfosse, Nicolas},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {929},
  month = feb,
  year = {2023}
}

► References

[1] A. Y. Kitaev, Fault-tolerant quantum computation by anyons, Annals Phys. 303, 2 (2003).
https://doi.org/10.1016/S0003-4916(02)00018-0

[2] S. B. Bravyi and A. Y. Kitaev, Quantum codes on a lattice with boundary, arXiv:quant-ph/9811052 (1998).
https://doi.org/10.48550/arXiv.quant-ph/9811052
arXiv:quant-ph/9811052

[3] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topological quantum memory, Journal of Mathematical Physics 43, 4452 (2002).
https://doi.org/10.1063/1.1499754

[4] B. Zeng, A. Cross, and I. L. Chuang, Transversality versus universality for additive quantum codes, IEEE Transactions on Information Theory 57, 6272 (2011).
https://doi.org/10.1109/TIT.2011.2161917

[5] B. Eastin and E. Knill, Restrictions on transversal encoded quantum gate sets, Physical Review Letters 102, 110502 (2009).
https://doi.org/10.1103/PhysRevLett.102.110502

[6] S. Bravyi and R. König, Classification of Topologically Protected Gates for Local Stabilizer Codes, Physical Review Letters 110, 170503 (2013).
https://doi.org/10.1103/PhysRevLett.110.170503

[7] F. Pastawski and B. Yoshida, Fault-tolerant logical gates in quantum error-correcting codes, Physical Review A 91, 13 (2015).
https://doi.org/10.1103/PhysRevA.91.012305

[8] T. Jochym-O'Connor, A. Kubica, and T. J. Yoder, Disjointness of Stabilizer Codes and Limitations on Fault-Tolerant Logical Gates, Physical Review X 8, 21047 (2018).
https://doi.org/10.1103/PhysRevX.8.021047

[9] S. Bravyi and A. Kitaev, Universal quantum computation with ideal Clifford gates and noisy ancillas, Physical Review A 71, 022316 (2005).
https://doi.org/10.1103/PhysRevA.71.022316

[10] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Physical Review A 86, 032324 (2012).
https://doi.org/10.1103/PhysRevA.86.032324

[11] H. Bombin and M. A. Martin-Delgado, Topological Quantum Distillation, Physical Review Letters 97, 180501 (2006).
https://doi.org/10.1103/PhysRevLett.97.180501

[12] H. Bombin and M. Martin-Delgado, Exact topological quantum order in D=3 and beyond: Branyons and brane-net condensates, Physical Review B 75, 075103 (2007).
https://doi.org/10.1103/PhysRevB.75.075103

[13] A. Kubica, The ABCs of the color code: A study of topological quantum codes as toy models for fault-tolerant quantum computation and quantum phases of matter, Ph.D. thesis (2018).
https://doi.org/10.7907/059V-MG69

[14] A. Paetznick and B. W. Reichardt, Universal Fault-Tolerant Quantum Computation with Only Transversal Gates and Error Correction, Physical Review Letters 111, 090505 (2013).
https://doi.org/10.1103/PhysRevLett.111.090505

[15] J. T. Anderson, G. Duclos-Cianci, and D. Poulin, Fault-tolerant conversion between the Steane and Reed-Muller quantum codes, Physical Review Letters 113, 6 (2014).
https://doi.org/10.1103/PhysRevLett.113.080501

[16] H. Bombín, Dimensional jump in quantum error correction, New Journal of Physics 18, 043038 (2016).
https://doi.org/10.1088/1367-2630/18/4/043038

[17] H. Bombín, Gauge color codes: Optimal transversal gates and gauge fixing in topological stabilizer codes, New Journal of Physics 17, 083002 (2015).
https://doi.org/10.1088/1367-2630/17/8/083002

[18] A. Kubica and M. E. Beverland, Universal transversal gates with color codes: A simplified approach, Physical Review A 91, 032330 (2015).
https://doi.org/10.1103/PhysRevA.91.032330

[19] M. E. Beverland, A. Kubica, and K. M. Svore, Cost of universality: A comparative study of the overhead of state distillation and code switching with color codes, PRX Quantum 2, 020341 (2021).
https://doi.org/10.1103/PRXQuantum.2.020341

[20] A. Kubica, B. Yoshida, and F. Pastawski, Unfolding the color code, New Journal of Physics 17, 083026 (2015).
https://doi.org/10.1088/1367-2630/17/8/083026

[21] D. S. Wang, A. G. Fowler, C. D. Hill, and L. C. L. Hollenberg, Graphical algorithms and threshold error rates for the 2d colour code, Quantum Information and Computation 10, 780 (2010).
https://doi.org/10.48550/arXiv.0907.1708

[22] A. J. Landahl, J. T. Anderson, and P. R. Rice, Fault-tolerant quantum computing with color codes, arXiv:1108.5738 (2011).
https://doi.org/10.48550/arXiv.1108.5738
arXiv:1108.5738

[23] P. Sarvepalli and R. Raussendorf, Efficient decoding of topological color codes, Physical Review A - Atomic, Molecular, and Optical Physics 85, 022317 (2012).
https://doi.org/10.1103/PhysRevA.85.022317

[24] H. Bombin, G. Duclos-Cianci, and D. Poulin, Universal topological phase of two-dimensional stabilizer codes, New Journal of Physics 14, 073048 (2012).
https://doi.org/10.1088/1367-2630/14/7/073048

[25] N. Delfosse, Decoding color codes by projection onto surface codes, Physical Review A 89, 012317 (2014).
https://doi.org/10.1103/PhysRevA.89.012317

[26] N. Delfosse and N. H. Nickerson, Almost-linear time decoding algorithm for topological codes, Quantum 5, 595 (2021).
https://doi.org/10.22331/q-2021-12-02-595

[27] N. Maskara, A. Kubica, and T. Jochym-O'Connor, Advantages of versatile neural-network decoding for topological codes, Physical Review A 99, 052351 (2019).
https://doi.org/10.1103/PhysRevA.99.052351

[28] D. K. Tuckett, A. S. Darmawan, C. T. Chubb, S. Bravyi, S. D. Bartlett, and S. T. Flammia, Tailoring surface codes for highly biased noise, Physical Review X 9, 041031 (2019).
https://doi.org/10.1103/PhysRevX.9.041031

[29] F. Pastawski, L. Clemente, and J. I. Cirac, Quantum memories based on engineered dissipation, Physical Review A 83, 012304 (2011).
https://doi.org/10.1103/PhysRevA.83.012304

[30] K. Duivenvoorden, N. P. Breuckmann, and B. M. Terhal, Renormalization Group Decoder for a Four-Dimensional Toric Code, IEEE Transactions on Information Theory 65, 2545 (2019).
https://doi.org/10.1109/TIT.2018.2879937

[31] N. P. Breuckmann, K. Duivenvoorden, D. Michels, and B. M. Terhal, Local Decoders for the 2D and 4D Toric Code, Quantum Information and Computation 17, 0181 (2017).
https://doi.org/10.48550/arXiv.1609.00510

[32] N. P. Breuckmann and X. Ni, Scalable Neural Network Decoders for Higher Dimensional Quantum Codes, Quantum 2, 68 (2018).
https://doi.org/10.22331/q-2018-05-24-68

[33] A. Kubica and J. Preskill, Cellular-Automaton Decoders with Provable Thresholds for Topological Codes, Physical Review Letters 123, 020501 (2019).
https://doi.org/10.1103/PhysRevLett.123.020501

[34] P. W. Shor, Scheme for reducing decoherence in quantum computer memory, Physical Review A 52, R2493 (1995).
https://doi.org/10.1103/PhysRevA.52.R2493

[35] D. Gottesman, Class of quantum error-correcting codes saturating the quantum Hamming bound, Physical Review A 54, 1862 (1996).
https://doi.org/10.1103/PhysRevA.54.1862

[36] A. Calderbank and P. Shor, Good quantum error-correcting codes exist, Physical Review A 54, 1098 (1996).
https://doi.org/10.1103/PhysRevA.54.1098

[37] A. Calderbank, E. Rains, P. Shor, and N. Sloane, Quantum Error Correction and Orthogonal Geometry, Physical Review Letters 78, 405 (1997).
https://doi.org/10.1103/PhysRevLett.78.405

[38] H. Bombin, in Topological Codes, edited by D. A. Lidar and T. A. Brun (Cambridge University Press, 2013).
https://doi.org/10.48550/arXiv.1311.0277

[39] J. Edmonds, Paths, Trees, and Flowers, Canadian Journal of Mathematics 17, 449 (1965).
https://doi.org/10.4153/CJM-1965-045-4

[40] A. B. Aloshious and P. K. Sarvepalli, Projecting three-dimensional color codes onto three-dimensional toric codes, Physical Review A 98, 9 (2018).
https://doi.org/10.1103/PhysRevA.98.012302

[41] V. Kolmogorov, Blossom V: a new implementation of a minimum cost perfect matching algorithm, Mathematical Programming Computation 1, 43 (2009).
https://doi.org/10.1007/s12532-009-0002-8

[42] S. Bravyi and M. B. Hastings, in Proceedings of the forty-sixth annual ACM symposium on Theory of computing (2014) pp. 273—-282.
https://doi.org/10.1145/2591796.2591870

[43] A. Kubica and B. Yoshida, Ungauging quantum error-correcting codes, arXiv:1805.01836 (2018).
https://doi.org/10.48550/ARXIV.1805.01836
arXiv:1805.01836

[44] A. Hatcher, Algebraic Topology (Cambridge University Press, 2002).

[45] L. C. Glaser, Geometric combinatorial topology (Van Nostrand Reinhold Company, 1972).

[46] J. M. Sullivan, A crystalline approximation theorem for hypersurfaces, Ph.D. thesis (1990).

[47] A. L. Toom, in Multicomponent Systems, Vol. 6 (1980) pp. 549–575.

[48] C. H. Bennett and G. Grinstein, Role of irreversibility in stabilizing complex and nonergodic behavior in locally interacting discrete systems, Physical Review Letters 55, 657 (1985).
https://doi.org/10.1103/PhysRevLett.55.657

[49] N. Delfosse, in IEEE International Symposium on Information Theory - Proceedings (2013) pp. 917–921.
https://doi.org/10.1109/ISIT.2013.6620360

[50] S. Lang, Algebra (Springer, 2002).
https://doi.org/10.1007/978-1-4613-0041-0

[51] H. Bombín, Structure of 2D Topological Stabilizer Codes, Communications in Mathematical Physics 327, 387 (2014).
https://doi.org/10.1007/s00220-014-1893-4

[52] B. Yoshida, Classification of quantum phases and topology of logical operators in an exactly solved model of quantum codes, Annals of Physics 326, 15 (2011).
https://doi.org/10.1016/j.aop.2010.10.009

[53] J. Haah, Commuting Pauli Hamiltonians as Maps between Free Modules, Communications in Mathematical Physics 324, 351 (2013).
https://doi.org/10.1007/s00220-013-1810-2

[54] J. Harrington, Analysis of quantum error-correcting codes: symplectic lattice codes and toric codes, Ph.D. thesis (2004).
https://doi.org/10.7907/AHMQ-EG82

[55] G. Duclos-Cianci and D. Poulin, Fast Decoders for Topological Quantum Codes, Physical Review Letters 104, 050504 (2010).
https://doi.org/10.1103/PhysRevLett.104.050504

[56] S. Bravyi and J. Haah, Quantum Self-Correction in the 3D Cubic Code Model, Physical Review Letters 111, 200501 (2013).
https://doi.org/10.1103/PhysRevLett.111.200501

[57] H. Anwar, B. J. Brown, E. T. Campbell, and D. E. Browne, Fast decoders for qudit topological codes, New Journal of Physics 16, 063038 (2014).
https://doi.org/10.1088/1367-2630/16/6/063038

[58] B. J. Brown, N. H. Nickerson, and D. E. Browne, Fault-Tolerant Error Correction with the Gauge Color Code, Nature Communications 7, 4 (2015).
https://doi.org/10.1038/ncomms12302

[59] H. G. Katzgraber, H. Bombin, and M. A. Martin-Delgado, Error Threshold for Color Codes and Random Three-Body Ising Models, Physical Review Letters 103, 090501 (2009).
https://doi.org/10.1103/PhysRevLett.103.090501

[60] A. Kubica, M. E. Beverland, F. Brandão, J. Preskill, and K. M. Svore, Three-Dimensional Color Code Thresholds via Statistical-Mechanical Mapping, Physical Review Letters 120, 180501 (2018).
https://doi.org/10.1103/PhysRevLett.120.180501

[61] M. Vasmer and A. Kubica, Morphing quantum codes, PRX Quantum 3, 030319 (2022).
https://doi.org/10.1103/PRXQuantum.3.030319

[62] M. Vasmer, D. E. Browne, and A. Kubica, Cellular automaton decoders for topological quantum codes with noisy measurements and beyond, Scientific reports 11, 1 (2021).
https://doi.org/10.1038/s41598-021-81138-2

[63] C. Chamberland, A. Kubica, T. J. Yoder, and G. Zhu, Triangular color codes on trivalent graphs with flag qubits, New Journal of Physics 22, 023019 (2020).
https://doi.org/10.1088/1367-2630/ab68fd

Cited by

[1] Shayan Srinivasa Garani, Priya J. Nadkarni, and Ankur Raina, "Theory Behind Quantum Error Correcting Codes: An Overview", Journal of the Indian Institute of Science 103 2, 449 (2023).

[2] Mohammad Hossein Zarei and Mohsen Rahmani Haghighi, "Layer-by-layer disentangling two-dimensional topological quantum codes", Physical Review B 108 3, 035116 (2023).

[3] Oscar Higgott, Thomas C. Bohdanowicz, Aleksander Kubica, Steven T. Flammia, and Earl T. Campbell, "Improved Decoding of Circuit Noise and Fragile Boundaries of Tailored Surface Codes", Physical Review X 13 3, 031007 (2023).

[4] Oscar Higgott, "PyMatching: A Python package for decoding quantum codes with minimum-weight perfect matching", arXiv:2105.13082, (2021).

[5] David K. Tuckett, Stephen D. Bartlett, Steven T. Flammia, and Benjamin J. Brown, "Fault-Tolerant Thresholds for the Surface Code in Excess of 5 % Under Biased Noise", Physical Review Letters 124 13, 130501 (2020).

[6] Michael E. Beverland, Aleksander Kubica, and Krysta M. Svore, "Cost of Universality: A Comparative Study of the Overhead of State Distillation and Code Switching with Color Codes", PRX Quantum 2 2, 020341 (2021).

[7] Djordje Radicevic, "Systematic Constructions of Fracton Theories", arXiv:1910.06336, (2019).

[8] Aleksander Kubica and John Preskill, "Cellular-Automaton Decoders with Provable Thresholds for Topological Codes", Physical Review Letters 123 2, 020501 (2019).

[9] Christopher Chamberland and Kyungjoo Noh, "Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits", npj Quantum Information 6, 91 (2020).

[10] Élie Gouzien and Nicolas Sangouard, "Factoring 2048-bit RSA Integers in 177 Days with 13 436 Qubits and a Multimode Memory", Physical Review Letters 127 14, 140503 (2021).

[11] Michael Vasmer, Dan E. Browne, and Aleksander Kubica, "Cellular automaton decoders for topological quantum codes with noisy measurements and beyond", Scientific Reports 11, 2027 (2021).

[12] Michael Vasmer and Aleksander Kubica, "Morphing Quantum Codes", PRX Quantum 3 3, 030319 (2022).

[13] Aleksander Kubica and Michael Vasmer, "Single-shot quantum error correction with the three-dimensional subsystem toric code", Nature Communications 13, 6272 (2022).

[14] Nicolas Delfosse, "Hierarchical decoding to reduce hardware requirements for quantum computing", arXiv:2001.11427, (2020).

[15] Felix Thomsen, Markus S. Kesselring, Stephen D. Bartlett, and Benjamin J. Brown, "Low-overhead quantum computing with the color code", arXiv:2201.07806, (2022).

[16] Christopher T. Chubb, "General tensor network decoding of 2D Pauli codes", arXiv:2101.04125, (2021).

[17] Armanda O. Quintavalle, Michael Vasmer, Joschka Roffe, and Earl T. Campbell, "Single-Shot Error Correction of Three-Dimensional Homological Product Codes", PRX Quantum 2 2, 020340 (2021).

[18] Samuel C. Smith, Benjamin J. Brown, and Stephen D. Bartlett, "Local Predecoder to Reduce the Bandwidth and Latency of Quantum Error Correction", Physical Review Applied 19 3, 034050 (2023).

[19] Tomas Jochym-O'Connor and Theodore J. Yoder, "Four-dimensional toric code with non-Clifford transversal gates", Physical Review Research 3 1, 013118 (2021).

[20] Robert J. Harris, Elliot Coupe, Nathan A. McMahon, Gavin K. Brennen, and Thomas M. Stace, "Decoding Holographic Codes with an Integer Optimisation Decoder", arXiv:2008.10206, (2020).

[21] Robert J. Harris, Elliot Coupe, Nathan A. McMahon, Gavin K. Brennen, and Thomas M. Stace, "Decoding holographic codes with an integer optimization decoder", Physical Review A 102 6, 062417 (2020).

[22] Christophe Vuillot and Nikolas P. Breuckmann, "Quantum Pin Codes", arXiv:1906.11394, (2019).

[23] Kaavya Sahay and Benjamin J. Brown, "Decoder for the Triangular Color Code by Matching on a Möbius Strip", PRX Quantum 3 1, 010310 (2022).

[24] Haowen Wang, Yunjia Xue, Yingjie Qu, Xiaoyi Mu, and Hongyang Ma, "Multidimensional Bose quantum error correction based on neural network decoder", npj Quantum Information 8, 134 (2022).

[25] Arun B. Aloshious and Pradeep Kiran Sarvepalli, "Decoding toric codes on three dimensional simplical complexes", arXiv:1911.06056, (2019).

[26] Eric Sabo, Arun B. Aloshious, and Kenneth R. Brown, "Trellis Decoding For Qudit Stabilizer Codes And Its Application To Qubit Topological Codes", arXiv:2106.08251, (2021).

[27] Noah Shutty and Christopher Chamberland, "Decoding Merged Color-Surface Codes and Finding Fault-Tolerant Clifford Circuits Using Solvers for Satisfiability Modulo Theories", Physical Review Applied 18 1, 014072 (2022).

[28] Jiaxuan Zhang, Jian Zhao, Yu-Chun Wu, and Guo-Ping Guo, "Quantum error correction with the color-Gottesman-Kitaev-Preskill code", Physical Review A 104 6, 062434 (2021).

[29] Theerapat Tansuwannont and Debbie Leung, "Achieving Fault Tolerance on Capped Color Codes with Few Ancillas", PRX Quantum 3 3, 030322 (2022).

[30] Balint Pato, Theerapat Tansuwannont, Shilin Huang, and Kenneth R. Brown, "Optimization tools for distance-preserving flag fault-tolerant error correction", arXiv:2306.12862, (2023).

[31] Seok-Hyung Lee and Hyunseok Jeong, "Universal hardware-efficient topological measurement-based quantum computation via color-code-based cluster states", Physical Review Research 4 1, 013010 (2022).

[32] Skylar Turner, Josey Hanish, Eion Blanchard, Noah Davis, and Brian La Cour, "A Decoder for the Color Code with Boundaries", arXiv:2003.11602, (2020).

[33] July X. Li, Joseph M. Renes, and Pascal O. Vontobel, "Pseudocodeword-based Decoding of Quantum Color Codes", arXiv:2010.10845, (2020).

[34] Pedro Parrado-Rodríguez, Manuel Rispler, and Markus Müller, "Rescaling decoder for two-dimensional topological quantum color codes on 4.8.8 lattices", Physical Review A 106 3, 032431 (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-22 13:34:28) and SAO/NASA ADS (last updated successfully 2023-09-22 13:34:29). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.