Combining hard and soft decoders for hypergraph product codes

Antoine Grospellier1, Lucien Grouès1, Anirudh Krishna2, and Anthony Leverrier1

1Inria, 2 Rue Simone IFF, CS 42112, 75589 Paris Cedex 12, France
2Université de Sherbrooke, 2500 Boulevard de l'Université, Sherbrooke, QC J1K 2R1, Canada

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


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.

Quantum error correcting codes serve to buffer quantum information against noise. We are on the cusp of demonstrating that error correction is possible in the laboratory. It is clear what sorts of quantum codes will be used in the near term for achieving these milestones. The path further is less clear; quantum codes that succeed in the near term, such as the surface code, seem to require a prohibitive resource overhead as we scale. Can we find quantum codes which circumvent some of the limitations of these approaches?
While out of experimental reach currently, quantum low-density parity-check (LDPC) codes could be the answer in the long term. In theory, they promise a smaller resource cost compared to current techniques. However more research is needed before we can be certain whether this architecture is worth the experimental effort to explore. We take steps towards bridging this gap between theory and practice. To be specific, previous theoretical works only promise that quantum LDPC codes perform well for large quantum circuits. Part of the trouble stemmed from decoding algorithms, i.e. techniques to troubleshoot and correct errors. These algorithms seemed to require far too many qubits before becoming practical.
In this work, we pick a particular class of quantum LDPC codes called hypergraph product codes. We present new decoding algorithms, constructed as hybrids of classical and quantum decoding algorithms. We study different scenarios of increasing complexity, first assuming that the readout (syndrome extraction) can be done perfectly, and then working with models that assume that the readout itself is error prone. Our results show significant improvement over previous work and are supported by different metrics such as the (pseudo-)threshold and the weight of the parity checks. This provides evidence that such codes are well-worth investigating in the context of building large universal quantum computers.

► BibTeX data

► 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. ACM, 1997. 10.1137/​S0097539799359385. URL https:/​/​​10.1137/​S0097539799359385.

[2] Héctor 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:/​/​​doi/​10.1103/​PhysRevX.2.021004.

[3] 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:/​/​​doi/​10.1103/​PhysRevLett.104.050503.

[4] Nikolas P Breuckmann and Vivien Londe. Single-Shot Decoding of Linear Rate LDPC Quantum Codes with High Performance. arXiv preprint arXiv:2001.03568, 2020.

[5] Nikolas P Breuckmann and Barbara M Terhal. Constructions and noise threshold of hyperbolic surface codes. IEEE transactions on Information Theory, 62 (6): 3731–3744, 2016. 10.1109/​TIT.2016.2555700.

[6] 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.

[7] Benjamin J Brown, Naomi H Nickerson, and Dan E Browne. Fault-tolerant error correction with the gauge color code. Nature communications, 7 (1): 1–8, 2016. 10.1038/​ncomms12302.

[8] 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.

[9] Christopher T Chubb and Steven T Flammia. Statistical mechanical models for quantum codes with correlated noise. arXiv preprint arXiv:1809.10704, 2018.

[10] 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.

[11] 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–921. IEEE, 2013. 10.1109/​ISIT.2013.6620360.

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

[13] 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.

[14] 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, 2018a. 10.1109/​FOCS.2018.00076.

[15] 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–534. ACM, 2018b. 10.1145/​3188745.3188886.

[16] 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–1396, 1995. 10.1109/​18.412683.

[17] Michael H Freedman, David A Meyer, and Feng Luo. Z2-systolic freedom and quantum codes. Mathematics of quantum computation, Chapman & Hall/​CRC, pages 287–320, 2002.

[18] Daniel Gottesman. Stabilizer codes and quantum error correction. arXiv preprint quant-ph/​9705052, 1997.

[19] Daniel Gottesman. Fault-tolerant quantum computation with constant overhead. Quantum Information & Computation, 14 (15-16): 1338–1372, 2014. 10.5555/​2685179.2685184.

[20] Antoine Grospellier and Anirudh Krishna. Numerical study of hypergraph product codes. arXiv preprint arXiv:1810.03681, 2018.

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

[22] A Yu Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52 (6): 1191–1249, 1997. 10.4213/​rm892.

[23] 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–384. The Royal Society, 1998. 10.1126/​science.279.5349.342.

[24] 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–352. IEEE, 2012. 10.1109/​ISIT.2012.6284206.

[25] 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.

[26] 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.

[27] 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:/​/​​doi/​10.1103/​PhysRevResearch.2.023116.

[28] 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:/​/​​doi/​10.1103/​PhysRevX.11.011023.

[29] Anthony Leverrier, Jean-Pierre Tillich, and Gilles Zémor. Quantum expander codes. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 810–824. IEEE, 2015. 10.1109/​FOCS.2015.55.

[30] Muyuan Li and Theodore J. Yoder. A numerical study of bravyi-bacon-shor and subsystem hypergraph product codes. pages 109–119, 2020. 10.1109/​QCE49297.2020.00024.

[31] 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–391, 2019. 10.26421/​QIC19.5-6.

[32] Brendan D McKay and Xiaoji Wang. Asymptotic enumeration of 0–1 matrices with equal row sums and equal column sums. Linear algebra and its applications, 373: 273–287, 2003. 10.1016/​S0024-3795(03)00506-8.

[33] Pavel Panteleev and Gleb Kalachev. Degenerate quantum ldpc codes with good finite length performance. arXiv preprint arXiv:1904.02703, 2019.

[34] David Poulin and Yeojin Chung. On the iterative decoding of sparse quantum codes. Quantum Information & Computation, 8 (10): 987–1000, 2008. 10.5555/​2016985.2016993.

[35] Tom Richardson and Ruediger Urbanke. Modern coding theory. Cambridge university press, 2008.

[36] Michael Sipser and Daniel A Spielman. Expander codes. In Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on, pages 566–576. IEEE, 1994. 10.1109/​18.556667.

[37] Andrew Steane. Multiple-particle interference and quantum error correction. Proceedings of the Royal Society A, 452 (1954): 2551–2577, 1996. 10.1098/​rspa.1996.0136.

[38] 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 (2): 1193–1202, 2014. 10.1109/​TIT.2013.2292061.

[39] 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–58, 2003. 10.1016/​S0003-4916(02)00019-2.

[40] 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.

[41] 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.

Cited by

[1] Kao-Yueh Kuo, I-Chun Chern, and Ching-Yi Lai, 2021 IEEE International Symposium on Information Theory (ISIT) 1552 (2021) ISBN:978-1-5386-8209-8.

[2] Nikolas P. Breuckmann and Jens Niklas Eberhardt, "Quantum Low-Density Parity-Check Codes", PRX Quantum 2 4, 040101 (2021).

[3] Javier Valls, Francisco Garcia-Herrero, Nithin Raveendran, and Bane Vasic, "Syndrome-Based Min-Sum vs OSD-0 Decoders: FPGA Implementation and Analysis for Quantum LDPC Codes", IEEE Access 9, 138734 (2021).

[4] 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, 043423 (2020).

[5] Nikolas P. Breuckmann and Jens Niklas Eberhardt, "LDPC Quantum Codes", arXiv:2103.06309.

[6] Armanda O. Quintavalle, Michael Vasmer, Joschka Roffe, and Earl T. Campbell, "Single-Shot Error Correction of Three-Dimensional Homological Product Codes", PRX Quantum 2 2, 020340 (2021).

[7] Ryan Babbush, Jarrod McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven, "Focus beyond quadratic speedups for error-corrected quantum advantage", arXiv:2011.04149.

[8] Nicolas Delfosse, Vivien Londe, and Michael Beverland, "Toward a Union-Find decoder for quantum LDPC codes", arXiv:2103.08049.

[9] Armanda O. Quintavalle and Earl T. Campbell, "Lifting decoders for classical codes to decoders for quantum codes", arXiv:2105.02370.

[10] Nicolas Delfosse, Michael E. Beverland, and Maxime A. Tremblay, "Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes", arXiv:2109.14599.

[11] Maxime A. Tremblay, Nicolas Delfosse, and Michael E. Beverland, "Constant-overhead quantum error correction with thin planar connectivity", arXiv:2109.14609.

The above citations are from Crossref's cited-by service (last updated successfully 2021-10-22 06:43:52) and SAO/NASA ADS (last updated successfully 2021-10-22 06:43:56). The list may be incomplete as not all publishers provide suitable and complete citation data.