# Efficient decoding up to a constant fraction of the code length for
asymptotically good quantum codes

Anthony Leverrier Gilles Zémor Inria, France.
<EMAIL_ADDRESS>de Mathématiques de Bordeaux, UMR 5251,
France<EMAIL_ADDRESS>
###### Abstract

We introduce and analyse an efficient decoder for quantum Tanner codes that
can correct adversarial errors of linear weight. Previous decoders for quantum
low-density parity-check codes could only handle adversarial errors of weight
$O(\sqrt{n\log n})$. We also work on the link between quantum Tanner codes and
the Lifted Product codes of Panteleev and Kalachev, and show that our decoder
can be adapted to the latter. The decoding algorithm alternates between
sequential and parallel procedures and converges in linear time.

##  1 Introduction

###  1.1 Contributions

Historically, a major motivation behind the study of classical low-density
parity-check (LDPC) codes was the possibility of efficient decoding. In his
thesis, Gallager showed that random LDPC codes were asymptotically good codes
with high probability and proposed a first decoding algorithm based on message
passing [Gal62]. Much later, Sipser and Spielman introduced expander codes
which are explicit LDPC codes with a minimum distance linear in their length
$n$, together with an efficient decoder that provably corrects adversarial
errors of linear weight [SS96]. These expander codes are a special instance of
Tanner codes [Tan81] defined on a $\Delta$-regular expander graph: bits are
associated to the edges of the graph while parity-check constraints are
enforced at each vertex via small linear codes of length $\Delta$.

The LDPC property may be of even greater interest in the quantum case because
such codes can significantly reduce the required overhead for fault-tolerant
quantum computing [Got14]. For this, it is enough to find a code family
encoding $\Theta(n)$ logical qubits within $n$ physical qubits, with a
sufficient minimum distance $d=\Omega(n^{\alpha})$ for some $\alpha>0$ and an
efficient decoding algorithm. Quantum expander codes, which are obtained by
taking the hypergraph product [TZ14] of two expander codes, form one such
family when combined with the small-set-flip decoder [LTZ15, FGL18]. This
decoder corrects adversarial errors of weight proportional to the minimum
distance, that is $O(\sqrt{n})$. Very recently, Panteleev and Kalachev
discovered a first family of asymptotically good quantum LDPC codes [PK21a]
and suggested that a decoder similar to that of quantum expander codes might
be able to correct errors of large weight in linear time.

In the present paper, we describe such a linear-time decoder for quantum
Tanner codes [LZ22b], a family of good quantum LDPC codes obtained by applying
the Tanner code construction to a Left-Right Cayley complex [PK21a, DEL+21,
BE21] rather than to a graph. This decoder can correct adversarial errors of
linear weight. Previously, the best decoder available was able to correct
errors of weight $O(\sqrt{n\log n})$ [EKZ20].

###  1.2 Context and history

#### Quantum LDPC codes.

Quantum error correcting codes (QECC), initially devised to fight decoherence
with the goal of building large-scale quantum computers, have become a central
object of study in fields as diverse as computer science, topological phases
in physics, quantum information and even quantum gravity. Probably the best-
known QECC is the toric code of Kitaev which corresponds to the degenerate
ground-space of a simple local Hamiltonian defined on a torus [Kit03]. It is a
$2^{2}$-dimensional subspace encoding 2 qubits within the Hilbert space
$(\mathbbm{C}^{2})^{\otimes n}$ of $n$ physical qubits, defined as the common
eigenspace with eigenvalue 1 of a set of $n-2$ commuting Pauli operators,
called _generators_. The _minimum distance_ of a code is the minimal
weight111The weight of a Pauli operator is the number of qubits on which the
operator acts nontrivially. of a Pauli operator that commutes with all the
generators but that cannot be written as a product of generators. The toric
code achieves a remarkable distance of $\Theta(\sqrt{n})$, which remains the
current record for quantum codes with generators acting locally in a
topological space of constant dimension. In general, the parameters of such
local codes are rather severely constrained by the ambient space [BT09, BPT10,
Del13, BK22], and it is useful to relax the locality constraint and only
require that the generators of the code have constant weight, but are
otherwise arbitrary222We do not require the generators to be geometrically
local anymore, and they can therefore act on an arbitrary set of qubits. This
set should simply be of constant size.. In addition, we ask that any qubit is
involved in at most a constant number of generators. Such QECC are called
LDPC.

An important stepping stone in the study of quantum LDPC codes was the
constant-rate333The rate of a QECC is the ratio $k/n$ of the number $k$ of
logical qubits per physical qubit. generalisation of the toric code called
hypergraph (or homological) product construction that forms a quantum LDPC
code from two arbitrary classical LDPC codes [TZ14]. In particular, if the
classical codes are asymptotically good, then the resulting QECC has constant
rate and a minimum distance $d=\Theta(\sqrt{n})$. Ideas from higher-
dimensional expansion were useful to break the so-called _square-root barrier_
for the minimum distance, but only by polylogarithmic factors [EKZ20, KT21]. A
much more impressive improvement came from the idea of adding a twist to the
homological product construction [HHO20] to obtain
$d=\widetilde{\Theta}(n^{3/5})$. Further generalizations, either balanced
product codes or lifted product codes, were developed in [BE21] and [PK20] and
finally led to the asymptotically good quantum LDPC codes of Panteleev and
Kalachev [PK21a]. Hidden behind this final construction lies a higher-
dimensional generalization of a graph called a Left-Right Cayley complex
introduced in [DEL+21] to construct (classical) locally testable codes.
Combining this complex, which is a balanced product of Cayley graphs, with the
Tanner code construction of [Tan81] yields an alternative family of good
quantum LDPC codes called quantum Tanner codes [LZ22b]. It should be
emphasized that before these recent works, it was completely unclear whether
quantum LDPC codes with a minimum distance significantly above $\sqrt{n}$
could exist at all.

#### Decoders for quantum LDPC codes.

Topological codes, such as the toric code and its various generalizations in
higher dimensions, are by far the most studied quantum LDPC codes. In
particular, they now come with relatively efficient decoders that solve the
following problem: given the syndrome of a physical Pauli error
$\boldsymbol{e}$, i.e. the list of generators that do not commute with the
error, return a guess $\hat{\boldsymbol{e}}$ for the error such that
$\boldsymbol{e}$ and $\hat{\boldsymbol{e}}$ differ by a product of
generators444In this case, $\boldsymbol{e}$ and $\hat{\boldsymbol{e}}$ are
called _equivalent_., which is sufficient since generators act trivially on
the codespace. This is a crucial relaxation compared to the classical decoding
problem which requires to recover the exact error. While this could suggest at
first sight that the decoding problem is simpler in the quantum case, this is
in fact far from clear. A typical issue arises when the error corresponds to
half a generator. In that case, it might not be clear for the decoder how to
break the symmetry between the two equivalent errors corresponding to each
half of the generator. A related observation is that the value of the error on
a given qubit is never well defined since it is straightforward to find
equivalent errors with a distinct action on that qubit. These issues are by
now relatively well understood for topological codes and the minimum weight
perfect matching decoder [Edm65] yields a decoder with very good performance
and a reasonable complexity of $O(n^{3})$. Faster decoders exist for
topological codes, for instance Union-Find has essentially a linear complexity
in the worst case and performs optimally for errors of weight less than
$(d-1)/2$ [DN21].

Decoding more general, non topological LDPC codes, appears to be more
challenging. While some solutions behave reasonably well against random
errors, most notably the combination of Belief Propagation and Ordered
Statistics Decoding proposed in [PK21b], an important challenge is to
understand how well one can correct adversarial errors. Inspired by a decoder
of Hastings [Has14] for 4-dimensional hyperbolic codes [GL14], the small-set-
flip (SSF) decoder of quantum expander codes can correct $\Theta(\sqrt{n})$
errors and works in a greedy fashion by trying to find small local patterns
that can decrease the syndrome weight [LTZ15]. The decoder of [EKZ20] exploits
the homological product structure in a more global way to (slightly) beat the
$\sqrt{n}$ bound. The recent invention of good quantum LDPC codes raises the
natural question of whether one can indeed correct adversarial errors of
linear weight in polynomial, or even linear time555We note that [LH22] studies
such a decoder for a possible construction of asymptotically good quantum LDPC
codes that relies on a conjecture about the existence of 2-sided lossless
expander graphs with free group action.. We answer this question in the
affirmative, but note that our decoder is somewhat more complicated than SSF.
In particular, while the _normal_ mode of the decoder is very similar to SSF,
we also need to consider an _exceptional_ mode to take care of potentially
problematic error patterns.

#### Comparison with recent results.

Two independent works with decoders for linear weight errors have appeared at
the same time as the present manuscript. First Gu, Pattison and Tang present
and analyse a related decoder for quantum Tanner codes [GPT22]. Instead of
directly decoding the mismatch as here, they compute a global cost function
equal to the sum of the weights of all the local corrections, and apply a
greedy algorithm to find out which qubits to flip in order to decrease the
value of the function. Technically, they improve the bound on the robustness
of random codes, and show that there exists $\varepsilon>0$ such that the dual
of the tensor code obtained from random codes of length $\Delta$ is
$\Delta^{3/2+\varepsilon}$-robust with probability tending to 1 when the
length $\Delta$ goes to infinity. This better robustness, strictly better than
$\Delta^{3/2}$ allows for a simplified decoding algorithm, without any need
for an exceptional mode as in the present paper. Then Dinur, Hsieh, Lin and
Vidick present a variation of the codes of Panteleev and Kalachev, where the
roles of the qubits and of the generators are exchanged [DHLV22]. One
advantage is that the qubits are associated with 1-cells of the chain complex
while the generators are associated with 2-cells and 0-cells, which
corresponds to the standard framework of mapping a chain complex to a CSS
code. The hope is that this variation will generalise more easily to longer
chain complexes, which may be helpful to design elusive quantum locally
testable codes [AE15, Has17, LLZ22]. Remarkably, [DHLV22] establishes that
dual of tensor codes obtained from random codes satisfy optimal robustness, up
to $\Omega(\Delta^{2})$. This result was also obtained independently by
Kalachev and Panteleev [KP22]. This better robustness then allows the authors
to show that their quantum LDPC codes are also asymptotically good, similarly
to the original PK codes and to quantum Tanner codes. Furthermore, it is also
possible to extend the small set flip decoder of [LTZ15] to design decoders
for both kinds of errors that correct arbitrary errors up to a linear weight.

Finally, the decoding algorithm introduced in the present paper can be
significantly simplified if the local codes display optimal robustness. In
that case, it becomes possible to parallelize the decoding procedure of both
PK codes and quantum Tanner codes to obtain a logarithmic-time complexity
[LZ22a].

The paper is organised as follows. Section 2 gives an overview of the paper,
recalls the construction of the quantum Tanner codes, describes the decoding
algorithm and states our main result showing that the decoder corrects all
error patterns of weight below a constant fraction of the code length. Section
3 is a preliminary to the detailed part of the paper and introduces the
required technical material. Section 4 gives a detailed description of the
quantum Tanner codes which rely here on a quadripartite version of the left-
right Cayley complex and not a bipartite version as in [LZ22b], since this
would complicate the exposition. Similarly, Section 5 discusses the decoding
algorithm and the tools used in its analysis. Section 6 is the core of the
paper, giving the precise description of the decoder and its detailed
analysis, and establishing the main theorem. Finally, Section 7 explores the
links between the quantum Tanner codes and the lifted product codes of
Panteleev and Kalachev, and explains how our decoding algorithm yields an
efficient decoder for the lifted product codes as well, thereby solving an
open problem of [PK21a].

##  2 Overview

#### The left-right Cayley complex.

We will work with the square complex of [PK21a], which can also be thought of
as a quadripartite version [Gol21] of the square complex of Dinur et al.
[DEL+21]. We recall its construction, using the language of [DEL+21]. It is an
incidence structure $X$ between a set $V$ of vertices, two sets of edges
$E_{A}$ and $E_{B}$, that we will refer to as $A$-edges and $B$-edges, and a
set $Q$ of squares (or quadrangles). The vertex-set $V$ is defined from a
group $G$. While we used a slightly more general bipartite version version of
the complex in [LZ22b], we prefer to use here the quadripartite version as it
will simplify the exposition. The vertex set is therefore partitioned as
$V=V_{00}\cup V_{01}\cup V_{10}\cup V_{11}$, with each part identified as a
copy of the group $G$. Formally, we set $V_{ij}=G\times\\{ij\\}$ for
$i,j\in\\{0,1\\}$. We also have two self-inverse subsets $A=A^{-1}$ and
$B=B^{-1}$ of the group $G$: for $i\in\\{0,1\\}$, a vertex $v=(g,i0)\in
V_{i0}$ and a vertex $v^{\prime}=(g^{\prime},i1)\in V_{i1}$ are said to be
related by an $A$-edge if $g^{\prime}=ag$ for some $a\in A$. Similarly, for
$j\in\\{0,1\\}$, vertices $v=(g,0j)$ and $v^{\prime}=(gb,1j)$ are said to be
related by a $B$-edge if $g^{\prime}=gb$ for some $b\in B$. The sets $E_{A}$
and $E_{B}$ make up the set of $A$-edges and $B$-edges respectively, and
define graphs $\mathcal{G}_{A}$ and $\mathcal{G}_{B}$ where $\mathcal{G}_{A}$
consists of two copies of the double cover of the left Cayley graph ${\sf
Cay}(G,A)$ and $\mathcal{G}_{B}$ consists of two copies of the double cover of
the right Cayley graph ${\sf Cay}(G,B)$.

Next, the set $Q$ of squares is defined as the set of $4$-subsets of vertices
of the form

$\\{(g,00),(ag,01),(gb,10),(agb,11)\\}.$

The four vertices of a square threrefore belong to the four distinct copies of
$G$, as depicted on Figure 1.

An advantage of the quadripartite version we consider here is that we do not
need to enforce any additional constraint on $G,A,B$ such as the Total No-
Conjugacy condition defined in [DEL+21] requiring that $ag\neq gb$ for all
choices of $g,a,b$.

$g\in V_{00}$$ag\in V_{01}$$agb\in V_{11}$$gb\in V_{10}$ Figure 1: Square
$\\{(g,00),(ag,01),(agb,11),(gb,10)\\}$ of the complex.

If we restrict the vertex set to $V_{0}:=V_{00}\cup V_{11}$, every square is
now incident to only two vertices: one in $V_{00}$ and one in $V_{11}$. The
set of squares can then be seen as a set of edges on $V_{0}$, and it therefore
defines a bipartite graph that we denote by
$\mathcal{G}_{0}^{\square}=(V_{0},Q)$. Similarly, the restriction to the
vertices of $V_{1}:=V_{01}\cup V_{10}$ defines the graph
$\mathcal{G}_{1}^{\square}$, which is an exact replica of
$\mathcal{G}_{0}^{\square}$: both graphs are defined over two copies of the
group $G$, with $g,g,^{\prime}\in G$ being related by an edge whenever
$g^{\prime}=agb$ for some $a\in A,b\in B$. We assume for simplicity that $A$
and $B$ are of the same cardinality $\Delta$. For any vertex $v$, we denote by
$Q(v)$ the $Q$-neighbourhood of $v$ which is defined as the set of squares
incident to $v$. The $Q$-neighbourhood $Q(v)$ has cardinality $\Delta^{2}$ and
is isomorphic to the product set $A\times B$: the situation is illustrated on
Figure 2 and discussed in detail in Section 4.

$Q(g,00)$$Q(gb,10)$$Q(ag,01)$$Q(agb,11)$$b$$b$$a$$a$ Figure 2: The four local
views $Q(v)$ that contain the square $\\{(g,00),(ag,01),(agb,11),(gb,10)\\}$.
The views of two vertices connected by an $A$-edge (resp. a $B$-edge) share a
row depicted in red (resp. a column in blue). The labeling is chosen to ensure
that a given square, such as the one in red and blue, is indexed similarly, by
$(a,b)$ here, in the four local views. The $\sigma_{X}$-type generators are
codewords of $C_{A}\otimes C_{B}$ in the local views of $V_{00}\cup V_{11}$;
the $\sigma_{Z}$-type generators are codewords of $C_{A}^{\perp}\otimes
C_{B}^{\perp}$ in the local views of $V_{01}\cup V_{10}$. They automatically
commute since their support can only intersect on a shared row or column (as
depicted), and the orthogonality of the local codes ensure that they commute
on this row or column.

#### Quantum Tanner codes on the complex $X$.

A _Tanner code_ , or expander code, on a $\Delta$-regular graph
$\mathcal{G}=(V,E)$ is the set of binary vectors indexed by $E$ (functions
from $E$ to $\mathbb{F}_{2}$), such that on the edge neighbourhood of every
vertex $v\in V$, we see a codeword of a small code $C$ of length $\Delta$
[Tan81, SS96]. We denote the resulting code by
$\text{Tan}(\mathcal{G},C)\subset\mathbb{F}_{2}^{E}$.

Following [LZ22b], we consider _quantum Tanner codes_ which are quantum CSS
codes formed by two classical Tanner codes $\mathcal{C}_{0}$ and
$\mathcal{C}_{1}$ with support on the set $Q$ of squares of a Left-Right
Cayley complex. The CSS construction requires both codes to satisfy the
orthogonality condition $\mathcal{C}_{0}^{\perp}\subset\mathcal{C}_{1}$.
Enforcing this condition requires some care for the choice of the local codes
of $\mathcal{C}_{0}$ and $\mathcal{C}_{1}$. We will define local codes on the
space $\mathbb{F}_{2}^{A\times B}$ that we may think of as the space of
matrices whose rows (columns) are indexed by $A$ (by $B$). If
$C_{A}\subset\mathbb{F}_{2}^{A}$ and $C_{B}\subset\mathbb{F}_{2}^{B}$ are two
linear codes, we define the tensor (or product) code $C_{A}\otimes C_{B}$ as
the space of matrices $x$ such that for every $b\in B$ the column vector
$(x_{ab})_{a\in A}$ belongs to $C_{A}$ and for every $a\in A$ the row vector
$(x_{ab})_{b\in B}$ belongs to $C_{B}$. Recall that the dual $C^{\perp}$ of a
code $C$ of length $n$ is the set of words orthogonal to all words in $C$:

$C^{\perp}:=\\{x\in\mathbb{F}_{2}^{n}\>:\>\langle x,y\rangle=0\;\forall y\in
C\\}.$

We finally define $\mathcal{C}_{0}$ and $\mathcal{C}_{1}$ to be the following
classical Tanner codes:

$\mathcal{C}_{0}=\text{Tan}(\mathcal{G}_{0}^{\square},(C_{A}\otimes
C_{B})^{\perp}),\quad\mathcal{C}_{1}=\text{Tan}(\mathcal{G}_{1}^{\square},(C_{A}^{\perp}\otimes
C_{B}^{\perp})^{\perp}),$

with bits associated to each square of $Q$ and local constraints enforced at
the vertices of $V_{0}$ and $V_{1}$, respectively. We will refer to the dual
of tensor codes $(C_{A}\otimes C_{B})^{\perp}$ as _dual tensor codes_. Let us
denote $C_{0}:=C_{A}\otimes C_{B}$ and $C_{1}:=C_{A}^{\perp}\otimes
C_{B}^{\perp}$, so that
$\mathcal{C}_{i}=\text{Tan}(\mathcal{G}_{i}^{\square},C_{i}^{\perp})$ for
$i\in\\{0,1\\}$. To check the orthogonality condition between the two codes,
it is convenient to look at their generators (or parity-checks). We define a
$C_{0}$-generator for $\mathcal{C}_{0}$ (resp. a $C_{1}$-generator for
$\mathcal{C}_{1}$) as a vector of $\mathbb{F}_{2}^{Q}$ whose support lies
entirely in the $Q$-neighborhood $Q(v)$ of $V_{0}$ (resp. $V_{1}$), and which
is equal to a codeword of $C_{0}$ (resp. $C_{1}$) on $Q(v)$. The Tanner code
$\mathcal{C}_{0}$ (resp. $\mathcal{C}_{1}$) is defined as the set of vectors
orthogonal to all $C_{0}$-generators (resp. $C_{1}$-generators). The condition
$\mathcal{C}_{0}^{\perp}\subset\mathcal{C}_{1}$ simply says that all
$C_{0}$-generators are orthogonal to all $C_{1}$-generators: this follows from
the fact that if a $C_{0}$-generator on $v_{0}\in V_{0}$ and a
$C_{1}$-generator on $v_{1}\in V_{1}$ have intersecting supports, then $v_{0}$
and $v_{1}$ must be neighbours in the left-right Cayley complex and their
local views must intersect on either a column or a row, on which the two
generators equal codewords of $C_{A}$ and $C_{A}^{\perp}$, or of $C_{B}$ and
$C_{B}^{\perp}$ (see Fig. 2).

We denote by $\mathcal{Q}=(\mathcal{C}_{0},\mathcal{C}_{1})$ the _quantum
Tanner code_ obtained in this way from $\mathcal{C}_{0}$ and
$\mathcal{C}_{1}$, and recall the main result from [LZ22b].

######  Theorem 1 (Quantum Tanner codes are asymptotically good [LZ22b]).

There exists an infinite family of square complexes $X$ such that the
following holds. For any $\rho\in(0,1/2)$, $\varepsilon\in(0,1/2)$ and
$\delta>0$ satisfying
$-\delta\log_{2}\delta-(1-\delta)\log_{2}(1-\delta)<\rho,$ randomly choosing
$C_{A}$ and $C_{B}$ of rates $\rho$ and $1-\rho$ yields, with probability $>0$
for $\Delta$ large enough, an infinite sequence of quantum codes
$\mathcal{Q}=(\mathcal{C}_{0},\mathcal{C}_{1})$ of rate $(2\rho-1)^{2}$,
length $n$ and minimum distance $\geqslant\delta n/4\Delta^{3/2+\varepsilon}$.

Concretely, the complexes $X$ that work in Theorem 1 are all complexes such
that ${\sf Cay}(G,A)$ and ${\sf Cay}(G,B)$ are Ramanujan graphs and for which
$\Delta$ is fixed, independent of the complex size, and large enough.

The proof of Theorem 1 in [LZ22b] went along the following lines: If one
considers a codeword $\mathbf{x}$ of $\mathcal{C}_{1}^{\square}$ and
identifies it with its support, a set of squares that reduces to a set of
edges in the graph $\mathcal{G}_{1}^{\square}$, then this is a subgraph of
minimum degree at least $\delta\Delta$, a lower bound on the minimum distance
of the component dual tensor code. Expansion in $\mathcal{G}_{1}^{\square}$ is
not quite enough to deduce that $|\mathbf{x}|$ must be large, but if
$|\mathbf{x}|$ is small, expansion does tell us that its local views on
vertices of $V_{1}$ must have a small weight (close to $\Delta$) on average.
If we decompose these local views, which have the structure of dual tensor
codewords on $A\times B$, as sums of column vectors, i.e. elements of
$C_{A}\otimes\mathbb{F}_{2}^{B}$, and row vectors in
$\mathbb{F}_{2}^{A}\otimes C_{B}$, then, the definition of the complex $X$
tells us that the individual column and row vectors from these local views
also exist in the $Q$-neighbourhoods of vertices of $V_{0}$. Switching to
expansion in the graphs $\mathcal{G}_{A}$ and $\mathcal{G}_{B}$, we obtain
that most individual column $C_{A}$-codewords and row $C_{B}$-codewords from
the $Q$-neighbourhoods of vertices of $V_{1}$, must cluster around local views
of vertices of $V_{0}$. A local analysis of these clustered local views then
shows that adding some non-zero tensor codeword must reduce its Hamming
weight, and in this way one obtains iteratively that the global codeword
$\mathbf{x}$ of $\mathcal{C}_{1}$ can be expressed as a sum of generators,
which yields the lower bound on the minimum distance.

#### Robustness of the component codes $C_{A}$ and $C_{B}$.

Crucial to the analysis sketched above is the ability to claim that if a dual
tensor codeword $x=(x_{ab})\in\mathbb{F}_{2}^{A\times B}$ has sufficiently
small weight, then it can be expressed as a sum $x=r+c$, where the union of
row codewords $r\in\mathbb{F}_{2}^{A}\otimes C_{B}$ and the union of column
codewords $c\in C_{A}\otimes\mathbb{F}_{2}^{B}$ are both of small weight. This
is a robustness property. More precisely, we say that a dual tensor code
$(C_{A}^{\perp}\otimes
C_{B}^{\perp})^{\perp}=C_{A}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes
C_{B}$ is $w$-robust if any codeword $x$ of weight $\leqslant w$ has its
support included in the union of $|x|/d_{A}$ columns and $|x|/d_{B}$ rows,
where $d_{A}$ and $d_{B}$ are the minimum distances of $C_{A}$ and $C_{B}$. A
similar notion is used both in [DEL+21] and [PK21a]. What was shown in [LZ22b]
is that for any $\varepsilon>0$ and large enough $\Delta$, when $C_{A}$ and
$C_{B}$ are chosen at random, then the dual tensor codes $(C_{A}\otimes
C_{B})^{\perp}$ and $(C_{A}^{\perp}\otimes C_{B}^{\perp})^{\perp}$ are both
$\Delta^{3/2-\varepsilon}$-robust with high probability. This property will
again be crucial when considering decoding issues.

#### The decoding problem.

A standard property of QECC is that the ability to correct all Pauli errors of
weight up to $t$ implies the ability to correct _arbitrary_ errors of weight
less than $t$. For a CSS code, bit flips and phase flips can be decoded
independently, and it is therefore sufficient to consider only one type of
errors. Since we chose $C_{A}$ and $C_{B}$ of rate $\rho$ and $1-\rho$,
respectively, we see that the classical Tanner codes $\mathcal{C}_{0}$ and
$\mathcal{C}_{1}$ have the same parameters and that the resulting quantum
Tanner codes will protect equally well against bit flips and phase flips.
Without loss of generality, we therefore consider a phase-flip error with
support on $\boldsymbol{e}\in\mathbb{F}_{2}^{Q}$. This error is detected by
the classical Tanner code $\mathcal{C}_{1}$, and the goal of the decoder is to
output an error candidate $\hat{\boldsymbol{e}}$ such that
$\boldsymbol{e}+\hat{\boldsymbol{e}}\in\mathcal{C}_{0}^{\perp}$. Recall indeed
that an element of $\mathcal{C}_{0}^{\perp}$ is a sum of generators, and
therefore acts trivially on the codespace. For this reason, it is not
necessary to recover the exact error $\boldsymbol{e}$, and any _equivalent_
error in the coset $\boldsymbol{e}+\mathcal{C}_{0}^{\perp}$ is equally good.

An approach mentioned in [LZ22b] for decoding (classical) Tanner codes is to
define a _mismatch_ vector that summarises how the local decoders associated
to each local code may disagree about the error, and then try to locally
modify this mismatch in order to reduce its weight. It is natural to see the
error $\boldsymbol{e}$ as a collection of local views on the vertices of
$V_{1}$: abusing notation slightly, we can write
$\boldsymbol{e}=\\{e_{v}\\}_{v\in V_{1}}$, where we see the local views
$e_{v}$ both as small length vectors in $\mathbb{F}_{2}^{Q(v)}$ and as vectors
of $\mathbb{F}_{2}^{Q}$ with $0$ coordinate values outside $Q(v)$. Since each
square of $Q$ belongs both to a local view of $V_{01}$ and to a local view of
$V_{10}$, we have that $\sum_{v\in V_{01}}e_{v}=\sum_{v\in V_{10}}e_{v}$. For
each vertex $v\in V_{1}$, one can compute a local error $\varepsilon_{v}$ with
support on $Q(v)$ of minimal Hamming weight yielding the corresponding local
syndrome. This gives a decomposition of the local views of the error

$e_{v}=\varepsilon_{v}+c_{v}+r_{v},$

with $c_{v}\in C_{A}\otimes\mathbb{F}_{2}^{B},r_{v}=\mathbb{F}_{2}^{A}\otimes
C_{B}$, and $\varepsilon_{v}$ of minimal Hamming weight. Here, we have that
$c_{v}+r_{v}$ is a codeword of the dual tensor code
$C_{1}^{\perp}=C_{A}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes
C_{B}$. The issue is that the local views $\\{\varepsilon_{v}\\}_{v\in V_{1}}$
are in general not consistent and do not define a global error candidate. We
measure this inconsistency by defining the mismatch vector

$Z:=\sum_{v\in V_{1}}\varepsilon_{v}\in\mathbb{F}_{2}^{Q}.$ (1)

If it is equal to zero, it means that each square/qubit is affected the same
value for the two views it belong to, and the decoder is able to define a
global error. Otherwise, the support of $Z$ corresponds to the set of squares
for which the local views disagree. Exploiting the previous remark that
$\sum_{v\in V_{1}}e_{v}=0$, we can rewrite the mismatch as

$Z=\sum_{v\in V_{1}}r_{v}+c_{v}=C_{0}+R_{0}+C_{1}+R_{1},$

where we defined

$C_{0}=\sum_{v\in V_{10}}c_{v},\quad R_{0}=\sum_{v\in V_{01}}r_{v},\quad
C_{1}=\sum_{v\in V_{01}}c_{v},\quad R_{1}=\sum_{v\in V_{10}}r_{v}.$

The idea behind our decoder is to find a decomposition
$\\{\hat{r}_{v},\hat{c}_{v}\\}_{v\in V_{1}}$ such that $Z=\sum_{v\in
V_{1}}\hat{r}_{v}+\hat{c}_{v}$. In that case, the decoder will output the
error candidate $\hat{\boldsymbol{e}}=\\{\hat{e}_{v}\\}_{v\in V_{1}}$ with

$\hat{e}_{v}:=\varepsilon_{v}+\hat{r}_{v}+\hat{c}_{v}.$ (2)

In particular, the vectors $\boldsymbol{e}$ and $\hat{\boldsymbol{e}}$ differ
by an element of $\mathcal{C}_{1}$ (since they have the same syndrome on
$V_{1}$), and a sufficient condition to guarantee the success of the decoder
is that $|\boldsymbol{e}+\hat{\boldsymbol{e}}|$ is less than the minimum
distance. In that case, it means that $\boldsymbol{e}$ and
$\hat{\boldsymbol{e}}$ necessarily differ by an element of
$\mathcal{C}_{0}^{\perp}$, that is a sum of generators. It is not difficult to
see that $|Z|=O(|\boldsymbol{e}|)$. Therefore if
$|\boldsymbol{e}|\leqslant\kappa n$ for some sufficiently small $\kappa>0$ and
if the algorithm can find $\hat{\boldsymbol{e}}$ of weight at most $O(|Z|)$,
then the decoder will return a correct solution since the minimum distance is
linear in $n$.

We now describe the main subroutine of decoding algorithm, which aims at
finding a decomposition $Z=\sum_{v\in V_{1}}\hat{r}_{v}+\hat{c}_{v}$. We will
keep track of 5 vectors initialized as follows

$\hat{Z}:=Z,\quad\hat{C}_{0}:=0,\quad\hat{R}_{0}:=0,\quad\hat{C}_{1}:=0,\quad\hat{R}_{1}:=0.$

It will alternate between two procedures:

#### Sequential procedure in $V_{0}$.

While there exists some $v\in V_{ii}$ and $c_{v}\in
C_{A}\otimes\mathbb{F}_{2}^{B},r_{v}\in\mathbb{F}_{2}^{A}\otimes C_{B}$ such
that $|\hat{Z}+c_{v}+r_{v}|<|\hat{Z}|$, perform the update:

$\hat{Z}\leftarrow\hat{Z}+c_{v}+r_{v},\quad\hat{C}_{i}\leftarrow\hat{C}_{i}+c_{v},\quad\hat{R}_{i}\leftarrow\hat{R}_{i}+r_{v}.$

Now it may happen that this sequential decoder will get stalled at some point,
and not be able to decrease the Hamming weight $|\hat{Z}|$ by a local
modification on a $Q$-neighbourhood of a vertex of $V_{0}$. When this happens,
we can consider the subgraph of $\mathcal{G}_{0}^{\square}$ induced by the
vector $(R_{0}+C_{0})\cap(R_{1}+C_{1})$ and realise that its minimum degree
must be at least $\delta\Delta/2$ (provided the initial error $\boldsymbol{e}$
is of sufficently small weight). Conceptually, this subgraph does not look
very different from a Tanner codeword, and if we follow the blueprint of the
proof of the lower bound on the minimum distance (sketched just after Theorem
1), then it is natural to expect that the stalled decoder will be unlocked
simply by switching the sequential decoding procedure to vertices of $V_{1}$.
However, we cannot quite make this work. The issue is that we again need
robustness of the component codes $C_{A},C_{B}$, and this time the robustness
parameter $w=\Delta^{1/2-\varepsilon}$ guaranteed us by random choice falls
just short. To circumvent this problem, we use a more complicated decoding
procedure to unlock the stalled sequential decoder. It consists of two rounds
of parallel decoding.

#### Parallel decoding procedure.

  * –

First parallel decoding step, on vertices of $V_{1}$. Identify vertices of
$V_{1}$ for which there exists $c_{v}\in
C_{A}\otimes\mathbb{F}_{2}^{B},r_{v}\in\mathbb{F}_{2}^{A}\otimes C_{B}$ and
subsets $A_{0}\subset A$ and $B_{0}\subset B$ of the local coordinate sets
that are sufficiently large and such that the Hamming weight of
$\hat{Z}+c_{v}+r_{v}$ decreases sufficiently on the reduced coordinate set
$A_{0}\times B_{0}$. For all vertices $v$ where this is satisfied, update as
before:

$\hat{Z}\leftarrow\hat{Z}+c_{v}+r_{v},\quad\hat{C}_{j}\leftarrow\hat{C}_{j}+c_{v},\quad\hat{R}_{i}\leftarrow\hat{R}_{i}+r_{v}.$

See Section 6.1 for a precise description of the criteria for updating.

  * –

Second parallel decoding step, on vertices of $V_{0}$. Identify vertices of
$V_{0}$ for for which there exists $c_{v}\in
C_{A}\otimes\mathbb{F}_{2}^{B},r_{v}\in\mathbb{F}_{2}^{A}\otimes C_{B}$ such
that $|\hat{Z}+c_{v}+r_{v}|<|\hat{Z}|$. Among all possible choices, maximise
the difference $|\hat{Z}|-|\hat{Z}+c_{v}+r_{v}|$. For all such vertices
perform the update

$\hat{Z}\leftarrow\hat{Z}+c_{v}+r_{v},\quad\hat{C}_{j}\leftarrow\hat{C}_{j}+c_{v},\quad\hat{R}_{i}\leftarrow\hat{R}_{i}+r_{v}.$

What the decoder does by default is apply the sequential decoding procedure.
Whenever this is not possible, it applies the parallel decoding procedure. It
continues until $\hat{Z}=0$, at which point it stops and outputs
$(\hat{R}_{0},\hat{C}_{0},\hat{R}_{1},\hat{C}_{1})$.

A word of comment is in order here. As mentioned above, what happens is that
when the sequential decoder is stalled, we cannot guarantee the existence of a
$Q$-neighbourhood $Q(v)$, for $v\in V_{1}$, on which we can decrease
$|\hat{Z}|$. But this is almost the case: what we can guarantee is the
existence of vertices $v$ for which one can decrease $|\hat{Z}|$ on a large
subset of $Q(v)$. Furthermore, this will be the case for most vertices of
$V_{1}$ on whose $Q$-neighbourhoods $\hat{Z}$ has a large Hamming weight: this
is why we apply this tweaked local decoding procedure in parallel on all
possible vertices of $V_{1}$. After this first parallel decoding step we
cannot guarantee that $|\hat{Z}|$ has decreased, however we can guarantee a
substancial decrease of $|\hat{Z}|$ after the second parallel decoding step
described above.

Finally, the output of the decoder gives us a decomposition
$Z=\hat{C}_{0}+\hat{R}_{0}+\hat{C}_{1}+\hat{R}_{1}$ of the original mismatch
(1). For $v\in V_{01}$, the local view $\hat{r}_{v}$ of $\hat{R}_{0}$ and the
local view $\hat{c}_{v}$ of $\hat{C}_{1}$ give the required local view (2) of
a candidate global error vector $\hat{\boldsymbol{e}}$, while for $v\in
V_{10}$ the local view $\hat{e}_{v}$ of $\hat{\boldsymbol{e}}$ stems from the
local views of $\hat{R}_{0}$ and $\hat{C}_{1}$.

Our main result states that the above decoder will always succeed in producing
an adequate error vector $\hat{\boldsymbol{e}}$, provided the initial error
weight $|\boldsymbol{e}|$ is a sufficiently small fraction of the code length.

######  Theorem 2.

There exists a constant $\kappa$, depending only on $\delta$, a lower bound
for the minimum distances of both component codes $C_{A}$ and $C_{B}$, such
that for large enough fixed $\Delta$, the above decoding algorithm corrects
all error patterns of weight less than $\kappa n/\Delta^{4}$ for the quantum
Tanner code of length $n=|Q|$.

Since the decoder needs only to look at $Q$-neighbourhoods on which the
mismatch $|Z|$ is nonzero, by carefully keeping track of this set of vertices,
we obtain a decoder that runs in linear time.

A direct consequence of the analysis is the soundness of the code, a weaker
property than local testability that asserts that sufficiently small errors
have a syndrome with a weight proportional to that of the error (local
testability would require this to hold for arbitrary errors). This result was
previously established for quantum Tanner codes in [HL22].

Interestingly, our decoder can be adapted to work with the asymptotically good
codes of Panteleev and Kalachev [PK21a]. In particular, we show that the
theorem above still holds for these codes, provided the error patterns have
weight at most $\kappa n/\Delta^{6}$. Along the way, we point out the hidden
relation between the quantum Tanner codes and the lifted product codes of
[PK21a].

#### Additional comments.

So as to not let the analysis of the decoder become overly burdensome, we have
not tried to make the constant $\kappa$ explicit in Theorem 2, nor have we
tried to optimise the dependency in $\Delta$ of the number of correctable
errors. For a similar reason, we have left out possible variations on the
decoder. In particular, since one has to resort to parallel decoding when the
sequential decoder is stalled, a natural temptation is to make the decoder
fully parallel and replace the sequential decoding step by a parallel one. We
do not anticipate difficulties of a novel nature in doing so, but our analysis
stems rather naturally from a sequential approach to decoding, and we have
tried to limit the flow of technicalities by avoiding these variations.

As mentioned in [PK21a] and [LZ22b], the question of alternatives to random
choice for the component codes $C_{A},C_{B}$ remains open. Additionally,
finding component codes $C_{A},C_{B}$ with better robustness would simplify
our analysis and yield a fully sequential decoder. On the other hand, showing
that decoding a linear number of adversarial errors is possible with reduced
robustness potentially simplifies the search for constructions of adequate
component codes.

#### Acknowledgements.

We would like to thank Benjamin Audoux, Alain Couvreur, Shai Evra, Omar Fawzi,
Tali Kaufman, Jean-Pierre Tillich, and Christophe Vuillot for many fruitful
discussions on quantum codes over the years. We acknowledge support from the
Plan France 2030 through the project NISQ2LSQ, ANR-22-PETQ-0006. GZ also
acknowledges support from the ANR through the project QUDATA,
ANR-18-CE47-0010.

##  3 Preliminaries

###  3.1 Expander Graphs

Let $\mathcal{G}=(V,E)$ be a graph. Graphs will be undirected but may have
multiple edges. For $S,T\subset V$, let $E(S,T)$ denote the multiset of edges
with one endpoint in $S$ and one endpoint in $T$. Let $\mathcal{G}$ be a
$\Delta$-regular graph on $n$ vertices, and let
$\Delta=\lambda_{1}\geqslant\lambda_{2}\geqslant\ldots\geqslant\lambda_{n}$ be
the eigenvalues of the adjacency matrix of $\mathcal{G}$. For $n\geqslant 3$,
we define
$\lambda(\mathcal{G}):=\max\\{|\lambda_{i}|,\lambda_{i}\neq\pm\Delta\\}$. The
graph $\mathcal{G}$ is said to be _Ramanujan_ if
$\lambda(\mathcal{G})\leqslant 2\sqrt{\Delta-1}$.

We recall the following version of the expander mixing lemma (see e.g.
[HLW06]) for bipartite graphs.

######  Lemma 3 (Expander mixing lemma).

Let $\mathcal{G}$ be a connected $\Delta$-regular bipartite graph on the
vertex set $V_{0}\cup V_{1}$. For any pair of sets $S\subset V_{0},T\subset
V_{1}$, it holds that

$|E(S,T)|\leqslant\frac{\Delta}{|V_{0}|}|S||T|+\lambda(\mathcal{G})\sqrt{|S||T|}.$

###  3.2 Tanner codes

A binary linear code of length $n$ is an $\mathbb{F}_{2}$-linear subspace of
$\mathbb{F}_{2}^{n}$. For sets $E$ of cardinality $|E|=n$, it will be
convenient for us to identify $\mathbb{F}_{2}^{n}$ with $\mathbb{F}_{2}^{E}$,
which we can think of as the space of functions from $E$ to $\mathbb{F}_{2}$.
Identication with $\mathbb{F}_{2}^{n}$ amounts to defining a one-to-one map
between $E$ and $[n]=\\{1,2,\ldots,n\\}$, i.e. a numbering of the elements of
$E$.

Let $\mathcal{G}=(V,E)$ be a regular graph of degree $\Delta$, and for any
vertex $v$ denote by $E(v)$ the set of edges incident to $v$. Assume an
identification of $\mathbb{F}_{2}^{E(v)}$ with $\mathbb{F}_{2}^{\Delta}$ for
every $v\in V$. Let $x\in\mathbb{F}_{2}^{E}$ be a vector indexed by (or a
function defined on) the set $E$. Let us define the local view of $x$ at
vertex $v$ as the subvector $x_{v}:=(x_{e})_{e\in E(v)}$, i.e. $x$ restricted
to the edge-neighbourhood $E(v)$ of $v$.

Let $C_{0}$ be a linear code of length $\Delta$, dimension
$k_{0}=\rho_{0}\Delta$, and minimum distance $d_{0}=\delta_{0}\Delta$. We
define the Tanner code [Tan81] associated to $\mathcal{G}$ and $C_{0}$ as

$\text{Tan}(\mathcal{G},C_{0}):=\\{x\in\mathbb{F}_{2}^{E}:x_{v}\in
C_{0}\;\text{for all}\;v\in V\\}.$

In words, the Tanner code is the set of vectors over $E$ all of whose local
views lie in $C_{0}$. By counting the number of linear equations satisfied by
the Tanner code, we obtain

$\dim\text{Tan}(\mathcal{G},C_{0})\geqslant(2\rho_{0}-1)n.$ (3)

We also have the bound [SS96, Gur10] on the minimum distance $d$ of the Tanner
code:

$d\geqslant\delta_{0}(\delta_{0}-\lambda(\mathcal{G})/\Delta)n.$

Therefore, if $(\mathcal{G}_{i})$ is a family of $\Delta$-regular expander
graphs with $\lambda(\mathcal{G}_{i})\leqslant\lambda<d_{0}$, and if
$\rho_{0}>1/2$, then the associated family of Tanner codes has rate and
minimum distance which are both $\Omega(n)$, meaning we have an asymptotically
good family of codes, as was first shown in [SS96].

###  3.3 Quantum CSS codes

A quantum CSS code is specific instance of a stabilizer code [Got97] that can
be defined by two classical codes $\mathcal{C}_{0}$ and $\mathcal{C}_{1}$ in
the ambient space $\mathbb{F}_{2}^{n}$, with the property that
$\mathcal{C}_{0}^{\perp}\subset\mathcal{C}_{1}$ [CS96, Ste96]. It is a _low-
density parity-check_ (LDPC) code whenever both $\mathcal{C}_{0}$ and
$\mathcal{C}_{1}$ are the kernels of sparse parity-check matrices. The
resulting quantum code $\mathcal{Q}=(\mathcal{C}_{0},\mathcal{C}_{1})$ is a
subspace of $(\mathbb{C}_{2})^{\otimes n}$, the space of $n$ qubits:

$\mathcal{Q}:=\mathrm{Span}\left\\{\sum_{z\in\mathcal{C}_{1}^{\perp}}|x+z\rangle\>:\>x\in\mathcal{C}_{0}\right\\},$

where $\\{|x\rangle\>:\>x\in\mathbb{F}_{2}^{n}\\}$ is the canonical basis of
$(\mathbb{C}_{2})^{\otimes n}$. The dimension $k$ of the code counts the
number of logical qubits and is given by

$k=\text{dim}\,(\mathcal{C}_{0}/\mathcal{C}_{1}^{\perp})=\text{dim}\,\mathcal{C}_{0}+\text{dim}\,\mathcal{C}_{1}-n.$

Its minimum distance is $d=\min(d_{X},d_{Z})$ with

$d_{X}=\min_{w\in\mathcal{C}_{0}\setminus\mathcal{C}_{1}^{\perp}}|w|,\quad
d_{Z}=\min_{w\in\mathcal{C}_{1}\setminus\mathcal{C}_{0}^{\perp}}|w|.$

We denote the resulting code parameters by $\llbracket n,k,d\rrbracket$ and
say that a code family $(Q_{n})_{n}$ is _asymptotically good_ if its
parameters are of the form

$\llbracket n,k=\Theta(n),d=\Theta(n)\rrbracket.$

An $n$-qubit Pauli error $E_{1}\otimes\ldots\otimes E_{n}$ with
$E_{i}\in\\{\mathbbm{1},\sigma_{X},\sigma_{Y},\sigma_{Z}\\}$666The 1-qubit
Pauli matrices are defined by $\mathbbm{1}=\left(\begin{smallmatrix}1&0\\\
0&1\end{smallmatrix}\right),\sigma_{X}=\left(\begin{smallmatrix}0&1\\\
1&0\end{smallmatrix}\right),\sigma_{Z}=\left(\begin{smallmatrix}1&0\\\
0&-1\end{smallmatrix}\right)$ and $\sigma_{Y}=i\sigma_{X}\sigma_{Z}$. is
conveniently described by two $n$-bit strings
$(e_{0},e_{1})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$ via the mapping

$\mathbbm{1}\mapsto(0,0),\quad\sigma_{X}\mapsto(1,0),\quad\sigma_{Y}\mapsto(1,1),\quad\sigma_{Z}\mapsto(0,1),$

which forgets global phases. The parity-check matrices of $\mathcal{C}_{0}$
and $\mathcal{C}_{1}$ give rise to syndrome maps
$\sigma_{0},\sigma_{1}:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}^{m}$ that associate
a pair of syndromes
$(\sigma_{0}(\boldsymbol{e}_{0}),\sigma_{1}(\boldsymbol{e}_{1}))\in\mathbb{F}_{2}^{m}\times\mathbb{F}_{2}^{m}$
to any $n$-qubit Pauli error
$(\boldsymbol{e}_{0},\boldsymbol{e}_{1})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$.
The decoding problem for a stabilizer code is as follows: given a syndrome
$(\sigma_{0}(\boldsymbol{e}_{0}),\sigma_{1}(\boldsymbol{e}_{1}))$, recover the
error up to an element of the stabilizer group, that is return
$(\hat{\boldsymbol{e}}_{0},\hat{\boldsymbol{e}}_{1})$ such that
$\boldsymbol{e}_{0}+\hat{\boldsymbol{e}}_{0}\in\mathcal{C}_{1}^{\perp}$ and
$\boldsymbol{e}_{1}+\hat{\boldsymbol{e}}_{1}\in\mathcal{C}_{0}^{\perp}$.

While an optimal decoding of _random_ errors would typically exploit possible
correlations between $\boldsymbol{e}_{0}$ and $\boldsymbol{e}_{1}$, it is
always possible to correct both errors independently. Here, we will be
concerned with the adversarial setting where $\boldsymbol{e}_{0}$ and
$\boldsymbol{e}_{1}$ are of sufficiently low weight, but otherwise arbitrary.
In that case, both errors should be decoded independently, and we will focus
on the case where $(\boldsymbol{e}_{0}=0,\boldsymbol{e}_{1}=e)$ in the
following.

###  3.4 Tensor codes and dual tensor codes: robustness

Definitions and results for this section are taken from [LZ22b], to which we
refer for proofs and comments.

Let $A$ and $B$ be two sets of size $\Delta$. We define codes on the ambient
space $\mathbb{F}_{2}^{A\times B}$ that we may think of as the space of
matrices whose rows (columns) are indexed by $A$ (by $B$). If
$C_{A}\subset\mathbb{F}_{2}^{A}$ and $C_{B}\subset\mathbb{F}_{2}^{B}$ are two
linear codes, we define the tensor (or product) code $C_{A}\otimes C_{B}$ as
the space of matrices $x$ such that for every $b\in B$ the column vector
$(x_{ab})_{a\in A}$ belongs to $C_{A}$ and for every $a\in A$ the row vector
$(x_{ab})_{b\in B}$ belongs to $C_{B}$. It is well known that
$\dim(C_{A}\otimes C_{B})=\dim(C_{A})\dim(C_{B})$ and that the minimum
distance of the tensor code is $d(C_{A}\otimes C_{B})=d(C_{A})d(C_{B})$.

Consider the codes $C_{A}\otimes\mathbb{F}_{2}^{B}$ and
$\mathbb{F}_{2}^{A}\otimes C_{B}$ consisting respectively of the space of
matrices whose columns are codewords of $C_{A}$ and whose rows are codewords
of $C_{B}$. We may consider their sum
$C_{A}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes C_{B}$ which is
called a dual tensor code, since it is the dual code of the tensor code
$C_{A}^{\perp}\otimes
C_{B}^{\perp}=(C_{A}^{\perp}\otimes\mathbb{F}_{2}^{B})\cap(\mathbb{F}_{2}^{A}\otimes
C_{B}^{\perp})$. It is relatively straightforward to check that
$d(C_{A}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes
C_{B})=\min(d(C_{A}),d(C_{B}))$.

######  Definition 4.

Let $0\leqslant w\leqslant\Delta^{2}$. Let $C_{A}$ and $C_{B}$ be codes of
length $\Delta$ with minimum distances $d_{A}$ and $d_{B}$. We shall say that
the dual tensor code
$C=C_{A}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes C_{B}$ is
$w$-robust, if for any codeword $x\in C$ of Hamming weight $|x|\leqslant w$,
there exist $A^{\prime}\subset A,B^{\prime}\subset B$,
$|A^{\prime}|\leqslant|x|/d_{B}$, $|B^{\prime}|\leqslant|x|/d_{A}$, such that
$x_{ab}=0$ whenever $a\notin A^{\prime},b\notin B^{\prime}$.

######  Proposition 5.

Let $C_{A}$ and $C_{B}$ be codes of length $\Delta$ with minimum distances
$d_{A}$ and $d_{B}$, and suppose
$C=C_{A}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes C_{B}$ is
$w$-robust with $0<w<d_{A}d_{B}$. Then for any codeword $x\in C$ such that
$|x|\leqslant w$, there exist $A^{\prime}\subset A,B^{\prime}\subset B$,
$|A^{\prime}|\leqslant|x|/d_{B}$, $|B^{\prime}|\leqslant|x|/d_{A}$ and a
decomposition $x=c+r$, with $c\in C_{A}\otimes\mathbb{F}_{2}^{B^{\prime}}$ and
$r\in\mathbb{F}_{2}^{A^{\prime}}\otimes C_{B}$.

###### Proof.

To see this, apply the definition and write $x=r^{\prime}+c^{\prime}$, with
$r^{\prime}_{ab}=c^{\prime}_{ab}$ for any $(a,b)\in(A\setminus
A^{\prime})\times(B\setminus B^{\prime})$. The restrictions of $r^{\prime}$
and $c^{\prime}$ to $(A\setminus A^{\prime})\times(B\setminus B^{\prime})$
both belong to the code obtained by tensoring $C_{A}^{\prime}$ and
$C_{B}^{\prime}$, the punctured codes deduced from $C_{A}$ and $C_{B}$ by
throwing away coordinates of $A^{\prime}$ and $B^{\prime}$. This code is the
same as the punctured code obtained from $C_{A}\otimes C_{B}$ by throwing away
the coordinates $A^{\prime}\times B\cup A\times B^{\prime}$. Therefore, there
exists a tensor codeword of $C_{A}\otimes
C_{B}=C_{A}\otimes\mathbb{F}_{2}^{B}\cap\mathbb{F}_{2}^{A}\otimes C_{B}$ that
coincides with $c^{\prime}=r^{\prime}$ on $(A\setminus
A^{\prime})\times(B\setminus B^{\prime})$: adding this tensor codeword to both
$c^{\prime}$ and $r^{\prime}$ yields the required pair $r,c$ such that
$x=r+c$. ∎

######  Proposition 6.

Let $C_{A}$ and $C_{B}$ be codes of length $\Delta$ and minimum distances
$d_{A},d_{B}$ such that the dual tensor code
$C_{A}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes C_{B}$ is $w$-robust
with $w\leqslant d_{A}d_{B}/2$. Then, any word $x$ close to both the column
and row code is also close to the tensor code: precisely, if
$d(x,C_{A}\otimes\mathbb{F}_{2}^{B})+d(x,\mathbb{F}_{2}^{A}\otimes
C_{B})\leqslant w$ then

$\displaystyle d(x,C_{A}\otimes
C_{B})\leqslant\frac{3}{2}\left(d(x,C_{A}\otimes\mathbb{F}_{2}^{B})+d(x,\mathbb{F}_{2}^{A}\otimes
C_{B})\right).$ (4)

######  Definition 7.

Let $C_{A}\subset\mathbb{F}_{2}^{A}$ and $C_{B}\subset\mathbb{F}_{2}^{B}$. For
integers $w,p$, let us say that the dual tensor code
$C_{A}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes C_{B}$ is $w$-robust
with $p$-resistance to puncturing, if for any $A^{\prime}\subset A$ and
$B^{\prime}\subset B$ such that $|A^{\prime}|=|B^{\prime}|=\Delta-w^{\prime}$,
with $w^{\prime}\leqslant p$, the dual tensor code

$C_{A^{\prime}}\otimes\mathbb{F}_{2}^{B^{\prime}}+\mathbb{F}_{2}^{A^{\prime}}\otimes
C_{B^{\prime}}$

is $w$-robust.

We shall need the following result on the robustness of random dual tensor
codes.

######  Theorem 8.

Let $0<\rho_{A}<1$ and $0<\rho_{B}<1$. Let $0<\varepsilon<1/2$ and
$1/2+\varepsilon<\gamma<1$. Let $C_{A}$ be a random code obtained from a
random uniform $\rho_{A}\Delta\times\Delta$ generator matrix, and let $C_{B}$
be a random code obtained from a random uniform
$(1-\rho_{B})\Delta\times\Delta$ parity-check matrix. With probability tending
to $1$ when $\Delta$ goes to infinity, the dual tensor code

$C_{A}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes C_{B}$

is $\Delta^{3/2-\varepsilon}$-robust with $\Delta^{\gamma}$-resistance to
puncturing.

##  4 Detailed description of quantum Tanner codes

We recall the ingredients that enable us to define the family of
asymptotically good quantum LDPC codes introduced in [LZ22b]. The only
difference with [LZ22b] is that we prefer to work here with a quadripartite
version of the Cayley complex since it gives a simpler description of the
decoding algorithm. This quadripartite version was mentioned in passing in
[LZ22b], and is not much more than a particular instance of the bipartite
version, and is also suited to the lower bound of Theorem 1 on the minimum
distance. Below we discuss the quadripartite structure in some more detail.

###  4.1 Left-right Cayley complexes (quadripartite version)

The square complex we shall rely on for the construction first appeared in
[PK21a] as a balanced product of double covers of non-bipartite Cayley graphs.
For the sake of simplicity, we will rather use the language of left-right
Cayley complexes in their quadripartite version. A left-right Cayley complex
$X$ is introduced in [DEL+21] from a group $G$ and two sets of generators
$A=A^{-1}$ and $B=B^{-1}$. As in [DEL+21] we will restrict ourselves, for the
sake of simplicity, to the case $|A|=|B|=\Delta$. The complex is made up of
vertices, $A$-edges, $B$-edges, and squares. The vertex set consists of four
copies of the group $G$ in the quadripartite version, $V=V_{00}\cup V_{10}\cup
V_{01}\cup V_{11}$ with $V_{ij}=G\times\\{ij\\}$. The advantage of this
quadripartite version, also considered in [PK21a] and [Gol21], is that it does
not require any additional assumption on the choice of group and generators,
for instance that $ag\neq gb$ for all $g\in G,a\in A,b\in B$, as in [DEL+21].
We will also use the notation $V_{0}:=V_{00}\cup V_{11}$ and
$V_{1}:=V_{01}\cup V_{10}$. The $A$-edges are pairs of vertices of the form
$\\{(g,i0),(ag,i1)\\}$ and $B$-edges are of the form $\\{(g,0j),(gb,1j)\\}$
for $g\in G,a\in A,b\in B$, $i,j=0,1$. We denote by $E_{A}$ and $E_{B}$ these
two edge sets. The associated graphs are denoted by
$\mathcal{G}_{A}=(V,E_{A})$ and $\mathcal{G}_{B}=(V,E_{B})$. A square is a set
of four vertices of the form $\\{(g,00),(ag,01),(gb,10),(agb,11)\\}$. The set
of squares (or quadrangles) of the complex is denoted by $Q$. Every vertex is
incident to exactly $\Delta^{2}$ squares. For a vertex $v$, the set of
incident squares is called the $Q$-neighbourhood, and denoted by $Q(v)$.

The sets of generators $A$ and $B$ will be chosen so that the Cayley graphs
${\sf Cay}(G,A)$ and ${\sf Cay}(G,B)$ are non-bipartite Ramanujan graphs. It
should be understood that when writing ${\sf Cay}(G,A)$ we implicitely mean
the Cayley graph defined by left multiplication by elements of $A$, while
${\sf Cay}(G,B)$ stands for the Cayley graph defined by right multiplication
by elements of $B$. The sets $A$ and $B$ could in principle be chosen to be
identical, but we keep a distinct notation for both sets, in particular in
order to allow the above abuse of notation to be non-confusing.

We see that the subset of edges of $E_{A}$ that connect vertices of $V_{00}$
to vertices of $V_{01}$ make up a double cover of the Cayley graph ${\sf
Cay}(G,A)$, the edges $E_{A}$ that connect $V_{10}$ to $V_{11}$ make up a
second copy of the same double cover. Therefore, the graph $\mathcal{G}_{A}$
is a disjoint union of two copies of the double cover of ${\sf Cay}(G,A)$.
Similarly, $\mathcal{G}_{B}$ is a disjoint union of two copies of the double
cover of ${\sf Cay}(G,B)$. We will regularly talk about expansion in
$\mathcal{G}_{A}$ (or $\mathcal{G}_{B}$) to mean expansion in either of the
connected components of $\mathcal{G}_{A}$ ($\mathcal{G}_{B}$).

Let us introduce one additional graph that exists on the complex $X$, and that
we denote by $\mathcal{G}^{\square}$. This graph puts an edge between all
pairs of vertices of the form $\\{(g,i),(agb,i)\\}$, $g\in G,a\in A,b\in
B,i=0,1$. The graph $\mathcal{G}^{\square}$ is therefore made up of two
connected components, on $V_{0}$ and $V_{1}$, that we denote by
$\mathcal{G}_{0}^{\square}$ and $\mathcal{G}_{1}^{\square}$. We note that
$\mathcal{G}^{\square}$ is regular of degree $\Delta^{2}$, and may have
multiple edges.

If ${\sf Cay}(G,A)$ and ${\sf Cay}(G,B)$ are Ramanujan, then
$\mathcal{G}^{\square}$ inherits some of their expansion properties.
Specifically:

######  Lemma 9.

Assume that ${\sf Cay}(G,A)$ and ${\sf Cay}(G,B)$ are Ramanujan graphs, then

$\lambda(\mathcal{G}_{0}^{\square})\leqslant
4\Delta,\quad\lambda(\mathcal{G}_{1}^{\square})\leqslant 4\Delta.$

The proof follows from the fact that the adjacency matrix of
$\mathcal{G}^{\square}$ is the product of the adjacency matrices of
$\mathcal{G}_{A}$ and $\mathcal{G}_{B}$, and that these two adjacency matrices
commute, by definition of the square complex. See [LZ22b] for a little more
detail.

###  4.2 Labelling $Q$-neighbourhoods

We will define Tanner codes on $\mathcal{G}_{0}^{\square}$ and
$\mathcal{G}_{1}^{\square}$, which implies a labelling of the coordinates in
every $Q$-neighbourhood $Q(v)$. There is a natural labeling of $Q(v)$ by the
set $A\times B$, namely a one-to-one map $\phi_{v}~{}:A\times B\to Q(v)$,
which we now state explicitely.

We set

$\displaystyle\text{for}\;v=(g,00)\in V_{00},\quad$
$\displaystyle\phi_{v}(a,b)=\\{(g,00),(ag,01),(gb,10),(agb,11)\\},$
$\displaystyle\text{for}\;v=(g,01)\in V_{01},\quad$
$\displaystyle\phi_{v}(a,b)=\\{(g,01),(a^{-1}g,00),(gb,11),(a^{-1}gb,10)\\},$
$\displaystyle\text{for}\;v=(g,10)\in V_{10},\quad$
$\displaystyle\phi_{v}(a,b)=\\{(g,10),(ag,11),(gb^{-1},00),(agb^{-1},01)\\},$
$\displaystyle\text{for}\;v=(g,11)\in V_{11},\quad$
$\displaystyle\phi_{v}(a,b)=\\{(g,11),(a^{-1}g,10),(gb^{-1},01),(a^{-1}gb^{-1},00)\\}.$

The map $\phi_{v}$ thus defined is obviously one-to-one, and one easily checks
that:

Any two vertices $v=(g,i0)$ and $w=(gb,i1)$, $i=0,1$, that are connected
through a $B$-edge (labelled $b$), have a common “column”, i.e. their
$Q$-neighbourhoods share exactly $\Delta$ squares that are labelled
$(a,b),a\in A$, in both $Q(v)$ and $Q(w)$.

Similarly,

Any two vertices $v=(g,0i)$ and $w=(ag,1i)$, $i=0,1$, that are connected
through an $A$-edge (labelled $a$), have a common row, i.e. their
$Q$-neighbourhoods share exactly $\Delta$ squares that are labelled
$(a,b),b\in B$, in both $Q(v)$ and $Q(w)$.

The situation is illustrated on Figure 2. Summarising, any two vertices
connected by $B$-edge (an $A$-edge) have a common column (row) in their
$Q$-neighbourhoods, that is labelled by the same $b\in B$ ($a\in A$). This is
the reason for the possibly intriguing inversions in the definition of
$\phi_{v}$: without these inversions the $Q$-neighbourhoods of two
neighbouring vertices would still share a common row or a common column, but
their indexes in their respective local views would be inverse of each other.
This would still be manageable but slightly less convenient.

###  4.3 Local codes

The constraints of a Tanner code consist of local constraints from small codes
enforced on the local view of each vertex. For quantum Tanner codes, now that
all local $Q$-neighbourhoods are isomorphic to $A\times B$, we may put local
constraints that are codewords of the tensor codes $C_{A}\otimes C_{B}$ and
$C_{A}^{\perp}\otimes C_{B}^{\perp}$.

Recall that the generators of the quantum Tanner code correspond to a basis of
$C_{A}\otimes C_{B}$ in each local view of $V_{00}\cup V_{11}$ (for the
$\sigma_{Z}$-type generators) and to a basis of $C_{A}^{\perp}\otimes
C_{B}^{\perp}$ in each local view of $V_{01}\cup V_{10}$ (for the
$\sigma_{X}$-type generators). The classical code
$\mathcal{C}_{0}\subset\mathbb{F}_{2}^{Q}$ correcting $\sigma_{X}$-type errors
is the Tanner code on the graph $\mathcal{G}_{0}^{\square}$ with local
constraints corresponding to the dual tensor code $(C_{A}\otimes
C_{B})^{\perp}=C_{A}^{\perp}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes
C_{B}^{\perp}$. With the notation of Section 3.2,
$\mathcal{C}_{0}=\text{Tan}(\mathcal{G}_{0}^{\square},C_{A}^{\perp}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes
C_{B}^{\perp})$. Similarly, the classical code
$\mathcal{C}_{1}\subset\mathbb{F}_{2}^{Q}$ correcting $\sigma_{Z}$-type errors
is the Tanner code on the graph $\mathcal{G}_{1}^{\square}$ with local
constraints corresponding to the dual tensor code $(C_{A}^{\perp}\otimes
C_{B}^{\perp})^{\perp}=C_{A}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes
C_{B}$, i.e.
$\mathcal{C}_{1}=\text{Tan}(\mathcal{G}_{1}^{\square},C_{A}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes
C_{B})$.

#### Summary.

A large enough $\Delta$ is chosen, together with an infinite family of groups
$G$ with generating sets $A,B$, $|A|=|B|=\Delta$, such that the left Cayley
graph ${\sf Cay}(G,A)$ and the right Cayley graph ${\sf Cay}(G,B)$ are
Ramanujan. The quadripartite left-right square complex $X$ is defined by
$G,A,B$.

For the conditions for the component codes that together with the above square
complexes $X$ will yield asymptotically good quantum codes, we recall Theorem
16 from [LZ22b].

######  Theorem 10.

Fix $\rho\in(0,1/2)$, $\varepsilon\in(0,1/2)$, $\gamma\in(1/2+\varepsilon,1)$
and $\delta>0$. If $\Delta$ is large enough and $C_{A}$ and $C_{B}$ are codes
of length $\Delta$ such that

  1. 1.

$0<\dim C_{A}\leqslant\rho\Delta$ and $\dim C_{B}=\Delta-\dim C_{A}$,

  2. 2.

the minimum distances of $C_{A},C_{B},C_{A}^{\perp},C_{B}^{\perp}$ are all
$\geqslant\delta\Delta$,

  3. 3.

both dual tensor codes $C_{0}^{\perp}=(C_{A}\otimes C_{B})^{\perp}$ and
$C_{1}^{\perp}=(C_{A}^{\perp}\otimes C_{B}^{\perp})^{\perp}$ are
$\Delta^{3/2-\varepsilon}$-robust with $\Delta^{\gamma}$-resistance to
puncturing (see Definition 7),

then the quantum code $\mathcal{Q}=(\mathcal{C}_{0},\mathcal{C}_{1})$ has
length $|Q|$, dimension at least $(1-2\rho)^{2}|Q|$ and minimum distance at
least $|Q|\delta/4\Delta^{3/2+\varepsilon}$.

It was proved in [LZ22b] (see also Theorem 8), that for any fixed $\rho$ and
$\delta>0$ such that
$-\delta\log_{2}\delta-(1-\delta)\log_{2}(1-\delta)<\rho$, then for any fixed
$\varepsilon,\gamma$ and $\Delta$ large enough, randomly choosing $C_{A}$ and
$C_{B}$ with the required rates will yield codes that satisfy conditions 2 and
3 in Theorem 10 with high probability. In the sequel we will set, somewhat
arbitrarily, $\gamma=1-\varepsilon$, so as to minimise the number of
constants, and we will naturally assume that the codes $C_{A}$ and $C_{B}$
satisfy the conditions of Theorem 10.

##  5 The decoding strategy

We recall that we consider without loss of generality a bit-flip error
$\boldsymbol{e}\in\mathbb{F}_{2}^{Q}$ and wish to correct it with the help of
the classical Tanner code $\mathcal{C}_{1}$. The goal of the decoder is to
output some guess $\hat{\boldsymbol{e}}\in\mathbb{F}_{2}^{Q}$ and it is
successful if $\boldsymbol{e}+\hat{\boldsymbol{e}}\in\mathcal{C}_{0}^{\perp}$.

For a vertex $v\in V$, denote by $e_{v}$ the local view of $\boldsymbol{e}$ on
$Q(v)$, i.e. its restriction to $Q(v)$, which we also extend back to
$\mathbb{F}_{2}^{Q}$ by padding it with $0$s. The error $\boldsymbol{e}$ can
be identified with the collection of local views
$\boldsymbol{e}=\\{e_{v}\\}_{v\in V_{1}}$ and we note that they satisfy
$\sum_{v\in V_{01}}e_{v}=\sum_{v\in V_{10}}e_{v}$, since $(Q(v))_{v\in
V_{01}}$ and $(Q(v))_{v\in V_{10}}$ are both partitions of $Q$. The Hamming
weight of $\boldsymbol{e}$ is

$|\boldsymbol{e}|=\sum_{v\in V_{01}}|e_{v}|=\sum_{v\in V_{10}}|e_{v}|.$

As observed in [LZ22b], a possible approach to decoding a Tanner code is to
consider the _mismatch_ of the error $\boldsymbol{e}$. It is defined as
follows. For each vertex $v\in V_{1}$, one can compute an error
$\varepsilon_{v}$ of minimal Hamming weight yielding the corresponding local
syndrome. This gives a decomposition of the local views of the error
$e_{v}=\varepsilon_{v}+c_{v}+r_{v}$ with $c_{v}\in
C_{A}\otimes\mathbb{F}_{2}^{B},r_{v}=\mathbb{F}_{2}^{A}\otimes C_{B}$, and
$\varepsilon_{v}$ of minimal Hamming weight. In the case where
$e_{v}=\varepsilon_{v}$ for all $v\in V_{1}$, then the decoder has succeeded
in recovering the true error. In general, however, we have
$e_{v}\neq\varepsilon_{v}$ for some $v\in V_{1}$. The mismatch vector in
$\mathbb{F}_{2}^{Q}$ defined as $Z:=\sum_{v\in V_{1}}\varepsilon_{v}$ then
characterises the inconsistency between the local views in $V_{10}$ and
$V_{01}$. From $\sum_{v\in V_{1}}e_{v}=0$, we obtain that

$Z=\sum_{v\in V_{1}}r_{v}+c_{v}.$

We observe that the minimality of $\varepsilon_{v}$ implies that
$|e_{v}+c_{v}+r_{v}|\leqslant|e_{v}|$ and therefore $|c_{v}+r_{v}|\leqslant
2|e_{v}|$. This immediately shows that

$|Z|\leqslant\sum_{v\in V_{1}}|r_{v}+c_{v}|\leqslant 2\sum_{v\in
V_{1}}|e_{v}|=4|\boldsymbol{e}|.$

We note that the quantum Tanner codes are a priori not locally testable, and
therefore the Hamming weight of the mismatch can be much smaller than that of
the error (otherwise a simple test for detecting an error would be to sample
bits of the mismatch).

The idea behind the decoder will be to find a decomposition
$\\{\hat{r}_{v},\hat{c}_{v}\\}_{v\in V_{1}}$ such that $Z=\sum_{v\in
V_{1}}\hat{r}_{v}+\hat{c}_{v}$. In that case, the decoder will return the
following guess for the decomposition of the error: $\\{\hat{e}_{v}\\}_{v\in
V_{1}}$ with

$\hat{e}_{v}:=\varepsilon_{v}+\hat{r}_{v}+\hat{c}_{v}.$

In particular, the vectors $\boldsymbol{e}$ and $\hat{\boldsymbol{e}}$ differ
by an element of $\mathcal{C}_{1}$ since they both give the same syndrome, and
a sufficient condition to guarantee the success of the decoder is that
$|\boldsymbol{e}+\hat{\boldsymbol{e}}|<d_{\min}(\mathcal{Q})$.

Since each column $A\times\\{b\\}$ of a $Q$-neighbourhood $Q(v)$ appears also
in the $Q$-neighbourhood of a neighbouring vertex, we have that for either
$v\in V_{00}$ or $v\in V_{10}$, each column subvector of $c_{v}$ is a codeword
of $C_{A}$ that appears in two local views, one indexed by a vertex of
$V_{10}$ and one by a vertex of $V_{00}$: for $v\in V_{01}\cup V_{11}$, we
have that any column subvector of $c_{v}$ lies both in the local view around a
vertex of $V_{01}$ and around a vertex of $V_{11}$.

A similar observation also holds for row codewords: This implies that one can
also define couples $(c_{v},r_{v})$ for all vertices of $V_{0}$.

It is convenient to define four vectors associated with the collection
$\\{r_{v},c_{v}\\}_{v\in V_{1}}$,

$C_{0}=\sum_{v\in V_{10}}c_{v},\quad R_{0}=\sum_{v\in V_{01}}r_{v},\quad
C_{1}=\sum_{v\in V_{01}}c_{v},\quad R_{1}=\sum_{v\in V_{10}}r_{v},$

that provide a decomposition of the mismatch:

$Z=C_{0}+R_{0}+C_{1}+R_{1}.$

Note that $(C_{0},R_{0},C_{1},R_{1})$ and $\\{r_{v},c_{v}\\}_{v\in V}$ are in
one-to-one correspondence.

We will denote this decomposition as

$\mathcal{Z}=(C_{0},R_{0},C_{1},R_{1})=\\{r_{v},c_{v}\\}_{v\in V}.$

The decoder then simply aims at finding a valid decomposition
$\hat{\mathcal{Z}}=(\hat{C}_{0},\hat{R}_{0},\hat{C}_{1},\hat{R}_{1})$ of $Z$
and this decomposition will yield the correct guess provided that
$|\boldsymbol{e}+\hat{\boldsymbol{e}}|=|\sum_{v\in
V_{10}}c_{v}+r_{v}+\hat{c}_{v}+\hat{r}_{v}|=|C_{0}+R_{1}+\hat{C}_{0}+\hat{R}_{1}|$
is less than the minimal distance of the quantum Tanner code.

A natural idea for the decoder is to progressively decrease the weight of $Z$,
so as to obtain a consistent assignment that will correspond to the output of
the decoder. To do this, one can look for some vertex $v$, as well as some
local codeword $c_{v}+r_{v}$ of the dual tensor code such that
$|Z+c_{v}+r_{v}|<|Z|$. If it was always possible to guarantee the existence of
such a vertex and local codeword, then one would simply repeat the operation
until reaching a complete decomposition of the mismatch. At each step, the
weight of the mismatch decreases by at least 1, so at most $|Z|$ steps are
required. In addition, we observe that
$|\hat{C}_{0}+\hat{R}_{1}|\leqslant\Delta^{2}|Z|\leqslant
4\Delta^{2}|\boldsymbol{e}|$ and we recall that $|C_{0}+R_{1}|=\sum_{v\in
V_{10}}|c_{v}+r_{v}|\leqslant 2|\boldsymbol{e}|$. We conclude that if we could
always find a vertex and a local codeword that could be added to the mismatch
to decrease its weight, then the decoder would return a valid correction
provided the initial error is not too large:

$|\boldsymbol{e}|\leqslant\frac{d_{\min}(\mathcal{Q})}{4\Delta^{2}+2}.$

Unfortunately, we only know how to prove the existence of local codewords
decreasing the weight of $Z$ if the local dual tensor code is $w$-robust with
$w>\Delta^{3/2}$, and we recall that Theorem 8 only asserts that randomly
chosen codes $C_{A}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes C_{B}$
and $C_{A}^{\perp}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes
C_{B}^{\perp}$ are $w$-robust for $w=O(\Delta^{3/2-\varepsilon})$ for random
codes $C_{A},C_{B}$.

For this reason, we need to tweak this natural decoder in order to deal with
error configurations (described by their mismatch $Z$) whose weight cannot be
decreased locally by the addition of some $c_{v}+r_{v}$. For this purpose, we
will add a _parallel_ procedure that will be described in detail in Section 6.
The actual decoder will apply the sequential local procedure described above,
though we will only need to apply it to vertices of $V_{0}$, and resort to the
parallel procedure whenever the sequential decoder is stalled. The parallel
procedure will consist of two phases, the first will be applied to vertices of
$V_{1}$, and the second to vertices of $V_{0}$. While it may not be possible
to decrease locally the Hamming weight of the mismatch when the sequential
decoder is stalled, we will show that together, the two steps of the parallel
procedure will significantly decrease the Hamming weight of $Z$, by a factor
which becomes close to $\sqrt{\Delta}$ when the exponent $\varepsilon$ that
defines the robustness parameter $w=\Delta^{3/2-\varepsilon}$ tends to $0$.
Since the sequential procedure decreases $|Z|$ at every step, the number of
sequential steps is at most linear in $|Z|$, and therefore in the Hamming
weight $|\boldsymbol{e}|$ of the initial error, provided it is not too large.
Since any parallel step divides $|Z|$ by a constant, the total number of
parallel steps is logarithmic in $|\boldsymbol{e}|$.

In both cases, sequential and parallel, the decoder needs only look at
$Q$-neighbourhoods on which the mismatch $|Z|$ is nonzero: therefore, by
carefully keeping track of the set of vertices for which the mismatch is
nonzero, the decoder can run in linear-time in the standard uniform cost
computational model.

#### Norm and minimal decomposition of the mismatch.

The analysis of the decoder will rest on a careful study of a situation where
the sequential decoder is stalled, that is, where there does not exist any
vertex (in $V_{0}$) where one can add a codeword of the dual tensor code that
would decrease the Hamming weight of $Z$. (If the sequential decoder is never
stalled, then there is essentially nothing to prove.) The parallel procedure
that will unlock the situation will consist of two steps. While the
combination of both steps will reduce the Hamming weight $|Z|$ of the
mismatch, it is not the case of the first part alone. In order to keep track
of the progress of the decoding algorithm, we will therefore require another
metric beside the Hamming weight: this role will be played by the norm of the
decomposition, that will be a proxy for the number of vertices of $V_{0}$ for
which $c_{v}+r_{v}\neq 0$.

First, note that there are many valid decompositions of the mismatch since
adding any codeword of the tensor code $C_{A}\otimes C_{B}$ to both $r_{v}$
and $c_{v}$ does not change their sum. For an element
$r\in\mathbb{F}_{2}^{A}\otimes C_{B}$ or $c\in
C_{A}\otimes\mathbb{F}_{2}^{B}$, we denote by $\|r\|$ or $\|c\|$ the number of
nonzero rows (for $r$) or columns (for $c$) in its support:

$\displaystyle\|r\|$
$\displaystyle:=\min\\{|A^{\prime}|\;\text{s.t.}\;A^{\prime}\subseteq
A,\mathrm{supp}(r)\subset\mathbb{F}_{2}^{A^{\prime}}\otimes C_{B}\\},$
$\displaystyle\|c\|$
$\displaystyle:=\min\\{|B^{\prime}|\;\text{s.t.}\;B^{\prime}\subseteq
B,\mathrm{supp}(c)\subset C_{A}\otimes\mathbb{F}_{2}^{B^{\prime}}\\}.$

The norm $\|\mathcal{Z}\|$ of the decomposition is then simply:

$\displaystyle\|\mathcal{Z}\|$
$\displaystyle:=\|C_{0}\|+\|R_{0}\|+\|C_{1}\|+\|R_{1}\|,$

with

$\|C_{0}\|:=\sum_{v\in V_{10}}\|c_{v}\|,\quad\|R_{0}\|:=\sum_{v\in
V_{01}}\|r_{v}\|,\quad\|C_{1}\|:=\sum_{v\in
V_{01}}\|c_{v}\|,\quad\|R_{1}\|:=\sum_{v\in V_{10}}\|r_{v}\|.$

It will be useful for us to consider a _minimal_ decomposition of the
mismatch, $\mathcal{Z}=(C_{0},R_{0},C_{1},R_{1})$, which simply corresponds to
a decomposition of minimal norm. We define the norm $\|Z\|$ of the mismatch to
be the norm of a such minimal decomposition:

$\|Z\|:=\min_{\text{$\mathcal{Z}$ is a decomposition of $Z$}}\|\mathcal{Z}\|.$

A minimal decomposition has the property that for each vertex, it is not
possible to add a codeword of $C_{A}\otimes C_{B}$ that decreases the norm of
the local view: for each $v\in V$, and each $u\in C_{A}\otimes C_{B}$, it
holds that

$\|r_{v}+c_{v}+u\|\geqslant\|r_{v}+c_{v}\|.$

##  6 Analysis of the decoder

###  6.1 The decoding algorithm

The goal of the algorithm is to find a small decomposition of $Z$. We will
keep track of 5 vectors initialized as follows

$\hat{Z}:=Z,\quad\hat{C}_{0}:=0,\quad\hat{R}_{0}:=0,\quad\hat{C}_{1}:=0,\quad\hat{R}_{1}:=0.$

It will alternate between two procedures:

#### Sequential procedure.

This procedure is relatively natural, and consists of modifying $\hat{Z}$
locally, i.e. in some $Q(v)$, so as to decrease the Hamming weight of
$\hat{Z}$. Specifically, while there exists some $v\in V_{00}$ or $v\in
V_{11}$, and $c_{v}\in
C_{A}\otimes\mathbb{F}_{2}^{B},r_{v}\in\mathbb{F}_{2}^{A}\otimes C_{B}$ such
that $|\hat{Z}+c_{v}+r_{v}|<|\hat{Z}|$, perform the update:

$\hat{Z}\leftarrow\hat{Z}+c_{v}+r_{v},\quad\hat{C}_{j}\leftarrow\hat{C}_{j}+c_{v},\quad\hat{R}_{i}\leftarrow\hat{R}_{i}+r_{v}.$

#### Parallel procedure.

Ideally, we would like the sequential procedure to be applicable until we have
$\hat{Z}=0$, at which point decoding would be complete. However, we cannot
always guarantee the existence of a vertex for which we can decrease the
Hamming weight of $\hat{Z}$. The sequential decoder may be stalled. At this
point we switch to an alternative procedure which will unlock the situation.
We remark that we could try to extend the sequential procedure to vertices of
$V_{1}$ and not just apply it to vertices of $V_{0}$ as specified above.
However, we cannot guarantee that this extended sequential decoder will not
stall as well, and we will deal with the stalled decoder through a procedure
whose analysis only needs to know that sequential decoder is stalled on
$V_{0}$. This alternative procedure consists of two parallel decoding steps.

The first parallel decoding step is the most involved. It consists of looking
for all vertices $v$ of $V_{1}$ for which the weight of $\hat{Z}$ can be
decreased, not on all their $Q$-neighbourhood $Q(v)$, but on a sufficiently
large subset of $Q(v)$, i.e. indexed by some $A_{0}\times B_{0}$ for
$A_{0}\subset A$, $B_{0}\subset B$. We give below the precise criteria for
vertices $v$ for which the decoder updates $\hat{Z}$ on $Q(v)$. We cannot
guarantee that this first parallel decoding step decreases the Hamming weight
of $\hat{Z}$. However, we will show that this first parallel decoding step
significantly decreases the number of active vertices of $V_{0}$: the active
vertices $v$ of $\hat{Z}$, for $v\in V_{ij}$, are the vertices on whose
$Q$-neighbourhoods we have $R_{i}+C_{j}\neq 0$, for a relevant decomposition
$\mathcal{Z}=(C_{0},R_{0},C_{1},R_{1})$ of $\hat{Z}$. We shall be more precise
with the definition of this set when we start the analysis. Specifically it
divides this number by a quantity close to $\Delta$. Proving this (as stated
in Theorem 23) will be the most technical part of the analysis of the decoder.

The _second parallel decoding step_ is conceptually simpler. It consists
simply of looking for all vertices of $V_{0}$ on which the value of
$|\hat{Z}|$ can be decreased and _simultaneously_ updating $\hat{Z}$ on all
such vertices. Precisely:

#### Second parallel decoding step.

Simultaneously, for each $v\in V_{0}$, search for codewords $c_{v}\in
C_{A}\otimes\mathbb{F}_{2}^{B},r_{v}\in\mathbb{F}_{2}^{A}\otimes C_{B}$ such
that $|\hat{Z}+c_{v}+r_{v}|<|\hat{Z}|$. If such $c_{v},r_{v}$ exist, choose
$c_{v},r_{v}$ that maximize the difference $|\hat{Z}|-|\hat{Z}+c_{v}+r_{v}|$
and perform the update

$\hat{Z}\leftarrow\hat{Z}+c_{v}+r_{v},\quad\hat{C}_{j}\leftarrow\hat{C}_{j}+c_{v},\quad\hat{R}_{i}\leftarrow\hat{R}_{i}+r_{v}$

for the appropriate $i,j\in\\{0,1\\}$.

Just by relying on the fact that the number of active vertices of $V_{0}$ has
been greatly reduced after the first parallel decoding step, it will be
relatively straightforward to show that afer the second parallel decoding
step, the Hamming weight of $\hat{Z}$ must incur a significant reduction from
its value from before the first parallel decoding step. Together, both
parallel steps, first on $V_{1}$ and then on $V_{0}$, enable us to unlock the
situation and divide the Hamming weight of $\hat{Z}$ by a quantity that we
will show to be close to $\sqrt{\Delta}$.

We now finish this description of the decoder by giving the precise
description of the first parallel decoding step. We need to recall that the
dual tensor code $C_{A}\otimes\mathbb{F}^{B}+\mathbb{F}^{A}\otimes C_{B}$ is
$w$-robust with resistance to puncturing $p$ with $w=\Delta^{3/2-\varepsilon}$
and $p\geqslant\Delta^{\gamma}$, where $\varepsilon>0$ can be taken
arbitrarily close to $0$ and $\gamma<1$ can be taken arbitrarily close to $1$.
For simplicity we will choose $\gamma=1-\varepsilon$.

#### First parallel decoding step.

The tweaked decoder does the following: on $V_{1}$ it looks, in parallel, for
vertices $v$ for which it can identify a partition $A=A_{0}\cup
A^{\prime\prime}$ and a partition $B=B_{0}\cup B^{\prime\prime}$ such that
$|A^{\prime\prime}|\leqslant\Delta^{\gamma}/2$ and
$|B^{\prime\prime}|\leqslant\Delta^{\gamma}/2$ and which satisfy the following
properties:

  * –

the value of $|\hat{Z}|$ on the restricted local view $A_{0}\times B_{0}$ of
$Q(v)$ is $>w/2$,

  * –

there exists $r_{v}+c_{v}\in
C_{A_{0}}\otimes\mathbb{F}^{B_{0}}+\mathbb{F}^{A_{0}}\otimes C_{B_{0}}$ such
that $|r_{v}+c_{v}|>w$, and replacing $\hat{Z}$ by $\hat{Z}+r_{v}+c_{v}$
decreases the value of $|\hat{Z}|$ on $A_{0}\times B_{0}$ so that it becomes
$<w/2$.

The behaviour of the decoder on the $Q$-neighbourhood of such a vertex $v$ is
then to

  * –

first update $\hat{Z}$ to $\hat{Z}+r_{v}+c_{v}$, update $\hat{R}_{i}$ to
$\hat{R}_{i}+r_{v}$, and $\hat{C}_{j}$ to $\hat{R}_{j}+c_{v}$,

  * –

look for individual rows and columns on $Q(v)$, on which it is possible to
decrease the weight of $\hat{Z}$ by adding a single (column) codeword of
$C_{A}$ or a single (row) codeword of $C_{B}$. If such rows or columns exist
it updates $\hat{Z},\hat{R}_{i},\hat{C}_{j}$ correspondingly, and stops its
treatment of $Q(v)$ when there are no more such rows or columns.

We stress that this whole procedure is applied _in parallel_ to all
$Q$-neighbourhoods from the original stalled $\hat{Z}$.

###  6.2 Analysis of the parallel procedure

We suppose the sequential decoder is stalled. We let
$\mathcal{Z}=(R_{0},C_{0},R_{1},C_{1})$ be a minimum representation of the
current stalled mismatch $\hat{Z}$, meaning that
$\|\mathcal{Z}\|=\|\hat{Z}\|$. In particular we will keep in mind that
$\mathcal{Z}$ is locally minimal, meaning that its norm cannot be decreased by
adding a codeword of the tensor code in a single local view. The decoder does
not know of such a representation, but analysing it will be key to
understanding what the decoder is able to do from the sole observation of
$\hat{Z}$, which it does see. We will denote by
$\mathcal{Z}^{\prime}=(C_{0}^{\prime},R_{0}^{\prime},C_{1}^{\prime},R_{1}^{\prime})$
the representation of the updated value of $\hat{Z}^{\prime}$ of $\hat{Z}$
after the first parallel decoding step. This representation is deduced from
$\mathcal{Z}$ through local updates as specified by the above description of
the algorithm during the first parallel decoding step. We note that
$\mathcal{Z}^{\prime}$ does not have to be a minimal representation.
Similarly, we define
$\mathcal{Z}^{\prime\prime}=(C_{0}^{\prime\prime},R_{0}^{\prime\prime},C_{1}^{\prime\prime},R_{1}^{\prime\prime})$
to be the representation of the updated mismatch $\hat{Z}^{\prime\prime}$
after the second parallel decoding step, again deduced from
$\mathcal{Z}^{\prime\prime}$ through the specified updates of $\hat{R}_{i}$,
$\hat{C}_{j}$.

Let us denote by $S_{0}=S_{00}\cup S_{11}$ the set of vertices $v\in V_{ii}$
of the stalled sequential decoder such that $R_{i}+C_{i}$ is non-zero on
$Q(v)$. Note that $S_{0}$ depends on the choice $\mathcal{Z}$ of the
representation of $\hat{Z}$. We call these vertices the active vertices of
$\mathcal{Z}$ (or simply of $\hat{Z}$ when its representation is implicit).

It will be useful to keep in mind that for any vertex $v$ of $V_{ii}\subset
V_{0}$, the fact that the sequential decoder cannot decrease $|\hat{Z}|$
locally means that on $Q(v)$, the Hamming weight of
$(R_{0}+C_{0})\cap(R_{1}+C_{1})$ is at least half the Hamming weight of
$R_{i}+C_{i}$: otherwise we could decrease $|\hat{Z}|$ by updating $\hat{Z}$
to $\hat{Z}+r_{v}+c_{v}$ where $r_{v}+c_{v}$ is the value of $R_{i}+C_{i}$ on
$Q(v)$.

We first start by drawing consequences from this fact that will tell us a lot
about the structure of $S_{0}$ and the local views of $R_{0}+C_{0}$ and
$R_{1}+C_{1}$ on the $Q$-neighbourhoods of $V_{0}$.

Let $0<\beta<1/2$. Let us define ${\sf Col}_{0}^{\beta}$ to be the set of
columns in all $Q$-neighbourhoods of $V_{00}$ (we could also view them in
$Q$-neighbourhoods of $V_{10}$), that share at least $\beta\Delta$ coordinates
with $C_{1}$, i.e. that have at least $\beta\Delta$ coordinates on which
$C_{1}$ is equal to $1$. Similarly, we define ${\sf Col}_{1}^{\beta}$ to be
the set of columns in all $Q$-neighbourhoods of $V_{11}$ that share at least
$\beta\Delta$ coordinates with $C_{0}$. We also define ${\sf Row}_{0}^{\beta}$
to be the set of rows in all $Q$-neighbourhoods of $V_{00}$ that share at
least $\beta\Delta$ coordinates with $R_{1}$ and likewise ${\sf
Row}_{1}^{\beta}$ denotes the set rows that share at least $\beta\Delta$
coordinates with $R_{0}$.

Our main technical lemma reads:

######  Lemma 11.

Suppose $|S_{0}|\leqslant\frac{\delta}{8\Delta}|V_{0}|$. For $\Delta$ large
enough, There is a constant $\kappa(\beta)$, depending only on $\beta$, such
that, whenever the decoder is stalled: for $i=0,1$,

$\displaystyle|{\sf
Col}_{i}^{\beta}|\leqslant\frac{\kappa(\beta)}{\Delta^{1-2\varepsilon}}|S_{0}|.$
$\displaystyle|{\sf
Row}_{i}^{\beta}|\leqslant\frac{\kappa(\beta)}{\Delta^{1-2\varepsilon}}|S_{0}|.$

A word of comment may be helpful at this point. Consider a column (say) in
some local view, of a vertex of $V_{00}$ (without loss of generality). Suppose
this column supports a non-zero $C_{A}$-codeword that contributes to the
makeup of the global $C_{0}$ vector in the current $\mathcal{Z}$-decomposition
of $\hat{Z}$. What prevents us from adding this codeword to $\hat{Z}$ and
decrease its weight? It is naturally the presence of contributions of either
$R_{0}$, or $R_{1}$, or $C_{1}$ (or all three) to the support of this column
vector. What we want to point out here, is that the contribution of $R_{0}$ is
completely described by a unique $Q$-neighbourhood of a single vertex of
$V_{00}$, and that the contribution of $R_{1}$ is similarly described by the
$Q$-neighbourhood of just one vertex of $V_{10}$. However, the contribution of
$C_{1}$ stems from up to $\Delta$ different $Q$-neighbourhoods, and its nature
is very much different. What Lemma 11 essentially says is that this
contribution is going to be negligible and that it will suffice for us (and
the decoder) to focus on the contributions of $R_{0}$ and $R_{1}$.

The proof of Lemma 11 will rely upon the subgraphs, both of
$\mathcal{G}_{0}^{\square}$ and of $\mathcal{G}_{A}$, induced by the active
vertices, and rely upon expansion in both these graphs. We first need to
define $S_{ii}^{\ell}$ to be the subset of $S_{ii}$ that consists of either

  * (a)

the set of vertices $v$ for which the local view on $Q(v)$ of $R_{i}+C_{i}$ is
made up of at least $\ell$ non-zero columns vectors of $C_{i}$,

  * (b)

or the set of vertices $v$ for which the local view on $Q(v)$ of $R_{i}+C_{i}$
is made up of at least $\ell$ non-zero row vectors of $R_{i}$.

######  Lemma 12.

For $i=0,1$, if $|S_{0}|\leqslant\frac{\delta}{8\Delta}|V_{0}|$, we have

$\displaystyle|S_{ii}^{\ell}|\leqslant$
$\displaystyle\frac{256}{\delta^{2}\ell^{2}}|S_{0}|\quad$ if
$\delta\ell\leqslant\Delta^{1/2-\varepsilon}$
$\displaystyle|S_{ii}^{\ell}|\leqslant$
$\displaystyle\frac{256}{\Delta^{1-2\varepsilon}}|S_{0}|\quad$
$\displaystyle\text{if $\delta\ell\geqslant\Delta^{1/2-\varepsilon}$}.$

###### Proof.

We prove the result for $i=1$ and definition (a) of $S_{11}^{\ell}$, the other
cases being identical. We consider $E(S_{11}^{\ell},S_{00})$ in the subgraph
of $\mathcal{G}^{\square}$ where the edges belong to
$(R_{0}+C_{0})\cap(R_{1}+C_{1})$. We argue that the degree of every vertex of
$S_{11}$ is at least half the weight of its local view in $R_{1}+C_{1}$, so at
least half of $\ell\delta\Delta$ when this quantity is not more than
$\Delta^{3/2-\varepsilon}$, by robustness of the local dual tensor code. This
gives

$\frac{1}{2}\ell\delta\Delta|S_{11}^{\ell}|\leqslant|E(S_{11}^{\ell},S_{00})|.$

We now apply the Expander mixing Lemma 3 in $\mathcal{G}_{0}^{\square}$. This
gives

$\displaystyle\frac{1}{2}\ell\delta\Delta|S_{11}^{\ell}|$
$\displaystyle\leqslant\Delta^{2}\frac{|S_{11}^{\ell}||S_{00}|}{|V_{00}|}+4\Delta\sqrt{|S_{11}^{\ell}||S_{00}|}$
$\displaystyle\leqslant\frac{1}{4}\delta\Delta|S_{11}^{\ell}|+4\Delta\sqrt{|S_{11}^{\ell}||S_{00}|}$
since $|S_{00}|/|V_{00}|\leqslant 2|S_{0}|/|V_{0}|$ and
$|S_{0}|\leqslant\delta|V_{0}|/8\Delta$
$\displaystyle\ell\delta\sqrt{|S_{11}^{\ell}|}$ $\displaystyle\leqslant
16\sqrt{|S_{00}|}$ $\displaystyle|S_{11}^{\ell}|$
$\displaystyle\leqslant\frac{256}{\delta^{2}\ell^{2}}|S_{00}|$

which gives the first statement of the lemma by writing
$|S_{00}|\leqslant|S_{0}|$. The second statement follows analogously, by
arguing that when $\delta\ell\geqslant\Delta^{1/2-\varepsilon}$ the weight of
the local view is not less than $\Delta^{3/2-\varepsilon}$. ∎

######  Lemma 13.

Let $T_{10}^{\beta,\ell}$ be the set of vertices of $V_{10}$ whose
$Q$-neighbourhoods contain at least $\ell$ columns of ${\sf Col}_{0}^{\beta}$.
Under the hypothesis $|S_{0}|\leqslant\frac{\delta}{8\Delta}|V_{0}|$, for
$\Delta$ large enough, we have

$|T_{10}^{\beta,\ell}|\leqslant\frac{64}{\beta^{2}\Delta}|S_{11}^{\ell\beta/2}|.$

###### Proof.

Consider a the subarray of the $Q$-neighbourhood of a vertex of
$T_{10}^{\beta,\ell}$ consisting of the $\ell$ columns of ${\sf
Col}_{0}^{\beta}$. One easily checks, by counting the number coordinates in
the subbarray on which $\hat{C}_{1}$ must be equal to $1$, that there are at
least $\beta\Delta/2$ rows on which $\hat{C}_{1}$ has weight at least
$\beta\ell/2$. This in turn implies that, in the graph $\mathcal{G}_{A}$, this
vertex has at least $\beta\Delta/2$ outgoing edges that fall into
$|S_{11}^{\ell\beta/2}|$.

Let us estimate $|E(T_{10}^{\beta,\ell},S_{11}^{\ell\beta/2})|$ in
$\mathcal{G}_{A}$. We have just proved

$|T_{10}^{\beta,\ell}|\frac{1}{2}\beta\Delta\leqslant|E(T_{10}^{\beta,\ell},S_{11}^{\ell\beta/2})|.$

We now apply the Expander mixing Lemma 3 in $\mathcal{G}_{A}$. We get

$|T_{10}^{\beta,\ell}|\frac{1}{2}\beta\Delta\leqslant\Delta\frac{|T_{10}^{\beta,\ell}||S_{11}^{\ell\beta/2}|}{|V_{11}|}+2\sqrt{\Delta}\sqrt{|T_{10}^{\beta,\ell}||S_{11}^{\ell\beta/2}|}.$

Writing $|S_{11}^{\ell\beta/2}|/|V_{11}|\leqslant|S_{11}|/|V_{11}|\leqslant
2|S_{0}|/|V_{0}|$, we get, for fixed $\beta$ and $\Delta$ large enough,

$\displaystyle|T_{10}^{\beta,\ell}|\frac{1}{4}\beta\Delta$
$\displaystyle\leqslant
2\sqrt{\Delta}\sqrt{|T_{10}^{\beta,\ell}||S_{11}^{\ell\beta/2}|}$
$\displaystyle|T_{10}^{\beta,\ell}|^{1/2}$
$\displaystyle\leqslant\frac{8}{\beta\Delta^{1/2}}|S_{11}^{\ell\beta/2}|^{1/2}$

whence the claimed result after squaring. ∎

###### Proof of Lemma 11.

We prove the Lemma for $|{\sf Col}_{0}^{\beta}|$, the other cases being
essentially identical. Write

$\displaystyle|{\sf
Col}_{0}^{\beta}|\leqslant\sum_{\ell<\ell_{\max}}\ell|T_{10}^{\beta,\ell}|+\Delta|T_{10}^{\beta,\ell_{\max}}|$
(5)

where $\ell_{\max}$ is chosen so as to have
$\delta\ell_{\max}\beta/2=\Delta^{1/2-\varepsilon}$. Applying Lemmas 13 and 12
we obtain

$\displaystyle|{\sf Col}_{0}^{\beta}|$
$\displaystyle\leqslant\sum_{\ell<\ell_{\max}}\ell\frac{64}{\beta^{2}\Delta}|S_{11}^{\ell\beta/2}|+\Delta\frac{64}{\beta^{2}\Delta}|S_{11}^{\ell_{\max}\beta/2}|$
$\displaystyle\leqslant\sum_{\ell}\frac{2^{16}}{\delta^{2}\ell\beta^{4}}\frac{1}{\Delta}|S_{0}|+\frac{2^{14}}{\delta^{2}\beta^{2}\Delta^{1-2\varepsilon}}|S_{0}|$

from which the result follows, after writing that
$\sum_{\ell}1/\ell\leqslant\ln\Delta\leqslant\Delta^{2\varepsilon}$. ∎

######  Definition 14 (normal vertices of $S_{00}$ and $S_{11}$).

Let us say that a vertex $v$ of $S_{00}$ is _normal_ if
$\|r_{v}\|+\|c_{v}\|<\Delta^{1/2-\varepsilon}/4$, where $r_{v},c_{v}$ are the
local components of $R_{0},C_{0}$. Normal vertices of $S_{11}$ are defined
similarly. A vertex which is not normal will be said to be _exceptional_.

Below we will talk about normal columns of $C_{0}$ and normal rows of $R_{1}$.
This will mean that in their respective local views in $V_{00}$ and $V_{11}$
they belong to the local view of a normal vertex.

The terminology “normal” and “exceptional” is justified by the following
lemma.

######  Lemma 15.

Let $S_{0}^{e}$ be the set of exceptional vertices of $S_{0}$. Under the
hypothesis $|S_{0}|\leqslant\frac{\delta}{8\Delta}|V_{0}|$, we have

$|S_{0}^{e}|\leqslant\frac{\kappa}{\delta^{2}\Delta^{1-2\varepsilon}}|S_{0}|$

for some absolute constant $\kappa$.

###### Proof.

Let $S_{00}^{e}$ ($S_{11}^{e}$) be the set of exceptional vertices of $S_{00}$
($S_{11}$). The definition of an exceptional (not normal) vertex $v$ of
$S_{00}$ implies that $R_{0}+C_{0}$ has weight at least
$\delta\Delta^{3/2-\varepsilon}/8$ on $Q(v)$, and therefore that
$(R_{0}+C_{0})\cap(R_{1}+C_{1})$ has weight at least
$\delta\Delta^{3/2-\varepsilon}/16$ on $Q(v)$. The weight of
$(R_{0}+C_{0})\cap(R_{1}+C_{1})$ on $\bigcup_{v\in S_{00}^{e}}Q(v)$ is
therefore at least

$|S_{00}^{e}|\delta\Delta^{3/2-\varepsilon}/16$

and it is also not more than the number of edges $|E(S_{00}^{e},S_{11})|$ in
the graph $\mathcal{G}_{0}^{\square}$. By the Expander mixing Lemma in
$\mathcal{G}_{0}^{\square}$, we have

$\frac{1}{16}\delta\Delta^{3/2-\varepsilon}|S_{00}^{e}|\leqslant|E(S_{00}^{e},S_{11})|\leqslant\Delta^{2}\frac{|S_{00}^{e}||S_{11}|}{|V_{00}|}+4\Delta\sqrt{|S_{00}^{e}||S_{11}|}.$

Writing $|S_{11}|/|V_{00}|\leqslant 2|S_{0}|/|V_{0}|$, for $\Delta$ large
enough, we straightforwardly obtain that

$\displaystyle\frac{1}{32}\delta\Delta^{3/2-\varepsilon}|S_{00}^{e}|^{1/2}$
$\displaystyle\leqslant 4\Delta|S_{11}|^{1/2}$ $\displaystyle|S_{00}^{e}|$
$\displaystyle\leqslant\frac{2^{14}}{\delta^{2}}\frac{1}{\Delta^{1-2\varepsilon}}|S_{11}|.$

We obtain similarly

$|S_{11}^{e}|\leqslant\frac{2^{14}}{\delta^{2}}\frac{1}{\Delta^{1-2\varepsilon}}|S_{00}|.$

Hence the result, by summing the two inequalities. ∎

Similarly to $S_{0}=S_{00}\cup S_{11}$, let us set $S_{1}=S_{10}\cup S_{01}$
where $S_{10}$ and $S_{01}$ are the set of active vertices of $V_{10}$ and
$V_{01}$ relative to $\hat{Z}$. In other words, $S_{10}$ $(S_{01})$ is the set
of vertices of $V_{10}$ ($V_{01}$) on which the local view of $R_{1}+C_{0}$
($R_{0}+C_{1}$) is non-zero.

######  Definition 16 (agglutinating vertices of $V_{ij}$, $i\neq j$).

Let us say that a vertex $v$ of $S_{ij}$ is agglutinating if
$\|r_{v}\|\geqslant\delta\Delta/3$, where $r_{v}$ is the local component of
$R_{i}$, or if $\|c_{v}\|\geqslant\delta\Delta/3$, where $c_{v}$ is the local
component of $C_{j}$.

######  Definition 17 (decodable agglutinating vertex).

Let us say that an agglutinating vertex $v$ of $S_{10}$ (resp. $S_{01}$) is
decodable, if at most $\Delta^{\gamma}/2$ columms in its local view are in
common with exceptional vertices of $S_{00}$ (resp. $S_{11}$), and at most
$\Delta^{\gamma}/2$ rows in its local view are in common with exceptional
vertices of $S_{11}$ (resp. $S_{00}$).

We now show that every decodable agglutinating vertex really is decodable in
the sense of the first parallel decoding step:

######  Proposition 18.

The tweaked decoder that is applied during the first parallel decoding step,
described in Section 6.1, identifies correctly every decodable agglutinating
vertex $v$ of $S_{10}$ or of $S_{01}$, i.e. it finds the required non-zero
$r_{v}+c_{v}$.

###### Proof.

Let $v$ be a decodable agglutinating vertex of $S_{10}$, the case $v\in
S_{01}$ being essentially identical. We set $A_{0}$ to consist of all the
indexes of all normal rows in $Q(v)$ and $B_{0}$ to consist of all the indexes
of normal columns. We now show that the local component $r_{v}+c_{v}$ of
$R_{1}+C_{0}$, restricted to $A_{0}\times B_{0}$ satisfies all the
requirements of the tweaked decoder. Indeed, we must have
$|(r_{v}+c_{v})_{|A_{0}\times B_{0}}|>w$, otherwise robustness (with
resistance to puncturing) would imply that $r_{v}+c_{v}$ would be expressible
as sum of fewer than $O(\Delta^{1/2})$ non-zero rows and columns of
$C_{A}\otimes\mathbb{F}_{2}^{B}$ and $\mathbb{F}_{2}^{A}\otimes C_{B}$, which
would contradict local minimality of $\|r_{v}\|+\|c_{v}\|$, since we have
supposed either $\|r_{v}\|\geqslant\delta\Delta/3$, or
$\|c_{v}\|\geqslant\delta\Delta/3$, by definition of an agglutinating vertex.

Furthermore, the contribution of $R_{0}$ on any normal column is less than
$\Delta^{1/2-\varepsilon}/4$ by definition of a normal column. Therefore, the
weight of $R_{0}$ on $A\times B_{0}$ is less than
$\Delta\cdot\Delta^{1/2-\varepsilon}/4=w/4$. Similarly, the weight of $C_{1}$
on $A_{0}\times B$ is less than $w/4$, and therefore the weight of
$R_{0}+C_{1}$ on $A_{0}\times B_{0}$ is $<w/2$. After removing $r_{v}+c_{v}$,
the updated value $R_{1}^{\prime}+C_{0}^{\prime}$ on $A_{0}\times B_{0}$ is
zero, so the value of $|\hat{Z}|$ on $A_{0}\times B_{0}$ is that of
$|R_{0}+C_{1}|$ and is $<w/2$.

Finally, since the weight of $R_{0}+C_{1}$ on $A_{0}\times B_{0}$ is $<w/2$
and the weight of $R_{1}+C_{0}$ on $A_{0}\times B_{0}$ is $>w$, we have that
the weight of $\hat{Z}=R_{0}+C_{1}+R_{1}+C_{0}$ on $A_{0}\times B_{0}$ is
$>w/2$. ∎

We remark that the above proof tells us in passing that the Hamming weight of
$\hat{Z}$ on the local view of a decodable agglutinating vertex is at least
$w/2$. We note this for future reference.

######  Proposition 19.

Whenever the sequential decoder is stalled, the Hamming weight of $\hat{Z}$
restricted to $Q(v)$, for $v$ a decodable agglutinating vertex of $S_{10}$ or
of $S_{01}$, is at least equal to $\Delta^{3/2-\varepsilon}/2$.

Let us denote by $K^{\gamma}_{10}$ ($K_{01}^{\gamma}$) the set of vertices of
$V_{10}$ ($V_{01}$) whose $Q$-neighbourhoods have at least $\Delta^{\gamma}/2$
columns (rows) in common with exceptional vertices of $S_{00}$, or that have
at least $\Delta^{\gamma}/2$ rows (columns) in common with exceptional
vertices of $S_{11}$. We then set $K^{\gamma}=K_{10}^{\gamma}\cup
K_{01}^{\gamma}$. These can be thought of as the vertices of $V_{1}$ whose
$Q$-neighbourhoods share an exceptionally large number of rows or of columns
with exceptional vertices of $S_{0}$.

######  Lemma 20.

Suppose $|S_{0}|\leqslant\frac{\delta}{8\Delta}|V_{0}|$. Then there is an
absolute constant $\kappa$ such that

$|K^{\gamma}|\leqslant\frac{\kappa}{\delta^{2}}\frac{1}{\Delta^{2-4\varepsilon}}|S_{0}|.$

###### Proof.

We give an upper bound for $K_{10}^{\gamma}$, an identical one follows for
$K_{01}^{\gamma}$ by symmetry. Consider the case when $K_{10}^{\gamma}$ has
$\Delta^{\gamma}/2$ columns in common with the $Q$-neighbourhoods of
exceptional vertices of $S_{00}^{e}$, the other case being similar. This last
fact means that all vertices of $K_{10}^{\gamma}$ have degree at least
$\Delta^{\gamma}/2$ in the subgraph of $\mathcal{G}_{B}$ induced by
$K_{10}^{\gamma}$ and $S_{00}^{e}$. By the Expander mixing Lemma in
$\mathcal{G}_{B}$ we therefore have

$|K_{10}^{\gamma}|\Delta^{\gamma}/2\leqslant|E(K^{\gamma},S_{0}^{e})|\leqslant\Delta\frac{|K_{10}^{\gamma}||S_{00}^{e}|}{|V_{00}|}+2\sqrt{\Delta}\sqrt{|K_{10}^{\gamma}||S_{0}^{e}|}.$

Bounding $|S_{00}^{e}|/|V_{00}|$ from above by $2|S_{0}|/|V_{0}|$ we easily
get

$|K_{10}^{\gamma}|\Delta^{\gamma}/4\leqslant
2\sqrt{\Delta}\sqrt{|K_{10}^{\gamma}||S_{0}^{e}|}$

whence

$\displaystyle|K_{10}^{\gamma}|^{1/2}$ $\displaystyle\leqslant
8\Delta^{1/2-\gamma}|S_{0}^{e}|^{1/2}$ $\displaystyle|K_{10}^{\gamma}|$
$\displaystyle\leqslant 64\Delta^{1-2\gamma}|S_{0}^{e}|$
$\displaystyle\leqslant\frac{\kappa}{\delta^{2}}\Delta^{2\varepsilon-2\gamma}|S_{0}|$

by applying Lemma 15. Hence the result, since we have supposed
$\gamma=1-\varepsilon$. ∎

######  Proposition 21.

Let $v$ be a vertex of $S_{10}$ (resp. $S_{01}$) that is not in $K^{\gamma}$
and that is decoded by the tweaked decoder. Let $A_{n}$ and $B_{n}$ be the
index sets of its normal rows and its normal columns respectively. After
(tweaked) decoding, the contribution of $R_{1}^{\prime}+C_{0}^{\prime}$ (resp.
$R_{0}^{\prime}+C_{1}^{\prime}$) to the coordinate set indexed by $A_{n}\times
B_{n}$ in $Q(v)$ is supported by columns of ${\sf Col}_{0}^{\beta}$ and ${\sf
Row}_{1}^{\beta}$ (resp. ${\sf Col}_{1}^{\beta}$ and ${\sf Row}_{0}^{\beta}$)
for some $\beta>1/3$.

###### Proof.

We treat the case $v\in S_{10}$, the case $v\in S_{01}$ being essentially
identical. First consider the dual-tensor codeword
$r_{v}^{\prime}+c_{v}^{\prime}$ that the decoder has identified on
$A_{0}\times B_{0}$ (which may not be equal to $A_{n}\times B_{n}$). We
compare it to $r_{v}+c_{v}$, the reduced local view of $R_{1}+C_{0}$. We
recall, that by definition of the tweaked decoder, we must have that
$|\hat{Z}+r^{\prime}_{v}+c^{\prime}_{v}|$ is less than $w/2$ on $A_{0}\times
B_{0}$. So in particular it must be less than $w/2$ on $(A_{0}\cap
A_{n})\times(B_{0}\cap B_{n})$. Since the value of $|\hat{Z}+r_{v}+c_{v}|$ is
less than $w/2$ on $A_{n}\times B_{n}$, by definition of normal rows and
columns, we must have that
$|r_{v}+c_{v}+r^{\prime}_{v}+c^{\prime}_{v}|\leqslant w$ on $(A_{0}\cap
A_{n})\times(B_{0}\cap B_{n})$. Now $A_{0}\cap A_{n}$ and $B_{0}\cap B_{n}$
both have cardinality at least
$\Delta-\Delta^{\gamma}/2-\Delta^{\gamma}/2=\Delta-\Delta^{\gamma}$, so that
we may apply robustness with resistance to puncturing to
$r_{v}+c_{v}+r^{\prime}_{v}+c^{\prime}_{v}$ and deduce that
$\|r_{v}\|+\|c_{v}\|+\|r^{\prime}_{v}\|+\|c^{\prime}_{v}\|$ is
$O(\Delta^{1/2}+\Delta^{\gamma})$. This in turn implies that, after tweaked
decoding, every normal column (i.e. indexed by $b\in B_{n}$) has at most
$O(\Delta^{1/2}+\Delta^{\gamma})$ coordinates on which $R_{0}$ or
$R_{1}^{\prime}$ equals $1$: therefore, if a column, indexed by $b\in B_{n}$
say, is the support of a non-zero column codeword $c\in C_{A}$ in
$C_{0}^{\prime}$, the only way this column has not been decoded is for the
support of $c$ on $A\times\\{b\\}$ to coincide with the support of $C_{1}$ on
almost half its coordinates (minus $O(\Delta^{1/2}+\Delta^{\gamma})$),
otherwise more than half the support of $c$ contributes to $\hat{Z}$, and
adding $c$ would decrease $|\hat{Z}|$. Summarising, if the column under
discussion does not belong to ${\sf Col}_{0}^{\beta}$, it will be decoded by
the tweaked decoder. A similar argument holds for normal rows. ∎

Note that the choice $\beta>1/3$ in this last proposition is somewhat
arbitrary and could in principle be chosen arbitrarily close to $1/2$.

######  Proposition 22.

Let $v$ be a vertex of $S_{10}$ (resp. $S_{01}$) that is not in $K^{\gamma}$
and that is not identified as decodable (hence not decoded) by the tweaked
decoder. Let $A_{n}$ and $B_{n}$ be the index sets of its normal rows and its
normal columns respectively. Then the contribution of $R_{1}+C_{0}$ (resp.
$R_{0}+C_{1}$) to the coordinate set indexed by $A_{n}\times B_{n}$ in $Q(v)$
is supported by columns of ${\sf Col}_{0}^{\beta}$ and ${\sf Row}_{1}^{\beta}$
(resp. ${\sf Col}_{1}^{\beta}$ and ${\sf Row}_{0}^{\beta}$) for
$\beta=1/6+o_{\Delta}(1)$.

###### Proof.

Suppose $v\in S_{10}$ is such a vertex. The vertex $v$ cannot be agglutinating
by Proposition 18. Indeed, if it were agglutinating, then since we suppose it
not in $K^{\gamma}$, it would be a decodable agglutinating vertex and would be
decoded by the tweaked decoder. Therefore, we have $\|r_{v}\|<\delta\Delta/3$
and $\|c_{v}\|<\delta\Delta/3$, where $r_{v},c_{v}$ are the components of
$R_{1}$ and $C_{0}$ on $Q(v)$. For every column of $Q(v)$, the contribution of
$R_{1}$ to its support is therefore $<\delta\Delta/3$. For every normal
column, the contribution of $R_{0}$ to its support is
$<\Delta^{1/2-\varepsilon}/4$ by definition of normality. Therefore, on every
normal column on which $C_{0}$ is non-zero we must have a contribution of
$C_{1}$ that is at least
$\delta\Delta/2-\delta\Delta/3-\Delta^{1/2-\varepsilon}/4$. We argue similarly
for normal rows in $Q(v)$. ∎

#### Situation after the first parallel decoding step.

We now argue that this tweaked decoding step has drastically reduced the
number of active vertices of $\hat{Z}$ in $V_{0}$.

A remaining active vertex of $V_{0}$ may be one of the exceptional vertices of
$S_{0}^{e}\subset S_{0}$. By Lemma 15 there are at most
$\kappa|S_{0}|/\Delta^{1-2\varepsilon}$ of them, for some constant $\kappa$.

To bound from above the additional number of active vertices, we simply bound
from above the number of $C_{A}$-column vectors of $C_{0}^{\prime}$ and
$C_{1}^{\prime}$ (and of $C_{B}$-row vectors of $R_{0}^{\prime}$ and
$R_{1}^{\prime}$) that are supported by the $Q$-neighbourhood of a non-
exceptional vertex $v\notin S_{e}$. Such a row or column codeword may

  * –

belong to the $Q$-neighbourhood of a vertex of $V_{1}$ that has many columns
or rows in common with exceptional vertices of $V_{0}$: the set of such
vertices was defined as $K^{\gamma}$, and by Lemma 20, there are not more than
$\kappa|S_{0}|/\Delta^{2-4\varepsilon}$ of them. These vertices therefore
contribute at most $2\Delta|K^{\gamma}|$ row and column vectors, so not more
than $\kappa|S_{0}|/\Delta^{1-4\varepsilon}$ for some constant $\kappa$.

  * –

Remaining row or column codewords (that have not been removed by the decoder
or have wrongly been introduced by the decoder) may also be present in the
$Q$-neighbourhoods of vertices of $V_{1}$ that have been decoded by the
tweaked decoder. By Proposition 21, all these rows and columns must belong to
${\sf Row}_{i}^{\beta}$ and ${\sf Col}_{i}^{\beta}$, for some fixed value
$\beta$ and $i=0,1$. By Lemma 11 there are at most
$\kappa|S_{0}|/\Delta^{1-2\varepsilon}$ such column and row vectors, for some
constant $\kappa$.

  * –

The remaining row or column codewords must be present in the the
$Q$-neighbourhoods of vertices of $V_{1}$ that are not in $K^{\gamma}$ and
have not been decoded by the tweaked decoder. By Proposition 22, all these
rows and columns must belong to ${\sf Row}_{i}^{\beta}$ and ${\sf
Col}_{i}^{\beta}$, for some fixed value $\beta$ and $i=0,1$. Again, by Lemma
11 there are at most $\kappa|S_{0}|/\Delta^{1-2\varepsilon}$ such column and
row vectors, for some constant $\kappa$.

Summing everything, we have shown the following:

######  Theorem 23.

We suppose $|S_{0}|\leqslant\frac{\delta}{8\Delta}|V_{0}|$. Let
$S_{0}^{\prime}$ be the set of active vertices of $V_{0}$ after the first
parallel decoding step, i.e. the set of vertices of $V_{00}$ on whose
$Q$-neighbourhood $R_{0}^{\prime}+C_{0}^{\prime}$ is non-zero, together with
the set of vertices of $V_{11}$ on on whose $Q$-neighbourhood
$R_{1}^{\prime}+C_{1}^{\prime}$ is non-zero. We have
$|S_{0}^{\prime}|\leqslant\kappa|S_{0}|/\Delta^{1-4\varepsilon}$ for some
constant $\kappa$.

Before analysing the second parallel decoding step, we need the following
consequence of the above analysis.

######  Proposition 24.

When the sequential decoder is stalled, we have
$|\hat{Z}|\geqslant\kappa|S_{0}|\Delta^{1/2-\varepsilon}$ for some constant
$\kappa$.

###### Proof.

By Lemma 15, the number of exceptional vertices in $S_{0}^{e}$ is a small
fraction of the set of active vertices $S_{0}$. There are therefore at least
at least $|S_{0}|/2$ (say) normal rows and columns. By Lemma 20 only a small
fraction of the set of normal rows and columns spanned by $S_{0}$ can end up
in the $Q$-neighbourhood of a vertex of $K^{\gamma}$ in $V_{1}$. Furthermore,
by arguing as in the proof of Proposition 22, if a normal row or a normal
column is not in the $Q$-neighbourhood of a decodable agglutinating vertex, it
must belong to one of the sets ${\sf Row}_{i}^{\beta}$ or ${\sf
Col}_{j}^{\beta}$ for $\beta=1/6+o_{\Delta}(1)$, otherwise it would have
already been decoded by the sequential decoder. Therefore, most normal rows
and columns of $S_{0}$ must belong to the $Q$-neighbourhood of a decodable
agglutinating vertex of $S_{1}$ (hence the terminology ’agglutinating’). The
number of decodable agglutinating vertices of $S_{1}$ is therefore at least
equal to $\kappa|S_{0}|/\Delta$ for some constant $\kappa$, and the result
follows from Proposition 19. ∎

#### Analysis of the second parallel decoding step.

This step is simpler than the first. Recall that the second parallel decoding
step is applied on vertices of $V_{0}$ and uses regular decoding (i.e.
decreases $|\hat{Z}|$ as much as possible on complete, unpunctured, local
views).

To avoid confusion between the different stages of the decoder, let us denote
by $\hat{Z},\hat{Z}^{\prime},\hat{Z}^{\prime\prime}$ respectively the values
of the mismatch $\hat{Z}$ of the stalled serial decoder before the first
parallel decoding step, just after the first parallel decoding step on
$V_{1}$, and finally after the second parallel decoding step on $V_{0}$.
Accordingly we write $\hat{Z}=C_{0}+R_{0}+C_{1}+R_{1}$,
$\hat{Z}^{\prime}=C^{\prime}_{0}+R^{\prime}_{0}+C^{\prime}_{1}+R^{\prime}_{1}$,
$\hat{Z}^{\prime\prime}=C^{\prime\prime}_{0}+R^{\prime\prime}_{0}+C^{\prime\prime}_{1}+R^{\prime\prime}_{1}$,
and use the notation $S_{0}=S_{00}\cup S_{11}$,
$S_{0}^{\prime}=S_{00}^{\prime}\cup S_{11}^{\prime}$,
$S_{0}^{\prime\prime}=S_{00}^{\prime\prime}\cup S_{11}^{\prime\prime}$ for the
set of active vertices of $V_{0}$ at each stage of decoding.

We recall also that $\mathcal{Z}=(C_{0},R_{0},C_{1},R_{1})$ has been chosen to
be a minimal representation of $\hat{Z}$. The representations
$\mathcal{Z^{\prime}}=(C_{0}^{\prime},R_{0}^{\prime},C_{1}^{\prime},R_{1}^{\prime})$
and
$\mathcal{Z}^{\prime\prime}=(C_{0}^{\prime\prime},R_{0}^{\prime\prime},C_{1}^{\prime\prime},R_{1}^{\prime\prime})$
are however simply deduced from $\mathcal{Z}$ by the decoder’s increments.

######  Lemma 25.

Let $x_{0}\geqslant 1$ (resp. $x_{1}\geqslant 1$) be such that
$x_{0}\delta\Delta$ (resp. $x_{1}\delta\Delta$) is the average weight of
$R^{\prime\prime}_{0}+C^{\prime\prime}_{0}$ (resp.
$R^{\prime\prime}_{1}+C^{\prime\prime}_{1}$) on the union of the
$Q$-neighbourhoods of $S^{\prime\prime}_{00}$ (resp. $S^{\prime\prime}_{11}$).
Under the hypothesis $|S_{0}|\leqslant\frac{\delta}{8\Delta}|V_{0}|$, we have

$\displaystyle|S^{\prime\prime}_{00}|$
$\displaystyle\leqslant\frac{256}{x_{0}^{2}\delta^{2}}|S^{\prime}_{0}|$
$\displaystyle|S^{\prime\prime}_{11}|$
$\displaystyle\leqslant\frac{256}{x_{1}^{2}\delta^{2}}|S^{\prime}_{0}|.$

###### Proof.

Observe that $x_{i}\geqslant 1$, $i=0,1$, because $\delta\Delta$ is the
minimum distance of the dual tensor code. Now for any vertex $v$ of $V_{00}$,
we must have

$|(R^{\prime\prime}_{0}+C^{\prime\prime}_{0})_{|Q(v)}|\leqslant
2|(R^{\prime}_{1}+C^{\prime}_{1})_{|Q(v)}|$ (6)

(otherwise the zero vector is a better choice than
$R^{\prime\prime}_{0}+C^{\prime\prime}_{0}$ on $Q(v)$, since it gives a lower
value of $|\hat{Z}^{\prime\prime}|$).

From (6) we have that the average degree of vertices of
$S^{\prime\prime}_{00}$ in the subgraph of $\mathcal{G}_{0}^{\square}$ induced
by $S^{\prime\prime}_{00}$ and $S^{\prime}_{11}$ is at least
$x\delta\Delta/2$. Applying the Expander mixing Lemma in
$\mathcal{G}_{0}^{\square}$ we have

$\frac{1}{2}|S^{\prime\prime}_{00}|x\delta\Delta\leqslant|E(S^{\prime\prime}_{00},S^{\prime}_{11})|\leqslant\Delta^{2}\frac{|S_{00}^{\prime\prime}||S_{11}^{\prime}|}{|V_{00}|}+4\Delta\sqrt{|S^{\prime\prime}_{00}||S^{\prime}_{11}|}.$

Writing $|S_{11}^{\prime}|/|V_{00}|\leqslant
2|S_{0}^{\prime}|/|V_{0}|\leqslant 2|S_{0}|/|V_{0}|$ by Theorem 23 and
applying the hypothesis $|S_{0}|\leqslant\frac{\delta}{8\Delta}|V_{0}|$, we
get

$\displaystyle\frac{1}{4}|S^{\prime\prime}_{00}|x_{0}\delta\Delta$
$\displaystyle\leqslant 4\Delta\sqrt{|S^{\prime\prime}_{00}||S^{\prime}_{0}|}$
$\displaystyle|S^{\prime\prime}_{00}|^{1/2}$
$\displaystyle\leqslant\frac{16}{x_{0}\delta}|S^{\prime}_{0}|^{1/2}$
$\displaystyle|S^{\prime\prime}_{00}|$
$\displaystyle\leqslant\frac{256}{x_{0}^{2}\delta^{2}}|S^{\prime}_{0}|.$

The same reasoning is valid for $S^{\prime\prime}_{11}$. ∎

The following theorem is the core result of the analysis of the whole parallel
decoding procedure, it states that together the two steps of the parallel
decoding procedure decrease the Hamming weight of $\hat{Z}$.

######  Theorem 26.

Under the hypothesis $|S_{0}|\leqslant\frac{\delta}{8\Delta}|V_{0}|$, after
the second parallel decoding step we have
$|\hat{Z}^{\prime\prime}|\leqslant\kappa|S_{0}|\Delta^{4\varepsilon}$ for some
constant $\kappa$.

###### Proof.

From Lemma 25 we obtain that

$|R^{\prime\prime}_{0}+C^{\prime\prime}_{0}|=\sum_{v\in
S^{\prime\prime}_{00}}|(R^{\prime\prime}_{0}+C^{\prime\prime}_{0})_{Q(v)}|=|S^{\prime\prime}_{00}|x_{0}\delta\Delta\leqslant\frac{256}{x_{0}\delta}|S^{\prime}_{0}|\Delta$

and applying Theorem 23 we obtain

$|R^{\prime\prime}_{0}+C^{\prime\prime}_{0}|\leqslant\kappa|S_{0}|\Delta^{4\varepsilon}$

for some constant $\kappa$ (remembering that $x_{0}\geqslant 1$). We have
naturally the same upper bound for
$|R^{\prime\prime}_{1}+C^{\prime\prime}_{1}|$ and since

$|\hat{Z}^{\prime\prime}|\leqslant|R^{\prime\prime}_{0}+C^{\prime\prime}_{0}|+|R^{\prime\prime}_{1}+C^{\prime\prime}_{1}|$

we have the claimed result. ∎

For the proof of Theorem 2 we will also need the following Lemma. Recall that
$\|\hat{Z}\|$ denotes the minimum weight $\|\mathcal{Z}\|$ of a representation
of $\hat{Z}$.

######  Lemma 27.

Let $\hat{Z}$ and $\hat{Z}^{\prime\prime}$ be the states of $\hat{Z}$ just
before a parallel decoding procedure and just after the second step of the
parallel decoding procedure. We have
$\|\hat{Z}^{\prime\prime}\|\leqslant\|\hat{Z}\|/2$.

###### Proof.

Recall that we have taken $\mathcal{Z}=(C_{0},R_{0},C_{1},R_{1})$ such that
$\|\mathcal{Z}\|=\|\hat{Z}\|$. As mentioned just before Lemma 25, the two
representations
$\mathcal{Z^{\prime}}=(C_{0}^{\prime},R_{0}^{\prime},C_{1}^{\prime},R_{1}^{\prime})$
and
$\mathcal{Z}^{\prime\prime}=(C_{0}^{\prime\prime},R_{0}^{\prime\prime},C_{1}^{\prime\prime},R_{1}^{\prime\prime})$
that are deduced from $\mathcal{Z}$ through the parallel decoder’s updates are
not necessarily minimal, but nevertheless it suffices to show that
$\|\mathcal{Z}^{\prime\prime}\|\leqslant\|\mathcal{Z}\|/2$.

Let $x_{0},x_{1}$ be defined as in Lemma 25. We consider two cases

  * (i)

$x_{0}>\Delta^{1/4}$. In this case Lemma 25 and Theorem 23 imply
$|S_{00}^{\prime\prime}|\leqslant\frac{\kappa\Delta^{4\varepsilon}}{\delta^{2}\Delta^{3/2}}|S_{0}|$
for some constant $\kappa$. We deduce
$\|R_{0}^{\prime\prime}\|+\|C_{0}^{\prime\prime}\|\leqslant|S_{00}^{\prime\prime}|2\Delta\leqslant|S_{0}|/4$
for $\Delta$ large enough.

  * (ii)

$x_{0}\leqslant\Delta^{1/4}$. All vertices of $S_{00}^{\prime\prime}$ on which
$R_{00}^{\prime\prime}+C_{00}^{\prime\prime}$ has Hamming weight less than
$\Delta^{3/2-\varepsilon}$ contribute, by applying robustness with
$w=\Delta^{3/2-\varepsilon}$, at most
$\frac{2}{\delta}\Delta^{1/2-\varepsilon}|S_{00}^{\prime\prime}|$ to
$\|R_{0}^{\prime\prime}\|+\|C_{0}^{\prime\prime}\|$. The vertices of
$S_{00}^{\prime\prime}$ on which $R_{00}^{\prime\prime}+C_{00}^{\prime\prime}$
has Hamming weight $\geqslant\Delta^{3/2-\varepsilon}$ number not more than
$\frac{\delta}{\Delta^{1/4-\varepsilon}}|S_{00}^{\prime\prime}|$, and we again
easily deduce from Lemma 25 and Theorem 23 that
$\|R_{0}^{\prime\prime}\|+\|C_{0}^{\prime\prime}\|\leqslant|S_{0}|/4$ for
$\Delta$ large enough.

We therefore always have
$\|R_{0}^{\prime\prime}\|+\|C_{0}^{\prime\prime}\|\leqslant|S_{0}|/4$. We also
have the symmetrical inequality
$\|R_{1}^{\prime\prime}\|+\|C_{1}^{\prime\prime}\|\leqslant|S_{0}|/4$, and
summing both we get

$\|R_{0}^{\prime\prime}\|+\|C_{0}^{\prime\prime}\|+\|R_{1}^{\prime\prime}\|+\|C_{1}^{\prime\prime}\|\leqslant|S_{0}|/2\leqslant\|\hat{Z}\|/2.$

∎

###### Proof of Theorem 2.

Let $\boldsymbol{e}$ be the original error vector, with local view $e_{v}$ for
vertices $v\in V$. We recall that the decoder initially computes a local
estimation $\varepsilon_{v}$ of the error on all $Q$-neighbourhoods of
vertices $v\in V_{1}$. We have $\varepsilon_{v}=e_{v}+r_{v}+c_{v}$ where
$r_{v}+c_{v}$ is a local dual tensor codeword. Over the partition
$(Q(v))_{v\in V_{01}}$ of the set $Q$ of coordinates, the global vector
$\boldsymbol{\varepsilon}_{01}$ defined by the local views $\varepsilon_{v}$
differs from the error vector $\boldsymbol{e}$ by a vector $R_{0}+C_{1}$,
similarly the global vector $\boldsymbol{\varepsilon}_{10}$ defined by the
local views $\varepsilon_{v}$ for $v\in V_{10}$ differs from $\boldsymbol{e}$
by a vector $R_{1}+C_{0}$. The two vectors $R_{0}+C_{1}$ and $R_{1}+C_{0}$ do
not a priori coincide, and their sum defines the original mismatch $Z$. The
goal of the decoder is to find a decomposition
$Z=\hat{C}_{0}+\hat{R}_{0}+\hat{C}_{1}+\hat{R}_{1}$ and output
$\hat{\boldsymbol{e}}=\boldsymbol{\varepsilon}_{01}+\hat{R}_{0}+\hat{C}_{1}$.

We will have proved that our decoder works after ensuring two things:

  * –

that it indeed finds a decomposition
$Z=\hat{C}_{0}+\hat{R}_{0}+\hat{C}_{1}+\hat{R}_{1}$,

  * –

that the corresponding $\hat{\boldsymbol{e}}$ is such that
$|\boldsymbol{e}+\hat{\boldsymbol{e}}|=|R_{0}+C_{1}+\hat{R}_{0}+\hat{C}_{1}|<d_{\min}$
where $d_{\min}$ is the minimum distance of the quantum code.

By Proposition 24 and Theorem 26 we have that, for a sufficiently small value
of $\varepsilon$ (namely $\varepsilon<1/10$), the Hamming weight $|\hat{Z}|$
decreases during parallel decoding steps whenever we have
$|S_{0}|\leqslant\frac{\delta}{8\Delta}|V_{0}|$. Furthermore, the Hamming
weight $|\hat{Z}|$ decreases at every sequential decoding step by definition.
Therefore to ensure convergence to some valid output $\hat{\boldsymbol{e}}$ we
only need to ensure that the condition
$|S_{0}|\leqslant\frac{\delta}{8\Delta}|V_{0}|$ is satisfied throughout the
decoding process.

To estimate the number $|S_{0}|$ of active vertices in $V_{0}$, we can simply
upper bound it by $\|\hat{Z}\|$ and track the evolution of $\|\hat{Z}\|$
during the course of the decoding algorithm.

At the initial stage, we have $\hat{Z}=Z$ which is the original mismatch
vector. We note that we will have $r_{v}+c_{v}\neq 0$ only if
$|e_{v}|\geqslant\delta\Delta/2$. Since $Q$ is partitioned into
$Q$-neighbourhoods of vertices of $V_{01}$, we have that the number of
vertices of $V_{01}$ for which $r_{v}+c_{v}\neq 0$ is at most
$2|\boldsymbol{e}|/\delta\Delta$, with the same conclusion holding for
$V_{01}$. Crudely upper bounding the contribution of every such vertex to
$\|Z\|$ by $2\Delta$, we have $\|Z\|\leqslant 8|\boldsymbol{e}|/\delta$.
Strictly speaking, we have upper bounded the number of terms of one possible
expression of $Z$ as a sum of local row and column vectors, but the conclusion
holds anyway since $\|Z\|$ refers to the minimum number of terms of such a
decomposition of $Z$.

Similarly, we remark that $|r_{v}+c_{v}|\leqslant 2|e_{v}|$, from which we
have the upper bound for the Hamming weight of $Z$, $|Z|\leqslant
4|\boldsymbol{e}|$, and also

$|R_{0}+C_{1}|\leqslant 2|\boldsymbol{e}|,$ (7)

for $(R_{0},C_{0},R_{1},C_{1})$ the original decomposition of $Z$.

For any sequential decoding step, we clearly have that the weight
$\|\hat{Z}\|$ is increased by at most $2\Delta$. Since the weight
$\|\hat{Z}\|$ only decreases during a parallel decoding step, we have that
$\|\hat{Z}\|$ stays upper bounded by
$8|\boldsymbol{e}|/\delta+|Z|2\Delta\leqslant
8|\boldsymbol{e}|(\Delta+1/\delta)$ so that the requirement
$|S_{0}|\leqslant\frac{\delta}{8\Delta}|V_{0}|$ is always satisfied whenever

$8|\boldsymbol{e}|(\Delta+\frac{1}{\delta})\leqslant\frac{\delta}{8\Delta}|V_{0}|$

i.e. whenever

$|\boldsymbol{e}|\leqslant\frac{\delta^{2}}{64\Delta(\delta\Delta+1)}|V_{0}|=\frac{\delta^{2}}{32\Delta^{3}(\delta\Delta+1)}|Q|$

since $|Q|=|V_{0}|\Delta^{2}/2$. We have therefore proved that under the
hypothesis of Theorem 2, the decoder always finds a decomposition of $Z$.

Next we evaluate an upper bound on the Hamming weight
$|\hat{R}_{0}+\hat{C}_{1}|$ of the output of the decoder. To this end we upper
bound the increment of $|\hat{R}_{0}+\hat{C}_{1}|$ during sequential decoding,
during all the first parallel decoding steps, and finally during all second
parallel decoding steps.

We note that during a sequential decoding step, the $Q$-neighbourhood of a
single vertex is modified, this vertex being in $V_{00}$ or in $V_{11}$. This
translates either into a modification of $\hat{R}_{0}$ or into a modification
of $\hat{C}_{1}$, which affects at most $\Delta$ rows or $\Delta$ columns.
Therefore a sequential decoding step translates into an augmentation of
$|\hat{R}_{0}+\hat{C}_{1}|$ by at most $\Delta^{2}$. Since the value of
$|\hat{Z}|$ decreases at every step, the total contribution of sequential
decoding does not exceed $|Z|\Delta^{2}\leqslant 4|\boldsymbol{e}|\Delta^{2}$.

During a first parallel decoding step, the only modification to
$|\hat{R}_{0}+\hat{C}_{1}|$ is induced by the parallel decoder’s action on
vertices $v$ of $V_{01}$. We note that the decoder modifies the associated
$Q$-neighbourhood only if it decreases $|\hat{Z}|$ on a subset of $Q(v)$ by at
least $w/2=\Delta^{3/2-\varepsilon}/2$. Since all these sub-$Q$-neighbourhoods
are disjoint, their number is at most $2|\hat{Z}|/\Delta^{3/2-\varepsilon}$
and the total increment of $|\hat{R}_{0}+\hat{C}_{1}|$ during this step is at
most $\Delta^{2}$ times this number of vertices, namely
$2|\hat{Z}|\Delta^{1/2+\varepsilon}$. Now by Proposition 24 and Theorem 26,
the next time a first parallel decoding step occurs the value of $|\hat{Z}|$
will have been divided by at least $\kappa\Delta^{1/2-5\varepsilon}$ for some
constant $\kappa$, therefore the sum of the contributions to
$|\hat{R}_{0}+\hat{C}_{1}|$ of all parallel decoding steps is at most
$4|Z|\Delta^{1/2+\varepsilon}\leqslant
16|\boldsymbol{e}|\Delta^{1/2+\varepsilon}$ by summing the converging
geometric series.

Finally, for the contribution of the second parallel decoding steps, we argue
as before that the increment of $|\hat{R}_{0}+\hat{C}_{1}|$ is at most
$\Delta^{2}$ per vertex on which the decoder takes action. The number of such
vertices is not more than $|S_{0}^{\prime}|+|S_{0}^{\prime\prime}|$,
$|S_{0}^{\prime}|$ being an upper bound on the number of active vertices on
which the decoder may act, and $|S_{0}^{\prime\prime}|$ being an upper bound
on the number of inactive vertices which will become active because the
decoder decides to update them. Applying Theorem 23 and Lemma 25 (which also
holds for $S_{11}^{\prime\prime}$), we have that
$|S_{0}^{\prime}|\leqslant\kappa|S_{0}|/\Delta^{1-4\varepsilon}$ and
$|S_{0}^{\prime\prime}|\leqslant\kappa|S_{0}|/\Delta^{1-4\varepsilon}$ for
some constant $\kappa$. The increment to $|\hat{R}_{0}+\hat{C}_{1}|$ is
therefore at most

$\kappa|S_{0}|\Delta^{1+4\varepsilon}\leqslant\kappa\|\hat{Z}\|\Delta^{1+4\varepsilon}$

for some constant $\kappa$, where $\hat{Z}$ refers to the value just before
the parallel decoding procedure is applied. As stated above, the maximum value
of $\|\hat{Z}\|$ is bounded from above by
$8|\boldsymbol{e}|(\Delta+1/\delta)$. Since every parallel decoding procedure
divides the current value of $\|\hat{Z}\|$ by at least $2$ (by Lemma 27), it
is an easy exercice in combinatorics to see that the sum of all the values of
$\|\hat{Z}\|$ before each parallel decoding procedure cannot exceed
$16|\boldsymbol{e}|(\Delta+1/\delta)$, irrespective of the distribution of the
parallel decoding steps during the whole decoding procedure. We obtain
therefore that total contribution of the second parallel decoding steps is at
most

$\kappa|\boldsymbol{e}|\Delta^{2+4\varepsilon}$

for some constant $\kappa$ and $\Delta$ large enough.

Summarising, the upper bound on the contribution of the second parallel
decoding steps dominates the other terms and we have that the final output of
the decoder is $\hat{R}_{0}+\hat{C}_{1}$ of Hamming weight

$|\hat{R}_{0}+\hat{C}_{1}|\leqslant\kappa|\boldsymbol{e}|\Delta^{2+4\varepsilon}$

for some constant $\kappa$. From (7) we therefore obtain

$|\boldsymbol{e}+\hat{\boldsymbol{e}}|=|R_{0}+C_{1}+\hat{R}_{0}+\hat{C}_{1}|\leqslant|R_{0}+C_{1}|+|\hat{R}_{0}+\hat{C}_{1}|\leqslant
c|\boldsymbol{e}|\Delta^{2+4\varepsilon}$

for some constant $\kappa$. Applying the lower bound on $d_{\min}$ from
Theorem 1 we obtain that $|\boldsymbol{e}+\hat{\boldsymbol{e}}|<d_{\min}$
which concludes the proof. ∎

##  7 Link with the Lifted Product codes

In this section, we briefly recall the construction of the lifted product
codes introduced by Panteleev and Kalachev [PK21a] and explain how quantum
Tanner codes can be obtained from lifted product codes, or more generally from
hypergraph product codes. Finally, we show that the decoder we studied in the
previous sections immediately gives an efficient decoder for lifted product
codes.

###  7.1 Construction of the Lifted Product codes

Take a group $G$ and two symmetric subsets $A=\\{a_{i}\\}\subset G$,
$B=\\{b_{i}\\}\subset G$ of size $\Delta$. Let $h_{A}$ and $h_{B}$ be two
parity-check matrices on $\mathbb{F}_{2}\subset\mathbb{F}_{2}[G]$ of size
$m\times\Delta$. We further define two diagonal matrices of size $\Delta$ over
$G$:

$D_{A}:=\mathrm{diag}(a_{1},\ldots,a_{\Delta}),\qquad
D_{B}:=\mathrm{diag}(b_{1},\ldots,b_{\Delta})$

and set $H_{A}:=h_{A}D_{A}$ and $H_{B}:=h_{B}D_{B}$.

Consider the graph with two vertices and $\Delta$ parallel edges, and define
two Tanner codes $T_{A}$ and $T_{B}$ on this graph, where the local
constraints on both vertices are given by the codes $\ker h_{A}$ and $\ker
h_{B}$, respectively. The corresponding Tanner graphs have vertex sets
$A\cup(C_{0}\cup C_{1})$ for $T_{A}$ and $B\cup(D_{0}\cup D_{1})$ for $T_{B}$.
In particular, we have $|C_{0}|=|C_{1}|=|D_{0}|=|D_{1}|=m$.

The lifted product codes of [PK21a] are defined on qubits indexed by ($|G|$
copies of) $A\times B\cup(C_{0}\cup C_{1})\times(D_{0}\cup D_{1})$, and have
$\sigma_{X}$-generators indexed by ($|G|$ copies of) $A\times(D_{0}\cup
D_{1})$, and $\sigma_{Z}$-generators by ($|G|$ copies of) $(C_{0}\cup
C_{1})\times B$. We will use the following identification between
$\mathbb{F}_{2}^{G}$ and the group algebra $\mathbb{F}_{2}[G]$:

$(x_{g})_{g\in G}\quad\leftrightarrow\quad\sum_{g\in G}x_{g}g$

where $x_{g}\in\mathbb{F}_{2}$. This allows us to describe a subset of
$A\times B\times G$, e.g. the support of a stabilizer, as a matrix in
$\mathbb{F}_{2}[G]^{A\times B}$.

A relatively simple way of describing the lifted product codes is _via_ their
stabilizer elements. For instance, a general $\sigma_{Z}$-stabilizer is
associated with two matrices $(U_{0},U_{1})$ with entries indexed by
$C_{0}\times B$ and $C_{1}\times B$, and values in $\mathbb{F}_{2}[G]$. The
corresponding operator is a product of $\sigma_{Z}$-Pauli matrices with a
support given by

$\underbrace{h_{A}^{T}U_{0}+H_{A}^{T}U_{1}}_{A\times
B}+\underbrace{U_{0}h_{B}^{T}}_{C_{0}\times
D_{0}}+\underbrace{U_{0}H_{B}^{T}}_{C_{0}\times
D_{1}}+\underbrace{U_{1}h_{B}^{T}}_{C_{1}\times
D_{0}}+\underbrace{U_{1}H_{B}^{T}}_{C_{1}\times D_{1}}.$

We leave the factor $G$ implicit for ease for notation, and represent the
support of a set by its indicator vector. Similarly, a general
$\sigma_{X}$-stabilizer element $(V_{0},V_{1})$ has support

$\underbrace{V_{0}h_{B}+V_{1}H_{B}}_{A\times
B}+\underbrace{h_{A}V_{0}}_{C_{0}\times
D_{0}}+\underbrace{H_{A}V_{0}}_{C_{1}\times
D_{0}}+\underbrace{h_{A}V_{1}}_{C_{0}\times
D_{1}}+\underbrace{H_{A}V_{1}}_{C_{1}\times D_{1}}.$

A generator of the code is obtained by taking $(U_{0},U_{1})$, or
$(V_{0},V_{1})$, of Hamming weight equal to 1. The generators of the lifted
product codes have weight at most $2\Delta$.

###  7.2 Quantum Tanner codes from Lifted Product codes

Let us define matrices $g_{A}$ indexed by $C^{\prime}\times A$ and $g_{B}$ by
$D^{\prime}\times B$ to be the parity-check matrices of $(\ker h_{A})^{\perp}$
and $(\ker h_{B})^{\perp}$. Note that $|C^{\prime}|=|D^{\prime}|=\Delta-m$ and
that

$g_{A}h_{A}^{T}=0,\quad g_{B}h_{B}^{T}=0.$

We further define $G_{A}:=g_{A}D_{A}^{-1}$ and $G_{B}:=g_{B}D_{B}^{-1}$ that
satisfy $G_{A}H_{A}^{T}=0$ and $G_{B}H_{B}^{T}=0$.

The quantum Tanner code is nothing but the code with $\sigma_{Z}$-stabilizers
$(U_{0}^{\prime},U_{1}^{\prime})\in\mathbb{F}_{2}[G]^{(C_{0}\cup C_{1})\times
D^{\prime}}$ and $\sigma_{X}$-stabilizers
$(V_{0}^{\prime},V_{1}^{\prime})\in\mathbb{F}_{2}[G]^{(C^{\prime}\times(D_{0}\cup
D_{1})}$ corresponding to the stabilizers
$(U_{0},U_{1}):=(U_{0}^{\prime}G_{B},U_{1}^{\prime}g_{b})$ and
$(V_{0},V_{1}):=(g_{A}^{T}V_{0}^{\prime},G_{A}^{T}V_{1}^{\prime})$ of the
Lifted Product code. They take the following form:

$\displaystyle\sigma_{Z}-\text{stabilizer}\;(U_{0}^{\prime},U_{1}^{\prime})$
$\displaystyle:\quad\underbrace{h_{A}^{T}U_{0}^{\prime}G_{B}+H_{A}^{T}U_{1}^{\prime}g_{b}}_{A\times
B}+\underbrace{U_{0}^{\prime}G_{B}h_{B}^{T}}_{C_{0}\times
D_{0}}+\underbrace{U_{0}^{\prime}G_{B}H_{B}^{T}}_{C_{0}\times
D_{1}}+\underbrace{U_{1}^{\prime}g_{B}h_{B}^{T}}_{C_{1}\times
D_{0}}+\underbrace{U_{1}^{\prime}g_{b}H_{B}^{T}}_{C_{1}\times D_{1}}$
$\displaystyle\quad=\underbrace{h_{A}^{T}U_{0}^{\prime}G_{B}+H_{A}^{T}U_{1}^{\prime}g_{b}}_{A\times
B}+\underbrace{U_{0}^{\prime}G_{B}h_{B}^{T}}_{C_{0}\times
D_{0}}+\underbrace{U_{1}^{\prime}g_{b}H_{B}^{T}}_{C_{1}\times D_{1}},$
$\displaystyle\sigma_{X}-\text{stabilizer}\;(V_{0}^{\prime},V_{1}^{\prime})$
$\displaystyle:\quad\underbrace{g_{A}^{T}V_{0}^{\prime}h_{B}+G_{A}^{T}V_{1}^{\prime}H_{B}}_{A\times
B}+\underbrace{h_{A}g_{A}^{T}V_{0}^{\prime}}_{C_{0}\times
D_{0}}+\underbrace{H_{A}g_{A}^{T}V_{0}^{\prime}}_{C_{1}\times
D_{0}}+\underbrace{h_{A}G_{A}^{T}V_{1}^{\prime}}_{C_{0}\times
D_{1}}+\underbrace{H_{A}G_{A}^{T}V_{1}^{\prime}}_{C_{1}\times D_{1}}$
$\displaystyle\quad=\underbrace{g_{A}^{T}V_{0}^{\prime}h_{B}+G_{A}^{T}V_{1}^{\prime}H_{B}}_{A\times
B}+\underbrace{H_{A}g_{A}^{T}V_{0}^{\prime}}_{C_{1}\times
D_{0}}+\underbrace{h_{A}G_{A}^{T}V_{1}^{\prime}}_{C_{0}\times D_{1}}.$

We immediately notice that the supports of the $\sigma_{X}$-stabilizers and
the $\sigma_{Z}$-stabilizers only overlap on $A\times B$. In particular, we
can simply discard all the qubits in $(C_{0}\cup C_{1})\times(D_{0}\cup
D_{1})$ and define a shorter stabilizer code on $A\times B$ with the
stabilizers corresponding to $(U_{0}^{\prime},U_{1}^{\prime})$ and
$(V_{0}^{\prime},V_{1}^{\prime})$. This is nothing but the quantum Tanner code
$Q=(\mathcal{C}_{0},\mathcal{C}_{1})$ with local tensor codes $C_{A}\otimes
C_{B}$ and $C_{A}^{\perp}\times C_{B}^{\perp}$ where we define

$C_{A}=\ker g_{A},\quad C_{B}=\ker h_{B},\quad C_{A}^{\perp}=\ker h_{A},\quad
C_{B}^{\perp}=\ker g_{B}.$

###  7.3 Decoding Lifted Product codes

An error vector $\boldsymbol{e}=(\boldsymbol{e}^{X},\boldsymbol{e}^{Z})$ for
the lifted product code is described a $\sigma_{X}$-type error
$\boldsymbol{e}^{X}$ and a $\sigma_{Z}$-type error $\boldsymbol{e}^{Z}$:

$\boldsymbol{e}^{X/Z}=\boldsymbol{e}^{X/Z}_{AB}+\boldsymbol{e}^{X/Z}_{00}+\boldsymbol{e}^{X/Z}_{01}+\boldsymbol{e}^{X/Z}_{10}+\boldsymbol{e}^{X/Z}_{11}$

with $\boldsymbol{e}^{X/Z}_{AB}\in\mathbb{F}_{2}[G]^{A\times B}$ and
$\boldsymbol{e}^{X/Z}_{ij}\in\mathbb{F}_{2}[G]^{C_{j}\times D_{i}}$. This
error gives rise to a syndrome $(S_{0},S_{1},T_{0},T_{1})$ with
$(S_{0},S_{1})$ detected by $\sigma_{Z}$-generators and $(T_{0},T_{1})$
detected by $\sigma_{X}$-generators, as follows:

$\displaystyle S_{0}$
$\displaystyle=h_{A}\boldsymbol{e}^{Z}_{AB}+\boldsymbol{e}^{Z}_{00}h_{B}+\boldsymbol{e}^{Z}_{10}H_{B}\quad\in\mathbb{F}_{2}[G]^{C_{0}\times
B},$ $\displaystyle S_{1}$
$\displaystyle=H_{A}\boldsymbol{e}^{Z}_{AB}+\boldsymbol{e}^{Z}_{01}h_{B}+\boldsymbol{e}^{Z}_{11}H_{B}\quad\in\mathbb{F}_{2}[G]^{C_{1}\times
B},$ $\displaystyle T_{0}$
$\displaystyle=\boldsymbol{e}^{X}_{AB}h_{B}^{T}+h_{A}^{T}\boldsymbol{e}^{X}_{00}+H_{A}^{T}\boldsymbol{e}^{X}_{01}\quad\in\mathbb{F}_{2}[G]^{A\times
D_{0}},$ $\displaystyle T_{1}$
$\displaystyle=\boldsymbol{e}^{X}_{AB}H_{B}^{T}+h_{A}^{T}\boldsymbol{e}^{X}_{10}+H_{A}^{T}\boldsymbol{e}^{X}_{11}\quad\in\mathbb{F}_{2}[G]^{A\times
D_{1}}.$

One of the features of this quantum code (and also of the hypergraph product
code of two classical Tanner codes) is that one can easily remove the error
from $C_{0}\times D_{1}\cup C_{1}\times D_{0}$ by adding a stabilizer of