# A Blindness Property of the Min-Sum Decoding for the Toric Code

Julien du Crest1, Mehdi Mhalla2, Valentin Savin3
1Université Grenoble Alpes, Grenoble INP, LIG, F-38000 Grenoble, France
2Université Grenoble Alpes, CNRS, Grenoble INP, LIG, F-38000 Grenoble, France
3Université Grenoble Alpes, CEA-Léti, F-38054 Grenoble, France

###### Abstract

Kitaev’s toric code is one of the most prominent models for fault-tolerant
quantum computation, currently regarded as the leading solution for
connectivity constrained quantum technologies. Significant effort has been
recently devoted to improving the error correction performance of the toric
code under message-passing decoding, a class of low-complexity, iterative
decoding algorithms that play a central role in both theory and practice of
classical low-density parity-check codes. Here, we provide a theoretical
analysis of the toric code under min-sum (MS) decoding, a message-passing
decoding algorithm known to solve the maximum-likelihood decoding problem in a
localized manner, for codes defined by acyclic graphs. Our analysis reveals an
intrinsic limitation of the toric code, which confines the propagation of
local information during the message-passing process. We show that if the
unsatisfied checks of an error syndrome are at distance $\geq 5$ from each
other, then the MS decoding is locally blind: the qubits in the direct
neighborhood of an unsatisfied check are never aware of any other unsatisfied
checks, except their direct neighbor. Moreover, we show that degeneracy is not
the only cause of decoding failures for errors of weight at least 4, that is,
the MS non-degenerate decoding radius is equal to $3$, for any toric code of
distance $\geq 9$. Finally, complementing our theoretical analysis, we present
a pre-processing method of practical relevance. The proposed method, referred
to as stabiliser-blowup, has linear complexity and allows correcting all
(degenerate) errors of weight up to 3, providing quadratic improvement in the
logical error rate performance, as compared to MS only.

##  1 Introduction

Message passing (MP) decoding stands as both the fundamental theoretical
reason behind the invention of classical LDPC codes (departing from previous
minimum distance centric constructions), and the key to their success and
widespread application in real-world systems. However, quantum LDPC codes are
known to be classically degenerate [1], thus the sparsity of their Tanner
graph does no longer fulfill its role of enabling efficient MP decoding, but
merely acts as an enabler for fault-tolerance (_e.g._ , fault-tolerant
syndrome extraction and fault-tolerant operations on logical qubits).
Consequently, a significant effort has been devoted over the last few years to
efficient decoding of quantum LDPC codes, by either combining the MP decoding
with a post-processing step [2, 3, 4, 5], and/or improving the MP decoding
performance itself [6, 7, 8, 9, 10].

Here, we consider the MP decoding of the Kitaev toric code [11], the planar
version of which is currently the dominant error-correction solution to
achieve fault-tolerance in large-scale quantum computers, especially for
connectivity constrained technologies [12]. Among the large class of quantum
LDPC codes, the toric code is also known to be the less responsive to MP, due
the the presence of weight-$2$ degenerate errors undecodable by vanilla MP
decoders, such as belief-propagation (BP)111We use BP for the MP decoding
using Bayesian rules to update the exchanged messages (also known as sum-
product). It performs the exact Bayesian inference on trees, but may be used
on more general graphical models. Note that BP is sometimes used (included in
some of the papers cited here) with the generic meaning of MP. or min-sum
(MS). Consequently, the logical error rate of these vanilla decoders scales as
$p^{2}$, where $p$ is the physical error rate, well behind the
$p^{\left\lceil\frac{d}{2}\right\rceil}$ scaling of a minimum distance
decoding (_i.e._ , correcting any error of weight
$\leq\left\lfloor\frac{d-1}{2}\right\rfloor$), where $d$ is the minimum
distance of the code. A few approaches proposed in the literature, such as BP
with memory [8], generalized BP [10], or neural-BP [13, 14], succeeded to
improve the logical error rate performance for small distance toric codes
($d\leq 9$), but they all failed to scale to larger distance codes. Precisely,
for $d\leq 9$, the above approaches may yield a logical error rate that scales
as $p^{\left\lceil\frac{d}{2}\right\rceil}$, but this scaling does not longer
improve with increasing minimum distance222The Adaptive BP with Memory (AMBP)
in [8] may improve the slope of the logical error rate curve beyond $d=9$,
which comes from the use of many MBP decoders (with different meta-parameter
values). Put differently, this improvement is attributable to a form of
decoding diversity, rather than the intrinsic error correction capacity of the
MBP decoder, which saturates at $d=9$ [8, Section 4.4]., indicating the
presence of undecodable errors of weight $5$. Here, we try to understand if
such difficulties come from an intrinsic limitation of the toric code itself,
hindering further improvement of MP-based decoding for $d>9$.

We consider binary MP decoding, corresponding to separate decoding of $X$ and
$Z$-type errors. The input of the decoder consists of the error syndrome and
the a priori _soft value_ of each qubit (_e.g._ , error probabilities or log-
likelihood ratio values). Decoding is carried out through an iterative
exchange of extrinsic messages between qubits and checks they participate in,
which is conveniently described via the Tanner graph representation of the
code. In this representation, messages are exchanged between neighboring qubit
and checks of the Tanner graph, and the iterative nature of the decoding
process is aimed at spreading the information globally. At each decoding
iteration, an a posteriori _soft value_ is computed for each qubit, based on
the collected messages, gradually improving the estimation of the error. In
the sequel, we shall simply use the terminology of a priori and a posteriori
value (omitting soft). For details on MP decoders we refer to [15].

Our goal is to understand how the information is spreading on the toric code,
and what is the maximum length it can travel. To provide a formal statement,
we first introduce the notion of local blindness of an MP decoder. Informally,
given an error syndrome $\mathbf{s}$ and an unsatisfied check $c$, _i.e._ ,
such that $\mathbf{s}(c)=1$, we consider a fake syndrome , having $c$ as the
only unsatisfied check (note that is not a valid error syndrome, since no
error can generate it). We say that the MP decoding of $\mathbf{s}$ is
_locally blind_ in the neighborhood of $c$, if running the MP decoding on the
error syndrome $\mathbf{s}$, or on the fake syndrome , yields the same a
posteriori value for any qubit $q$ neighboring $c$, and for any number of
decoding iterations. Put differently, at no iteration are the qubits
neighboring $c$ aware that it is not the only unsatisfied check of the
syndrome: the MP decoder fails to convey the information from the other
unsatisfied checks. Intuitively, this may happen when $c$ is too far away from
the other unsatisfied checks of the syndrome.

### Main Results

In this work, we focus on the MS decoding, with the conventional flooded
scheduling. The reason is twofold. First, MS is an MP decoding algorithm that
is aimed at solving the maximum likelihood (ML) decoding problem in a
_localized_ manner (see Section 2 for details). It actually succeeds in doing
so for codes defined by acyclic graphs. However, quantum LDPC codes (as well
as good classical LDPC codes) are defined by graphs with cycles, preventing
local information from being spread effectively, and causing a degradation of
the error correction performance with respect to ML decoding. Second, MS
presents a number of practical advantages, _e.g._ , low computational
complexity (only requires additions and comparisons) and robustness to low
precision arithmetic (_e.g._ , below $6$-bit messages), being the _de facto_
solution used in practical applications and hardware implementations [16].
Moreover, assuming a Pauli channel model for physical qubit errors, with $X$
and $Z$ errors decoded independently, MS does not need an a priori knowledge
of the channel $X,Y,Z$ error probabilities [4].

Our first result states that the local information exchange of the MS is not
spreading globally:

######  Theorem 1 (MS Local Blindness).

Consider an error syndrome $\mathbf{s}$ on a toric code, such that all the
unsatisfied checks are at distance at least 5 from each other. Then, under the
i.i.d. noise assumption, the MS decoding of $\mathbf{s}$ is locally blind in
the neighborhood of any unsatisfied check.

In particular, it follows that such a syndrome is undecodable by MS. Further,
we are interested in determining the smallest weight of an undecodable non-
degenerate error. We say that an error $\mathbf{e}$ is non-degenerate if it
generates a syndrome that cannot be generated by any other error
$\mathbf{e}^{\prime}\neq e$, such that $|e^{\prime}|\leq|e|$. For instance,
1-dimensional errors $\mathbf{e}$ of weight
$|e|\leq\left\lfloor\frac{d-1}{2}\right\rfloor$ and generating a syndrome of
weight $2$ are non-degenerate. But some 2-dimensional errors may also be non-
degenerate.

Before introducing the next Theorem, we refine the classical notion of
decoding radius (i.e., the largest integer $\omega$, such that any error of
weight $\leq\omega$ is decoded correctly), by introducing the non-degenerate
decoding radius, which only takes into account non-degenerate errors.

######  Theorem 2 (MS Non-Degenerate Decoding Radius).

For any toric code of distance $\geq 9$, the non-degenerate decoding radius of
the MS is 3.

We give formal proofs of Theorems 1 and 2, based on the formalism of decoding
trees. We also conjecture that Theorem 1 holds for the normalized MS decoder,
irrespective of the normalization factor (note also that for an appropriate
choice of the normalization factor, the normalized MS provides a good
approximation of BP). Although the proof techniques we use do not translate
directly to normalized MS, we provide numerical evidence to corroborate our
conjecture.

Finally, we propose a method to remove low-weight degeneracy on the toric
code, which naturally complements the above analysis. Although the toric code
is know to be the hypergraph product code of two classical repetition codes
[17], on which the MS decoding radius is equal to
$\left\lfloor\frac{d-1}{2}\right\rfloor$, the decoding radius of the MS on the
toric code is only equal to 1, and the essence of Theorem 2 is that even the
non-degenerate decoding radius is no greater than $3$. We propose a new pre-
processing that runs in linear time and allows correcting all (degenerate)
errors of weight up to $3$ thus improving the decoding radius of the MS to 3.
We refer to this pre-processing step as stabiliser-blowup (SB), and it amounts
to applying a change of variable that locally removes the degeneracy to allow
the decoder to converge. We formally prove the following Theorem.

######  Theorem 3 (Stabilizer Blowup Pre-Processing).

SB+MS is able to correct all errors of weight up to 3 on a toric code of
distance $\geq 7$.

It follows that the SB+MS yields a quadratic improvement in the logical error
rate performance, as compared to MS only. In particular, it can be applied to
quadratically reduce the number of calls to a possible post-processing step,
which remains a must333According to the limited performances of state of the
art MS improvements, of which the poor performances are likely being explained
by the local blindness property from Theorem 1. for the MS-based decoding of
toric codes of minimum distance $d\geq 9$.

##  2 Preliminaries

###  2.1 The Decoding Problem

In the rest of the paper, we will restrict ourselves to a simple setup:
decoding independent and identically distributed (i.i.d.) $X$ errors on the
toric code. In this noise model, the a priori values of all qubits are the
same, and only depend on the probability of $X$ error on each qubit.
Everything said here also applies to $Z$ errors.

Since the toric code is a CSS code, the maximum likelihood444Here we only
discuss the ML decoding of quantum codes and not the quantum ML decoding,
where one is interested in decoding the most likely equivalence class of
errors. This simplification of the problem makes sense in the rest of the
paper since our goal is to show that the decoder is unable to decode even
constant sized errors, so we are not so much concerned about logical errors,
but rather about decoding failures (inability to output a valid correction).
(ML) decoding of $X$ errors can be stated as: for a matrix $\mathbf{H}$, and a
syndrome $\mathbf{s}$, find the most likely error $\tilde{e}$ such that
$\mathbf{H}\tilde{e}=\mathbf{s}$. Assuming an i.i.d. noise model, finding the
most likely error is equivalent to finding the error of smallest weight.

A tie occur in the ML decoding if there are several smallest weight (or in the
general setting, most likely) errors satisfying the syndrome. If the decision
is taken globally, the ML decoder may output either the list of all such
errors, or any one of them (e.g., randomly chosen). This is no longer possible
for decoders based on local decisions, such as MP decoders, where each qubit
is decided based on local information. In this case, it is more convenient to
consider the following _localized_ version of the ML decoder. For a matrix
$\mathbf{H}$, a syndrome $\mathbf{s}$, and a qubit $q$: if all the smallest
weight errors satisfying the syndrome agree on qubit $q$, that is, $\exists
a\in\\{0,1\\}$, such that $\mathbf{e}(q)=a$ for any smallest weight
$\mathbf{e}$ satisfying $\mathbf{H}\mathbf{e}=\mathbf{s}$, then set
$\tilde{\mathbf{e}}(q)=a$; otherwise, set $\tilde{\mathbf{e}}(q)$ to a random
value in $\\{0,1\\}$. Obviously, if there is only one smallest weight error
satisfying the syndrome, then both the ML and its localized variant output
this error. Otherwise, the error outputted by the localized ML may actually
not satisfy the given syndrome.

###  2.2 Degenerate Errors

For a given syndrome $\mathbf{s}$, we write $\mathbf{s}(c)$ to denote the
value of $\mathbf{s}$ on check $c$. If $\mathbf{s}(c)=1$, we say that check
$c$ is unsatisfied, otherwise we say it is satisfied.

The notions of degenerate syndrome and degenerate error, introduced below,
capture the fact that there may be several errors of minimal weight explaining
a given syndrome. Such a syndrome would intuitively be hard to decode, since
it would be difficult for the decoder to arbitrate between those errors, as it
is a classical decoder, not aware of the degeneracy of the code.

For a given parity-check matrix $\mathbf{H}$, for any syndrome $\mathbf{s}$,
we denote by $\mathcal{E}(\mathbf{s})$ the set of errors satisfying this
syndrome.

$\mathcal{E}(\mathbf{s})=\\{\mathbf{e}\enskip|\mathbf{H}\mathbf{e}=\mathbf{s}\\}$

Moreover, we denote by $|e|$ the (Hamming) weight of an error $e$, and define
$\mathcal{E}_{\min}(S)$ as the subset of errors of minimal weight.

$\mathcal{E}_{\min}(\mathbf{s})=\\{\mathbf{e}\in\mathcal{E}(\mathbf{s})\mid|\mathbf{e}|=\min_{\mathbf{e}^{\prime}\in\mathcal{E}(\mathbf{s})}|\mathbf{e}^{\prime}|\\}$

######  Definition 1.

A syndrome $S$ is said degenerate if $|\mathcal{E}_{\min}(\mathbf{s})|>1$.

######  Definition 2.

An error $\mathbf{e}$ is said degenerate if there exists
$\mathbf{e}^{\prime}\neq e$ such that $|e^{\prime}|\leq|e|$ and
$\mathbf{H}\mathbf{e}^{\prime}=\mathbf{H}\mathbf{e}$.

######  Lemma 1.

If $\mathbf{e}\in\mathcal{E}_{\min}(\mathbf{s})$, then $\mathbf{e}$ is
degenerate iff $\mathbf{s}$ is degenerate.

We also refine the classical notion of decoding radius to discuss more
precisely the decoding of non-degenerate errors.

######  Definition 3.

The non-degenerate decoding radius $\omega$, for a given decoder and code, is
the largest integer $\omega$ such that all non-degenerate errors of weight
$\leq\omega$ are correctly decoded.

###  2.3 The MS Decoder

For LDPC codes, the two main MP decoders used are the BP and the MS. On
acyclic graphs, the first solves the maximum a posteriori decoding problem,
while the second solves the _localized_ ML decoding problem, discussed above
(see also [15]). Algorithmically, they both function by iteratively exchanging
messages on the Tanner graph of the code. Although they are usually described
in an algorithmic way, by specifying the functions used to compute the
exchanged messages, they can be alternatively described by means of decoding
(or computation) trees, introduced by Wiberg [15], which is more convenient
for our purposes. We refer to [15] for the algorithmic description and the
definition of the decoding tree in the general setting, and provide below the
definition of the decoding tree for the particular case of the toric code.

It is straightforward to see that the localized ML corrects all the non-
degenerate errors, and fails (with high probability555Since ties are resolved
randomly in the localized ML, there is a non-zero probability that such random
choices yield a valid minimum-weight explanation of the syndrome.) on the
degenerate ones. Although the MS decoder aims at solving the localized ML
decoding problem, we show in this paper that it fails even to decode some non-
degenerate errors of small weight on the toric code. However, counter
intuitively, the MS is also able to correct some degenerate errors. A
discussion on the decoding of degenerate errors by the MS on the toric code
can be found in Appendix A.

###  2.4 The Decoding Tree of the Toric Code

We represent the toric code as a square tiling of the torus, i.e., a two-
dimensional square lattice with periodic boundaries, where the qubits are
located on the edges, the $Z$ checks on the vertices, and the $X$ checks or
the plaquettes. Note that the definition of $X$ and $Z$ checks is reversed by
considering the dual lattice. Thus, we shall only consider here one type of
checks, and we assume they are located on the vertices of the lattice. A toric
code is depicted in Figure 1(a) (or see [11] for a formal introduction).

For the graph representation of the toric code, and more generally for any
graph $G=(V,E)$, we use the notation $\mathcal{N}(\enskip)$ to refer to the
set of edges incident to a vertex, or the set of vertices incident to an edge,
clear from the context:

$\mathcal{N}(v)=\\{e\in E\mid e\text{ incident to
}v\\},\qquad\mathcal{N}(e)=\\{v\in V\mid v\text{ incident to }e\\}$

As mentioned above, the MS algorithm converges to a localized ML decision if
the Tanner graph of the code is a tree [15]. This is not true if the Tanner
graph contains cycles, however, there is a neat way to explicitly compute the
a posteriori value that the MS will output for every qubit at every iteration,
using the notion of minimal configurations on decoding trees. Those ideas
where first presented in [15], and we quickly review here what will be
necessary for the proofs of the next section.

((a)) Square tiling of the torus

((b)) Decoding tree $\mathcal{T}_{i,q}$ of qubit $q$ at iteration $i=3$

Figure 1: Decoding tree of the toric code. (a) Toric code defined by a square
lattice with periodic boundaries. Checks are represented by squares, placed on
the lattice vertices, and qubits are represented by edges. (b) The decoding
tree of qubit $q$ is shown for three decoding iterations. A check $c$ from the
original lattice may have several associated vertices in the decoding tree,
denoted as $v_{c}$, $v^{\prime}_{c}$. Similarly, each qubit from the original
lattice may have several associated edges in the decoding tree (e.g., the edge
$(v_{1},v_{2})$ and one of the dangling edges of $v^{\prime}_{2}$ are both
associated with the qubit incident to checks $1$ and $2$ in the original
lattice). We consider the decoding tree as being rooted in the edge $e_{q}$,
associated with qubit $q$ from the original lattice (see main text).

For a given qubit $q$, one may recursively trace back through time the
computation of its a posteriori value, by examining the updates that have
occurred. This trace back will form a tree graph rooted at $q$ and consisting
of interconnected qubit and checks in the same way as in the original graph,
but the same qubit or checks may appear at several places in the tree because
of the loopy structure of the decoding graph. For toric codes, checks are
represented by vertices of a square lattice, while qubits are represented by
edges (Figure 1(a)). Accordingly, the decoding tree of the toric code will
have vertices and edges representing, respectively, checks and qubits at
different decoding iterations. Decoding trees can be formally defined by using
the notion of walk without return, introduced below.

######  Definition 4.

A walk $W$ in a graph $G=(V,E)$ as a sequence of edges $W=e_{1}e_{2}\dots
e_{k}$, for which there exists a sequence of vertices $v_{1}v_{2}\dots
v_{k+1}$, such that

$e_{i}=(v_{i},v_{i+1}),\quad\forall i\in\\{1,k\\}.$

We say that $W$ is a walk without return (wwr) if $\enskip v_{i}\neq
v_{i+2},\enskip\forall i\in\\{1,\ldots,k-1\\}$. The length $|W|$ of a walk is
the number of edges it contains.

######  Definition 5.

A path is a walk such that all edges are distinct.

######  Definition 6.

(For the toric code) The decoding tree $\mathcal{T}_{i,q}$ is composed of all
the wwr of length $i$ in the toric code lattice, starting with edge $e_{q}$
(associated to qubit $q$).

When necessary, we also subscript the vertices with the name of the associated
check, so $u_{c}\in V(\mathcal{T}_{i,q})$ is a vertex in $\mathcal{T}_{i,q}$
associated to check $c$.

A decoding tree is illustrated in Figure 1(b). Note that we consider this tree
as being rooted in the edge $e_{q}$, and that it ends with dangling edges
(defined below). Technically, we could insert a qubit vertex on each edge,
such that the decoding tree would be rooted in a qubit vertex, and terminated
with qubit vertices. We will not do this here, and will rather stick to the
usual convention for toric codes, where qubits are represented by edges.
Remark that since a decoding tree is defined by walks without return, each
vertex $u$ has exactly 3 children (see Figure 1(b)).

######  Definition 7.

A dangling edge of $\mathcal{T}_{i,q}$ is an edge $e$ such that
$|\mathcal{N}(e)|=1$.

In the context of decoding trees, we naturally extend the definitions of walk,
walk without return and path, that can now eventually start/end with dangling
edges.

######  Definition 8.

The distance between two vertices in $\mathcal{T}_{i,q}$ is the length of the
path (the number of edges) from one to the other. The distance of a vertex to
the bottom is the minimum over the length of all paths that start with that
vertex and end with a dangling edge.

Since the graph representation of the toric code contains loops, several
vertices/edges in the decoding tree may be associated to the same check/qubit
of the toric code. Therefore, we extend the notation of the syndrome to
vertices of $\mathcal{T}_{i,q}$ as: $\mathbf{s}(v_{c})=\mathbf{s}(c),\forall
v_{c}\in V(\mathcal{T}_{i,q})$.

######  Definition 9.

For a decoding tree $\mathcal{T}_{i,q}$ and a syndrome $\mathbf{s}$, a
configuration is a function $C:E(\mathcal{T}_{i,q})\rightarrow\\{0,1\\}$ such
that:

$\sum_{e\in\mathcal{N}(v)}C(e)=\mathbf{s}(v)\bmod 2,\enskip\forall v\in
V(\mathcal{T}_{i,q})$

If $C(e)=1$, the edge $e$ is said to be labeled otherwise it is unlabeled.

Additionally, we are interested to know the labeling of the root edge of the
tree, and will call a root-labeled configuration $C_{\bullet}$ if
$C_{\bullet}(e_{q})=1$ and a root-unlabeled configuration $C_{\circ}$ if
$C_{\circ}(e_{q})=0$.

######  Definition 10.

We define the  weight  of a configuration as:

$|C|=\sum_{e\in E(\mathcal{T}_{i,q})}C(e)\quad\in\mathbb{N}$

Let $\mathfrak{C}$ be the set of all configurations for decoding tree
$\mathcal{T}_{i,q}$ and syndrome $\mathbf{s}$. We write

$\mathfrak{C}=\mathfrak{C}_{\bullet}\cup\mathfrak{C}_{\circ}$

where $\mathfrak{C}_{\bullet}$ and $\mathfrak{C}_{\circ}$ are the subset of
root-labeled/unlabeled configurations. Theses sets are non-empty since it is
always possible to define a configuration starting from the root down to the
dangling edges.

######  Definition 11.

A minimal root-labeled/unlabeled configuration
$C_{\circ}^{*}$/$C_{\bullet}^{*}$ is a configuration such that

$|C_{\circ}^{*}|=\min_{C_{\circ}\in\mathfrak{C}_{\circ}}|C|\quad/\quad|C_{\bullet}^{*}|=\min_{C_{\bullet}\in\mathfrak{C}_{\bullet}}|C|$

For i.i.d. noise, all qubits have the same a priori value, which factors out
through all the MS decoding steps, and thus can be set to 1 (which amounts to
saying that the maximum likelihood error is the minimum weight one). This will
be implicitly assumed in the next theorem and throughout the rest of the
paper.

######  Theorem 4 ([15, Section 4.1] ).

For i.i.d. noise, and given minimal configurations $C_{\circ}^{*}$ and
$C_{\bullet}^{*}$ for the decoding tree $\mathcal{T}_{i,q}$ and syndrome
$\mathbf{s}$, the a posteriori value $\textsc{app}(q,i)$ computed by the MS
for qubit $q$ at iteration $i$ is given by
$\textsc{app}(q,i)=|C_{\bullet}^{*}|-|C_{\circ}^{*}|$.

##  3 The MS Limited Scope

In this section we prove Theorems 1 and 2. We first prove the first Theorem
that introduces all the ideas and is quite short and intuitive. Building on
the ideas of the first Theorem, together with some technical Lemmas, we then
show the second Theorem.

###  3.1 Theorem 1: MS Local Blindness

Consider an error syndrome $\mathbf{s}$, and let $c$ be an unsatisfied check,
_i.e._ , such that $\mathbf{s}(c)=1$. Let also denote the binary vector, such
that $\sc(c^{\prime})=\begin{cases}1,&\text{if $c=c^{\prime}$}\\\\[-4.30554pt]
0,&\text{otherwise}\end{cases}$.

Note that is not a valid error syndrome, as no error can generate it. If one
runs MS or any other MP decoder on , the decoder will run for infinitely many
iterations, without finding a valid explanation of the input “fake” syndrome .
We are interested in the a posteriori values computed by the decoder for the
qubits neighboring $c$. We denote by $\textsc{app}(q,i)$ the a posteriori
value of a qubit $q$ at iteration $i$, when the decoder is supplied with the
real error syndrome $\mathbf{s}$. Likewise, we denote by
$\textsc{app}^{c}(q,i)$ the a posteriori value of a qubit $q$ at iteration
$i$, when it is supplied with the fake error syndrome .

######  Definition 12.

Consider the MP decoding of a syndrome $\mathbf{s}$, and let $c$ be un
unsatisfied check. We say that the decoding of $\mathbf{s}$ is locally blind
in the neighborhood of $c$, if $\textsc{app}(q,i)=\textsc{app}^{c}(q,i)$, for
any qubit $q$ neighboring $c$, and any iteration $i\geq 0$.

We restate here our first Theorem. See 1

We will prove Theorem 1 by investigating the minimal configurations in the
decoding tree. We introduce first several definitions and prove some
preliminaries Lemmas, and delay the proof of Theorem 1 to Section 3.1.3.

####  3.1.1 Links and Alternating Chains

Below, we give a few definitions, and adapt some usual definitions in graph
theory to cope with the specificity of decoding trees (taking into account
dangling edges).

######  Definition 13.

A link is a path in the decoding tree such that its vertex endpoints (if they
exist) are associated with unsatisfied checks.

A link can have dangling edges as endpoints.

We call a proper link a link with both endpoints associated to unsatisfied
checks, and a dangling link a link where at least one of its endpoints is a
dangling edge. For short, we usually only give the vertex endpoints of a link.
Giving the endpoints of a proper link is enough to fully characterize it, so
we write $u{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v$. For a
dangling link, we write
$u{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}\\_$. Although this is not
enough to uniquely determine a dangling link (there exist many dangling links
with endpoint $u$), whenever this notation is used, it is always considered
that this is one of the possible dangling links of minimal length.

######  Definition 14.

Below we give a name to the 3 possible shapes of proper links of length 4 not
containing the root (see Figure 2):

  * •

The $I$-link going from an unsatisfied check 4 times down,

  * •

The $\Gamma$-link going once up then 3 times down,

  * •

The $\Lambda$-link going twice up then twice down.

For the $I$ and $\Gamma$ link, we naturally refer to the upper and lower
unsatisfied vertices relative to their depth in the tree.

((a)) $\Gamma$ link

((b)) $\Lambda$ link

((c)) $I$ link

Figure 2: The three different shapes of 4-link are depicted in bold. Square
vertices represent checks (black for unsatisfied and white for satisfied).
Note that in the following the bold notation will only be used to denote
labeled links.

######  Definition 15.

A labeled link is a link where all edges are labeled. An unlabeled link is a
link where at least one edge is unlabeled. From now on we use the notation  to
denote a labeled link, and  to denote an unlabeled link.

######  Definition 16.

An alternating chain is a walk in the tree consisting of a succession of links
alternating between labeled and unlabeled (see Figure 3). Subsequent links can
have overlapping edges.

Precisely, an alternating chain is a sequence of links
$L_{1},L_{2},\dots,L_{k}$ where

$\displaystyle\forall L_{i}=e_{1}\dots e_{k}v_{k},\enskip
L_{i+1}=v^{\prime}_{1}e^{\prime}_{1}\dots e^{\prime}_{k^{\prime}}:\qquad
v_{k}=v^{\prime}_{1}$ $\displaystyle L_{i},L_{i+1}\qquad\text{cannot be both
labeled or both unlabeled}$

Figure 3: An example of an alternating chain
$(\\_{\;\framebox[6.78122pt]{\rule{0.0pt}{3.87498pt}}\;}u_{3}\overset{\Lambda}{{\;\framebox[6.78122pt]{\rule{6.78122pt}{3.87498pt}}\;}}u_{2}{\;\framebox[6.78122pt]{\rule{0.0pt}{3.87498pt}}\;}u_{1}\overset{\Gamma}{{\;\framebox[6.78122pt]{\rule{6.78122pt}{3.87498pt}}\;}}v_{1}{\;\framebox[6.78122pt]{\rule{0.0pt}{3.87498pt}}\;}v_{2}\overset{I}{{\;\framebox[6.78122pt]{\rule{6.78122pt}{3.87498pt}}\;}}\\_)$
going from one dangling edge to another (Notice how the two edges above
$u_{2}$ are used twice, in
$u_{1}{\;\framebox[6.78122pt]{\rule{0.0pt}{3.87498pt}}\;}u_{2}$ and
$u_{2}{\;\framebox[6.78122pt]{\rule{6.78122pt}{3.87498pt}}\;}u_{3}$). Labeled
edges are depicted in bold. All three types of 4-links are depicted here, the
$\Lambda$ and $\Gamma$ links are proper, and the labeled $I$-link is dangling.

######  Lemma 2 (Walk Inversion Lemma).

Let $C$ be a configuration for a decoding tree $\mathcal{T}_{i,q}$ and
syndrome $\mathbf{s}$, and $W=e_{1}\dots e_{k}$ a walk in $\mathcal{T}_{i,q}$
such that both its endpoints are dangling edges. Let
$C^{\prime}:E(\mathcal{T}_{i,q})\rightarrow\\{0,1\\}$ be the map defined by

$\forall e\in E(\mathcal{T}_{i,q}),\,C^{\prime}(e)=(C(e)+(-1)^{n_{e}})/2\text{
where }n_{e}=|\\{e_{i}=e,e_{i}\in W\\}|$

Then $C^{\prime}$ is a configuration for $\mathbf{s}$. Put differently,
inverting the label of each edge as many times as it appears in the walk
preserves the property of being a configuration for a syndrome.

###### Proof.

Any vertex will touch an even number of edges (counting multiplicities) in
$W$. Hence inverting the labels as many times as they appear along $W$ will
keep the parity of all the vertices in the new configuration. ∎

####  3.1.2 Minimal Configurations in the MS Decoding Tree

In this section we prove the existence of minimal configurations with special
properties, which will be used later in the proof of Theorems 1 and 2.

######  Lemma 3 (4-links Lemma for root-unlabeled configuration).

Given a syndrome where all unsatisfied checks are at distance 4 or more from
one another, there exist a minimal configuration $C_{\circ}^{\leq 4}$ where
all labeled links are of length $\leq 4$.

###### Proof (Sketch)..

We give the proof for the existence of $C_{\circ}^{\leq 4}$ in the form of an
algorithm that takes any minimal configuration $C_{\circ}^{*}$ and transforms
it into a minimal configuration $C_{\circ}^{\leq 4}$ that satisfies the
condition that all labeled links are of length at most 4. The algorithm works
as follows: as long as there is a labeled link of length $\geq 5$, we find a
path from dangling edge to dangling edge containing it, then use Lemma 2 to
remove it. The path is chosen so that the new configuration stays minimal. The
details of the proof can be found in Appendix B.2 ∎

We now prove a similar statement for $C_{\bullet}$, but only for decoding
trees associated with any of the four qubits neighboring an unsatisfied
check666It can be shown that the statement does not hold for any other qubit..

######  Lemma 4 (4-link Lemma for root-labeled configuration).

Given a syndrome where all unsatisfied checks are at distance 4 or more from
one another, for a decoding tree $\mathcal{T}_{i,q}$ where $q$ is neighboring
an unsatisfied check $c$, there exists a minimal configuration
$C_{\bullet}^{\leq 4}$ where all labeled links are of length $\leq 4$.

###### Proof (Sketch)..

Starting with a minimal configuration $C_{\bullet}^{*}$, and using the
algorithm from the proof of Lemma 3, one can remove all the length $\geq 5$
labeled links not containing the root. Note that even if the algorithm could
be applied on a labeled link containing the root, this would yield an
unlabeled configuration which is not what we want. Supposing that there is a
labeled link containing the root of length $\geq 5$, it will also be removed
using the walk inversion Lemma, but the path used will be created differently.
The details of the proof can be found in Appendix B.3. ∎

######  Lemma 5.

Given a syndrome where all unsatisfied checks are all at distance at least 5,
and a configuration $C^{\leq 4}$ such that all labeled links are of length
$\leq 4$, then all proper labeled links have endpoints associated with a same
check $c$ (i.e., all proper links are of the form
$u_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v_{c}$ for some
unsatisfied check $c$).

###### Proof.

Since all labeled links are of length $\leq 4$ and all unsatisfied checks are
at distance $\geq 5$, any proper labeled link necessarily joins vertices
associated to the same check (by following a path around a plaquette of the
toric code). ∎

####  3.1.3 Proof of Theorem 1 (MS Local Blindness)

Using configurations from Lemma 3 and 4, and the property of the labeled links
from Lemma 5, we can now prove Theorem 1.

###### Proof.

Let $\mathbf{s}$ be a syndrome such that all the unsatisfied checks are at
distance $\geq 5$ from each others, $c$ be an unsatisfied check in
$\mathbf{s}$, and $q\in\mathcal{N}(c)$. Let be the fake syndrome (defined in
Section 3.1) where only $c$ is unsatisfied , and $\mathbf{s}^{\neq
c}=\mathbf{s}-\mathbf{s}^{c}$ (informally, we can think of $\mathbf{s}$ as the
disjoint union of $\mathbf{s}^{c}$ and $\mathbf{s}^{\neq c}$).

Let also $\mathcal{T}_{i,q}$ be the decoding tree associated to $q$ at
iteration $i$. On $\mathcal{T}_{i,q}$, we now consider some minimal
configurations $C_{\bullet},C_{\circ}$ associated to syndrome $\mathbf{s}$,
and ${C_{\bullet}^{c}},{C_{\circ}^{c}}$ associated to , such that all four
configurations satisfy Lemmas 3, 4, and 5. Now, considering $C_{\bullet}$ (the
same will hold for $C_{\circ}$), we define
${C_{\bullet}}_{|c},{C_{\bullet}}_{|\neq
c}:E(\mathcal{T}_{i,q})\rightarrow\\{0,1\\}$ where:

  * (i)

${C_{\bullet}}_{|c}$ is defined by the labeled links in $C_{\bullet}$ that
have all their vertex endpoints equal to $c$ (i.e., the proper labeled links
of the form $u_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v_{c}$
and the dangling labeled links of the form
$u_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}\\_$). Formally,

${C_{\bullet}}_{|c}(e)=1\iff e\in
u_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v_{c}\text{ or }e\in
u_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}\\_$

Clearly ${C_{\bullet}}_{|c}$ is a configuration for $\mathbf{s}^{c}$.

  * (ii)

${C_{\bullet}}_{|\neq c}$ is defined by the remaining labeled links (that is,
labeled links with endpoint(s) different from $c$). Alternatively,

${C_{\bullet}}_{|\neq c}=C_{\bullet}-{C_{\bullet}}_{|c}$

Using the fact that all proper links are between vertices associated to the
same check, it holds that ${C_{\bullet}}_{|\neq c}$ is a configuration for
$\mathbf{s}^{\neq c}$.

Since $C_{\bullet}$ is minimal, we conclude that ${C_{\bullet}}_{|c}$ is a
minimal root-labeled configuration for $\mathbf{s}^{c}$, and
${C_{\bullet}}_{|\neq c}$ is a minimal root-unlabeled configuration for
$\mathbf{s}^{\neq c}$.

Similarly, we can write $C_{\circ}$ as
$C_{\circ}={C_{\circ}}_{|c}+{C_{\circ}}_{|\neq c}$, where ${C_{\circ}}_{|c}$
is a minimal root-unlabeled configuration for $\mathbf{s}^{c}$, and
${C_{\circ}}_{|\neq c}$ is a minimal root-unlabeled configuration for
$\mathbf{s}^{\neq c}$. It follows that:

$|{C_{\bullet}}_{|\neq c}|=|{C_{\circ}}_{|\neq
c}|,\quad|{C_{\bullet}}_{|c}|=|{C_{\bullet}^{c}}|,\text{
and}\quad|{C_{\circ}}_{|c}|=|{C_{\circ}^{c}}|$

Therefore,

$\displaystyle\textsc{app}(q,i)$ $\displaystyle=|C_{\circ}|-|C_{\bullet}|$
$\displaystyle=|{C_{\circ}}_{|c}|+|{C_{\circ}}_{|\neq
c}|-(|{C_{\bullet}}_{|c}|+|{C_{\bullet}}_{|\neq c}|)$
$\displaystyle=|{C_{\circ}}_{|c}|-|{C_{\bullet}}_{|c}|$
$\displaystyle=|{C_{\circ}^{c}}|-|{C_{\bullet}^{c}}|$
$\displaystyle=\textsc{app}^{c}(q,i)$

So the blindness property is satisfied for any qubit $q$ neighboring $c$,
which concludes the proof of Theorem 1. ∎

######  Corollary 1.

Such a syndrome is undecodable by the MS

###### Proof.

The blindness property for Theorem 1 implies that each of the four qubits
around an unsatisfied check has the same same a posteriori value (thus the
same error estimate), at each iteration, as its horizontal/vertical symmetric.
Hence the parity of each unsatisfied check is never satisfied, for any number
of iterations, and as such, this syndrome is undecodable by the MS. ∎

Finally, we note that the blindness property can actually be proven for qubit-
to-check messages entering an unsatisfied check, the computation tree of such
a message being given by the either left of right half of the decoding tree in
Figure 1(b) (with root edge $e_{q}$ becoming a dangling edge). Consequently,
it also applies to check-to-qubit messages going out from an unsatisfied
check, since such outgoing messages only depend on the incoming ones.

###  3.2 Theorem 2 : MS Non-Degenerate Decoding Radius

We now go on to prove Theorem 2, which we restate here for the reader’s
convenience.

See 2

We first show that there exist weight 4 non-degenerate errors that are
undecodable by the MS. Specifically, we use the error consisting of 4
consecutive horizontal qubits in error, denoted by $\epsilon^{4}$, and
$\mathbf{s}^{4}$ its weight 2 syndrome. Note that this error can appear
anywhere on the code up to translation, and rotations. The proof follows the
ideas of Theorem 1. Since Lemmas 3 and 4 were shown for unsatisfied checks at
distance $\geq 4$, they automatically apply in the context of Theorem 2 for
syndrome $\mathbf{s}^{4}$. We only need to show a (weaker) analog of Lemma 5.

We then need to show that all weight $\leq 3$ non-degenerate errors are
decodable by the MS. This is done using exhaustive search for small codes, and
by reduction to localized errors by analysing the number of iterations needed
to decode.

####  3.2.1 Preliminary Lemmas

We now show the analog of Lemma 5, only this time the result is a little
weaker. But first we show a preliminary Lemma used in the proof.

######  Lemma 6.

For the syndrome $\mathbf{s}^{4}$, and for any decoding tree
$\mathcal{T}_{i,q}$ associated to qubit $q$ neighboring an unsatisfied check
$c$:

Let $u{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v$ be a $\Lambda$-link
in $\mathcal{T}_{i,q}$ and $S$ be the smallest subtree of $\mathcal{T}_{i,q}$
containing it, then for any vertex $w\in V(\mathcal{T}_{i,q})\setminus V(S)$
associated to an unsatisfied check,

$d(u,w)=d(v,w)\geq 6$

###### Proof.

Suppose there is a $\Lambda$-link
$u_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v_{c^{\prime}}$. We
now consider the corresponding walk without return between the checks $c$ and
$c^{\prime}$ on the toric code. There are two possibilities, either
$c=c^{\prime}$ (Figure 4(a)), or $c\neq c^{\prime}$ (Figure 4(b)). In any
case, let $g$ be the toric code check associated with the grandfather of
$u_{c}$ and $v_{c^{\prime}}$ in $\mathcal{T}_{i,q}$. On the toric code, let
$q$ and $q^{\prime}$ the qubits incident to $g$ on the related walks without
return to $c$ and $c^{\prime}$. Then any wwr from $g$ to $c$ or $c^{\prime}$
and starting with $q^{\prime\prime}\notin\\{q,q^{\prime}\\}$ is of length
$\geq 4$. Hence, any vertex associated to an unsatisfied check in
$V(\mathcal{T}_{i,q})\setminus S$ must be at distance $\geq 6$ from $u_{c}$
and $v_{c}^{\prime}$. ∎

((a)) $\Lambda$-link between two vertices associated to the same check,
visualized on the toric code.

((b)) $\Lambda$-link between two vertices associated to different checks,
visualized on the toric code.

Figure 4: The cases of $\Lambda$-link

The following corollary is a straight application of Lemma 6.

######  Corollary 2.

Under the hypothesis of Lemma 6, let
$u{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v$ be an $I$-link with $v$
being its the bottom endpoint. Then $v$ cannot belong to a $\Lambda$-link.

The following Lemma is a (weaker) analog of Lemma 5 for the syndrome
$\mathbf{s}^{4}$.

######  Lemma 7.

For the syndrome $\mathbf{s}^{4}$, and for any decoding tree
$\mathcal{T}_{i,q}$ associated to qubit $q$ neighboring an unsatisfied check
$c$, there exists a minimal configuration such that the endpoints of any $I$
or $\Gamma$ labeled link are vertices associated to the same check.

###### Proof.

Take a configuration having all labeled links of length $\leq 4$. Suppose
there is a labeled link between $u^{0}_{c}$ and $v^{0}_{c^{\prime}}$, and take
one deepest if there are several. If applying, always consider $u^{0}$ always
be on a higher level than $v^{0}$.

  * (i)

If this link is an $I$-link or a $\Gamma$-link, then there must exist an
unlabeled $I$-link
$u^{0}_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}u^{1}_{c}$ where
$u^{1}_{c}$ is at the same depth as $v^{0}$. Then set
$\mathcal{A}=\\{u^{1}_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}u^{0}_{c},u^{0}_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v^{0}_{c^{\prime}}\\}$
The link
$u^{0}_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}u^{1}_{c}$ must be
unlabeled as otherwise the link
$u^{1}_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{0}_{c}$ of
length $\geq 5$ would contradict the assumptions of Lemma 3.

  * (ii)

If the link contains the root edge $q$ (in case of a labeled configuration),
then there must also exists an unlabeled link
$u^{0}_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}u^{1}_{c}$ where
$u^{1}_{c}$ is at the same depth as $v^{0}$ using the same argument. Then set
$\mathcal{A}=\\{u^{1}_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}u^{0}_{c},u^{0}_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v^{0}_{c^{\prime}}\\}$.

Now complete this into an alternating chain from dangling edge to dangling
edge by doing the following iterative algorithm that satisfies the property:

  * $(P)$

At each iteration of the algorithm, the chain endpoints are at the same depth
on both sides

At a given iteration, suppose without loss of generality that $u^{i}$ came
from a labeled link and $v^{i}$ from an unlabeled link. Then pick one labeled
link from $v^{i}$ going down. There must be one and it must be unique since we
assumed this is a valid labeling, and by Lemma 6, this cannot be a labeled
$\Lambda$-link. Also pick an unlabeled link of the same type in the
neighborhood of $u^{0}$. There must exist one, otherwise this would give a
labeled link of length $\geq 5$.

This algorithm gives a path from dangling edge to dangling edge. Now inverting
this path will remove the link between $u^{0}_{c}$ and $v^{0}_{c^{\prime}}$
while maintaining exactly the same weight, hence keeping the minimality of the
configuration. ∎

####  3.2.2 Sketch of Proof of Theorem 2

To prove the blindness of the qubits around the unsatisfied checks of
$\mathbf{s}^{4}$, we cannot use the fact that all proper labeled links are
between copies of the same checks. Fortunately, the only time there can be a
proper labeled link
$u_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v_{c^{\prime}},\
c\neq c^{\prime}$, it must be a $\Lambda$-link. Using a notion of pruning of
the decoding tree, we are able to split the decoding tree into a pruned tree
where the only remaining unsatisfied vertices are associated to $c$, and
removed subtrees where there might still be vertices associated to $c$, but
with the guarantee (that will be the bulk of the proof) that there are no
labeled edges between the removed subtrees and the pruned tree. The details of
the proof can be found in Appendix C.2.

To show that all non-degenerate errors of weight $\leq 3$ are decodable, we do
it by a formal argument for codes of larger distance ($d\geq 18$) by
introducing the notion of $\delta$-local syndrome, and we verify it
numerically for smaller codes ($9\leq d<18$). We defer the proof to Appendix
C.3.

###  3.3 Conjectures about Normalized MS and BP

For Normalized MS (NMS), we conjecture that Theorems 1 holds for any
normalization factor in $]0,1[$. To support our claim, we did some numerical
testing for codes with minimum distance $d\in\\{11,24\\}$ (giving a “small”
and a “larger” code, odd and even size), normalization factor $\lambda$
between 0.0625 and 1, with a step of 0.0625, and for a maximum number of
decoding iterations equal to 100. Note that since the normalization factors
are sums of powers of two, we do not have to worry about numerical instability
and check equality up to floating point precision. Verifying the statement for
all error syndromes with all the unsatisfied checks at distance $\geq 5$ even
for reasonably small code sizes is not feasible, so we only tested syndromes
of weight 2, satisfying the condition that the two unsatisfied checks are at
distance $\geq 5$. Also to support even more our claim, we tested the syndrome
defined by $\mathbf{s}(c_{i,j})=1\iff j=5i\mod 13$ on toric codes of distance
$d=13$ (Figure 5) and $d=26$. This is a syndrome “packed” with as many
unsatisfied checks as possible, all at distance 5 or 6 from each other. In all
our numerical experiments, the blindness property is conserved.

Figure 5: Syndrome defined by $\mathbf{s}(c_{i,j})=1\iff j=5i\mod 13$ on a
toric code of distance $d=13$. Note that this is not a valid error syndrome
(as it is of odd weight), but it is only used to verify the blindness
property. For $d=26$ we get a valid error syndrome.

For BP, we know the blindness statement of Theorem 1 to be false, since BP
takes into account all the configurations in the decoding tree (for a given
syndrome), and not only a minimal one (see [15] for more details). However,
the minimal configurations are still somehow dominant in the a posteriori
reliabilities computed by the BP, so we wonder if a similar statement could be
made, perhaps using a relaxed notion of blindness. So far, our preliminary
numerical results suggest that syndromes satisfying the hypothesis of Theorem
1 are not decodable by BP, and moreover
$\displaystyle\lim_{i\rightarrow\infty}\left(\textsc{app}(q,i)-\textsc{app}^{c}(q,i)\right)=0$,
which is likely explained by the fact that minimal configurations become more
dominant as the decoding tree size increases.

##  4 Stabiliser-Blowup Pre-Processing

In Section 3, we made a point that there is more than just degeneracy
preventing the convergence of the MS, and that there is no hope to correct
adversarial errors of weight 4 or more on the toric code using MS. While all
the non-degenerate errors of weight $\leq 3$ are decodable by the MS (see
Appendix C.3), numerical simulations show that most degenerate errors are not
(see Appendix A for a detailed discussion). Here we present a new pre-
processing that runs in linear time and allows to correct all errors of weight
up to 3. The idea of the pre-processing is to infer where the decoder might
fail by looking at local degenerate syndromes. We then apply a code
modification, corresponding to a change of variables, that locally removes the
degeneracy to allow the decoder to converge.

###  4.1 The Stabiliser-Blowup Graph Modification

((a))

((b))

Figure 6: Stabiliser-blowup for degenerate errors of weight 2: the four edges
around the original plaquette are replaced by four new edges, connecting the
checks around the plaquette to a new check in the middle of the plaquette.
Labels $q_{i}$’s on the edges of the original plaquette are interpreted here
as binary random variables, equal to $1$ if the corresponding qubit is in
error, and $0$ otherwise. Each new edge is labeled by the sum of the $q_{i}$’s
incident to the same check. (a) The diagonal weight-2 syndrome, shown on the
original plaquette together with one of its possible explanations
($q_{1}=q_{2}=1$) on the left. After the blowup, the syndrome is uniquely
explained as $q_{4}+q_{1}=q_{2}+q3=1$. (b) The square weight-4 syndrome, shown
on the original plaquette together with one of its possible explanations
($q_{1}=q_{3}=1$). After the blowup, the syndrome is uniquely explained as
$q_{4}+q_{1}=q_{1}+q_{2}=q_{2}+q3=q_{3}+q_{4}=1$.

The stabiliser-blowup is a decoding graph modification that allows to locally
remove the degeneracy of the code around a plaquette. In the following, we use
it as a preprocessing to remove the degeneracy of degenerate weight 2 errors
(depicted in Figure 6) and degenerate weight 3 errors (depicted in Figure 7).

Figure 7: Stabiliser-blowup for degenerate errors of weight 3: an example of a
weight-3 degenerate error on the original toric code (generating a weight-2
syndrome) becoming a weight-3 non-degenerate error after the blowup.

We remove the four edges associated to the qubits around a given plaquette and
replace them by four new edges connecting the four corner checks of the
plaquette to an additional (satisfied) check in the middle. Each new edge
corresponds to the parity of the two removed edges around a given check. Thus,
the sum of the four new edges must be even, hence the addition of the
satisfied middle check connecting them. We later show that any solution
satisfying the syndrome on the modified graph will easily yield a valid
solution for the original graph, and this solution is unique up to stabiliser
equivalence. As a remark, this code change should not be applied on two
neighboring plaquettes, as this would create new degeneracy issues between
them (see Figure 8). Therefore, we use the stabiliser-blowup as a pre-
processing, and only apply the blowup where the error syndrome suggests that
degeneracy issues might occur. One could ask why those local degeneracy issues
are not directly solved “by hand” as a pre-processing, by assigning a fixed
value to one of the qubits thus removing the degeneracy. But this could lead
to a degradation of the decoding by systematically increasing the weight of
the outputted error, thus increasing the likelihood of logical errors, so we
instead rely on the MS to decide on the error pattern.

Figure 8: Stabiliser-blowup on adjacent plaquettes leads to undecodable
weight-1 errors: the weight-1 error on the original toric code becomes a
weight-2 degenerate error after the blowup.

###  4.2 The Algorithm

In order to correct all errors of weight $\leq 3$, it is enough to consider
the syndromes of _local_ degenerate errors of weight 2 and 3. Whenever one of
those patterns appears around a plaquette, we do the blowup, except if an
adjacent plaquette (sharing an edge) is already blown-up.

To remove all errors of weight $\leq 3$, we use the following greedy
heuristic: We go through all plaquettes in the lexicographical order of their
coordinates. We do this three times, corresponding to steps (i) (ii) (iii)
below, each time checking for a different set of patterns. If one of the
patterns looked for at this step is found in the neighborhood of a plaquette
$p$, we apply the blowup on $p$ if it has no adjacent plaquette that has been
blown-up. The local neighborhood of each plaquette is labeled in Figure 9.

Figure 9: The neighborhood of plaquette $p$, corresponding to the 16 checks in
its surrounding. In bold the corner case of the heuristic in (i) is depicted.

Each check is given a number, and in the following we associate to each check
a true/false value depending on whether it is unsatisfied/satisfied.

  * (i)

Weight 2 degenerate errors with condition on diagonal

    * –

$\mathbf{s}(c_{1})\wedge\mathbf{s}(c_{2})\wedge\mathbf{s}(c_{3})\wedge\mathbf{s}(c_{4})$

    * –

$\overline{\mathbf{s}(c_{1})}\wedge\mathbf{s}(c_{2})\wedge\overline{\mathbf{s}(c_{3})}\wedge\mathbf{s}(c_{4})\wedge\Big{(}\mathbf{s}(c_{9})\oplus\mathbf{s}(c_{11})\oplus\mathbf{s}(c_{5})\oplus\mathbf{s}(c_{15})=0\Big{)}$

    * –

$\mathbf{s}(c_{1})\wedge\overline{\mathbf{s}(c_{2})}\wedge\mathbf{s}(c_{3})\wedge\overline{\mathbf{s}(c_{4})}\wedge\Big{(}\mathbf{s}(c_{6})\oplus\mathbf{s}(c_{8})\oplus\mathbf{s}(c_{12})\oplus\mathbf{s}(c_{14})=0\Big{)}$

  * (ii)

Weight 2 diagonal degenerate errors without condition

    * –

$\overline{\mathbf{s}(c_{1})}\wedge\mathbf{s}(c_{2})\wedge\overline{\mathbf{s}(c_{3})}\wedge\mathbf{s}(c_{4})$

    * –

$\mathbf{s}(c_{1})\wedge\overline{\mathbf{s}(c_{2})}\wedge\mathbf{s}(c_{3})\wedge\overline{\mathbf{s}(c_{4})}$

  * (iii)

Weight 3 degenerate errors - patterns not yet catched by (i) and (ii)

    * –

$\mathbf{s}(c_{1})\wedge\overline{\mathbf{s}(c_{2})}\wedge\overline{\mathbf{s}(c_{11})}\wedge\overline{\mathbf{s}(c_{4})}\wedge\overline{\mathbf{s}(c_{3})}\wedge\mathbf{s}(c_{12})$

    * –

$\overline{\mathbf{s}(c_{1})}\wedge\overline{\mathbf{s}(c_{2})}\wedge\mathbf{s}(c_{11})\wedge\mathbf{s}(c_{4})\wedge\overline{\mathbf{s}(c_{3})}\wedge\overline{\mathbf{s}(c_{12})}$

    * –

$\mathbf{s}(c_{1})\wedge\overline{\mathbf{s}(c_{2})}\wedge\overline{\mathbf{s}(c_{4})}\wedge\overline{\mathbf{s}(c_{3})}\wedge\overline{\mathbf{s}(c_{15})}\wedge\mathbf{s}(c_{14})$

    * –

$\overline{\mathbf{s}(c_{1})}\wedge\mathbf{s}(c_{2})\wedge\overline{\mathbf{s}(c_{4})}\wedge\overline{\mathbf{s}(c_{3})}\wedge\mathbf{s}(c_{15})\wedge\overline{\mathbf{s}(c_{14})}$

The diagonal condition of (i) comes from a corner case that would make the
heuristic fail if not property taken into account. This is illustrated in
Figure 9, where, if the plaquette $p$ is blown-up, then the plaquette on the
right could not be blown-up in its turn, and the MS would fail to converge.
Clearly (i) and (ii) are enough to take care of all weight 2 degenerate
errors. There are some weight 3 errors which are also taken into account by
(i) and (ii), the remaining ones being taken care of by (iii).

See 3

The proof of the Theorem is given in Appendix C.4, by using the tools
introduced to prove the second part of Theorem 2.

####  4.2.1 Numerical Results

Here we plot the error correction performance of the MS versus the SB+MS. One
can see that the slopes match the expected values. Indeed, the MS is able to
converge on all errors of weight 1 but fails on some errors of weight 2. The
dominant term is thus $p^{2}$ and the slope matches it for small $p$. For the
SB+MS since the smallest undecodable error is of weight 4, and the slope
matches the $p^{4}$ curve.

Figure 10: Numerical results for MS and SB+MS decoding on the toric code of
distance 11. A maximum number of 15 decoding iterations are used for the MS
decoding. The slope of the MS is $p^{2}$ since the smallest undecodable errors
are of weight 2, and the slope of the SB+MS is $p^{4}$ since the smallest
undecodable errors are of weight 4.

####  4.2.2 SB+MS+OSD

One of the most used post-processing is Ordered Statistic Decoding (OSD),
proposed in [2]. Numerically, MS+OSD is a good approximation of the classical
ML for the toric code (see for example [3]). However since the OSD post-
processing is very costly, namely $\mathcal{O}(n^{3})$,777We acknowledge that
the theoretical complexity of Gaussian elimination is $\mathcal{O}(n^{2.38})$
(see for example [18]), but such algorithms are not practical as they suffer
from huge constant costs, and for real life use cases, the Gaussian
elimination algorithm is used. it is interesting to run the best possible
decoder beforehand to avoid unnecessary use of OSD. Looking at the curves from
Figure 10, this yields a quadratic improvement in the number of calls of OSD,
only needing to call OSD with probability $\approx p^{4}$ compared to $\approx
p^{2}$. Since our post-processing is linear, this implies a significant
improvement on the average decoding complexity for small $p$, going from
$\mathcal{O}(n\log(n)+p^{2}n^{3})$ to $\mathcal{O}(n\log(n)+p^{4}n^{3})$.

##  5 Conclusion

Using the powerful framework of decoding tree, we were able to show that there
is an inherent limitation to the error-correction capability of the MS on the
toric code. This was done by introducing the notion of blindness, which not
only emphasize the fact that the decoder is unable to converge, but also prove
that the spreading of the messages in the code is inherently limited. We also
showed that by using a low cost syndrome-aware pre-processing we were able to
make the decoding radius and the non-degenerate decoding radius of the MS
match. In the vein of what had been done recently on the limitations of the
renormalization decoder on the toric code in [19], to the best of our
knowledge this is the first formal result explaining why the MS decoder does
not perform well on the toric code, and we also conjecture that similar
results could be obtained for other iterative decodings (NMS and BP) that have
similar decoding processes, and can also be explained using the decoding tree,
although in a different manner that do not allow the proofs to transfer
directly.

The blindness property we proved here comes from a strong imbalance between
the girth and the diameter of the graph. This can be seen as a _graph
degeneracy_ , complementing the standard notion of _code degeneracy_ (i.e.,
classical minimum distance smaller that the quantum minimum distance), the
latter being independent of the Tanner graph representation of the code. It is
worth noticing that for well-constructed classical LDPC codes, e.g.,
constructed by the progressive edge growth algorithm [20], such a graph
degeneracy does not happen: the length of the shortest cycle passing through a
given check is greater than or equal to the maximum distance between that
check and all the others. This ensures fast spreading of messages in the
Tanner graph. We suspect that the graph degeneracy could have blindness
effects for more general quantum LDPC codes, although the imbalance between
girth and diameter would be reduced for finite-length Tanner graphs with
increased connectivity degree.

Additionally, it might be interesting to explore the stabiliser-blowup pre-
processing on its own, to see if it can be applied to a wider class of codes.
There should be a straightforward generalisation for all planar codes, but we
do believe that the pre-processing could be extended to generic quantum LDPC
codes.

## Acknowledgment

The authors would like to thank Leonid Pryadko and Xingrui Liu for usefull
discussions during the elaboration of this work. This work was supported by
the QuantERA grant EQUIP (French ANR-22-QUA2-0005-01), and by the Plan France
2030 (NISQ2LSQ project, ANR-22-PETQ-0006).

##  Appendix A Additional Results on Small Weight Non-Degenerate and
Degenerate Errors

###  A.1 Weight 2 Degenerate Errors are Undecodable by MS

There are only two degenerate errors of weight 2 up to translation and
rotations (depicted in Figure 11). To show that they are both undecodable by
the MS, we use the fact that both syndromes are invariant under some
symmetries. The two cases are depicted in Figure 11 (a) and (b). For the
weight 2 syndrome of (a), it is clear that by the symmetry about the $\ell$
line, $\textsc{app}(q_{k},i)=\textsc{app}(q^{\prime}_{k},i)$ for
$k\in\\{0,1\\}$, $\forall i\geq 0$. Hence the estimate error around $c$ will
never satisfy the syndrome $\mathbf{s}$. A similar argument applies for (b).

Figure 11: Undecodable degenerate errors of weight 2

###  A.2 A Weight 3 Degenerate Error Decodable by MS

Although we said earlier that degenerate syndromes are key to understand the
failures of the MS, and we made it clear using numerical simulations in the
above subsection, it is not true that degenerate implies undecodable by MS. In
Figure 12 we provide the smallest example of a degenerate syndrome that is
decodable (in 1 iteration) by the MS.

Figure 12: Equivalent weight 3 decodable degenerate errors (generating the
same degenerate syndrome of weight 4): Although the three errors are all of
weight 3, the MS will converge to the middle error in just one iteration (this
can be easily checked, by computing “by hand” the a posteriori value of each
qubit after one iteration).

##  Appendix B Proof of Lemmas 3 and 4

We first start by showing a few technical lemmas before proving Lemmas 3 and
4.

###  B.1 Technical Lemmas

######  Definition 17.

A labeled link is said maximal if it cannot be extended into a longer labeled
link. It is said robustly maximal if there is no other labeled link sharing at
least one edge with it that is of greater length.

######  Lemma 8.

Given a configuration $C$, and a maximal proper labeled link
$u{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v$. Then at least 2 of
the 3 edges going down from $v$ are unlabeled.

###### Proof.

Since $v$ is the endpoint of a maximal labeled link, it is either true that:

  * (i)

$u$ belongs to the subtree rooted in $v$, in which case the only labeled edge
going down from $v$ is the one belonging to the labeled link
$u{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v$, as otherwise
$u{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v$ could be extended
and would not be maximal.

  * (ii)

On the other hand, if $u$ does not belong to the subtree rooted in $v$, all
three edges below $v$ are unlabeled as otherwise the labeled link
$u{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v$ could be extended
and would not be maximal.

∎

######  Lemma 9.

Given a configuration $C$ for a syndrome where all unsatisfied checks are at
distance $\geq 4$, and a maximal proper labeled link
$u{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v_{c}$, where $v_{c}$
is at distance $\geq 5$ from the bottom. Then there exists an unlabeled
$I$-link
$v_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v^{\prime}_{c}$ such
that $v_{c}$ is its upper endpoint.

###### Proof.

By Lemma 8, there must be one unlabeled edge $e_{q}$ going down from $v_{c}$.
In the toric code, there exists a path of length 4 that starts from $c$, goes
through qubit $q$ and loops back to $c$. Hence, since $e_{q}$ is unlabeled,
there exist an unlabeled $I$-link
$v_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v^{\prime}_{c}$. ∎

######  Lemma 10.

Given a minimal configuration $C$ for a syndrome where all unsatisfied checks
are at distance $\geq 4$, and a maximal proper labeled link
$u{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v$ of length $\geq 4$,
where $v$ is a distance $d\leq 4$ from the bottom. Then any dangling link
$v{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}\\_$ is of length $d$ and
unlabeled.

###### Proof.

We note that the subtree rooted in $v$ does not contain any unsatisfied vertex
(since all vertices in the subtree are at distance $\leq$ 3 from $v$). In
particular, the proper link
$u{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v$ must come from
above. Since $u{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v$ is
maximal, it cannot be extended inside the subtree rooted in $v$, and since $C$
is minimal it follows that all the edges in this subtree are unlabeled. Thus,
any dangling link $v{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}\\_$ is
of length $d$ and unlabeled. ∎

###  B.2 Proof of Lemma 3

###### Proof.

Let $C_{\circ}^{*}$ be any minimal root-unlabeled configuration on the
decoding tree $\mathcal{T}_{i,q}$.

##### Case 1 (Proper labeled link
$u^{0}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{0}$):

Suppose there is a proper labeled link
$u^{0}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{0}$ of length
$\geq 5$. If there are several choices, it is always possible to take one that
is robustly maximal and as deep as possible (i.e., that in the subtrees rooted
in $u^{0}$ and $v^{0}$, there are no labeled links of length $\geq 5$, except
possibly $u^{0}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{0}$).

Now recursively create an alternating chain $\mathcal{A}$ containing the
labeled link $u^{0}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{0}$
that goes from one dangling edge to another. This alternating chain will have
the property:

$P:\text{all labeled links in $\mathcal{A}$ are maximal}$

We start with
$\mathcal{A}=\\{u^{0}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{0}\\}$.
Set $i=0$ and do recursively starting from $u^{0}$ (and later do the same for
$v^{0}$):

  * (i)

$i$ even: an unlabeled link must be appended. If $u^{i}$ is at distance $\geq
5$ from the bottom, then there exists an unlabeled $I$ link
$u^{i}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}u^{i+1}$ such that
$u^{i}$ is its upper endpoint (by Lemma 9). Set
$\mathcal{A}=\mathcal{A}\cup\\{u^{i}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}u^{i+1}\\}$888Strictly
speaking, an alternating chain is an ordered sequence of links so the union
should be seen as preppending/appending the link to the ordered list..

Otherwise, $u^{i}$ is at distance $d\leq 4$ from the bottom, and there exists
a dangling unlabeled link
$u^{i}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}\\_$ of length $d$ (by
Lemma 10). Set
$\mathcal{A}=\mathcal{A}\cup\\{u^{i}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}\\_\\}$
and terminate the algorithm on this side.

  * (ii)

$i$ odd: a labeled link must be appended. Take any labeled link having $u^{i}$
as endpoint (we show below that is necessarily maximal). If it is a proper
labeled link
$u^{i}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}u^{i+1}$, set
$\mathcal{A}=\mathcal{A}\cup\\{u^{i}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}u^{i+1}\\}$.

Otherwise, it is a dangling link
$u^{i}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}\\_$. Set
$\mathcal{A}=\mathcal{A}\cup\\{u^{i}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}\\_\\}$
and terminate the algorithm on this side.

Since $u^{0}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{0}$ was
taken to be as deep as possible, any time a labeled link is appended, it must
be of length $\leq 4$, and if it is a proper link, since all vertices
associated to unsatisfied checks are at distance $\geq 4$, it must be of
length exactly 4, and thus maximal, so property $P$ is conserved throughout
the algorithm.

This algorithm will always terminate because, one of the following is always
true:

  * (i)

When adding an unlabeled link, either the algorithm terminates on this side or
an $I$-link was appended, in which case the depth increases by 4.

  * (ii)

When adding a labeled link, either the algorithm terminates on this side, or a
proper labeled link
$u^{i}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}u^{i+1}$ of length
4 has been appended, in which case the depth decreases by at most 3 as $u^{i}$
is already the bottom endpoint of an unlabeled $I$ link so it cannot also be
the bottom endpoint of a labeled $I$ link.

Thus the algorithm must end.

We now have an algorithm to construct an alternating chain that goes from
dangling edge to dangling edge. This is not enough to use the inversion Lemma
directly, so we further modify it to ensure that there is no dangling
unlabeled link of length $\geq 3$.

Suppose there is one unlabeled dangling link of length $\geq 3$, without loss
of generality write it
$u^{k}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}\\_$. Then since
$u^{k}$ it at distance $\geq 3$ from the bottom, $u^{k}$ must be the upper
endpoint of a $\Gamma$-link
$u^{k}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}u^{k+1}$. This
$\Gamma$-link must be unlabeled because :

  * (i)

If $k=0$, $u^{k-1}=v^{0}$ and
$u^{k-1}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}u^{k+1}$ would be
longer than $u^{0}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{0}$
and this would give a contradiction to the fact that
$u^{0}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{0}$ is robustly
maximal.

  * (ii)

If $k\neq 0$, then
$u^{k-1}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}u^{k+1}$ would be
a labeled link of length $\geq 6$ which would contradict the fact that
$u^{0}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{0}$ was taken as
deep as possible.

Now set
$\mathcal{A}=\Big{(}\mathcal{A}\setminus\\{u^{k}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}\\_\\}\Big{)}\cup\\{u^{k}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}u^{k+1}\\}$.

At this point, we arrive at unsatisfied check $u^{k+1}$ at distance $\leq 2$
of the bottom, and we need to add a labeled dangling link to finish our
alternating chain. Since $u^{k+1}$ is unsatisfied, it is must be the endpoint
of a labeled link. It is impossible that $u^{k+1}$ is the bottom endpoint of a
labeled $I$ or $\Gamma$ link as it would contradict the fact that
$u^{k}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}u^{k+1}$ is unlabeled.
So it must either be a labeled dangling link, in which case we are done, or it
is a labeled $\Lambda$-link. In that case we append it and then finish the
alternating chain by appending a length 2 unlabeled dangling link that must
exist according to Lemma 10. We now have the alternating chain with all the
required properties to finish the proof.

We look at the walk given by the alternating chain (with possible back-and-
forth). We do the path inversion according to Lemma 2. This gets rid of the
labeled link $u^{0}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{0}$
of length $\geq 5$.

To conclude the proof, we now argue that the configuration obtained by
applying the walk inversion Lemma is minimal.

The added cost of labeling each previously unlabeled proper 4-link will be
compensated by unlabeling the next proper labeled 4-link, if it exists. As
they are both of length 4 and there will be as many edges being unlabeled as
being relabeled999It should be easy to convince oneself that this is also true
when there are overlapping edges.. We only need to deal with the dangling
links at both ends of the alternating chain. We show that whatever weight will
be added at both end is compensated by the unlabeling of
$u^{0}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{0}$, thus
keeping the minimality of the configuration.

There are several cases to consider. On both sides, the chain can end with
either an unlabeled link of length 1 or 2, or a labeled link of length 1, 2, 3
or 4, preceeded by an unlabeled $I$ link of length 4. Consider one end of the
alternating chain, and denote these cases as $U_{1},U_{2}$ and
$L_{1},\dots,L_{4}$ respectively.

  * •

$U_{1}$,$U_{2}$: adds 1 or 2 to the weight

  * •

$L_{1}$: adds 3 to the weight.

  * •

$L_{2}$,$L_{3}$,$L_{4}$: adds respectively 2, 1 or 0 to the weight

The only troublesome case is $L_{1}$, since if that where to happen on both
ends of the alternating chain, the added weight of 6 might not be compensated
by unlabeling of a weight 5 labeled link
$u^{0}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{0}$. A simple
parity argument takes care of this corner case: in case the
$u^{0}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{0}$ is of length
5, $u^{0}$ and $v^{0}$ must be at a depth of different parity in the
tree101010The only case where this is not true is when the link contains the
root but this case is purposefully avoided in the Theorem. Since at each step
adding a 4-link conserves the parity of the depth, it cannot be that the case
$L_{1}$ happens on both ends.

##### Case 2 (Dangling labeled link
$u^{0}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}\\_$):

Suppose there is a dangling labeled link with endpoint $u^{0}$ of length $\geq
5$. The same algorithm can be applied from $u^{0}$, except the argument for
the minimality has to be (easily) adapted from Case 1.

##### Recursive Application of the Algorithm:

By applying the algorithm as long as there are labeled links of length $\geq
5$ (except possibly if it contains the root), this algorithm transforms any
minimal root-unlabeled configuration in a minimal root-unlabeled configuration
where all labeled links not containing the root are of length $\leq 4$. ∎

###  B.3 Proof of Lemma 4

###### Proof.

Starting with a minimal configuration $C_{\bullet}^{*}$, and using the
algorithm from the proof of Lemma 3, one can remove all the length $\geq 5$
labeled links not containing the root.

Now suppose there is a labeled link of length $\geq 5$ containing the root
$e_{q}$. Since $q$ is neighboring an unsatisfied check $c$, we know that there
is an unsatisfied vertex $u_{c}$ just next to $e_{q}$.

Note that the edges going down from $u_{c}$ must be unlabeled. This is
because, since $e_{q}$ is labeled, to keep the parity of $u_{c}$, it must be
that two edges below $u_{c}$ are labeled, hence, that there are two labeled
links $u_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}u^{\prime}$
and
$u_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}u^{\prime\prime}$
below it. But then the labeled link
$u^{\prime}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}u^{\prime\prime}$
does not contains the root and must be of length $\geq 8$ which is a
contradiction. So we conclude that the longest labeled link starting from
$u_{c}$ and going through the root $e_{q}$ is robustly maximal.

##### Case 1 (proper labeled link
$u_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v$):

Suppose the labeled link containing the root is of length $\geq 5$ of the form
$u_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v$. Let $u_{c}$ and
$w$ be the vertices adjacent to $e_{q}$. Since all the labeled links not
containing the root are of length $\leq 4$, it follows that from the three
edges going down from $w$, only the one contained in the path going to $v$ is
labeled. Then, we can take an unlabeled edge $e$ going down from $w$, such
that there exists a proper unlabeled 4-link
$u_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v^{\prime}_{c}$
containing $e_{q}$ and $e$.

  * (i)

Suppose $v^{\prime}_{c}$ is contained in a labeled proper 4-link
$v^{\prime}_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{\prime\prime}_{c}$.
In that case, we use a “trick” and run the algorithm from the proof of Lemma
3, as if
$v^{\prime\prime}_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v$ was
a proper labeled link (we can do this since the edges adjacent to
$v^{\prime\prime}_{c}$ and $v$ on the
$v^{\prime\prime}_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v$ link
are labeled; also, note that the link
$v^{\prime\prime}_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v$
contains at least 5 labeled edges, which guarantees the minimality of the new
configuration, obtained after applying the algorithm). This will invert the
labels of the edges on the
$v^{\prime\prime}_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v$,
giving us a configuration where the link
$u_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v^{\prime}_{c}$ is
labeled and contains the root $e_{q}$, and where all the labeled links are of
length 4, thus concluding the proof.

  * (ii)

Suppose $v^{\prime}_{c}$ is not contained in a proper link, it must then
contained in a dangling labeled link
$v^{\prime}_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}\\_$. This
dangling labeled link cannot be of length 1 since we know $v$ is deeper than
$v^{\prime}_{c}$. So it can be of length 2, 3 or 4. In which case $v$ is the
vertex endpoint of an unlabeled dangling link
$v{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}\\_$, of length
respectively 1, 2 or 3. In that case inverting the alternating chain
$\\{v^{\prime}_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}\\_,v^{\prime}_{c}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v,v{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}\\_\\}$
gives a minimal configuration where all labeled links are of length at most 4,
and this concludes the proof.

##### Case 2 (dangling labeled link
$u_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}\\_$):

Suppose the labeled link containing the root is a dangling link of length
$\geq 5$. The same argument as above can be adapted in combination with Case 2
in the proof of Lemma 3 to conclude the proof.

∎

##  Appendix C Proof of Theorem 2 and 3

###  C.1 Pruning

######  Definition 18.

Pruning

Given a decoding tree $\mathcal{T}_{i,q}$, we define the pruning of
$\mathcal{T}_{i,q}$ as a pair $(\hat{\mathcal{T}}_{i,q},\mathcal{S})$ where:

  * •

$\mathcal{S}$ is a set of removed subtrees (each subtree in $\mathcal{S}$ is
rooted in some vertex).

  * •

$\hat{\mathcal{T}}_{i,q}$, the pruned tree, is a connected subgraph of
$\mathcal{T}_{i,q}$ containing the root edge $e_{q}$, obtained by removing the
subtrees in $\mathcal{S}$.

Since each subtree in $\mathcal{S}$ is routed in a vertex,
$\hat{\mathcal{T}}_{i,q}$ has new dangling edges (which are incident in
$\mathcal{T}_{i,q}$ to the root of some tree in $\mathcal{S}$). We refer to
those as severed edges.

###  C.2 The Non-Degenerate Error $\epsilon^{4}$ of Weight 4 is Undecodable by
MS

We now proceed to show the upper bound on the decoding radius of Theorem 2, by
showing that the decoder is blind on the syndrome $\mathbf{s}^{4}$.

Let $c$ be an unsatisfied check in $\mathbf{s}^{4}$, the syndrome associated
to $\epsilon^{4}$, and $q\in\mathcal{N}(c)$. Let $\mathcal{T}_{i,q}$ be the
decoding tree associated to $q$ at iteration $i$, and let also be the fake
syndrome where only $c$ is unsatisfied (Section 3.1).

On $\mathcal{T}_{i,q}$, we now consider some minimal configurations
$C_{\bullet},C_{\circ}$ associated to syndrome $\mathbf{s}$, and
${C_{\bullet}^{c}},{C_{\circ}^{c}}$ associated to syndrome where all labeled
links are of length $\leq 4$ and for all proper $I$ and $\Lambda$ links, both
endpoints are a copy of the same check (thanks to Lemmas 3,4, and 7).

##### Outline of the proof:

We now proceed to show that
$|C_{\bullet}|-|C_{\circ}|=|{C_{\bullet}^{c}}|-|{C_{\circ}^{c}}|$, which
implies the blindness property for qubit $q$ by Theorem 4.

##### Step 1, the Pruning:

Explore $\mathcal{T}_{i,q}$ by doing a breadth-first search. Whenever a vertex
$w_{c^{\prime}}$ associated to a check such that
$\mathbf{s}(w_{c^{\prime}})=1$ and $c^{\prime}\neq c$ is found in
$\mathcal{T}_{i,q}$, proceed as follows.

Let $g$ be the grandfather of $w_{c^{\prime}}$ in $\mathcal{T}_{i,q}$, and
prune the subtree rooted in $g$ in $\mathcal{T}_{i,q}$. After doing that for
the whole tree, we are left with a pair
$(\hat{\mathcal{T}}_{i,q},\mathcal{S})$.

Note that for any subtree in $\mathcal{S}$, it holds that all unsatisfied
vertices are at depth $\geq 2$, as otherwise this would give a path in the
toric code between unsatisfied checks of length $<4$.

##### Claim 1:

In any of the minimal configurations $C_{\bullet},C_{\circ},{C_{\bullet}^{c}}$
and ${C_{\circ}^{c}}$ all severed edges are unlabeled.

Consider a severed edge, incident (in $\mathcal{T}_{i,q}$) to the root vertex
of some removed subtree $S$. If $e$ is labeled, it must belong to a labeled
link. There are 3 cases:

  * (i)

Suppose $e$ belongs to a dangling labeled link
$v{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}\\_$ with endpoint $v$
in $S$. Since $S$ was removed, $v$ must be at depth $\geq 2$ in $S$. So
$v{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}\\_$ must be of length
$\geq 7$ (2 to go from $v$ to $e$, plus $e$, plus at least $4$ edges to go
back down to a dangling edge in $\hat{\mathcal{T}}_{i,q}$) which is
impossible.

  * (ii)

Suppose $e$ belongs to a dangling labeled link
$v{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}\\_$ with endpoint $v$
in $\hat{\mathcal{T}}_{i,q}$. Since there is an unsatisfied vertex $u$ at
depth 2 in $S$, and that $u$ and $v$ must be at distance $\geq 4$, then $v$ is
at distance $\geq 5$ from the bottom, thus the length of
$v{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}\\_$ is $\geq 5$ which
is impossible by assumption.

  * (iii)

Suppose $e$ belongs to a labeled proper link. It must be of the form
$u_{c}{\;\framebox[7.5347pt]{\rule{7.5347pt}{4.30554pt}}\;}v_{c}$ where
$u_{c}\in\hat{\mathcal{T}}_{i,q}$ and $v_{c}\in S$ and of length 4. But $S$
was removed because of the unsatisfied vertex $w_{c^{\prime}}$ with
$c^{\prime}\neq c$, which is at depth 2 in $S$. Since $d(u_{c},v_{c})=4$,
$v_{c}$ is at depth $\geq 2$ in $S$, and $d(u_{c},w_{c^{\prime}})\geq 4$, we
conclude that $v_{c}$ must be at depth exactly 2 in $S$, and moreover
$d(u_{c},v_{c})=d(u_{c},w_{c^{\prime}})=4$. Thus,
$w_{c^{\prime}}{\;\framebox[7.5347pt]{\rule{0.0pt}{4.30554pt}}\;}v_{c}$ is a
$\Lambda$-link with both endpoints at distance $4$ from $u_{c}$, which yields
a contradiction by applying Lemma 6.

##### Claim 2:

Denoting
$\hat{C}_{\circ},\hat{C}_{\bullet},\hat{C_{\circ}^{c}},\hat{C_{\bullet}^{c}}$
the restriction of the minimal configurations to the pruned tree
$\hat{\mathcal{T}}_{i,q}$, we have that
$|\hat{C}_{\circ}|=|\hat{C_{\circ}^{c}}|$ and
$|\hat{C}_{\bullet}|=|\hat{C_{\bullet}^{c}}|$.

This is because all the severed edges are unlabeled so the labeling induced by
configurations $\hat{C}_{\bullet}$ and $\hat{C_{\bullet}^{c}}$ (resp.
$\hat{C}_{\circ}$ and $\hat{C_{\circ}^{c}}$) are interchangeable and of same
weight, as otherwise it would contradict the minimality of $C_{\bullet}$ and
${C_{\bullet}^{c}}$ (resp. $C_{\circ}$ and ${C_{\circ}^{c}}$).

##### Claim 3:

For every subtree $S\in\mathcal{S}$, since the corresponding severed edge $e$
is unlabeled in both $C_{\circ}$ and $C_{\bullet}$, then the restriction of
$C_{\circ}$ and $C_{\bullet}$ to $S$ have the same weight.

Clearly the minimality of the labeling on such a subtree does not depend on
the rest of the tree since $e$ is unlabeled in both cases, so they must have
the same weight.

By Claims 1 and 3,

$|C_{\bullet}|-|C_{\circ}|=|\hat{C}_{\bullet}|-|\hat{C}_{\circ}|\text{ and
}|{C_{\bullet}^{c}}|-|{C_{\circ}^{c}}|=|\hat{C_{\bullet}^{c}}|-|\hat{C_{\circ}^{c}}|$

By Claim 2,

$|\hat{C}_{\bullet}|-|\hat{C}_{\circ}|=|\hat{C_{\bullet}^{c}}|-|\hat{C_{\circ}^{c}}|$

Hence

$|C_{\bullet}|-|C_{\circ}|=|{C_{\bullet}^{c}}|-|{C_{\circ}^{c}}|$

###  C.3 Decoding of Non-Degenerate Errors of Weight $\leq 3$ by MS

We now show that the non-degenerate decoding radius of the MS is $\geq 3$, to
conclude the proof of Theorem 2. We first give a few definitions and prove two
preliminary Lemmas.

Given a toric code $T$, we will refer to a connected planar subgraph $\tau$
induced by one or several plaquettes of $T$ as a patch. Precisely, $\tau$ is a
connected subgraph induced by its vertex set $V(\tau)$, which must satisfy
$V(\tau)=\cup_{i}V(p_{i})$, where $V(p_{i})$ denotes the set of vertices
(checks) of plaquette $p_{i}$. It is easily seen that if $\tau$ is a patch of
$T$ and $T^{\prime}$ is a toric code of higher minimum distance, then $\tau$
can be embedded in $T^{\prime}$ via a graph monomorphism $\tau\rightarrow
T^{\prime}$, and this embedding is unique up to translations, reflections, and
rotations in $T^{\prime}$. We will use such a patch embedding to embed in
$T^{\prime}$ planar subgraphs of $T$ and syndromes. We note that (i) for any
planar subgraph $\sigma$ of $T$ there exists a patch $\tau$ in $T$ such that
$\sigma$ is a subgraph of $\tau$, and (ii) there exists a patch $\tau$ with
$V(\tau)=V(T)$.

######  Definition 19.

Let $T$ and $T^{\prime}$ be toric codes, with $T^{\prime}$ of larger minimum
distance.

  * (i)

Consider a planar subgraph $\sigma$ of $T$, it must be contained in a patch
$\tau$ in $T$. We define the embedding of $\sigma$ in $T^{\prime}$ as the
subgraph $\sigma^{\prime}$ of $T^{\prime}$ induced by embedding $\tau$ in
$T^{\prime}$. This embedding is unique up to translations, reflections, and
rotations in $T^{\prime}$.

  * (ii)

Consider a syndrome $\mathbf{s}$ on $T$, and a minimal connected (necessarily
planar) subgraph $\sigma$ of $T$ covering all its unsatisfied checks. We
define the embedding of $\mathbf{s}$ in $T^{\prime}$ as the syndrome
$\mathbf{s}^{\prime}$ on $T^{\prime}$ induced by embedding $\sigma$ in
$T^{\prime}$. This embedding is unique up to translations, reflections, and
rotations in $T^{\prime}$.

######  Definition 20.

For a toric code $T$, the distance between two sets of checks
$C,C^{\prime}\subseteq V(T)$ is defined as
$d(C,C^{\prime}):=\min\\{\,d(c,c^{\prime})\mid c\in C,\ c^{\prime}\in
C^{\prime}\,\\}$. We extend this definition to qubits, errors, syndromes, and
subgraphs of the toric code in the following way (where the same extension
applies to the second argument of $d(-,-)$):

  * •

For a set of qubits $Q\subset E(T)$, $d(Q,-):=d(\mathcal{N}(Q),-)$, where
$\mathcal{N}(Q):=\cup_{q\in Q}\mathcal{N}(q)$.

  * •

For a syndrome $\mathbf{s}$,
$d(\mathbf{s},-):=d(\operatorname{supp}(\mathbf{s}),-)$, where
$\operatorname{supp}(\mathbf{s}):=\\{c\in V(T)\mid\mathbf{s}(c)=1\\}$

  * •

For an error $\mathbf{e}$,
$d(\mathbf{e},-):=d(\operatorname{supp}(\mathbf{e}),-)$, where
$\operatorname{supp}(\mathbf{e}):=\\{q\in E(T)\mid\mathbf{e}(q)=1\\}$.

  * •

For a subgraph $\sigma$ of $T$, $d(\sigma,-):=d(V(\sigma),-)$, where
$V(\sigma)$ is the vertex set of $\sigma$.

######  Definition 21.

The diameter of a syndrome $\mathbf{s}$ is the minimum over the diameters of
all the connected subgraphs covering its unsatisfied checks.

######  Definition 22.

For a toric code, a  $\delta$-local syndrome $\mathbf{s}$ is a syndrome where
all unsatisfied checks are contained in a connected subgraph of diameter
$\delta$.

######  Definition 23.

We say a syndrome $\mathbf{s}$ is decoded in $k$ iterations if the MS decoder
finds an error $\mathbf{e}$ such that $\mathbf{H}\mathbf{e}=\mathbf{s}$ at
iteration $k$ and not before.

######  Lemma 11.

Let $T$ be a toric code of distance $d$, and $\mathbf{s}$ be a $\delta$-local
syndrome decoded in $k$ iterations. If $d\geq 2k+\delta$, then for any toric
code $T^{\prime}$ of distance $d^{\prime}>d$, the embedding of $\mathbf{s}$ in
$T^{\prime}$ will be corrected in $k$ iterations.

###### Proof.

Let $\sigma$ be the connected subgraph containing all the edges at distance
$\leq\delta$ from $\mathbf{s}$, and their check neighborhood, that is:

$E(\sigma)=\\{e\in E(T)\mid d(e,\mathbf{s})\leq\delta\\}\text{ and
}V(\sigma)=\displaystyle\bigcup_{e\in E(\sigma)}\mathcal{N}(e).$

Note that $\sigma$ is planar as $\delta<d$ so we can define $\sigma^{\prime}$
to be the embedding of $\sigma$ in $T^{\prime}$. For any qubit $q^{\prime}\in
T^{\prime}$, either $d(q^{\prime},\mathbf{s})\geq k$ in which case one can see
that its a posteriori at each iteration will be
$\textsc{app}(q^{\prime},i)=1+2i$, for $i\leq k$ or
$d(q^{\prime},\mathbf{s})<k$, in which case, $q^{\prime}\in\sigma^{\prime}$,
and at each iteration, its a posteriori is the same as that of $q\in\sigma$,
its corresponding qubit in $T$. This is because since $d\geq 2k+\delta$, there
are no qubits in $T$ that have a decoding tree reaching unsatisfied checks of
$\mathbf{s}$ by going around the toric code. Formally, this condition can be
stated as: given $\tau$ a minimal connected covering of $\mathbf{s}$, then for
all $q$ in $T$, $E(\tau)\cup\\{e\in E(T),\ d(e,q)\leq k\\}$ does not contain a
logical operator. Thus at iteration $k$, the decoder will converge on the
embedding of $\mathbf{s}$ on $T^{\prime}$. ∎

######  Lemma 12.

Let $T$ be any toric code, $\mathbf{s}_{1}$ a syndrome decoded in $k_{1}$
iterations and $\mathbf{s}_{2}$ a syndrome decoded in $k_{2}$ iterations.
Further assume that $k_{1}\leq k_{2}$, and that if the decoder where left to
run on $\mathbf{s}_{1}$ for any number $k\in[k_{1},k_{2}]$ of iterations (even
after the syndrome is satisfied), the error outputted at each iteration would
still satisfy the syndrome. Let $\delta$ be the distance between
$\mathbf{s}_{1}$ and $\mathbf{s}_{2}$. If $\delta\geq 2k_{2}$ then the
syndrome $\mathbf{s}_{1}+\mathbf{s}_{2}$ is decodable in $k_{2}$ iterations.

###### Proof.

For any qubit $q$, either is true:

  * (i)

$d(\mathbf{s}_{1},q)\geq k_{2}$ and $d(\mathbf{s}_{2},q)\geq k_{2}$. In this
case the decoding tree of $q$ does not contain unsatisfied checks for any
iteration $k\leq k_{2}$. So $\textsc{app}(q,k)=1+2k$.

  * (ii)

There exist $i,j$ with $\\{i,j\\}=\\{1,2\\}$ such that $d(e_{i},q)<k_{2}$ and
$d(e_{j},q)\geq k_{2}$

In that case the decoder will take the same decision on $q$ as if the syndrome
was only $\mathbf{s}_{i}$.

At iteration $k_{2}$, by (ii) in the $k_{2}$-neighborhood of $\mathbf{s}_{1}$
and $\mathbf{s}_{2}$, both syndromes are satisfied, and by (i) all the other
qubits are not in error, so the syndrome $\mathbf{s}_{1}+\mathbf{s}_{2}$ is
satisfied. ∎

We are now ready to finish the proof of Theorem 2. We do this by treating the
first cases numerically, and then use the Lemmas 11, 12 introduced before to
prove the result for $d\geq 18$.

###### Proof.

For any toric code of distance $9\leq d<18$, all the non-degenerate errors of
weight $\leq 3$ are decodable by the MS algorithm. This is checked by
exhaustive numerical verification.

For toric codes of minimum distance $\geq 18$, we do the following :

  * (i)

It can be easily checked that all weight 1 errors are non-degenerate and can
be decoded by the MS in 1 iteration, for any toric code of distance $d\geq 3$.

  * (i’)

Moreover, it is also true that for a weight 1 error on a toric code of
distance $\geq 5$, if the decoder where allowed to continue after the first
iteration (when it already decodes the error), at the second iteration it
would still output the same weight 1 error.

  * (ii)

Any weight 2 non-degenerate error where the two qubits in error are at
distance $\geq 2$ will be decodable in 1 iteration because of (i) and Lemma 12
for any toric code of distance $d\geq 6$.

  * (ii’)

For the remaining non-degenerate errors of weight 2, those where the distance
between the two qubits in error is at most 1 (i.e., of diameter 3), there are
only 4 types of error up to symmetries and translations (shown in Fig. 13).
For those, we check numerically that the decoder converges in at most 2
iterations on a toric code of distance 7. Using Lemma 11, since
$2k+\delta=2\times 2+3=7$, we conclude that all the errors of weight 2 and
diameter 3 are corrected on a toric code of any distance $d\geq 7$.

  * (iii)

Any weight 3 error where the distance between any two pair of qubits is $\geq
2$ is correctable in 1 iteration by Lemma 12 for any toric code of distance
$\geq 3$.

  * (iii’)

Remaining errors can be written as the sum of an error $\mathbf{e}_{1}$ of
weight 1 (of diameter 1) and an error $\mathbf{e}_{2}$ of weight 2 and of
diameter $\leq 3$ (depicted in Figure 13). Suppose
$d(\mathbf{e}_{1},\mathbf{e}_{2})\geq 4$. By (i), $\mathbf{e}_{1}$ is decoded
in $1$ iterations. and by (ii’), $\mathbf{e}_{2}$ is decoded in $\leq 2$
iterations. We can thus use Lemma 12 on the syndromes associated to
$\mathbf{e}_{1}$ and $\mathbf{e}_{2}$ to conclude that
$\mathbf{e}_{1}+\mathbf{e}_{2}$ is decoded in 2 iterations. Note that this
argument is true for any error of weight 3 satisfying the condition
$d(\mathbf{e}_{1},\mathbf{e}_{2})\geq 4$ irrespective of the distance of the
code.

  * (iii”)

For the remaining finite number of weight 3 errors of diameter $\delta\leq
8=4+1+3$ (where $d(\mathbf{e}_{2},\mathbf{e}_{2})\leq 4$, the diameter of
$\mathbf{e}_{1}$ is 1 and the diameter of $\mathbf{e}_{2}$ is at most 3). We
check numerically that these errors are decodable in $\leq 5$ iterations on a
toric code of distance $18$. By applying Lemma 11, and since
$2k+\delta=2\times 5+8\leq 18$, we conclude that for any toric code of
distance $d\geq 18$, all weight $3$ non-degenerate errors are decodable.

∎

Figure 13: The weight 2 errors of diameter 3 (up to symmetries and
translation), all are decodable in 2 iterations of the MS.

###  C.4 Proof of Theorem 3

We now prove Theorem 3, using the tools introduced in the proof of the second
part of Theorem 2.

For all toric codes of distance $7\leq d\leq 28$ we enumerate all errors of
weight $\leq 3$ and check that SB+MS is able to correct them. There are two
cases:

  * (i)

the diameter of the error is $\leq 8$.

  * (ii)

there must be one qubit in error that is at distance $\geq 4$ from the others.

For case (i), we know that all errors of weight $\leq 3$ take at most 10
iterations to converge, hence using Lemma 11, we conclude that this holds for
any toric code of distance $\geq 2\times 10+8=28$. Case (ii) can be taken care
of using Lemma 12 using the same argument as above, so we conclude this is
true for any toric code of distance $\geq 28$.

## References

  * [1] 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, arXiv:0801.1241.
  * [2] P. Panteleev and G. Kalachev, “Degenerate quantum LDPC codes with good finite length performance,” _Quantum_ , vol. 5, p. 585, 2021, arXiv:1904.02703.
  * [3] 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.
  * [4] J. du Crest, M. Mhalla, and V. Savin, “Stabilizer inactivation for message-passing decoding of quantum LDPC codes,” in _IEEE Information Theory Workshop (ITW)_. IEEE, 2022, pp. 488–493, arXiv:2205.06125.
  * [5] J. du Crest, F. Garcia-Herrero, M. Mhalla, V. Savin, and J. Valls, “Check-agnosia based post-processor for message-passing decoding of quantum LDPC codes,” _Quantum_ , vol. 8, p. 1334, 2024,  arXiv:2310.15000.
  * [6] 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, arXiv:0912.4546.
  * [7] 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,  arXiv:1903.07404.
  * [8] 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, arXiv:2104.13659.
  * [9] H. Yao, W. A. Laban, C. Häger, H. D. Pfister _et al._ , “Belief propagation decoding of quantum LDPC codes with guided decimation,” 2023, preprint, arXiv:2312.10950.
  * [10] J. Old and M. Rispler, “Generalized belief propagation algorithms for decoding of surface codes,” _Quantum_ , vol. 7, p. 1037, 2023, arXiv:2212.03214 .
  * [11] A. Y. Kitaev, “Fault-tolerant quantum computation by anyons,” _Annals of physics_ , vol. 303, no. 1, pp. 2–30, 2003, arXiv:quant-ph/9707021.
  * [12] Google Quantum AI, “Suppressing quantum errors by scaling a surface code logical qubit,” _Nature_ , vol. 614, no. 7949, pp. 676–681, 2023, arXiv:2207.06431.
  * [13] Y.-H. Liu and D. Poulin, “Neural belief-propagation decoders for quantum error-correcting codes,” _Phys. Rev. Lett._ , vol. 122, p. 200501, May 2019, arXiv:1811.07835.
  * [14] S. Varsamopoulos, K. Bertels, and C. G. Almudever, “Comparing neural network based decoders for the surface code,” _IEEE Transactions on Computers_ , vol. 69, no. 2, pp. 300–311, 2019, arXiv:1811.12456.
  * [15] N. Wiberg, “Codes and decoding on general graphs,” 1996. [Online]. Available: https://api.semanticscholar.org/CorpusID:115168171
  * [16] 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.
  * [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] G. H. Golub and C. F. Van Loan, _Matrix computations_. JHU press, 2013.
  * [19] W. Rozendaal and G. Zémor, “Analysis of the error-correcting radius of a renormalisation decoder for Kitaev’s toric code,” _IEEE Transactions on Information Theory_ , 2024, arXiv:2309.12165.
  * [20] X.-Y. Hu, E. Eleftheriou, and D.-M. Arnold, “Regular and irregular progressive edge-growth Tanner graphs,” _IEEE Transactions on Information Theory_ , vol. 51, no. 1, pp. 386–398, 2005, arXiv:1007.3588.