Fast erasure decoder for hypergraph product codes
1Inria, Paris, France
2Okinawa Institute of Science and Technology Graduate University, Okinawa, Japan
3Microsoft, Paris, France
4Microsoft Quantum, Redmond, Washington 98052, USA
| Published: | 2024-08-27, volume 8, page 1450 |
| Eprint: | arXiv:2208.01002v3 |
| Doi: | https://doi.org/10.22331/q-2024-08-27-1450 |
| Citation: | Quantum 8, 1450 (2024). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We propose a decoder for the correction of erasures with hypergraph product codes, which form one of the most popular families of quantum LDPC codes. Our numerical simulations show that this decoder provides a close approximation of the maximum likelihood decoder that can be implemented in $O(N^2)$ bit operations where $N$ is the length of the quantum code. A probabilistic version of this decoder can be implemented in $O(N^{1.5})$ bit operations.
► BibTeX data
► References
[1] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. ``Topological quantum memory''. Journal of Mathematical Physics 43, 4452–4505 (2002).
https://doi.org/10.1063/1.1499754
[2] Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N Cleland. ``Surface codes: Towards practical large-scale quantum computation''. Physical Review A 86, 032324 (2012).
https://doi.org/10.1103/PhysRevA.86.032324
[3] Robert Gallager. ``Low-density parity-check codes''. IRE Transactions on Information Theory 8, 21–28 (1962).
https://doi.org/10.1109/TIT.1962.1057683
[4] David JC MacKay, Graeme Mitchison, and Paul L McFadden. ``Sparse-graph codes for quantum error correction''. IEEE Transactions on Information Theory 50, 2315–2330 (2004).
https://doi.org/10.1109/TIT.2004.834737
[5] Jean-Pierre Tillich and Gilles Zémor. ``Quantum ldpc codes with positive rate and minimum distance proportional to the square root of the blocklength''. IEEE Transactions on Information Theory 60, 1193–1202 (2013).
https://doi.org/10.1109/TIT.2013.2292061
[6] Daniel Gottesman. ``Fault-tolerant quantum computation with constant overhead''. Quantum Information & Computation 14, 1338–1372 (2014).
https://doi.org/10.5555/2685179.2685184
[7] Omar Fawzi, Antoine Grospellier, and Anthony Leverrier. ``Constant overhead quantum fault-tolerance with quantum expander codes''. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). Pages 743–754. IEEE (2018).
https://doi.org/10.1145/3434163
[8] Maxime A Tremblay, Nicolas Delfosse, and Michael E Beverland. ``Constant-overhead quantum error correction with thin planar connectivity''. Physical Review Letters 129, 050504 (2022).
https://doi.org/10.1103/PhysRevLett.129.050504
[9] Emanuel Knill, Raymond Laflamme, and Gerald J Milburn. ``A scheme for efficient quantum computation with linear optics''. nature 409, 46–52 (2001).
https://doi.org/10.1038/35051009
[10] Sara Bartolucci, Patrick Birchall, Hector Bombin, Hugo Cable, Chris Dawson, Mercedes Gimeno-Segovia, Eric Johnston, Konrad Kieling, Naomi Nickerson, Mihir Pant, et al. ``Fusion-based quantum computation''. Nature Communications 14, 912 (2023).
https://doi.org/10.1038/s41467-023-36493-1
[11] Yue Wu, Shimon Kolkowitz, Shruti Puri, and Jeff D Thompson. ``Erasure conversion for fault-tolerant quantum computing in alkaline earth rydberg atom arrays''. Nature communications 13, 4657 (2022).
https://doi.org/10.7910/DVN/H9LV4H
[12] Mingyu Kang, Wesley C Campbell, and Kenneth R Brown. ``Quantum error correction with metastable states of trapped ions using erasure conversion''. PRX Quantum 4, 020358 (2023).
https://doi.org/10.1103/prxquantum.4.020358
[13] Aleksander Kubica, Arbel Haim, Yotam Vaknin, Harry Levine, Fernando Brandão, and Alex Retzker. ``Erasure qubits: Overcoming the $ t\_1 $ limit in superconducting circuits''. Physical Review X 13, 041022 (2023).
https://doi.org/10.1103/PhysRevX.13.041022
[14] Takahiro Tsunoda, James D Teoh, William D Kalfus, Stijn J de Graaf, Benjamin J Chapman, Jacob C Curtis, Neel Thakur, Steven M Girvin, and Robert J Schoelkopf. ``Error-detectable bosonic entangling gates with a noisy ancilla''. PRX Quantum 4, 020354 (2023).
https://doi.org/10.1103/PRXQuantum.4.020354
[15] Shrinivas Kudekar, Tom Richardson, and Rüdiger L Urbanke. ``Spatially coupled ensembles universally achieve capacity under belief propagation''. IEEE Transactions on Information Theory 59, 7761–7813 (2013).
https://doi.org/10.1109/TIT.2013.2280915
[16] Tom Richardson and Ruediger Urbanke. ``Modern coding theory''. Cambridge university press. (2008).
https://doi.org/10.1017/CBO9780511791338
[17] Michael G Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, and Daniel A Spielman. ``Efficient erasure correcting codes''. IEEE Transactions on Information Theory 47, 569–584 (2001).
https://doi.org/10.1109/18.910575
[18] Victor Vasilievich Zyablov and Mark Semenovich Pinsker. ``Decoding complexity of low-density codes for transmission in a channel with erasures''. Problemy Peredachi Informatsii 10, 15–28 (1974).
[19] Nicolas Delfosse and Gilles Zémor. ``Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel''. Physical Review Research 2, 033042 (2020).
https://doi.org/10.1103/PhysRevResearch.2.033042
[20] Sangjun Lee, Mehdi Mhalla, and Valentin Savin. ``Trimming decoding of color codes over the quantum erasure channel''. In 2020 IEEE International Symposium on Information Theory (ISIT). Pages 1886–1890. IEEE (2020).
https://doi.org/10.1109/ISIT44484.2020.9174084
[21] Andrew Steane. ``Multiple-particle interference and quantum error correction''. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 452, 2551–2577 (1996).
https://doi.org/10.1098/rspa.1996.0136
[22] A Robert Calderbank and Peter W Shor. ``Good quantum error-correcting codes exist''. Physical Review A 54, 1098 (1996).
https://doi.org/10.1103/PhysRevA.54.1098
[23] Markus Grassl, Th Beth, and Thomas Pellizzari. ``Codes for the quantum erasure channel''. Physical Review A 56, 33 (1997).
https://doi.org/10.1103/PhysRevA.56.33
[24] Thomas J Richardson and Rüdiger L Urbanke. ``Efficient encoding of low-density parity-check codes''. IEEE Transactions on Information Theory 47, 638–656 (2001).
https://doi.org/10.1109/18.910579
[25] Xiao-Yu Hu, E. Eleftheriou, and D.-M. Arnold. ``Progressive edge-growth tanner graphs''. In GLOBECOM'01. IEEE Global Telecommunications Conference (Cat. No.01CH37270). Volume 2, pages 995–1001 vol.2. (2001).
https://doi.org/10.1109/GLOCOM.2001.965567
[26] Xiao-Yu Hu, E. Eleftheriou, and D.M. Arnold. ``Regular and irregular progressive edge-growth tanner graphs''. IEEE Transactions on Information Theory 51, 386–398 (2005).
https://doi.org/10.1109/TIT.2004.839541
[27] T S Manu. ``Progressive edge growth algorithm for generating LDPC matrices'' (2014).
[28] Nicholas Connolly. ``Pruned peeling and vh decoder'' (2022).
[29] Douglas Wiedemann. ``Solving sparse linear equations over finite fields''. IEEE Transactions on Information Theory 32, 54–62 (1986).
https://doi.org/10.1109/TIT.1986.1057137
[30] Erich Kaltofen and B David Saunders. ``On Wiedemann's method of solving sparse linear systems''. In International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes. Pages 29–38. Springer (1991).
https://doi.org/10.5555/646027.676885
[31] Brian A LaMacchia and Andrew M Odlyzko. ``Solving large sparse linear systems over finite fields''. In Conference on the Theory and Application of Cryptography. Pages 109–133. Springer (1990).
https://doi.org/10.1007/3-540-38424-3_8
[32] Erich Kaltofen. ``Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems''. Mathematics of Computation 64, 777–806 (1995).
https://doi.org/10.2307/2153451
[33] Alexey A Kovalev and Leonid P Pryadko. ``Fault tolerance of quantum low-density parity check codes with sublinear distance scaling''. Physical Review A 87, 020304 (2013).
https://doi.org/10.1103/PhysRevA.87.020304
[34] Pavel Panteleev and Gleb Kalachev. ``Degenerate quantum ldpc codes with good finite length performance''. Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
[35] Shilin Huang, Michael Newman, and Kenneth R Brown. ``Fault-tolerant weighted union-find decoding on the toric code''. Physical Review A 102, 012419 (2020).
https://doi.org/10.1103/PhysRevA.102.012419
[36] 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
[37] Nicolas Delfosse, Vivien Londe, and Michael E Beverland. ``Toward a union-find decoder for quantum ldpc codes''. IEEE Transactions on Information Theory (2022).
https://doi.org/10.1109/TIT.2022.3143452
[38] Anirudh Krishna, Inbal Livni Navon, and Mary Wootters. ``Viderman's algorithm for quantum ldpc codes''. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 2481–2507. SIAM (2024).
https://doi.org/10.1137/1.9781611977912.88
[39] Nikolas P Breuckmann and Jens N Eberhardt. ``Balanced product quantum codes''. IEEE Transactions on Information Theory 67, 6653–6674 (2021).
https://doi.org/10.1109/TIT.2021.3097347
[40] Pavel Panteleev and Gleb Kalachev. ``Asymptotically good quantum and locally testable classical ldpc codes''. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Pages 375–388. (2022).
https://doi.org/10.1145/3519935.3520017
[41] Anthony Leverrier and Gilles Zémor. ``Quantum tanner codes''. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). Pages 872–883. IEEE (2022).
https://doi.org/10.1109/FOCS54457.2022.00117
[42] Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, and Thomas Vidick. ``Good quantum ldpc codes with linear time decoders''. In Proceedings of the 55th annual ACM symposium on theory of computing. Pages 905–918. (2023).
https://doi.org/10.1145/3564246.3585101
Cited by
[1] Gayathri R., Shobhit Bhatnagar, Abhinav Vaishya, and P Vijay Kumar, 2025 IEEE Information Theory Workshop (ITW) 1 (2025) ISBN:979-8-3315-3142-3.
[2] Kao-Yueh Kuo and Yingkai Ouyang, "Degenerate quantum erasure decoding", npj Quantum Information 12 1, 75 (2026).
[3] Samuel C. Smith, Benjamin J. Brown, and Stephen D. Bartlett, "Mitigating errors in logical qubits", Communications Physics 7 1, 386 (2024).
[4] Minghao Fu, Cewen Tian, Zaixu Fan, and Hongyang Ma, "Resource-Efficient Decoding of Topological Color Codes via Neural-Guided Union-Find Optimization", Applied Sciences 15 16, 8937 (2025).
[5] Abd El Latif Kadry, Yihan Zhang, and Nir Weinberger, 2025 IEEE International Symposium on Information Theory (ISIT) 1 (2025) ISBN:979-8-3315-4399-0.
[6] Bruno Costa Alves Freire, Nicolas Delfosse, and Anthony Leverrier, 2025 IEEE International Symposium on Information Theory (ISIT) 1 (2025) ISBN:979-8-3315-4399-0.
[7] Jefrin Sharmitha Prabhu, Abhinav Vaishya, Shobhit Bhatnagar, Aryaman Manish Kolhe, V. Lalitha, and P. Vijay Kumar, 2025 IEEE International Symposium on Information Theory (ISIT) 1 (2025) ISBN:979-8-3315-4399-0.
[8] Mert Gökduman, Hanwen Yao, and Henry D. Pfister, 2024 60th Annual Allerton Conference on Communication, Control, and Computing 1 (2024) ISBN:979-8-3315-4103-3.
[9] Hanwen Yao, Mert Gökduman, and Henry D. Pfister, "Cluster Decomposition for Improved Erasure Decoding of Quantum LDPC Codes", IEEE Journal on Selected Areas in Information Theory 6, 176 (2025).
[10] Gayathri R., Shobhit Bhatnagar, and P Vijay Kumar, 2026 National Conference on Communications (NCC) 268 (2026) ISBN:979-8-3315-4715-8.
[11] Shin Nishio, Nicholas Connolly, Nicolò Lo Piparo, William John Munro, Thomas Rowan Scruby, and Kae Nemoto, "Multiplexed Quantum Communication with Surface and Hypergraph Product Codes", Quantum 9, 1613 (2025).
[12] Stefano Paesani and Benjamin J. Brown, "High-Threshold Quantum Computing by Fusing One-Dimensional Cluster States", Physical Review Letters 131 12, 120603 (2023).
[13] Grégoire de Gliniasty, Paul Hilaire, Pierre-Emmanuel Emeriau, Stephen C. Wein, Alexia Salavrakos, and Shane Mansfield, "A Spin-Optical Quantum Computing Architecture", Quantum 8, 1423 (2024).
[14] Daoheng Niu, Yuxuan Zhang, Alireza Shabani, and Hassan Shapourian, "All-photonic one-way quantum repeaters with measurement-based error correction", npj Quantum Information 9 1, 106 (2023).
[15] Thomas Strohm, Karen Wintersperger, Florian Dommert, Daniel Basilewitsch, Georg Reuber, Andrey Hoursanov, Thomas Ehmer, Davide Vodola, and Sebastian Luber, "Ion-Based Quantum Computing Hardware: Performance and End-User Perspective", arXiv:2405.11450, (2024).
[16] Bruno C. A. Freire, Nicolas Delfosse, and Anthony Leverrier, "Optimizing hypergraph product codes with random walks, simulated annealing and reinforcement learning", arXiv:2501.09622, (2025).
[17] Victor V. Albert and Philippe Faist, "Handbook of Error-Correcting Codes", arXiv:2606.11484, (2026).
[18] Lev Stambler, Anirudh Krishna, and Michael E. Beverland, "Addressing Stopping Failures for Small Set Flip Decoding of Hypergraph Product Codes", arXiv:2311.00877, (2023).
[19] Kun Liu, Takahiro Tsunoda, Sophia H. Xue, Evan McKinney, Zeyuan Zhou, Shifan Xu, Robert J. Schoelkopf, and Yongshan Ding, "Efficient Routing of Quantum LDPC Codes on Programmable 2D Toric Architectures", arXiv:2604.18714, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 03:29:50) and SAO/NASA ADS (last updated successfully 2026-08-09 13:10:03). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch ADS cited-by data during last attempt 2026-08-10 03:29:50: Cannot retrieve data from ADS due to rate limitations.
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.