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

Julien Du Crest1, Mehdi Mhalla2, Valentin Savin3
1 Univ. Grenoble Alpes, Grenoble INP, LIG, F-38000 Grenoble, France
2 Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG, F-38000 Grenoble, France
3 Univ. Grenoble Alpes, CEA-Léti, F-38054 Grenoble, France
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### 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, 15, 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$-check111A 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., and then run the MP
decoding again. Inactivating these qubits means that we take them out from 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$-check222By a slight abuse of language, we shall sometimes say that the
$X$-check is inactivated (instead of the qubits in its support). 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 constructions, 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}^{\text{T}}=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 $\operatorname{im}H_{X}^{\text{T}}$ and
$\operatorname{im}H_{Z}^{\text{T}}$. 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-\operatorname*{rank}(H_{X})-\operatorname*{rank}(H_{Z})=\dim\left(\ker
H_{X}/\operatorname{im}H_{Z}^{\text{T}}\right)=\dim\left(\ker
H_{Z}/\operatorname{im}H_{X}^{\text{T}}\right)$.

The condition $H_{X}H_{Z}^{\text{T}}=0$ implies that any $Z$-check is a
codeword of $\mathcal{C}_{X}=\ker H_{X}$, and any $X$-check is a codeword of
$\mathcal{C}_{Z}=\ker H_{Z}$. Hence, $\mathcal{C}_{X}$ and $\mathcal{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\left\\{|v|,v\in\ker
H_{X}\setminus\operatorname{im}H_{Z}^{\text{T}}\right\\}$, and similarly,
$d_{Z}=\min\left\\{|v|,v\in\ker
H_{Z}\setminus\operatorname{im}H_{X}^{\text{T}}\right\\}$, 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, 19, 20].

###  2.2 Pauli Errors and Decoding

We assume that encoded qubits are affected by Pauli errors, where each qubit
is independently 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 independently333Alternatively, 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., 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^{\prime}_{X}$, such that
$e^{\prime}_{X}+e_{X}\in\ker H_{Z}$. Decoding is successful if
$\hat{e}_{X}+e_{X}\in\operatorname{im}H_{X}^{\text{T}}$, 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
$\operatorname{im}H_{X}^{\text{T}}$ acts trivially on any code state. Elements
of $\operatorname{im}H_{X}^{\text{T}}$ 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 $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}},$
(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 LLR444We 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.) 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}\geq 0,\text{ and
}\hat{e}_{X}(i)=1,\text{ otherwise}$ (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-Propagation555Many authors
confuse BP with the general MP principle. We shall use SP terminology in this
paper to avoid any possible confusion., 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 used666We 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]..

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 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 sequentially777We discuss here horizontal scheduling
strategies, applying to check-nodes. Similar vertical scheduling strategies
apply to bit-nodes., 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
$\operatorname*{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.

##  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

Figure 1: Probability distribution of $\operatorname*{rank}(r_{X})$ values.

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^{\prime}_{X}:=e_{X}+r_{X}$, we have $H_{Z}e^{\prime}_{X}=s_{X}$ and
$|e^{\prime}_{X}|=|e_{X}|$. Hence, $e^{\prime}_{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^{\prime}_{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 $\left(\tilde{\gamma}_{i}\right)_{i}$ be the output soft information of
the MP decoder, and $\hat{e}_{X}$ be the corresponding hard decision estimate
(Eq. (2)). We define

$\displaystyle\delta(e_{X},e^{\prime}_{X})\
:=\sum_{i\in\operatorname{supp}(\hat{e}_{X}+e_{X})}\\!\\!\\!\\!|\tilde{\gamma}_{i}|\
\
-\sum_{i\in\operatorname{supp}(\hat{e}_{X}+e^{\prime}_{X})}\\!\\!\\!|\tilde{\gamma}_{i}|.$
(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^{\prime}_{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^{\prime}_{X}$ (“lost
in-between” behavior). Put differently, we expect the
$\delta(e_{X},e^{\prime}_{X})$ value to be small.

Using $|\tilde{\gamma}_{i}|=(-1)^{\hat{e}_{X}(i)}\tilde{\gamma}_{i}$ and
$e^{\prime}_{X}=e_{X}+r_{X}$, one can easily verify that
$\delta(e_{X},e^{\prime}_{X})$ rewrites as
$\delta(e_{X},e^{\prime}_{X})=\sum_{i\in\operatorname{supp}(e_{X})}\tilde{\gamma}_{i}-\sum_{i\in\operatorname{supp}(e^{\prime}_{X})}\tilde{\gamma}_{i}=\sum_{i\in\operatorname{supp}(r_{X})}(-1)^{e^{\prime}_{X}(i)}\tilde{\gamma}_{i}$,
and therefore,

$|\delta(e_{X},e^{\prime}_{X})|\leq\tilde{\gamma}(r_{X}):=\sum_{i\in\operatorname{supp}(r_{X})}|\tilde{\gamma}_{i}|$
(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

$\operatorname*{rank}(r_{X}):=|\\{r^{\prime}_{X}\mid\tilde{\gamma}(r^{\prime}_{X})<\tilde{\gamma}(r_{X})\\}|.$
(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
$\operatorname*{rank}(r_{X})$ values. Fig. 1 shows the estimated probability
distribution (histogram format) of $\operatorname*{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
$\operatorname*{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}=\left[\begin{array}[]{cc}H_{Z|r_{X}}&A\\\
0&H_{Z|\overline{r_{X}}}\end{array}\right],$ (6)

where $H_{Z|r_{X}}$ is the submatrix determined by the columns corresponding
to the qubits in $\operatorname{supp}(r_{X})$, and the rows having at least
one non-zero entry in any one of these columns888Note that $r_{X}\in\ker
H_{Z}$, hence any row of $H_{Z}$ has an even number ($\geq 0$) of non-zero
entries in the columns corresponding to $\operatorname{supp}(r_{X})$. (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|\overline{r_{X}}}$,
with input syndrome $s_{X|\overline{r_{X}}}=[0\ H_{Z|\overline{r_{X}}}]e_{X}$
(that is, syndrome $s_{X}$ is restricted to the rows of the
$H_{Z|\overline{r_{X}}}$ submatrix only). If MP decoding succeeds, it provides
an estimate $\hat{e}_{X|\overline{r_{X}}}$ of the error outside
$\operatorname{supp}(r_{X})$. To estimate the error on
$\operatorname{supp}(r_{X})$, we solve the linear system
$H_{Z|r_{X}}e_{X|r_{X}}=s_{X|r_{X}}+A\hat{e}_{X|\overline{r_{X}}}$. If the
system has a solution999Note that the system will have at least two solutions.
We pick any of them., say $\hat{e}_{X|{r}_{X}}$, the decoding process stops
and outputs $\hat{e}_{X}:=(\hat{e}_{X|{r}_{X}},\hat{e}_{X|\overline{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_{\text{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.

$\hat{e}_{X}\leftarrow\text{MP}(H_{Z},s_{X})$

if  _$H_{Z}\hat{e}_{X}=s_{X}$_ then

Return $\hat{e}_{X}$

else

Compute $X$-check reliability values

$\tilde{\gamma}(r_{X})=\sum_{i\in\operatorname{supp}(r_{X})}\left|\tilde{\gamma}_{i}\right|,\
\forall r_{X}$

Sort $X$-checks in increasing order of reliability

for  _$1\leq\lambda\leq\lambda_{\text{\rm max}}$_ do

$r_{X}\leftarrow$ next least reliable $X$-check

$\hat{e}_{X|\overline{r_{X}}}\leftarrow\text{MP}\left(H_{Z|\overline{r_{X}}},s_{X|\overline{r_{X}}}\right)$

if  _$H_{Z|\overline{r_{X}}X}\hat{e}_{X|\overline{r_{X}}}\neq
s_{X|\overline{r_{X}}}$_ then

Continue

else

Solve $H_{Z|r_{X}}e_{X|r_{X}}=s_{X|r_{X}}+A\hat{e}_{X|\overline{r_{X}}}$

if  _the system has a solution $\hat{e}_{X|{r}_{X}}$_ then

Return $\hat{e}_{X}:=(\hat{e}_{X|{r}_{X}},\hat{e}_{X|\overline{r_{X}}})$

else

Continue

Return decoding failure

Algorithm 1 X-error SI$[\lambda_{\text{max}}]$ post-processing

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|\overline{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|\overline{r_{X}}}$. This may happen when some of the active qubits
become “dead ends” (degree $1$ is the reduced matrix
$H_{Z|\overline{r_{X}}}$), thus “absorbing” the error around the $Z$-checks
they are connected to.

###  3.3 Complexity

The SI$[\lambda_{\text{max}}]$ post-processing step has worst-case complexity
$\mathcal{O}(\lambda_{\text{max}}n\log n)$, where $\lambda_{\text{max}}$ is
the maximum number of inactivated $X$-checks and $\mathcal{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_{\text{max}}$ is not a
constant, but scales linearly with $n$, the worst-case complexity becomes
$\mathcal{O}(n^{2}\log n)$. In any case, the average-case complexity is
$\mathcal{O}(\lambda_{\text{ave}}n\log n)$, where $\lambda_{\text{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 $\mathcal{O}(n^{3})$. The
best algorithm to solve a general system of linear equations has complexity
$\mathcal{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,\leq 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_{\text{max}}=10]$ significantly outperforms the OSD-0 post-
processing101010We 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. in case of either MS or SP decoding, for both scheduling
strategies. For NMS decoding111111For 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$., the performance of
SI$[\lambda_{\text{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_{\text{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_{\text{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\leq\lambda_{\text{ave}}\leq\lambda_{\text{max}}$. It can be seen that
$\leq\lambda_{\text{ave}}$ approaches $1$ for low error probabilities, giving
an average-case complexity slightly higher than the MP decoding complexity.

Figure 2: Comparison of SI and OSD on B1$[882,24,\leq 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.

###  4.2 Threshold

In Fig. 3, we provide numerical evidence that SI can achieve a threshold for a
family of generalized bicycle codes121212 These codes can be found in the
alist format at https://gricad-gitlab.univ-grenoble-alpes.fr/ducrestj/qldpc-
codes 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],\quad 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_{\text{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_{\text{max}}=0.02\,m_{X}$, for the
five simulated codes131313 Precisely, $\lambda_{\text{max}}=2,3,5,10,82$, for
code length $n=126,254,510,1022,8190$, respectively.. 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_{\text{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.

(a) NMS-SI$[\lambda_{\text{max}}=0.02\,m_{X}]$ (b) NMS-OSD-0

Figure 3: Threshold for SI$[\lambda_{\text{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.

##  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
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}\mathop{\text{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, Likoping 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