††thanks: Institute for Quantum Information and Matter, California Institute
of Technology, Pasadena, CA, USA††thanks: Center for Theoretical Physics,
Massachusetts Institute of Technology, Cambridge, MA, USA††thanks: School of
Computation, Information and Technology, Technical University of Munich &
Munich Center for Quantum Science and Technology, Munich, Germany††thanks:
School of Computation, Information and Technology, Technical University of
Munich & Munich Center for Quantum Science and Technology, Munich,
Germany††thanks: Department of Mathematics, Massachusetts Institute of
Technology, Cambridge, MA, USA††thanks: AWS Center for Quantum Computing &
California Institute of Technology, Pasadena, CA, USA

# Single-shot decoding of good quantum LDPC codes

Shouzhen Gu  Eugene Tang  Libor Caha
Shin Ho Choe  Zhiyang He (Sunny)  Aleksander Kubica

###### Abstract

Quantum Tanner codes constitute a family of quantum low-density parity-check
(LDPC) codes with good parameters, i.e., constant encoding rate and relative
distance. In this article, we prove that quantum Tanner codes also facilitate
single-shot quantum error correction (QEC) of adversarial noise, where one
measurement round (consisting of constant-weight parity checks) suffices to
perform reliable QEC even in the presence of measurement errors. We establish
this result for both the sequential and parallel decoding algorithms
introduced by Leverrier and Zémor. Furthermore, we show that in order to
suppress errors over multiple repeated rounds of QEC, it suffices to run the
parallel decoding algorithm for constant time in each round. Combined with
good code parameters, the resulting constant-time overhead of QEC and
robustness to (possibly time-correlated) adversarial noise make quantum Tanner
codes alluring from the perspective of quantum fault-tolerant protocols.

##  1 Introduction

Quantum error correcting (QEC) codes [1, 2] are the backbone of quantum fault-
tolerant protocols needed to reliably operate scalable quantum computers. Due
to their simplicity, stabilizer codes [3], which can be realized by measuring
a set of commuting Pauli operators known as parity checks, have received much
attention. From the perspective of fault tolerance, it might be desirable to
further require that qubits are placed on some lattice and to restrict parity
checks to be constant-weight and geometrically local. However, such
topological QEC codes, which include the toric code [4, 5] and the color code
[6, 7, 8] as examples, have limited code parameters [9, 10, 11]. To avoid
these limitations, one can drop the assumption about geometric locality of
parity checks (while still maintaining the assumption about their constant
weight) to obtain a more general family of QEC codes known as quantum low-
density parity-check (QLDPC) codes; see Ref. [12] for a recent review.
Importantly, QLDPC codes can have essentially optimal parameters, as shown by
recent breakthrough results [13, 14, 15, 16], culminating in the construction
of (asymptotically) good QLDPC codes whose encoding rates and relative
distances are constant [17]. A key component of the construction of
asymptotically good QLDPC codes is the presence of “product-expanding” local
codes. Since then, a few alternative constructions of good QLDPC codes have
been proposed [18, 19].

Good parameters alone are not enough for QEC codes to be interesting beyond
the theoretical realm. In order to be practically relevant and useful, QEC
codes need computationally efficient decoding algorithms which process the
error syndrome and identify errors afflicting the encoded information.
Importantly, decoding algorithms need to operate at least at the speed at
which quantum fault-tolerant protocols are being implemented; otherwise, the
error syndrome will keep accumulating and one will suffer from the so-called
backlog problem [20]. Recently, a few computationally efficient (and provably
correct) decoding algorithms have been developed for good QLDPC codes [21, 22,
19], assuming access to the noiseless error syndrome.

To extract the error syndrome, one usually implements appropriate quantum
circuits composed of basic quantum operations, such as state preparation,
entangling gates and measurements. Unfortunately, these basic operations are
imperfect and, for that reason, the assumption about the noiseless error
syndrome is unrealistic. In particular, practical QEC codes and decoding
algorithms should exhibit robustness to measurement errors. Arguably, one of
the simplest ways to achieve such robustness involves repeating measurements
until a reliable account of the error syndrome is obtained [23, 5]. However,
this approach incurs significant time overhead since the number of repetitions
needed in general grows with the code distance.

An alternative to repeated measurement rounds of the error syndrome was
introduced in the form of single-shot QEC by Bombín [24]. The basic idea
behind single-shot QEC is to carefully select a code for which the decoding
problem has sufficient structure to reliably infer qubit errors even with
imperfect syndrome measurements. The strength of this approach is that
significantly fewer measurements are necessary for codes that admit single-
shot decoding compared to the simple strategy of repeated measurements.

Single-shot QEC can be considered either for stochastic or adversarial noise.
In the stochastic case, one is interested in noise that afflicts a (randomly
selected) constant fraction of qubits. Additional structure may be needed for
both the noise and the code, since the expected weight of the errors can be
far beyond the code distance. Examples of such structure include sufficiently
high expansion in the associated factor graphs, e.g., quantum expander codes
[25]; or the presence of geometrically local redundancies among constant-
weight parity checks, e.g., the 3D subsystem toric code [26, 27] and the gauge
color code [28]. In the adversarial case, as considered by Campbell [29], one
can realize single-shot QEC for any code by measuring a carefully chosen set
of parity checks; similar ideas of exploiting a redundant set of parity checks
to simultaneously handle measurement and qubit errors were also explored in
Refs. [30, 31, 32]. The limitation of this approach is that, even when
starting with a QLDPC code, the parity checks needed for single-shot QEC may
have weight growing with code length, which makes it less appealing from the
perspective of quantum fault-tolerant protocols.

We remark that while stochastic noise and adversarial noise models are
generally incomparable, the distinction fades for asymptotically good QEC
codes. Since these codes, by definition, have constant relative distance, they
have the ability to correct arbitrary errors of weight up to a constant
fraction of the number of qubits. In particular, stochastic noise with
sufficiently low rate is correctable with high probability. Since in the rest
of the paper we focus on good QLDPC codes, it suffices to consider the case of
adversarial noise.

###  1.1 Main Results

In this article, we focus on a class of asymptotically good QLDPC codes called
quantum Tanner codes [18]. They admit computationally efficient decoding
algorithms, such as the sequential and parallel mismatch decomposition
algorithms introduced in Ref. [33] and the potential-based decoder introduced
in Ref. [22]. The problem of decoding quantum Tanner codes has so far been
considered only in the scenario with noiseless error syndrome. Here, we study
the performance of the aforementioned sequential and parallel mismatch
decomposition decoders in the presence of measurement errors. We show that the
decoders are _single-shot_ , under the following definition. For a more
detailed discussion of single-shot decoding, see Section 3.

Suppose a data error $e$ occurs on the qubits. Let $\sigma$ be the (ideal)
syndrome corresponding to the data error. Suppose that the measured syndrome
is corrupted by measurement error $D$. With access to the noisy syndrome
$\tilde{\sigma}=\sigma+D$ as input, the decoder tries to output a correction
$\hat{f}$ close to the data error.

######  Definition 1.1 (Informal Statement of Definition 3.3).

A decoder is said to be $(\alpha,\beta)$-single-shot if, for sufficiently low-
weight errors, the correction $\hat{f}$ returned on input $\tilde{\sigma}$
satisfies $|e+\hat{f}|_{R}\leq\alpha|e|_{R}+\beta|D|$, where $|e|_{R}$ is the
stabilizer-reduced weight of $e$, i.e., the weight of the smallest error
equivalent to $e$ up to the addition of stabilizers.

In other words, using a single round of noisy syndrome measurement, the
decoder finds and applies the correction $\hat{f}$, resulting in the residual
error $e+\hat{f}$ of weight below $\alpha|e|_{R}+\beta|D|$. Let $n$ be the
number of physical qubits of the quantum Tanner code. Our main theorems are as
follows.

######  Theorem 1.2 (Informal Statement of Theorem 4.17).

There exists a constant $\beta$ such that the sequential decoder (Algorithm 1)
is $(\alpha=0,\beta)$-single-shot.

######  Theorem 1.3 (Informal Statement of Theorem 4.20).

There exists a constant $\beta$ such that for all $\alpha>0$, the
$O(\log(1/\alpha))$-iteration parallel decoder (Algorithm 3) is
$(\alpha,\beta)$-single-shot. In particular, for $O(\log n)$ iterations of
parallel decoding one obtains $\alpha=0$.

We further consider the situation where multiple rounds of qubit error, noisy
syndrome measurement, and decoding occur. We show that under mild assumptions
on the weights of qubit and measurement errors, repeated applications of an
$(\alpha,\beta)$-single-shot decoder will keep the residual error weight
bounded. Specifically, consider the case where an initial error
$(e_{1},D_{1})$ is partially corrected by the decoder, leaving a residual
error $e_{1}^{\prime}$. A new error $(e_{2},D_{2})$ is then applied on top of
the existing residual error, giving total error
$(e_{1}^{\prime}+e_{2},D_{2})$. The decoder attempts to correct using a new
round of syndrome measurements (without using the syndromes of previous
rounds), leaving residue $e_{2}^{\prime}$. This process is repeated for
multiple rounds. Then we have the following.

######  Theorem 1.4 (Informal Statement of Theorem 3.5).

Consider an $(\alpha,\beta)$-single-shot decoder and multiple rounds of errors
$(e_{i},D_{i})$ for $i=1,\cdots,M$. For any $c>0$, there exists a constant
$C_{*}>0$ such that if $\max(|e_{i}|,|D_{i}|)\leq C_{*}n$ for all $i$, then
the final residual error $e_{M}^{\prime}$ satisfies $|e_{M}^{\prime}|_{R}\leq
cn$.

A direct implication of this result is that for the parallel decoder
(Algorithm 3), a constant number of iterations suffices to keep the residual
error weight bounded at each round. This process can be repeated essentially
indefinitely until ideal error correction is required, at which point the
$O(\log n)$-iteration parallel decoder can be used. For more details, see the
discussion at the end of Section 3.3.

The rest of this paper is organized as follows. In Section 2, we provide the
necessary background on quantum Tanner codes. For more detailed explanations,
see Refs. [18] and [33]. In Section 3, we describe the decoding problem for
quantum (CSS) codes under measurement noise, and discuss the notion of single-
shot decoding. We then define $(\alpha,\beta)$-single-shot decoding and derive
general consequences of this definition under multiple rounds of error and
decoding. The main result of this section is the proof of Theorem 3.5. Section
4 forms the bulk of the paper. There, we review the sequential and parallel
decoders from Ref. [33] and prove that the decoders are single-shot in
Theorems 4.17 and 4.20. Finally, we end with some discussions in Section 5.

##  2 Quantum Tanner Codes

###  2.1 Classical codes

A classical binary linear code is a subspace $C\subseteq\mathbb{F}_{2}^{n}$.
We refer to $n$ as the block length of the code. The number of encoded bits
(also referred to as the code dimension) is given by $k=\dim C$ and the rate
of the code is $R=k/n$. The distance of $C$ is defined as $d=\min_{x\in
C\setminus\\{0\\}}|x|$, where $|\cdot|$ is the Hamming weight of a vector and
where $0$ denotes the zero vector. A code with distance $d$ can protect
against any unknown error of weight less than $d/2$. Often, it is useful to
specify a code $C$ via a parity check matrix $H$. By definition, $C=\ker H$.

The dual code of a code $C$ is defined as
$C^{\perp}=\\{x\in\mathbb{F}_{2}^{n}:\langle x,y\rangle=0\ \forall y\in C\\}$.
The tensor product code of two codes
$C_{A}\subseteq\mathbb{F}_{2}^{A},C_{B}\subseteq\mathbb{F}_{2}^{B}$ is
$C_{A}\otimes C_{B}\subseteq\mathbb{F}_{2}^{A\times B}$, where the codewords
can be thought of as matrices such that every column is a codeword of $C_{A}$
and every row is a codeword of $C_{B}$. The dual tensor code of $C_{A}$ and
$C_{B}$, denoted by $C_{A}\boxplus C_{B}$, is defined as

$C_{A}\boxplus C_{B}\equiv\left(C_{A}^{\perp}\otimes
C_{B}^{\perp}\right)^{\perp}=C_{A}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes
C_{B}\subseteq\mathbb{F}_{2}^{A\times B}.$

A parity check matrix for $C_{A}\boxplus C_{B}$ is $H_{A}\otimes H_{B}$, where
$H_{A}$ and $H_{B}$ are the parity check matrices of $C_{A}$ and $C_{B}$,
respectively.

The dual tensor codes we use are required to satisfy the following robustness
condition.

######  Definition 2.1.

The code $C_{A}\boxplus C_{B}$ is said to be $\kappa$-product-expanding if any
$x\in C_{A}\boxplus C_{B}$ can be expressed as $c+r$, with $c\in
C_{A}\otimes\mathbb{F}_{2}^{B}$ and $r\in\mathbb{F}_{2}^{A}\otimes C_{B}$ such
that

$\kappa\left(\frac{1}{|A|}\|c\|_{A}+\frac{1}{|B|}\|r\|_{B}\right)\leq\frac{1}{|A||B|}|x|\,.$
(1)

Here, $\|c\|_{A}$ denotes the number of non-zero columns in $c$ and
$\|r\|_{B}$ denotes the number of non-zero rows in $r$. When it is clear from
context, we will drop the subscripts on the norms. The notion of product-
expansion was introduced by Panteleev and Kalachev [17]. It is equivalent to
robust testability of tensor product codes [34] and agreement testability
[35], and also implies another notion called $w$-robustness of dual tensor
codes [18]. It has been proven that random codes are product-expanding with
high probability [36, 19].

######  Theorem 2.2 (Theorem 1 in Ref. [36]).

Let $\rho\in(0,1)$. For any $\Delta$, let $C_{A}$ be a random code of
dimension $\lceil\rho\Delta\rceil$ and $C_{B}$ be a random code of dimension
$\lceil(1-\rho)\Delta\rceil$. There exists a constant $\kappa$ such that both
$C_{A}\boxplus C_{B}$ and $C_{A}^{\perp}\boxplus C_{B}^{\perp}$ are
$\kappa$-product-expanding with probability approaching 1 as
$\Delta\to\infty$.

###  2.2 Quantum codes

An $n$-qubit quantum code is a subspace $\mathcal{C}$ of an $n$-qubit Hilbert
space, i.e., $\mathcal{C}\subseteq\left(\mathbb{C}^{2}\right)^{\otimes n}$. We
are interested in stabilizer codes, which are codes that can be expressed as
the simultaneous $+1$-eigenspace of an abelian subgroup $\mathcal{S}$ of the
$n$-qubit Pauli group satisfying $-I\not\in\mathcal{S}$. If $\mathcal{S}$ can
be generated by two sets $\mathcal{S}_{X}$ and $\mathcal{S}_{Z}$ comprising,
respectively, Pauli $X$-type and $Z$-type operators, then we refer to the
corresponding stabilizer code as a Calderbank-Shor-Steane (CSS) code [37, 38].
By ignoring the phase factors for such $X$-type and $Z$-type operators, we can
identify them with their supports as vectors in $\mathbb{F}_{2}^{n}$.

For any CSS code stabilized by
$\mathcal{S}=\langle\mathcal{S}_{X},\mathcal{S}_{Z}\rangle$, we can define two
$n$-bit classical codes $C_{X}=\ker H_{X}$ and $C_{Z}=\ker H_{Z}$, where each
row in $H_{X}$ and $H_{Z}$ is the support of a stabilizer generator in
$\mathcal{S}_{X}$ and $\mathcal{S}_{Z}$, respectively. The dimension of a CSS
code is $k=k_{X}+k_{Z}-n$, where $k_{X}$ and $k_{Z}$ are the dimensions of
$C_{X}$ and $C_{Z}$, respectively. The distance is $d=\min(d_{X},d_{Z})$,
where $d_{X}=\min_{x\in C_{Z}\setminus C_{X}^{\perp}}|x|$ and
$d_{Z}=\min_{x\in C_{X}\setminus C_{Z}^{\perp}}|x|$. A quantum code of
distance $d$ can protect against any unknown error of weight less than $d/2$.
A quantum code $\mathcal{C}\subseteq(\mathbb{C}^{2})^{\otimes n}$ of dimension
$k$ and distance $d$ is said to be an $[[n,k,d]]$ code. A family of CSS codes
is said to be low-density parity-check (LDPC) if $H_{X}$ and $H_{Z}$ are
sparse, i.e., have at most a constant number of non-zero entries in every
column and row.

###  2.3 Quantum Tanner code construction

We now describe the construction of quantum Tanner codes. The code is placed
on a geometric object called the left-right Cayley complex. Let $G$ be a
finite group and $A=A^{-1},B=B^{-1}$ be two symmetric generating sets of $G$.
The left-right Cayley complex $\operatorname{Cay}_{2}(A,G,B)$ is a two-
dimensional object with vertices $V$, edges $E$, and faces $Q$ defined as
follows:

  * •

$V=V_{00}\sqcup V_{01}\sqcup V_{10}\sqcup V_{11}$, where
$V_{ij}=G\times\\{(i,j)\\}$ for $i,j\in\\{0,1\\}$ ,

  * •

$E=E_{A}\sqcup E_{B}$, where $E_{A}=\\{\\{(g,i0),(ag,i1)\\}:g\in G,a\in
A,i\in\\{0,1\\}\\}$ and $E_{B}=\\{\\{(g,0j),(gb,1j)\\}:g\in G,b\in
B,j\in\\{0,1\\}\\}$ ,

  * •

$Q=\\{\\{(g,00),(ag,01),(gb,10),(agb,11)\\}:g\in G,a\in A,b\in B\\}$ .

Let $Q(v)$ denote the set of faces incident to a given vertex $v$. Each face
incident to $v$ can be obtained by choosing an $A$-type edge and a $B$-type
edge incident to $v$ and completing them into a square. Therefore, $Q(v)$ is
in bijection with the set $A\times B$, and can be thought of as a matrix with
rows indexed by $A$ and columns indexed by $B$ (Figure 1). Similarly, the set
of faces incident to a given $A$-edge is in bijection with $B$ and the set of
faces incident to a given $B$-edge is in bijection with $A$.

Figure 1: The local structure of the left-right Cayley complex around a vertex
labelled by $g\in G$. The incident faces $Q(v)$ has a natural bijection with
$A\times B$. As examples, the red and blue faces in the complex are mapped to
the squares of the same colors in the matrix given by $A\times B$.

Consider the usual Cayley graph $\operatorname{Cay}(A,G)$ with the vertex set
$G$ and the edge set $\\{\\{g,ag\\}:g\in G,a\in A\\}$. Ignoring the $B$ edges
from the complex, we have that $(V,E_{A})$ is the disjoint union of two copies
of the bipartite cover of $\operatorname{Cay}(A,G)$. Similarly, $(V,E_{B})$ is
the disjoint union of two copies of the bipartite cover of
$\operatorname{Cay}(G,B)$.111We denote the Cayley graph with left group action
by $\operatorname{Cay}(A,G)$ and the Cayley graph with right group action by
$\operatorname{Cay}(G,B)$. Note that the right Cayley graph
$\operatorname{Cay}(G,B)$ with edges $\\{g,gb\\}$ is isomorphic to the left
Cayley graph $\operatorname{Cay}(B,G)$ by mapping every $g$ to $g^{-1}$. We
say that a $\Delta$-regular graph is Ramanujan if the second largest
eigenvalue of its adjacency matrix is at most $2\sqrt{\Delta-1}$, and we will
consider left-right Cayley complexes with component Cayley graphs
$\operatorname{Cay}(A,G)$ and $\operatorname{Cay}(G,B)$ that are Ramanujan.
Explicitly, Ramanujan Cayley graphs can be obtained by taking
$G=\operatorname{PSL}_{2}(q^{i})$, where $q$ is an odd prime power and $A,B$
are (appropriately chosen) symmetric generating sets of constant size
$\Delta=|A|=|B|=q+1$ [35].

Quantum Tanner codes are CSS codes defined by placing qubits on the faces of a
left-right Cayley complex. We fix two classical codes, $C_{A}$ of length $|A|$
and $C_{B}$ of length $|B|$, which are used to define a pair of local codes
providing the parity checks of the quantum code. An $X$-type stabilizer
generator is defined as a codeword from a generating set of
$C_{0}=C_{A}\otimes C_{B}$, with support on the faces incident to a given
vertex in $V_{0}=V_{00}\cup V_{11}$. More precisely, there is an $X$-type
stabilizer generator $s(x,v)$ for every generator $x\in C_{A}\otimes C_{B}$
and every vertex $v\in V_{0}$. Identifying $Q(v)$ with $A\times B$ using the
bijection explained earlier, the support of $s(x,v)$ is the subset of $Q(v)$
defined by the support of $x$; see Figure 2 for an illustration. Similarly,
the $Z$-type stabilizers are generated by codewords of
$C_{1}=C_{A}^{\perp}\otimes C_{B}^{\perp}$ on the faces incident to vertices
of $V_{1}=V_{01}\cup V_{10}$. The fact that $X$ and $Z$ parity checks commute
is because $X$ and $Z$ generators are either disjoint or overlap on the faces
incident to a single edge. On this set of faces, isomorphic to either $B$ or
$A$, the supports of the $X$ and $Z$ operators are codewords of either $C_{B}$
and $C_{B}^{\perp}$, respectively, or $C_{A}$ and $C_{A}^{\perp}$,
respectively. It is clear that a family of quantum Tanner codes is QLDPC if
the degrees of the component Cayley graphs are bounded.

Figure 2: An example of a stabilizer generator with local codes
$C_{A}=\operatorname{span}\\{111\\}$ and
$C_{B}=\operatorname{span}\\{110,011\\}$. The codeword $x=111\otimes 110\in
C_{A}\otimes C_{B}$ has support as shown on the right. Identifying that matrix
with the faces incident to a $V_{0}$ vertex gives an $X$-type stabilizer
generator.

Leverrier and Zémor showed that quantum Tanner codes defined on expanding
left-right Cayley complexes using product-expanding local codes have good
parameters [18, 33].

######  Theorem 2.3 (Theorem 1 in Ref. [33]).

Let $\rho,d_{r},\kappa\in(0,1)$ and $\Delta$ be a sufficiently large constant.
Let $C_{A},C_{B}\subseteq\mathbb{F}_{2}^{\Delta}$ be classical codes of rates
$\rho$ and $(1-\rho)$ respectively, such that the distances of
$C_{A},C_{B},C_{A}^{\perp},C_{B}^{\perp}$ are all at least $d_{r}\Delta$, and
such that $C_{A}\boxplus C_{B}$ and $C_{A}^{\perp}\boxplus C_{B}^{\perp}$ are
both $\kappa$-product-expanding. Using a family of $\Delta$-regular Ramanujan
Cayley graphs $\operatorname{Cay}(A,G)$ and $\operatorname{Cay}(G,B)$, define
the left-right Cayley complex $\operatorname{Cay}_{2}(A,G,B)$. Then the
quantum Tanner codes defined using the components above have parameters

$\left[\\!\left[n,k\geq(1-2\rho)^{2}n,d\geq\frac{d_{r}^{2}\kappa^{2}}{256\Delta}n\right]\\!\right]\,.$
(2)

##  3 Single-shot Decoding

###  3.1 Decoding CSS codes

Let us now formally define the decoding problem for quantum (CSS) codes. After
we encode logical information in a quantum code, errors will occur on the
physical system. We are interested in how to “undo” these errors and,
subsequently, recover the original logical state. Specifically, consider a
logical state $|\psi\rangle$ of a stabilizer code $\mathcal{C}$. A Pauli error
$E$ occurs, and we gain information about the error by measuring a set of
stabilizer generators $\\{S_{i}\\}$. This gives a syndrome $\sigma$, a bit
string whose values $\sigma_{i}$ correspond to the eigenvalues
$(-1)^{\sigma_{i}}$ of the stabilizers measured. Thus, $\sigma_{i}=0$ whenever
$S_{i}$ commutes with $E$ and $\sigma_{i}=1$ when it anticommutes. The task of
decoding is to use $\sigma$ to determine a correction $\hat{F}$ such that
$\hat{F}E|\psi\rangle=|\psi\rangle$. In other words, $\hat{F}E$ should be a
stabilizer of the code. When $\mathcal{C}$ is a CSS code, we can express the
problem as follows.

######  Definition 3.1.

Let $\mathcal{C}$ be a CSS code specified by two parity check matrices
$H_{X}\in\mathbb{F}_{2}^{r_{X}\times n}$ and
$H_{Z}\in\mathbb{F}_{2}^{r_{Z}\times n}$. Let
$e=(e_{X},e_{Z})\in\mathbb{F}_{2}^{2n}$ be an error with corresponding
syndrome $\sigma=(\sigma_{X},\sigma_{Z})\in\mathbb{F}_{2}^{r_{Z}+r_{X}}$,
where $\sigma_{Z}=H_{X}e_{Z}$ and $\sigma_{X}=H_{Z}e_{X}$. Given input
$\sigma$, the task of decoding is to find corrections
$\hat{f}=(\hat{f}_{X},\hat{f}_{Z})\in\mathbb{F}_{2}^{2n}$ such that
$e_{X}+\hat{f}_{X}\in C_{X}^{\perp}$ and $e_{Z}+\hat{f}_{Z}\in C_{Z}^{\perp}$.

In the definition above, we associate the bit string $e=(e_{X},e_{Z})$ with
the Pauli errors $E=E_{X}E_{Z}$ where $E_{X}$ and $E_{Z}$ are Pauli $X$ and
$Z$ operators with support $e_{X}$ and $e_{Z}$, respectively (ignoring phase
information). The correction $\hat{f}$ is similarly associated with a Pauli
operator $\hat{F}$.

We note that for CSS codes, the decoding problem can be split into two
separate problems for the $X$ and $Z$ codes that can be solved independently.
For quantum Tanner codes in particular, there is symmetry between the $X$ and
$Z$ codes, as can be seen by switching $V_{0}$ and $V_{1}$ labels and
switching $C_{A},C_{B}$ with $C_{A}^{\perp},C_{B}^{\perp}$. Therefore, it
suffices to give an algorithm for decoding one type of error. In the remainder
of the paper, we will consider solely the case where $X$-errors occur, with
$Z$-errors treated analogously. For convenience, we will often drop
subscripts, for example writing $e$ for $e_{X}$ or $H$ for $H_{Z}$.

The above discussion assumes that the ideal syndrome is accessible to the
decoder. Let us now consider the case when the syndrome measurements are
unreliable, motivated by the fact that the quantum circuits implementing the
parity checks are necessarily imperfect. Suppose that the ideal syndrome
$\sigma_{X}$ of an error $e_{X}$ is corrupted by measurement error $D_{X}$, so
that the actual noisy syndrome readout is
$\tilde{\sigma}_{X}=\sigma_{X}+D_{X}$. A naive decoding of the syndrome
$\tilde{\sigma}_{X}$ may result in a correction $\hat{f}_{X}$ which does not
bring the state back to the code space, i.e., $e_{X}+\hat{f}_{X}\not\in
C_{X}^{\perp}$. Furthermore, there may be no guarantee that
$e_{X}+\hat{f}_{X}$ is close to $C_{X}^{\perp}$.

One of the standard procedures to account for measurement errors is to
repeatedly measure the stabilizer generators in order to gain enough
confidence in their measurement outcomes [23, 5]. This will incur large time
overhead. Alternatively, syndrome measurements can be performed fault-
tolerantly by preparing special ancilla qubit states offline [39, 40]. This
will incur large qubit overhead. It would be ideal if we could avoid both
overheads at the same time.

###  3.2 Single-shot decoding

Bombín [24] introduced _single-shot_ decoders as an alternative approach.
These decoders take in a noisy syndrome as input and, even in the presence of
syndrome noise, return a correction that can be used to reduce the data error.
Most likely, there will be some resulting residual error, but its weight is
bounded by some function of the syndrome noise. In more detail, the single-
shot property posits that it suffices to perform $O(n)$ parity check
measurements (in the context of QLDPC codes, one further requires constant
weight of measured parity checks), and, using _only_ these measurement
outcomes, one can perform reliable QEC that keeps the residual noise at bay.

In our analysis, we need the following definition.

######  Definition 3.2.

Let $\mathcal{C}$ be an $n$-qubit CSS code and $e\in\mathbb{F}_{2}^{n}$ be a
Pauli $X$ error. The stabilizer-reduced weight $|e|_{R}$ of $e$ is defined as
the weight of the smallest error equivalent to $e$ up to the addition of
stabilizers of $\mathcal{C}$, i.e., $|e|_{R}=\min_{e^{\prime}\in
C_{X}^{\perp}}|e+e^{\prime}|$. The stabilizer-reduced weight of a Pauli $Z$
error is defined analogously.

The stabilizer-reduced weight of an error is a convenient theoretical measure
of how detrimental the error really is. Note that since stabilizers do not
change the code state, errors are only well-defined up to the addition of
stabilizers. As such, any bound on the performance of the decoder is
unambiguously defined using the stabilizer-reduced weight, which can be
significantly smaller than the original weight.

Since we focus on asymptotically good QLDPC codes, it is enough to consider
single-shot decoding for adversarial noise. Campbell [29] captures adversarial
single-shot decoding as follows. Let both the data error $e$ and the syndrome
noise $D$ be sufficiently small. A decoder is single-shot if it outputs a
correction such that the weight of the residual error is bounded by a
polynomial of $|D|$. In this work, we would like to consider constant-time
decoding using the parallel decoder (Algorithm 3) for quantum Tanner codes.
This setting does not directly fit into the previous definition since the
residual error could depend on $|e|$ in addition to $|D|$. To allow for
nontrivial dependence on $|e|$, we give the following definition, which is
relevant for asymptotically good codes where the residual error size is at
most linear in $|e|$ and $|D|$.

######  Definition 3.3.

Let $\mathcal{C}$ be a CSS code specified by parity check matrices
$H_{X}\in\mathbb{F}_{2}^{r_{X}\times n}$ and
$H_{Z}\in\mathbb{F}_{2}^{r_{Z}\times n}$. Let
$e=(e_{X},e_{Z})\in\mathbb{F}_{2}^{2n}$ be a data error,
$D=(D_{X},D_{Z})\in\mathbb{F}_{2}^{r_{Z}+r_{X}}$ be a syndrome error, and
$\tilde{\sigma}=(\tilde{\sigma}_{X},\tilde{\sigma}_{Z})\in\mathbb{F}_{2}^{r_{Z}+r_{X}}$
be the corresponding noisy syndrome, where
$\tilde{\sigma}_{X}=H_{Z}e_{X}+D_{X}$ and
$\tilde{\sigma}_{Z}=H_{X}e_{Z}+D_{Z}$. A decoder for $\mathcal{C}$ is
$(\alpha,\beta)$-single-shot if there exist constants $A,B,C$ such that, for
$P\in\\{X,Z\\}$, whenever

$\displaystyle A|e_{P}|_{R}+B|D_{P}|\leq Cn,$ (3)

the decoder finds a correction $\hat{f}_{P}\in\mathbb{F}_{2}^{n}$ from given
input $\tilde{\sigma}_{P}$ such that

$\displaystyle|e_{P}+\hat{f}_{P}|_{R}\leq\alpha|e_{P}|+\beta|D_{P}|\,.$ (4)

This definition, combined with Theorems 4.17 and 4.20 below, gives the
following results for the sequential and parallel decoders of the quantum
Tanner codes.

######  Theorem 3.4 (Summary).

There exist constants $A,B,C,\beta>0$ (dependent on the parameters of the
quantum Tanner code) such that if $A|e|_{R}+B|D|\leq Cn$, then the following
conditions hold:

  1. 1.

The sequential decoder (Algorithm 1) is $(\alpha=0,\beta)$-single-shot.

  2. 2.

The parallel decoder (Algorithm 3) with $k$-iterations is
$(\alpha=2^{-\Omega(k)},\beta)$-single-shot.

Note that the runtime of the sequential decoder is $O(n)$, and each iteration
of the parallel decoder is constant time. For the parallel decoder, $\alpha$
decreases exponentially with the number of parallel decoding iterations $k$,
and the results of this section will hold when $k$ is a sufficiently large
constant. It suffices to take $k=O(\log n)$ for $\alpha=0$ in the parallel
decoder.

Finally, we remark that we may increase the robustness to measurement errors
and improve the overall performance of single-shot decoding by leveraging
redundancies among parity checks, similar to the ideas explored in Refs. [30,
31, 32]. We can apply this approach to quantum Tanner codes without
compromising their QLDPC structure, which is a crucial difference between our
setting and the aforementioned works. Specifically, stabilizer generators of
quantum Tanner codes are supported on local neighborhoods, defined by the
local codes $C_{0}$ and $C_{1}$. We may apply the technique of adding
redundancy to each set of local checks separately. Since the local codes are
of length $\Delta^{2}$, any redundant check in a fixed local neighborhood will
not have weight more than $\Delta^{2}$, which is comparable to the weight of
the original checks.

###  3.3 Multiple rounds of decoding

In this section, we discuss what happens after multiple rounds of errors,
noisy measurements, and decoding. We show that under the assumptions of
Definition 3.3, there exists a variety of noise models such that, as long as
the overall noise level is sufficiently small, the encoded quantum information
will persist for an exponential number of rounds.

The results proven in this section hold for any decoder that can solve the
single-shot decoding problem under Definition 3.3. More precisely, we assume
that if the decoder is given the noisy syndrome from data error
$e\in\mathbb{F}_{2}^{n}$ and syndrome error $D\in\mathbb{F}_{2}^{r_{Z}}$
satisfying

$A|e|_{R}+B|D|\leq Cn\,,$ (5)

then it outputs a correction $\hat{f}$ such that the residual error satisfies

$|e+\hat{f}|_{R}\leq\alpha|e|+\beta|D|\,.$ (6)

We will assume that $\beta$ is constant and that $\alpha$ is a parameter in
the decoder that can be made arbitrarily small. For our analysis, we let $R,S$
be constants such that

$R\leq\frac{(1-\alpha)C}{2A}\quad\text{and}\quad
S\leq\frac{(1-\alpha)C}{2\left({\beta A}+(1-\alpha)B\right)}\,.$ (7)

We prove that as long as the data and syndrome errors in each round are
sufficiently small, the total error can be kept small indefinitely.

######  Theorem 3.5.

Consider errors $(e_{i},D_{i})$ that occur on rounds $i=1,2,\cdots$, with
decoding in between each round using new syndrome measurements (i.e., without
using the previous syndromes). If the errors satisfy $|e_{i}|\leq Rn$ and
$|D_{i}|\leq Sn$ for every round $i$, then the residual error $e_{i}^{\prime}$
after each round $i$ satisfies

$|e_{i}^{\prime}|_{R}\leq\frac{\alpha R+\beta S}{1-\alpha}n\,.$ (8)

###### Proof.

Initially, $e_{0}^{\prime}=0$, which satisfies the bound. Suppose after round
$i-1$, the residual error $e_{i-1}^{\prime}$ satisfies (8). The new total
error is $e_{i-1}^{\prime}+e_{i}$, and we have

$\displaystyle A|e_{i-1}^{\prime}+e_{i}|_{R}+B|D_{i}|$ $\displaystyle\leq
A|e_{i-1}^{\prime}|_{R}+A|e_{i}|+B|D_{i}|$ (9) $\displaystyle\leq
A\frac{\alpha R+\beta S}{1-\alpha}n+ARn+BSn$ (10) $\displaystyle\leq Cn\,,$
(11)

where the last inequality follows since

$A\frac{R+\beta S}{1-\alpha}+BS\leq C$ (12)

for $R$ and $S$ satisfying (7).Therefore, the decoder returns a correction
$\hat{f}$ with residual error

$\displaystyle|e_{i}^{\prime}|_{R}$
$\displaystyle\leq\alpha|e_{i-1}^{\prime}+e_{i}|_{R}+\beta|D_{i}|$ (13)
$\displaystyle\leq\alpha|e_{i-1}^{\prime}|_{R}+\alpha|e_{i}|+\beta|D_{i}|$
(14) $\displaystyle\leq\alpha\frac{\alpha R+\beta S}{1-\alpha}n+\alpha
Rn+\beta Sn$ (15) $\displaystyle=\frac{\alpha R+\beta S}{1-\alpha}n\,,$ (16)

where the third inequality uses the inductive hypothesis. ∎

From this result, we can immediately analyze the stochastic setting in which
large errors are unlikely.

######  Corollary 3.6.

Let $\\{(e_{i},D_{i})\\}_{i=1}^{M}$ be randomly distributed data and syndrome
errors (with possible correlations) such that

$\Pr(|e_{i}|>Rn)\leq e^{-an},\quad\text{and}\quad\Pr(|D_{i}|>Sn)\leq
e^{-bn}\,,$ (17)

for constants $a,b>0$. Suppose the decoder is run after each round of errors
using new syndrome measurements (i.e., without using the syndromes of previous
rounds). Then the final residual error $e_{M}^{\prime}$ satisfies

$\Pr\left(|e_{M}^{\prime}|_{R}>\frac{\alpha R+\beta S}{1-\alpha}n\right)\leq
M(e^{-an}+e^{-bn})\,.$ (18)

###### Proof.

This follows immediately from Theorem 3.5 after using a union bound on the
probability of a large data or syndrome error at every round. ∎

As a sample application of Corollary 3.6, we analyze the case of $p$-bounded
noise [41, 25], although any model of errors with sufficiently suppressed
tails will give the same conclusions.

######  Definition 3.7 ($p$-bounded noise).

Let $p\in[0,1)$. Let $A$ be a set and let $2^{A}$ be its power set. We say
that a probability distribution $E:2^{A}\rightarrow[0,1]$ is _$p$ -bounded_ if
for any $B\subseteq A$ we have

$\displaystyle\sum_{B^{\prime}\supseteq B}E(B^{\prime})\leq p^{|B|}\ .$ (19)

######  Corollary 3.8.

Let $\\{(e_{i},D_{i})\\}_{i=1}^{M}$ be data and syndrome errors where each of
the marginal distributions of $e_{i}$ and $D_{i}$ are $p$\- and $q$-bounded,
respectively. Suppose the decoder is run after each round of errors using a
new round of syndrome measurements (without using the syndromes of previous
rounds). Then, the final residual error $e_{M}^{\prime}$ satisfies

$\displaystyle\Pr\left(|e_{M}^{\prime}|_{R}>\frac{\alpha R+\beta
S}{1-\alpha}n\right)\leq
M\left(e^{-n\ln(2^{-H(R)}p^{-R})}+e^{-n\ln(2^{-\varrho
H(S/\varrho)}q^{-S})}\right)\ ,$ (20)

where $H(\tau)=-\tau\log_{2}\tau-(1-\tau)\log_{2}(1-\tau)$ is the binary
entropy function, and $\varrho=r_{Z}/n$.

###### Proof.

Let us first upper bound $\Pr(|e_{i}|>Rn)$. We have

$\displaystyle\Pr(|e_{i}|>Rn)$
$\displaystyle=\sum_{\begin{subarray}{c}|e|>Rn\end{subarray}}\Pr(e_{i}=e)\leq\sum_{|e|=Rn}\Pr(e_{i}\supset
e)\leq\sum_{|e|=Rn}p^{|e|}\leq\binom{n}{Rn}p^{Rn}\,,$ (21)

where the last inequality follows by $p$-boundedness. Using the binary entropy
bound for the binomial coefficient, we then have

$\displaystyle\Pr(|e_{i}|>Rn)$ $\displaystyle\leq\binom{n}{Rn}p^{Rn}\leq
2^{nH(R)}p^{Rn}=e^{-n\ln(2^{-H(R)}p^{-R})}\,.$ (22)

Similarly, we have

$\displaystyle\Pr(|D_{i}|>Sn)\leq e^{-n\ln(2^{-\varrho
H(S/\varrho)}q^{-S})}\,.$ (23)

Applying Corollary 3.6 gives the result. ∎

In particular, there exist thresholds $(p_{*},q_{*})=(2^{-H(R)/R},2^{-\varrho
H(S/\varrho)/S})$ below which errors are kept under control for an exponential
number of rounds of single-shot QEC with high probability.

Finally, we comment on the last round of QEC. In a typical setting of fault
tolerance, we choose to measure logical qubits in the computational basis,
which for a CSS code can be accomplished by measuring each physical qubit
(also in the computational basis). We then apply one final round of QEC, where
the $Z$-stabilizer eigenvalues are inferred by multiplying the $Z$-measurement
outcomes from those qubits in the stabilizer supports. Note that in this final
round, any measurement error can be treated as an $X$ data error immediately
before the measurement. We run the decoder with $\alpha$ sufficiently small so
that by the guarantee on the decoder, $|e+\hat{f}|_{R}=0$, i.e., we completely
correct the error. We can then infer the logical information by combining the
corrected single-qubit $Z$-measurement outcomes making up the $Z$-logical
operators. Therefore, fault tolerance may be achieved by using a faster (e.g.,
constant-time) decoder with larger $\alpha$ value in the middle of the
computation, and only applying the full decoder (e.g., logarithmic-time) with
$\alpha=0$ at the end of the computation.

##  4 Proofs of Single-shot Decoding of Quantum Tanner Codes

###  4.1 Decoding Algorithms

We consider the decoding problem for quantum Tanner codes with parameters as
in Theorem 2.3. We first provide an overview of how the decoder works. As
before, we will work exclusively with $X$-type errors, with $Z$-errors being
analogous. Suppose that the code state experiences data error $e$, and the
measurements experience syndrome error $D$. The decoder is consequently given
as input the noisy syndrome $\tilde{\sigma}=\sigma+D=H_{Z}e+D$. Due to the
structure of the code, the global syndrome $\tilde{\sigma}$ can equivalently
be viewed as a set of noisy local syndromes $\\{\tilde{\sigma}_{v}\\}_{v\in
V_{1}}$, where $\tilde{\sigma}_{v}$ denotes the restriction of
$\tilde{\sigma}$ to the checks associated with the local code $C_{1}^{\perp}$
at vertex $v$. At each $V_{1}$ vertex, the decoder computes a minimal weight
correction $\tilde{\varepsilon}_{v}\subseteq Q(v)$ based on the local syndrome
$\tilde{\sigma}_{v}$, i.e,

$\displaystyle\tilde{\varepsilon}_{v}=\operatorname{argmin}\\{|y|:y\subseteq
Q(v),\sigma_{v}(y)=\tilde{\sigma}_{v}\\}\,.$ (24)

Note that this is a completely local operation which can be done without
consideration of the syndrome state of the other vertices. Each square $q\in
Q$ contains two $V_{1}$ vertices, say $v\in V_{01}$ and $v^{\prime}\in
V_{10}$. These two vertices are each associated with their own local
corrections, $\tilde{\varepsilon}_{v}$ and $\tilde{\varepsilon}_{v^{\prime}}$,
which may disagree on whether there is an error on $q$. If there is no
disagreement on any square $q\in Q$, then a global correction
$\hat{f}\in\mathbb{F}_{2}^{Q}$ can be unambiguously defined by

$\displaystyle\hat{f}=\bigsqcup_{v\in
V_{01}}\tilde{\varepsilon}_{v}=\bigsqcup_{v^{\prime}\in
V_{10}}\tilde{\varepsilon}_{v^{\prime}}.$ (25)

However, this will usually not be the case. The disagreement between the
different candidate local corrections is captured by a “noisy mismatch vector”
defined as

$\tilde{Z}=\sum_{v\in V_{1}}\tilde{\varepsilon}_{v}\,.$ (26)

The goal of the main part of the algorithm is to reduce the size of
$\tilde{Z}$ by successively updating the best local corrections on the $V_{1}$
vertices. For example, it is possible that for a given $v\in V_{1}$, replacing
$\tilde{\varepsilon}_{v}$ with $\tilde{\varepsilon}_{v}+x$ for some $x\in
C_{1}^{\perp}$ in (26) would significantly decrease $|\tilde{Z}|$. In general,
we attempt to decompose $\tilde{Z}$ by adding codewords $x\in C_{1}^{\perp}$
on local views $Q(v)$ of vertices $v\in V$.222In the presence of measurement
errors, a full decomposition of $\tilde{Z}$ into local codewords may not be
possible. See Definition 4.4 and related comments before and after. We keep
track of the decomposition process through quantities
$\hat{C}_{0},\hat{C}_{1},\hat{R}_{0},\hat{R}_{1}\subseteq\mathbb{F}_{2}^{Q}$,
which are initially 0 and updated as follows. Suppose $x=c+r$ is supported on
a $V_{ij}$ local view ($i,j\in\\{0,1\\}$), where $c\in
C_{A}\otimes\mathbb{F}_{2}^{B}$ and $r\in\mathbb{F}_{2}^{A}\otimes C_{B}$.
Then we add $c$ to $\hat{C}_{j}$ and $r$ to $\hat{R}_{i}$. The interpretation
is that $\hat{C}_{1}+\hat{R}_{0}$ is the total change made to the local
corrections $\tilde{\varepsilon}_{v}$ from the $V_{01}$ vertices, and
$\hat{C}_{0}+\hat{R}_{1}$ is the total change made to those from the $V_{10}$
vertices. Therefore, at the end of the procedure, we output a guess for the
error, which from the perspective of the $V_{01}$ vertices is

$\hat{f}=\sum_{v\in V_{01}}\tilde{\varepsilon}_{v}+\hat{C}_{1}+\hat{R}_{0}\,.$
(27)

The algorithm can run either sequentially (Algorithm 1) or in parallel
(Algorithm 3), with the corresponding $\tilde{Z}$ decomposition subroutines
presented in Algorithm 2 and Algorithm 4 respectively.

Algorithm 1 Sequential decoder for quantum Tanner codes with parameter
$\varepsilon$

Input: A noisy syndrome $\tilde{\sigma}$ arising from data error $e$ and
syndrome error $D$.

Output: A correction $\hat{f}$ that approximates $e$.

1:$\tilde{\varepsilon}_{v}\leftarrow\operatorname{argmin}\\{|y|:y\subseteq
Q(v),\sigma_{v}(y)=\tilde{\sigma}_{v}\\}$ (or
$\tilde{\varepsilon}_{v}\leftarrow 0$ if no such $y$ exists) for all $v\in
V_{1}$

2:$\tilde{Z}\leftarrow\sum_{v\in V_{1}}\tilde{\varepsilon}_{v}$

3:$(\hat{C}_{0},\hat{C}_{1},\hat{R}_{0},\hat{R}_{1})\leftarrow\textsc{Mismatch}_{\varepsilon}(\tilde{Z})$

4:$\hat{f}\leftarrow\sum_{v\in
V_{01}}\tilde{\varepsilon}_{v}+\hat{C}_{1}+\hat{R}_{0}$

5:return $\hat{f}$

Algorithm 2 Sequential mismatch decomposition with parameter $\varepsilon$

Input: A vector $Z\in\mathbb{F}_{2}^{Q}$.
Output: A collection
$(\hat{C}_{0},\hat{C}_{1},\hat{R}_{0},\hat{R}_{1})\equiv\textsc{Mismatch}_{\varepsilon}(Z)$.

1:Set $\hat{C}_{0}=\hat{C}_{1}=\hat{R}_{0}=\hat{R}_{1}=0$ and $\hat{Z}=Z$.

2:while $\hat{Z}\neq 0$ do

3: if $\exists v\in V_{ij}$ and $0\neq x_{v}\in C_{1}^{\perp}$ in $Q(v)$ such
that $|\hat{Z}|-|\hat{Z}+x_{v}|\geq(1-\varepsilon)|x_{v}|$ then

4: Find $r_{v}\in\mathbb{F}_{2}^{A}\otimes C_{B}$ and $c_{v}\in
C_{A}\otimes\mathbb{F}_{2}^{B}$ such that $\|c_{v}\|+\|r_{v}\|$ is minimal
among
all $c_{v},r_{v}$ such that $r_{v}+c_{v}=x_{v}$

5: $\hat{C}_{j}\leftarrow\hat{C}_{j}+c_{v}$

6: $\hat{R}_{i}\leftarrow\hat{R}_{i}+r_{v}$

7: $\hat{Z}\leftarrow\hat{Z}+c_{v}+r_{v}$

8: else

9: return ($\hat{C}_{0},\hat{C}_{1},\hat{R}_{0},\hat{R}_{1}$)

10: end if

11:end while

12:return $(\hat{C}_{0},\hat{C}_{1},\hat{R}_{0},\hat{R}_{1})$

Algorithm 3 Parallel decoder for quantum Tanner codes with $k$ iterations

Input: A noisy syndrome $\tilde{\sigma}$ from a data error $e$ and syndrome
error $D$, and an integer $k>0$.
Output: A correction $\hat{f}$ that approximates $e$.

1:parallel for each $v\in V_{1}$ do

2: $\tilde{\varepsilon}_{v}\leftarrow\operatorname{argmin}\\{|y|:y\in
Q(v),\sigma_{v}(y)=\tilde{\sigma}_{v}\\}$ (or
$\tilde{\varepsilon}_{v}\leftarrow 0$ if no such $y$ exists)

3: $\tilde{Z}\leftarrow\sum_{v\in V_{1}}\tilde{\varepsilon}_{v}$

4: $\hat{f}\leftarrow\sum_{v\in V_{01}}\tilde{\varepsilon}_{v}$

5:end parallel for each

6:$(\hat{C}_{0},\hat{C}_{1},\hat{R}_{0},\hat{R}_{1})\leftarrow\textsc{ParMismatch}^{(k)}(\tilde{Z})$

7:$\hat{f}\leftarrow\hat{f}+\hat{C}_{1}+\hat{R}_{0}$ // update $\hat{f}$ in
parallel for each vertex $v\in V_{01}$

8:return $\hat{f}$

Algorithm 4 Parallel mismatch decomposition procedure with $k$ iterations

Input: A vector $Z\in\mathbb{F}_{2}^{Q}$ and integer $k>0$.
Output: A collection
$(\hat{C}_{0},\hat{C}_{1},\hat{R}_{0},\hat{R}_{1})\equiv\textsc{ParMismatch}^{(k)}(Z)$.

1:Set $\hat{C}_{0}=\hat{C}_{1}=\hat{R}_{0}=\hat{R}_{1}=0$ and $\hat{Z}=Z$.

2:repeat $k$ times

3: for $(i,j)\in\\{0,1\\}^{2}$ do

4: parallel for each $v\in V_{ij}$ do

5: if there exists $0\neq x_{v}\in C_{1}^{\perp}$ in $Q(v)$ such that
$|\hat{Z}|-|\hat{Z}+x_{v}|\geq|x_{v}|/2$ then

6: Choose $x_{v}$ such that $|x_{v}|$ maximal among all possible choices

7: Find $r_{v}\in\mathbb{F}_{2}^{A}\otimes C_{B}$ and $c_{v}\in
C_{A}\otimes\mathbb{F}_{2}^{B}$ such that $\|c_{v}\|+\|r_{v}\|$ is minimal
among all $c_{v},r_{v}$ such that $r_{v}+c_{v}=x_{v}$

8: $\hat{C}_{j}\leftarrow\hat{C}_{j}+c_{v}$

9: $\hat{R}_{i}\leftarrow\hat{R}_{i}+r_{v}$

10: $\hat{Z}\leftarrow\hat{Z}+c_{v}+r_{v}$

11: end if

12: end parallel for each

13: end for

14:end repeat

15:return $(\hat{C}_{0},\hat{C}_{1},\hat{R}_{0},\hat{R}_{1})$

These algorithms were analyzed in the scenario with perfect measurement
outcomes in Ref. [33], giving the following results:

######  Theorem 4.1 (Theorem 13 in Ref. [33]).

Let $\varepsilon\in(0,1)$. Suppose Algorithm 1 with parameter $\varepsilon$ is
given as input the noiseless syndrome $\sigma=H_{Z}e$ of an error
$e\in\mathbb{F}_{2}^{Q}$ of weight

$|e|\leq\frac{1}{2^{11}}\min\left(\frac{\varepsilon^{3}}{16},\kappa\right)(1-\varepsilon)d_{r}^{2}\kappa^{2}\frac{n}{\Delta}\,.$
(28)

Then it will output a correction $\hat{f}$ such that $e+\hat{f}\in
C_{X}^{\perp}$ in time $O(n)$.

######  Theorem 4.2 (Theorem 20 in Ref. [33]).

Let $\varepsilon\in(0,1/6)$. Suppose Algorithm 3 is given as input the
noiseless syndrome $\sigma=H_{Z}e$ of an error $e\in\mathbb{F}_{2}^{Q}$ of
weight

$|e|\leq\frac{1}{2^{12}}\min\left(\frac{\varepsilon^{3}}{16},\kappa\right)d_{r}^{2}\kappa^{2}\frac{n}{\Delta}\,.$
(29)

Then it will output a correction $\hat{f}$ such that $e+\hat{f}\in
C_{X}^{\perp}$ in time $O(\log n)$.

In the next sections, we will consider what happens when the decoders are
given a syndrome with possible errors.

###  4.2 Proof Preliminaries

We first give a summary of the main ideas of the proof. The key idea of the
proof is to bound the reduction in the weight of the noisy mismatch vector
$\tilde{Z}$ through each step of the algorithm, and to show that when the
weight of $\tilde{Z}$ is reduced, the weight of the residual error is also
subsequently reduced. There is a technical challenge to this idea however:
there is no direct relation between the weight of $\tilde{Z}$ and the error
weight.

To bridge these two objects, we define the notion of an ideal mismatch vector
$Z$ (see Eq. (32) below), which is equal to $\tilde{Z}$ when there is no
measurement noise. Since the mismatch $Z$ only captures the portion of the
error which cannot be removed using independent local corrections, we must
first “pre-process” the error by making any possible local corrections (see
Eq. (34) below). This establishes a direct connection between $Z$ and the
“pre-processed” error $e_{0}$ (see Lemma 4.7) and our analysis will be built
upon this connection.

We show that if $Z$ is decomposable into local corrections by Algorithm 2,
then most of these correction sets will also reduce the weight of $\tilde{Z}$
(Lemma 4.13). This in turn allows us to relate the weights of $Z$ and
$\tilde{Z}$. Finally, we show that if the qubit and measurement error weights
are bounded, the ideal mismatch vector $Z$ always admits the desired
decomposition into local correction sets (Lemma 4.15). These lemmas allow us
prove our main result (Theorem 4.17): as the weight of $\tilde{Z}$ decreases
throughout the steps of the algorithm, the residual error weight must also
decrease. The analysis of the parallel decoder then builds upon this bound,
with the additional requirement of showing that the decomposition of $Z$ into
local corrections must be essentially disjoint (Lemma 4.18).

In the remainder of this section, we set up notation and provide some
preliminary results used in the proofs of Theorems 4.17 and 4.20. We first
define quantities relating to the states of the decoders. Given the local
structure of the quantum Tanner codes, it will be more convenient to bound the
size of the syndrome noise in terms of its vertex support.

######  Definition 4.3.

Given a quantum Tanner code and a syndrome noise $D$, let us define $D_{v}$ to
be the restriction of $D$ to the set of stabilizer generators associated with
vertex $v$. We define the vertex support of $D$ to be the set of all vertices
such that $D_{v}\neq 0$. We denote the size of the vertex support by
$|D|_{V}$. Note that we have $\Delta^{-2}|D|\leq r^{-1}|D|\leq|D|_{V}\leq|D|$,
where $r$ is the number of stabilizer generators associated with the local
code.

Given the noisy syndrome $\tilde{\sigma}=H_{Z}e+D$, let $\tilde{\sigma}_{v}$
denote the restriction of $\tilde{\sigma}$ to the checks associated with the
vertex $v$. For each vertex $v\in V_{1}$, the decoder finds a locally minimal
correction $\tilde{\varepsilon}_{v}$ such that
$\sigma_{v}(\tilde{\varepsilon}_{v})=\tilde{\sigma}_{v}$ . In the event that
no local correction $\tilde{\varepsilon}_{v}$ exists for $\tilde{\sigma}_{v}$,
we may define $\tilde{\sigma}_{v}$ arbitrarily. In our case, we will simply
define $\tilde{\varepsilon}_{v}=0$ by convention. If $\varepsilon_{v}$ is the
locally minimal correction associated with the noiseless syndrome
$\sigma_{v}$, then we can decompose $\tilde{\varepsilon}_{v}$ into “noiseless”
and “noisy” parts as

$\tilde{\varepsilon}_{v}=\varepsilon_{v}+\varepsilon_{v}(D)\,,$ (30)

where $\varepsilon_{v}(D)$ is defined by
$\varepsilon_{v}(D)=\tilde{\varepsilon}_{v}-\varepsilon_{v}$. Note that
$\varepsilon_{v}(D)$ will be non-zero only when $D$ has non-zero support on
$v$.

The full noisy mismatch vector initialized by the decoder is given by

$\displaystyle\tilde{Z}$ $\displaystyle=\sum_{v\in
V_{1}}\tilde{\varepsilon}_{v}=\sum_{v\in
V_{1}}(\varepsilon_{v}+\varepsilon_{v}(D))\,.$ (31)

It will likewise be convenient to split the mismatch into a noiseless and a
noisy part, defined by

$\displaystyle Z=\sum_{v\in V_{1}}\varepsilon_{v}\quad\text{and}\quad
Z_{N}=\sum_{v\in V_{1}}\varepsilon_{v}(D)\,,~{}$ (32)

so that $\tilde{Z}=Z+Z_{N}$. We will also need the restrictions of these
vectors onto the vertices of $V_{01}$, which we define as

$\displaystyle\tilde{Z}^{01}=\sum_{v\in V_{01}}\tilde{\varepsilon}_{v},\quad
Z^{01}=\sum_{v\in V_{01}}\varepsilon_{v},\quad\text{and}\quad
Z_{N}^{01}=\sum_{v\in V_{01}}\varepsilon_{v}(D)\,.$ (33)

The key idea of the proof is to pre-process the error using $\tilde{Z}^{01}$,
and apply the local corrections $x_{v}$ step by step. Specifically, we define
the initial pre-processed error $\tilde{e}_{0}$, and the “noiseless” pre-
processed error $e_{0}$, by

$\displaystyle\tilde{e}_{0}$ $\displaystyle=e+\tilde{Z}^{01}=e+\sum_{v\in
V_{01}}\tilde{\varepsilon}_{v}\,,~{}$ (34) $\displaystyle e_{0}$
$\displaystyle=e+Z^{01}=\tilde{e}_{0}+Z_{N}^{01}\,.$ (35)

For the purpose of our proof, we consider the vector $\tilde{e}_{0}$ as the
initial error state of the algorithm, and $\tilde{Z}_{0}=\tilde{Z}$ as the
initial mismatch. Note that in practice it does not matter at what point in
the decoding procedure the set $\tilde{Z}^{01}$ is flipped. The pre-processing
is only introduced as a convenience in our proof in order to relate the weight
of $e$ to the weight of $Z$. The original algorithms considered in Ref. [33]
involve a “post-processing” step instead, where $\tilde{Z}^{01}$ is applied at
the very end rather than the beginning. Since the sets of qubits flipped are
ultimately the same in either case, the results here hold without
modification.

The core loop of the decoding algorithm finds, at each step $i$, some local
codeword $x_{i}=r_{i}+c_{i}\subseteq Q(v_{i})$ such that

$\displaystyle|\tilde{Z}_{i-1}|-|\tilde{Z}_{i-1}+x_{i}|\geq(1-\varepsilon)|x_{i}|.$
(36)

Having found a codeword which satisfies (36), we update the error and the
mismatch vectors by

$\displaystyle\tilde{e}_{i}=\tilde{e}_{i-1}+f_{i},\quad\text{and}\quad\tilde{Z}_{i}=\tilde{Z}_{i-1}+x_{i}\,,$
(37)

where the flip-set $f_{i}\subseteq Q(v_{i})$ is defined by

$\displaystyle f_{i}=\begin{cases}0&v_{i}\in V_{10}\ ,\\\ x_{i}&v_{i}\in
V_{01}\ ,\\\ c_{i}&v_{i}\in V_{11}\ ,\\\ r_{i}&v_{i}\in V_{00}\ .\\\
\end{cases}$ (38)

Likewise, we can define the associated “noiseless” error and mismatch at each
step by

$\displaystyle
e_{i}=e_{i-1}+f_{i}=\tilde{e}_{i}+Z_{N}^{01},\quad\text{and}\quad
Z_{i}=Z_{i-1}+x_{i}=\tilde{Z}_{i}+Z_{N}\,.$ (39)

Note that $Z_{N}$ and $Z_{N}^{01}$ are determined entirely by the syndrome
noise $D$ and initial error $e$, and are constant through the decoding
process.

In the presence of measurement errors, it is no longer true that the noisy
mismatch $\tilde{Z}$ can be decomposed into a sum of local codewords.333In the
case of perfect syndrome measurements, we have  $Z=\sum_{v\in
V_{1}}\varepsilon_{v}=\sum_{v\in V_{1}}(e_{v}+r_{v}+c_{v})=\sum_{v\in
V_{1}}(r_{v}+c_{v}),$ where $r_{v}+c_{v}$ is the codeword that the local error
is corrected to: $e_{v}+\varepsilon_{v}=r_{v}+c_{v}$. This decomposition no
longer holds in the presence of imperfect measurements. As such, some care
must be taken in characterizing what exactly we mean by a “mismatch”. This is
captured by the definition below.

######  Definition 4.4.

A mismatch vector is any $Z\in\mathbb{F}_{2}^{Q}$ that can be decomposed as
$Z=C_{0}+C_{1}+R_{0}+R_{1}$, where

$\displaystyle C_{j}=\sum_{v\in V_{\overline{j}j}}c_{v}\quad\text{and}\quad
R_{i}=\sum_{v\in V_{i\overline{i}}}r_{v}$ (40)

are the sum of local column codewords $c_{v}\in
C_{A}\otimes\mathbb{F}_{2}^{B}$ and row codewords
$r_{v}\in\mathbb{F}_{2}^{A}\otimes C_{B}$ on $Q(v)$, i.e., a mismatch vector
is an element in the span of local codewords $C_{1}^{\perp}$. Here, we define
$\overline{i}=1-i$ for convenience.

The division of $Z$ into local codewords of the form
$(C_{0},C_{1},R_{0},R_{1})$ is called a _decomposition_ of $Z$. Any given
mismatch vector $Z$ may have many distinct decompositions. Given any
decomposition, we define its _weight_ by

$\displaystyle\mathrm{wt}(C_{0},C_{1},R_{0},R_{1})=\|C_{0}\|+\|C_{1}\|+\|R_{0}\|+\|R_{1}\|,$
(41)

where $\|C_{i}\|$ and $\|R_{i}\|$ denote the number of non-zero columns and
rows, respectively, present in $C_{i}$ and $R_{i}$. Note that the weight is
well-defined since distinct local codewords $c_{v}\subseteq C_{i}$ and
$r_{v}\subseteq R_{i}$ are disjoint. We then define the _norm_ of a mismatch
to be

$\displaystyle\|Z\|=\min_{\begin{subarray}{c}(C_{0},C_{1},R_{0},R_{1})\\\
Z=C_{0}+C_{1}+R_{0}+R_{1}\end{subarray}}\mathrm{wt}(C_{0},C_{1},R_{0},R_{1}).$
(42)

Decompositions such that $\mathrm{wt}(C_{0},C_{1},R_{0},R_{1})=\|Z\|$ are
called _minimal weight_ decompositions for $Z$.

Note that technically the vector $\tilde{Z}$ which we call the noisy mismatch
vector is _not_ a mismatch vector at all as defined by Definition 4.4.
Nevertheless, we will continue to call $\tilde{Z}$ the noisy mismatch since
there is little chance of confusion. The noiseless part $Z$ is a genuine
mismatch vector by definition. The properties of the noiseless mismatch $Z$
are characterized by the following lemma from Ref. [33].

######  Lemma 4.5 (Lemma 17 in Ref. [33]).

Let $e\in\mathbb{F}_{2}^{Q}$ be an error and let $\varepsilon_{v}$ be a local
minimal correction for $e_{v}$ at every vertex $v\in V_{1}$. Let

$\displaystyle Z=\sum_{v\in V_{1}}\varepsilon_{v}\,.$ (43)

Then $Z$ is a mismatch vector which satisfies

$\displaystyle|Z|\leq
4|e|_{R},\quad\text{and}\quad\|Z\|\leq\frac{4}{\kappa\Delta}|e|_{R}\,.$ (44)

The main purpose of pre-processing in our proof is that the noiseless pre-
processed error $e_{0}$ and the noiseless mismatch $Z_{0}$ can be easily
related through the following property.

######  Definition 4.6.

Let $e\in\mathbb{F}_{2}^{Q}$ be an error. We say that the error is
$V_{ij}$-weighted if $\sigma_{v}(e)=0$ for all $v\in
V_{\overline{i}\overline{j}}$. Given a $V_{ij}$-weighted error $e$, we say
that a mismatch vector $Z$ is _associated_ with $e$ if
$\sigma_{v}(Z)=\sigma_{v}(e)$ for all $v\in V_{ij}$.

######  Lemma 4.7.

The quantity $e_{0}$ is a $V_{10}$-weighted error and $Z_{0}=Z$ is a mismatch
vector associated with $e_{0}$.

###### Proof.

First, we show that $Z$ is a mismatch vector. Note that $Z$ is the sum of
local minimal corrections $\varepsilon_{v}$ to the error $e$, i.e.,

$\displaystyle Z=\sum_{v\in V_{1}}\varepsilon_{v}\,,$ (45)

where for each vertex $v\in V_{1}$ we have $e_{v}=\varepsilon_{v}+x_{v}$ for
some $x_{v}\in C_{1}^{\perp}$. Therefore

$\displaystyle Z=\sum_{v\in V_{1}}(e_{v}+x_{v})=\sum_{v\in V_{1}}x_{v}\,,$
(46)

where the $e_{v}$ terms cancel since each face occurs exactly twice in the sum
above. Next, we show that $e_{0}$ is $V_{10}$-weighted. We have

$\displaystyle e_{0}=e+Z^{01}=e+\sum_{v\in V_{01}}\varepsilon_{v}\,.$ (47)

Note that the terms in the latter sum are disjoint for distinct vertices
$v,v^{\prime}\in V_{01}$. It follows that the restriction of $e_{0}$ to a
vertex $v\in V_{01}$ is given by

$\displaystyle(e_{0})_{v}=e_{v}+\varepsilon_{v}=x_{v}\,,$ (48)

which has zero syndrome. Finally we show that $Z$ is associated with $e_{0}$.
The restriction of $e_{0}$ to a vertex $v\in V_{10}$ is given by

$\displaystyle(e_{0})_{v}=e_{v}+Q(v)\cap\sum_{u\in V_{01}}\varepsilon_{u}\,.$
(49)

Likewise, the restriction of $Z$ to $v\in V_{10}$ is given by

$\displaystyle Z_{v}=\varepsilon_{v}+Q(v)\cap\sum_{u\in
V_{01}}\varepsilon_{u}\,.$ (50)

It follows that

$\displaystyle\sigma_{v}(Z)=\sigma_{v}(\varepsilon_{v})+\sigma_{v}\left(Q(v)\cap\sum_{u\in
V_{01}}\varepsilon_{u}\right)=\sigma_{v}(e_{v})+\sigma_{v}\left(Q(v)\cap\sum_{u\in
V_{01}}\varepsilon_{u}\right)=\sigma_{v}\left(e_{0}\right),$ (51)

which shows that $Z$ is associated with $e_{0}$. ∎

The notion of $e_{i}$ being a $V_{10}$-weighted error is invariant as the
decoder proceeds, i.e., if $e_{i}$ is initially $V_{10}$-weighted then it
remains so. Moreover, if $Z$ was initially a mismatch associated with $e_{0}$
then $Z_{i}$ remains associated with $e_{i}$ throughout all steps $i$ of the
decoder.

######  Lemma 4.8.

Let $Z$ be a weighted mismatch vector associated with a $V_{10}$-weighted
error $e$. Let $x=c+r\subseteq Q(v)$ be a codeword of $C_{1}^{\perp}$, with
$v\in V_{ij}$. Define

$f=\begin{cases}0,&v\in V_{10}\,,\\\ x,&v\in V_{01}\,,\\\ c,&v\in V_{11}\,,\\\
r,&v\in V_{00}\,,\end{cases}$ (52)

to be the associated flip set. Then $e+f$ is again a $V_{10}$-weighted error
and $Z+x$ is an associated mismatch vector.

###### Proof.

It is clear that $Z+x$ is a mismatch vector since $Z$ was one and we add a
single $C_{1}^{\perp}$ codeword.

We first show that $e+f$ remains $V_{10}$-weighted. Clearly $e+f$ is
$V_{10}$-weighted if $v\in V_{10}$ or $v\in V_{01}$ since we either add
nothing, or a local codeword to a $V_{01}$ vertex. Now suppose that $v\in
V_{00}$ so that $f=r$. We can decompose $r$ into $r=r_{1}+\cdots+r_{k}$, where
each $r_{i}$ is a local codeword supported on a single row, which we can
assume to be indexed by the edge $(v,u_{i})$ for some $u_{i}\in V_{01}$. The
syndrome of $e+r$ on a vertex $u\in V_{01}$ is therefore given by

$\displaystyle\sigma_{u}(e+f)=\begin{cases}\sigma_{u}(e)&u\neq u_{i}\text{ for
all }i,\\\ \sigma_{u}(e+r_{i})&u=u_{i}\text{ for some }i.\end{cases}$ (53)

In either case, we have $\sigma_{u}(e+f)=0$ so that $e+f$ is
$V_{10}$-weighted. The case where $v\in V_{11}$ is analogous, taking $f=c$ and
making a similar decomposition.

Finally, we show that $Z+x$ is associated with $e+f$. Let us write

$\displaystyle Z=\sum_{u\in V_{10}}\varepsilon_{u},$ (54)

where $\sigma_{u}(Z)=\sigma_{u}(e)$ for all $u\in V_{10}$. If $v\in V_{10}$
then there is nothing to show since all syndromes are unchanged. If $v\in
V_{01}$ then define

$\varepsilon_{u}^{\prime}=\varepsilon_{u}+Q(u)\cap x\,$ (55)

so that

$\displaystyle Z+x=\sum_{u\in V_{10}}\varepsilon_{u}^{\prime}.$ (56)

Since $(e+x)_{u}=e_{u}+Q(u)\cap x$, we see that $\varepsilon_{u}^{\prime}$ has
the same syndrome as $(e+f)_{u}$.

Lastly, suppose $v\in V_{00}$, with the $V_{11}$ case being analogous. Let
$f=r$. Note that $\varepsilon_{u}^{\prime}=\varepsilon_{u}$ and
$(e+r)_{u}=e_{u}$ for all $u\in V_{10}$ not adjacent to $v$. Therefore it
suffices to consider $u\in N(v)$. In this case, $Q(u)\cap c$ is just the
column of $c$ labeled by the edge $(u,v)$ and so $Q(u)\cap c$ is a local
codeword. Therefore $\sigma_{u}(c)=0$. It follows that

$\displaystyle\sigma_{u}(\varepsilon_{u}^{\prime})=\sigma_{u}(\varepsilon_{u})+\sigma_{u}(x)=\sigma_{u}(e)+\sigma_{u}(r)+\sigma_{u}(c)=\sigma_{u}(e)+\sigma_{u}(r)=\sigma_{u}(e+r)$
(57)

for all $u\in N(v)$. Therefore $\sigma_{u}(Z+x)=\sigma_{u}(e+f)$ for all $u\in
V_{10}$ and so $Z+x$ is associated with $e+f$. ∎

Lemma 4.7 and Lemma 4.8 show that $Z_{i}$ is a mismatch vector associated with
the $V_{10}$-weighted error $e_{i}$ for all $i$. We further cite the following
lemma from Ref. [33], which gives a sufficient condition for the existence of
good local corrections. This is the key to proving that in the noiseless case,
the sequential and parallel decoders converge.

######  Definition 4.9.

Let $Z$ be a mismatch vector and let $Z=C_{0}+C_{1}+R_{0}+R_{1}$ be a minimal
decomposition for $Z$. We say that a vertex $v\in V_{ij}$ is _active_ with
respect this decomposition if $Q(v)\cap(R_{i}+C_{j})\neq 0$.

######  Theorem 4.10 (Theorem 12 in Ref. [33]).

Fix $\delta\in(0,1)$. Let $Z$ be a non-zero mismatch vector. If for all
$i,j\in\\{0,1\\}$, the set of active vertices $S_{ij}\subseteq V_{ij}$ for a
minimal decomposition of $Z$ satisfies

$|S_{ij}|\leq\frac{1}{2^{12}}d_{r}^{2}\delta^{3}\kappa|V_{00}|\,,$ (58)

where $d_{r}$ denotes the relative distance of the local code, then there
exists a non-zero $x\subseteq Q(v)$ for some $v\in V_{ij}$ that is a
$C_{1}^{\perp}$ codeword such that

$|Z|-|Z+x|\geq(1-\delta)|x|\,.$ (59)

###  4.3 Sequential Decoder

To begin analyzing the sequential decoder with noisy input, the natural
question to ask is that if the ideal mismatch $Z$ can be decomposed by
Algorithm 2 into $\mathcal{F}=\\{x_{i}\\}_{i=1}^{t}$, how well do these local
corrections $x_{i}$ decompose the noisy mismatch $\tilde{Z}=Z+Z_{N}$? The
following two lemmas address this question.

######  Definition 4.11.

Let $Z$ be a mismatch vector. We say that $Z$ is _$\delta$ -decomposable_ if
Algorithm 2 successfully returns a decomposition of $Z$ when run with
parameter $\delta$, i.e., if Algorithm 2 halts with state $\hat{Z}=0$.

######  Lemma 4.12.

Let $Z$ be an $\delta$-decomposable mismatch and let
$\mathcal{F}=\\{x_{i}\\}_{i=1}^{t}$ denote the codewords returned by Algorithm
2 run with input $Z$ and parameter $\delta$. Then

$\displaystyle(1-\delta)\sum_{i=1}^{t}|x_{i}|\leq|Z|\leq\sum_{i=1}^{t}|x_{i}|\,.$
(60)

###### Proof.

Let

$\displaystyle Z_{k}=Z-\sum_{i=1}^{k}x_{i}\,,$ (61)

with $Z=Z_{0}$. Note that since Algorithm 2 completely decomposes $Z$, we have
$Z_{t}=0$ and

$\displaystyle Z=\sum_{i=1}^{t}x_{i}\,.$ (62)

For the decomposition with parameter $\delta$, we have
$|Z_{i-1}|-|Z_{i}|\geq(1-\delta)|x_{i}|$ and therefore

$|Z|\geq(1-\delta)\sum_{i=1}^{t}|x_{i}|\,.$ (63)

Together, we get the bounds

$\displaystyle(1-\delta)\sum_{i=1}^{t}|x_{i}|\leq|Z|\leq\sum_{i=1}^{t}|x_{i}|\,.$
(64)

∎

######  Lemma 4.13.

Let $Z$ be a mismatch vector and let $Z_{N}\in\mathbb{F}_{2}^{Q}$ be any
vector. Let $\tilde{Z}=Z+Z_{N}$. Suppose that $Z$ is $\delta$-decomposable
with decomposition $\mathcal{F}=\\{x_{i}\\}_{i=1}^{t}$. Let

$\mathcal{F}^{*}=\\{x\in\mathcal{F}:|\tilde{Z}|-|\tilde{Z}+x|\geq(1-\varepsilon)|x|\\}\,.$
(65)

Then

$\sum_{x\in\mathcal{F}^{*}}|x|\geq c_{1}|Z|-c_{2}|Z_{N}|$ (66)

for constants

$\displaystyle
c_{1}=\frac{\varepsilon-2\delta}{\varepsilon(1-\delta)}\quad\text{and}\quad
c_{2}=\frac{2}{\varepsilon}.$ (67)

In particular, if $\mathcal{F}^{*}=\emptyset$, then $c_{1}|Z|\leq
c_{2}|Z_{N}|$.

###### Proof.

This proof follows the idea of Lemma 5.1 in Ref. [42]. Given any set
$y\in\mathbb{F}_{2}^{Q}$, we have

$\displaystyle|\tilde{Z}|-|\tilde{Z}+y|$
$\displaystyle=|\tilde{Z}|-(|\tilde{Z}|+|y|-2|\tilde{Z}\cap
y|)=2|\tilde{Z}\cap y|-|y|\,.$ (68)

For all $y\in\mathcal{F}\setminus\mathcal{F}^{*}$, we have

$|\tilde{Z}\cap
y|=\frac{1}{2}(|y|+|\tilde{Z}|-|\tilde{Z}+y|)<\left(1-\frac{\varepsilon}{2}\right)|y|\,.$
(69)

Define $T=\sum_{x\in\mathcal{F}}|\tilde{Z}\cap x|$. We then have

$\displaystyle T$ $\displaystyle=\sum_{x\in\mathcal{F}^{*}}|\tilde{Z}\cap
x|+\sum_{y\in\mathcal{F}\setminus\mathcal{F}^{*}}|\tilde{Z}\cap y|$ (70)
$\displaystyle<\sum_{x\in\mathcal{F}^{*}}|x|+\left(1-\frac{\varepsilon}{2}\right)\sum_{y\in\mathcal{F}\setminus\mathcal{F}^{*}}|y|$
(71)
$\displaystyle=\frac{\varepsilon}{2}\sum_{x\in\mathcal{F}^{*}}|x|+\left(1-\frac{\varepsilon}{2}\right)\sum_{y\in\mathcal{F}}|y|$
(72)
$\displaystyle\leq\frac{\varepsilon}{2}\sum_{x\in\mathcal{F}^{*}}|x|+\frac{2-\varepsilon}{2(1-\delta)}|Z|\,,$
(73)

where the last inequality follows from Lemma 4.12. On the other hand, we also
have

$\displaystyle T$
$\displaystyle\geq|\tilde{Z}\cap\sum_{x\in\mathcal{F}}x|=|\tilde{Z}\cap Z|$
(74) $\displaystyle=|Z|-|Z\cap Z_{N}|\geq|Z|-|Z_{N}|\,.$ (75)

Combining these two inequalities, we get

$\displaystyle\frac{\varepsilon}{2}\sum_{x\in\mathcal{F}^{*}}|x|+\frac{2-\varepsilon}{2(1-\delta)}|Z|\geq|Z|-|Z_{N}|,$
(76)

or equivalently

$\displaystyle\sum_{x\in\mathcal{F}^{*}}|x|\geq\frac{\varepsilon-2\delta}{\varepsilon(1-\delta)}|Z|-\frac{2}{\varepsilon}|Z_{N}|,$
(77)

as desired. ∎

Note that Lemma 4.13 will set an implicit bound of $\delta<1/2$ since we
require $\varepsilon-2\delta>0$ for the bound (66) to be non-trivial.

Suppose now that the noisy mismatch vector $\tilde{Z}$ is given as input to
Algorithm 1 with parameter $\varepsilon$, which terminates after $T$
iterations. Let us denote the residual error by $\tilde{e}_{T}$ and its
associated mismatch by $\tilde{Z}_{T}=Z_{T}+Z_{N}$. If $Z_{T}$ is
$\delta$-decomposable, then Lemma 4.13 implies that $|Z_{T}|=O(Z_{N})$.
Namely, the sequential decoder terminates only when the mismatch noise $Z_{N}$
becomes significant. In the following lemma, we further relate the weight of
the noiseless residual error $e_{T}$ with $|Z_{T}|$.

######  Lemma 4.14 (Mismatch Correctness and Soundness).

Let $e$ be a $V_{10}$-weighted error and let $Z$ be an associated mismatch
vector. Suppose that $Z$ is $\delta$-decomposable and that

$\displaystyle~{}|e|_{R}+\frac{1}{\kappa(1-\delta)}|Z|<d\,.$ (78)

Then we have

$\displaystyle|Z|\geq(1-\delta)\kappa|e|_{R}\,.$ (79)

###### Proof.

Let $\mathcal{F}=\\{x_{i}\\}_{i=1}^{t}$ denote the decomposition returned for
$Z$ by Algorithm 2 with parameter $\delta$. Each $x_{i}$ is supported on the
local view of some vertex $v_{i}$ and has the further decomposition into
column and row codewords as $x_{i}=c_{i}+r_{i}$.

First, we prove that $e\cong\hat{C}_{1}+\hat{R}_{0}$, where $\cong$ denotes
equivalence up to stabilizers. Let $e_{0}=e$ and define $e_{i}=e_{i-1}+f_{i}$
where

$f_{i}=\begin{cases}0,&v\in V_{10}\,,\\\ x_{i},&v\in V_{01}\,,\\\ c_{i},&v\in
V_{11}\,,\\\ r_{i},&v\in V_{00}\,.\\\ \end{cases}$ (80)

Note that by construction we have

$\displaystyle e_{t}=e_{0}+\hat{C}_{1}+\hat{R}_{0}.$ (81)

By Lemma 4.8, the errors $e_{i}$ are all $V_{10}$-weighted, and the vector
$Z_{k}=Z+\sum_{i=1}^{k}x_{i}$ is a mismatch vector associated with $e_{i}$ at
each step. It follows by the $V_{10}$-weighting of $e_{t}$ that

$\displaystyle\forall v\in V_{01}:\quad\sigma_{v}(e_{t})=0.$ (82)

Since $Z_{t}=0$, it follows by the association of $Z_{t}$ and $e_{t}$ that

$\displaystyle\forall v\in V_{10}:\quad\sigma_{v}(e_{t})=\sigma_{v}(Z_{t})=0.$
(83)

It follows that $e_{t}$ has zero syndrome. It remains to show that $e_{t}$ is
a stabilizer, which we can do by bounding its weight. For each flip-set
$f_{i}$, we have

$\displaystyle|f_{i}|\leq|r_{i}|+|c_{i}|\leq\Delta(\|r_{i}\|+\|c_{i}\|)\leq|x_{i}|/\kappa\,,$
(84)

where we use the robustness of the local code in the last inequality. Using
Lemma 4.12, we then have

$\displaystyle|Z|\geq(1-\delta)\sum_{i=1}^{t}|x_{i}|\geq(1-\delta)\kappa\sum_{i=1}^{t}|f_{i}|.$
(85)

It follows that

$\displaystyle|e_{t}|_{R}=\left|e+\sum_{i=1}^{t}f_{i}\right|_{R}\leq|e|_{R}+\sum_{i=1}^{t}|f_{i}|\leq|e|_{R}+\frac{1}{\kappa(1-\delta)}|Z|<d.$
(86)

Therefore $e_{t}\cong 0$ and hence $e\cong\hat{C}_{1}+\hat{R}_{0}$. Finally,
we have

$\displaystyle|e|_{R}=\left|\hat{C}_{1}+\hat{R}_{0}\right|_{R}\leq\left|\hat{C}_{1}+\hat{R}_{0}\right|\leq\sum_{i=1}^{t}|f_{i}|\leq\frac{1}{\kappa(1-\delta)}|Z|.$
(87)

∎

Now we show that, without surprise, $Z_{T}$ is $\delta$-decomposable. Let us
define the constants

$\displaystyle A_{\varepsilon}$
$\displaystyle=\frac{24}{\kappa\Delta(1-\varepsilon)},\quad
B_{\varepsilon}=\frac{3\Delta}{\kappa(1-\varepsilon)},\quad\text{and}\quad
C_{\delta}=\frac{1}{2^{12}}d_{r}^{2}\delta^{3}\kappa\Delta^{-2}\,.$ (88)

For the purposes of the parallel decoder, it will be convenient to consider a
generalized mismatch decomposition procedure which initially starts the
decomposition with some weight parameter $\varepsilon$ and then switches to
some other parameter $\varepsilon^{\prime}$ partway through (see Lemma 4.18).
We state the generalized result below in Lemma 4.15, although we will only
need the special case where $\varepsilon=\varepsilon^{\prime}$ for the
analysis of the sequential decoder.

######  Lemma 4.15.

Let $e$ be an error and $D$ a syndrome noise. Let $\tilde{Z}\equiv Z+Z_{N}$
denote the initial noisy mismatch vector assigned to $e$ and $D$.

Let $\varepsilon,\varepsilon^{\prime}\in(0,1)$ be constants such that
$\varepsilon^{\prime}\leq\varepsilon$. Consider a modified Algorithm 2 which
takes input $\tilde{Z}$ and runs with parameter $\varepsilon$ for the first
$t$ steps and then switches to parameter $\varepsilon^{\prime}$ until it halts
at step $T\geq t$. Let $\tilde{Z}_{T}\equiv Z_{T}+Z_{N}$ denote the final
output of this process.

If $A_{\varepsilon}|e|_{R}+B_{\varepsilon}|D|_{V}\leq C_{\delta}n$, then
$Z_{T}$ is $\delta$-decomposable.

###### Proof.

Consider the process of running the modified Algorithm 2 with input
$\tilde{Z}$ and parameter $\varepsilon$ for $t$ steps, and then switching the
parameter to $\varepsilon^{\prime}$ until the algorithm finally halts at step
$T$. Let $\\{x_{1},\dots,x_{t}\\}$ be local codewords obtained with parameter
$\varepsilon$, and $\\{x_{t+1},\dots,x_{T}\\}$ the codewords obtained with
parameter $\varepsilon^{\prime}$. Denoting $\tilde{Z}_{i}$ the mismatch vector
at iteration $i$, we have

$\displaystyle|\tilde{Z}_{i-1}|-|\tilde{Z}_{i}|\geq\begin{cases}(1-\varepsilon)|x_{i}|,&i\in\\{1,\dots,t\\}\,,\\\
(1-\varepsilon^{\prime})|x_{i}|,&i\in\\{t+1,\dots,T\\}\ .\end{cases}$ (89)

We wish to show that $Z_{T}$ is $\delta$-decomposable. Suppose that Algorithm
2 returns local codewords $\\{y_{1},\dots,y_{K}\\}$ when given input $Z_{T}$
with parameter $\delta$. Let $S_{T+k,ij}$ denote a set of active vertices in
$V_{ij}$ for the mismatch

$\displaystyle Z_{T+k}\equiv Z_{T}+\sum_{\ell=1}^{k}y_{\ell}\,.$ (90)

For all $k\in[K]$, we have

$\displaystyle|S_{T+k,ij}|$
$\displaystyle\leq\|Z_{T+k}\|\leq\|Z\|+\sum_{i=1}^{T}\|x_{i}\|+\sum_{\ell=1}^{k}\|y_{\ell}\|\,,$
(91)

where the first inequality holds since there exists at least one non-zero row
or column for each active vertex. By robustness of the local code, we have
$\kappa\Delta\|x_{i}\|\leq|x_{i}|$. Continuing the chain of inequalities, we
have

$\displaystyle\eqref{ineq:1}$
$\displaystyle\leq\|Z\|+\frac{1}{\kappa\Delta}\sum_{i=1}^{T}|x_{i}|+\frac{1}{\kappa\Delta}\sum_{\ell=1}^{k}|y_{\ell}|$
(92)
$\displaystyle\leq\|Z\|+\frac{1}{\kappa\Delta}\sum_{i=1}^{T}|x_{i}|+\frac{1}{\kappa\Delta(1-\delta)}|Z_{T}|\,,$
(93)

where the first inequality follows by robustness and the second by the fact
that $|Z_{T+\ell-1}|-|Z_{T+\ell-1}+y_{\ell}|\geq(1-\delta)|y_{\ell}|$. Using
inequality (89), we get

$\displaystyle|Z_{T}|=\left|Z+\sum_{i=1}^{T}x_{i}\right|\leq|Z|+\sum_{i=1}^{T}|x_{i}|\leq|Z|+\frac{1}{1-\varepsilon}\left(|\tilde{Z}|-|\tilde{Z}_{t}|\right)+\frac{1}{1-\varepsilon^{\prime}}\left(|\tilde{Z}_{t}|-|\tilde{Z}_{T}|\right).$
(94)

Since $\varepsilon^{\prime}\leq\varepsilon$, it follows that

$\displaystyle|Z_{T}|\leq|Z|+\frac{1}{1-\varepsilon}|\tilde{Z}|.$ (95)

Inserting (95) into (93), we get

$\displaystyle|S_{T+k,ij}|$
$\displaystyle\leq\|Z\|+\frac{1}{\kappa\Delta(1-\delta)}|Z|+\frac{1}{\kappa\Delta(1-\varepsilon)}\left(\frac{2-\delta}{1-\delta}\right)|\tilde{Z}|$
(96)
$\displaystyle\leq\|Z\|+\frac{1}{\kappa\Delta(1-\delta)}|Z|+\frac{1}{\kappa\Delta(1-\varepsilon)}\left(\frac{2-\delta}{1-\delta}\right)(|Z|+|Z_{N}|)$
(97)
$\displaystyle\leq\frac{4}{\kappa\Delta}|e|_{R}+\frac{4}{\kappa\Delta(1-\delta)}|e|_{R}+\frac{1}{\kappa\Delta(1-\varepsilon)}\left(\frac{2-\delta}{1-\delta}\right)(4|e|_{R}+\Delta^{2}|D|_{V})\,,$
(98)

where the last inequality follows by applying Lemma 4.5, together with the
fact that $\varepsilon_{v}(D)$ can be non-zero only when $v$ is in the support
of $D$ and hence

$\displaystyle|Z_{N}|=\left|\sum_{v\in
V_{1}}\varepsilon_{v}(D)\right|\leq\sum_{v\in
V_{1}}\left|\varepsilon_{v}(D)\right|\leq|D|_{V}\max_{v\in
V_{1}}|\varepsilon_{v}(D)|\leq|D|_{V}\Delta^{2}.$ (99)

Simplifying, we finally get

$\displaystyle|S_{T+k,ij}|$
$\displaystyle\leq\frac{4}{\kappa\Delta}\left(\frac{2-\delta}{1-\delta}\right)\left(\frac{2-\varepsilon}{1-\varepsilon}\right)|e|_{R}+\frac{\Delta}{\kappa(1-\varepsilon)}\left(\frac{2-\delta}{1-\delta}\right)|D|_{V}$
(100)
$\displaystyle\leq\frac{12}{\kappa\Delta}\left(\frac{2}{1-\varepsilon}\right)|e|_{R}+\frac{3\Delta}{\kappa(1-\varepsilon)}|D|_{V}$
(101) $\displaystyle\equiv A_{\varepsilon}|e|_{R}+B_{\varepsilon}|D|_{V},$
(102)

where we use the fact that $(2-\delta)/(1-\delta)\leq 3$ for
$\delta\in(0,1/2)$. It follows that if we have
$A_{\varepsilon}|e|_{R}+B_{\varepsilon}|D|_{V}\leq C_{\delta}n$, then the
active vertex condition of Theorem 4.10 is always satisfied so that Algorithm
2 must be able to completely decompose $Z_{T}$. ∎

It remains for us to check that (78) in Lemma 4.14 holds.

######  Lemma 4.16.

Assume the hypotheses of Lemma 4.15, and furthermore that

$\displaystyle
A_{\varepsilon}|e|_{R}+B_{\varepsilon}|D|_{V}\leq\frac{d}{\Delta}.$ (103)

Then

$\displaystyle|Z_{T}|\geq(1-\delta)\kappa|e_{T}|_{R}.$ (104)

###### Proof.

By Lemmas 4.7 and 4.8, the error $e_{T}$ is $V_{10}$-weighted and $Z_{T}$ is
an associated mismatch vector. Applying Lemma 4.14, it suffices to prove

$\displaystyle|e_{T}|_{R}+\frac{1}{\kappa(1-\delta)}|Z_{T}|<d\ .$ (105)

We have

$\displaystyle|e_{T}|_{R}$
$\displaystyle=\left|e_{0}+\sum_{i=1}^{T}f_{i}\right|_{R}\leq|e_{0}|_{R}+\sum_{i=1}^{T}|f_{i}|\leq|e_{0}|_{R}+\frac{1}{\kappa}\sum_{i=1}^{T}|x_{i}|\leq|e_{0}|_{R}+\frac{1}{\kappa(1-\varepsilon)}|\tilde{Z}|,$
(106)

where the second inequality follows from (84). We then get

$\displaystyle|e_{T}|_{R}+\frac{1}{\kappa(1-\delta)}|Z_{T}|$
$\displaystyle\leq|e_{0}|_{R}+\frac{1}{\kappa(1-\varepsilon)}|\tilde{Z}|+\frac{1}{\kappa(1-\delta)}|Z_{T}|$
(107)
$\displaystyle\leq|e_{0}|_{R}+\frac{1}{\kappa(1-\varepsilon)}|\tilde{Z}|+\frac{1}{\kappa(1-\delta)}\left(|Z|+\frac{1}{1-\varepsilon}|\tilde{Z}|\right)$
(108)
$\displaystyle=|e_{0}|_{R}+\frac{1}{\kappa(1-\delta)}|Z|+\frac{1}{\kappa(1-\varepsilon)}\left(1+\frac{1}{1-\delta}\right)|\tilde{Z}|\,,$
(109)

where we use (95) in the second inequality. Next, we may assume without loss
of generality that $e$ is a reduced error. Then we have

$|e_{0}|_{R}=|\tilde{e}_{0}+Z_{N}^{01}|_{R}=\big{|}e+\sum_{v\in
V_{01}}\varepsilon_{v}\big{|}_{R}\leq|e|+\sum_{v\in
V_{01}}|e_{v}|=2|e|=2|e|_{R}\,,$ (110)

where we use the fact that $\varepsilon_{v}$ are minimum weight corrections in
the inequality above and the fact that $e_{u}\cap e_{v}=\emptyset$ for
distinct vertices $u,v\in V_{01}$ in the second last equality. Following the
same steps as from (96) to (98), we therefore get

$\displaystyle|e_{T}|_{R}+\frac{1}{\kappa(1-\delta)}|Z_{T}|$
$\displaystyle\leq
2|e|_{R}+\frac{4}{\kappa(1-\delta)}|e|_{R}+\frac{1}{\kappa(1-\varepsilon)}\left(1+\frac{1}{1-\delta}\right)(4|e|_{R}+\Delta^{2}|D|_{V})$
(111)
$\displaystyle\leq\left[2+\frac{4}{\kappa(1-\varepsilon)}\left(1+\frac{2-\varepsilon}{1-\delta}\right)\right]|e|_{R}+\Delta
B_{\varepsilon}|D|_{V}.$ (112)

We can simplify the inequality above by noting that $\kappa\leq d_{r}\leq 1$
[36]. Then we have

$\displaystyle
2+\frac{4}{\kappa(1-\varepsilon)}\left(1+\frac{2-\varepsilon}{1-\delta}\right)$
$\displaystyle=\frac{1}{\kappa}\left[2\kappa+\frac{4}{1-\varepsilon}\left(1+\frac{2-\varepsilon}{1-\delta}\right)\right]$
(113)
$\displaystyle\leq\frac{1}{\kappa}\left[4+\frac{4}{1-\varepsilon}\left(1+\frac{2-\varepsilon}{1-\delta}\right)\right]$
(114)
$\displaystyle=\frac{4}{\kappa}\left(\frac{2-\delta}{1-\delta}\right)\left(\frac{2-\varepsilon}{1-\varepsilon}\right)$
(115) $\displaystyle\leq\frac{24}{\kappa(1-\varepsilon)}=\Delta
A_{\varepsilon}.$ (116)

Therefore it suffices to require

$\displaystyle
A_{\varepsilon}|e|_{R}+B_{\varepsilon}|D|_{V}\leq\frac{d}{\Delta}$ (117)

in order that inequality (105) holds. ∎

Combining the inequalities, we obtain the main result for sequential decoder.

######  Theorem 4.17 (Main Theorem for the Sequential Decoder).

Let $e$ be an error and let $D$ be a syndrome error. Suppose that

$\displaystyle A_{\varepsilon}|e|_{R}+B_{\varepsilon}|D|_{V}$
$\displaystyle\leq\min\left(C_{\delta}n,d/\Delta\right)\,.$ (118)

Let $\tilde{\sigma}=\sigma(e)+D$. Then Algorithm 1 with input $\tilde{\sigma}$
and parameter $\varepsilon$ will output a correction $\hat{f}$ satisfying

$\displaystyle|e+\hat{f}|_{R}\leq\left(1+\frac{2c_{2}}{\kappa
c_{1}}\right)\Delta^{2}|D|_{V}.$ (119)

###### Proof.

Suppose that Algorithm 1 with parameter $\varepsilon$ terminates after $T$
steps with output $\hat{f}$. Let $Z_{T}$ denote the state of the mismatch
after the algorithm terminates. By Lemma 4.15, $Z_{T}$ is
$\delta$-decomposable. This allows us to apply Lemma 4.13, giving

$0\geq c_{1}|Z_{T}|-c_{2}|Z_{N}|\,,$ (120)

since the set $\mathcal{F}^{*}$ must be empty when Algorithm 1 with parameter
$\varepsilon$ terminates. By Lemma 4.16, we get

$|Z_{T}|\geq(1-\delta)\kappa|e_{T}|_{R}\,.$ (121)

But we know

$\displaystyle|e_{T}|_{R}$
$\displaystyle=|\tilde{e}_{T}+Z_{N}^{01}|_{R}\geq|\tilde{e}_{T}|_{R}-|Z_{N}^{01}|_{R}\geq|\tilde{e}_{T}|_{R}-\Delta^{2}|D|_{V}\,.$
(122)

Combining the inequalities (120), (121), and (122) finally gives

$\displaystyle|e+\hat{f}|_{R}$ $\displaystyle=|\tilde{e}_{T}|_{R}$ (123)
$\displaystyle\leq|e_{T}|_{R}+\Delta^{2}|D|_{V}$ (124)
$\displaystyle\leq\frac{1}{(1-\delta)\kappa}|Z_{T}|+\Delta^{2}|D|_{V}$ (125)
$\displaystyle\leq\frac{c_{2}}{c_{1}(1-\delta)\kappa}|Z_{N}|+\Delta^{2}|D|_{V}$
(126)
$\displaystyle\leq\left(1+\frac{c_{2}}{c_{1}(1-\delta)\kappa}\right)\Delta^{2}|D|_{V}\,.$
(127)

Note that the restriction $\delta<1/2$, as required by Lemma 4.13, implies
that $(1-\delta)^{-1}\leq 2$. ∎

This completes our proof of the main theorem for the sequential decoder.

###  4.4 Parallel Decoder

The key idea in analyzing the parallel decoder is to compare the performance
of one iteration of parallel decoding to that of a full execution of the
sequential decoder. Our convention in this section will be that superscript
indices will denote the parallel decoding iteration (always with parameter
$1/2$), while subscript indices will denote the sequential decoding iteration.
For example, $\tilde{Z}^{(k)}_{j}$ denotes the mismatch obtained after $k$
iterations of parallel decoding and then $j$ iterations of sequential
decoding.

For convenience, we will fix some parameters in this section. Throughout, we
will take $\varepsilon=1/2$ for the parallel decoder. We will write
$A=A_{\varepsilon=1/2}$ and $B=B_{\varepsilon=1/2}$.

######  Lemma 4.18.

Let $\varepsilon^{\prime}\in(0,1/6)$. Let $\tilde{Z}^{(k)}$ denote the current
state of the (noisy) mismatch vector. Let $\tilde{Z}_{T}^{(k)}$ denote the
residual mismatch after running the sequential decoder with input
$\tilde{Z}^{(k)}$ and parameter $\varepsilon^{\prime}$. Then after one
iteration of parallel decoding, the weight of the mismatch is reduced by at
least

$\displaystyle|\tilde{Z}^{(k)}|-|\tilde{Z}^{(k+1)}|\geq\frac{1}{16}(1-6\varepsilon^{\prime})\left(|\tilde{Z}^{(k)}|-|\tilde{Z}_{T}^{(k)}|\right).$
(128)

###### Proof.

The proof closely follows the ideas of Lemma 18 in Ref. [33]. For ease of
notation we write $\tilde{Z}^{(k)}$ as $\tilde{Z}$ throughout this proof.
Suppose that Algorithm 2 runs with input $\tilde{Z}$ and parameter
$\varepsilon^{\prime}$ returns local codewords $\\{x_{i}\\}_{i=1}^{T}$ and
residual mismatch $\tilde{Z}_{T}$. Therefore we can write

$\displaystyle\tilde{Z}=\sum_{i=1}^{T}x_{i}+\tilde{Z}_{T}\,.$ (129)

We will analyze the overlap among the sets $x_{i}$, and argue that the
parallel decoder’s output will intersect non-trivially with the sequential
decoder’s output. Let us define the sets

$\displaystyle x_{i}^{\prime}=\left(\tilde{Z}\cap
x_{i}\right)\setminus\bigcup_{j<i}x_{j}\,.$ (130)

Note that the sets $x_{i}^{\prime}$ are disjoint, and that they satisfy

$\displaystyle\bigcup_{i=1}^{T}x_{i}^{\prime}=\tilde{Z}\cap\bigcup_{i=1}^{T}x_{i}\supseteq\tilde{Z}\cap\sum_{i=1}^{T}x_{i}\,,$
(131)

which implies

$\displaystyle\left|\tilde{Z}\setminus\bigcup_{i=1}^{T}x_{i}^{\prime}\right|\leq\left|\tilde{Z}\setminus\left(\tilde{Z}\cap\sum_{i=1}^{T}x_{i}\right)\right|=\left|\tilde{Z}\setminus\sum_{i=1}^{T}x_{i}\right|\leq\left|\tilde{Z}+\sum_{i=1}^{T}x_{i}\right|=|\tilde{Z}_{T}|\,.$
(132)

Next, we define the set of “good” indices $G\subseteq[T]$ such that $i\in G$
if and only if

$\displaystyle|x_{i}^{\prime}|\geq\left(1-\frac{3}{2}\varepsilon^{\prime}\right)|x_{i}|\,.$
(133)

Let $B=[T]\setminus G$ denote the remaining set of “bad” indices. For each
$j\in[T]$, let us define

$\displaystyle\tilde{Z}^{\prime}_{j}=\tilde{Z}\setminus\bigcup_{i\leq
j}x_{i}^{\prime}=\tilde{Z}^{\prime}_{j-1}\setminus x_{j}^{\prime}\,.$ (134)

We wish to bound the difference between $\tilde{Z}_{j}$ and
$\tilde{Z}_{j}^{\prime}$. Let us denote this difference by

$\displaystyle A_{j}=\tilde{Z}_{j}\setminus\tilde{Z}_{j}^{\prime}\,.$ (135)

To bound the size of $A_{j}$, we examine how the size of $\tilde{Z}$ changes
as we update it by adding codewords $x_{j}$. Since the $x_{j}$’s were obtained
by running the decoder with parameter $\varepsilon^{\prime}$, it follows that

$\displaystyle|\tilde{Z}_{j-1}\cap
x_{j}|\geq(1-\varepsilon^{\prime}/2)|x_{j}|\,.$ (136)

${\color[rgb]{0.29,0.56,0.89}\definecolor[named]{pgfstrokecolor}{rgb}{0.29,0.56,0.89}\tilde{Z}}{\color[rgb]{0.29,0.56,0.89}{}_{j-1}}$${\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}x}{\color[rgb]{0.82,0.01,0.11}{}_{j}}$$\mathrm{II}$$\mathrm{I}$$\mathrm{III}$$\mathrm{IV}$$\mathrm{V}$
Figure 3: Reference for sets involved in proof of Lemma 4.18. The regions
indicated are: $\mathrm{II}\cup\mathrm{IV}=\tilde{Z}^{\prime}_{j-1}$,
$\mathrm{I}\cup\mathrm{III}=A_{j-1}$, $\mathrm{II}=\tilde{Z}^{\prime}_{j}$,
$\mathrm{IV}=x_{j}^{\prime}$, $\mathrm{III}\cup\mathrm{IV}=\tilde{Z}_{j-1}\cap
x_{j}$, $\mathrm{I}\cup\mathrm{V}=A_{j}$, and
$\mathrm{I}\cup\mathrm{II}\cup\mathrm{V}=\tilde{Z}_{j}.$

Referring to Figure 3, we have $A_{j}\setminus
A_{j-1}=x_{j}\setminus\tilde{Z}_{j-1}$, and hence

$\displaystyle|A_{j}\setminus
A_{j-1}|=|x_{j}\setminus\tilde{Z}_{j-1}|=|x_{j}|-|x_{j}\cap\tilde{Z}_{j-1}|\leq|x_{j}|-\left(1-\frac{\varepsilon^{\prime}}{2}\right)|x_{j}|=\frac{\varepsilon^{\prime}}{2}|x_{j}|\,.$
(137)

We also have

$\displaystyle(A_{j-1}\setminus A_{j})\sqcup
x_{j}^{\prime}=\tilde{Z}_{j-1}\cap x_{j}\,,$ (138)

corresponding to the unions of regions $\mathrm{III}$ and $\mathrm{IV}$ in
Figure 3. If $j\in B$ is a “bad” index, then we have

$\displaystyle|A_{j-1}\setminus
A_{j}|+\left(1-\frac{3}{2}\varepsilon^{\prime}\right)|x_{j}|>|A_{j-1}\setminus
A_{j}|+|x_{j}^{\prime}|=|\tilde{Z}_{j-1}\cap
x_{j}|\geq\left(1-\frac{\varepsilon^{\prime}}{2}\right)|x_{j}|\,,$ (139)

where the first inequality follows from the fact that $j\in B$ and the last
from the decoding condition with parameter $\varepsilon^{\prime}$. It follows
that

$\displaystyle|A_{j-1}\setminus A_{j}|\geq\varepsilon^{\prime}|x_{j}|,$ (140)

and hence

$\displaystyle|A_{j-1}|-|A_{j}|=|A_{j-1}\setminus A_{j}|-|A_{j}\setminus
A_{j-1}|\geq\varepsilon^{\prime}|x_{j}|-\frac{\varepsilon^{\prime}}{2}|x_{j}|=\frac{\varepsilon^{\prime}}{2}|x_{j}|\,,$
(141)

where we use inequalities (137) and (140) above. It follows that we have

$\begin{cases}|A_{j}|-|A_{j-1}|\leq\ \ \varepsilon^{\prime}|x_{j}|/2,&\forall
j\in G\,,\\\ |A_{j}|-|A_{j-1}|\leq-\varepsilon^{\prime}|x_{j}|/2,&\forall j\in
B\,.\end{cases}$ (142)

Summing the inequalities above, we get

$\displaystyle
0\leq|A_{T}|-|A_{0}|=\sum_{j=1}^{T}\left(|A_{j}|-|A_{j-1}|\right)\leq\frac{\varepsilon^{\prime}}{2}\left(\sum_{j\in
G}|x_{j}|-\sum_{j\in B}|x_{j}|\right)\,,$ (143)

where $|A_{0}|=0$ by definition. Therefore

$\displaystyle\sum_{j\in B}|x_{j}|\leq\sum_{j\in G}|x_{j}|\,.$ (144)

We have

$\displaystyle\sum_{j\in
B}|x_{j}^{\prime}|\leq\left(1-\frac{3}{2}\varepsilon^{\prime}\right)\sum_{j\in
B}|x_{j}|\leq\left(1-\frac{3}{2}\varepsilon^{\prime}\right)\sum_{j\in
G}|x_{j}|\leq\sum_{j\in G}|x_{j}^{\prime}|\,,$ (145)

and hence

$\displaystyle|\tilde{Z}|-|\tilde{Z}_{T}|\leq\left|\bigcup_{j=1}^{T}x_{j}^{\prime}\right|=\sum_{j=1}^{T}|x_{j}^{\prime}|=\sum_{j\in
B}|x_{j}^{\prime}|+\sum_{j\in G}|x_{j}^{\prime}|\leq 2\sum_{j\in
G}|x_{j}^{\prime}|\,.$ (146)

Now, consider the iteration of parallel decoding beginning with input
$\tilde{Z}\equiv\tilde{Z}^{(k)}$. Let $u\in\mathbb{F}_{2}^{Q}$ denote the set
of all qubits which have been acted on by the parallel decoder, i.e.,

$\displaystyle u=\bigcup_{z_{v}\in\mathcal{F}}z_{v}\,,$ (147)

where $\mathcal{F}=\\{z_{v}\\}$ is the collection of all local codewords found
by the decoder in the current iteration. We now prove that for all $j\in G$,
we have $|x_{j}\cap u|\geq c|x_{j}|$ for some constant $c>0$.

Fix some $x_{j}$ and let $v$ denote its anchoring vertex. Let us write
$y=|x_{j}^{\prime}\cap u|$. First, let us show that we must have

$\displaystyle|x_{j}^{\prime}\setminus u|<\frac{3}{4}|x_{j}|\,.$ (148)

Suppose otherwise. Then let $z_{v}$ denote the codeword (possibly zero) that
the parallel decoder assigns to vertex $v$. Note that we have $z_{v}\subseteq
u$ by definition, as well as

$\displaystyle|\overline{Z}|-|\overline{Z}+z_{v}|\geq\frac{1}{2}|z_{v}|\,,$
(149)

where $\overline{Z}$ denotes the current state of the noisy mismatch in the
parallel decoder. By definition of $u$ as the execution support of the
decoder, the qubits of $x_{j}^{\prime}\setminus u$ are untouched by the
algorithm. Therefore, since $x_{j}^{\prime}\subseteq\tilde{Z}$, it follows
that $x_{j}^{\prime}\setminus u\subseteq\overline{Z}$ and
$x_{j}^{\prime}\setminus u\subseteq\overline{Z}+z_{v}$. Therefore we have

$\displaystyle x_{j}^{\prime}\setminus u=x_{j}^{\prime}\setminus
u\cap(\overline{Z}+z_{v})\subseteq x_{j}\cap(\overline{Z}+z_{v})\,.$ (150)

The addition of $x_{j}$ to $\overline{Z}+z_{v}$ therefore removes at least
$|x_{j}^{\prime}\setminus u|\geq\frac{3}{4}|x_{j}|$ qubits from
$\overline{Z}$. Consequently, the addition of $x_{j}$ to $\overline{Z}+z_{v}$
can add at most $|x_{j}|/4$ qubits, so that

$\displaystyle|\overline{Z}+z_{v}|-|\overline{Z}+z_{v}+x_{j}|\geq\frac{1}{2}|x_{j}|\,.$
(151)

Adding this inequality to (149), we get

$\displaystyle|\overline{Z}|-|\overline{Z}+z_{v}+x_{j}|\geq\frac{1}{2}(|x_{j}|+|z_{v}|)\geq\frac{1}{2}|z_{v}+x_{j}|\,.$
(152)

Similar to the argument above, the addition of $x_{j}$ to $z_{v}$ adds at
least $|x_{j}\setminus z_{v}|\geq|x_{j}^{\prime}\setminus u|\geq 3|x_{j}|/4$
qubits, and hence removes at most $|x_{j}|/4$ qubits. Therefore

$\displaystyle|z_{v}+x_{j}|-|z_{v}|\geq\frac{1}{2}|x_{j}|\,.$ (153)

Since $|z_{v}+x_{j}|>|z_{v}|$, this contradicts the assumption that $z_{v}$ is
the local codeword selected by the decoder, since the decoder will choose to
maximize the Hamming weight of its local codewords. It follows that we’ve
established the inequality

$\displaystyle|x_{j}^{\prime}\setminus u|<\frac{3}{4}|x_{j}|\,.$ (154)

This then implies that for all $j\in G$, we have

$\displaystyle|x_{j}^{\prime}\cap
u|>|x_{j}^{\prime}|-\frac{3}{4}|x_{j}|\geq\left(1-\frac{3}{2}\varepsilon^{\prime}\right)|x_{j}|-\frac{3}{4}|x_{j}|=\left(\frac{1}{4}-\frac{3}{2}\varepsilon^{\prime}\right)|x_{j}|\,.$
(155)

Since the $x_{j}^{\prime}$ are disjoint, we get

$\displaystyle|u|\geq\sum_{j\in G}|x_{j}^{\prime}\cap
u|>\left(\frac{1}{4}-\frac{3}{2}\varepsilon^{\prime}\right)\sum_{j\in
G}|x_{j}|\geq\left(\frac{1}{4}-\frac{3}{2}\varepsilon^{\prime}\right)\sum_{j\in
G}|x_{j}^{\prime}|\geq\frac{1}{8}\left(1-6\varepsilon^{\prime}\right)\left(|\tilde{Z}|-|\tilde{Z}_{T}|\right)\,,$
(156)

where the last inequality follows from (146). Finally, by the decoding
criterion (149), the total decrease in mismatch weight is

$\displaystyle|\tilde{Z}^{(k)}|-|\tilde{Z}^{(k+1)}|\geq\frac{1}{2}\sum_{z_{v}\in\mathcal{F}}|z_{v}|\geq\frac{1}{2}|u|\geq\frac{1}{16}(1-6\varepsilon^{\prime})\left(|\tilde{Z}^{(k)}|-|\tilde{Z}_{T}^{(k)}|\right),$
(157)

where we restore the superscript $(k)$ in this last inequality for clarity. ∎

Now, as in the sequential case, we bound the weight of the residual mismatch
by the weight of measurement noise.

######  Lemma 4.19.

Let $e$ be an error and $D$ be a syndrome noise. Let $\tilde{Z}$ be the
initial mismatch vector assigned to $e$ and $D$. Let $\tilde{Z}^{(k)}$ denote
the state of the mismatch vector after $k$ iterations of parallel decoding.
Let $\tilde{Z}^{(k)}_{T}$ denote the residual mismatch vector obtained by
running the sequential decoder with input $\tilde{Z}^{(k)}$ and parameter
$\varepsilon^{\prime}$.

Suppose that $A|e|_{R}+B|D|_{V}\leq C_{\delta}n$. Then for all
$k\in\mathbb{N}^{+}$ we have

$\displaystyle|\tilde{Z}_{T}^{(k)}|\leq\left(1+\frac{2(1-\delta)}{\varepsilon^{\prime}-2\delta}\right)\Delta^{2}|D|_{V}\equiv(1+\zeta)\Delta^{2}|D|_{V}\,.$
(158)

###### Proof.

Suppose that $\mathcal{F}=\\{x_{i}\\}_{i=1}^{K}$ are the codewords which have
been found by the parallel decoder after $k$ iterations. Note that we can
equivalently consider the same sequence to be obtained by running the
sequential decoder with parameter $1/2$, i.e., we can consider
$\tilde{Z}^{(k)}$ to be a state of the mismatch after $K$ iterations of
sequential decoding with parameter $1/2$. It follows that
$\tilde{Z}_{T}^{(k)}$ is a mismatch obtained by first running the sequential
decoder with input $\tilde{Z}$ and parameter $1/2$ for $K$ iterations, and
then switching to parameter $\varepsilon^{\prime}$ for the remaining
iterations.

Applying Lemma 4.15 with $\varepsilon=1/2$, our assumptions on $|e|_{R}$ and
$|D|_{V}$ imply that $Z^{(k)}_{T}$ is $\delta$-decomposable. Next, applying
Lemma 4.13 (with $\varepsilon^{\prime}$ as $\varepsilon$), it follows that

$\displaystyle|Z_{T}^{(k)}|\leq\frac{2(1-\delta)}{\varepsilon^{\prime}-2\delta}|Z_{N}|\,.$
(159)

We then have

$\displaystyle|\tilde{Z}_{T}^{(k)}|=|Z_{T}^{(k)}+Z_{N}|\leq|Z_{T}^{(k)}|+|Z_{N}|\leq\left(1+\frac{2(1-\delta)}{\varepsilon^{\prime}-2\delta}\right)|Z_{N}|\leq\left(1+\frac{2(1-\delta)}{\varepsilon^{\prime}-2\delta}\right)\Delta^{2}|D|_{V}.$
(160)

∎

For simplicity, we take $\varepsilon^{\prime}=3\delta$ in the following
theorem. Note that this sets an upper bound on $\delta$ so that $\delta<1/18$.

######  Theorem 4.20 (Main Theorem for the Parallel Decoder).

Let $e$ be an error and $D$ be a syndrome error. Let $\tilde{Z}$ be the
initial (noisy) mismatch associated with $e$ and $D$. Assume that

$\displaystyle A|e|_{R}+B|D|_{V}$
$\displaystyle\leq\min\left(C_{\delta}n,d/\Delta\right)\,.$ (161)

Then after $k$ iterations of parallel decoding, the decoder returns a
correction $\hat{f}^{(k)}$ such that

$\displaystyle|e+\hat{f}^{(k)}|_{R}\leq\alpha_{k}|e|_{R}+\beta|D|_{V}\,,$
(162)

where

$\displaystyle\alpha_{k}=\frac{24}{5\kappa}(1-\gamma)^{k},\quad\beta=\frac{6}{\kappa\delta}\Delta^{2},\quad\text{and}\quad\gamma=(1-18\delta)/16\,.$
(163)

###### Proof.

Applying Lemmas 4.18 and 4.19, it follows that the mismatch after $k$
iterations of parallel decoding is bounded above as

$\displaystyle|\tilde{Z}^{(k)}|\leq\left(1-\gamma\right)|\tilde{Z}^{(k-1)}|+\gamma(1+\zeta)\Delta^{2}|D|_{V}\,.$
(164)

Summing this inequality over $k$ gives

$\displaystyle|\tilde{Z}^{(k)}|$
$\displaystyle\leq(1-\gamma)^{k}|\tilde{Z}|+\gamma(1+\zeta)\Delta^{2}|D|_{V}\left(1+(1-\gamma)+(1-\gamma)^{2}+\ldots+(1-\gamma)^{k-1}\right)$
(165)
$\displaystyle\leq(1-\gamma)^{k}|\tilde{Z}|+(1+\zeta)\Delta^{2}|D|_{V}\,.$
(166)

Next, let $\tilde{e}^{(k)}$ denote the state of the error after $k$ iterations
of parallel decoding. Let $\tilde{e}^{(k)}_{T}$ denote the state of the error
after $T$ additional iterations of sequential decoding with parameter
$\varepsilon^{\prime}$. Let us write

$\displaystyle\tilde{e}^{(k)}_{T}=\tilde{e}^{(k)}+\sum_{i=1}^{T}f_{i},$ (167)

where $\\{f_{i}\\}_{i=1}^{T}$ are the associated flip-sets with parameter
$\varepsilon^{\prime}$. It follows from Lemma 4.8 that ${e}^{(k)}_{T}$ is
$V_{10}$-weighted with associated mismatch ${Z}^{(k)}_{T}$. Lemma 4.16 then
implies that

$\displaystyle|{e}^{(k)}_{T}|_{R}\leq\frac{1}{(1-\delta)\kappa}|Z^{(k)}_{T}|\leq\frac{\zeta}{(1-\delta)\kappa}|Z_{N}|\leq\frac{\zeta}{(1-\delta)\kappa}\Delta^{2}|D|_{V}.$
(168)

It remains to bound the weight of $|\tilde{e}^{(k)}|_{R}$. We have

$\displaystyle|\tilde{e}^{(k)}|_{R}$
$\displaystyle\leq|e^{(k)}|_{R}+\Delta^{2}|D|_{V}$ (169)
$\displaystyle\leq\left|e^{(k)}_{T}+\sum_{i=1}^{T}f_{i}\right|_{R}+\Delta^{2}|D|_{V}$
(170)
$\displaystyle\leq|e^{(k)}_{T}|_{R}+\sum_{i=1}^{T}|f_{i}|+\Delta^{2}|D|_{V}$
(171)
$\displaystyle\leq\frac{\zeta}{(1-\delta)\kappa}\Delta^{2}|D|_{V}+\frac{1}{\kappa}\sum_{i=1}^{T}|x_{i}|+\Delta^{2}|D|_{V}$
(172)
$\displaystyle\leq\left(1+\frac{\zeta}{(1-\delta)\kappa}\right)\Delta^{2}|D|_{V}+\frac{1}{(1-\varepsilon^{\prime})\kappa}\left(|\tilde{Z}^{(k)}|-|\tilde{Z}_{T}^{(k)}|\right)$
(173)
$\displaystyle\leq\left(1+\frac{\zeta}{(1-\delta)\kappa}\right)\Delta^{2}|D|_{V}+\frac{1}{(1-\varepsilon^{\prime})\kappa}|\tilde{Z}^{(k)}|$
(174)
$\displaystyle\leq\left(1+\frac{\zeta}{(1-\delta)\kappa}\right)\Delta^{2}|D|_{V}+\frac{1+\zeta}{(1-\varepsilon^{\prime})\kappa}\Delta^{2}|D|_{V}+\frac{(1-\gamma)^{k}}{(1-\varepsilon^{\prime})\kappa}|\tilde{Z}|\,.$
(175)

In the above, the first inequality (169) follows from (122). Inequality (172)
follows from (168) and the $\kappa$-product-expansion of the local code.
Inequality (173) follows from the fact that each local codeword $x_{i}$
satisfies the decoding condition with parameter $\varepsilon^{\prime}$.
Finally, inequality (175) follows from (166).

Using the fact that $|\tilde{Z}|\leq 4|e|_{R}+\Delta^{2}|D|_{V}$, we can
rewrite the inequality above in terms of $|e|_{R}$ and $|D|_{V}$ following the
same steps used in (96) to (98). This gives us

$\displaystyle|\tilde{e}^{(k)}|_{R}\leq\left(1+\frac{\zeta}{(1-\delta)\kappa}+\frac{1+\zeta}{(1-\varepsilon^{\prime})\kappa}+\frac{(1-\gamma)^{k}}{(1-\varepsilon^{\prime})\kappa}\right)\Delta^{2}|D|_{V}+\frac{4(1-\gamma)^{k}}{(1-\varepsilon^{\prime})\kappa}|e|_{R}\,.$
(176)

Finally, setting $\varepsilon^{\prime}=3\delta$, and using the fact that
$\kappa\leq 1$ [36], we can relax the inequality above slightly to get
$4/((1-\varepsilon^{\prime})\kappa)\leq 24/(5\kappa)$, as well as

$\displaystyle
1+\frac{\zeta}{(1-\delta)\kappa}+\frac{1+\zeta}{(1-\varepsilon^{\prime})\kappa}+\frac{(1-\gamma)^{k}}{(1-\varepsilon^{\prime})\kappa}$
$\displaystyle\leq\frac{1}{\kappa}\left(1+\frac{2}{\delta}+\frac{2-\delta}{1-3\delta}\cdot\frac{1}{\delta}+\frac{1}{1-3\delta}\right)$
(177)
$\displaystyle\leq\frac{1}{\kappa}\left(1+\frac{2}{\delta}+\frac{2}{1-3\delta}\cdot\frac{1}{\delta}\right)$
(178) $\displaystyle\leq\frac{6}{\kappa\delta}\,,$ (179)

which holds for $\delta\in(0,1/18)$. ∎

##  5 Discussion

In our article, we have shown that quantum Tanner codes admit single-shot QEC.
Given information from a single round of noisy measurements, the mismatch
decomposition decoder [33] is able to output a correction that is close to the
data error that occurred. For a variety of noise models, including adversarial
or stochastic noise, the single-shot decoder is able to maintain the encoded
quantum information for up to an exponential number of correction rounds. The
parallelized version of the decoder can be run in constant time while keeping
the residual error small. During readout, a logarithmic number of iterations
suffices to recover the logical information.

One may also ask about the possibility of single-shot QEC with other decoders
for good QLDPC codes. Due to the close connection between the decoders
analyzed here and the potential-based decoder for quantum Tanner codes in Ref.
[22] (for example, the ability to map between candidate flip sets for both
types of decoders), a corollary of the proofs presented here is that the
potential-based decoder also has the single-shot property. Likewise, under the
mapping of errors shown in Ref. [21], the decoders considered here are
applicable to the original good QLDPC codes by Panteleev and Kalachev [17].
Our analysis does not straightforwardly carry over to the code and decoder
proposed in Ref. [19], and it remains to be seen whether that construction
also admits single-shot decoding.

We further remark that all known constructions of asymptotically good QLDPC
codes admit a property called small-set (co)boundary expansion [43], which in
the case of quantum Tanner codes, was used to prove the No Low-Energy Trivial
States (NLTS) conjecture (see Property 1 of reference [44]). Small-set
(co)boundary expansion is also equivalent to the notion of soundness [45],
which lower bounds the syndrome weight by some function of reduced error
weight. Indeed, soundness is a strong indication of single-shot decodability.
Similarly, quantum locally testable codes [46, 47, 48, 49, 50] admit analogous
soundness properties, although decoders for such codes are unexplored. Note
that in our proof, what we needed was a notion of soundness for the mismatch
vector (see Lemma 4.14), which is distinct from the usual notion of soundness
for the syndrome. The weight of the mismatch is in general incomparable to the
weight of the syndrome, so the precise relation between these two definitions
of soundness is not well understood.

In conclusion, our results can be viewed as a step toward making general QLDPC
codes more practical. While many challenges still remain, there have been
promising developments in this direction [41, 51, 52, 53]. We believe that
quantum LDPC codes, similar to classical LDPC codes, will constitute the gold
standard for future quantum telecommunication technologies and form the
backbone of resource-efficient quantum fault-tolerant protocols.

###### Acknowledgements.

We would like to thank Robert König, Anthony Leverrier and Chris Pattison for
inspiring discussions on single-shot QEC and QLDPC codes. S.G. acknowledges
funding from the U.S. Department of Energy (DE-AC02-07CH11359), and the
National Science Foundation (PHY-1733907). The Institute for Quantum
Information and Matter is an NSF Physics Frontiers Center. E.T. acknowledges
funding from the Sloan Foundation, DARPA 134371-5113608, and DOD KK2014. L.C.
and S.C. gratefully acknowledge support by the European Research Council under
grant agreement no. 101001976 (project EQUIPTNT). Z.H. would like to thank NSF
grant CCF 1729369 for support.

## Data availability

Data sharing not applicable to this article as no datasets were generated or
analyzed during the current study.

## References

  * Shor [1995] P. W. Shor, Scheme for reducing decoherence in quantum computer memory, Physical Review A 52, R2493 (1995).
  * Steane [1996a] A. M. Steane, Error correcting codes in quantum theory, Physical Review Letters 77, 793 (1996a).
  * Gottesman [1996] D. Gottesman, Class of quantum error-correcting codes saturating the quantum Hamming bound, Physical Review A 54, 1862 (1996).
  * Kitaev [2003] A. Kitaev, Fault-tolerant quantum computation by anyons, Annals of Physics 303, 2 (2003).
  * Dennis  _et al._ [2002] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topological quantum memory, Journal of Mathematical Physics 43, 4452 (2002).
  * Bombin and Martin-Delgado [2006] H. Bombin and M. A. Martin-Delgado, Topological quantum distillation, Phys. Rev. Lett. 97, 180501 (2006).
  * Bombín and Martin-Delgado [2007] H. Bombín and M. Martin-Delgado, Exact topological quantum order in $D=3$ and beyond: Branyons and brane-net condensates, Physical Review B 75, 075103 (2007).
  * Kubica [2018] A. Kubica,  _The ABCs of the Color Code: A Study of Topological Quantum Codes as Toy Models for Fault-Tolerant Quantum Computation and Quantum Phases Of Matter_ , Ph.D. thesis, Caltech (2018).
  * Bravyi and Terhal [2009] S. Bravyi and B. Terhal, A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes, New Journal of Physics 11, 043029 (2009).
  * Bravyi  _et al._ [2010] S. Bravyi, D. Poulin, and B. Terhal, Tradeoffs for reliable quantum information storage in 2D systems, Phys. Rev. Lett. 104, 050503 (2010).
  * Baspin and Krishna [2022] N. Baspin and A. Krishna, Quantifying nonlocality: How outperforming local quantum codes is expensive, Physical Review Letters 129, 050505 (2022).
  * Breuckmann and Eberhardt [2021a] N. P. Breuckmann and J. N. Eberhardt, Quantum low-density parity-check codes, PRX Quantum 2, 040101 (2021a).
  * Evra  _et al._ [2022] S. Evra, T. Kaufman, and G. Zémor, Decodable quantum ldpc codes beyond the $\sqrt{n}$ distance barrier using high-dimensional expanders, SIAM Journal on Computing , FOCS20 (2022).
  * Hastings  _et al._ [2021] M. B. Hastings, J. Haah, and R. O’Donnell, Fiber bundle codes: breaking the $n^{1/2}\text{polylog}(n)$ barrier for quantum LDPC codes, in  _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ (2021) pp. 1276–1288.
  * Panteleev and Kalachev [2022a] P. Panteleev and G. Kalachev, Quantum LDPC codes with almost linear minimum distance, IEEE Transactions on Information Theory 68, 213 (2022a).
  * Breuckmann and Eberhardt [2021b] N. P. Breuckmann and J. N. Eberhardt, Balanced product quantum codes, IEEE Transactions on Information Theory 67, 6653 (2021b).
  * Panteleev and Kalachev [2022b] P. Panteleev and G. Kalachev, Asymptotically good quantum and locally testable classical LDPC codes, in  _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ (2022) pp. 375–388.
  * Leverrier and Zémor [2022] A. Leverrier and G. Zémor, Quantum Tanner codes, in  _2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)_ (IEEE, 2022) pp. 872–883.
  * Dinur  _et al._ [2022a] I. Dinur, M.-H. Hsieh, T.-C. Lin, and T. Vidick, Good quantum LDPC codes with linear time decoders (2022a), arXiv:2206.07750.
  * Terhal [2015] B. M. Terhal, Quantum error correction for quantum memories, Rev. Mod. Phys. 87, 307 (2015).
  * Leverrier and Zémor [2023] A. Leverrier and G. Zémor, Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes, in  _Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ (SIAM, 2023) pp. 1216–1244.
  * Gu  _et al._ [2023] S. Gu, C. A. Pattison, and E. Tang, An efficient decoder for a linear distance quantum LDPC code, in  _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_, STOC 2023 (Association for Computing Machinery, New York, NY, USA, 2023) p. 919–932.
  * Shor [1996] P. Shor, Fault-tolerant quantum computation, in  _Proceedings of 37th Conference on Foundations of Computer Science_ (IEEE Comput. Soc. Press, 1996) pp. 56–65.
  * Bombín [2015] H. Bombín, Single-shot fault-tolerant quantum error correction, Phys. Rev. X 5, 031043 (2015).
  * Fawzi  _et al._ [2018] O. Fawzi, A. Grospellier, and A. Leverrier, Constant overhead quantum fault-tolerance with quantum expander codes, in  _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ (IEEE, 2018).
  * Kubica and Vasmer [2022] A. Kubica and M. Vasmer, Single-shot quantum error correction with the three-dimensional subsystem toric code, Nature Communications 13, 6272 (2022).
  * Bridgeman  _et al._ [2023] J. C. Bridgeman, A. Kubica, and M. Vasmer, Lifting topological codes: Three-dimensional subsystem codes from two-dimensional anyon models (2023), arXiv:2305.06365.
  * Bombín [2015] H. Bombín, Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes, New Journal of Physics 17, 083002 (2015).
  * Campbell [2019] E. T. Campbell, A theory of single-shot error correction for adversarial noise, Quantum Science and Technology 4, 025006 (2019).
  * Fujiwara [2014] Y. Fujiwara, Ability of stabilizer quantum error correction to protect itself from its own imperfection, Physical Review A 90, 062304 (2014).
  * Ashikhmin  _et al._ [2020] A. Ashikhmin, C. Y. Lai, and T. A. Brun, Quantum Data-Syndrome Codes, IEEE Journal on Selected Areas in Communications 38, 449 (2020).
  * Delfosse  _et al._ [2022] N. Delfosse, B. W. Reichardt, and K. M. Svore, Beyond single-shot fault-tolerant quantum error correction, IEEE Transactions on Information Theory 68, 287 (2022).
  * Leverrier and Zémor [2023] A. Leverrier and G. Zémor, Decoding quantum tanner codes, IEEE Transactions on Information Theory , 1 (2023).
  * Ben-Sasson and Sudan [2006] E. Ben-Sasson and M. Sudan, Robust locally testable codes and products of codes, Random Structures & Algorithms 28, 387 (2006).
  * Dinur  _et al._ [2022b] I. Dinur, S. Evra, R. Livne, A. Lubotzky, and S. Mozes, Locally testable codes with constant rate, distance, and locality, in  _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ (2022) pp. 357–374.
  * Kalachev and Panteleev [2022] G. Kalachev and P. Panteleev, Two-sided robustly testable codes (2022), arXiv:2206.09973.
  * Calderbank and Shor [1996] A. R. Calderbank and P. W. Shor, Good quantum error-correcting codes exist, Phys. Rev. A 54, 1098 (1996).
  * Steane [1996b] A. Steane, Multiple-particle interference and quantum error correction, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 452, 2551 (1996b).
  * Knill [2005] E. Knill, Quantum computing with realistically noisy devices, Nature 434, 39 (2005).
  * Steane [1997] A. M. Steane, Active stabilization, quantum computation, and quantum state synthesis, Physical Review Letters 78, 2252 (1997).
  * Gottesman [2014] D. Gottesman, Fault-tolerant quantum computation with constant overhead, Quantum Info. Comput. 14, 1338–1372 (2014).
  * Grospellier [2019] A. Grospellier,  _Constant time decoding of quantum expander codes and application to fault-tolerant quantum computation_ , Ph.D. thesis, Sorbonne Université (2019).
  * Kaufman and Lubotzky [2013] T. Kaufman and A. Lubotzky, High dimensional expanders and property testing (2013), arXiv:1312.2367.
  * Anshu  _et al._ [2022] A. Anshu, N. Breuckmann, and C. Nirkhe, NLTS hamiltonians from good quantum codes (2022), arXiv:2206.13228.
  * Quintavalle  _et al._ [2021] A. O. Quintavalle, M. Vasmer, J. Roffe, and E. T. Campbell, Single-shot error correction of three-dimensional homological product codes, PRX Quantum 2, 020340 (2021).
  * Aharonov and Eldar [2015] D. Aharonov and L. Eldar, Quantum locally testable codes, SIAM Journal on Computing 44, 1230 (2015).
  * Hastings [2017] M. B. Hastings, Quantum codes from high-dimensional manifolds, in  _8th Innovations in Theoretical Computer Science Conference (ITCS 2017)_ (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017).
  * Leverrier  _et al._ [2022] A. Leverrier, V. Londe, and G. Zémor, Towards local testability for quantum coding, Quantum 6, 661 (2022).
  * Cross  _et al._ [2022] A. Cross, Z. He, A. Natarajan, M. Szegedy, and G. Zhu, Quantum locally testable code with exotic parameters (2022), arXiv:2209.11405.
  * Wills  _et al._ [2023] A. Wills, T.-C. Lin, and M.-H. Hsieh, General distance balancing for quantum locally testable codes (2023), arXiv:2305.00689.
  * Cohen  _et al._ [2022] L. Z. Cohen, I. H. Kim, S. D. Bartlett, and B. J. Brown, Low-overhead fault-tolerant quantum computing using long-range connectivity, Science Advances 8, eabn1717 (2022).
  * Tremblay  _et al._ [2022] M. A. Tremblay, N. Delfosse, and M. E. Beverland, Constant-overhead quantum error correction with thin planar connectivity, Physical Review Letters 129, 050504 (2022).
  * Pattison  _et al._ [2023] C. A. Pattison, A. Krishna, and J. Preskill, Hierarchical memories: Simulating quantum LDPC codes with local gates (2023), arXiv:2303.04798.