Informed Dynamic Scheduling for QLDPC Codes

In a single-qubit system, Pauli operators describe the operations acting on a single qubit, consisting of $I,X,Z,$ and $Y=iXZ$, where $i=\sqrt{-1}$ and each element is mutually anti-commute [4]. For example, $X$ and $Z$ denote a bit-flip and phase-flip on a single qubit state. The Pauli group $\mathcal{G}_{1}$ is formed by Pauli operators with the multiplicative factors $\pm{1}$ and $\pm{i}$. For an $N$-qubit system, the general Pauli group $\mathcal{G}_{N}$ is considered as the $N$-fold tensor product of $\mathcal{G}_{1}$.

Quantum stabilizer codes are well-studied due to their similar form to classical linear codes [18, 19]. An $[[N,K,d]]$ stabilizer code $C_{S}$ encodes $K$ qubits to an $N$-qubit codeword with a minimum distance $d$. As its name suggests, $C_{S}$ is defined by its stabilizer group $\mathcal{S}\subseteq\mathcal{G}_{n}$, where $-I\notin\mathcal{S}$. All the elements in $\mathcal{S}$ are mutually commuted to ensure the bit-flip and phase-flip can be detected simultaneously. Furthermore, $\mathcal{S}$ can be characterized by $N-K$ generators $g_{i}\in\mathcal{G}_{n},0\leq i<N-K$, i.e., $\mathcal{S}=\langle g_{i}\rangle$. An $N$-qubit codeword $\ket{\psi}\in C_{S}$ is then the $+1$ eigenstate of all the generators, i.e., $\mathcal{P}\ket{\psi}=\ket{\psi},\ \mathcal{P}\in\langle g_{i}\rangle$. Since the Pauli operators can be expressed as a binary string, i.e., $I\mapsto(0\ 0),X\mapsto(1\ 0),Z\mapsto(0\ 1),Y\mapsto(1\ 1)$, the set of $N-K$ generators can then be represented as a binary matrix $H_{S}=(H_{X_{\mathcal{S}}}\ H_{Z_{\mathcal{S}}})$, where $H_{X_{\mathcal{S}}},H_{Z_{\mathcal{S}}}\in F^{(N-K)\times N}_{2}$. By using the binary representation, the commutativity of each generator is then expressed as the orthogonality of the rows under the symplectic product, equivalently,

where $\oplus$ is the addition under mod 2.

It can be seen that identifying two matrices satisfying the constraint (1) is not trivial. Thus, a class of stabilizer codes, called the Calderbank, Shor-Steane (CSS) codes, are widely used [20, 21]. The parity-check matrix for a CSS code has the form

Thus, the equation (1) can be reduced to $H_{X}H_{Z}^{T}=\mathbf{0}$. Suppose two classical linear block codes satisfy the relationship $C_{X}\subset C_{Z}$, then the parity-check matrix $H_{Z}$ of the code $C_{Z}$ and $H_{X}$ of $C^{\bot}_{X}$ can form a CSS code since $G_{X}H_{Z}^{T}=\mathbf{0}$, where $G_{X}$ is the generator matrix of $C_{X}$. If $C_{X}$ and $C_{Z}$ are LDPC codes, i.e., the non-zero elements in its parity-check matrix are sparse, then the corresponding quantum code is called a QLDPC code. The QLDPC codes considered in this paper, including the bicycle code [6], generalized bicycle code [9], and HP code [17], are all types of CSS codes.

For an $N$-qubit system, any arbitrary error pattern can be digitalized and can then be represented as the element in the $N$-fold Pauli group, which consists of $X$ and $Z$ [22]. Thus, the noisy model can be viewed as two independent channels, a bit-flip with probability $p_{x}$ and a phase-flip with $p_{z}$. Since all the codes considered in this paper are CSS codes, neglecting the correlation between $X$ and $Z$ errors, it is sufficient to decode using just one type of parity-check matrix and error channel. For instance, the bit-flip noisy channel with crossover probability $p_{x}$ and $H_{Z}=H$ are considered in this paper.

To apply binary BP on the given error correction code, the parity-check matrix $H\in F^{M\times N}_{2}$ of the code is first transformed to a factor graph (or the Tanner graph [23]), which consists of $M$ check nodes and $N$ variable nodes, denoted as $c_{i}$ and $v_{j}$, corresponding to the $i$th row and the $j$th column of the parity-check matrix, respectively. Let $d_{c_{i}}$ be the degree of check node $c_{i}$. Them each check node $c_{i}$ has $d_{c_{i}}$ edges linked to its neighboring variable node $v_{j}$, where $v_{j}\in\mathcal{N}(c_{i})=\{v_{j^{\prime}}|{H}_{ij^{\prime}}=1\}$. Likewise, each variable node $v_{j}$ has $d_{v_{j}}$ edges linked to its neighboring check node $c_{i}$, where $d_{v_{j}}$ is the degree of variable node $v_{j}$ and $c_{i}\in\mathcal{N}(v_{j})=\{c_{i^{\prime}}|{H}_{i^{\prime}j}=1\}$.

To avoid confusion in this paper, we refer to an error vector $\mathbf{e}\in F^{N}_{2}$ as an error pattern. The index of each coordinate of $\mathbf{e}$ is referred to as the error position or a variable node in error (in the Tanner graph). The support of $\mathbf{e}$, denoted as $\text{supp}(\mathbf{e})$, is the set of indices corresponding to the non-zero error positions in $\mathbf{e}$, i.e., $\text{supp}(\mathbf{e})=\{j|0\leq j<N,e_{j}\neq 0\}$. Then, the weight of $\mathbf{e}$ is the cardinality of $\text{supp}(\mathbf{e})$, denoted as $w(\mathbf{e})$. The syndrome $\mathbf{s}\in F^{M}_{2}$ corresponding to an error pattern $\mathbf{e}$ can be computed as $\mathbf{s}=H\cdot\mathbf{e}$. Likewise, the syndrome position or a check node, the support of a syndrome $\text{supp}(\mathbf{s})$, and the weight $w(\mathbf{s})$ are used under a similar definition as for an error pattern.

A difference in using BP on quantum codes is that the intrinsic information from the channel cannot be measured directly due to the collapse of the quantum state. Instead, the syndrome measured on the auxiliary qubits is the only information that can be obtained [4]. Hence, the so-called syndrome-based BP (sBP) is used [24]. Considering the sBP decoder in the log domain [25], where the log-likelihood ratio (LLR) is used for message passing, we denote a message from $v_{j}$ to the neighboring $c_{i}$ at the $k$th iteration as $L^{k}_{v_{j}\rightarrow c_{i}}$, where $0\leq j<N$. Then, due to the lack of different prior intrinsic information for each variable node $v_{j}$, at the $0$th iteration, the prior LLR $L^{0}_{v_{j}}$ and $L^{0}_{v_{j}\rightarrow c_{i}}$ are both assigned to the identical constant value $\ln\frac{1-p}{p}$ for all $j$, given $p_{x}=p$. Then the message from $c_{i}$ to $v_{j}$ is computed according to

where $s_{i}$ denotes the $i$th syndrome position, where $0\leq i<M$.

In the next iteration, $L_{v_{j}\rightarrow c_{i}}$ is computed according to

The element-wise LLR $L^{k+1}_{v_{j}}$ at the $(k+1)$th iteration for each $v_{j}$ can be computed as

and the estimated error $\hat{e}^{k}_{v_{j}}=0$ if $L^{k+1}_{v_{j}}>0$; Otherwise, $\hat{e}^{k}_{v_{j}}=1$. Then the estimated syndrome at the $k$ iteration is $\hat{\mathbf{s}}^{k}=H\cdot\hat{\mathbf{e}}^{k}$. If $\hat{\mathbf{s}}^{k}$ is consistent with the given syndrome $\mathbf{s}$, the decoder is declared to have converged. Otherwise, the sBP decoder will repeat (3) and (4) until either the decoder converges or the maximum iteration $I_{\max}$ is reached. The sBP introduced above is sometimes referred to as flooding scheduling since, for an iteration, all the C2V messages are updated, followed by an update of all the variable-to-check (V2C) messages.

In the Tanner graph, a cycle is formed by a set of check and variable nodes that create a closed loop. The cycle length is determined by the number of edges it contains. As mentioned in Section 2.1, the CSS code is built from two classical codes that satisfy the symplectic product relationship, leading to more cycles and even length-4 cycles compared to the classical code, which will induce multiple quantum trapping sets. A quantum trapping set consists of classical-type trapping sets and symmetric stabilizer trapping sets. The classical type includes a set of variable nodes that cannot converge correctly even after sufficiently large iterations [8, Definition 1]. The subgraph induced by this kind of trapping set will contain odd-degree check nodes, and the most problematic trapping sets will contain degree-1 and degree-2 check nodes in the induced sub-graphs [26].

In contrast, the symmetric stabilizer trapping sets refer to a set of variable nodes that converge incorrectly, where the corresponding syndrome is inconsistent with the given syndrome [8, Definition 4]. Symmetric stabilizer trapping, which is unique to quantum codes, is related to code construction. Certain quantum codes have numerous sets of variable and check nodes, whose induced subgraphs have no odd-degree check nodes and can be partitioned into symmetric disjoint subsets [8, Definition 5]. Under these conditions, it’s possible that, given a syndrome, there are two equal-weight error patterns in the subgraph. As a result, the iterative decoder cannot determine which one should be converged upon and often converges to the addition of these two error patterns, leading to a zero syndrome. According to [8], HP codes suffer from an error floor due to the abundance of quantum trapping sets.

Unlike fixed scheduling, where the update order of the check or variable node is predetermined sequentially before the iteration begins, IDS, an edge-wise decoder, dynamically changes the update order of the edges according to the residual

where the residual is referred to as the norm of the difference between the pre-computed message $m^{pre}_{k}$ and the current message $m_{k}$. For instance, a specific criterion of the RBP [13] is to identify the update order according to the residual of the C2V message, which is defined as

The criterion is based on the idea that a larger residual indicates lower message reliability, necessitating more message updates to achieve convergence. Therefore, prioritizing updates to these edges can accelerate the convergence rate. Additionally, following the edge-wise criterion, the update order can spoil the constraint of the topological structure compared to fixed scheduling, which may lead to an improvement in error-rate performance.

To reduce the complexity of the pre-computation $m^{pre}_{c_{i}\rightarrow v_{j}}$, the min-sum algorithm (MSA) [29] can be applied to replace (3) with

Several algorithms based on sRBP for quantum codes are presented in this section. The concept of the edge pool is introduced to aid in distinguishing the similarities and differences between algorithms. Let $c_{\max}$ and $v_{\max}$ respectively denote the chosen check node and the variable node corresponding to the $\max_{\bigl{\{}\{c_{i},v_{j}\}\in\mathfrak{R}\bigl{\}}}r_{c_{i}\rightarrow v_{j}}$, where $\{c_{i},v_{j}\}$ represents an edge connected by check node $c_{i}$ and variable node $v_{j}$, and an edge pool $\mathfrak{R}$ is a set of edges. Then, after computing all residuals $r_{c_{i}\rightarrow v_{j}}$ for all $0\leq i<M,v_{j}\in\mathcal{N}(c_{i})$ by using (7) and (8), we can arrange the sRBP and its variation algorithms into three main steps:

1. S.1

   Select the $c_{\max}$ and $v_{\max}$ corresponding to the maximum residual of all edges in the edge pool $\mathfrak{R}$ and update the edge from $c_{\max}$ to $v_{\max}$ by (3). The residual of the updated edge is assigned as zero.

2. S.2

   For every $c_{a}\in\mathcal{N}(v_{\max})\setminus c_{\max}$, update edges from $v_{\max}$ to $c_{a}$ using (4), and for every $v_{b}\in\mathcal{N}(c_{a})\setminus v_{\max}$, compute the new residual of the edges from $c_{a}$ to $v_{b}$ using (7).

3. S.3

   Select the next $c_{\max}$ and $v_{\max}$ as in S.1 but from the new edge pool $\mathfrak{R}^{\prime}$, which depends on different decoders.

The decoder will repeat the three steps above for a single iteration, where an iteration is conventionally defined as when the number of C2V updates reaches the total number of undirected edges $E$ in the parity-check matrix due to an unbalanced update of the edge-wise decoder. It can be observed that S.2 only depends on the choice of $c_{\max}$ and $v_{\max}$ in S.1. As a result, different IDSs concentrate on designing the $\mathfrak{R}$ and $\mathfrak{R}^{\prime}$. The design for the sRBP is shown in the Edge pool for sRBP.

In classical error correction, the convergent rate of RBP is faster than for both BP and LBP, i.e., the error rate performance is better for the first few iterations. However, if there are many iterations, the performance may worsen due to the greedy group phenomenon [13]. When RBP encounters an error that it can not solve, it may try to correct the wrong variable node, leading to another unsatisfied check node. As a result, the residual of the edges related to this incorrect variable node will always be significant. The update will always occur in these greedy groups of edges, consuming a large number of resources and never succeeding.

A node-wise RBP (NW-RBP) [15] has been proposed to address this issue. This approach simultaneously updates all edges from the same check node, allowing for the update of edges outside the greedy group and ultimately improving the error rate. In [15], the authors showed how NW-RBP can tackle trapping sets. Suppose a variable node in a trapping set has been solved. In that case, at least one degree-2 check node becomes degree-1, which is likely to be chosen due to the large residual, resulting in the possible correctness for another variable node in the trapping set. However, the performance improvement using NW-RBP comes at the partial cost of the convergence rate. For syndrome-based NW-RBP (NW-sRBP), the design is shown in Edge pool for NW-sRBP.

After updating $m_{c_{\max}\rightarrow v_{\max}}$ and propagating the related edges from $v_{\max}$ to its neighboring $c_{a}$, it is reasonable that not only the message for the edge from the $v_{\max}$ but also the message emitting from $c_{a}$ will be more reliable. Thus, the authors in [16] propose a strategy in which the next update is related to the latest-updated variable node, which they call the latest-message-driven RBP (LMD-RBP). From [16], it shows that the LMD-RBP algorithm performs better during the first few decoding iterations for the 5G New Radio LDPC codes [30]. The design for the syndrome-based LMD-RBP (LMD-sRBP) is shown in the Edge pool for LMD-sRBP.

We show the distribution of the error weight versus the solvable error ratio using sBP, sLBP, and other sRBP variations on the $[[256,32]]$ bicycle code, as shown in Fig. 1.

The results show that sBP can effectively solve error patterns with a weight of 9 or less with a ratio of over $94\%$. However, the solvable ratio decreases and cannot solve weights larger than 13, while sLBP can solve error patterns with a weight of 10 or less with a ratio over $98\%$. sRBP can almost solve error patterns with a weight of 10 or less with a ratio over $99\%$. However, for those with weights larger than 11, the ratio decreases rapidly. In contrast, by using LMD-sRBP, almost all error patterns with a weight of 10 or less can be solved with a ratio over $99\%$. Compared to sLBP, the average solvable ratio for weights larger than 11 is also higher.

The results shown in Fig. 1 indicate that there is room for improvement in performance using sRBP-based decoders on QLDPC codes. In classical error correction, the information of the residual of variable node, related to the different prior LLR $L^{0}_{v_{j}}$, can be used to assist the decoder in identifying the reliability of edges, resulting in the change of update priority [31, 32, 33].

However, this assistance design is limited when considering sRBP on QLDPC codes since the identical prior LLR is assigned for every variable node as described in Section 2.2. Additionally, QLDPC codes are often regular, defined in [34] as the parity-check matrix having a constant row weight and a constant column weight, which are not necessarily equal. Here, weight refers to the number of non-zero positions in a row or column. This regularity of QLDPC codes, due to construction limitation introduced in Section 2.1, coupled with identical prior LLR assignments, results in an equal residual in many edges. Thus, the decoder may struggle to identify the reliability residual of the C2V and select the ineffective edge, which will have no effect on the error position in the trapping set, leading to a performance limitation.

To address the negative impact of the greedy group and trapping set, the first strategy is to design an edge pool that can offer various edges whenever we need to make a selection. In this way, the chance of the message exchange within and outside the greedy group or trapping set possibly leads to the decoding success. The second strategy is to predict an error position possibly belonging to the support of an error pattern and operate a pre-correction. If the error position involved in a trapping set can be solved first, then the effect of the trapping set may be mitigated. However, a candidate error position should be elaborately found since the syndrome is used as an input. Otherwise, the syndrome corresponding to the new error pattern after pre-correction would likely differ significantly from the original, resulting in a limitation on decoder performance.

To provide the diversity of the edge pool, we propose an $\mathfrak{R}$ induced by a variable node $v_{t}$ and a list of its neighboring check nodes that have not been updated, where $v_{t}$ will be adjusted for each time we update a C2V edge.

Given a current considered variable node $v_{t}$, each time to determine a C2V edge for updating, only those edges neighboring $v_{t}$ are compared in S.1, and $v_{t}$ is set to be different for the next time to determine the new C2V message update; in this way, we ensure that there must be different edges between $\mathfrak{R}^{\prime}$ and $\mathfrak{R}$. The order of the considered $v_{t}$ can be carefully designed by exploiting the correlation between each variable node, but in practice, sequentially setting $v_{t}$ from $0$ to $N-1$ is sufficient.

An additional $d_{v_{t}}$-tuple flag list $\mathbf{f}^{v_{t}}$ is further introduced to the C2V comparison for each $v_{t}$. Each element in $\mathbf{f}^{v_{t}}$, denoted as $f^{v_{t}}_{c_{i}}$, corresponds to neighboring check node $c_{i}\in\mathcal{N}(v_{t})$, which is initialized as 0. Each time to find a C2V edge from the edge pool induced by $v_{t}$, only edges from check node $c_{i}$ where $f^{v_{t}}_{c_{i}}=0$ are considered. When a C2V edge is updated in S.1, we set $f^{v_{t}}_{c_{\max}}=1$. In this way, we can further provide different edges between $\mathfrak{R}$ and $\mathfrak{R}^{\prime}$ induced by $v_{t}$. To ensure at least one edge can be updated from $\mathfrak{R}$ induced by $v_{t}$, once the number of neighboring $c_{i}$ where $f^{v_{t}}_{c_{i}}=1$ reaches $d_{v_{t}}-1$, all $f^{v_{t}}_{c_{i}}$ are reset to 0.

In summary, the proposed pool design can deliver a diverse edge update order by creating abundant different edges for every new edge pool, providing a chance for message exchange within and outside the trapping set. Moreover, the complexity of the proposed design can be lower than other sRBP-based decoders presented in Section 3 since only the C2V neighboring $v_{t}$, and check nodes where $f^{v_{t}}_{c_{i}}=0$ will be involved in the residual comparison. The design for $\mathfrak{R}$ and $\mathfrak{R}^{\prime}$ is shown in Proposed Edge pool design.

To predict a candidate error position that likely belongs to $\text{supp}(\mathbf{e})$ under the given syndrome $\mathbf{s}=H\cdot\mathbf{e}$, Proposition 1 is given to assist us in identifying the candidate more accurately.

The lower the value of $d_{v_{j}}-2w^{1}_{v_{j}}$ means the higher the ratio of the check nodes neighboring $v_{j}$ involving the given syndrome, which implies that the $j$th error position is likely belonging to $\text{supp}(\mathbf{e})$. Thus, we can obtain all candidate error positions by computing and sorting based on $d_{v_{j}}-2w^{1}_{v_{j}}$. A case is presented in Example 1.

Based on Proposition 1, we can build a sequence that reflects the possibility of errors belonging to $\text{supp}(\mathbf{e})$ for a given syndrome, where the most likely error in $\text{supp}(\mathbf{e})$ will occur at the beginning of this sequence, hereafter called the estimated support sequence. Since not every element in the support of an error pattern will exist in the first few positions in the estimated support sequence, we must carefully reduce the effect of an error position in the sequence individually. Suppose an error position belonging to the support is selected. In that case, we can obtain a new syndrome by reducing its corresponding syndrome position from the given syndrome, which might lead to the success of the sRBP. If a selected error is not in the support, the following position in the sequence will be considered for a new decoding process.

Now, we introduce our proposed algorithm. Denote $\lambda_{\max}$ as the maximum number of error positions that we want to select from the estimated support sequence. Each time we select an error position from the sequence for the decoder, it is referred to as a trial. The algorithm begins with the first position that we select, i.e., $\lambda=0$. For each trial we record the $N$-tuple standard error pattern $\mathbf{e}_{c}=(0,...0,1,0,...0)$, where only the $c$th position is $1$ and $c$ is the $\lambda$th element in the estimated support sequence. To reduce the impact of $\mathbf{e}_{c}$, we compute its corresponding syndrome $\mathbf{s}_{\mathbf{e}_{c}}=H\cdot\mathbf{e}_{c}$ and then compute the input syndrome for the decoder presented in Section 4.1 as $\mathbf{s}_{\mathbf{r}}=\mathbf{s}\oplus\mathbf{s}_{\mathbf{e}_{c}}$. The decoder for each trial will operate $I_{t}$ iterations; thus, the total maximum number of iterations $I_{\max}$ will become $I_{t}\cdot\lambda_{\max}$.

If the decoder converges to an estimated error pattern $\hat{\mathbf{e}}_{r}$, then terminate and output the final estimated error pattern as $\hat{\mathbf{e}}=\hat{\mathbf{e}}_{r}+\mathbf{e}_{c}$. If the decoder does not converge when the number of iterations reaches $I_{t}$, then move to the next position of the sequence until $\lambda_{\max}$. Otherwise, declare that the decoder has failed to converge. We conclude that the sRBP is equipped with a predict-and-reduce-error mechanism, referred to as PRE-sRBP, and the details are provided in Algorithm 1.

Fig. 2 shows the solvable ratio using PRE-sRBP where $\lambda_{\max}=15$ and $I_{t}=6$. In comparison to that shown in Fig. 1, the algorithm can solve error patterns with a weight of up to $11$, but the solvable ratio decreases to $88\%,50\%,$ and $17\%$ for weights $12,13$, and $14$, respectively.

The impact of trapping sets may be mitigated if a variable node involved in the trapping set is selected from the estimated support sequence. A scenario is demonstrated in Example 2 to show the effect of the selection on the decoder.

HP code is more severely impacted by the trapping set. As shown in Fig. 4, when using LMD-sRBP, the ratio for some high-weight error patterns improves, while for certain weights, it remains almost the same as when using sBP. Using PRE-sRBP, the solvable ratios for the collected error weight are all above $90\%$.

From Example 2, we can see that the selection of $\lambda_{\max}$ is important for the performance of PRE-sRBP. Apparently, a higher value of $\lambda_{\max}$ leads to a better performance until the upper bound $N$ is reached, as shown in Fig. 5.

However, error patterns where the decoder fails can waste a lot of decoding time. Considering the latency issue for practical applications, setting a large number for $\lambda_{\max}$ is impractical. Thus, we set an upper bound for $I_{\max}$ for simulations. This configuration provides a trade-off between $I_{t}$ and $\lambda_{\max}$ such that the proper $\lambda_{\max}$ will be determined.

For instance, considering the $[[256,32]]$ bicycle code at $p_{x}=0.02$, the frame-error rate (FER) versus the selection of $\lambda_{\max}$ is shown in Fig. 6, which shows that when $\lambda_{\max}\approx 10$, the FER begins to drop rapidly, consistent with the results where the solvable ratio of sRBP-based decoders begins to decline for error weights larger than 10. However, $\lambda_{\max}$ should not exceed 45 to ensure sufficient iterations $I_{t}$.

In each simulation, at least $100$ logical errors are collected, and the maximum iterations $I_{\max}=90$ for sBP and syndrome-based IDS decoders unless otherwise specified. In the simulations, sBP uses (3) for C2V updates, and the sLBP processes each check node sequentially.

Fig. 7 shows the FER performance versus the bit-flip crossover probability $p_{x}$ using different IDS decoders based on the $[[256,32]]$ bicycle code. The edge pool design significantly impacts performance. For example, NW-sRBP performs worse than sRBP and sLBP, contrary to the results for classical LDPC codes. When carefully designed for the edge pool, the performance using LMD-sRBP at $p_{x}=0.01$ reaches an FER of $7.4\times 10^{-6}$, which improves by almost an order compared to sLBP. By updating diverse edges and proactively reducing the predicted error position, PRE-sRBP where $\lambda_{\max}=15$, achieves the best performance among the considered IDS decoders.

We show the plot for FER versus the maximum number of iterations $I_{\max}$ in Fig. 8, which shows that sRBP can provide a faster convergence rate than sLBP at $p_{x}=0.02$. The figure also indicates that the elaborately designed edge pool can lead to massive improvements in the convergence rate. For example, since the edge neighboring the newest updated variable nodes is updated, LMD-sRBP provides the lowest error rate within three iterations. For PRE-sRBP, parameter $\lambda_{\max}$ is adjusted for different $I_{\max}$. The figure shows that PRE-sRBP not only provides a convergence rate on par with sRBP in the first few iterations but also the lowest frame-error rate performance after $I_{\max}=16$ where $\lambda_{\max}\geq 5$.

Fig. 9 shows the performance of the $[[126,28,8]]$ generalized bicycle code using different sRBP-based decoders. It shows that using edge-wise decoders can provide a better FER than sBP and sLBP. Whereas, the limitation of further improving performance by designing different edge pools is also reflected in the subtle performance gap between using sRBP, NW-sRBP, and LMD-sRBP. It is worth noting that the gap between our proposed decoders and LMD-sRBP for this code is larger than for the $[[256,32]]$ bicycle code, which indicates the significant impact of using additional predict-and-reduce-error mechanisms.

The structure of the hyper-graph product will lead to multiple quantum trapping sets, which can result in a performance limitation [8]. Fig. 10 shows that under $I_{\max}=90$, the performance of the $[[400,16,6]]$ HP code using sRBP, NW-sRBP, and LMD-sRBP is nearly identical. This implies that the influence of the edge pool design is negligible, and a more intense mechanism is needed for improvement. As a result, using the predict-and-reduce-error mechanism, PRE-sRBP can yield a significant performance gain compared to other decoders. In Fig. 10, all decoders have converged under $I_{\max}=90$, except the proposed PRE-sRBP.

Under sufficiently large iterations, say $I_{\max}=N$, the error rate using PRE-sRBP can be further improved. In Fig. 11, we compare the performance of the $[[400,16,6]]$ HP code using PRE-sRBP to other sBP-based decoders, including the posterior LLR adjustment method (Post-Adjust sBP) [35], sBP+OSD [10], and the sBP-guided decimation (sBPGD) [36]. The maximum number of iterations $I_{\max}$ is shown in the brackets, and $\lambda_{\max}$ is shown alongside it for PRE-sRBP. Post-Adjust sBP can improve the FER to $10^{-3}$ by flipping the posterior LLR of selected variable nodes at each iteration. sBP+OSD uses the soft output obtained from BP where $I_{\max}=N$ as the reliability auxiliary to search for possible error patterns, where the performance can be improved by increasing the search depth (order). Fig. 11 shows that sBP+OSD with a zero order (sBP+OSD-0) provides merely a slight performance gain from sBP. A relatively significant increase can be achieved using sBP+OSD with 60 orders by using a combination sweep method (sBP+OSD-CS) at the cost of additional complexity. sBPGD provides approximately an order of magnitude gain over sBP at the cost of $N$ rounds, each consisting of 400 iterations. Notably, our proposed PRE-sRBP under $I_{\max}=90$ where $\lambda_{\max}=15$ can outperform those considered decoders when $I_{\max}=400$. Furthermore, the performance can be improved where $I_{\max}=400$, and $\lambda_{\max}=50$, providing about two orders of magnitude improvement compared to sBP.

Consider a parity-check matrix whose Tanner graph consists of $M$ check nodes, $N$ variable nodes, and the total number of edges $E=M\cdot\bar{d}_{c}=N\cdot\bar{d}_{v}$, where $\bar{d}_{c}$ and $\bar{d}_{v}$ denote the average degree of the check nodes and the variable nodes, respectively. We evaluate the complexity in terms of the C2V message, the V2C message, the pre-computed C2V, and the residual comparison per iteration in Table 1. An iteration for sBP consists of updates to all C2V and V2C edges, i.e., an iteration includes $E$ C2V and V2C updates. For sRBP, an iteration is defined as when the number of C2V updates reaches $E$ due to the unbalanced update distribution specified in Section 3.2.

In Table 1, it is shown that both sBP and sLBP have the same number of updates without any pre-computation or comparison. For all sRBP-based decoders, the number of V2C updates and pre-computations are the same since these operations occur in S.2. When a C2V edge is updated, each V2C from $v_{\max}$ (or $v_{k}$ for NW-sRBP) is then updated except for $c_{\max}$. Thus, there are $\bar{d}_{v}-1$ V2C updates. Additionally, the new C2V is computed from each check node neighboring $v_{\max}$, except for $c_{\max}$, to its neighboring variable nodes except for $v_{\max}$ (or $v_{k}$ for NW-sRBP), leading to a total pre-computation of $(\bar{d}_{c}-1)(\bar{d}_{v}-1)$.

The difference lies in the residual comparison due to different edge pools $\mathfrak{R}$ in S.1 and S.3. For sRBP to determine the C2V update, $\mathfrak{R}$ contains all the check and variable nodes; thus, $E-1$ comparisons are required. For the NW-sRBP, after $E-1$ comparisons, there are $\bar{d}_{c}$ edges updated from check node $c_{\max}$, i.e., there are $\frac{E-1}{\bar{d}_{c}}$ comparisons for one C2V update. For one iteration, the comparison is $E\cdot\frac{E-1}{\bar{d}_{c}}=M(E-1)$. In LMD-sRBP, the number of comparisons can be computed in two steps following the method of constructing $\mathfrak{R}_{I}$ and $\mathfrak{R}$. There are $(\bar{d}_{v}-1)(\bar{d}_{c}-1)-1$ comparisons to determine the $v^{*}_{\max}$ and $\bar{d}_{v}-1$ to determine the $c^{*}_{\max}$ neighboring $v^{*}_{\max}$. Thus, the total comparisons for one C2V update is $(\bar{d}_{v}-1)\bar{d}_{c}-1$. PRE-sRBP will contain a sequence computation process and the sRBP-based process. In the sRBP-based process, for one C2V update, PRE-sRBP will only compare messages from check nodes neighboring the variable node $v_{t}$ and those that have not been updated to their neighboring variable nodes excluding $v_{j}$, resulting in a comparison below $\bar{d}_{v}(\bar{d}_{c}-1)-1$.