{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T21:39:31Z","timestamp":1773437971105,"version":"3.50.1"},"reference-count":42,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T00:00:00Z","timestamp":1724716800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Plan France 2030","award":["ANR-22- PETQ-0006"],"award-info":[{"award-number":["ANR-22- PETQ-0006"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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<\/mml:mi>(<\/mml:mo>N<\/mml:mi>2<\/mml:mn><\/mml:msup>)<\/mml:mo><\/mml:math> bit operations where N<\/mml:mi><\/mml:math> is the length of the quantum code. A probabilistic version of this decoder can be implemented in O<\/mml:mi>(<\/mml:mo>N<\/mml:mi>1.5<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math> bit operations.<\/jats:p>","DOI":"10.22331\/q-2024-08-27-1450","type":"journal-article","created":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T16:27:16Z","timestamp":1724776036000},"page":"1450","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":10,"title":["Fast erasure decoder for hypergraph product codes"],"prefix":"10.22331","volume":"8","author":[{"given":"Nicholas","family":"Connolly","sequence":"first","affiliation":[{"name":"Inria, Paris, France"},{"name":"Okinawa Institute of Science and Technology Graduate University, Okinawa, Japan"}]},{"given":"Vivien","family":"Londe","sequence":"additional","affiliation":[{"name":"Microsoft, Paris, France"}]},{"given":"Anthony","family":"Leverrier","sequence":"additional","affiliation":[{"name":"Inria, Paris, France"}]},{"given":"Nicolas","family":"Delfosse","sequence":"additional","affiliation":[{"name":"Microsoft Quantum, Redmond, Washington 98052, USA"}]}],"member":"9598","published-online":{"date-parts":[[2024,8,27]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. ``Topological quantum memory''. Journal of Mathematical Physics 43, 4452\u20134505 (2002).","DOI":"10.1063\/1.1499754"},{"key":"1","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.86.032324"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Robert Gallager. ``Low-density parity-check codes''. IRE Transactions on Information Theory 8, 21\u201328 (1962).","DOI":"10.1109\/TIT.1962.1057683"},{"key":"3","doi-asserted-by":"publisher","unstructured":"David JC MacKay, Graeme Mitchison, and Paul L McFadden. ``Sparse-graph codes for quantum error correction''. IEEE Transactions on Information Theory 50, 2315\u20132330 (2004).","DOI":"10.1109\/TIT.2004.834737"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Jean-Pierre Tillich and Gilles Z\u00e9mor. ``Quantum ldpc codes with positive rate and minimum distance proportional to the square root of the blocklength''. IEEE Transactions on Information Theory 60, 1193\u20131202 (2013).","DOI":"10.1109\/TIT.2013.2292061"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Daniel Gottesman. ``Fault-tolerant quantum computation with constant overhead''. Quantum Information & Computation 14, 1338\u20131372 (2014).","DOI":"10.5555\/2685179.2685184"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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\u2013754. IEEE (2018).","DOI":"10.1145\/3434163"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Maxime A Tremblay, Nicolas Delfosse, and Michael E Beverland. ``Constant-overhead quantum error correction with thin planar connectivity''. Physical Review Letters 129, 050504 (2022).","DOI":"10.1103\/PhysRevLett.129.050504"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Emanuel Knill, Raymond Laflamme, and Gerald J Milburn. ``A scheme for efficient quantum computation with linear optics''. nature 409, 46\u201352 (2001).","DOI":"10.1038\/35051009"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/s41467-023-36493-1"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.7910\/DVN\/H9LV4H"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/prxquantum.4.020358"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Aleksander Kubica, Arbel Haim, Yotam Vaknin, Harry Levine, Fernando Brand\u00e3o, and Alex Retzker. ``Erasure qubits: Overcoming the $ t\\_1 $ limit in superconducting circuits''. Physical Review X 13, 041022 (2023).","DOI":"10.1103\/PhysRevX.13.041022"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PRXQuantum.4.020354"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Shrinivas Kudekar, Tom Richardson, and R\u00fcdiger L Urbanke. ``Spatially coupled ensembles universally achieve capacity under belief propagation''. IEEE Transactions on Information Theory 59, 7761\u20137813 (2013).","DOI":"10.1109\/TIT.2013.2280915"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Tom Richardson and Ruediger Urbanke. ``Modern coding theory''. Cambridge university press. (2008).","DOI":"10.1017\/CBO9780511791338"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Michael G Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, and Daniel A Spielman. ``Efficient erasure correcting codes''. IEEE Transactions on Information Theory 47, 569\u2013584 (2001).","DOI":"10.1109\/18.910575"},{"key":"17","unstructured":"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\u201328 (1974)."},{"key":"18","doi-asserted-by":"publisher","unstructured":"Nicolas Delfosse and Gilles Z\u00e9mor. ``Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel''. Physical Review Research 2, 033042 (2020).","DOI":"10.1103\/PhysRevResearch.2.033042"},{"key":"19","doi-asserted-by":"publisher","unstructured":"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\u20131890. IEEE (2020).","DOI":"10.1109\/ISIT44484.2020.9174084"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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\u20132577 (1996).","DOI":"10.1098\/rspa.1996.0136"},{"key":"21","doi-asserted-by":"publisher","unstructured":"A Robert Calderbank and Peter W Shor. ``Good quantum error-correcting codes exist''. Physical Review A 54, 1098 (1996).","DOI":"10.1103\/PhysRevA.54.1098"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Markus Grassl, Th Beth, and Thomas Pellizzari. ``Codes for the quantum erasure channel''. Physical Review A 56, 33 (1997).","DOI":"10.1103\/PhysRevA.56.33"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Thomas J Richardson and R\u00fcdiger L Urbanke. ``Efficient encoding of low-density parity-check codes''. IEEE Transactions on Information Theory 47, 638\u2013656 (2001).","DOI":"10.1109\/18.910579"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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\u20131001 vol.2. (2001).","DOI":"10.1109\/GLOCOM.2001.965567"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Xiao-Yu Hu, E. Eleftheriou, and D.M. Arnold. ``Regular and irregular progressive edge-growth tanner graphs''. IEEE Transactions on Information Theory 51, 386\u2013398 (2005).","DOI":"10.1109\/TIT.2004.839541"},{"key":"26","unstructured":"T S Manu. ``Progressive edge growth algorithm for generating LDPC matrices'' (2014)."},{"key":"27","unstructured":"Nicholas Connolly. ``Pruned peeling and vh decoder'' (2022)."},{"key":"28","doi-asserted-by":"publisher","unstructured":"Douglas Wiedemann. ``Solving sparse linear equations over finite fields''. IEEE Transactions on Information Theory 32, 54\u201362 (1986).","DOI":"10.1109\/TIT.1986.1057137"},{"key":"29","doi-asserted-by":"publisher","unstructured":"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\u201338. Springer (1991).","DOI":"10.5555\/646027.676885"},{"key":"30","doi-asserted-by":"publisher","unstructured":"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\u2013133. Springer (1990).","DOI":"10.1007\/3-540-38424-3_8"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Erich Kaltofen. ``Analysis of Coppersmith\u2019s block Wiedemann algorithm for the parallel solution of sparse linear systems''. Mathematics of Computation 64, 777\u2013806 (1995).","DOI":"10.2307\/2153451"},{"key":"32","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.87.020304"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Pavel Panteleev and Gleb Kalachev. ``Degenerate quantum ldpc codes with good finite length performance''. Quantum 5, 585 (2021).","DOI":"10.22331\/q-2021-11-22-585"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Shilin Huang, Michael Newman, and Kenneth R Brown. ``Fault-tolerant weighted union-find decoding on the toric code''. Physical Review A 102, 012419 (2020).","DOI":"10.1103\/PhysRevA.102.012419"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Nicolas Delfosse and Naomi H Nickerson. ``Almost-linear time decoding algorithm for topological codes''. Quantum 5, 595 (2021).","DOI":"10.22331\/q-2021-12-02-595"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Nicolas Delfosse, Vivien Londe, and Michael E Beverland. ``Toward a union-find decoder for quantum ldpc codes''. IEEE Transactions on Information Theory (2022).","DOI":"10.1109\/TIT.2022.3143452"},{"key":"37","doi-asserted-by":"publisher","unstructured":"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\u20132507. SIAM (2024).","DOI":"10.1137\/1.9781611977912.88"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Nikolas P Breuckmann and Jens N Eberhardt. ``Balanced product quantum codes''. IEEE Transactions on Information Theory 67, 6653\u20136674 (2021).","DOI":"10.1109\/TIT.2021.3097347"},{"key":"39","doi-asserted-by":"publisher","unstructured":"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\u2013388. (2022).","DOI":"10.1145\/3519935.3520017"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Anthony Leverrier and Gilles Z\u00e9mor. ``Quantum tanner codes''. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). Pages 872\u2013883. IEEE (2022).","DOI":"10.1109\/FOCS54457.2022.00117"},{"key":"41","doi-asserted-by":"publisher","unstructured":"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\u2013918. (2023).","DOI":"10.1145\/3564246.3585101"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-08-27-1450\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T16:27:26Z","timestamp":1724776046000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-08-27-1450\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,27]]},"references-count":42,"URL":"https:\/\/doi.org\/10.22331\/q-2024-08-27-1450","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,27]]},"article-number":"1450"}}