# Stabilizer Inactivation for Message-Passing Decoding of Quantum LDPC Codes

Julien Du Crest, Mehdi Mhalla, Valentin Savin

► To cite this version:

Julien Du Crest, Mehdi Mhalla, Valentin Savin. Stabilizer Inactivation for Message-Passing Decoding of Quantum LDPC Codes. 2022 IEEE Information Theory Workshop (ITW), Nov 2022, Mumbai, France. IEEE, pp.488-493, 2023, 10.1109/itw54588.2022.9965902 . hal-04993679

HAL Id: hal-04993679

https://hal.science/hal-04993679v1

Submitted on 17 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Stabilizer Inactivation for Message-Passing Decoding of Quantum LDPC Codes

Julien Du Crest¹, Mehdi Mhalla², Valentin Savin³

¹ Univ. Grenoble Alpes, Grenoble INP, LIG, F-38000 Grenoble, France

² Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG, F-38000 Grenoble, France

³ Univ. Grenoble Alpes, CEA-Léti, F-38054 Grenoble, France

julien.du-crest@univ-grenoble-alpes.fr, mehdi.mhalla@univ-grenoble-alpes.fr, valentin.savin@cea.fr

March 15, 2023

## Abstract

We propose a post-processing method for message-passing (MP) decoding of CSS quantum LDPC codes, called stabilizer-inactivation (SI). It relies on inactivating a set of qubits, supporting a check in the dual code, and then running the MP decoding again. This allows MP decoding to converge outside the inactivated set of qubits, while the error on these is determined by solving a small, constant size, linear system. Compared to the state of the art post-processing method based on ordered statistics decoding (OSD), we show through numerical simulations that MP-SI outperforms MP-OSD for different quantum LDPC code constructions, different MP decoding algorithms, and different MP scheduling strategies, while having a significantly reduced complexity. We also provide numerical evidence that SI post-processing may achieve a threshold on a family of generalized bicycle codes, of length varying from 126 to 8190 qubits.

## 1 Introduction

In a well-celebrated work [1], Gallager introduced the family of low-density parity-check (LDPC) codes, which became a staple of classical error correction over the past twenty years. They came equipped with iterative message-passing (MP) decoders, which is indisputably
the main reason of their success: Not only MP decoders represented a low-complexity decoding approach (linear complexity per decoding iteration), but it was later shown that LDPC codes can be optimized, so that their error correction thresholds under MP decoding closely approach the theoretical Shannon limit [2, 3].

The quantum counterparts of LDPC codes, referred to as qLDPC codes, are Calderbank-Shor-Steane (CSS) quantum codes, defined by two orthogonal classical LDPC codes. qLDPC codes are likely to be the first practical codes used for fault-tolerant quantum computing [4], as they have low weight stabilizer group generators, which makes it possible to extract the error syndrome in a fault tolerant way. Moreover, the qLDPC family has been recently shown to yield good asymptotic codes, with linear minimum distance and constant rate [5, 6]. This augurs for practical constructions with increased error correction capacity, or reduced qubit overhead.

However, if decoding a qLDPC code boils down to decoding the two constituent classical LDPC codes (assuming separate decoding of *X* and *Z* errors), their orthogonality translates into a so-called degeneracy property, which causes a significant degradation of the MP decoding performance [7]. Thus, decoding solutions are usually devised on a case-by-case basis, being distinguished by their scope and extent. Heuristic techniques to partially overcome the degeneracy of qLDPC codes have been proposed in [7]. Reweighted belief-propagation decoding has also been proposed in [8] (and references therein), and more recently, neural belief-propagation decoding has been proposed in [9]. For hypergraph-product LDPC and quantum expander codes, a linear-time decoding algorithm has been proposed in [10, 11], decoding up to a constant fraction of the minimum distance, by exploiting the expanding properties of the LDPC code. Recently, Panteleev et Kalachev proposed a new decoding approach, combining MP with an ordered statistics decoding (OSD) post-processing step [12]. It stands currently as the most efficient decoding solution applying generally across a large spectrum of qLDPC codes [13]. (Since the first version of this paper, linear time decoders for linear minimum distance qLDPC codes, decoding adversarial errors of linear weight, have been proposed in [14–16]).

Here, we continue the idea of a general purpose decoder, in which MP decoding is combined with a post-processing step. We call our post-processing step *stabilizer inactivation (SI)*. Assuming we are decoding for some type of errors, say *X*-errors, the idea of the SI post-processing step is to *inactivate* the qubits in the support of some *X*-check<fnref n="1" />, and then run the MP decoding again. Inactivating these qubits means that we take them out from

<footnote n="1">¹A *check* is a generator of the stabilizer group, corresponding to a row of the check matrix. Note that *Z*-checks are used to decode *X*-errors.</footnote>
the MP decoding process (which happens if we set to zero the corresponding log-likelihood
ratio values, input to the MP decoder). If the inactivated X-check<fnref n="2" /> is carefully chosen, the
MP decoding converges outside its support. All that remains is to determine the error on
the support of the inactivated X-check, which amounts to solving a small linear system.
We show that the MP-SI outperforms the MP-OSD decoder for different qLDPC code con-
structions, different MP decoding algorithms, and different MP scheduling strategies, while
having a significantly reduced complexity.

2 Preliminaries

2.1 qLDPC Codes

qLDPC codes are CSS quantum codes, defined by two classical LDPC codes with parity
check matrices $H_X$ and $H_Z$, such that $H_X H_Z^\top = 0$. The rows of $H_X$ and $H_Z$ are referred to
as X-checks and Z-checks, respectively, and they generate the X-type and Z-type stabilizer
groups, namely $im\,H_X^\top$ and $im\,H_Z^\top$. Here and henceforth, an element $g$ of the stabilizer
group is identified to the binary vector indicating the qubits acted on non-trivially by $g$.
For a code of length $n$ qubits, $H_X$ and $H_Z$ have $n$ columns, while the number of encoded
logical qubits is given by $k = n - \text{rank}(H_X) - \text{rank}(H_Z) = \dim (\ker H_X / \text{im } H_Z^\top) =$
$\dim (\ker H_Z / \text{im } H_X^\top)$.

The condition $H_X H_Z^\top = 0$ implies that any $Z$-check is a codeword of $C_X = \ker H_X$, and any $X$-check is a codeword of $C_Z = \ker H_Z$. Hence, $C_X$ and $C_Z$ have poor classical minimum distance, equal to $\mathcal{O}(1)$ as a function of $n$. However, since the elements of the stabilizer group act trivially on any code state, the quantum minimum distance is defined as $d = \min(d_X, d_Z)$, where $d_X = \min\{|v|, v \in \ker H_X \setminus \text{im } H_Z^\top\}$, and similarly, $d_Z = \min\{|v|, v \in \ker H_Z \setminus \text{im } H_X^\top\}$, and $|v|$ denotes the weight (number of 1's) of the binary vector $v$. As a function of $n$, the quantum minimum distance of qLDPC codes varies from $d = \mathcal{O}(\sqrt{n})$ for the hypergraph-product (HP) construction proposed in [17] to $d = \mathcal{O}(n)$ for the lifted-product (LP) construction over non-abelian groups in [5]. Other constructions of qLDPC codes, with minimum distance in between the above bounds, have also been recently proposed in the literature [18–20].

<footnote n="2">²By a slight abuse of language, we shall sometimes say that the *X*-check is inactivated (instead of the qubits in its support).</footnote>
## 2.2 Pauli Errors and Decoding

We assume that encoded qubits are affected by Pauli errors, where each qubit is indepen-
dently acted on by a Pauli $I, X, Y, Z$ error, with probability $p_I, p_X, p_Y, p_Z$. The total error
probability is denoted by $p = 1 - p_I = p_X + p_Y + p_Z$. Since $Y = iXZ$, we only need to
correct for $X$ and $Z$ errors. For simplicity, we shall assume that $X$ and $Z$ errors are decoded
independently<fnref n="3" />, in which case the $X$-error channel model is a classical binary symmetric
channel (BSC), with error probability $\varepsilon_X = p_X + p_Y$, and the $Z$-error channel model is a
BSC, with error probability $\varepsilon_Z = p_Z + p_Y$.

In the sequel, we shall only discuss the case of $X$-errors, since a similar discussion applies
to $Z$-errors. We also identify an $X$-error to a binary vector $e_X$ of length $n$, where $1$ entries
indicate the qubits on which an $X$ error occurred. The error $e_X$ produces a syndrome
$s_X := H_Z e_X$, which can be observed by measuring the $Z$-checks of the qLDPC code (here,
we shall assume that the syndrome measurement is fault free).

The task of the decoder is to determine an estimate $\hat{e}_X$ of the error $e_X$, given the
observed syndrome $s_X$. Note that the same syndrome would have been produced by any
other error $e'_X$, such that $e'_X + e_X \in \ker H_Z$. Decoding is successful if $\hat{e}_X + e_X \in \text{im } H_X^\top$,
that is, the estimate and the true error differ by an element of the $X$-type stabilizer group.
Indeed, such a mismatch is not problematic, since elements of $\text{im } H_X^\top$ acts trivially on any
code state. Elements of $\text{im } H_X^\top$ are sometimes referred to as *degenerate errors* [7], since
they need not (and actually cannot) be corrected. By definition, a qLDPC code has many
low-weight degenerate errors (any $X$-check is a degenerate error).

## 2.3 MP Decoders

We adopt the terminology related to the bipartite (Tanner) graph representation of classical
LDPC codes [21]. The bipartite graph has vertices referred to as bit-nodes and check-nodes,
and its adjacency matrix is given by the parity check matrix of the code. An MP decoder
is an iterative decoding algorithm exchanging extrinsic messages along the edges of the
bipartite graph, which can be described as follows [22]:

(i) The input consists of the observed syndrome $s_X$, as well as an *a priori soft information* for each bit-node, usually given in the form of an log-likelihood ratio (LLR) value. Assuming the BSC model from the previous section, the *a priori* LLR is the same for all bit-nodes

<footnote n="3">³Alternatively, one may decode first one type of error, say the *X*-error, then decode the *Z*-error conditional on the decoded *X*-error, in which case the *Z*-error channel model becomes a mixture of two BSCs.</footnote>
$i = 1, \dots, n$, and given by

$$ \gamma_i := \log \frac{\Pr(E_X(i) = 0)}{\Pr(E_X(i) = 1)} = \log \frac{1 - \varepsilon_X}{\varepsilon_X}, \qquad (1) $$

where the unknown error $e_X$ is seen as a realization of a random variable, denoted here and in the sequel by $E_X$.

(ii) Extrinsic messages are exchanged between bit-nodes and check-nodes, in several rounds, also referred to as decoding iterations. At each iteration, an updated soft information (posterior LLR<fnref n="4" />) value $\tilde{\gamma}_i$ is computed for each each bit-node $i = 1, \dots, n$, based on which an error estimate is made:

$$ \hat{e}_X(i) = 0, \text{ if } \tilde{\gamma}_i \ge 0, \text{ and } \hat{e}_X(i) = 1, \text{ otherwise} \qquad (2) $$

(iii) Decoder stops if either $H_Z \hat{e}_X = s_X$, or a maximum (predetermined) number of decoding iterations is reached. It outputs the current error estimate $\hat{e}_X$ (hard decision), and possibly the corresponding soft information values (soft decision).

One may distinguish different MP decoding algorithms, the most well-known being the Sum-Product (SP, also known as Belief-Propagation<fnref n="5" />, BP [23]) and the Min-Sum (MS) algorithms. On cycle free graphs, SP implements maximum a posteriori (MAP) decoding, while MS implements maximum-likelihood (ML) decoding. For graphs with cycles, computation trees provide a way to describe SP and MS decoders as an either MAP or ML decision process on a cycle-free graph [24]. Compared to SP, MS may present several practical advantages: it has a lower computational complexity (only requires additions and comparisons), and under the BSC model assumption, it does not need an a priori knowledge of the channel error probability $\varepsilon_X$. Hence, for the MS decoder, the a priori input LLRs can be initialized to any constant value, $\gamma_i = \gamma, \forall i = 1, \dots, n$, without modifying the decoder output. However, to avoid computation instability issues, $\gamma = 1$ should be used<fnref n="6" />.

MP decoders may use different scheduling strategies, determining the order in which bit-node and check-node messages are updated. The conventional assumption is that at

<footnote n="4">⁴We use (updated) “soft information” rather than “posterior LLR”, since the later conveys a Bayesian inference meaning, which is only exact for the Sum-Product decoding on acyclic graphs, as explained later in the text.</footnote>

<footnote n="5">⁵Many authors confuse BP with the general MP principle. We shall use SP terminology in this paper to avoid any possible confusion.</footnote>

<footnote n="6">⁶We warn the reader that computation instability may actually improve the MS decoding performance, depending on the $\gamma$ value, and this even for double-precision floating-point (64 bits) implementations. While for classical LDPC codes this impact is usually negligible, for qLDPC codes we have observed significant differences. We believe this is due to phenomena related to the code degeneracy. See also the random perturbation technique in [7].</footnote>
each iteration, all bit-nodes and subsequently all check-nodes pass new messages to their neighbors, which is known as parallel or flooding scheduling. A different approach, known as serial scheduling, is to process check-nodes sequentially<sup>7</sup>, with an immediate propagation of their messages to the neighbor bit-nodes. The main advantage of the serial schedule is that it propagates information faster and converges in about half the number of iterations compared to the flooding schedule [25]. The serial scheduling can be also partly parallelized, by processing sequentially layers (groups) of check-nodes, while processing in parallel check-nodes within the same layer. This scheduling technique is known as layered scheduling. In case that any bit-node is connected at most once to each check-node layer, serial and layered scheduling exhibit *strictly the same* decoding performance and convergence speed. The choice of a scheduling strategy is usually related to a specific decoder architecture implemented in hardware. Partly parallel architecture implementing a layered scheduling are widely used in practical implementations [26], but ultra-high throughput hardware implementations are based on unrolled fully-parallel architectures [27], implementing a flooding scheduling.

## 2.4 OSD Post-Processing

The MP-OSD decoder proposed in [12] combines MP decoding with an OSD post-processing step, in case the former fails to find a hard decision estimate $\hat{e}_X$ satisfying the given syndrome $s_X$. The post-processing step utilizes the soft decision outputted by the MP decoder. In its most basic form (OSD-0), bit-nodes are sorted according to their reliability (that is, absolute value of the corresponding soft decision), and a number of rank $H_Z$ least reliable bit-nodes are determined, such that the corresponding columns of $H_Z$ are linearly independent. The hard decision estimates of these bit-nodes are discarded, and they are then re-estimated by solving the linear system determined by the corresponding columns (for the remaining, more reliable bit-nodes, the hard decision estimates outputted by the MP decoder are kept). Hence, OSD always outputs a valid solution $\hat{e}_X$ of the system $H_Z e_X = s_X$. In [12], MP-OSD has been shown to produce effective results, when the MP decoder is a normalized version of the MS (NMS) using a serial scheduling.

<footnote n="7">⁷We discuss here *horizontal* scheduling strategies, applying to check-nodes. Similar *vertical* scheduling strategies apply to bit-nodes.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: Probability distribution of rank($r_X$) values.</figcaption></figure>

# 3 Stabilizer Inactivation Post-Processing

In the following, we will only discuss the correction of $X$ errors, but similar arguments apply to $Z$-errors.

## 3.1 Stabilizer-Splitting Errors

Let $e_X$ be an $X$-error, and $s_X = H_Z e_X$ the corresponding syndrome. We discuss in this section the case where $e_X$ divides the support of some $X$-check $r_X$ in two equal parts, that is, $X$ errors occur on exactly half of the qubits checked by $r_X$. For $e'_X := e_X + r_X$, we have $H_Z e'_X = s_X$ and $|e'_X| = |e_X|$. Hence, $e'_X$ and $e_X$ are errors of the same weight, differing on only $|r_Z|$ qubits, and which are valid (and equivalent) corrections of the syndrome. We refer to such an error as a stabilizer-splitting error (see also the example in [7, Fig. 2] and the symmetric stabilizer trapping sets defined in [28] for a more in-depth comprehension of the phenomenon). If an MP decoder is run with input syndrome $s_X$, it is drawn by $e'_X$ and $e_X$ in two different directions, with similar intensity. This may cause the MP decoder getting lost, while trying to find its way to a valid correction of the syndrome.

Let $(\tilde{\gamma}_i)_i$ be the output soft information of the MP decoder, and $\hat{e}_X$ be the corresponding hard decision estimate (Eq. (2)). We define

$$ \delta(e_X, e'_X) := \sum_{i \in \text{supp}(\hat{e}_X + e_X)} |\tilde{\gamma}_i| - \sum_{i \in \text{supp}(\hat{e}_X + e'_X)} |\tilde{\gamma}_i|. \qquad (3) $$

Since flipping a hard-decision estimate value requires the corresponding soft information
to change its sign, the two sums in Eq. (3) indicate the necessary change in the soft information, so that the corresponding hard decision estimate moves from $\hat{e}_X$ to either $e_X$ (left sum), or $e'_X$ (right sum). In case the MP decoder fails, that is $H_Z\hat{e}_X \neq s_X$, we expect that this is due to the decoder being attracted to a similar degree towards both $e_X$ and $e'_X$ ("lost in-between" behavior). Put differently, we expect the $\delta(e_X, e'_X)$ value to be small.

Using $|\tilde{\gamma}_i| = (-1)^{\hat{e}_X(i)}\tilde{\gamma}_i$ and $e'_X = e_X + r_X$, one can easily verify that $\delta(e_X, e'_X)$ rewrites as $\delta(e_X, e'_X) = \sum_{i \in \text{supp}(e_X)} \tilde{\gamma}_i - \sum_{i \in \text{supp}(e'_X)} \tilde{\gamma}_i = \sum_{i \in \text{supp}(r_X)} (-1)^{e'_X(i)}\tilde{\gamma}_i$, and therefore,

$$|\delta(e_X, e'_X)| \le \tilde{\gamma}(r_X) := \sum_{i \in \text{supp}(r_X)} |\tilde{\gamma}_i| \quad (4)$$

We refer to $\tilde{\gamma}(r_X)$ as the reliability of the X-check $r_X$. Hence, we may use X-check reliability values to determine which X-checks are possibly responsible of a "lost in-between" behavior. To illustrate this, let us define

$$\text{rank}(r_X) := |\{r'_X | \tilde{\gamma}(r'_X) < \tilde{\gamma}(r_X)\}|. \quad (5)$$

We generate random errors $e_X$, where each error divides the support of a random X-check $r_X$ in two equal parts, and compute the rank($r_X$) values. Fig. 1 shows the estimated probability distribution (histogram format) of rank($r_X$) values. We consider the lifted product code B1[882, 24] from [12], decoded by the SP algorithm, with both flooded and serial schedulings (we use 50 decoding iterations for serial scheduling, and 100 decoding iterations for flooded scheduling). We assume a depolarizing channel with $p_X = p_Y = p_Z = p/3$, where $p = 0.1$ or $p = 0.06$, giving $\varepsilon_X = 0.0667$ or $\varepsilon_X = 0.04$ (Section 2.2). As expected, it can be observed that the rank($r_X$) value is small with high probability (the width of histogram bins is equal to 5).

## 3.2 SI Post-Processing

We consider the situation where the MP decoder fails to find a hard decision estimate $\hat{e}_X$ satisfying the given syndrome $s_X$. The idea of the SI post-processing (Algorithm 1) is to inactivate the qubits in the support of the less reliable X-checks. By a slight abuse of language we shall say that we inactivate the X-check itself (rather than its support). We start by inactivating the least reliable X-check, and let this be $r_X$. This means that we discard the qubits checked by $r_X$ from the MP decoding process. Precisely, let

$$H_Z = \begin{bmatrix} H_{Z|r_X} & A \\ 0 & H_{Z|\bar{r}_X} \end{bmatrix}, \quad (6)$$
where $H_{Z|r_X}$ is the submatrix determined by the columns corresponding to the qubits in $\text{supp}(r_X)$, and the rows having at least one non-zero entry in any one of these columns<fnref n="8" /> (for the sake of illustration, in (6) we assumed that $H_{Z|r_X}$ is a leading submatrix). Then we rerun MP decoding on the matrix $H_{Z|\bar{r}_X}$, with input syndrome $s_{X|\bar{r}_X} = [0 \ H_{Z|\bar{r}_X}]e_X$ (that is, syndrome $s_X$ is restricted to the rows of the $H_{Z|\bar{r}_X}$ submatrix only). If MP decoding succeeds, it provides an estimate $\hat{e}_{X|\bar{r}_X}$ of the error outside $\text{supp}(r_X)$. To estimate the error on $\text{supp}(r_X)$, we solve the linear system $H_{Z|r_X}e_{X|r_X} = s_{X|r_X} + A\hat{e}_{X|\bar{r}_X}$. If the system has a solution<fnref n="9" />, say $\hat{e}_{X|r_X}$, the decoding process stops and outputs $\hat{e}_X := (\hat{e}_{X|r_X}, \hat{e}_{X|\bar{r}_X})$. In case that either the system has no solution, or the MP decoding fails, SI post-processing continues by inactivating the next least reliable X-check, until a maximum (fixed) number of X-check inactivations, denoted by $\lambda_{\max}$, is reached.

Two observations are in place here: (i) X-check reliability values are computed only once, after the initial MP decoding attempt (run on the whole $H_Z$ matrix). (ii) X-checks are sorted in increasing order of reliability, and inactivated, one at a time, in this order. In our experiments, run on qLDPC codes of length less than 2000 qubits, inactivating several X-checks at the same time did not improve the decoding performance.

Finally, as mentioned above, the following two situations may occur, causing SI post-processing to continue: (i) the MP decoder does not converge to a solution on the reduced matrix $H_{Z|\bar{r}_X}$, or (ii) it does converge, but the system on the remaining qubits cannot be solved. The first kind of error typically happens when the inactivated X-check was not one that implied the failure in the first place (initial MP decoding attempt on the full $H_Z$ matrix). The second kind of error happens when the MP decoding converged to a wrong solution on the reduced matrix $H_{Z|\bar{r}_X}$. This may happen when some of the active qubits become “dead ends” (degree 1 is the reduced matrix $H_{Z|\bar{r}_X}$), thus “absorbing” the error around the Z-checks they are connected to.

## 3.3 Complexity

The SI[$\lambda_{\max}$] post-processing step has worst-case complexity $O(\lambda_{\max}n \log n)$, where $\lambda_{\max}$ is the maximum number of inactivated X-checks and $O(n \log n)$ is the complexity of the MP decoding (assuming the number of decoding iterations increases as $\log n$ [22]). Solving the linear system in the SI post-processing step has constant complexity, since the size of the system does not exceed the maximum X-check weight. In case $\lambda_{\max}$ is not a constant,

<footnote n="8">⁸Note that $r_X \in \ker H_Z$, hence any row of $H_Z$ has an even number ($\ge 0$) of non-zero entries in the columns corresponding to $\text{supp}(r_X)$.</footnote>

<footnote n="9">⁹Note that the system will have at least two solutions. We pick any of them.</footnote>
<caption>**Algorithm 1:** X-error SI[$\lambda_{max}$] post-processing</caption>

```
    ê_X ← MP(H_Z, s_X)
    if H_Zê_X = s_X then
        Return ê_X
    else
        Compute X-check reliability values
        û(r_X) = Σ_{i∈supp(r_X)} |û_i|, ∀r_X
        Sort X-checks in increasing order of reliability
        for 1 ≤ λ ≤ λ_{max} do
            r_X ← next least reliable X-check
            ê_{X|r_X} ← MP(H_Z|r_X, s_X|r_X)
            if H_Z|r_X X ê_{X|r_X} ≠ s_X|r_X then
                Continue
            else
                Solve H_Z|r_X e_{X|r_X} = s_X|r_X + Aê_{X|r_X}
                if the system has a solution ê_{X|r_X} then
                    Return ê_X := (ê_{X|r_X}, ê_{X|r_X})
                else
                    Continue
    Return decoding failure
```

but scales linearly with $n$, the worst-case complexity becomes $O(n^2 \log n)$. In any case, the average-case complexity is $O(\lambda_{ave} n \log n)$, where $\lambda_{ave}$ is the average number of inactivated X-checks during SI post-processing.

The OSD-0 post-processing needs to solve a linear system, whose size scales linearly with $n$. Thus, its complexity is at most $O(n^3)$. The best algorithm to solve a general system of linear equations has complexity $O(n^{2.38})$ [29], although it is of little practical use (except for extremely large systems).
# 4 Numerical Results

## 4.1 Logical Error Rate Performance

In Fig. 2, we provide numerical results for the codes B1[881, 24, ≤ 24] and C2[1922, 50, 16] from [12]. The first is a lifted product code, and the second a hypergraph-product code. We note that for both B1 and C2 codes, the constituent classical LDPC codes have column weight at least 3, and no cycles of length 4. These characteristics are well suited to the proposed SI post-processing method, since except for the resolution of a small, constant size, linear system, it entirely relies on MP decoding.

We consider the depolarizing channel, with physical error rate $p$ (shown on the abscissa), and $p_X = p_y = p_Z = p/3$. Fig. 2 shows the logical-X error rate, for three different MP algorithms, and two different schedulings, using either SI or OSD-0 post-processing. It can be observed that SI[$\lambda_{max}$ = 10] significantly outperforms the OSD-0 post-processing<sup>10</sup> in case of either MS or SP decoding, for both scheduling strategies. For NMS decoding<sup>11</sup>, the performance of SI[$\lambda_{max}$ = 10] is only slightly better than that of OSD-0, but comes however at the cost of a significantly reduced complexity.

The SI[all] curves in Fig. 2 correspond to the case when the $\lambda_{max}$ value is set to the total number of X-checks (number of rows of $H_X$), thus providing the best achievable performance by the proposed SI post-processing. (We note that for the code B1, the SI[all] performance is slightly better using serial scheduling than using flooding scheduling, while the opposite occurs for the code C2 – not shown in the figure). Finally, in order to evaluate the average-case complexity, we also show in Fig. 2 the $\lambda_{ave}$ values for the SI[all] post-processing, in the lower part of the waterfall region (logical error rates less than $10^{-3}$). In order to avoid a bias due to MP decoding performance, the average is computed only over the cases when the SI post-processing is used (MP decoding failed), thus $1 \le \lambda_{ave} \le \lambda_{max}$. It can be seen that $\le \lambda_{ave}$ approaches 1 for low error probabilities, giving an average-case complexity slightly higher than the MP decoding complexity.

<footnote n="10"><sup>10</sup>We note that we perform OSD-0 post-processing on binary MP decoding (of X-errors), which explains the slight shift of the curves with respect to [12], where non-binary MP decoding (of both X and Z errors) is performed.</footnote>

<footnote n="11"><sup>11</sup>For the NMS decoding, the normalization factor is chosen so as to ensure the best performance of the corresponding post-processing step. NMS-OSD exhibits very good performance using normalization factor 0.625 (the same normalisation factor was used in [12], for non-binary NMS decoding). However, its performance would have been severely degraded, if the normalization factor had been set to 0.9. Conversely, NMS-SI performs well when the normalization factor is set to 0.9, but rather poor when it is set to 0.625.</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 2: Comparison of SI and OSD on B1[882, 24, ≤ 24] code (left) and C2[1922, 50, 16] code (right) with MS (top), NMS (middle) and SP (bottom) decoders and flooded ('F', circle markers) and serial ('S', square markers) scheduling. OSD post-processing is of order 0. For NMS, we use normalization factor 0.625 for OSD (following [12]) and 0.9 for SI. All MP decoders use 50 decoding iterations for serial scheduling, and 100 decoding iterations for flooded scheduling.</figcaption></figure>
## 4.2 Threshold

In Fig. 3, we provide numerical evidence that SI can achieve a threshold for a family of generalized bicycle codes<fnref n="12" /> proposed in [12, Appendix C, Fig. 9]. Generalized bicycle codes (first studied in [30]) are constructed by using two commuting square matrices $A$ and $B$, with $H_X = [A, B]$, $H_Z = [B^T, A^T]$. For the family of codes considered here, $A$ and $B$ are circulant matrices, thus they commute, and code parameters are given by $[[n, k]] = [[2^{s+1} - 2, 2s]]$, for $s = 6, 7, 8, 9, 12$.

We estimate the threshold under MP decoding, with both SI and OSD post-processing, for the depolarizing channel (same channel model as before). For a fair comparison between SI and OSD, we use NMS with appropriate normalization factors. The scheduling chosen is serial, as it allows faster convergence and better results in most cases.

For the SI post-processing, we choose $\lambda_{max} = 10$ for the code of length 1022 qubits, representing 2% of the number of $X$-checks, denoted by $m_X$. Note that $m_X = (n-k)/2$. Then, we keep the same ratio between the maximum number of inactivated $X$-checks, and the total number of $X$-checks, that is, we consider $\lambda_{max} = 0.02 m_X$, for the five simulated codes<fnref n="13" />. Since $m_X \approx n/2$, the worst case complexity of the MP-SI decoder scales as $0.01n^2 \log(n)$. However, we note that the average case complexity approaches $O(n \log n)$ in the low error rate region (that is, $\lambda_{ave}$ approaches 1 for low error probabilities, similar to the observation made in Section 4.1).

The threshold given by SI is around 13%, while the one of OSD-0 is only 12%. Apart from the numerical results, the computational advantage of SI becomes clear for codes above a thousand qubits. The observed threshold phenomenon shows that the SI post-processing scales well with longer codes, in spite of the fact that it inactivates only one check at a time, and the inactivation is tested for quite a small (2%) fraction of checks.

## 5 Conclusion and Perspectives

The degeneracy of qLPDC codes is the main reason for the inefficiency of MP decoders. To cope with this phenomenon, the SI post-processing method inactivates a set of qubits, supporting a check in the dual code. Except for the resolution of a small, constant size, linear system, the proposed MP-SI approach entirely relies on MP decoding. Its low complexity and compatibility with various MP decoding algorithms and scheduling strategies make it an

<footnote n="12">¹²These codes can be found in the alist format at https://gricad gitlab.univ-grenoble-alpes.fr/ducrestj/qldpc-codes</footnote>

<footnote n="13">¹³Precisely, $\lambda_{max} = 2, 3, 5, 10, 82$, for code length $n = 126, 254, 510, 1022, 8190$, respectively.</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 3: Threshold for SI[$\lambda_{max} = 0.02 m_X$] and OSD-0 on a family of generalized bicycle codes with NMS and serial scheduling. For NMS, we use normalization factor 0.625 for OSD (following [12]) and 0.9 for SI. All MP decoders use serial scheduling with at most 100 decoding iterations.</figcaption></figure>

attractive and practical decoding solution. Our numerical simulations showed that MP-SI provides effective results, especially when the constituent classical LDPC codes have column weight at least 3, and no cycles of length 4. We have also shown that SI post-processing can achieve a threshold on a family of generalized bicycle codes, outperforming the one achieved by OSD.

Finally, we note that in this work we considered binary MP decoding algorithms, where $X$ and $Z$ errors are decoded separately. While correlation between $X$ and $Z$ errors can still be taken into account by binary decoding (e.g., by initializing the $Z$-error decoding conditional on the output of the $X$-error decoding), a more effective approach to deal with correlated errors consists of the use non-binary decoding. Since the state of the art for correlated Pauli errors remains the non-binary NMS decoder with OSD post-processing [12], it would be interesting to generalize the proposed SI post-processing to the non-binary case.

## Acknowledgment

This work was supported by the QuantERA grant EQUIP, by the French Agence Nationale de la Recherche, ANR-22-QUA2-0005-01, and by the Plan France 2030 through the project ANR-22-PETQ-0006.
References

[1] R. G. Gallager, "Low-density parity-check codes," *IRE Trans. on Information Theory*, vol. 8, no. 1, pp. 21–28, 1962.

[2] T. J. Richardson and R. L. Urbanke, "The capacity of low-density parity-check codes under message-passing decoding," *IEEE Trans. on Inf. Theory*, vol. 47, no. 2, pp. 599–618, 2001.

[3] T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke, "Design of capacity-approaching irregular low-density parity-check codes," *IEEE Trans. on Information Theory*, vol. 47, no. 2, pp. 619–637, 2001.

[4] D. Gottesman, "Fault-tolerant quantum computation with constant overhead," *Quantum Information & Computation*, vol. 14, no. 15-16, pp. 1338–1372, 2014.

[5] P. Panteleev and G. Kalachev, "Asymptotically good quantum and locally testable classical LDPC codes," arXiv:2111.03654, 2021.

[6] A. Leverrier and G. Zémor, "Quantum Tanner codes," arXiv:2202.13641, 2022.

[7] D. Poulin and Y. Chung, "On the iterative decoding of sparse quantum codes," *Quantum Information and Computation*, vol. 8, no. 10, pp. 987–1000, 2008.

[8] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo, "Fifteen years of quantum ldpc coding and improved decoding strategies," *IEEE Access*, vol. 3, pp. 2492–2519, 2015.

[9] Y.-H. Liu and D. Poulin, "Neural belief-propagation decoders for quantum error-correcting codes," *Physical review letters*, vol. 122, no. 20, p. 200501, 2019.

[10] A. Leverrier, J.-P. Tillich, and G. Zémor, "Quantum expander codes," in *IEEE Annual Symposium on Foundations of Computer Science*. IEEE, 2015, pp. 810–824.

[11] O. Fawzi, A. Grospellier, and A. Leverrier, "Efficient decoding of random errors for quantum expander codes," in *Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing*, 2018, pp. 521–534.

[12] P. Panteleev and G. Kalachev, "Degenerate quantum LDPC codes with good finite length performance," *Quantum*, vol. 5, p. 585, 2021, arXiv:1904.02703.
[13] J. Roffe, D. R. White, S. Burton, and E. Campbell, "Decoding across the quantum low-density parity-check code landscape," *Physical Review Research*, vol. 2, no. 4, p. 043423, 2020, arXiv:2005.07016.

[14] S. Gu, C. A. Pattison, and E. Tang, "An efficient decoder for a linear distance quantum ldpc code," *arXiv preprint arXiv:2206.06557*, 2022.

[15] A. Leverrier and G. Zémor, "Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes," *arXiv preprint arXiv:2206.07571*, 2022.

[16] I. Dinur, M.-H. Hsieh, T.-C. Lin, and T. Vidick, "Good quantum ldpc codes with linear time decoders," *arXiv preprint arXiv:2206.07750*, 2022.

[17] J.-P. Tillich and G. Zémor, "Quantum ldpc codes with positive rate and minimum distance proportional to the square root of the blocklength," *IEEE Transactions on Information Theory*, vol. 60, no. 2, pp. 1193-1202, 2013, arXiv:0903.0566.

[18] M. B. Hastings, J. Haah, and R. O'Donnell, "Fiber bundle codes: Breaking the $N^{1/2}$ polylog($N$) barrier for quantum LDPC codes," *arXiv:2009.03921*, 2020.

[19] P. Panteleev and G. Kalachev, "Quantum LDPC codes with almost linear minimum distance," *arXiv:2012.04068*, 2020.

[20] N. P. Breuckmann and J. N. Eberhardt, "Balanced product quantum codes," *arXiv:2012.09271*, 2020.

[21] R. M. Tanner, "A recursive approach to low complexity codes," *IEEE Transactions on Information Theory*, vol. 27, no. 5, pp. 533-547, 1981.

[22] V. Savin, "LDPC decoders," in *Channel coding: Theory, algorithms, and applications*, D. Declercq, M. Fossorier, and E. Biglieri, Eds. Elsevier, 2014, pp. 211-260.

[23] J. Pearl, "Reverend Bayes on inference engines: A distributed hierarchical approach," in *Proc. of the 2nd National Conference on Artificial Intelligence (AAAI-82)*, 1982, pp. 133-136.

[24] N. Wiberg, "Codes and decoding on general graphs," Ph.D. dissertation, Linkoping University, Sweden, 1996.
[25] E. Sharon, S. Litsyn, and J. Goldberger, "Efficient serial message-passing schedules for LDPC decoding," *IEEE Trans. on Inf. Theory*, vol. 53, no. 11, pp. 4076-4091, 2007.

[26] E. Boutillon and G. Masera, "Hardware design and realization for iteratively decodable codes," in *Channel coding: Theory, algorithms, and applications*, D. Declercq, M. Fossorier, and E. Biglieri, Eds. Elsevier, 2014, pp. 583-642.

[27] P. Schläfer, N. Wehn, M. Alles, and T. Lehnigk-Emden, "A new dimension of parallelism in ultra high throughput LDPC decoding," in *SiPS 2013 Proceedings*. IEEE, 2013, pp. 153-158.

[28] N. Raveendran and B. Vasić, "Trapping Sets of Quantum LDPC Codes," *Quantum*, vol. 5, p. 562, Oct. 2021. [Online]. Available: https://doi.org/10.22331/q-2021-10-14-562

[29] G. H. Golub and C. F. Van Loan, *Matrix computations*. JHU press, 2013.

[30] A. A. Kovalev and L. P. Pryadko, "Quantum kronecker sum-product low-density parity-check codes with finite rate," *Phys. Rev. A*, vol. 88, p. 012311, Jul 2013. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.88.012311