Generalizing the matching decoder for the Chamon code

Zohar Schwartzman-Nowik; Benjamin J. Brown

doi:10.22331/q-2025-06-18-1775

Generalizing the matching decoder for the Chamon code

Zohar Schwartzman-Nowik^1,2 and Benjamin J. Brown³

¹School of Computer Science and Engineering, Hebrew University, Jerusalem, Israel
²Faculty of Engineering and the Institute of Nanotechnology and Advanced Materials, Bar Ilan University, Ramat Gan, Israel
³IBM Denmark, Sundkrogsgade 11, 2100 Copenhagen, Denmark

Published:	2025-06-18, volume 9, page 1775
Editor:	Alioscia Hamma
Eprint:	arXiv:2411.03443v2
Doi:	https://doi.org/10.22331/q-2025-06-18-1775
Citation:	Quantum 9, 1775 (2025).

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

Abstract

Different choices of quantum error-correcting codes can reduce the demands on the physical hardware needed to build a quantum computer. To achieve the full potential of a code, we must develop practical decoding algorithms that can correct errors that have occurred with high likelihood. Matching decoders are very good at correcting local errors while also demonstrating fast run times that can keep pace with physical quantum devices. We implement variations of a matching decoder for a three-dimensional, non-CSS, low-density parity check code known as the Chamon code, which has a non-trivial structure that does not lend itself readily to this type of decoding. The non-trivial structure of the syndrome of this code means that we can supplement the decoder with additional steps to improve the threshold error rate, below which the logical failure rate decreases with increasing code distance. We find that a generalized matching decoder that is augmented by a belief-propagation step prior to matching gives a threshold of 10.5% for depolarizing noise.

Featured image: A plane of checks of the three-dimensional Chamon code that respects a symmetry. All errors violate exactly two distinct checks. This property allows us to use matching to look for clusters in the syndrome that can be locally corrected. Checks are shown by black sites and qubits are shown by white sites. Single qubit Pauli errors shown on the colored qubit sites violate exactly two checks, shown by yellow check sites.

Popular summary

Minimum-weight perfect matching (MWPM) decoders are very effective decoders for quantum error correction, offering both speed and accuracy. However their use has largely been limited to well structured codes, with specific syndrome properties. In this work, we extend the reach of matching-based decoding to more complex quantum codes. We focus on the Chamon code, a three-dimensional, non-CSS, low-density parity-check (LDPC) code with a non-trivial syndrome structure. By identifying and exploiting hidden symmetries within the code, we define subsets of stabilizers that allow us to apply matching decoders locally. We further enhance this approach using belief propagation to pass global information into these local decoders, leading to a high threshold of 10.5% under depolarizing noise. This work shows that matching decoders, long considered limited to a narrow class of codes, can be generalized to handle a broader range of quantum LDPC codes, including those with complex or unconventional structure. This opens new possibilities for practical quantum error correction beyond the standard code families.

► BibTeX data

@article{SchwartzmanNowik2025generalizing,
  doi = {10.22331/q-2025-06-18-1775},
  url = {https://doi.org/10.22331/q-2025-06-18-1775},
  title = {Generalizing the matching decoder for the {C}hamon code},
  author = {Schwartzman-Nowik, Zohar and Brown, Benjamin J.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1775},
  month = jun,
  year = {2025}
}

► References

[1] Dorit Aharonov and Michael Ben-Or. Fault-tolerant quantum computation with constant error. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 176–188, 1997. URL https://doi.org/10.1145/258533.258579.
https://doi.org/10.1145/258533.258579

[2] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43 (9): 4452–4505, 2002. URL https://doi.org/10.1063/1.1499754.
https://doi.org/10.1063/1.1499754

[3] Antonio deMarti iOlius, Patricio Fuentes, Román Orús, Pedro M Crespo, and Josu Etxezarreta Martinez. Decoding algorithms for surface codes. Quantum, 8: 1498, 2024. ISSN 2521-327X. URL https://doi.org/10.22331/q-2024-10-10-1498.
https://doi.org/10.22331/q-2024-10-10-1498

[4] Guillaume Duclos-Cianci and David Poulin. Fast decoders for topological quantum codes. Phys. Rev. Lett., 104: 050504, Feb 2010. URL https://doi.org/10.1103/PhysRevLett.104.050504.
https://doi.org/10.1103/PhysRevLett.104.050504

[5] Sergey Bravyi and Jeongwan Haah. Quantum self-correction in the 3d cubic code model. Phys. Rev. Lett., 111: 200501, 2013. URL https://doi.org/10.1103/PhysRevLett.111.200501.
https://doi.org/10.1103/PhysRevLett.111.200501

[6] James R. Wootton and Daniel Loss. High threshold error correction for the surface code. Phys. Rev. Lett., 109: 160503, Oct 2012. URL https://doi.org/10.1103/PhysRevLett.109.160503.
https://doi.org/10.1103/PhysRevLett.109.160503

[7] Nicolas Delfosse and Naomi H Nickerson. Almost-linear time decoding algorithm for topological codes. Quantum, 5: 595, 2021. URL https://doi.org/10.22331/q-2021-12-02-595.
https://doi.org/10.22331/q-2021-12-02-595

[8] Sergey Bravyi, Martin Suchara, and Alexander Vargo. Efficient algorithms for maximum likelihood decoding in the surface code. Phys. Rev. A, 90: 032326, 2014. URL https://doi.org/10.1103/PhysRevA.90.032326.
https://doi.org/10.1103/PhysRevA.90.032326

[9] Jack Edmonds. Paths, trees, and flowers. Canadian Journal of mathematics, 17: 449–467, 1965. URL https://doi.org/10.4153/CJM-1965-045-4.
https://doi.org/10.4153/CJM-1965-045-4

[10] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. Surface codes: Towards practical large-scale quantum computation. Phys. Rev. A, 86: 032324, 2012. URL https://doi.org/10.1103/PhysRevA.86.032324.
https://doi.org/10.1103/PhysRevA.86.032324

[11] J Pablo Bonilla Ataides, David K Tuckett, Stephen D Bartlett, Steven T Flammia, and Benjamin J Brown. The xzzx surface code. Nature communications, 12 (1): 2172, 2021. URL https://doi.org/10.1038/s41467-021-22274-1.
https://doi.org/10.1038/s41467-021-22274-1

[12] Benjamin J Brown. Conservation laws and quantum error correction: towards a generalised matching decoder. IEEE BITS the Information Theory Magazine, 2023. URL https://doi.org/10.1109/MBITS.2023.3246025.
https://doi.org/10.1109/MBITS.2023.3246025

[13] Oscar Higgott. Pymatching: A python package for decoding quantum codes with minimum-weight perfect matching. ACM Transactions on Quantum Computing, 3 (3): 1–16, 2022. URL https://doi.org/10.1145/3505637.
https://doi.org/10.1145/3505637

[14] Oscar Higgott and Craig Gidney. Sparse blossom: correcting a million errors per core second with minimum-weight matching. Quantum, 9: 1600, 2025. URL https://doi.org/10.22331/q-2025-01-20-1600.
https://doi.org/10.22331/q-2025-01-20-1600

[15] Sebastian Krinner, Nathan Lacroix, Ants Remm, Agustin Di Paolo, Elie Genois, Catherine Leroux, Christoph Hellings, Stefania Lazar, Francois Swiadek, Johannes Herrmann, Graham J. Norris, Christian Kraglund Andersen, Markus Müller, Alexandre Blais, Christopher Eichler, and Andreas Wallraff. Realizing repeated quantum error correction in a distance-three surface code. Nature, 605 (7911), 2022. ISSN 1476-4687. URL https://doi.org/10.1038/s41586-022-04566-8.
https://doi.org/10.1038/s41586-022-04566-8

[16] Neereja Sundaresan, Theodore J. Yoder, Youngseok Kim, Muyuan Li, Edward H. Chen, Grace Harper, Ted Thorbeck, Andrew W. Cross, Antonio D. Córcoles, and Maika Takita. Demonstrating multi-round subsystem quantum error correction using matching and maximum likelihood decoders. Nature Communications, 14 (1): 2852, 2023. URL https://doi.org/10.1038/s41467-023-38247-5.
https://doi.org/10.1038/s41467-023-38247-5

[17] Yue Wu and Lin Zhong. Fusion blossom: Fast mwpm decoders for qec. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 01, 2023. URL https://doi.org/10.1109/QCE57702.2023.00107.
https://doi.org/10.1109/QCE57702.2023.00107

[18] Cody Jones. Improved accuracy for decoding surface codes with matching synthesis, 2024. URL https://doi.org/10.48550/arXiv.2408.12135.
https://doi.org/10.48550/arXiv.2408.12135

[19] Google Quantum AI. Quantum error correction below the surface code threshold. Nature, 638: 920–926, 2025. URL https://doi.org/10.1038/s41586-024-08449-y.
https://doi.org/10.1038/s41586-024-08449-y

[20] A.Yu. Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303 (1): 2–30, 2003. ISSN 0003-4916. URL https://doi.org/10.1016/S0003-4916(02)00018-0.
https://doi.org/10.1016/S0003-4916(02)00018-0

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

[22] David S. Wang, Austin G. Fowler, Charles D. Hill, and Lloyd C. L. Hollenberg. Graphical algorithms and threshold error rates for the 2d color code. Quantum Info. Comput., 10 (9): 780–802, September 2010. ISSN 1533-7146. URL https://doi.org/10.26421/QIC10.9-10-5.
https://doi.org/10.26421/QIC10.9-10-5

[23] Georgia M. Nixon and Benjamin J. Brown. Correcting spanning errors with a fractal code. IEEE Transactions on Information Theory, 67 (7): 4504–4516, 2021. URL https://doi.org/10.1109/TIT.2021.3068359.
https://doi.org/10.1109/TIT.2021.3068359

[24] Jonathan F. San Miguel, Dominic J. Williamson, and Benjamin J. Brown. A cellular automaton decoder for a noise-bias tailored color code. Quantum, 7: 940, March 2023. ISSN 2521-327X. URL https://doi.org/10.22331/q-2023-03-09-940.
https://doi.org/10.22331/q-2023-03-09-940

[25] Nicolas Delfosse. Decoding color codes by projection onto surface codes. Phys. Rev. A, 89: 012317, Jan 2014. URL https://doi.org/10.1103/PhysRevA.89.012317.
https://doi.org/10.1103/PhysRevA.89.012317

[26] Benjamin J Brown and Dominic J Williamson. Parallelized quantum error correction with fracton topological codes. Physical Review Research, 2 (1): 013303, 2020. URL https://doi.org/10.1103/PhysRevResearch.2.013303.
https://doi.org/10.1103/PhysRevResearch.2.013303

[27] 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. Phys. Rev. Lett., 124: 130501, Mar 2020. URL https://doi.org/10.1103/PhysRevLett.124.130501.
https://doi.org/10.1103/PhysRevLett.124.130501

[28] Basudha Srivastava, Anton Frisk Kockum, and Mats Granath. The XYZ$^2$ hexagonal stabilizer code. Quantum, 6: 698, April 2022. ISSN 2521-327X. URL https://doi.org/10.22331/q-2022-04-27-698.
https://doi.org/10.22331/q-2022-04-27-698

[29] Kaavya Sahay and Benjamin J. Brown. Decoder for the triangular color code by matching on a möbius strip. PRX Quantum, 3: 010310, Jan 2022. URL https://doi.org/10.1103/PRXQuantum.3.010310.
https://doi.org/10.1103/PRXQuantum.3.010310

[30] Aleksander Kubica and Nicolas Delfosse. Efficient color code decoders in $d\geq 2$ dimensions from toric code decoders. Quantum, 7: 929, February 2023. ISSN 2521-327X. URL https://doi.org/10.22331/q-2023-02-21-929.
https://doi.org/10.22331/q-2023-02-21-929

[31] Eric Huang, Arthur Pesah, Christopher T. Chubb, Michael Vasmer, and Arpit Dua. Tailoring three-dimensional topological codes for biased noise. PRX Quantum, 4: 030338, Sep 2023. URL https://doi.org/10.1103/PRXQuantum.4.030338.
https://doi.org/10.1103/PRXQuantum.4.030338

[32] Asmae Benhemou, Kaavya Sahay, Lingling Lao, and Benjamin J. Brown. Minimising surface-code failures using a color-code decoder. Quantum, 9: 1632, 2025. ISSN 2521-327X. URL https://doi.org/10.22331/q-2025-02-17-1632.
https://doi.org/10.22331/q-2025-02-17-1632

[33] Claudio Chamon. Quantum glassiness in strongly correlated clean systems: An example of topological overprotection. Physical review letters, 94 (4): 040402, 2005. URL https://doi.org/10.1103/PhysRevLett.94.040402.
https://doi.org/10.1103/PhysRevLett.94.040402

[34] Sergey Bravyi, Bernhard Leemhuis, and Barbara M Terhal. Topological order in an exactly solvable 3d spin model. Annals of Physics, 326 (4): 839–866, 2011. URL https://doi.org/10.1016/j.aop.2010.11.002.
https://doi.org/10.1016/j.aop.2010.11.002

[35] Jian Zhao, Yu-Chun Wu, and Guo-Ping Guo. Quantum memory error correction computation based on chamon model, 2023. URL https://doi.org/10.48550/arXiv.2303.05267.
https://doi.org/10.48550/arXiv.2303.05267

[36] Naomi H. Nickerson and Benjamin J. Brown. Analysing correlated noise on the surface code using adaptive decoding algorithms. Quantum, 3: 131, April 2019. ISSN 2521-327X. URL https://doi.org/10.22331/q-2019-04-08-131.
https://doi.org/10.22331/q-2019-04-08-131

[37] Craig Gidney and Cody Jones. New circuits and an open source decoder for the color code, 2023. URL https://doi.org/10.48550/arXiv.2312.08813.
https://doi.org/10.48550/arXiv.2312.08813

[38] 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. URL https://doi.org/10.1088/1367-2630/16/6/063038.
https://doi.org/10.1088/1367-2630/16/6/063038

[39] 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. URL https://doi.org/10.1103/PhysRevApplied.19.034050.
https://doi.org/10.1103/PhysRevApplied.19.034050

[40] David J. C. MacKay. Information Theory, Inference, and Learning Algorithms. Copyright Cambridge University Press, 2003. URL https://www.inference.org.uk/itila/.
https://www.inference.org.uk/itila/

[41] 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. Phys. Rev. X, 13: 031007, Jul 2023. URL https://doi.org/10.1103/PhysRevX.13.031007.
https://doi.org/10.1103/PhysRevX.13.031007

[42] Austin G. Fowler. Optimal complexity correction of correlated errors in the surface code, 2013. URL https://doi.org/10.48550/arXiv.1310.0863.
https://doi.org/10.48550/arXiv.1310.0863

[43] Nicolas Delfosse and Jean-Pierre Tillich. A decoding algorithm for css codes using the x/z correlations. In 2014 IEEE International Symposium on Information Theory, pages 1071–1075, 2014. URL https://doi.org/10.1109/ISIT.2014.6874997.
https://doi.org/10.1109/ISIT.2014.6874997

[44] Anthony Leverrier, Simon Apers, and Christophe Vuillot. Quantum XYZ Product Codes. Quantum, 6: 766, July 2022. ISSN 2521-327X. URL https://doi.org/10.22331/q-2022-07-14-766.
https://doi.org/10.22331/q-2022-07-14-766

[45] Daniel Gottesman. Stabilizer codes and quantum error correction. California Institute of Technology, 1997. URL https://thesis.library.caltech.edu/2900/.
https://thesis.library.caltech.edu/2900/

[46] Sergey Bravyi, Matthias Englbrecht, Robert König, and Nolan Peard. Correcting coherent errors with surface codes. npj Quantum Information, 4 (1): 55, 2018. URL https://doi.org/10.1038/s41534-018-0106-y.
https://doi.org/10.1038/s41534-018-0106-y

[47] Andrew S Darmawan and David Poulin. Tensor-network simulations of the surface code under realistic noise. Physical review letters, 119 (4): 040502, 2017. URL https://doi.org/10.1103/PhysRevLett.119.040502.
https://doi.org/10.1103/PhysRevLett.119.040502

[48] Zohar Schwartzman-Nowik, Liran Shirizly, and Haggai Landa. Modeling error correction with lindblad dynamics and approximate channels. Phys. Rev. A, 111: 022613, Feb 2025. URL https://doi.org/10.1103/PhysRevA.111.022613.
https://doi.org/10.1103/PhysRevA.111.022613

[49] Zohar Schwartzman-Nowik and Benjamin J Brown. Simulation of success rates of generalized matching decoders of the cubic chamon code., 2024. URL https://github.com/zoharno/chamon_decoder.
https://github.com/zoharno/chamon_decoder

[50] Eric Jones, Travis Oliphant, Pearu Peterson, et al. SciPy: Open source scientific tools for Python, 2001–. URL http://www.scipy.org/.
http://www.scipy.org/

[51] Omar Fawzi, Antoine Grospellier, and Anthony Leverrier. Efficient decoding of random errors for quantum expander codes. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 521–534, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355599. URL https://doi.org/10.1145/3188745.3188886.
https://doi.org/10.1145/3188745.3188886

[52] Joschka Roffe, David R. White, Simon Burton, and Earl Campbell. Decoding across the quantum low-density parity-check code landscape. Physical Review Research, 2 (4), Dec 2020. ISSN 2643-1564. URL https://doi.org/10.1103/PhysRevResearch.2.043423.
https://doi.org/10.1103/PhysRevResearch.2.043423

[53] Joschka Roffe. LDPC: Python tools for low density parity check codes, 2022. URL https://pypi.org/project/ldpc/.
https://pypi.org/project/ldpc/

[54] Emanuel Knill, Raymond Laflamme, and Wojciech H Zurek. Resilient quantum computation: error models and thresholds. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454 (1969): 365–384, 1998. URL https://doi.org/10.1098/rspa.1998.0166.
https://doi.org/10.1098/rspa.1998.0166

[55] Pavel Panteleev and Gleb Kalachev. Degenerate Quantum LDPC Codes With Good Finite Length Performance. Quantum, 5: 585, November 2021. ISSN 2521-327X. URL https://doi.org/10.22331/q-2021-11-22-585.
https://doi.org/10.22331/q-2021-11-22-585

[56] Sergey Bravyi, Andrew W Cross, Jay M Gambetta, Dmitri Maslov, Patrick Rall, and Theodore J Yoder. High-threshold and low-overhead fault-tolerant quantum memory. Nature, 627 (8005): 778–782, 2024. URL https://doi.org/10.1038/s41586-024-07107-7.
https://doi.org/10.1038/s41586-024-07107-7

[57] Antoine Grospellier, Lucien Grouès, Anirudh Krishna, and Anthony Leverrier. Combining hard and soft decoders for hypergraph product codes. Quantum, 5: 432, April 2021. ISSN 2521-327X. URL https://doi.org/10.22331/q-2021-04-15-432.
https://doi.org/10.22331/q-2021-04-15-432

Cited by

[1] Zhipeng Liang, Zhengzhong Yi, Fusheng Yang, Jiahan Chen, Zicheng Wang, and Xuan Wang, "High-dimensional quantum XYZ product codes for biased noise", Physical Review A 112 5, 052439 (2025).

[2] Zohar Schwartzman-Nowik and Benjamin J. Brown, "Generalizing the matching decoder for the Chamon code", Quantum 9, 1775 (2025).

[3] Dominic J. Williamson, "Partial Self-Correction in Layer Codes", arXiv:2510.09218, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 13:13:46) and SAO/NASA ADS (last updated successfully 2026-08-09 13:13:47). 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.