{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T02:42:26Z","timestamp":1778553746423,"version":"3.51.4"},"reference-count":41,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T00:00:00Z","timestamp":1618444800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Hypergraph product codes are a class of constant-rate quantum low-density parity-check (LDPC) codes equipped with a linear-time decoder called small-set-flip (SSF). This decoder displays sub-optimal performance in practice and requires very large error correcting codes to be effective. In this work, we present new hybrid decoders that combine the belief propagation (BP) algorithm with the SSF decoder. We present the results of numerical simulations when codes are subject to independent bit-flip and phase-flip errors. We provide evidence that the threshold of these codes is roughly 7.5% assuming an ideal syndrome extraction, and remains close to 3% in the presence of syndrome noise. This result subsumes and significantly improves upon an earlier work by Grospellier and Krishna (arXiv:1810.03681). The low-complexity high-performance of these heuristic decoders suggests that decoding should not be a substantial difficulty when moving from zero-rate surface codes to constant-rate LDPC codes and gives a further hint that such codes are well-worth investigating in the context of building large universal quantum computers.<\/jats:p>","DOI":"10.22331\/q-2021-04-15-432","type":"journal-article","created":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T17:32:52Z","timestamp":1618507972000},"page":"432","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":49,"title":["Combining hard and soft decoders for hypergraph product codes"],"prefix":"10.22331","volume":"5","author":[{"given":"Antoine","family":"Grospellier","sequence":"first","affiliation":[{"name":"Inria, 2 Rue Simone IFF, CS 42112, 75589 Paris Cedex 12, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lucien","family":"Grou\u00e8s","sequence":"additional","affiliation":[{"name":"Inria, 2 Rue Simone IFF, CS 42112, 75589 Paris Cedex 12, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anirudh","family":"Krishna","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Sherbrooke, 2500 Boulevard de l'Universit\u00e9, Sherbrooke, QC J1K 2R1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anthony","family":"Leverrier","sequence":"additional","affiliation":[{"name":"Inria, 2 Rue Simone IFF, CS 42112, 75589 Paris Cedex 12, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2021,4,15]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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\u2013188. ACM, 1997. 10.1137\/S0097539799359385. URL https:\/\/doi.org\/10.1137\/S0097539799359385.","DOI":"10.1137\/S0097539799359385"},{"key":"1","doi-asserted-by":"publisher","unstructured":"H\u00e9ctor Bombin, Ruben S Andrist, Masayuki Ohzeki, Helmut G Katzgraber, and Miguel A Martin-Delgado. Strong resilience of topological codes to depolarization. Physical Review X, 2 (2): 021004, 2012. 10.1103\/PhysRevX.2.021004. URL https:\/\/link.aps.org\/doi\/10.1103\/PhysRevX.2.021004.","DOI":"10.1103\/PhysRevX.2.021004"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, David Poulin, and Barbara Terhal. Tradeoffs for reliable quantum information storage in 2D systems. Physical Review Letters, 104 (5): 050503, 2010. 10.1103\/PhysRevLett.104.050503. URL https:\/\/link.aps.org\/doi\/10.1103\/PhysRevLett.104.050503.","DOI":"10.1103\/PhysRevLett.104.050503"},{"key":"3","unstructured":"Nikolas P Breuckmann and Vivien Londe. Single-Shot Decoding of Linear Rate LDPC Quantum Codes with High Performance. arXiv preprint arXiv:2001.03568, 2020."},{"key":"4","doi-asserted-by":"publisher","unstructured":"Nikolas P Breuckmann and Barbara M Terhal. Constructions and noise threshold of hyperbolic surface codes. IEEE transactions on Information Theory, 62 (6): 3731\u20133744, 2016. 10.1109\/TIT.2016.2555700.","DOI":"10.1109\/TIT.2016.2555700"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Nikolas P Breuckmann, Christophe Vuillot, Earl Campbell, Anirudh Krishna, and Barbara M Terhal. Hyperbolic and semi-hyperbolic surface codes for quantum storage. Quantum Science and Technology, 2 (3): 035007, 2017. 10.1088\/2058-9565\/aa7d3b.","DOI":"10.1088\/2058-9565\/aa7d3b"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Benjamin J Brown, Naomi H Nickerson, and Dan E Browne. Fault-tolerant error correction with the gauge color code. Nature communications, 7 (1): 1\u20138, 2016. 10.1038\/ncomms12302.","DOI":"10.1038\/ncomms12302"},{"key":"7","doi-asserted-by":"publisher","unstructured":"A Robert Calderbank and Peter W Shor. Good quantum error-correcting codes exist. Physical Review A, 54 (2): 1098, 1996. 10.1103\/PhysRevA.54.1098.","DOI":"10.1103\/PhysRevA.54.1098"},{"key":"8","unstructured":"Christopher T Chubb and Steven T Flammia. Statistical mechanical models for quantum codes with correlated noise. arXiv preprint arXiv:1809.10704, 2018."},{"key":"9","doi-asserted-by":"publisher","unstructured":"Jonathan Conrad, Christopher Chamberland, Nikolas P Breuckmann, and Barbara M Terhal. The small stellated dodecahedron code and friends. Phil. Trans. R. Soc. A, 376 (2123): 20170323, 2018. 10.1098\/rsta.2017.0323.","DOI":"10.1098\/rsta.2017.0323"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Nicolas Delfosse. Tradeoffs for reliable quantum information storage in surface codes and color codes. In Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, pages 917\u2013921. IEEE, 2013. 10.1109\/ISIT.2013.6620360.","DOI":"10.1109\/ISIT.2013.6620360"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43 (9): 4452\u20134505, 2002. 10.1063\/1.1499754.","DOI":"10.1063\/1.1499754"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Ilya Dumer, Alexey A Kovalev, and Leonid P Pryadko. Thresholds for correcting errors, erasures, and faulty syndrome measurements in degenerate quantum codes. Physical review letters, 115 (5): 050502, 2015. 10.1103\/PhysRevLett.115.050502.","DOI":"10.1103\/PhysRevLett.115.050502"},{"key":"13","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, 2018a. 10.1109\/FOCS.2018.00076.","DOI":"10.1109\/FOCS.2018.00076"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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, pages 521\u2013534. ACM, 2018b. 10.1145\/3188745.3188886.","DOI":"10.1145\/3188745.3188886"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Marc PC Fossorier and Shu Lin. Soft-decision decoding of linear block codes based on ordered statistics. IEEE Transactions on Information Theory, 41 (5): 1379\u20131396, 1995. 10.1109\/18.412683.","DOI":"10.1109\/18.412683"},{"key":"16","doi-asserted-by":"crossref","unstructured":"Michael H Freedman, David A Meyer, and Feng Luo. Z2-systolic freedom and quantum codes. Mathematics of quantum computation, Chapman & Hall\/CRC, pages 287\u2013320, 2002.","DOI":"10.1201\/9781420035377.ch12"},{"key":"17","unstructured":"Daniel Gottesman. Stabilizer codes and quantum error correction. arXiv preprint quant-ph\/9705052, 1997."},{"key":"18","doi-asserted-by":"publisher","unstructured":"Daniel Gottesman. Fault-tolerant quantum computation with constant overhead. Quantum Information & Computation, 14 (15-16): 1338\u20131372, 2014. 10.5555\/2685179.2685184.","DOI":"10.5555\/2685179.2685184"},{"key":"19","unstructured":"Antoine Grospellier and Anirudh Krishna. Numerical study of hypergraph product codes. arXiv preprint arXiv:1810.03681, 2018."},{"key":"20","doi-asserted-by":"publisher","unstructured":"Larry Guth and Alexander Lubotzky. Quantum error correcting codes and 4-dimensional arithmetic hyperbolic manifolds. Journal of Mathematical Physics, 55 (8): 082202, 2014. 10.1063\/1.4891487.","DOI":"10.1063\/1.4891487"},{"key":"21","doi-asserted-by":"publisher","unstructured":"A Yu Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52 (6): 1191\u20131249, 1997. 10.4213\/rm892.","DOI":"10.4213\/rm892"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Emanuel Knill, Raymond Laflamme, and Wojciech H Zurek. Resilient quantum computation: error models and thresholds. In Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, volume 454, pages 365\u2013384. The Royal Society, 1998. 10.1126\/science.279.5349.342.","DOI":"10.1126\/science.279.5349.342"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Alexey A Kovalev and Leonid P Pryadko. Improved quantum hypergraph-product LDPC codes. In Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, pages 348\u2013352. IEEE, 2012. 10.1109\/ISIT.2012.6284206.","DOI":"10.1109\/ISIT.2012.6284206"},{"key":"24","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 (2): 020304, 2013. 10.1103\/PhysRevA.87.020304.","DOI":"10.1103\/PhysRevA.87.020304"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Alexey A Kovalev, Sanjay Prabhakar, Ilya Dumer, and Leonid P Pryadko. Numerical and analytical bounds on threshold error rates for hypergraph-product codes. Physical Review A, 97 (6): 062320, 2018. 10.1103\/PhysRevA.97.062320.","DOI":"10.1103\/PhysRevA.97.062320"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Anirudh Krishna and David Poulin. Topological wormholes: Nonlocal defects on the toric code. Phys. Rev. Research, 2: 023116, May 2020. 10.1103\/PhysRevResearch.2.023116. URL https:\/\/link.aps.org\/doi\/10.1103\/PhysRevResearch.2.023116.","DOI":"10.1103\/PhysRevResearch.2.023116"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Anirudh Krishna and David Poulin. Fault-tolerant gates on hypergraph product codes. Phys. Rev. X, 11: 011023, Feb 2021. 10.1103\/PhysRevX.11.011023. URL https:\/\/link.aps.org\/doi\/10.1103\/PhysRevX.11.011023.","DOI":"10.1103\/PhysRevX.11.011023"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Anthony Leverrier, Jean-Pierre Tillich, and Gilles Z\u00e9mor. Quantum expander codes. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 810\u2013824. IEEE, 2015. 10.1109\/FOCS.2015.55.","DOI":"10.1109\/FOCS.2015.55"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Muyuan Li and Theodore J. Yoder. A numerical study of bravyi-bacon-shor and subsystem hypergraph product codes. pages 109\u2013119, 2020. 10.1109\/QCE49297.2020.00024.","DOI":"10.1109\/QCE49297.2020.00024"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Vivien Londe and Anthony Leverrier. Golden codes: quantum LDPC codes built from regular tessellations of hyperbolic 4-manifolds. Quantum Information & Computation, 19 (5-6): 361\u2013391, 2019. 10.26421\/QIC19.5-6.","DOI":"10.26421\/QIC19.5-6"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Brendan D McKay and Xiaoji Wang. Asymptotic enumeration of 0\u20131 matrices with equal row sums and equal column sums. Linear algebra and its applications, 373: 273\u2013287, 2003. 10.1016\/S0024-3795(03)00506-8.","DOI":"10.1016\/S0024-3795(03)00506-8"},{"key":"32","unstructured":"Pavel Panteleev and Gleb Kalachev. Degenerate quantum ldpc codes with good finite length performance. arXiv preprint arXiv:1904.02703, 2019."},{"key":"33","doi-asserted-by":"publisher","unstructured":"David Poulin and Yeojin Chung. On the iterative decoding of sparse quantum codes. Quantum Information & Computation, 8 (10): 987\u20131000, 2008. 10.5555\/2016985.2016993.","DOI":"10.5555\/2016985.2016993"},{"key":"34","doi-asserted-by":"crossref","unstructured":"Tom Richardson and Ruediger Urbanke. Modern coding theory. Cambridge university press, 2008.","DOI":"10.1017\/CBO9780511791338"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Michael Sipser and Daniel A Spielman. Expander codes. In Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on, pages 566\u2013576. IEEE, 1994. 10.1109\/18.556667.","DOI":"10.1109\/18.556667"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Andrew Steane. Multiple-particle interference and quantum error correction. Proceedings of the Royal Society A, 452 (1954): 2551\u20132577, 1996. 10.1098\/rspa.1996.0136.","DOI":"10.1098\/rspa.1996.0136"},{"key":"37","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 (2): 1193\u20131202, 2014. 10.1109\/TIT.2013.2292061.","DOI":"10.1109\/TIT.2013.2292061"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Chenyang Wang, Jim Harrington, and John Preskill. Confinement-higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory. Annals of Physics, 303 (1): 31\u201358, 2003. 10.1016\/S0003-4916(02)00019-2.","DOI":"10.1016\/S0003-4916(02)00019-2"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Weilei Zeng and Leonid P Pryadko. Higher-dimensional quantum hypergraph-product codes with finite rates. Physical Review Letters, 122 (23): 230501, 2019. 10.1103\/PhysRevLett.122.230501.","DOI":"10.1103\/PhysRevLett.122.230501"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Guanyu Zhu, Ali Lavasani, and Maissam Barkeshli. Instantaneous braids and dehn twists in topologically ordered states. Phys. Rev. B, 102: 075105, Aug 2020. 10.1103\/PhysRevB.102.075105.","DOI":"10.1103\/PhysRevB.102.075105"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-04-15-432\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T17:33:18Z","timestamp":1618507998000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-04-15-432\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,15]]},"references-count":41,"URL":"https:\/\/doi.org\/10.22331\/q-2021-04-15-432","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,15]]},"article-number":"432"}}