Efficient Color Code Decoders In $dgeq 2$ Dimensions From Toric Code Decoders

Republished By Plato

Followers: 0

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

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 $dgeq 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 {$dgeq 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}<br /> }

► 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] 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).

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

[3] Djordje Radicevic, “Systematic Constructions of Fracton Theories”, arXiv:1910.06336, (2019).

[4] É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).

[5] 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).

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

[7] 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).

[8] 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).

[9] Samuel C. Smith, Benjamin J. Brown, and Stephen D. Bartlett, “A local pre-decoder to reduce the bandwidth and latency of quantum error correction”, arXiv:2208.04660, (2022).

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

[11] 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).

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

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

[14] 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).

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

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

[17] Michael Vasmer and Aleksander Kubica, “Morphing Quantum Codes”, PRX Quantum 3 3, 030319 (2022).

[18] 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).

[19] Christophe Vuillot and Nikolas P. Breuckmann, “Quantum Pin Codes”, arXiv:1906.11394, (2019).

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

[21] 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).

[22] 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).

[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] Theerapat Tansuwannont and Debbie Leung, “Achieving Fault Tolerance on Capped Color Codes with Few Ancillas”, PRX Quantum 3 3, 030322 (2022).

[25] 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).

[26] 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).

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

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

[29] 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).

[30] 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 SAO/NASA ADS (last updated successfully 2023-02-22 05:14:24). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2023-02-22 05:14:22).

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.

SEO Powered Content & PR Distribution. Get Amplified Today.
Platoblockchain. Web3 Metaverse Intelligence. Knowledge Amplified. Access Here.
Source: https://quantum-journal.org/papers/q-2023-02-21-929/

Time Stamp: February 21, 2023

Time Stamp: May 4, 2023

Efficient color code decoders in $dgeq 2$ dimensions from toric code decoders

Republished By Plato

Abstract

► BibTeX data

► References

Cited by

More from Quantum Journal

Universal construction of genuinely entangled subspaces of any size

Sequential hypothesis testing for continuously-monitored quantum systems

Spacetime-Efficient Low-Depth Quantum State Preparation with Applications

Matrix concentration inequalities and efficiency of random universal sets of quantum gates

Entanglement-enhanced test proposal for local Lorentz-symmetry violation via spinor atoms

Dissipative phase transitions in $n$-photon driven quantum nonlinear resonators

Fluid fermionic fragments for optimizing quantum measurements of electronic Hamiltonians in the variational quantum eigensolver

Transformations of Stabilizer States in Quantum Networks

Determining the ability for universal quantum computing: Testing controllability via dimensional expressivity

Sample-efficient verification of continuously-parameterized quantum gates for small quantum processors

About Us

Vertical Search & Ai

Platform

Stay Connected

Account