Guided Decimation for Belief-Propagation Decoding of Quantum Low-Density Parity-Check Codes

Abstract

Abstract Quantum low-density parity-check (qLDPC) codes have emerged as a promising solution for fault-tolerant quantum computing systems. However, the conventional belief propagation (BP) decoder applied to qLDPC codes suffers from the degeneracy problem and short cycles that lead to symmetric stabilizer trapping sets. To address these challenges, we propose a novel BP-based iterative algorithm referred to as BP guided decimation (BPGD). Decimation is assigning high belief to a variable node, and freezing that belief. After the first BP run, two new BP runs are initiated by decimating the variable node with the lowest absolute belief i.e., freezing its value to 0 and 1, respectively. This iterative process continues until convergence is attained or a fixed decimation count is reached. The complexity of BPGD is reduced by significantly reducing the count of the active nodes that participate in the BP operations. Pruning the BP runs is also done to reduce the complexity, by discarding the branch with the lowest total absolute beliefs. As a result, BPGD offers a controllable trade-off between complexity and performance, enabling the reduction of complexity at the expense of a potential decrease in performance. Notably, when compared against BP-ordered statistics decoding (order 0), BPGD demonstrates superior performance.