#
Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation

Hanwen Yao  Duke Quantum Center, Duke University, Durham, NC, USA  Dept. of
Electrical and Computer Engineering, Duke University, Durham, NC, USA  Waleed
Abu Laban  Dept. of Electrical Engineering, Chalmers University of Technology,
Gothenburg, Sweden  Christian Häger  Dept. of Electrical Engineering, Chalmers
University of Technology, Gothenburg, Sweden
Alexandre Graell i Amat  Dept. of Electrical Engineering, Chalmers University
of Technology, Gothenburg, Sweden  Henry D. Pfister  Duke Quantum Center, Duke
University, Durham, NC, USA  Dept. of Electrical and Computer Engineering,
Duke University, Durham, NC, USA  Dept. of Mathematics, Duke University,
Durham, NC, USA

###### Abstract

Quantum low-density parity-check (QLDPC) codes have emerged as a promising
technique for quantum error correction. A variety of decoders have been
proposed for QLDPC codes and many of them utilize belief propagation (BP)
decoding in some fashion. However, the use of BP decoding for degenerate QLDPC
codes is known to face issues with convergence. These issues are commonly
attributed to short cycles in the Tanner graph and multiple syndrome-matching
error patterns due to code degeneracy. Although various methods have been
proposed to mitigate the non-convergence issue, such as BP with ordered
statistics decoding (BP-OSD) and BP with stabilizer inactivation (BP-SI),
achieving better performance with lower complexity remains an active area of
research.

In this work, we propose to decode QLDPC codes with BP guided decimation
(BPGD), which has been previously studied for constraint satisfaction and
lossy compression problems. The decimation process is applicable to both
binary BP and quaternary BP and involves sequentially freezing the value of
the most reliable qubits to encourage BP convergence. Despite its simplicity,
we find that BPGD significantly reduces BP failures due to non-convergence
while maintaining a low probability of error given convergence, achieving
performance on par with BP-OSD and BP-SI. To better understand how and why
BPGD improves performance, we discuss several interpretations of BPGD and
their connection to BP syndrome decoding.

##  1 Introduction

In a quantum computing system, error correction is an essential building block
to protect fragile quantum information against decoherence and other noise
sources. The general framework of quantum stabilizer codes has been studied
extensively [1, 2, 3]. Using this framework, various quantum error-correcting
codes have been constructed over the past two decades including toric codes
[4, 5], surface codes [6, 7, 8, 9, 10], and various quantum low-density
parity-check (QLDPC) codes [11, 12, 13, 14, 15, 16, 17]. Among them, QLDPC
codes provide a promising direction because they can support multiple logical
qubits and their low-weight stabilizers allow reliable syndrome measurement in
practice. Until recently, researchers did not know how to construct QLDPC
codes with constant rate and linear distance. But, in a series of recent
advances [18, 19, 20, 21], researchers have overcome this obstacle and there
are now constructions of asymptotically _good_ quantum LDPC codes with
constant rate and linear minimum distance.

In classical communication, low-density parity-check (LDPC) codes were first
proposed by Gallager [22] in 1962 and are now widely applied in practical
communication systems [23, 24]. LDPC codes are typically decoded with the
belief propagation (BP) algorithm [25], which has low complexity and can
provide good performance for code rates close to the channel capacity [26, 27,
28, 29]. However, in the quantum scenario, the performance of BP decoding
based on syndrome measurement is hindered by cycles in the Tanner graph and
code degeneracy. The first problem follows from the commutativity constraint
imposed on stabilizer codes which produces unavoidable cycles in the Tanner
graph that degrade the BP decoding performance [30, 31]. The second is because
good QLDPC codes are recognized to be highly _degenerate_ ; this means that
their minimum distance is much larger than the minimum weight of their
stabilizers. Due to degeneracy, the syndrome (i.e., stabilizer measurements)
can be used to identify a correction procedure that works with high
probability even when the actual error is not uniquely identified. This
hinders convergence of the BP decoding process [30, 32].

Since the initial application of BP to decode QLDPC codes by Poulin and Chung
[30], significant efforts have been made to enhance its performance. Various
methods have been proposed to modify the BP decoding process itself, including
random perturbation [30], enhanced feedback [33], grouping check nodes as
super nodes [31], parity-check matrix augmentation [34], neural BP [35, 36,
37], generalized BP [38], and adaptive BP with memory [39]. Alternatively,
post-processing methods have also been explored to improve performance. In
[16], when BP fails to converge, it was proposed to use ordered statistics
decoding (OSD) to construct a syndrome-matching error pattern based on the
soft information provided by BP. This is called the BP-OSD algorithm. Another
post-processing approach introduced in [40] involves iteratively running BP
with stabilizer inactivation (BP-SI).

In this work, we propose to improve the BP decoding performance for QLDPC
codes by combining it with guided decimation. The term “decimation” refers to
the process of sequentially fixing variables to hard decisions during
iterative decoding [41, 42]. In our proposed belief propagation guided
decimation (BPGD) algorithm, we incorporate this method by sequentially
freezing the most reliable qubit based on its soft information after a certain
number of BP iterations. Despite its simplicity, we show that BPGD outperforms
both BP-OSD with order 0 and BP-SI with 10 inactivated stabilizers under
independent Pauli-$\sigma_{x}$ errors. Notably, BPGD exhibits lower complexity
than BP-OSD and comparable complexity to BP-SI, without the need to solve any
systems of linear equations.

The BPGD algorithm was first shown to work well for $K$-SAT constraint
satisfaction [42, 43] and lossy compression problems [44, 45]. A variation has
also been shown to improve the neural BP performance for classical LDPC codes
[46]. To better understand how guided decimation improves BP performance for
QLDPC codes, we discuss some interpretations of BPGD and their connection to
the BP syndrome decoding problem for the stabilizer codes. Additionally,
through a randomized version of BPGD, we shed light on how code degeneracy
contributes to the non-convergence issue in syndrome BP decoding over QLDPC
codes. Our experiment also shows that guided decimation improves BP
convergence, and highlights how BPGD benefits from code degeneracy.
Furthermore, we extend BPGD from binary symbols to quaternary symbols,
demonstrating competitive performance compared to BP-OSD in the high-error-
rate regime under depolarizing noise.

##  2 Preliminaries

###  2.1 Binary Linear Codes

Let $\mathbb{F}_{2}=\\{0,1\\}$ be the binary Galois field defined by modulo-2
addition and multiplication. A length-$n$ binary linear code ${\cal
C}\subseteq\mathbb{F}_{2}^{n}$ is a subset of length-$n$ binary strings
satisfying $w+x\in{\cal C}$ for all $w,x\in{\cal C}$. Such a code forms a
vector space over $\mathbb{F}_{2}$. A generator matrix
$G\in\mathbb{F}_{2}^{k\times n}$ for ${\cal C}$ is a $k\times n$ matrix whose
rows span the code. A parity-check matrix $H\in\mathbb{F}_{2}^{(n-k)\times n}$
for ${\cal C}$ is an $(n-k)\times n$ matrix whose rows are orthogonal to the
code.

For communication where the codeword $x\in{\cal C}$ is corrupted by an
additive error vector $z\in\mathbb{F}_{2}^{n}$, the received vector is given
by $y=x+z$. Then, the optimal recovery process for $x$ given $y$ is given by
choosing a codeword $\widehat{x}$ that maximizes the conditional probability
given $y$. Since $Hx=0$, it follows that the syndrome vector $s\triangleq
Hy\in\mathbb{F}_{2}^{n-k}$ satisfies

$s=H(x+z)=Hz.$ (1)

For the binary symmetric channel (BSC) where $z$ is an i.i.d. vector, the
optimal recovery process can also be implemented by _syndrome decoding_ where
the syndrome $s$ is mapped to the minimum-weight error vector in the coset
$\\{u\in\mathbb{F}_{2}^{n}\,|\,Hu=s\\}$ containing $z$. For more details on
this well-known classical setup, see [47].

###  2.2 Stabilizer Formalism

An $[[n,k]]$ quantum stabilizer code is an error correction code designed to
protect $k$ logical qubits with $n$ physical qubits against noise. To
establish the definition of quantum stabilizer codes, we first define the
Pauli operators. For a single qubit, its pure quantum state is represented as
a unit vector in the two-dimensional Hilbert space ${\mathbb{C}}_{2}$. The
Pauli operators for a single qubit system are defined as the $2\times 2$
complex Hermitian matrices

$I=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix},\,\sigma_{x}=\begin{bmatrix}0&1\\\
1&0\end{bmatrix},\,\sigma_{z}=\begin{bmatrix}1&0\\\
0&-1\end{bmatrix},\,\sigma_{y}=\imath\sigma_{x}\sigma_{z}=\begin{bmatrix}0&-\imath\\\
\imath&0\end{bmatrix},$

and they form a basis for all $2\times 2$ complex matrices. For an $n$-qubit
system, we are working in ${\mathbb{C}}_{2}^{\otimes n}$, the $n$-fold
Kronecker product of the two-dimensional Hilbert space. Given two length-$n$
binary vectors $a=(a_{1},a_{2},\ldots,a_{n})\in{\mathbb{F}}_{2}^{n}$, and
$b=(b_{1},b_{2},\ldots,b_{n})\in{\mathbb{F}}_{2}^{n}$, we define the $n$-fold
Pauli operator $D(a,b)$ as

$D(a,b)=\sigma_{x}^{a_{1}}\sigma_{z}^{b_{1}}\otimes\sigma_{x}^{a_{2}}\sigma_{z}^{b_{2}}\otimes\ldots\otimes\sigma_{x}^{a_{n}}\sigma_{z}^{b_{n}}.$
(2)

It follows that the Pauli operators $\imath^{k}D(a,b)$ with
$a,b\in{\mathbb{F}}_{2}^{n}$ and an overall phase $\imath^{k}$ with
$k\in\\{0,1,2,3\\}$ form the $n$-qubit Pauli group, denoted as ${\cal P}_{n}$.
Since $\sigma_{x}\sigma_{z}=-\sigma_{z}\sigma_{x}$, the multiplication rule in
this group is given by

$\displaystyle D(a,b)D(a^{\prime},b^{\prime})$
$\displaystyle=(-1)^{a^{\prime}b^{T}+b^{\prime}a^{T}}D(a^{\prime},b^{\prime})D(a,b)$
(3) $\displaystyle=(-1)^{a^{\prime}b^{T}}D(a+a^{\prime},b+b^{\prime}).$ (4)

The _symplectic inner product_ between length-$2n$ binary vectors $(a,b)$ and
$(a^{\prime},b^{\prime})$ is defined by

$\langle(a,b),(a^{\prime},b^{\prime})\rangle_{s}\triangleq(a^{\prime},b^{\prime})\Lambda(a,b)^{T}=b^{\prime}a^{T}+a^{\prime}b^{T}\bmod
2,\quad\Lambda=\begin{bmatrix}0&I_{n}\\\ I_{n}&0\end{bmatrix}.$ (5)

It equals 0 if the two Pauli operators $D(a,b)$ and $D(a^{\prime},b^{\prime})$
commute and it is 1 if they anti-commute.

A quantum stabilizer code ${\cal C}$ with $n$ physical qubits is defined via a
commutative subgroup ${\cal S}\subseteq{\cal P}_{n}$ with $-I_{2}^{\otimes
n}\notin{\cal S}$. The subgroup ${\cal S}$ is referred to as the _stabilizer
group_ , and the Pauli operators in ${\cal S}$ are called the _stabilizers_ ,
or _checks_ in the context of decoding. The code space consists of all states
in ${\mathbb{C}}_{2}^{\otimes n}$ stabilized by ${\cal S}$ as follows:

${\cal C}=\\{|\psi\rangle\in{\mathbb{C}}_{2}^{\otimes
n}:M|\psi\rangle=|\psi\rangle,\,\forall M\in{\cal S}\\}.$ (6)

In other words, ${\cal C}$ consists of states that are +1 eigenstates for all
the stabilizers in ${\cal S}$. If ${\cal S}$ has $n-k$ independent generators,
the code space has dimension $k$. The _weight_ of a Pauli operator in ${\cal
P}_{n}$ is defined to be the number of elements in its $n$-fold Kronecker
product that are not equal to $I$. The _distance_ of a stabilizer code is
defined as the minimum weight of all Pauli operators in $N({\cal
S})\backslash{\cal S}$, where $N({\cal S})$ denotes the normalizer group of
${\cal S}$ in ${\cal P}$. If code ${\cal C}$ has distance $d$, we call ${\cal
C}$ an $[[n,k,d]]$ quantum stabilizer code. In particular, ${\cal C}$ is
called _degenerate_ if its distance $d$ is larger than the minimum weight of
its stabilizers.

In the symplectic representation, the stabilizer ${\cal S}$ is constructed
from the rows of the stabilizer matrix

$H=[H_{x},H_{z}],$ (7)

where $H_{x},H_{z}\in{\mathbb{F}}_{2}^{m\times n}$ are binary matrices with
$m$ rows and $n$ columns. In particular, each row $(h_{x},h_{z})$ of $H$
defines the stabilizer $D(h_{x},h_{z})$ and the set of stabilizers defined by
all rows generates the stabilizer group ${\cal S}$. In this way, the
constraint requiring all the stabilizers in $H$ to commute with each other can
be expressed as $H\Lambda H^{T}=H_{x}H_{z}^{T}+H_{z}H_{x}^{T}=0$. There is an
important class of stabilizer codes, known as Calderbank–Shor–Steane (CSS)
codes [48, 49], where each stabilizer has the form $D(a,0)$ (i.e., only
$\sigma_{x}$ operators) or $D(0,b)$ (i.e., only $\sigma_{z}$ operators). In
this case, we have

$H_{x}=\begin{bmatrix}0\\\ G_{2}\end{bmatrix},\quad
H_{z}=\begin{bmatrix}H_{1}\\\ 0\end{bmatrix},$ (8)

where $H_{1}\in\mathbb{F}_{2}^{(n-k_{1})\times n}$ is the parity-check matrix
of a classical $[n,k_{1}]$ code ${\cal C}_{1}$ and
$G_{2}\in\mathbb{F}_{2}^{k_{2}\times n}$ is the generator matrix of a
classical $[n,k_{2}]$ code ${\cal C}_{2}$. Thus, the stabilizer matrix has the
form

$H=\begin{bmatrix}0&H_{1}\\\ G_{2}&0\end{bmatrix}.$ (9)

For CSS codes, the commutativity constraint for the stabilizers, which is
given by $H\Lambda H^{T}=0$, reduces to $G_{2}H_{1}^{T}=0$ which is equivalent
to ${\cal C}_{2}\subseteq{\cal C}_{1}$. In this work, we will focus our
discussion on the CSS codes.

###  2.3 Syndrome Decoding of Stabilizer Codes

While classical codes are typically decoded from direct observations of the
received sequence, directly measuring qubits in a stabilizer code may destroy
the entanglement (or superposition) in the quantum state. To avoid this, one
instead measures whether or not certain stabilizers commute with the quantum
state. These measurements reveal the syndrome of the error that occurred and
then syndrome decoding can be used to identify the best method to correct the
error.

For an $[[n,k]]$ stabilizer code ${\cal C}$, we will consider two error models
in this work. The first model is the independent Pauli-$\sigma_{x}$ error
channel, where each encoded qubit is independently affected by a
Pauli-$\sigma_{x}$ error with a probability $p_{x}$. For this model, we will
discuss the binary version of our algorithm. The second model is the
_depolarizing channel_ characterized by a physical error rate $p$. In this
model, each encoded qubit is independently affected by Pauli $\sigma_{x}$,
$\sigma_{y}$, or $\sigma_{z}$ errors, each with probability $p/3$. For the
depolarizing channel, we will discuss the quaternary version of our algorithm.

In both of these models, the encoded state $|\psi\rangle$ is corrupted by an
$n$-qubit Pauli error $E=D(x,z)\in{\cal P}_{n}$ as $|\psi\rangle\rightarrow
E|\psi\rangle$. For the decoder, the goal is to detect and correct this error
by conducting measurements on all the stabilizers in the parity-check matrix
$H$. The measurement result can be expressed as the symplectic inner product
$\langle(a,b),(x,z)\rangle_{s}$ for a particular stabilizer $M=D(a,b)\in{\cal
S}$, indicating whether $E$ commutes or anti-commutes with $M$. The symplectic
inner product of the Pauli error $(x,z)$ with the stabilizers in $H$ form the
length-$m$ binary syndrome vector

$s=(x,z)\Lambda H^{T}.$ (10)

This succinctly encapsulates all the information derived from the
measurements. For CSS codes, $H_{1}$ defines $\sigma_{z}$-stabilizers that
interact with Pauli-$\sigma_{x}$ errors and $G_{2}$ defines
$\sigma_{x}$-stabilizers that interact with Pauli-$\sigma_{z}$ errors. Thus,
we can separate the length $m=n-k_{1}+k_{2}$ syndrome vector into two parts
$s=(s_{x},s_{z})$ where $s_{x}=xH_{1}^{T}$ has length $n-k_{1}$ and
$s_{z}=zG_{2}^{T}$ has length $k_{2}$. In this work, we assume that all
syndrome measurements are perfect.

Based on its syndrome, the Pauli error $E$ that affects the qubits can be
categorized as follows:

  1. 1.

Detectable Error: $E$ is called _detectable_ if its syndrome $s$ is not the
all-one vector. In other words, $E$ is detectable if it anticommutes with at
least one of the stabilizers in ${\cal S}$. Otherwise, $E$ is called _non-
detectable_.

  2. 2.

Degenerate Error: If $E$ is a non-detectable error, it is called _degenerate_
if it belongs to the stabilizer group, i.e., $E\in{\cal S}$. In this case, $E$
preserves the encoded state and needs no correction.

  3. 3.

Logical Error: If $E$ is a non-detectable error that does not belong to the
stabilizer group, i.e., $E\in N({\cal S})\backslash{\cal S}$, it is called a
_logical_ error, and it alters the logical state of the encoded qubits.

After obtaining the syndrome $s$ through measurement, the task of the decoder
is to find an estimated $\widehat{E}$ with the same syndrome. Then, the
reverse operator $\widehat{E}^{{\dagger}}$ can be applied to the affected
qubits as $E|\psi\rangle\rightarrow\widehat{E}^{{\dagger}}E|\psi\rangle$ for
error correction. This decoding process has four possible outcomes:

  1. 1.

Decoding Failure: The decoder fails to provide an estimated $\widehat{E}$ that
yields the syndrome $s$.

  2. 2.

Successful Decoding (Exact Match): The estimated error is equal to the channel
error, i.e., $\widehat{E}=E$.

  3. 3.

Successful Decoding (Degenerate Error): The difference between the estimated
error and the channel error is a degenerate error, i.e.,
$\widehat{E}^{{\dagger}}E\in{\cal S}$.

  4. 4.

Decoding Failure (Logical Error): The difference between the estimated error
and the channel error is a logical error, i.e., $\widehat{E}^{{\dagger}}E\in
N({\cal S})\backslash{\cal S}$.

Since there are $2^{m}$ possible syndromes, using a look-up table for error
estimation quickly becomes infeasible as the number of qubits increases
because $m$ typically scales linearly with $n$. Thus, a computationally
efficient decoder is required for long stabilizer codes. Now, we describe the
two decoding strategies for stabilizer codes using the names from [50].

Quantum Maximum Likelihood Decoding (QMLD): This decoding strategy aims at
finding the most probable error $E=D(X,Z)$ given the syndrome, where
$X,Z\in\mathbb{F}_{2}^{n}$ are random vectors drawn from some Pauli error
distribution. In this model, the syndrome is a random vector defined by
$S=(X,Z)\Lambda H^{T}$. Given the observed syndrome event $S=s$, we compute
$\widehat{E}=D(\widehat{X},\widehat{Z})$ where

$(\widehat{X},\widehat{Z})=\underset{(x^{\prime},z^{\prime})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}}{\arg\max}\;\Pr\big{(}(X,Z)=(x^{\prime},z^{\prime})\,|\,S=s\big{)}.$
(11)

For the independent Pauli-$\sigma_{x}$ error channel and the depolarizing
channel, solving (11) is at least as hard as the maximum-likelihood decoding
problem in classical coding theory, which is well-known to be NP-complete
[51].

Degenerate Quantum Maximum Likelihood Decoding (DQMLD): Denote the coset of
the stabilizer group ${\cal S}$ shifted by a Pauli error $E\in{\cal P}_{n}$ as
${\cal S}(E)$, and denote the set of all cosets of ${\cal S}$ as ${\cal
P}_{n}/{\cal S}$. In the context of a stabilizer code, where all Pauli errors
in the same coset ${\cal S}(E)$ affect the logic state of encoded qubits
equivalently, the optimal decoding strategy would be finding the most probable
coset ${\cal S}(E)$ given the observed syndrome event $S=s$. After that, the
decoder can choose any error pattern $\widehat{E}$ in this coset as the error
to be corrected, as the specific pattern selected does not affect the result
due to degeneracy. This decoding problem has been shown to be $\\#$P-complete
[50], which is computationally much harder than QMLD.

###  2.4 Syndrome Decoding for Pauli-$\sigma_{x}$ Errors

In Sections 3 and 4 that follow, we will focus on the syndrome decoding
problem for CSS codes over the independent Pauli-$\sigma_{x}$ error channel
with probability $p_{x}$, where the Pauli error has the form $E=D(X,0)$, with
$X\in{\mathbb{F}}_{2}^{n}$ being a random vector following the distribution:

$\Pr\big{(}X=(x_{1},x_{2},\ldots,x_{n})\big{)}=\prod_{i=1}^{n}p_{x}^{x_{i}}(1-p_{x})^{1-x_{i}}$
(12)

In the following, we will use the random vector $X$ to denote the channel
error for simplicity. For CSS codes in this case, given $X$, the decoder only
needs to consider part of the syndrome $S_{x}=XH_{1}^{T}$, where $H_{1}$ is
the submatrix of $H_{z}$ as in (8). The QMLD decoding problem then becomes
computing $\widehat{X}$ where

$\widehat{X}=\underset{x\in{\mathbb{F}}_{2}^{n}}{\arg\max}\;\Pr(X=x\,|\,S_{x}=s_{x})=\underset{x\in{\mathbb{F}}_{2}^{n}\,:\,xH_{1}^{T}=s_{x}}{\arg\min}\;\mathrm{wt}(x)$
(13)

This is equivalent to the maximum-likelihood decoding problem for the BSC in
classical coding theory, which is known to be NP-complete [51]. Thus, we turn
to the low-complexity belief propagation (BP) algorithm.

##  3 Belief Propagation Decoding

BP is a low-complexity algorithm that solves inference problems for graphical
models. Originated in the 1960s, Gallager’s LDPC decoder [22] already contains
the essence of BP, which was later formalized by Pearl in [52, 53]. In 1993,
the discovery of turbo codes [54] brought along the turbo decoding algorithm,
which is now recognized as an instance of BP [55]. In the late 1990s, those
ideas led to the formalization of factor graphs and the sum-product algorithm
[25, 56]. Among other decoders, BP is highly parallelizable for
implementation, and it achieves near-optimal decoding of LDPC codes and turbo
codes. It also has wide applications in other problems on graphical models,
such as the spin glass models [57], lossy compression with the low-density
generator matrix codes [44, 45], and constraint satisfaction problems such as
$K$-SAT [42, 43].

BP was first introduced to the quantum decoding problem by Poulin and Chung in
[30]. However, the performance of BP for the quantum syndrome decoding problem
for the QLDPC codes is degraded due to degeneracy [30, 32]. In this section,
we first review the binary BP algorithm for syndrome decoding of stabilizer
codes over independent Pauli-$\sigma_{x}$ errors. Then, we discuss some prior
improvements for BP that mitigate the non-convergence problem, including BP-
OSD and BP-SI.

###  3.1 Belief Propagation Syndrome Decoding for Pauli-$\sigma_{x}$ Errors

BP is an iterative message-passing algorithm that provides an estimate of the
marginal probability $\Pr(X_{i}=x_{i}|S_{x}=s_{x})$ for all $i\in[n]$. To run
BP for the syndrome decoding problem of stabilizer codes over independent
Pauli-$\sigma_{x}$ errors with probability $p_{x}$, we first need to construct
a Tanner graph $G=(V,C,E)$ representing $H_{1}$, where $H_{1}$ is the binary
matrix with $m$ rows and $n$ columns as shown in (8). In this Tanner graph,
the variable nodes in $V=\\{v_{1},\ldots,v_{n}\\}$ represent the elements of
$X=(X_{1},\ldots,X_{n})$ and the check nodes in $C=\\{c_{1},\ldots,c_{m}\\}$
represent the $\sigma_{z}$-stabilizers in $H_{1}$. A variable node $v_{i}$ is
connected to a check node $c_{j}$ if $H_{1}(i,j)=1$. In addition, each
variable node is connected to a degree 1 check node that represents the source
of the channel message, and each check node is connected to a degree 1
variable node that represents the source of a syndrome bit. An example Tanner
graph representing $H_{1}$ for the $[[7,1,3]]$ Steane code [49] with

$H_{1}=\begin{bmatrix}1&1&1&0&1&0&0\\\ 0&1&1&1&0&1&0\\\
0&0&1&0&1&1&1\end{bmatrix}$ (14)

is shown in Figure 1.

$v_{1}$$\mu_{v_{1}}$$v_{2}$$\mu_{v_{2}}$$v_{3}$$\mu_{v_{3}}$$v_{4}$$\mu_{v_{4}}$$v_{5}$$\mu_{v_{5}}$$v_{6}$$\mu_{v_{6}}$$v_{7}$$\mu_{v_{7}}$$c_{1}$$s_{x,1}$$c_{2}$$s_{x,2}$$c_{3}$$s_{x,3}$channel
messagesvariable nodes in $V$check nodes in $C$syndrome Figure 1: Tanner graph
for $H_{1}$ for the $[[7,1,3]]$ Steane code

Let $\mu_{v_{i}}$ denote the channel log-likelihood ratio (LLR) for $v_{i}$ as

$\mu_{v_{i}}=\log\frac{\Pr(X_{i}=0)}{\Pr(X_{i}=1)}=\log\frac{1-p_{x}}{p_{x}}.$
(15)

This is the initial estimate of the overall LLR of $X_{i}$. At iteration
$t=0$, set the message from each variable node $v_{i}$ to all its connected
check node $c_{j}$ as

$m^{(0)}_{v_{i}\rightarrow c_{j}}=\mu_{v_{i}}.$

Then, for iteration $t=0,1,\ldots,T$, given the syndrome
$s_{x}=(s_{x,1},\ldots,s_{x,m})$, the messages between variable nodes and
check nodes are updated as

$m^{(t)}_{c_{j}\rightarrow
v_{i}}=(-1)^{s_{x,j}}\tanh^{-1}\left(\tanh\prod_{v_{k}\in\partial
c_{j}\backslash v_{i}}m^{(t)}_{v_{k}\rightarrow c_{j}}\right),$ (16)

and

$m^{(t+1)}_{v_{i}\rightarrow c_{j}}=\mu_{v_{i}}+\sum_{c_{k}\in\partial
v_{i}\backslash c_{j}}m^{(t)}_{c_{k}\rightarrow v_{i}},$ (17)

where $s_{x,j}\in\\{0,1\\}$ is the syndrome of the $\sigma_{z}$-stabilizer
corresponding to $c_{j}$ (i.e., defined by the $j$-th row of $H_{1}$),
$\partial c_{j}$ denotes the set of variable nodes in $V$ connected to
$c_{j}$, and $\partial v_{i}$ denotes the set of check nodes in $C$ connected
to $v_{i}$. This update rule is called the sum-product algorithm [25]. The
_bias_ for variable node $v_{i}$ after $t$ iterations can be computed as

$m^{(t)}_{v_{i}}=\mu_{v_{i}}+\sum_{c_{k}\in\partial
v_{i}}m^{(t)}_{c_{k}\rightarrow v_{i}}.$ (18)

For sufficiently large $t$, one approximates the log-likelihood ratio of the
marginal probabilities for $X_{i}$ with

$m^{(t)}_{v_{i}}\approx\log\frac{\Pr(X_{i}=0\,|\,S_{z}=s_{z})}{\Pr(X_{i}=1\,|\,S_{z}=s_{z})}.$
(19)

This approximation is exact if the Tanner graph $G$ is a tree [25]. The sign
of the bias $m^{(t)}_{v_{i}}$ represents the hard value toward which this
variable node $v_{i}$ is biased, and the absolute value of the bias denoted as
$\gamma^{(t)}(v_{i})=|m^{(t)}_{v_{i}}|$, or just $\gamma(v_{i})$ if $t$ is
clear from the context, represents the _reliability_ of this variable node.
The larger the reliability, the more certain we are about its indicated hard
value.

BP for syndrome decoding is commonly equipped with the following termination
rule upon convergence [30]. After $t$ iterations, the estimated hard value for
$X_{i}$ can be computed as

$\widehat{x}^{(t)}_{i}=\begin{cases}0,&m^{(t)}_{v_{i}}>0\\\
1,&m^{(t)}_{v_{i}}\leqslant 0\end{cases}.$ (20)

The BP algorithm terminates early if the computed hard values
$\widehat{x}^{(t)}=(\widehat{x}^{(t)}_{1},\widehat{x}^{(t)}_{2},\ldots,\widehat{x}^{(t)}_{n})$
match the syndrome by satisfying $\widehat{x}^{(t)}H_{1}^{T}=s_{z}$. This
syndrome match event is called _convergence_ [30]. The BP decoder then outputs
$\widehat{E}=D(\widehat{x}^{(t)},0)$ as the estimated error operator. If none
of the estimated $\widehat{x}^{(t)}$ vectors match the syndrome when $t$
reaches a preset maximum iteration number $T$, then the BP decoder reports
failure due to _non-convergence_.

###  3.2 Prior Works that Mitigate the Non-Convergence Issue

BP for the syndrome decoding problem of QLDPC codes is known to have issues
with convergence [30, 32]. Consider the $[[882,24,18\leqslant d\leqslant 24]]$
generalized bicycle B1 code proposed in [16]. We simulated its BP decoding
performance with the sum-product algorithm over independent Pauli-$\sigma_{x}$
errors with probability $p_{x}$ and the performance can be found in the blue
curve in Figure 2. In our simulation, all the block error cases that we
observe are due to non-convergence.

To mitigate the non-convergence issue, Pantaleev and Kalachev [16] proposed
the use of ordered statistics decoding as a post-processor when BP fails to
converge. In Figure 2, the red curve shows the BP-OSD performance with order
0. In this simulation, we employ the normalized min-sum algorithm for message
passing with the normalization factor $\alpha=0.625$, matching the decoder in
[16]. The BP-OSD decoder shows a significant performance improvement over BP
and this gain has been observed across various families of quantum stabilizer
codes [16, 58]. However, it is important to note that OSD comes with a higher
computational complexity of $O(n^{3})$ [16] compared to BP. In this work, we
take BP-OSD as the primary benchmark for evaluating the performance of our
proposed BPGD algorithm.

Another approach to mitigate the non-convergence issue of BP, called BP with
stabilizer inactivation, is proposed by Crest, Mhalla and Savin in [40]. It
starts by sorting the $\sigma_{z}$-stabilizer rows in $H_{1}$ in increasing
order of reliability based on BP soft information. After that, the BP
algorithm is run $\lambda$ times with exactly one of the $\lambda$ least
reliable stabilizers inactivated (i.e. punctured), with early termination upon
convergence. This BP-SI approach is based on the intuition that the
“stabilizer-splitting” errors [40, 32] prevent BP convergence. In Figure 2,
the performance of BP-SI with $\lambda=10$ on the B1 code is shown in the
yellow curve. The data points for the yellow curve are taken and translated
directly from [40, Figure 2], where the decoder uses the serial message-
passing scheduling for the normalized min-sum algorithm with normalization
factor $\alpha=0.9$. In [40], the worst-case complexity and the average
complexity of BP-SI are claimed to be $O(\lambda_{\max}n\log n)$ and
$O(\lambda_{\text{avg}}n\log n)$, respectively, assuming BP has complexity
$O(n\log n)$. Here, $\lambda_{\max}$ represents the maximum number of
inactivated stabilizers and $\lambda_{\text{avg}}$ represents the average
number of inactivated stabilizers. Notably, at the end of post-processing for
both BP-OSD and BP-SI, one needs to solve a system of linear equations.

##  4 Binary Belief Propagation with Guided Decimation

In this work, we use BP with guided decimation to mitigate the non-convergence
issue of standard BP for QLDPC codes. The BPGD algorithm has two alternating
phases:

  1. 1.

iterative message-passing updates in BP to compute marginal probability
approximations for the variable nodes, and

  2. 2.

decimation, where we update the channel LLR of the most reliable variable node
to freeze its value.

###  4.1 Message-Passing Decoding with Decimation

Message-passing algorithms with “decimation” were first introduced for the
$K$-SAT constraint satisfaction problem based on insights from statistical
physics [41]. In such problems, there are typically many valid solutions and
the goal is to find just one of them. The problem is that the set of solutions
can fragment into many clusters that are well separated from each other in
Hamming space. When this happens, the BP algorithm does not converge to one of
the solutions but instead provides information about the average of a bit
value over all valid solutions. For example, a bit message is expected to be
uninformative (i.e., $m^{(t)}_{v_{i}}\approx 0$) if bit-$i$ is 0 in half of
the solutions and 1 in the other half. But, if the bit message is highly
biased towards 1 (i.e., $m^{(t)}_{v_{i}}\ll 0$), then bit-$i$ is expected that
it takes the value 1 in a large fraction of the valid solutions. In that case,
decimating (i.e., forcing) the bit value to 1 should not reduce the set of
accessible valid solutions by too much and the process can continue. In [41],
decimation was first combined with a related message-passing algorithm called
survey propagation. Survey propagation is designed to average over the
clusters in an improved manner that accounts for the fact that valid solutions
often have bits that are unconstrained.

Later, the idea of decimation was extended to define the BP guided decimation
(BPGD) algorithm [42] and related approaches were applied to the lossy
compression problem [44, 45]. For the simplest instance of this problem, a
uniform random binary source vector is quantized to a codeword in a binary
linear code. The goal is to find a codeword close to the source vector or,
ideally, the closest codeword. If the decoding process finds any codeword,
then decoding succeeds and the cost is given by the Hamming distance to the
source vector. Otherwise, the decoding process fails. The decoding and
decimation process is designed to minimize the average cost. During each round
of decoding and decimation, there is a natural lower bound on the cost given
by minimizing over all codewords matching the current set of decimated bits.
This lower bound is non-decreasing as the rounds progress and a good short-
term goal for the decimation process is to make hard decisions that preserve a
large number of codewords that are relatively close to the source vector. This
again leads to the rule of decimating bits whose messages are strongly biased
towards 0 or 1.

###  4.2 Intuition Behind BPGD for Quantum Decoding

Now, we discuss some intuitions for applying BPGD for the quantum degenerate
decoding problem. In [42], the BPGD algorithm is understood to approximate the
process of sampling a vector from the distribution implied by the Tanner
graph. From Figure 1, we see that the Tanner graph for BP syndrome decoding
constrains the error vector to match the observed syndrome and assumes each
error bit is drawn independently with probability $p_{x}$.

Applying this picture to the quantum decoding problem, we can think of BPGD
decoding as sampling from the error patterns that match the syndrome with
weights proportional to the distribution in (12). While this type of decoding
is not equivalent to either QMLD or DQMLD, we will argue that the sampling
approach is closer in spirit to DQMLD than QMLD. The reason is that the
sampling probability for a correction operator is proportional to the sum of
the probabilities of all the error patterns associated with that correction
operator. Thus, the error is more likely to be corrected. On the other hand,
QMLD tries only to find the error pattern with the highest individual
probability.

###  4.3 The BPGD Algorithm

Now, the BPGD algorithm is described in detail. First, the channel LLRs for
all $v_{i}$ variable nodes in the Tanner graph are initialized like the BP
algorithm to $\mu_{v_{i}}=\log((1-p_{x})/p_{x})$. Then, decoding proceeds in
rounds. In the $r$-th round, the BP algorithm is run for $T$ iterations
following (16) and (17). If the BP algorithm converges to an error pattern
matching the syndrome, then the decoder terminates and returns the hard values
of the variable nodes as the estimated error. Otherwise, the current estimated
error pattern does not match the syndrome, and out of all the variable nodes
that are not yet decimated, the variable node $v_{i}$ with the largest
reliability $\gamma(v_{i})$ is decimated by updating its channel message
$\mu_{v_{i}}$ based on its bias $m_{v_{i}}^{(rT)}$ to

$\mu_{v_{i}}=\begin{cases}\text{llr}_{\max},&\text{if }m_{v_{i}}^{(rT)}>0\\\
-\text{llr}_{\max},&\text{if }m_{v_{i}}^{(rT)}\leqslant 0,\end{cases}$ (21)

where $\text{llr}_{\max}$ is a large fixed number. If we choose
$\text{llr}_{\max}$ to be infinity (i.e. $\text{llr}_{\max}=\infty$), this
decimation effectively assigns a hard value for the variable node $v_{i}$
based on its bias. While letting $\text{llr}_{\max}$ to be infinity makes
sense in theory, this can also introduce numerical problems in software
implementation, and thus setting $\text{llr}_{\max}$ to be a large fixed
number (e.g. $\text{llr}_{\max}=25$) is preferred in practice.

After decimating the most reliable variable node, the process starts round
$r+1$ and the process continues either until the estimated error pattern
matches the syndrome or all the variable nodes have been decimated. After all
variable nodes are decimated, if the hard values of their biases still don’t
match the syndrome, then this is called a _non-convergence failure_ of the
BPGD algorithm. The pseudo-code for the BPGD algorithm is given in Algorithm
1.

Input: Tanner graph $G=(V,C,E)$ for $H_{1}$, block length $n$, syndrome
$s_{x}$, Pauli-$\sigma_{x}$ error rate $p_{x}$, number of iterations per round
$T$

Output: $\widehat{E}$ or non-convergence

1 $\mu_{v_{i}}=\log((1-p_{x})/p_{x})$ for all $v_{i}\in V$

2 $m^{(0)}_{v_{i}\rightarrow c_{j}}=\mu_{v_{i}}$ for all $v_{i}\in
V,c_{j}\in\partial v_{i}$ // BP initialization

3 $V_{u}=V$ // the set of undecimated variable nodes

4 for  _$r=1$ _to_ $n$_ do

5 run $T$ iterations of BP with the sum-product algorithm

6 $\widehat{x}\leftarrow$ hard values for the variable nodes

7 if  _$\widehat{x}H_{1}^{T}=s_{x}$_ then

8 return _$\widehat{E}=D(\widehat{x},0)$_

9 else

10 $v_{i}=\arg\max_{v\in V_{u}}\gamma(v_{i})$ // Pick the most reliable node
in $V_{u}$

11 if  _$m_{v_{i}}^{(rT)}\geqslant 0$_ then

12 $\mu_{v_{i}}=\text{llr}_{\max}$

13 else

14 $\mu_{v_{i}}=-\text{llr}_{\max}$

15 $V_{u}=V_{u}\backslash\\{v_{i}\\}$

16

return _non-convergence_

Algorithm 1 Binary belief propagation with guided decimation (BPGD) over
Pauli-$\sigma_{x}$ errors
0.040.050.060.070.080.090.10$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$$p_{x}$Block
Error Rate$[[882,24,18\leqslant d\leqslant 24]]$ B1 code [16]BPBP-OSD-0BP-SI,
$\lambda=10$ [40]BPGD, $T=10$BPGD, $T=100$ Figure 2: Performance of B1 code
[16] over independent Pauli-$\sigma_{x}$ errors.

###  4.4 Numerical Results

In Figure 2, we show the simulation result of the BPGD decoder for the
$[[882,24,18\leqslant d\leqslant 24]]$ B1 code [16] over independent
Pauli-$\sigma_{x}$ errors with probability $p_{x}$. In our software
implementation of Algorithm 1, we set $\text{llr}_{\max}=25$. BPGD with
$T=100$, shown by the green curve, yields the best performance. Using $T=100$
ensures that in each round, BP is run for a sufficient number of iterations to
provide accurate approximate marginal probabilities for the variable nodes.
Reducing the number of BP iterations per round from $T=100$ to $T=10$, shown
by the purple curve, does not significantly degrade the BPGD performance. It
is worth noting that, in our simulations, the majority of the errors (over
90%) from the BPGD runs for both $T=100$ and $T=10$ are attributed to non-
convergence. Therefore, similar to the BP algorithm, we rarely encounter
logical errors upon convergence from running BPGD. For comparison, Figure 3
also includes the decoding performance of BP, BP-OSD with order 0, and BP-SI
with $\lambda=10$, whose settings are explained in Section 3.2.

In Figure 3, we also show the performance of BPGD with $T=10$ for the
$[[1922,50,16]]$ C2 code proposed in [16] over independent Pauli-$\sigma_{x}$
errors with probability $p_{x}$. For this simulation, we again set
$\text{llr}_{\max}=25$ in Algorithm 1. For comparison, we include the
performances for BP, BP-OSD with order 0, and BP-SI with $\lambda=10$, whose
respective settings remain consistent with those in Figure 2: 1) the BP
decoder runs the basic sum-product algorithm; 2) the BP-OSD decoder with order
0 runs the serial normalized min-sum algorithm with normalization factor
$\alpha=0.625$; 3) the BP-SI decoder with $\lambda=10$ runs the serial
normalized min-sum algorithm with normalization factor $\alpha=0.9$, whose
data points are taken and translated directly from [40, Figure 2]. We can see
that for the two QLDPC codes we considered in Figure 2 and Figure 3, BPGD
shows better performance compared with BP-OSD with order 0, and is slightly
better than BP-SI with $\lambda=10$ over independent Pauli-$\sigma_{x}$
errors.

0.040.050.060.070.080.090.10$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$$p_{x}$Block
Error Rate$[[1922,50,16]]$ C2 code [16]BPBP-OSD-0BP-SI, $\lambda=10$ [40]BPGD,
$T=10$ Figure 3: Performance of C2 code [16] over independent
Pauli-$\sigma_{x}$ errors.

We would like to note that, in our simulations in Figure 2 and Figure 3, we
are using the basic sum-product algorithm with flooding scheduling for the
message-passing updates in BPGD. The performance shown in Figure 2 and Figure
3 still has potential for further improvements by exploring alternative
variants of BP including the normalized min-sum algorithm, serial scheduling
[59, 60], neural belief propagation [35, 37], and belief propagation with
memory [39].

###  4.5 Complexity Analysis for BPGD

BPGD requires at most $n$ decimation rounds, each involving $T$ iterations of
message-passing updates of complexity $O(n)$ and a search for the most
reliable qubit for decimation with complexity $O(n)$. Therefore, the worst-
case complexity of BPGD is $O(Tn^{2})$. This worst-case complexity scales
roughly the same as BP with SI [40], and it is better compared with BP-OSD
with order 0, which has complexity $O(n^{3})$ [16]. Moreover, unlike BP-OSD
and BP-SI, BPGD does not require solving systems of linear equations, which
makes it potentially more friendly for hardware implementation.

For the BPGD algorithm, if we assume BP in each round has complexity $O(Tn)$,
then its average-case complexity is $O(r_{\text{avg}}Tn)$, where
$r_{\text{avg}}$ denotes the average number of decimated variable nodes. The
value of $r_{\text{avg}}$ is highly dependent on the Pauli-$\sigma_{x}$ error
rate $p_{x}$, meaning BPGD has different average complexity in different error
rate regimes. In Table 1, we show the average number of decimated variable
nodes for BPGD with $T=10$ when decoding the B1 code. The simulation we
perform for Table 1 also produces four data points in the purple curve in
Figure 2. Note that when calculating $r_{\text{avg}}$ in Table 1, we take into
account both the convergent cases and the non-convergent cases. In the case of
non-convergence, the number of variable nodes decimated by BPGD equals the
block length $n=882$. From Table 1 we can see that, in the low error rate
regime such as $p_{x}=0.05$, $r_{\text{avg}}$ becomes very small, making the
average complexity of the BPGD approach $O(Tn)$, the complexity of the BP
algorithm. We note that a similar observation has also been made for BP-SI
concerning the average number of inactivated stabilizers in the low error rate
regime [40]. Instead of using a fixed number $T$ of BP iterations, if the BP
algorithm is run until convergence, then it is typical to assume that
$T=O(\log n)$ iterations are required.

$p_{x}$ | 0.05 | 0.06 | 0.07 | 0.08
---|---|---|---|---
simulation runs | 1000000 | 100000 | 100000 | 10000
$r_{\text{avg}}$ | 2.91 | 9.82 | 60.46 | 231.7
Table 1: Average number of decimated variables nodes of BPGD with $T=10$ when
decoding the B1 code [16] over Pauli-$\sigma_{x}$ errors.

One natural way to reduce the worst-case complexity of BPGD is by reducing the
maximum number of variable nodes it is allowed to decimate. This can be
achieved by modifying line 4 in Algorithm 1 to “for $r=1$ to $R$ do”, where
$R<n$ represents a predefined limit on the number of decimation rounds. With
this modification, the worst-case complexity of BPGD becomes $O(RTn)$. In
Figure 4, we present the decoding performance of BPGD with $T=100$ and
different round limits $R$ for the $[[882,24,18\leqslant d\leqslant 24]]$ B1
code [16]. As expected, the performance of BPGD steadily improves with
increasing the round limit $R$. The optimal performance is attained when $R$
is equal to the block length $n=882$. This allows us to achieve a desired
trade-off between worst-case complexity and the BPGD decoding performance
tailored to a specific application requirement.

0.040.050.060.070.080.090.10$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$$p_{x}$Block
X Error Rate$[[882,24,18\leqslant d\leqslant 24]]$ B1 code [16]BPBPGD,
$T=100$, $R=2$BPGD, $T=100$, $R=5$BPGD, $T=100$, $R=10$BPGD, $T=100$,
$R=50$BPGD, $T=100$, $R=882$ Figure 4: Performance of B1 code [16] under BPGD
decoders with different decimation round limits $R$ over independent
Pauli-$\sigma_{x}$ errors.

###  4.6 Exploring the Role of Degeneracy with Randomized BPGD

For a degenerate QLDPC code, one reason for the non-convergence challenge
faced by the BP algorithm is that, for a given syndrome, there may exist
multiple low-weight error patterns that match the syndrome [30]. Note that
because of degeneracy, many of those error patterns differ only by a
stabilizer. Intuitively, this is supposed to help the decoder, as it
essentially yields the same decoding result by outputting any of those
answers. However, when running the BP algorithm, the locally operating
algorithm can get confused about the direction to proceed, resulting in non-
convergence [32]. In a case study presented in [30, Section IV. A], Poulin and
Chung explored this scenario for a two-qubit stabilizer code. A more
comprehensive study of this phenomenon from the perspective of trapping sets
can be found in the work by Raveendran and Vasić [32]. In another work, Kuo
and Lai [39] examined this situation by regarding BP as an energy-minimization
process, and explain non-convergence as being trapped in a local minimum of
the energy function.

Here, we devise an experiment to shed light on this situation for the
$[[882,24,18\leqslant d\leqslant 24]]$ B1 code [16]. Consider the following
randomized version of the BPGD algorithm. In each round, instead of decimating
the most reliable variable node, we first identify the top few reliable
variable nodes, and then randomly select one of them for decimation.
Concretely, this randomized decimation process is executed as follows. In the
$r$-th round, denote $V_{u}$ as the set of variable nodes that have not yet
been decimated. After BP with $T$ iterations, we first find the most reliable
variable node in $V_{u}$ and denote its reliability as $\gamma_{\max}$. Then,
we construct a set $P$ including all the variable nodes $v_{i}\in V_{u}$ whose
reliability satisfies $\gamma(v_{i})\geqslant\gamma_{\max}-\gamma^{\prime}$.
Here, $P$ is a set consisting of many selected reliable variable nodes
prepared for random decimation, and $\gamma^{\prime}$ represents a positive
reliability gap such that the reliability threshold for the inclusion of an
$v_{i}$ in $P$ is $\gamma_{\max}-\gamma^{\prime}$. Note that $|P|\geqslant 1$
since $P$ always includes the most reliable variable node in $V_{u}$. After
constructing $P$, we randomly select a variable node in $P$ for decimation.
The pseudo-code for this randomized BPGD algorithm, denoted as BPGD-rd, is
presented in Algorithm 2. The differences between this algorithm and the BPGD
in Algorithm 1 regarding the randomized decimation process are shown in lines
10-12 in Algorithm 2.

Input: Tanner graph $G=(V,C,E)$ for $H_{1}$, block length $n$, syndrome
$s_{x}$, Pauli-$\sigma_{x}$ error rate $p_{x}$, number of iterations per round
$T$, reliability gap $\gamma^{\prime}$

Output: $\widehat{E}$ or non-convergence

1 $\mu_{v_{i}}=\log((1-p_{x})/p_{x})$ for all $v_{i}\in V$

2 $m^{(0)}_{v_{i}\rightarrow c_{j}}=\mu_{v_{i}}$ for all $v_{i}\in
V,c_{j}\in\partial v_{i}$ // BP initialization

3 $V_{u}=V$ // the set of undecimated variable nodes

4 for  _$r=1$ _to_ $n$_ do

5 run $T$ iterations of BP with the sum-product algorithm

6 $\widehat{x}\leftarrow$ hard values for the variable nodes

7 if  _$\widehat{x}H_{1}^{T}=s_{x}$_ then

8 return _$\widehat{E}=D(\widehat{x},0)$_

9 else

10 $\gamma_{\max}=\max_{v_{i}\in V_{u}}\gamma(v_{i})$

11 $P=\\{v_{i}\in
V_{u}\;|\;\gamma(v_{i})\geqslant\gamma_{\max}-\gamma^{\prime}\\}$

12 randomly select $v_{i}$ from $P$ // Decimate a random variable node in $P$

13 if  _$m_{v_{i}}^{(rT)}\geqslant 0$_ then

14 $\mu_{v_{i}}=\text{llr}_{\max}$

15 else

16 $\mu_{v_{i}}=-\text{llr}_{\max}$

17 $V_{u}=V_{u}\backslash\\{v_{i}\\}$

18

return _non-convergence_

Algorithm 2 Binary belief propagation with randomized guided decimation (BPGD-
rd) over Pauli-$\sigma_{x}$ errors

The decoding outcome of BPGD-rd is inherently non-deterministic, due to the
random selection of variable nodes for decimation in each round. Therefore,
this process can potentially converge to many different error patterns.
Leveraging this property, we consider the following experiment for the B1 code
[16]. First, we select a Pauli-$\sigma_{x}$ error pattern denoted as
$E_{x}=D(x,0)$, with $\mathrm{wt}(E_{x})=73$. This error pattern is randomly
generated through an independent Pauli-$\sigma_{x}$ error channel with
$p_{x}=0.08$. Then, we run the BPGD-rd algorithm 10000 times to decode the
syndrome of $E_{x}$ over the Pauli-$\sigma_{x}$ errors, each with a distinct
seed for the random decimation process. The configuration for BPGD-rd during
this experiment includes $T=10$ for the number of BP iterations per round,
$p_{x}=0.08$ for the Pauli-$\sigma_{x}$ error probability,
$\text{llr}_{\max}=25$, and $\gamma^{\prime}=1.0$ for the reliability gap.

index | frequency | weight | distance to $E_{x}$ | index | frequency | weight | distance to $E_{x}$
---|---|---|---|---|---|---|---
1 | 2944 | 73 | 22 | 6 | 110 | 73 | 26
2 | 2727 | 73 | 26 | 7 | 91 | 73 | 16
3 | 1560 | 73 | 20 | 8 | 68 | 73 | 20
4 | 1521 | 73 | 16 | 9 | 66 | 73 | 24
5 | 125 | 73 | 30 | 10 | 32 | 75 | 28
Table 2: A list of 10 most frequent error patterns obtained out of 10000 BPGD-
rd decoding runs for the B1 code [16] for a Pauli-$\sigma_{x}$ error $E_{x}$
of weight 73.

We observe that out of those 10000 BPGD-rd decoding runs, 9568 of them result
in convergence. Within these 9568 convergent cases, we identify a total of 111
distinct error patterns, whose weights range from 73 to 87. Table 2 shows the
10 most frequent error patterns along with their weights and distances
relative to the channel error $E_{x}$. Notably, all 111 error patterns differ
from $E_{x}$ by a stabilizer, which means that all the convergent cases decode
the syndrome successfully due to degeneracy. If we run the original BPGD
algorithm in Algorithm 1 to decode the syndrome of $E_{x}$, it converges to
the error pattern with index 2 in Table 2.

The significance of this experiment is two-fold: On one hand, we show that for
the syndrome decoding problem of a degenerate QLDPC code such as the B1 code,
there can be multiple low-weight error patterns that all match the input
syndrome, confusing the BP decoding process. In particular, for decoding
$E_{x}$ in this experiment, BP itself with the sum-product algorithm would
indeed have resulted in non-convergence. On the other hand, we also show that
by combining BP with guided decimation, we can break the symmetry and force
convergence towards one of those error patterns as the decoding output. In
this case, degeneracy plays to our advantage since decoding is successful no
matter which of 111 error patterns is the winner.

Here we make some additional remarks regarding this experiment. Firstly, it
can be observed that the distribution of the error patterns upon convergence
in the BPGD-rd algorithm is not uniform. We can see from Table 2 that, for the
syndrome decoding problem we investigated in this experiment, a significant
portion of the convergent cases focuses on four specific weight-73 error
patterns, as denoted by indices 1-4 in Table 2. In comparison, the original
weight-73 channel error $E_{x}$ does not even appear among those 111 observed
error patterns.

Secondly, we note that, due to the random decimation process inherent to BPGD-
rd, the results presented in this section are the product of a single
simulation run of this experiment. A repeat of the same experiment could yield
different numerical results. Additionally, the outcomes depend on the specific
choice of the channel error $E_{x}$. However, we observe that the phenomenon
of multiple distinct error patterns matching the input syndrome and the uneven
distribution among convergent error patterns appears to be a general
characteristic of the BPGD-rd algorithm.

##  5 Quaternary Belief Propagation with Guided Decimation

In this section, we discuss the syndrome decoding problem for the depolarizing
channel with physical error rate $p$, referring to Section 2.3, and present a
natural extension of the binary BPGD algorithm that gives the quaternary
version. Here, we represent the Pauli error as a random quaternary vector $Q$
with its realization $q=(q_{1},q_{2},\ldots,q_{n})\in\\{0,1,2,3\\}^{n}$, with
$0,1,2,3$ representing the absence of error, or the presence of a Pauli
$\sigma_{x}$, $\sigma_{y}$ or $\sigma_{z}$ error, respectively. We define the
Pauli error represented by $q$ as $E(q)$. For example,

$E(q=(1,0,2,3,0))=\sigma_{x}\otimes I\otimes\sigma_{y}\otimes\sigma_{z}\otimes
I.$ (22)

We also define $x_{q},z_{q}\in{\mathbb{F}}_{2}^{n}$ as the length-$n$ binary
vectors such that $E(q)=D(x_{q},z_{q})$. For $q=(1,0,2,3,0)$ in the above
example, we have

$x_{q}=(1,0,1,0,0),\quad z_{q}=(0,0,1,1,0).$ (23)

For the depolarizing channel, we consider the quaternary BP (Q-BP) algorithm,
first discussed in [30], that jointly decode the depolarizing noise by
considering correlations between Pauli-$\sigma_{x}$ and Pauli-$\sigma_{z}$
errors. Notably, Q-BP demonstrates better performance over depolarizing noise
compared with decoding Pauli-$\sigma_{x}$ errors and Pauli-$\sigma_{z}$ errors
separately with binary BP, as exemplified in [16, Figure 5].

To run the Q-BP algorithm for a CSS code, we need to construct a Tanner graph
$G=(V,C,E)$ similar to the binary BP. However, here $C$ contains check nodes
representing both the $\sigma_{x}$-stabilizers in $G_{2}$ and the
$\sigma_{z}$-stabilizers in $H_{1}$, where $H_{1}$ and $G_{2}$ are submatrices
of $H_{x}$ and $H_{z}$, respectively, as shown in (8). An illustrative example
for the $[[7,1,3]]$ Steane code with

$G_{2}=H_{1}=\begin{bmatrix}1&1&1&0&1&0&0\\\ 0&1&1&1&0&1&0\\\
0&0&1&0&1&1&1\end{bmatrix}$ (24)

is presented in Figure 5, where the red check nodes in $C$ represent the
$\sigma_{x}$-stabilizers, whose syndrome bits are computed as
$s_{x}=x_{q}H_{1}^{T}$, and the blue check nodes in $C$ represent the
$\sigma_{z}$-stabilizers, whose syndrome bits are computed as
$s_{z}=z_{q}G_{2}^{T}$.

$v_{1}$$\mu_{v_{1}}$$v_{2}$$\mu_{v_{2}}$$v_{3}$$\mu_{v_{3}}$$v_{4}$$\mu_{v_{4}}$$v_{5}$$\mu_{v_{5}}$$v_{6}$$\mu_{v_{6}}$$v_{7}$$\mu_{v_{7}}$$c_{x,1}$$s_{x,1}$$c_{x,2}$$s_{x,2}$$c_{x,3}$$s_{x,3}$$c_{z,1}$$s_{z,1}$$c_{z,2}$$s_{z,2}$$c_{z,3}$$s_{z,3}$channel
messagesvariable nodes in $V$check nodes in $C$syndrome Figure 5: Tanner graph
for the $[[7,1,3]]$ Steane code

After constructing the Tanner graph, we can run the Q-BP algorithm by
iterative doing check node and variable node updates similar to the binary BP,
except that the channel message $\mu_{v_{i}}$ is now initialized as

$\mu_{v_{i}}=(1-p,\,p/3,\,p/3,\,p/3),$ (25)

and each variable node $v_{i}\in V$ contain the information for four
probabilities $(p_{v_{i},0},p_{v_{i},1},p_{v_{i},2},p_{v_{i},3})$. After a
sufficient number of message-passing iterations, those four probabilities
approximate the marginal probabilities for $Q_{i}$ in the quaternary error
vector $Q=(Q_{1},Q_{2},\ldots,Q_{n})$ conditioned on the syndrome event $S=s$
as

$p_{v_{i},j}\approx\Pr(Q_{i}=j\;|\;S=s),\qquad\text{ for }j\in\\{0,1,2,3\\}.$
(26)

With the four probabilities normalized with

$p_{v_{i},0}+p_{v_{i},1}+p_{v_{i},2}+p_{v_{i},3}=1,$ (27)

we define the reliability for the variable node $v_{i}$ as
$\gamma(v_{i})=\max\\{p_{v_{i},0},p_{v_{i},1},p_{v_{i},2},p_{v_{i},3}\\}$. A
detailed description of the message-passing updates of Q-BP and its
convergence condition is available in [61] and [31]. An efficient log domain
implementation of Q-BP has also been discussed in [62].

Similar to its binary counterpart, the Q-BP algorithm can also be improved by
guided decimation, denoted as the quaternary belief propagation guided
decimation (Q-BPGD) algorithm. After the $T$ iterations of BP in each round,
out of all the variable nodes we have not yet decimated, we pick the variable
node $v_{i}$ with the largest reliability $\gamma(v_{i})$ and decimate it by
changing its channel message as

$\mu_{v_{i}}=\begin{cases}(1-\epsilon,\epsilon,\epsilon,\epsilon),&\text{ if
}\underset{j\in\\{0,1,2,3\\}}{\arg\max}\;p_{v_{i},j}=0\\\
(\epsilon,1-\epsilon,\epsilon,\epsilon),&\text{ if
}\underset{j\in\\{0,1,2,3\\}}{\arg\max}\;p_{v_{i},j}=1\\\
(\epsilon,\epsilon,1-\epsilon,\epsilon),&\text{ if
}\underset{j\in\\{0,1,2,3\\}}{\arg\max}\;p_{v_{i},j}=2\\\
(\epsilon,\epsilon,\epsilon,1-\epsilon),&\text{ if
}\underset{j\in\\{0,1,2,3\\}}{\arg\max}\;p_{v_{i},j}=3\\\ \end{cases}.$ (28)

As $\epsilon$ approaches zero, this decimation rule fixes $Q_{i}$ to one of
the values among $0,1,2,3$ according to the bias of its corresponding variable
node $v_{i}$. In our implementation, we set $\epsilon=1\times 10^{-10}$ for
numerical stability. We repeat this process until either convergence is
reached at some round $r$, or until all the variable nodes have been
decimated. The pseudo-code for the Q-BPGD algorithm is presented in Algorithm
3.

Input: Tanner graph $G$, block length $n$, syndrome $s$, physical error rate
$p$, number of iterations per round $T$

Output: $\widehat{E}$ or non-convergence

1 $\mu_{v_{i}}=(1-p,\,p/3,\,p/3,\,p/3)$ for all $v_{i}\in V$

2 $V_{u}=V$ // the set of undecimated variable nodes

3 for  _$r=1$ _to_ $n$_ do

4 run $T$ iterations of Q-BP

5 $\hat{q}\leftarrow$ hard values for the variable nodes

6 if  _$\hat{q}$ matches the syndrome $s$_ then

7 return _$\widehat{E}=E(\hat{q})$_

8 else

9 $v_{i}=\arg\max_{v\in V_{u}}\gamma(v_{i})$ // Decimate the most reliable
variable node in $V_{u}$

10 switch  _$\underset{j\in\\{0,1,2,3\\}}{\arg\max}\;p_{v_{i},j}$_ do

11 case  _$0$_ do $\mu_{v_{i}}=(1-\epsilon,\epsilon,\epsilon,\epsilon)$;

12 case  _$1$_ do $\mu_{v_{i}}=(\epsilon,1-\epsilon,\epsilon,\epsilon)$;

13 case  _$2$_ do $\mu_{v_{i}}=(\epsilon,\epsilon,1-\epsilon,\epsilon)$;

14 case  _$3$_ do $\mu_{v_{i}}=(\epsilon,\epsilon,\epsilon,1-\epsilon)$;

15

16 $V_{u}=V_{u}\backslash\\{v_{i}\\}$

17

return _non-convergence_

Algorithm 3 Quaternary belief propagation with guided decimation (Q-BPGD) over
depolarizing noise
0.040.050.060.070.080.090.10$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$Physical Error
Rate $p$Block Error Rate$[[180,10,15\leqslant d\leqslant 18]]$ A5 code
[16]Q-BPBP-OSD-10 [16, Figure 6]Q-BPGD, $T$ = 10 Figure 6: Performance of A5
code [16] over depolarizing noise.
0.040.050.060.070.080.090.10$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$Physical Error
Rate $p$Block Error Rate$[[882,48,16]]$ B2 code [16]Q-BPBP-OSD-0 [16, Figure
2]Q-BPGD, $T$ = 10 Figure 7: Performance of B2 code [16] over depolarizing
noise.

In Figure 6, we present simulation results for the Q-BPGD decoder with $T=10$
applied to the $[[180,10,15\leqslant d\leqslant 18]]$ A5 code proposed in
[16], over the depolarizing noise. Figure 6 also shows the performances of the
Q-BP decoder and the BP-OSD decoder with order 10 from [16, Figure 6]. For the
A5 code, Q-BPGD exhibits improved performance compared to Q-BP and similar
performance compared to BP-OSD with order 10.

In Figure 7, we also present the Q-BPGD performance with $T=10$ for the
$[[882,48,16]]$ B2 code [16]. The comparison includes both the Q-BP decoder
and the BP-OSD decoder with order 10 from [16, Figure 2]. For the B2 code,
Q-BPGD outperforms the BP-OSD decoder with order 0 in the high-error regime
but is surpassed by BP-OSD in the low-error-rate regime. We remark that
besides the BP-OSD performance that we have been using as the main comparison
benchmark in this paper, a very good decoding performance is also reported in
[39, Figure 13] for the B2 code using an adaptive version of BP with memory
over the depolarizing noise.

Asymptotically, the worst-case complexity of the Q-BPGD algorithm is the same
as the binary BPGD, which is $O(Tn^{2})$. However, for moderate block lengths,
Q-BPGD runs slower compared with binary BPGD, due to the computation of four
probabilities $(p_{v_{i},1},p_{v_{i},2},p_{v_{i},3},p_{v_{i},4})$ for every
variable node $v_{i}$ in each BP iteration. Our current software
implementation of Q-BPGD is slower than binary BPGD with incurring of
exponential and log functions, but we expect with approximation, the running
time of Q-BPGD is similar to that of binary BPGD. Furthermore, we remark that
the performance of Q-BPGD shown in Figure 6 and Figure 7 are also subject to
potential improvements by using other variants of Q-BP.

##  6 Conclusion

In this paper, we have introduced and evaluated the use of BPGD for decoding
QLDPC codes to encourage convergence. BPGD showed strong performance compared
with BP-OSD, and BP-SI under independent Pauli-$\sigma_{x}$ errors. To better
understand how BPGD boosts convergence, we have provided an alternative view
of the BP syndrome decoding setup for stabilizer codes as a sampling problem.
Furthermore, to understand the performance of BPGD for degenerate QLDPC codes,
we experimented with a randomized version of BPGD that helped illuminate the
role of degeneracy in syndrome decoding. Our experiments suggested that BPGD
performed well because degeneracy allows it to achieve successful decoding
along many different decimation paths. Furthermore, we have extended our
guided decimation from binary BP to quaternary BP, demonstrating competitive
performance compared to BP-OSD in the high-error-rate regime under
depolarizing noise.

## References

  * [1] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. Sloane, “Quantum error correction and orthogonal geometry,” _Physical Review Letters_ , vol. 78, no. 3, p. 405, 1997.
  * [2] A. R. Calderbank, E. M. Rains, P. M. Shor, and N. J. Sloane, “Quantum error correction via codes over GF(4),” _IEEE Transactions on Information Theory_ , vol. 44, no. 4, pp. 1369–1387, 1998.
  * [3] D. Gottesman, _Stabilizer codes and quantum error correction_. California Institute of Technology, 1997.
  * [4] A. Y. Kitaev, “Quantum computations: algorithms and error correction,” _Russian Mathematical Surveys_ , vol. 52, no. 6, p. 1191, 1997.
  * [5] ——, “Fault-tolerant quantum computation by anyons,” _Annals of physics_ , vol. 303, no. 1, pp. 2–30, 2003.
  * [6] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, “Topological quantum memory,” _Journal of Mathematical Physics_ , vol. 43, no. 9, pp. 4452–4505, 2002.
  * [7] M. H. Freedman, D. A. Meyer, and F. Luo, “${Z_{2}}$-systolic freedom and quantum codes,” _Mathematics of quantum computation, Chapman & Hall/CRC_, pp. 287–320, 2002.
  * [8] S. Bravyi, D. Poulin, and B. Terhal, “Tradeoffs for reliable quantum information storage in 2D systems,” _Physical review letters_ , vol. 104, no. 5, p. 050503, 2010.
  * [9] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, “Surface codes: Towards practical large-scale quantum computation,” _Physical Review A_ , vol. 86, no. 3, p. 032324, 2012.
  * [10] D. Horsman, A. G. Fowler, S. Devitt, and R. Van Meter, “Surface code quantum computing by lattice surgery,” _New Journal of Physics_ , vol. 14, no. 12, p. 123011, 2012.
  * [11] D. J. MacKay, G. Mitchison, and P. L. McFadden, “Sparse-graph codes for quantum error correction,” _IEEE Transactions on Information Theory_ , vol. 50, no. 10, pp. 2315–2330, 2004.
  * [12] 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.
  * [13] A. A. Kovalev and L. P. Pryadko, “Improved quantum hypergraph-product LDPC codes,” in _2012 IEEE International Symposium on Information Theory Proceedings_. IEEE, 2012, pp. 348–352.
  * [14] ——, “Quantum kronecker sum-product low-density parity-check codes with finite rate,” _Physical Review A_ , vol. 88, no. 1, p. 012311, 2013.
  * [15] J. Haah, “Local stabilizer codes in three dimensions without string logical operators,” _Physical Review A_ , vol. 83, no. 4, p. 042330, 2011.
  * [16] P. Panteleev and G. Kalachev, “Degenerate quantum LDPC codes with good finite length performance,” _Quantum_ , vol. 5, p. 585, 2021.
  * [17] S. Yang and R. Calderbank, “Quantum spatially-coupled codes,” _arXiv preprint arXiv:2305.00137_ , 2023.
  * [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,” in _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , 2021, pp. 1276–1288.
  * [19] N. P. Breuckmann and J. N. Eberhardt, “Balanced product quantum codes,” _IEEE Transactions on Information Theory_ , vol. 67, no. 10, pp. 6653–6674, 2021.
  * [20] P. Panteleev and G. Kalachev, “Quantum LDPC codes with almost linear minimum distance,” _IEEE Transactions on Information Theory_ , vol. 68, no. 1, pp. 213–229, 2021.
  * [21] ——, “Asymptotically good quantum and locally testable classical LDPC codes,” in _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , 2022, pp. 375–388.
  * [22] R. Gallager, “Low-density parity-check codes,” _IRE Transactions on information theory_ , vol. 8, no. 1, pp. 21–28, 1962.
  * [23] “Digital video broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for broadcasting, interactive services, news gathering and other broad-band satellite applications,” EN 302 307, European Telecommunications Standards Institute (ETSI).
  * [24] T. Richardson and S. Kudekar, “Design of low-density parity check codes for 5G new radio,” _IEEE Communications Magazine_ , vol. 56, no. 3, pp. 28–34, 2018.
  * [25] F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Factor graphs and the sum-product algorithm,” _IEEE Transactions on information theory_ , vol. 47, no. 2, pp. 498–519, 2001.
  * [26] M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Efficient erasure correcting codes,” _IEEE Transactions on Information Theory_ , vol. 47, no. 2, pp. 569–584, 2001.
  * [27] ——, “Improved low-density parity-check codes using irregular graphs,” _IEEE Transactions on information Theory_ , vol. 47, no. 2, pp. 585–598, 2001.
  * [28] T. J. Richardson and R. L. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding,” _IEEE Transactions on information theory_ , vol. 47, no. 2, pp. 599–618, 2001.
  * [29] T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke, “Design of capacity-approaching irregular low-density parity-check codes,” _IEEE transactions on information theory_ , vol. 47, no. 2, pp. 619–637, 2001.
  * [30] D. Poulin and Y. Chung, “On the iterative decoding of sparse quantum codes,” _arXiv preprint arXiv:0801.1241_ , 2008.
  * [31] 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.
  * [32] N. Raveendran and B. Vasić, “Trapping sets of quantum LDPC codes,” _Quantum_ , vol. 5, p. 562, 2021.
  * [33] Y.-J. Wang, B. C. Sanders, B.-M. Bai, and X.-M. Wang, “Enhanced feedback iterative decoding of sparse quantum codes,” _IEEE transactions on information theory_ , vol. 58, no. 2, pp. 1231–1241, 2012.
  * [34] A. Rigby, J. Olivier, and P. Jarvis, “Modified belief propagation decoders for quantum low-density parity-check codes,” _Physical Review A_ , vol. 100, no. 1, p. 012330, 2019.
  * [35] 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.
  * [36] X. Xiao, N. Raveendran, and B. Vasić, “Neural-net decoding of quantum LDPC codes with straight-through estimators,” in _in Proc. Information Theory and Applications Workshop (ITA)_ , 2019.
  * [37] S. Miao, A. Schnerring, H. Li, and L. Schmalen, “Neural belief propagation decoding of quantum LDPC codes using overcomplete check matrices,” in _2023 IEEE Information Theory Workshop (ITW)_. IEEE, 2023, pp. 215–220.
  * [38] J. Old and M. Rispler, “Generalized belief propagation algorithms for decoding of surface codes,” _Quantum_ , vol. 7, p. 1037, 2023.
  * [39] K.-Y. Kuo and C.-Y. Lai, “Exploiting degeneracy in belief propagation decoding of quantum codes,” _npj Quantum Information_ , vol. 8, no. 1, p. 111, 2022.
  * [40] J. Du Crest, M. Mhalla, and V. Savin, “Stabilizer inactivation for message-passing decoding of quantum LDPC codes,” in _2022 IEEE Information Theory Workshop (ITW)_. IEEE, 2022, pp. 488–493.
  * [41] M. Mézard, G. Parisi, and R. Zecchina, “Analytic and algorithmic solution of random satisfiability problems,” _Science_ , vol. 297, no. 5582, pp. 812–815, 2002.
  * [42] A. Montanari, F. Ricci-Tersenghi, and G. Semerjian, “Solving constraint satisfaction problems through belief propagation-guided decimation,” _arXiv preprint arXiv:0709.1667_ , 2007.
  * [43] A. Coja-Oghlan, “On belief propagation guided decimation for random $k$-SAT,” in _Proceedings of the twenty-second annual ACM-SIAM symposium on discrete algorithms_. SIAM, 2011, pp. 957–966.
  * [44] T. Filler and J. Fridrich, “Binary quantization using belief propagation with decimation over factor graphs of LDGM codes,” _arXiv preprint arXiv:0710.0192_ , 2007.
  * [45] V. Aref, N. Macris, and M. Vuffray, “Approaching the rate-distortion limit with spatial coupling, belief propagation, and decimation,” _IEEE Transactions on Information Theory_ , vol. 61, no. 7, pp. 3954–3979, 2015.
  * [46] A. Buchberger, C. Häger, H. D. Pfister, L. Schmalen, and A. G. i Amat, “Learned decimation for neural belief propagation decoders,” in _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2021, pp. 8273–8277.
  * [47] R. E. Blahut, _Algebraic Codes for Data Transmission_. Cambridge University Press, 2003, ISBN-10 0521553741.
  * [48] A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,” _Physical Review A_ , vol. 54, no. 2, p. 1098, 1996.
  * [49] A. Steane, “Multiple-particle interference and quantum error correction,” _Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences_ , vol. 452, no. 1954, pp. 2551–2577, 1996.
  * [50] P. Iyer and D. Poulin, “Hardness of decoding quantum stabilizer codes,” _IEEE Transactions on Information Theory_ , vol. 61, no. 9, pp. 5209–5223, 2015.
  * [51] E. Berlekamp, R. McEliece, and H. Van Tilborg, “On the inherent intractability of certain coding problems (corresp.),” _IEEE Transactions on Information Theory_ , vol. 24, no. 3, pp. 384–386, 1978.
  * [52] J. Pearl, “Reverend Bayes on inference engines: A distributed hierarchical approach,” in _Proceedings of the Second National Conference on Artificial Intelligence_ , 1982, pp. 133–136.
  * [53] ——, _Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Iinference (2nd ed.)_. San Francisco, CA: Morgan Kaufmann, 1988.
  * [54] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1,” in _Proceedings of ICC’93-IEEE International Conference on Communications_ , vol. 2. IEEE, 1993, pp. 1064–1070.
  * [55] R. J. McEliece, D. J. C. MacKay, and J.-F. Cheng, “Turbo decoding as an instance of Pearl’s “belief propagation” algorithm,” _IEEE Journal on selected areas in communications_ , vol. 16, no. 2, pp. 140–152, 1998.
  * [56] S. M. Aji and R. J. McEliece, “The generalized distributive law,” _IEEE transactions on Information Theory_ , vol. 46, no. 2, pp. 325–343, 2000.
  * [57] M. Mézard and G. Parisi, “The Bethe lattice spin glass revisited,” _The European Physical Journal B-Condensed Matter and Complex Systems_ , vol. 20, pp. 217–233, 2001.
  * [58] 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.
  * [59] E. Sharon, S. Litsyn, and J. Goldberger, “Efficient serial message-passing schedules for LDPC decoding,” _IEEE Transactions on Information Theory_ , vol. 53, no. 11, pp. 4076–4091, 2007.
  * [60] J. Goldberger and H. Kfir, “Serial schedules for belief-propagation: analysis of convergence time,” _IEEE Transactions on Information Theory_ , vol. 54, no. 3, pp. 1316–1319, 2008.
  * [61] K.-Y. Kuo and C.-Y. Lai, “Refined belief propagation decoding of sparse-graph quantum codes,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 1, no. 2, pp. 487–498, 2020.
  * [62] C.-Y. Lai and K.-Y. Kuo, “Log-domain decoding of quantum LDPC codes over binary finite fields,” _IEEE Transactions on Quantum Engineering_ , vol. 2, pp. 1–15, 2021.