quantum-computing

Informed Dynamic Scheduling for QLDPC Codes

Tzu-Hsuan Huang and Yeong-Luh Ueng

14 min read

0 likes

⚡ Quantum Brief

AI Audio Summary

0:00 / 0:00

Click to play

Quantum News · Media Library

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractRecent research has shown that syndrome-based belief propagation using layered scheduling (sLBP) can not only accelerate the convergence rate but also improve the error rate performance by breaking the quantum trapping sets for quantum low-density parity-check (QLDPC) codes, showcasing a result distinct from classical error correction codes. In this paper, we consider edge-wise informed dynamic scheduling (IDS) for QLDPC codes based on syndrome-based residual belief propagation (sRBP). However, the construction of QLDPC codes and the identical prior intrinsic information assignment will result in an equal residual in many edges, causing a performance limitation for sRBP. Two heuristic strategies, including edge pool design and error pre-correction, are introduced to tackle this obstacle and quantum trapping sets. Then, a novel sRBP equipped with a predict-and-reduce-error mechanism (PRE-sRBP) is proposed, which can provide over one order of performance gain on the considered bicycle codes and symmetric hypergraph (HP) code under similar iterations compared to sLBP.► BibTeX data@article{Huang2026informeddynamic, doi = {10.22331/q-2026-01-16-1967}, url = {https://doi.org/10.22331/q-2026-01-16-1967}, title = {Informed {D}ynamic {S}cheduling for {QLDPC} {C}odes}, author = {Huang, Tzu-Hsuan and Ueng, Yeong-Luh}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1967}, month = jan, year = {2026} }► References [1] Nikolas P. Breuckmann and Jens Niklas Eberhardt. ``Quantum low-density parity-check codes''. PRX Quantum 2, 040101 (2021). https://doi.org/10.1103/PRXQuantum.2.040101 [2] Maxime A. Tremblay, Nicolas Delfosse, and Michael E. Beverland. ``Constant-overhead quantum error correction with thin planar connectivity''. Phys. Rev. Lett. 129, 050504 (2022). https://doi.org/10.1103/PhysRevLett.129.050504 [3] Sergey Bravyi, Andrew W. Cross, Dmitri Maslov Jay M. Gambetta, Patrick Rall, and Theodore J. Yoder. ``High-threshold and low-overhead fault-tolerant quantum memory''. Nature 627, 778 (2024). https://doi.org/10.1038/s41586-024-07107-7 [4] Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information''.

Cambridge University Press. (2009). 10th Anniversary edition. https://doi.org/10.1017/cbo9780511976667 [5] A.R. Calderbank, E.M. Rains, P.M. Shor, and N.J.A. Sloane. ``Quantum error correction via codes over GF(4)''. IEEE Transactions on Information Theory 44, 1369 (1998). https://doi.org/10.1109/18.681315 [6] D.J.C. MacKay, G. Mitchison, and P.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 [7] David Poulin and Yeojin Chung. ``On the iterative decoding of sparse quantum codes''. Quant. Inf. Comput. 8, 0987–1000 (2008). https://doi.org/10.26421/QIC8.10-8 [8] Nithin Raveendran and Bane Vasić. ``Trapping sets of quantum LDPC codes''. Quantum 5 (2021). https://doi.org/10.22331/q-2021-10-14-562 [9] 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 [10] Joschka Roffe, David R. White, Simon Burton, and Earl Campbell. ``Decoding across the quantum low-density parity-check code landscape''. Phys. Rev. Res. 2, 043423 (2020). https://doi.org/10.1103/PhysRevResearch.2.043423 [11] Javier Valls, Francisco Garcia-Herrero, Nithin Raveendran, and Bane Vasić. ``Syndrome-based min-sum vs OSD-0 decoders: FPGA implementation and analysis for quantum ldpc codes''. IEEE Access 9, 138734–138743 (2021). https://doi.org/10.1109/ACCESS.2021.3118544 [12] Andres I. Vila Casado, Miguel Griot, and Richard Wesel. ``Improving LDPC decoders via informed dynamic scheduling''.

In Information Theory Workshop. Pages 208–213. (2007). https://doi.org/10.1109/ITW.2007.4313075 [13] Gal Elidan, Ian McGraw, and Daphne Koller. ``Residual belief propagation: Informed scheduling for asynchronous message passing'' (2012). arXiv:1206.6837. arXiv:1206.6837 [14] A. I. V. Casado, M. Griot, and R. D. Wesel. ``Informed dynamic scheduling for belief-propagation decoding of LDPC codes''. In 2007 IEEE International Conference on Communications. Pages 932–937. (2007). https://doi.org/10.1109/ICC.2007.158 [15] Andres I. Vila Casado, Miguel Griot, and Richard D. Wesel. ``LDPC decoders with informed dynamic scheduling''. IEEE Transactions on Communications 58, 3470–3479 (2010). https://doi.org/10.1109/TCOMM.2010.101910.070303 [16] Tofar C.-Y. Chang, Pin-Han Wang, Jian-Jia Weng, I-Hsiang Lee, and Yu T. Su. ``Belief-propagation decoding of LDPC codes with variable node–centric dynamic schedules''. IEEE Transactions on Communications 69, 5014–5027 (2021). https://doi.org/10.1109/TCOMM.2021.3078776 [17] 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 (2014). https://doi.org/10.1109/TIT.2013.2292061 [18] Daniel Eric Gottesman. ``Stabilizer codes and quantum error correction''. PhD thesis. California Institute of Technology. (1997). https://doi.org/10.7907/rzr7-dt72 [19] Richard Cleve. ``Quantum stabilizer codes and classical linear codes''. Phys. Rev. A 55, 4054–4059 (1997). https://doi.org/10.1103/PhysRevA.55.4054 [20] A. R. Calderbank and Peter W. Shor. ``Good quantum error-correcting codes exist''. Phys. Rev. A 54, 1098–1105 (1996). https://doi.org/10.1103/PhysRevA.54.1098 [21] A. M. Steane. ``Error correcting codes in quantum theory''. Phys. Rev. Lett. 77, 793–797 (1996). https://doi.org/10.1103/PhysRevLett.77.793 [22] Emanuel Knill and Raymond Laflamme. ``Theory of quantum error-correcting codes''. Phys. Rev. A 55, 900–911 (1997). https://doi.org/10.1103/PhysRevA.55.900 [23] F.R. Kschischang, B.J. Frey, and H.-A. Loeliger. ``Factor graphs and the sum-product algorithm''. IEEE Transactions on Information Theory 47, 498–519 (2001). https://doi.org/10.1109/18.910572 [24] D. J. C. MacKay. ``Information theory, inference and learning algorithms''.

Cambridge University Press. (2003). [25] Ching-Yi Lai and Kao-Yueh Kuo. ``Log-domain decoding of quantum LDPC codes over binary finite fields''. IEEE Transactions on Quantum Engineering 2, 1–15 (2021). https://doi.org/10.1109/TQE.2021.3113936 [26] Tom Richardson. ``Error floors of LDPC codes''. Proc. annual Allerton conference on commun. control and computing (2003). [27] D.E. Hocevar. ``A reduced complexity decoder architecture via layered decoding of LDPC codes''. In IEEE Workshop onSignal Processing Systems, 2004. SIPS 2004. Pages 107–112. (2004). https://doi.org/10.1109/SIPS.2004.1363033 [28] Juntan Zhang and M.P.C. Fossorier. ``Shuffled iterative decoding''. IEEE Transactions on Communications 53, 209–213 (2005). https://doi.org/10.1109/TCOMM.2004.841982 [29] J. Chen and M.P.C. Fossorier. ``Density evolution for two improved BP-based decoding algorithms of LDPC codes''. IEEE Communications Letters 6, 208–210 (2002). https://doi.org/10.1109/4234.1001666 [30] 3GPP. ``5G; NR; multiplexing and channel coding (release 15) 38.212''. document Technical specification (TS) (2018). [31] Xingcheng Liu, Zhenzhu Zhou, Ru Cui, and Erwu Liu. ``Informed decoding algorithms of LDPC codes based on dynamic selection strategy''. IEEE Transactions on Communications 64, 1357–1366 (2016). https://doi.org/10.1109/TCOMM.2016.2527642 [32] Xingcheng Liu, Chunlei Fan, and Xuechen Chen. ``Dynamic scheduling decoding of LDPC codes based on Tabu search''. IEEE Transactions on Communications 65, 4612–4621 (2017). https://doi.org/10.1109/TCOMM.2017.2732950 [33] Xingcheng Liu, Li'e Zi, Dong Yang, and Zhongfeng Wang. ``Improved decoding algorithms of LDPC codes based on reliability metrics of variable nodes''. IEEE Access (2019). https://doi.org/10.1109/ACCESS.2019.2904173 [34] R. Gallager. ``Low-density parity-check codes''. IRE Transactions on Information Theory 8, 21–28 (1962). https://doi.org/10.1109/TIT.1962.1057683 [35] Tzu-Hsuan Huang. ``PRE-sRBP''. https://github.com/quantumrbp/srbp.git (2026). https://github.com/quantumrbp/srbp.git [36] Nedeljko Varnica, Marc P. C. Fossorier, and Aleksandar Kavcic. ``Augmented belief propagation decoding of low-density parity check codes''. IEEE Transactions on Communications 55, 1308–1317 (2007). https://doi.org/10.1109/TCOMM.2007.900611 [37] D. Chase. ``Class of algorithms for decoding block codes with channel measurement information''. IEEE Transactions on Information Theory 18, 170–182 (1972). https://doi.org/10.1109/TIT.1972.1054746 [38] Joschka Roffe. ``LDPC: Python tools for low density parity check codes''. https://pypi.org/project/ldpc/ (2022). https://pypi.org/project/ldpc/ [39] Tzu-Hsuan Huang and Yeong-Luh Ueng. ``A binary BP decoding using posterior adjustment for quantum LDPC codes''. In ICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). Pages 9001–9005. (2024). https://doi.org/10.1109/ICASSP48485.2024.10446153 [40] H. Yao, W. A. Laban, C. Hager, A. G. i Amat, and H. D. Pfister. ``Belief propagation decoding of quantum LDPC codes with guided decimation'' (2023). arXiv:2312.10950. arXiv:2312.10950 [41] Julien Du Crest, Francisco Garcia-Herrero, Mehdi Mhalla, Valentin Savin, and Javier Valls. ``Layered decoding of quantum ldpc codes''. In 2023 12th International Symposium on Topics in Coding (ISTC). Pages 1–5. (2023). https://doi.org/10.1109/ISTC57237.2023.10273477 [42] Adam Holmes, Mohammad Reza Jokar, Ghasem Pasandi, Yongshan Ding, Massoud Pedram, and Frederic T. Chong. ``Nisq+: Boosting quantum computing power by approximating quantum error correction''. In 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA). Pages 556–569. (2020). https://doi.org/10.1109/ISCA45697.2020.00053 [43] Kao-Yueh Kuo and Ching-Yi Lai. ``Refined belief propagation decoding of sparse-graph quantum codes''. IEEE Journal on Selected Areas in Information Theory 1, 487–498 (2020). https://doi.org/10.1109/JSAIT.2020.3011758Cited byCould not fetch Crossref cited-by data during last attempt 2026-01-16 13:35:33: Could not fetch cited-by data for 10.22331/q-2026-01-16-1967 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-01-16 13:35:33: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractRecent research has shown that syndrome-based belief propagation using layered scheduling (sLBP) can not only accelerate the convergence rate but also improve the error rate performance by breaking the quantum trapping sets for quantum low-density parity-check (QLDPC) codes, showcasing a result distinct from classical error correction codes. In this paper, we consider edge-wise informed dynamic scheduling (IDS) for QLDPC codes based on syndrome-based residual belief propagation (sRBP). However, the construction of QLDPC codes and the identical prior intrinsic information assignment will result in an equal residual in many edges, causing a performance limitation for sRBP. Two heuristic strategies, including edge pool design and error pre-correction, are introduced to tackle this obstacle and quantum trapping sets. Then, a novel sRBP equipped with a predict-and-reduce-error mechanism (PRE-sRBP) is proposed, which can provide over one order of performance gain on the considered bicycle codes and symmetric hypergraph (HP) code under similar iterations compared to sLBP.► BibTeX data@article{Huang2026informeddynamic, doi = {10.22331/q-2026-01-16-1967}, url = {https://doi.org/10.22331/q-2026-01-16-1967}, title = {Informed {D}ynamic {S}cheduling for {QLDPC} {C}odes}, author = {Huang, Tzu-Hsuan and Ueng, Yeong-Luh}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1967}, month = jan, year = {2026} }► References [1] Nikolas P. Breuckmann and Jens Niklas Eberhardt. ``Quantum low-density parity-check codes''. PRX Quantum 2, 040101 (2021). https://doi.org/10.1103/PRXQuantum.2.040101 [2] Maxime A. Tremblay, Nicolas Delfosse, and Michael E. Beverland. ``Constant-overhead quantum error correction with thin planar connectivity''. Phys. Rev. Lett. 129, 050504 (2022). https://doi.org/10.1103/PhysRevLett.129.050504 [3] Sergey Bravyi, Andrew W. Cross, Dmitri Maslov Jay M. Gambetta, Patrick Rall, and Theodore J. Yoder. ``High-threshold and low-overhead fault-tolerant quantum memory''. Nature 627, 778 (2024). https://doi.org/10.1038/s41586-024-07107-7 [4] Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information''.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Discussion

0 professional contributions

Be the first to add a constructive contribution.

Informed Dynamic Scheduling for QLDPC Codes

Tags

Source Information