Pipelined correlated minimum weight perfect matching of the surface code

Alexandru Paler; Austin G. Fowler

doi:10.22331/q-2023-12-12-1205

Pipelined correlated minimum weight perfect matching of the surface code

Alexandru Paler^1,2 and Austin G. Fowler³

¹Aalto University, Espoo 02150, Finland
²University of Texas at Dallas, Richardson, TX 75080, USA
³Google Inc., Santa Barbara, 93117 CA, USA

Published:	2023-12-12, volume 7, page 1205
Eprint:	arXiv:2205.09828v2
Doi:	https://doi.org/10.22331/q-2023-12-12-1205
Citation:	Quantum 7, 1205 (2023).

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

Abstract

We describe a pipeline approach to decoding the surface code using minimum weight perfect matching, including taking into account correlations between detection events. An independent no-communication parallelizable processing stage reweights the graph according to likely correlations, followed by another no-communication parallelizable stage for high confidence matching. A later general stage finishes the matching. This is a simplification of previous correlated matching techniques which required a complex interaction between general matching and re-weighting the graph. Despite this simplification, which gives correlated matching a better chance of achieving real-time processing, we find the logical error rate practically unchanged. We validate the new algorithm on the fully fault-tolerant toric, unrotated, and rotated surface codes, all with standard depolarizing noise. We expect these techniques to be applicable to a wide range of other decoders.

► BibTeX data

@article{Paler2023pipelinedcorrelated,
  doi = {10.22331/q-2023-12-12-1205},
  url = {https://doi.org/10.22331/q-2023-12-12-1205},
  title = {Pipelined correlated minimum weight perfect matching of the surface code},
  author = {Paler, Alexandru and Fowler, Austin G.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {1205},
  month = dec,
  year = {2023}
}

► References

[1] S. B. Bravyi and A. Yu. Kitaev. ``Quantum codes on a lattice with boundary'' (1998). arXiv:quant-ph/9811052.
arXiv:quant-ph/9811052

[2] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill. ``Topological quantum memory''. J. Math. Phys. 43, 4452–4505 (2002). url: https://doi.org/10.1063/1.1499754.
https://doi.org/10.1063/1.1499754

[3] Robert Raussendorf and Jim Harrington. ``Fault-tolerant quantum computation with high threshold in two dimensions''. Phys. Rev. Lett. 98, 190504 (2007).
https://doi.org/10.1103/PhysRevLett.98.190504

[4] R. Raussendorf, J. Harrington, and K. Goyal. ``Topological fault-tolerance in cluster state quantum computation''. New J. Phys. 9, 199 (2007). url: https://doi.org/10.1088/1367-2630/9/6/199.
https://doi.org/10.1088/1367-2630/9/6/199

[5] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. 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

[6] Austin G. Fowler and Craig Gidney. ``Low overhead quantum computation using lattice surgery'' (2019). arXiv:1808.06709.
arXiv:1808.06709

[7] D. Litinski. ``A game of surface codes: Large-scale quantum computing with lattice surgery''. Quantum 3, 128 (2019).
https://doi.org/10.22331/q-2019-03-05-128

[8] Craig Gidney and Austin G. Fowler. ``Flexible layout of surface code computations using autoccz states'' (2019). arXiv:1905.08916.
arXiv:1905.08916

[9] I. D. Kivlichan, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, Wei Sun, Zhang Jiang, N. Rubin, A. G. Fowler, A. Aspuru-Guzik, H. Neven, and R. Babbush. ``Improved fault-tolerant quantum simulation of condensed-phase correlated electrons via trotterization''. Quantum 4, 296 (2020).
https://doi.org/10.22331/q-2020-07-16-296

[10] Ruben S. Andrist, H. Bombin, Helmut G. Katzgraber, and M. A. Martin-Delgado. ``Optimal error correction in topological subsystem codes''. Phys. Rev. A 85, 050302 (2012).
https://doi.org/10.1103/PhysRevA.85.050302

[11] Guillaume Duclos-Cianci and David Poulin. ``Fault-tolerant renormalization group decoder for abelian topological codes'' (2013). arXiv:1304.6100.
arXiv:1304.6100

[12] Adrian Hutter, James R. Wootton, and Daniel Loss. ``Efficient markov chain monte carlo algorithm for the surface code''. Phys. Rev. A 89, 022326 (2014).
https://doi.org/10.1103/PhysRevA.89.022326

[13] James Wootton. ``A simple decoder for topological codes''. Entropy 17, 1946–1957 (2015).
https://doi.org/10.3390/e17041946

[14] Austin G. Fowler. ``Optimal complexity correction of correlated errors in the surface code'' (2013). arXiv:1310.0863.
arXiv:1310.0863

[15] P. Baireuther, M. D. Caio, B. Criger, C. W. J. Beenakker, and T. E. O'Brien. ``Neural network decoder for topological color codes with circuit level noise''. New J. Phys 21, 013003 (2019).
https://doi.org/10.1088/1367-2630/aaf29e

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

[17] Antonio deMarti iOlius, Patricio Fuentes, Román Orús, Pedro M. Crespo, and Josu Etxezarreta Martinez. ``Decoding algorithms for surface codes'' (2023). arXiv:2307.14989.
arXiv:2307.14989

[18] Jack Edmonds. ``Paths, trees, and flowers''. Canadian Journal of Mathematics 17, 449–467 (1965).
https://doi.org/10.4153/CJM-1965-045-4

[19] J. Edmonds. ``Maximum matching and a polyhedron with 0,1-vertices''. J. Res. Nat. Bur. Standards 69B, 125–130 (1965).

[20] Oscar Higgott. ``Pymatching: A python package for decoding quantum codes with minimum-weight perfect matching''. ACM Transactions on Quantum Computing 3 (2022).
https://doi.org/10.1145/3505637

Cited by

[1] Tzu-Hao Lin and Ching-Yi Lai, "Union-Intersection Union-Find for Decoding Depolarizing Errors in Topological Codes", IEEE Journal on Selected Areas in Information Theory 6, 163 (2025).

[2] Bence Hetényi and James R. Wootton, "Creating Entangled Logical Qubits in the Heavy-Hex Lattice with Topological Codes", PRX Quantum 5 4, 040334 (2024).

[3] Yuxin Ji, Qinghui Chen, Rui Wang, Naihua Ji, and Hongyang Ma, "Quantum error correction for heavy hexagonal code using deep reinforcement learning with policy reuse", Quantum Information Processing 23 7, 255 (2024).

[4] Rajeev Acharya, Dmitry A. Abanin, Laleh Aghababaie-Beni, Igor Aleiner, Trond I. Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Nikita Astrakhantsev, Juan Atalaya, Ryan Babbush, Dave Bacon, Brian Ballard, Joseph C. Bardin, Johannes Bausch, Andreas Bengtsson, Alexander Bilmes, Sam Blackwell, Sergio Boixo, Gina Bortoli, Alexandre Bourassa, Jenna Bovaird, Leon Brill, Michael Broughton, David A. Browne, Brett Buchea, Bob B. Buckley, David A. Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Anthony Cabrera, Juan Campero, Hung-Shen Chang, Yu Chen, Zijun Chen, Ben Chiaro, Desmond Chik, Charina Chou, Jahan Claes, Agnetta Y. Cleland, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, Alexander L. Crook, Ben Curtin, Sayan Das, Alex Davies, Laura De Lorenzo, Dripto M. Debroy, Sean Demura, Michel Devoret, Agustin Di Paolo, Paul Donohoe, Ilya Drozdov, Andrew Dunsworth, Clint Earle, Thomas Edlich, Alec Eickbusch, Aviv Moshe Elbag, Mahmoud Elzouka, Catherine Erickson, Lara Faoro, Edward Farhi, Vinicius S. Ferreira, Leslie Flores Burgos, Ebrahim Forati, Austin G. Fowler, Brooks Foxen, Suhas Ganjam, Gonzalo Garcia, Robert Gasca, Élie Genois, William Giang, Craig Gidney, Dar Gilboa, Raja Gosula, Alejandro Grajales Dau, Dietrich Graumann, Alex Greene, Jonathan A. Gross, Steve Habegger, John Hall, Michael C. Hamilton, Monica Hansen, Matthew P. Harrigan, Sean D. Harrington, Francisco J. H. Heras, Stephen Heslin, Paula Heu, Oscar Higgott, Gordon Hill, Jeremy Hilton, George Holland, Sabrina Hong, Hsin-Yuan Huang, Ashley Huff, William J. Huggins, Lev B. Ioffe, Sergei V. Isakov, Justin Iveland, Evan Jeffrey, Zhang Jiang, Cody Jones, Stephen Jordan, Chaitali Joshi, Pavol Juhas, Dvir Kafri, Hui Kang, Amir H. Karamlou, Kostyantyn Kechedzhi, Julian Kelly, Trupti Khaire, Tanuj Khattar, Mostafa Khezri, Seon Kim, Paul V. Klimov, Andrey R. Klots, Bryce Kobrin, Pushmeet Kohli, Alexander N. Korotkov, Fedor Kostritsa, Robin Kothari, Borislav Kozlovskii, John Mark Kreikebaum, Vladislav D. Kurilovich, Nathan Lacroix, David Landhuis, Tiano Lange-Dei, Brandon W. Langley, Pavel Laptev, Kim-Ming Lau, Loïck Le Guevel, Justin Ledford, Joonho Lee, Kenny Lee, Yuri D. Lensky, Shannon Leon, Brian J. Lester, Wing Yan Li, Yin Li, Alexander T. Lill, Wayne Liu, William P. Livingston, Aditya Locharla, Erik Lucero, Daniel Lundahl, Aaron Lunt, Sid Madhuk, Fionn D. Malone, Ashley Maloney, Salvatore Mandrà, James Manyika, Leigh S. Martin, Orion Martin, Steven Martin, Cameron Maxfield, Jarrod R. McClean, Matt McEwen, Seneca Meeks, Anthony Megrant, Xiao Mi, Kevin C. Miao, Amanda Mieszala, Reza Molavi, Sebastian Molina, Shirin Montazeri, Alexis Morvan, Ramis Movassagh, Wojciech Mruczkiewicz, Ofer Naaman, Matthew Neeley, Charles Neill, Ani Nersisyan, Hartmut Neven, Michael Newman, Jiun How Ng, Anthony Nguyen, Murray Nguyen, Chia-Hung Ni, Murphy Yuezhen Niu, Thomas E. O’Brien, William D. Oliver, Alex Opremcak, Kristoffer Ottosson, Andre Petukhov, Alex Pizzuto, John Platt, Rebecca Potter, Orion Pritchard, Leonid P. Pryadko, Chris Quintana, Ganesh Ramachandran, Matthew J. Reagor, John Redding, David M. Rhodes, Gabrielle Roberts, Eliott Rosenberg, Emma Rosenfeld, Pedram Roushan, Nicholas C. Rubin, Negar Saei, Daniel Sank, Kannan Sankaragomathi, Kevin J. Satzinger, Henry F. Schurkus, Christopher Schuster, Andrew W. Senior, Michael J. Shearn, Aaron Shorter, Noah Shutty, Vladimir Shvarts, Shraddha Singh, Volodymyr Sivak, Jindra Skruzny, Spencer Small, Vadim Smelyanskiy, W. Clarke Smith, Rolando D. Somma, Sofia Springer, George Sterling, Doug Strain, Jordan Suchard, Aaron Szasz, Alex Sztein, Douglas Thor, Alfredo Torres, M. Mert Torunbalci, Abeer Vaishnav, Justin Vargas, Sergey Vdovichev, Guifre Vidal, Benjamin Villalonga, Catherine Vollgraff Heidweiller, Steven Waltman, Shannon X. Wang, Brayden Ware, Kate Weber, Travis Weidel, Theodore White, Kristi Wong, Bryan W. K. Woo, Cheng Xing, Z. Jamie Yao, Ping Yeh, Bicheng Ying, Juhwan Yoo, Noureldin Yosri, Grayson Young, Adam Zalcman, Yaxing Zhang, Ningfeng Zhu, and Nicholas Zobrist, "Quantum error correction below the surface code threshold", Nature 638 8052, 920 (2025).

[5] Yiqing Zhou, Chao Wan, Yichen Xu, Jin Peng Zhou, Kilian Q. Weinberger, and Eun-Ah Kim, "Learning to decode logical circuits", Nature Computational Science 5 12, 1158 (2025).

[6] Luka Skoric, Dan E. Browne, Kenton M. Barnes, Neil I. Gillespie, and Earl T. Campbell, "Parallel window decoding enables scalable fault tolerant quantum computation", Nature Communications 14 1, 7040 (2023).

[7] Jiajun Chen, Jierui Peng, and Jingyi Liu, "Two-Stage Neural Residual Decoding for FastSurface-Code Quantum Error Correction", (2026).

[8] Ants Remm, Nathan Lacroix, Lukas Bödeker, Elie Genois, Christoph Hellings, François Swiadek, Graham J. Norris, Christopher Eichler, Alexandre Blais, Markus Müller, Sebastian Krinner, and Andreas Wallraff, "Experimentally informed decoding of stabilizer codes based on syndrome correlations", Physical Review Research 8 1, 013044 (2026).

[9] Samuel C. Smith, Benjamin J. Brown, and Stephen D. Bartlett, "Mitigating errors in logical qubits", Communications Physics 7 1, 386 (2024).

[10] Younghun Kim, Martin Sevior, and Muhammad Usman, "Transversal cnot gate with multicycle error correction", Physical Review Applied 23 2, 024074 (2025).

[11] S.N. Saadatmand, Tyler L. Wilson, Mark J. Hodson, Mark Field, Simon J. Devitt, Madhav Krishnan Vijayan, Alan Robertson, Thinh P. Le, Jannis Ruh, Alexandru Paler, Arshpreet Singh Maan, Ioana Moflic, Athena Caesura, and Josh Y. Mutus, "Superconducting qubits in the millions: The potential and limitations of modularity", Physical Review Applied 25 6, 064038 (2026).

[12] Johannes Bausch, Andrew W. Senior, Francisco J. H. Heras, Thomas Edlich, Alex Davies, Michael Newman, Cody Jones, Kevin Satzinger, Murphy Yuezhen Niu, Sam Blackwell, George Holland, Dvir Kafri, Juan Atalaya, Craig Gidney, Demis Hassabis, Sergio Boixo, Hartmut Neven, and Pushmeet Kohli, "Learning high-accuracy error decoding for quantum processors", Nature 635 8040, 834 (2024).

[13] Kaavya Sahay, Yingjia Lin, Shilin Huang, Kenneth R. Brown, and Shruti Puri, "Error Correction of Transversal cnot Gates for Scalable Surface-Code Computation", PRX Quantum 6 2, 020326 (2025).

[14] Anthony Ryan O'Rourke and Simon Devitt, "Compare the pair: Rotated versus unrotated surface codes at equal logical error rates", Physical Review Research 7 3, 033074 (2025).

[15] Muhammad AbuGhanem, "Superconducting quantum computers: who is leading the future?", EPJ Quantum Technology 12 1, 102 (2025).

[16] Friederike Butt, Lars Esser, and Markus Müller, "Decoding three-dimensional color codes with boundaries", Physical Review A 113 4, 042416 (2026).

[17] Robert Joo, "Decoding the surface code with a spatio-temporal transformer", EPJ Quantum Technology 13 1, 52 (2026).

[18] Craig Gidney, Noah Shutty, and Cody Jones, "Magic state cultivation: growing T states as cheap as CNOT gates", arXiv:2409.17595, (2024).

[19] Tristan Müller, Thomas Alexander, Michael E. Beverland, Markus Bühler, Blake R. Johnson, Thilo Maurer, and Drew Vandeth, "Improved belief propagation is sufficient for real-time decoding of quantum memory", arXiv:2506.01779, (2025).

[20] F. Battistel, C. Chamberland, K. Johar, R. W. J. Overwater, F. Sebastiano, L. Skoric, Y. Ueno, and M. Usman, "Real-time decoding for fault-tolerant quantum computing: progress, challenges and outlook", Nano Futures 7 3, 032003 (2023).

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

[22] Antonio deMarti iOlius, Josu Etxezarreta Martinez, Patricio Fuentes, and Pedro M. Crespo, "Performance enhancement of surface codes via recursive minimum-weight perfect-match decoding", Physical Review A 108 2, 022401 (2023).

[23] György P. Gehér, Ophelia Crawford, and Earl T. Campbell, "Tangling Schedules Eases Hardware Connectivity Requirements for Quantum Error Correction", PRX Quantum 5 1, 010348 (2024).

[24] György P. Gehér, Campbell McLauchlan, Earl T. Campbell, Alexandra E. Moylett, and Ophelia Crawford, "Error-corrected Hadamard gate simulated at the circuit level", Quantum 8, 1394 (2024).

[25] Victor V. Albert and Philippe Faist, "Handbook of Error-Correcting Codes", arXiv:2606.11484, (2026).

[26] Yiqing Zhou, Chao Wan, Yichen Xu, Jin Peng Zhou, Kilian Q. Weinberger, and Eun-Ah Kim, "Learning to decode logical circuits", arXiv:2504.16999, (2025).

[27] Arianna Meinking, Julie Campos, and Kenneth R. Brown, "Leveraging Correlated Decoding for Bias-Tailored Compass Codes", arXiv:2605.27598, (2026).

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