Multiple-Bases Belief Propagation List Decoding for Quantum LDPC Codes This work was supported in part by NSF under Grant CCF-2415440.

Sheida Rabeti and Hessam Mahdavifar · 2026

Read Multiple-Bases Belief Propagation List Decoding for Quantum LDPC Codes This work was supported in part by NSF under Grant CCF-2415440. by Sheida Rabeti and Hessam Mahdavifar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14170.txt.

Introduction

Rabeti and Mahdavifar propose a Multiple-Bases Belief-Propagation List Decoder for quantum low-density parity-check codes. Its key idea is decoding diversity: several redundant parity-check representations built via cycle-free subtree decompositions of the Tanner graph run belief propagation in parallel. That extension carries the old MBBP framework into the quantum setting while keeping the linear-time complexity of standard BP. Simulations show it beating existing BP rivals, including BP with ordered statistics decoding.

Catalog record

CREATORSheida Rabeti and Hessam Mahdavifar
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28199
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.14170

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Multiple-Bases Belief Propagation List Decoding for Quantum LDPC Codes This work was supported in part by NSF under Grant CCF-2415440. Sheida Rabeti and Hessam Mahdavifar Abstract In this paper, we propose a belief-propagation (BP)-based decoder, termed the Multiple-Bases Belief-Propagation List Decoder (MBBP-LD), for quantum low-density parity-check (QLDPC) codes. The key idea is to generate structured decoding diversity by constructing multiple redundant parity-check representations via cycle-free subtree decompositions of the Tanner graph, and running BP decoding in parallel across these representations. This extends the classical Multiple-Bases Belief-Propagation (MBBP) framework to the quantum setting while preserving the linear-time complexity and efficiency of standard BP decoding, and avoids the need for super-linear post-processing. Simulation results demonstrate that MBBP-LD improves upon existing BP-based decoders, including BP with ordered statistics decoding (BP-OSD) and belief propagation with guided decimation (BPGD) across several QLDPC codes, while requiring substantially fewer total BP iterations. For bivariate bicycle codes [ [ 144 , 12 , 12 ] ] [[144,12,12]] and [ [ 288 , 12 , 18 ] ] [[288,12,18]] , MBBP-LD achieves up to 20 % 20\% reduction in error rate compared to BPGD and up to 30 % 30\% compared to BP-OSD in the low- and moderate-error regimes. For the larger B1 code [ [ 882 , 24 , 18 ⩽ d ⩽ 24 ] ] [[882,24,18\leqslant d\leqslant 24]] , MBBP-LD attains comparable or improved performance relative to BPGD while maintaining BP-like decoding latency under parallel implementation. I Introduction Quantum error-correcting codes are essential for fault-tolerant quantum computation. Among existing constructions, quantum low-density parity-check (QLDPC) codes have attracted significant attention due to their sparse parity-check matrices, which reduce qubit–qubit interactions during syndrome extraction and make them well suited for architectures with limited qubit connectivity. Building on the success of classical LDPC codes introduced by Gallager [ 9 ] , recent advances in QLDPC code constructions have further highlighted their potential for scalable quantum computing [ 1 , 3 , 21 ] . However, realizing this potential in practice depends on the availability of efficient and high-performance decoding algorithms. Belief propagation (BP) remains one of the most widely used decoding algorithms for both classical and quantum LDPC codes due to its low complexity and highly optimized hardware implementations. However, in QLDPC codes, its performance is often degraded by code degeneracy, short cycles, and trapping sets in the Tanner graph. A variety of BP-based improvements have been proposed to address these limitations. These include BP with ordered statistics decoding (BP-OSD), which achieves strong performance at the cost of a super-linear complexity dominated by the order-statistics stage scaling as \mathcal{O}(n^{3}) in the worst case (where n is the block length) [ 14 ] , as well as iterative enhancements such as layered decoding, serial scheduling, and bit-flipping methods [ 7 , 16 , 4 ] . Other approaches rely on additional post-processing, including stabilizer inactivation (BP-SI) and belief propagation with guided decimation (BPGD), with complexities \mathcal{O}(n^{2}\log n) and \mathcal{O}(n^{2}) , respectively [ 8 , 23 ] . Further variants such as Ambiguity Clustering, Localized Statistics Decoding, and the Ordered Tanner Forest method also aim to improve decoding performance through increasingly sophisticated post-processing steps [ 22 , 12 , 5 ] . In this work, we propose a Multiple-Bases Belief-Propagation List-Decoding (MBBP-LD) framework for QLDPC codes. The key idea is to generate structured decoding diversity within the BP framework, enabling improved error-rate performance while preserving the low-complexity and hardware-efficient nature of BP. In particular, the proposed approach maintains decoding latency comparable to standard BP under parallel implementation and avoids the need for super-linear post-processing, in contrast to existing high-performance BP-based decoders such as BP-OSD and BPGD. More specifically, the proposed decoder constructs multiple redundant parity-check representations, executes BP decoding on each in parallel, and aggregates the resulting candidate error estimates through a list-based decision stage. Building on classical MBBP decoding [ 11 , 10 ] , our approach extends BP-based methods in two important respects. First, we employ augmented parity-check constructions that allow duplicated parity-check rows [ 18 , 17 ] . Second, and more importantly, instead of random row selection as in [ 18 , 17 ] , we introduce deterministic subtree-based decompositions of the Tanner graph to construct structured redundant representations. These cycle-free substructures induce diverse decoding trajectories across parallel BP instances, thereby mitigating trapping-set effects and enhancing decoding performance. II Preliminaries II-A Quantum Stabilizer and CSS Codes An [[n,k,d]] quantum stabilizer code is a 2^{k} -dimensional subspace \mathcal{C}\subseteq(\mathbb{C}^{2})^{\otimes n} with an Abelian stabilizer group \mathcal{S} : \mathcal{C}=\{|\psi\rangle\in(\mathbb{C}_{2})^{\otimes n}\colon s|\psi\rangle=|\psi\rangle,\forall s\in\mathcal{S}\}. (1) Each generator g\in\mathcal{S} acts as a parity-check constraint. The minimum distance d of a stabilizer code is the minimum weight of some Pauli operator P\in{\cal P}_{n} commuting with elements in {\cal S} such that P\notin{\cal S} . A Calderbank–Shor–Steane (CSS) code is a stabilizer code with a parity-check matrix of the form H=\begin{bmatrix}H_{X}&0\\ 0&H_{Z}\end{bmatrix}, where H_{X},H_{Z} are classical binary parity-check matrices satisfying H_{X}H_{Z}^{T}=0 . Such codes can correct Pauli- X and Pauli- Z errors independently using H_{Z} and H_{X} , respectively. In this work, we focus on QLDPC CSS codes, where both H_{X} and H_{Z} are sparse. II-B Belief Propagation (BP) Decoding BP decoding operates on the Tanner graph of {\cal G}=(V_{c}\cup V_{v},E) , where V_{c} are check nodes, V_{v} are variable nodes, and E denotes edges. Also, d_{v} and d_{c} denote the maximum degrees of variable nodes and check nodes, respectively. For each variable v_{i} , the log-likelihood ratio (LLR) is initialized as \mu_{i}=\log\frac{1-p}{p} , where p is the physical error probability (assumed identical for Pauli- X and Pauli- Z errors). During iterations, messages are updated using the normalized min-sum rule: \displaystyle m^{(t+1)}_{c\to v} \displaystyle=\alpha\!\!\left(\prod_{v^{\prime}\in N(c)\setminus v}\mathrm{sign}\hbox{$\left(\vbox to0.0pt{}\right.$}m^{(t)}_{v^{\prime}\to c}\hbox{$\left)\vbox to0.0pt{}\right.$}\right)\min_{v^{\prime}\in N(c)\setminus v}\!\!\left|m^{(t)}_{v^{\prime}\to c}\right|, (2) \displaystyle m^{(t+1)}_{v\to c} \displaystyle=\mu_{i}+\sum_{c^{\prime}\in N(v)\setminus c}m^{(t)}_{c^{\prime}\to v}. (3) The posterior LLR is m^{(t)}_{i}=\mu_{i}+\sum_{c\in N(v_{i})}m^{(t)}_{c\to v_{i}} . A hard decision is made as \hat{e}_{i}=0 if m^{(t)}_{i}\geqslant 0 , otherwise \hat{e}_{i}=1 . The algorithm halts when all parity checks satisfy the syndrome (i.e., a valid error pattern is found) or when a maximum number of iterations is reached. Serial scheduling updates check nodes sequentially and immediately propagates messages within the same iteration, improving convergence speed. In QLDPC codes, the presence of short cycles and degeneracy can significantly affect the convergence behavior of BP, motivating the need for modified decoding strategies. II-C Belief Propagation with Augmented Parity Checks Augmented parity-check (APC) decoding improves BP by introducing redundancy through duplicating a subset of rows in the original parity-check matrix [ 18 , 17 ] . Let H\in\mathbb{F}_{2}^{m\times n} denote the original parity-check matrix and define the augmented matrix as H_{A}=\begin{bmatrix}H\\ H_{\text{dup}}\end{bmatrix}, where H_{\text{dup}} contains duplicated rows from H . BP is then executed on H_{A} instead of H . Duplicated checks place more emphasis on certain parity constraints and change the convergence behavior of BP, which can help mitigate trapping sets while preserving the same per-iteration complexity as standard BP [ 17 ] . Existing APC methods typically generate H_{\text{dup}} through random row selection. However, the use of randomly selected duplicated rows may not fully exploit the underlying graph structure, which motivates more structured approaches to constructing redundant parity-check representations. III Multiple-Bases Belief-Propagation List-decoding (MBBP-LD) In this section, we extend the classical Multiple-Bases Belief-Propagation (MBBP) framework [

Read the complete text