# Quantum Codes on Graphs

Matthew B. Hastings  Microsoft Quantum, Redmond, WA

###### Abstract

We consider some questions related to codes constructed using various graphs,
in particular focusing on graphs which are not lattices in two or three
dimensions. We begin by considering Floquet codes which can be constructed
using “emergent fermions”. Here, we are considering codes that in some sense
generalize the honeycomb codeHastings and Haah (2021) to more general, non-
planar graphs. We then consider a class of these codes that is related to
(generalized) toric codes on $2$-complexes. For (generalized) toric codes on
$2$-complexes, the following question arises: can the distance of these codes
grow faster than square-root? We answer the question negatively, and remark on
recent systolic inequalitiesAlpert et al. (2022). We then turn to the case
that of planar codes with vacancies, or “dead qubits”, and consider the
statistical mechanics of decoding in this setting. Although we do not prove a
threshold, our results should be asymptotically correct for low error
probability and high degree decoding graphs (high degree taken before low
error probability). In an appendix, we discuss a toy model of vacancies in
planar quantum codes, giving a phenomenological discussion of how errors occur
when “super-stabilizers” are not measured, and in a separate appendix we
discuss a relation between Floquet codes and chain maps.

The toric codeKitaev (2006) is a quantum stabilizer code where the qubits are
arranged on a two-dimensional surface. One can consider a variety of different
lattices for the qubits, and indeed one may even consider non-translationally
invariant cellulations of the surface to define the code, but in general all
these forms involve some notion of geometric locality of the stabilizers. In
constrast, this paper considers quantum codes where checks are defined on
general graphs, considering both Floquet codes and stabilizer codes.

In Section I, we give some background on Floquet codes and discuss the
relation between certain Floquet codes and the Kramers-Wannier transform. In
Section II, we consider Floquet codes which can be regarded as emergent
Majorana fermions coupled to a $\mathbb{Z}_{2}$ gauge field, and discuss
possible patterns of checks. One particular class of these codes gives rise to
what we call a “(twisted) toric code on a $2$-complex”, a particular kind of
CSS stabilizer code; in Section III we bound the distance of this class of
codes, assuming that the code is LDPC, showing that it is not possible to have
the minimum distance of the code grow faster than the square-root of the
number of qubits. As we discuss, there are examples of this codeFreedman et
al. (2002); Evra et al. (2022) for which the _product_ of distances grows
faster than the number of qubits, though recent systolic inequalitiesAlpert et
al. (2022) show that it cannot grow _polynomially_ faster than the number of
qubits. However, we show that it is not possible to have both $Z$\- and
$X$-distances grow faster than square-root for this kind of code. This
contrasts with more general codes for which one can have distances greater
than square-rootHastings et al. (2021) or even linear in the number of
qubitsPanteleev and Kalachev (2021); Panteleev and Kalachev (2022), and these
codes can in turn be used to construct linear distance toric codes on
$11$-manifolds with degrees of freedom on $4$-cellsFreedman and Hastings
(2021).

In Section IV, we consider the case of a toric code or planar Floquet code
with some vacancies or dead qubits. We consider the case that one can
measure“superstabilizers” near these vacancies; these can give rise to a check
graph with high degree vertices and we consider the statistical mechanics of
decoding in this case. Finally, in Appendix A, we give a homological
interpretation of certain Floquet codes as chain maps and in Appendix B, we
give a toy model of vacancies in planar codes, describing how error
probability increases with time if superstabilizers are not measured; one
interesting feature is a possible superlinear growth in error probability with
time.

##  I Floquet Code Background, Measuring Checks and The Kramers-Wannier
Transform

Floquet codesHastings and Haah (2021); Haah and Hastings (2022); Aasen et al.
(2022); Kesselring et al. (2022) are quantum codes where some operators called
“checks” are measured in some sequence, which may be periodic in time or non-
periodicDavydova et al. (2023). In this paper, we consider codes on qubits,
rather than qudits. After each check is measured, in the kinds of codes
considered here, the qubits will be described by some stabilizer code,
stabilized by some group called the“instantaneous stabilizer group” (ISG).
This ISG is changing in time.

After measuring some check, the check itself will be part of the ISG at that
time. Any other previously measured checks $C$ will also be in the ISG if no
measurement at an intervening time anti-commuted with the given check $C$.
There may also be elements of the ISG which are formed by products of checks.

All Floquet codes in this paper will involve choosing some sequence of one or
two qubit measurements as checks. Each single qubit checks will measure one of
the three possible Pauli operators on that qubit. Each two qubit check will
measure the product of a pair of Pauli operators; any of the $9$ possible
products may be measured.

The honeycomb code and related Floquet codes (on other trivalent planar graphs
with $3$-colorable plaquettes) makes use of a certain pattern of checks. This
pattern is as follows. Consider a ring of sites (of size $6$ in the case of
the honeycomb code), and label the sites by integers $1,\ldots,m$ for even
$m$, with the label periodic in $m$. Then in some round one measures a set of
checks that can be chosen to be (by choosing a basis of Pauli operators on
each qubit appropriately)) $X_{2j-1}X_{2j}$ for $j=0,1,\ldots,m/2$. Then in
the following round on measures a set of checks that can be chosen to be
(again by choosing a basis of Paulis) $Z_{2j}Z_{2j+1}$ for
$j=0,1,2,\ldots,m/2$.

In fact, the same pattern also occurs in the $e\leftrightarrow m$ automorphism
codeAasen et al. (2022), where this pattern is used as part of a Kramers-
Wannier transform by preceding it by single qubit measurements and following
with single qubit measurements. These measurements can be chosen as follows:
first measure single qubit $Z$ on all even qubits, then implement those
pairwise measurements, then follow by measuring single qubit $X$ on all odd
qubits. Then this sequence implements a Kramers-Wannier transform, mapping

$Z_{2j-1}\rightarrow\pm Z_{2j-2}Z_{2j},$ (1)

and mapping

$X_{2j-1}X_{2j+1}\rightarrow\pm X_{2j},$ (2)

where the signs are determined by the measurement outcomes.

Let’s consider what happens in the first two measurement rounds. Consider a
given pair of qubits labeled $2j-1,2j$. Then, we first measure $Z_{2j}$ and
next measure $X_{2j-1}X_{2j}$. The measurement $X_{2j-1}X_{2j}$ defines a
stabilizer code, with a single “logical qubit”. The effect of these two
measurements is to encode qubit $2j-1$ into this logical qubit. To see this,
we can consider the two Pauli operators $X_{2j-1}$ and $Z_{2j-1}$. The
operator $X_{2j-1}$ commutes with all of these measurements and is also a
logical operator of the code defined by $X_{2j-1}X_{2j}$. The operator
$Z_{2j-1}$ can be multiplied by the operator $Z_{2j}$ after the measurement of
$Z_{2j}$, to give $Z_{2j-1}Z_{2j}$, which is another logical operator of the
code defined by $X_{2j-1}X_{2j}$.

Similarly, the measurement of $Z_{2j}Z_{2j+1}$ defines a stabilizer code, with
logical operators $Z_{2j}$ and $X_{2j}X_{2j+1}$. After measuring $X_{2j+1}$,
this effectively decodes this code, as we can multiply $X_{2j}X_{2j+1}$ by
$X_{2j+1}$ to get $X_{2j}$, so these logical operators of the code defined by
$Z_{2j}Z_{2j+1}$ become operator $Z_{2j}$ and $X_{2j}$ on qubit $2j$.

As shown in Aasen et al. (2022), the effect of these four rounds of
measurements (single qubit $Z$, pairwise $XX$, pairwise $ZZ$, single qubit
$X$) is to implement a Kramers-Wannier transform. So, other than these
decoding and encoding operations effected by single qubit measurements, the
effect of $Z_{2j}Z_{2j+1}$ for $j=0,1,2,\ldots,m/2$ on a state stabilized by
$X_{2j-1}X_{2j}$ for $j=0,1,\ldots,m/2$ is to map the qubits encoded in this
code stabilized by $X_{2j-1}X_{2j}$ to qubits encoded in a code stabilized by
$Z_{2j}Z_{2j+1}$, while performing a Kramers-Wannier transform.

This Kramers-Wannier transform effectively measures a certain product of
Paulis. Note that the map Eqs. 1 and 2 will map $\prod_{j}Z_{2j-1}$ to plus or
minus identity. Indeed, the measurements effectively measure this product.
Similarly, the measurements produce a state of definite $\prod_{j}X_{2j}$. It
should be no surprise that this happens; indeed, the product of measurements
$X_{2j-1}X_{2j}$ is equal to the product of $X_{j}$ over all $j$, and this
product commutes with the subsequent measurements of $Z_{2j}Z_{2j+1}$, and
after measuring $X$ on odd qubits, we are left with definite
$\prod_{j}X_{2j}$.

The Kramers-Wannier transform can be implemented in a different way
followingTantivasadakarn et al. (2021). In this way, one uses single qubit $X$
measurements and controlled-$Z$ gates, instead of pairwise measurements. The
effect again is to perform the Kramers-Wannier transform while measuring a
product of single qubit operators on the input state.

Unfortunately, this Kramers-Wannier transform has problems if it is used as a
general technique to measure stabilizers. That is, one might try the
following. Suppose one has some stabilizer code with some high weight
stabilizer. Without loss of generality this stabilizer can be written as a
product of Pauli $X$ over some set of qubits, and so one could use those
qubits as input to a Kramers-Wannier transform to measure that stabilizer,
implementing that transform twice to return the qubits to their original
state. However, method of measuring stabilizers can lead to an increase in the
weight of errors. By Eq. 2, the map implements $X_{2j-1}X_{2j+1}\rightarrow\pm
X_{2j}$. Hence, $X_{1}X_{2j+1}\rightarrow X_{2}X_{4}\ldots X_{2j}$ so a two
qubit on the input state can map to an arbitrarily high weight error under
Kramers-Wannier transform. Indeed, avoiding this production of high weight
errors when measuring high weight stabilizers is the reason for the ShorShor
(1996), SteaneSteane (1997), and KnillKnill (2005) fault tolerant schemes.

##  II “Majorana-Gauge Field” Codes

We now consider a class of Floquet codes where we do not use single qubit
measurements and where the two qubit measurements have a particular form. Each
such code will be defined by some trivalent graph, $G$, as well as by some
further data, giving a sequence of edges of the codes, which will correspond
to a sequence of measurements. There is a one-to-one correspondence between
qubits of the code and vertices of the graph.

The codes we consider here have some interpretation in terms of Majorana
fermions coupled to a gauge field. They are related to codes of Chapman et al.
(2022), but we consider more general graphs. One class of codes that we
consider below is related to so-called “matching codes”Wootton (2015). Our
codes differ (and generalize) in two ways. First, rather than a stabilizer
code with a fixed stabilizer group, we consider a Floquet code, whose
stabilizer group changes in time. Second, while this ISG at a given time is
related to a matching code, it generalizes it because rather than considering
a two-dimensional lattice, we consider matchings on more general trivalent
graphs.

More generally, $G$ need not be a graph but may be a _multigraph_. That is, a
multigraph means that there be more than one edge between any pair of
vertices; further, edges have an identity, so if there are multiple edges
between a pair of vertices, different edges will correspond to different
checks. However, for brevity, we refer to $G$ as a graph.

We will assume that $G$ is connected. The case where $G$ is not connected can
be easily understood in terms of the connected case, as it will correspond to
having several codes, one for each connected component.

For each of the three edges attached to a given qubit, we make an arbitrary
assignment of the $3$ Pauli operators, $X,Y,Z$, choosing a different Pauli
operator on each edge. This choice has no affect on the distance or rate of
the code; indeed, it has no effect on the properties of the code unless the
external noise is biased in some way (for example, $X$ errors more likely than
$Z$ errors).

Thus, each edge is labeled by a pair of Pauli operators, one for each of the
two vertices attached to that edge. Then each edge corresponds to a two qubit
measurement, where we measure the product of the given Pauli operators on
those two qubits. For example, given an edge between vertices $1$ and $2$,
where we choose Pauli $X$ for that edge on qubit $1$ and Pauli $Y$ for that
edge on qubit $2$, the edge corresponds to a measurement of $X_{1}Y_{2}$.

Then, given a sequence of edges of the code, we measure the corresponding
checks in that order, repeating the sequence periodically.

There is a natural interpretation of these checks in terms of Majoranas,
similar to that of the Kitaev honeycomb modelKitaev (2006). For each qubit
$j$, introduce four Majorana operators,
$\gamma_{0}^{j},\gamma_{x}^{j},\gamma_{y}^{j},\gamma_{z}^{j}$. Impose a
constraint $\gamma_{0}^{j}\gamma_{x}^{j}\gamma_{y}^{j}\gamma_{z}^{j}=1$ for
all $j$. Represent Pauli operators $X,Y,Z$ on that qubit by
$i\gamma_{0}^{j}\gamma_{x}^{j},i\gamma_{0}^{j}\gamma_{y}^{j},i\gamma_{0}^{j}\gamma_{z}^{j}$,
respectively. See Hastings and Haah (2021) also. We will not use this
representation here, but it accounts for our choice of the term Majorana-Gauge
Field code. 111In fact, one can consider graphs of higher degree than $3$. In
this case, if we have $d$ edges attacked to some vertex, then we take Majorana
operators $\gamma_{0},\gamma_{1},\ldots,\gamma_{d}$ on that vertex. Then, one
can construct $d$ anticommuting operators on that vertex of the form
$i\gamma_{0}\gamma_{j}$ for $j\in\\{1,\ldots,d\\}$, with each operator having
even fermion parity, and each check will be the product of one such operator
on one vertex and another such operator on another vertex. Assume $d$ odd and
fix a definite value for the product $\gamma_{0}\gamma_{1}\ldots\gamma_{d}$,
which commutes with all checks. Even products of these operators
$\gamma_{0},\ldots,\gamma_{d}$ can be realized as products of Pauli operators
on $m$ qubits, so long as $2^{m}\geq 2^{d/2-1}$. However, for now we stick to
degree $3$.

###  II.1 Homology

These checks generate some group. This group is sometimes called the “gauge
group” in the subsystem code literature, but we avoid using this term as it
may cause confusion with other uses of the term “gauge”, e.g., “gauge fields”.
Let us define ${\cal G}$ to be the group generated by checks, as well as by
$-1$ (i.e., by a sign). Let ${\cal Q}$ be be ${\cal G}$ modulo sign and let
${\cal N}$ be the group generated by $-1$, i.e. we have a short exact sequence
$1\rightarrow N\rightarrow G\rightarrow Q\rightarrow 1$. The group ${\cal Q}$
is abelian.

Let us determine the rank of ${\cal Q}$. Let there be $n_{V}$ vertices in
graph $G$. Hence, there are

$n_{E}=\frac{3}{2}n_{V}$

edges. So, ${\cal Q}$ is generated by this set of cardinality $n_{E}$.
However, if we take a product of checks corresponding to some set of edges,
then that product is equal (up to sign) to the identity if and only if, for
each vertex, either all three edges attached to that vertex appear in the
given set or no edges attached to that vertex appear in the given set. Since
we have assumed that $G$ is connected, the only nontrivial product of checks
equal (up to sign) to the identity is the product of _all_ checks. Hence, the
rank of ${\cal Q}$ is equal to $n_{E}-1$.

Let the “stabilizer group” be the image in ${\cal Q}$ of the center of ${\cal
G}$, i.e., the stabilizer group is the center of ${\cal G}$ up to sign. Let
${\cal S}$ denote the stabilizer group. We emphasize that ${\cal S}$ is _not_
the ISG, though if some element of ${\cal S}$ is in the ISG then it will
remain in the ISG for all subsequent rounds.

Before considering ${\cal S}$, we pause to define a certain homology theory. A
$1$-chain will be some formal sum of edges of $G$ with $\mathbb{Z}_{2}$
coefficients, i.e., we have a $\mathbb{Z}_{2}$ vector space with dimension
equal to the number of edges, with basis elements of the vector space in one-
to-one correspondence with edges. A $0$-chain will be a formal sum of vertices
of $G$ with $\mathbb{Z}2$ coefficients, and we define the obvious boundary
operator $\partial$ mapping $1$-chains to $0$-chains, mapping each edge to the
sum of vertices in that edge. A $1$-cycle is a $1$-chain whose boundary
vanishes. Hence, a $1$-cycle has is a sum of edges, where for every vertex an
_even_ number of edges are in that sum, so a $1$-cycle corresponds to a sum of
closed loops on the graph, disconnected from each other. Each such closed loop
is a simple cycle, in the language of graph theory.

Corresponding to every $1$-chain is some element of ${\cal Q}$, namely that
element is the product of checks corresponding to edges whose coefficient in
that chain is equal to $1$, modulo sign. One may verify that every $1$-cycle
corresponds to some product of checks which commutes with every check
individually and hence corresponds to some element of ${\cal S}$. Let us show
indeed that these $1$-cycles generate ${\cal S}$. Consider some edge $(i,j)$
between vertices $i$ and $j$, and consider some $1$-chain $v$. One may verify
that the product of checks corresponding to $v$ commutes with the check
corresponding to $e$ if and only if $\partial v$ has the same coefficient on
vertex $i$ as it does on vertex $j$. That is, it occurs if and only if the
number of edges in $v$ attached to $i$ has the same parity (mod $2$) as the
number of edges attached to $j$. However, since $G$ is assumed connected, in
order for the product of checks corresponding to $v$ to commute with all
checks, either $\partial v=0$ identically or $\partial v$ is equal to $1$ on
every vertex, i.e., every vertex has either an even or odd number of edges
attached to it in $v$. If $\partial v=0$ identically, then $v$ is a $1$-cycle.
If $\partial v$ equals $1$ on every vertex, then $v=x+y$, where $x$ is some
$1$-cycle and $y$ is the sum of _all_ edges. Since the product of checks
corresponding to $y$ is equal to the identity as explained above, the product
of checks corresponding to $v$ is the same as the product of checks
corresponding to some $1$-cycle, namely $x$.

Hence, the rank of ${\cal S}$ is equal to the rank of the group of $1$-cycles.
This group is called the first homology group of $G$, and by the Euler
characteristic of the chain complex we are studying, the rank of the first
homology group is equal to $n_{E}-n_{V}+1$, since the rank of the zeroth
homology group (the group of $0$-chains, modulo boundaries of $1$-chains) is
equal to $1$ since $G$ is connected. Hence, the rank of the stabilizer group
${\cal S}$ equals

$n_{E}-n_{V}+1=\frac{1}{2}n_{V}+1.$

Since ${\cal Q}$ has rank $n_{E}-1=(3/2)n_{V}-1$, and ${\cal S}$ has rank
$s\equiv(1/2)n_{V}+1$, the difference between the rank of ${\cal G}$ and the
rank of ${\cal S}$ is $n_{V}-2$. So, we can write ${\cal G}$ as generated by
(modulo sign)

$\tilde{Z}_{1},\ldots,\tilde{Z}_{s},\tilde{X}_{s+1},\tilde{Z}_{s+1},\ldots,\tilde{X}_{s+r},\tilde{X}_{s+r},$

where

$r=\frac{n_{V}-2}{2}=\frac{1}{2}n_{V}-1,$

and where the operators $\tilde{Z}_{i},\tilde{X}_{j}$ are products of Paulis
which obey the usual Pauli anticommutation relations, and where

$s=\frac{1}{2}n_{V}+1$

is the rank of ${\cal S}$.

After these generalities, let us consider some specific measurement sequences.
Start with the system in a maximally mixed state, and measure checks in some
sequence. After each measurement, the state is a stabilizer state, which is
stabilized by some group called the _instantaneous stabilizer group (ISG)_.
Every element of the ISG is in ${\cal G}$.

###  II.2 Floquet Codes from Sequences of Perfect Matchings

Define a _perfect matching_ to be a subset of edges of the graph $G$ such that
every vertex is in exactly one edge in that subset. Suppose we perform some
arbitrary sequence of measurements and then measure the checks on some perfect
matching. Then, the ISG contains the checks corresponding to the edges in the
perfect matching. We claim, and we now show that _the ISG is then generated by
the checks in the perfect matching and possibly by some products of checks
corresponding to $1$-cycles_. Every element of the ISG commutes with these
checks. By the discussion above, if an element $O$ of the ISG (which is a
product of checks, and hence corresponds to some $1$-chain $v$) commutes with
a given check $(i,j)$ in the perfect matching, then $\partial v$ has the same
coefficient on vertex $i$ as it does on $j$. If $\partial v$ is equal to $1$
on $i$ and $j$, then we may multiply $O$ by the check corresponding to edge
$(i,j)$; this gives some other element of the ISG, and that element
corresponds to some chain $v^{\prime}$ such that $\partial v^{\prime}$
vanishes on $i$ and $j$. In this way, since the matching is perfect, given any
element of $O$ of the ISG, we may multiply it by checks in the perfect
matching so that the resulting operator $O^{\prime}$ corresponds to a
$1$-cycle, as claimed.

Let $C$ be any even length simple cycle $C$ in $G$ such that half the edges in
$C$ have the corresponding check in the ISG, i.e., following the edges in $C$,
we see that they alternating between being in the ISG and not being in the IG,
we can measure the element of ${\cal S}$ corresponding to that cycle $C$ by
measuring the checks corresponding to edges in $C$ which are not in the
matching.

So, we can choose the ISG to contain edges in some matching, as well as
products of edges corresponding to any cycle of even length by appropriately
measuring products of checks.

So, in this subsection we consider codes for which the sequence of checks
measured is given by picking some sequence of perfect matchings, called
$m_{1},m_{2},\ldots,m_{k}$, for some $k$, and then measuring all the checks in
$m_{1}$ in an arbitrary order (the order does not matter), then all the checks
in $m_{2}$, and so on, repeating the sequence periodically with period $k$,
identifying $m_{k+i}$ with $m_{i}$.

Given any two perfect matchings, $m,m^{\prime}$, we can define a set of simple
cycles that we call $C(m,m^{\prime})$ as follows. Pictorially, simply draw on
the graph the edges that appear in exactly one of the two matchings (but not
both of them), and this will give a set of simple cycles. Formally, each
matching $m$ or $m^{\prime}$ can be identified with some $1$-chain $v_{m}$ or
$v_{m^{\prime}}$ where the chain has a coefficient $1$ on the edges in the
matching. Then, $v_{m}+v_{m^{\prime}}$ is a $1$-cycle and hence corresponds to
a union of simple cycles; these simple cycles are those in $C(m,m^{\prime})$.

It is easy to verify the following: _suppose after measuring all the checks in
some matching $m_{i}$, the ISG is generated (up to signs) by those checks and
by products of checks corresponding to $1$-cycles in some given set $S$; then
after measuring all the checks in matching $m_{i+1}$, the ISG is generated by
the checks in $m_{i+1}$, and by products of checks corresponding to cycles in
$S$, and by products of checks corresponding to simple cycles in
$C(m,m^{\prime})$._

######  Definition 1.

Let us define a _graph matching code_ to be a stabilizer code on a trivalent
graph, with “checks” on the graph as defined above, such that the stabilizer
group of the graph matching code is generated by the checks corresponding to
edges of some perfect matching, and by products of checks corresponding to
simple cycles, for some set of simple cycles.

Thus, what we have shown is that for such a measurement sequence using perfect
matchings, after measuring any perfect matching the ISG is that of a graph
matching code.

Indeed, following such a sequence of measurements, if we start from a
maximally mixed state, it follows that the $1$-cycles in $S$ correspond to
simple cycles, rather than sums of more than one simple cycle. After measuring
the checks in $m_{i+1}$, we may update the set $S$ to some set $S^{\prime}$
containing the cycles in $S$ as well as those in $C(m,m^{\prime})$. Of course,
it may be the case that there is some redundancy between these generators of
the ISG, i.e., some product may be the identity.

One source of redundancy may be some redundancy in the generators which
corresponds to cycles in $S^{\prime}$. If that occurs, we may remove some
cycles from $S^{\prime}$ to obtain a set of cycles with no redundancy. In
practice, however, this case is important for fault tolerance: such a
redundancy may occur when some elements of $C(m,m^{\prime})$ is already in $S$
and that is how we can detect if some error occurs because we are measuring
some operator whose value is already determined by the previous measurements.

Now let us compute the number of logical qubits. First, suppose that $S$ is
maximal: every product of checks corresponding to a $1$-cycle is in the ISG.
These products of checks are simply the elements of the center of ${\cal G}$
and the rank of the group generated by them is $(1/2)n_{V}+1$ as given above.
The number of checks in the perfect matching is $(1/2)n_{V}$. However, there
is a redundancy: the product of all checks in the perfect matching is equal to
the product of checks corresponding to some $1$-cycle. This $1$-cycle is
simply the sum of all checks _not_ in the perfect matching. It is easy to
verify that this is the only redundancy: suppose some product of checks in the
matching times some product of checks corresponding to a $1$-cycle is equal to
the identity. Then, every vertex has either zero or three edges attached to it
in this product (i.e., in the product of checks in the matching times the
product of checks corresponding to $1$-cycles). Suppose some vertex $v$ has
three edges attached to in the product; then, every neighbor $w$ of $v$ also
has three edges attached to it in the product, as either $w$ is attached to
$v$ by a check in the matching or by a check in the $1$-cycles. Hence, since
$G$ is connected, the claim follows. Indeed, this redundancy occurs by taking
the product of all checks in the matching times the product of all checks in
all the simple cycles which do _not_ use any checks in the matching.

So, the rank of group generated by the center of ${\cal G}$ and by checks in a
perfect matching is equal to $(1/2)n_{V}+1+(1/2)n_{V}-1=n_{V}$, and so if $S$
is maximal, there are no logical qubits. If $S$ is less than maximal, there
may be logical qubits; if $S$ contains all the simple cycles which do _not_
use any checks in the matching, then the number of logical qubits is equal
$(1/2)n_{V}$ minus the rank of $S$.

##  III Toric Codes on $2$-Complexes

Let us now consider an interesting class of graph matching codes. We consider
two types of simple cycles. One type of simple cycle we call an “avoiding
cycle”. Such an avoiding cycle is a simple cycle that does not contain any
edges of the matching. (Deleting the edges of the matching from the graph
leaves the union of all avoiding cycles.) The other type of simple cycle we
call an “alternating cycle”. An alternating cycle is one of even length, such
that the edges alternate between being in the matching and not being in the
matching.

We will consider in this section graph matching codes in which the set of
simple cycles $S$ defining the code includes all avoiding cycles and some set
$S^{\prime}$ of other cycles which is independent of the set of avoiding
cycles. The honeycomb code is an example of such a code where $S^{\prime}$ is
the set of alternating cycles, but we may consider more general $S^{\prime}$.
Here, by “independent of”, we regard a cycle as corresponding to a $1$-chain
on the graph with $\mathbb{Z}_{2}$ coefficients.

We will show that, up to a low depth Clifford circuit and use of ancillas, and
ignoring certain degenerate cases discussed below, these codes are equivalent
to codes that we may call “twisted toric codes on $2$-complexes”. First, note
that there are two qubits in each check in the matching, but in the $+1$
eigenspace of that check there is effectively only a single qubit, i.e., a
logical qubit of that code defined by that check. Here is where the use of the
low depth Clifford and ancillas comes in: we may apply a Clifford gate (such
as a CNOT or other gate, depending on the check) to replace those two qubits
in the check with a single effective qubit, and some ancilla. The check forces
that ancilla to be in a particular state (say $Z=+1$), and so we ignore the
ancillas.

Each vertex is in exactly one avoiding cycle. Except for certain degenerate
cases, the two vertices in any given edge are in _different_ avoiding cycles
from each other; a case where they are the same avoiding cycle is that the
graph $G$ has two vertices and there are three edges connecting those two
vertices. So, ignoring the case where the cycles are the same, each effective
qubit is in two checks corresponding to avoiding cycles. We may choose (by
applying single qubit Cliffords) to have these checks act as Pauli $Z$ on the
effective qubit.

Each effective qubit is also in some number of checks corresponding to cycles
$S^{\prime}$. These checks act as Pauli $X$ or Pauli $Y$ operators on the
effective qubits in that cycle, possibly multiplied by Pauli $Z$ operator on
qubits which are adjacent to that cycle, i.e., which correspond to edges
attached to a vertex in that cycle.

Let us define twisted and untwisted toric codes on a $2$-complex as follows.
We define a graph $G_{eff}$ whose vertices correspond to avoiding cycles in
$G$, with an edge between two vertices if some edge in the perfect matching in
$G$ connects a vertex in one avoiding cycle to a vertex in the other. (Remark:
if one really wants to include the degenerate case above where an effective
qubit is in only a single avoiding cycle, this can also be treated by allowing
$G_{eff}$ to have self-loops.) We place a qubit on each edge of $G_{eff}$. We
promote $G_{eff}$ to a $2$-complex by attaching $2$-cells corresponding to
cycles of $G$ in $S^{\prime}$: given an cycle $C$ in $S^{\prime}$, the edges
in $C$ which are in the matching define a sequence of edges of $G_{eff}$.
Then, we may define the untwisted toric code on that $2$-complex by placing a
qubit on each edge, placing a $Z$-stabilizer generator on each vertex, and
placing an $X$-stabilizer generator on each plaquette. We define a twisted
toric code on that $2$-complex by placing a qubit on each edge, placing a
$Z$-stabilizer generator on each vertex, and on each plaquette we place a
stabilizer generator which is a product of Pauli $X$ operators on the qubits
corresponding to edges in that plaquette possibly multiplied by some product
of Pauli $Z$ operators supported on qubits in that plaquette or adjacent to
that plaquette, and further possibly multiplied by a factor of $i=\sqrt{-1}$
if needed for Hermiticity.

So, ignoring the degenerate case, the graph matching codes where $S$ includes
all avoiding cycles are (twisted) toric codes.

In this and other $2$-complexes, we will often continue to refer to $1$-cells
as edges and $0$-cells as vertices, using the terminology of graphs rather
than complexes, as we will make use of some other graphs later.

We will say generally that a code is a (possibly twisted) toric code on a
$2$-complex if some $2$-complex exists giving that code following the
prescription of the above paragraph. For us, a $2$-complex will have some
graph for its $1$-skeleton, and the $2$-cells will be polygons attached to
cycles of the graph.

Note indeed that a CSS code is a toric code on a $2$-complex if and only if
every qubit participates in exactly two $Z$-stabilizer generators. The “only
if” direction is obvious: each edge has two endpoints. We will discuss the
“if” direction later, in Section III.4, when talking about integer homology.

The following question arises: if we consider toric codes on $2$-complexes,
what is the maximum possible distance of the code? For an untwisted toric
code, there are in fact two distances: $d_{X}$, the distance against $X$
errors and $d_{Z}$, the distance against $Z$ errors. The value of $d_{X}$ is
equal to the minimum weight of a representative of a nontrivial first homology
class while $d_{Z}$ is equal to the minimum weight of a representative of a
nontrivial first cohomology class. The weight of a representative is defined
to be the number of qubits on which it acts nontrivially.

What about the distance of a twisted toric code? We will show that, roughly
speaking, the twisting obtained from graph matching codes cannot improve the
distance compared to an untwisted code. Consider some twisted toric code
${\cal T}$ that arises from some graph matching code. Let ${\cal T}^{\prime}$
be an untwisted toric code defined in the obvious way from ${\cal T}$, using
the same $Z$-stabilizer generators, and making the plaquette stabilizers
products of Pauli $X$ around each plaquette. Then, any $Z$-type logical
operator $O$ of the untwisted ${\cal T}^{\prime}$ is a logical operator of the
twisted ${\cal T}$; one may verify that $O$ commutes with the stabilizers of
${\cal T}^{\prime}$ since they are the same as those of ${\cal T}$ up to
possibly multiplying by Pauli $Z$ operators and one may verify that $O$ is not
in the stabilizer group of ${\cal T}$ because any nontrivial product of
plaquette stabilizers of ${\cal T}$ corresponds to some nontrivial product of
cycles in $S^{\prime}$, and each such product (by assumption on indepdence of
$S^{\prime}$) will include at least one edge in the matching and hence will
act as Pauli $X$ or $Y$ on at least one effective qubit. Further, any $X$-type
logical operator of the untwisted ${\cal T}$ corresponds to some cycle in
$G_{eff}$ and hence to some cycle in $G$ in the obvious way (each edge in
$G_{eff}$ is some edge in the matching, and we combine those edges with edges
not in the matching to obtain a cycle in $G$), and that cycle in $G$ then
corresponds to some logical operator of the twisted ${\cal T}$: it will be a
product of Pauli $X$ on the edges in the cycle in $G_{eff}$, possibly
multiplied by Pauli $Z$ on qubits in or adjacent to that cycle.

The simplest example of a toric code on a $2$-complex is to consider “the”
toric code on a cellulation of a $2$-torus. In this case, one can obtain a
code with $N$ qubits and with $d_{X},d_{Z}$ both being $\Theta(\sqrt{N})$,
where $\Theta(\cdot)$ is computer science big-O notation. One may ask if one
can do better.

If we demand that the code be LDPC (low-density parity check) also then we
will show in Section III.3 that it is not possible that $d_{X}$ and $d_{Z}$
both be $\omega(\sqrt{N})$, where again we use big-O notation, and
$\omega(\sqrt{N})$ means asymptotically larger than $\sqrt{N}$. Here,

######  Definition 2.

A CSS code is LDPC if all $X$ and $Z$ stabilizers act on ${\cal O}(1)$ qubits
and all qubits are only in ${\cal O}(1)$ stabilizers (note that by
construction, each qubit is in exactly $2=O(1)$ $Z$-stabilizers).

Remark: we use computer science big-O notation throughout. When we give a
bound on distance, later, such as saying something in ${\cal O}(\sqrt{N})$, we
mean that it is bounded by a constant times $\sqrt{N}$ with the constant
depending on the constants hidden in the definition of LDPC.

###  III.1 Systolic Freedom for Codes on $2$-Complexes

There are examples of LDPC toric codes on $2$-complexes where the product
$d_{X}d_{Z}$ is polylogarithmically larger than $N$. The first example of this
is in fact the first exampleFreedman et al. (2002) of any code to achieve
$d_{X}d_{Z}$ asymptotically larger than $N$, and it is a toric code on a
cellulation of a particular $3$-manifold. The distances $d_{X},d_{Z}$ are
related to so-called “systoles” of this manifold (least area surfaces
representing nontrivial homology), and the property that $d_{X}d_{Z}\gg N$ is
derived from a property of this manifold called systolic freedom (namely that
the product of the areas of certain systoles is asymptotically larger than the
volume of the manifold). So, we use the term “systolic freedom” to refer to
$d_{X}d_{Z}\gg N$.

The second exampleEvra et al. (2022) gives $d_{X}=\Theta(\log(N))$ and
$d_{Z}=\Theta(N)$, slightly improving the power of $\log(N)$ in the product
$d_{X}d_{Z}$. In this case, the code is a toric code on a particular
$2$-complex which is a high dimensional expander.

To turn those toric codes with unbalanced distance (i.e., $d_{Z}\gg d_{X}$ but
$d_{X}d_{Z}\gg N$) into a code with $d_{Z},d_{X}\gg\sqrt{N}$, it is possible
to use a distance balancing trick. In the first example of a $3$-manifold
codeFreedman et al. (2002), this distance balancing was done explicitly by
constructing a toric code on a _four_ -manifold, with degrees of freedom on
_two_ -cells. In later examples, an abstract distance balancing trick was used
(see Hastings (2016) which was then generalized and improved in Ref. Evra et
al. (2022)), but when applied to the toric code on a $2$-complex, the result
is again a toric code on a higher dimensional complex with degrees of freedom
on cells of dimension $>1$. So, in neither case do we obtain a toric code on a
two complex. In particular, in both cases, each qubit is in more than $2$
$Z$-stabilizers.

There is however a simple way to balance distance, albeit at the cost of
breaking the LDPC property. Choose some integer $\ell>1$, and insert $\ell-1$
vertices into each edge of the $2$-complex. This subdivides each edge into
$\ell$ edges and $\ell-1$ vertices in the obvious way. As a result, the
boundaries of $2$-cells get subdivided, and the weight of each $X$-stabilizer
hence increases by a factor $\ell$, so for $\ell\gg 1$ the resulting code is
not LDPC. This subdivision multiplies the number of qubits by $\ell$, and
multiplies $d_{X}$ by $\ell$ while leaving $d_{Z}$ unchanged. So, choosing
$\ell=d_{Z}/d_{X}$ we obtain a code on $Nd_{Z}/d_{X}$ qubits with
$d_{Z}=d_{X}$. Applying this to the construction of Ref. Evra et al. (2022),
we get a code on $N^{\prime}$ qubits with
$d_{Z}=d_{X}=\Omega(\sqrt{N^{\prime}\log(N^{\prime})})$.

Remark: the reader may verify that this subdivision of each edge into $\ell$
edges is equivalent to concatenating the given code with a repetition code
with stabilizers $Z_{1}Z_{2},Z_{2}Z_{3},\ldots,Z_{\ell}$. From standard
results, this concatenation increases $d_{X}$ by a factor $\ell$, while
leaving $d_{Z}$ unchanged. The increase in weight of the $X$-stabilizers of
the concatenated code then follows since we must express $X$-stabilizers in
terms of logical operators of the repetition code.

Remark: one might attempt to restore the LDPC property by subdividing the
$2$-cells. Let us sketch a way to do this, giving a pictorial description.
Unfortunately, this way does not give the desired distance properties of the
code, but it is worth discussing. Consider some $2$-cell. Its boundary is a
circle, subdivided with $m=O(\ell)$ vertices. Draw this boundary as a circle
in the plane. Draw another circle inside it, subdivided with $\lfloor
m/2\rfloor$ vertices, and draw edges from one circle to the other, drawing the
edges without crossing. For example, label the vertices in the outer circle by
$1,2,\ldots,m$ in order around the circle, periodic mod $m$, and label the
vertices in the inner circle by $1^{\prime},2^{\prime},\ldots,(\lfloor
m/2\rfloor)^{\prime}$ in order, and then draw edges from vertex $j^{\prime}$
to vertices $2j,2j+1$ for each $j$. Fill all the holes between the two circles
in the drawing with $2$-cells, so that there are $2$-cells with boundary
containing vertices $j^{\prime},2j,2j+1$ and with boundary containing vertices
$2j+1,2j+2,j^{\prime},j^{\prime}+1$. Then, the local geometry is bounded,
meaning that every vertex attaches to only ${\cal O}(1)$ edges and so that all
$2$-cells between the circle have only ${\cal O}(1)$ cells in their boundary.
Repeat this by again drawing a circle of $\approx m/4$ vertices inside the
previous one, and so on, approximately halving the number of vertices each
time, until finally some circle has only ${\cal O}(1)$ vertices and can be
filled with a $2$-cell. This subdivision can be thought of as introducing some
“hyperbolic geometry” inside the outermost circle. Unfortunately, this
subdivision creates “shortcuts” across the outermost circle, and the distance
$d_{X}$ of the code may be reduced by a factor proportional to
$\log(\ell)/\ell$. So, it does not suffice to give us an LDPC code with
distance $\omega(\sqrt{N})$.

###  III.2 Systolic Almost-Rigidity

These examples of Freedman et al. (2002); Evra et al. (2022) both have
$d_{X}d_{Z}$ only polylogarithmically larger than $N$. However, there are
several examples of stabilizer quantum codes where $d_{X}d_{Z}$ is
polynomially larger than $N$; indeed, it is now possible to have
$d_{X}d_{Z}\sim N^{2}$. One may wonder: can one have $d_{X}d_{Z}$ polynomially
larger than $N$ if one restricts to toric codes on $2$-complexes?

The answer is no if one restrict to LDPC codes. This follows from a result
called “systolic almost-rigidity” for simplicial complexesAlpert et al.
(2022).

To use that result, first note that given any toric code into a $2$-complex,
we may turn the corresponding $2$-complex into a simplicial complex (so that
all $2$-cells are triangles) by triangulating each $2$-cell: pictorially, the
triangulation can be seen quite simply by drawing each $2$-cell as some
polygon in the plane, adding an extra vertex in the center, and drawing edges
from each vertex in the polygon to the center. This triangulation may reduce
the distance $d_{X}$ by creating “shortcuts” across the $2$-cell, but given
that the initial code is LDPC, the distance $d_{X}$ is reduced by at most a
constant factor. So, it suffices to consider toric codes on simplicial
$2$-complexes.

For toric codes on simplicial $2$-complexes, theorem 2 of Ref. Alpert et al.
(2022) shows that for any $\epsilon>0$, we have $d_{X}d_{Z}\leq{\cal
O}(N^{1+\epsilon})$. To translate that theorem into the language of codes,
their choice of a nontrivial first cohomology class $\alpha$ corresponds to
the choice of a nontrivial $Z$-type logical operator. Their quantity
$\mathrm{cut}^{\alpha}(M)$ equals the least weight representative of that
$Z$-type logical operator; see Lemma 1 below. Their quantity
$\mathrm{sys}_{\alpha}(M)$ corresponds to the minimum, over all $X$-type
logical operators which anticomute with the given $Z$-type logical operator,
of the least weight representative of that $X$-type logical operator.

Thus, the theorem actually says a stronger statement than that
$d_{X}d_{Z}\leq{\cal O}(N^{1+\epsilon})$. It says that given any nontrivial
$Z$-type logical operator, there is some $X$-type logical operator which
anticommutes with it, and some representatives of those $Z$-type and $X$-type
logical operators, such that the product of the distances is $\leq{\cal
O}(N^{1+\epsilon})$.

The authors of Ref. Alpert et al. (2022) conjecture that their theorem can be
strengthened to bound $d_{X}d_{Z}\leq{\cal O}(N\mathrm{polylog}(N))$, but do
not prove this. It is also interesting to ask whether a similar result applies
if we relax the LDPC assumption on the code.

Here is the lemma needed to translate their results to quantum information
theory langauge. Remark: similar results appear in Alpert et al. (2022) when
the complex is obtained by triangulating a manifold. There is nothing novel in
our proof of the above lemma and we give it primarily to translate their
results to quantum information theory terms.

######  Lemma 1.

Given a choice of $Z$-type logical operator $\alpha$, define a “cut” to be a
subset of qubits $H$ such that any representative of an $X$-type logical
operator which anticommutes with $\alpha$ must have support on $H$. Define
$\mathrm{cut}^{\alpha}(M)$ to be the minimum cardinality of a cut. Remark:
this is a paraphrase of the definition of Ref. Alpert et al. (2022) in quantum
information theory terms. Then, $\mathrm{cut}^{\alpha}(M)$ equals the minimum
weight of a representative of logical operator $\alpha$ and the minimum is
attained when $H$ is the support of such a minimum weight representative.

###### Proof.

First we show that if $O$ is a representative of $\alpha$, and if $H$ is the
support of $O$, then $H$ indeed is a cut. This is obvious, since if an
operator anticommutes with logical operator $\alpha$, and hence with $O$, it
must have support on the support of $O$.

Next we will show that given any cut $H$, there must be some representative
$O$ of $\alpha$ supported on $H$. Then, by the above paragraph, it follows
that the minimum cut is attained on the support of a minimum weight
representative.

To show that there is a representative of $\alpha$ supported on $H$, note that
by CNOT gates supported on $H$, and by CNOT gates supported on the complement
of $H$, we can bring the stabilizer group to the following form. There are
some stabilizers, supported on $H$ or on its complement, which are either $X$
or $Z$ on a single qubit. There are some qubits in $H$ which are in EPR pairs
with qubits outside $H$; i.e., we have two stabilizers of the form
$XX^{\prime}$ and $ZZ^{\prime}$ where the primed qubits are outside $H$ and
the unprimed qubits are inside $H$. Finally, there are some qubits with
stabilizers $XX^{\prime}$ or $ZZ^{\prime}$, but not both, again where the
primed qubits are outside $H$ and the unprimed qubits are inside $H$.

Now consider the logicals once the stabilizer group is in that form. If there
is a pair of qubits with stabilizer $XX^{\prime}$ but not $ZZ^{\prime}$, then
there are logicals $X$ (or $X^{\prime}$) and $ZZ^{\prime}$, while if they have
stabilizer $ZZ^{\prime}$ but not $XX^{\prime}$, then there are logicals $Z$
(or $Z^{\prime}$) and $XX^{\prime}$. There may also be logical qubits where
$X$ and $Z$ logical operators are both supported on $H$ or both supported on
the complement of $H$.

Any $Z$-type logical operator then is of the form $OO^{\prime}PQ$, where $O$
is a product of $Z$-type logical operators on some logical qubits where both
$X$\- and $Z$-type logicals are supported on $H$, where $O^{\prime}$ is
similar except the support is the complement of $H$, and where $P$ is a
product of $Z$-type logical operators on logical qubits where the stabilizer
group (after the transformation above) is of the form $XX^{\prime}$ (i.e., $P$
can be represented by a product of operators $ZZ^{\prime}$ on those qubits)
and $Q$ is a product of $Z$-type logical operators on logical qubits where the
stabilizer group (after the transformation above) is of the form $ZZ^{\prime}$
(i.e., $Q$ can be represented by a product of operators $Z$ on those qubits).

However, by the assumption that $H$ is a cut, $O^{\prime}$ must be the
identity operator, as otherwise there is an $X$-type logical supported outside
$H$ which anticommutes with it. Similarly, $P$ must be the identity. But then
any $Z$-type logical operator $OQ$ has a representative on $H$. ∎

###  III.3 Bound on Minimum Distance

######  Lemma 2.

Let $M$ be some $2$-complex corresponding to some LDPC code. Consider the
corresponding chain complex with $\mathbb{Z}_{2}$ coefficients. Let
$\mathrm{weight}(\cdot)$ of some cycle or cocycle denote the Hamming weight.
Consider some nontrivial $1$-cocycle $S$ which has the property that $S$
cannot be written as the sum of two cocycles, each with lower weight than $S$
and such that $S$ is a minimum weight representative of some given cohomology
class. Then $\mathrm{weight}(S)={\cal O}(\sqrt{N})$ or there is some $1$-cycle
$C$ which has inner product $1$ with $S$ such that $\mathrm{weight}(C)={\cal
O}(\sqrt{N})$.

###### Proof.

We use a graph metric for distance on the $1$-skeleton of $M$.

Let $\mathrm{supp}(S)$ be the support of $S$, i.e., the set of edges with
nonvanishing coefficient in $S$.

Define a “boundary set” of vertices to be the set of vertices which are in the
boundary of some edge in $\mathrm{supp}(S)$.

Consider the following “boundary graph” $B$: the vertex set is the boundary
set and there is an edge between two vertices if the distance between them,
using a graph metric on $M\setminus\mathrm{supp}(S)$, is bounded by the
largest diameter of a $2$-cell in $M$. We claim that this graph is connected:
indeed, if not, then for any connected component, the sum of edges in
$\mathrm{supp}(S)$ which are in the coboundary of a vertex in that connected
component would define some cocycle with lower weight than $S$, because (by
definition of the boundary graph) no $2$-cell is in the coboundary of two
different edges, with one edge in the coboundary of a vertex in one connected
component and the other edge in the coboundary of a vertex in another
connected component. The sum of these cocycles over connected components would
equal $S$.

Consider any vertex $i$ in the boundary set. For any $r$, let $b_{r}(i)$ be
the set of vertices of $M$ which can be reached from $i$ by a path of length
at most $r$ which avoids the support of $S$. Here we use the graph metric on
$M$ for the path length.

Let $c_{0}={\cal O}(1)$ be a constant chosen later. We consider two cases:
either, for some $r\leq c_{0}\sqrt{N}$, there is some edge $e$ in
$\mathrm{supp}(S)$ which is in the coboundary of two different vertices in
$b_{r}(i)$, or there is no such edge for any such $r$.

In the first case, we can identify a $1$-cycle $C$ with weight $\leq
1+2c_{0}\sqrt{N}$: the edge $e$ has two vertices $j,k$ in its boundary, and
there is some path $P$ of length $\leq 2c_{0}\sqrt{N}$ which avoids
$\mathrm{supp}(S)$ from $j$ to $k$. Then, concatenate $P$ with $(j,k)$ to get
a path of length ${\cal O}(\sqrt{N})$ which intersects $\mathrm{supp}(S)$
exactly once. Let $C$ be the $1$-cycle which is the sum of edges in that path.

So, consider the second case. In an abuse of notation, let $b_{r}(i)$ also
denote the $0$-cochain which is the sum of vertices in the given set
$b_{r}(i)$. Consider the $1$-cochain $S^{\prime}=S+\partial^{T}b_{r}(i)$,
where $\partial^{T}$ is the coboundary operator. The weight of $S^{\prime}$ is
equal to the sum of two weights, the first being the weight of $S^{\prime}$
restricted to the support of $S$, and the second being the weight of
$S^{\prime}$ restricted to the complement of the support of $S$. Calls these
weights $w_{1},w_{2}$ respectively.

We claim $\mathrm{weight}(S)-w_{1}=\Omega(r)$. Indeed, assume
$\mathrm{weight}(S)\geq c_{0}\sqrt{N}$, as otherwise the lemma follows. Then,
since graph $B$ is connected, for $r\leq c_{0}\sqrt{N}$, the intersection of
$b_{r}(i)$ with the boundary set has cardinality $\Omega(r)$, where the
constant hidden in the big-O notation depends only on the constants hidden in
the definition of LDPC, not on the choice of $c_{0}$. Note that by the
assumption that we are in the second case, there is no edge in $S$ which is in
the coboundary of two distinct vertices in $b_{r}(i)$.

So, since $S$ is minimal, $w_{2}=\Omega(r)$, as otherwise $S^{\prime}$ would
be lower weight than $S$. Hence, for all $r={\cal O}(\sqrt{N})$, $b_{r}(i)$
has $\Omega(r)$ edges in its coboundary, and hence, $b_{r}(i)$ has cardinality
$\Omega(r^{2})=\Omega(c_{0}^{2}N)$. Let us put back in the constants hidden in
the big-O notation: the cardinality of $b_{r}(i)$ is $\geq
c^{\prime}c_{0}^{2}N$, for some constant $c^{\prime}$ which depends on the
constants hidden in the definition of LDPC. However, there are only $N/2$
vertices in $M$, as there are $N$ edges. Hence $c^{\prime}c_{0}^{2}\leq 1/2$.

Since $c^{\prime}$ is fixed, we may choose $c_{0}$ large enough to give a
contradiction, i.e., $S$ has weight $\leq c_{0}\sqrt{N}$ or there is some $C$
with inner product $1$ with $S$ which has weight $\leq 2c_{0}\sqrt{N}+1$. ∎

A figure may help understand Lemma 2. See Fig. 1.

Figure 1: A sketch to illustrate the proof of Lemma 2. Suppose $M$ has the
topology of a cyclinder. The curving lines on top and bottom of the figure
represent circles in the boundary of the cylinder, and the left side of the
figure is attached to the right side to give a cylinder. $M$ occupies the
region between these lines; we do not show the cells in $M$ but they are
implicit in the figure. The vertical line is the support of $S$, i.e., the
edges in $S$ are those which cut the vertical line. The curving line in the
middle of the figure represents part of the coboundary of $b_{r}(i)$, namely
the part not touching the vertical line, in particular those edges in the
coboundary are those cut by the curving line. The number of edges cut by this
curving line represents $w_{2}$. So, as we increase $r$, the “bubble”
increases in size, and $w_{2}$ increases while $w_{1}$ decreases.

###  III.4 A Remark on Distances with Integer Homology

Out of interest, let us consider some related bounds on “distances” in the
case of integer homology. That is, we consider the homology of the chain
complex _with integer coefficients_ associated with the given $2$-complex
defined by the quantum come. At this point, we must first remark that in the
case of integer coefficients there may be more than one choice of chain
complex associated with a given quantum code. For example, suppose we have a
code on three qubits, with stabilizer generators
$Z_{1}Z_{2},Z_{2}Z_{3},Z_{3}Z_{1}$ and $X_{1}X_{2}X_{3}$. This of course
corresponds to a $2$-complex with a single $2$-cell which is a triangle, with
the edges corresponding to qubits $1,2,3$ respectively. Depending on the
orientation of the the triangle, one defines different chain complexes with
integer coefficients which agree, mod $2$, with the $\mathbb{Z}_{2}$ chain
complex corresponding to the given quantum code.

In Freedman and Hastings (2021), such an integer chain complex was called a
“lift” of the $\mathbb{Z}_{2}$ chain complex. While every $\mathbb{Z}_{2}$
chain complex admits a lift, in Ref. Freedman and Hastings (2021), it was
conjectured that not every $\mathbb{Z}_{2}$ chain complex corresponding to an
LDPC code admits a “sparse lift”. Here, a “sparse lift”, means a lift such
that every row and column of every boundary operator of the chain complex has
the sum of the absolute values of its entries bounded by ${\cal O}(1)$.

However, in the case of a code where every qubit participates in two
$Z$-stabilizer generators, the corresponding $\mathbb{Z}_{2}$ chain complex
does admit some sparse lift. This sparse lift is given by the chain complex
with integer coefficients corresponding to the $2$-complex corresponding to
that code. We now explain how to construct that $2$-complex. First define the
graph corresponding to the $Z$-stabilizer generators. Consider some $2$-cell,
which corresponds to some $X$-stabilizer of form $X_{1}X_{2}\ldots X_{k}$ on
some number $k$ of qubits. Each qubit corresponds to some edge $(i,j)$ of the
graph where $i,j$ are vertices. We identify edge $(i,j)$ with edge $(j,i)$. By
the assumption that the $Z$\- and $X$-stabilizers commute, the qubits
$1,2,...\ldots,k$ can be ordered so that the corresponding edges define some
cycle on the graph: they are in some sequence
$(i_{1},i_{2}),(i_{2},_{3}),\ldots,(i_{k},i_{1})$. Then, simply define the
boundary of the $2$-cell to be those edges
$(i_{1},i_{2}),(i_{2},_{3}),\ldots,(i_{k},i_{1})$ in that sequence, orienting
each edge from $i_{a}$ to $i_{a+1}$. In the corresponding chain complex, to
choose a basis, we will pick an arbitrary orientation of each edge. Thus, the
boundary operator acting on the given $2$-cell will map the boundary to
$\pm(i_{1},i_{2})+\pm(i_{2},i_{3})+\ldots$, where each sign depends on whether
the arbitrary orientation of each edge is from $i_{a}$ to $i_{a+1}$ or from
$i_{a+1}$ to $i_{a}$.

Now that we can define a chain complex with integer coefficients corresponding
to some quantum code, we consider the integer homology. A representative of
homology or cohomology is some vector in a vector space with integer
coefficients, and we define the weight of that representative to be the sum of
absolute values of the coefficients. We denote this weight by
$\mathrm{weight}(\cdot)$.

######  Lemma 3.

Let $M$ be some $2$-complex corresponding to some LDPC code. Consider the
corresponding chain complex with integer coefficients. Consider some
nontrivial cocycle $S$ which has the property that $S$ cannot be written as
the sum of two cocycles, each with lower weight than $S$, and such that $S$ is
a minimum weight representative of some given cohomology class. Then
$\mathrm{weight}(S)={\cal O}(\sqrt{N})$ or there is some $1$-cycle $C$ which
has nonvanishing inner product with $S$ such that $\mathrm{weight}(C)={\cal
O}(\sqrt{N})$.

###### Proof.

We use a graph metric for distance on the $1$-skeleton of $M$. Let
$\mathrm{supp}(S)$ be the support of $S$.

If necessary, we subdivide222By “subdivide”, we mean precisely that: subdivide
the $1$-cell, by replacing it with $k$ $1$-cells and $k-1$ $0$-cells arranged
in a line for some $k$. This may increase the number of $1$-cells in the
boundary of a $2$-cell, but this effect on the LDPC property does not matter
for this proof. This is primarily a bookkeeping device. the edges of $M$ so
that the cohomology representative has the property that it has coefficients
either $0$ or $\pm 1$ on each edge, e.g., if $S$ has coefficient $2$ on some
edge of $M$, we subdivide that edge in two and give the represenatative
coefficient $1$ on each edge. Then, we define “positive” and “negative” sets
of vertices: if some edge $(i,j)$ is in $\mathrm{supp}({\tilde{S}})$, then $i$
is in the positive set if the edge is oriented from $j$ to $i$ and the
coefficient is $+1$ or if the edge is oriented from $i$ to $j$ and the
coefficient is $-1$; otherwise, $i$ is in the negative set. The vertex $j$ is
in the positive set if $i$ is in the negative set and vice-versa. If needed,
we further subdivide the edges so that no vertex is in the positive set from
some edge and in the negative set from some other edge, e.g., in fact if $S$
has coefficient $2$ on some edge of $M$, we should subdivide that edge in
three, and give $S$ coefficients $1,0,1$ on the three edges in order; then,
the first vertex is positive, the second is negative, the third is positive,
and the fourth is negative. Further, we subdivide the $2$-cells of $M$, adding
additional edges, so that each two cell has only two edges with nonvanishing
coefficients in its boundary.

We refer to the subdivided $M$ simply as ${\tilde{M}}$, and refer to the
corresponding cohomology representative as ${\tilde{S}}$. On the edges of
${\tilde{M}}$ arising from subdivision, we use any metric so long as the total
length of a subdivided edge of $M$ is equal to $1$; any added edges from
subdividing $2$-cells are given length $1$.

Consider the following “positive graph” $G^{+}$: the vertex set is the set of
positive vertices and there is an edge between two vertices if the distance
between them, using a graph metric on
${\tilde{M}}\setminus\mathrm{supp}({\tilde{S}})$, is bounded by the largest
diameter of a $2$-cell in ${\tilde{M}}$. We claim that this graph is
connected: indeed, if not, for each connected component, restricting
${\tilde{S}}$ to the edges which are in the coboundary of some vertex in that
connected component would define some cocycle with lower weight than $S$; more
precisely, it gives some cocycle of ${\tilde{M}}$ which pulls back to some
cocycle of $M$ with lower weight than $S$. Define a “negative graph” $G^{-}$
similarly.

Let $\ell$ be the distance from the positive set to the negative set on the
$1$-skeleton of ${\tilde{M}}$ with $\mathrm{supp}({\tilde{S}})$ removed, i.e.,
$\ell$ is the minimal length of a path from positive set to negative set
avoiding $\mathrm{supp}({\tilde{S}})$. We claim that
$\mathrm{weight}(S)=\mathrm{weight}({\tilde{S}})\leq N/\ell$. Indeed, consider
any $d$, $0<d<\ell$. Consider the cochain equal to $C$ plus the sum, over all
vertices $v$ which can be reached by a path of distance at most $d$ which
starts at the positive set and avoids the support of ${\tilde{S}}$, of the
coboundary of $v$. This is some other cochain which has the same inner product
with $C$, and for distinct $d$ these cochains are disjoint. By assumption that
the given $S$ is minimal (and hence ${\tilde{S}}$ is minimal), each of these
other cochains has weight $\geq\mathrm{weight}(S)$ and their sum is at most
$N$.

Now, for any integer $k\geq 1$, define a $k$-fold cover of ${\tilde{M}}$ in
the obvious way, using the ${\tilde{S}}$ as a “cut” to define the cover333i,e,
vertices in the cover are labelled by a pair, giving a vertex in the
${\tilde{M}}$ and an integer taken periodic mod $k$. Going from positive to
negative set in ${\tilde{S}}$ increases this integer by one, while going on
other edges does not change the integer.. Call this cover ${\tilde{M}}(k)$.
Choose some pre-image of ${\tilde{S}}$ in this cover such that it gives a
nontrivial cocycle of the same weight as ${\tilde{S}}$; call this pre-image
${\tilde{S}}(k)$, and define positive and negative graphs and positive and
negative sets as before. Note that ${\tilde{S}}(k)$ is minimal weight, as any
cocycle of lower weight in the cover ${\tilde{M}}(k)$ would define some
cocycle of lower weight than ${\tilde{S}}$ in ${\tilde{M}}$ by applying the
covering map. Now we claim that the distance from the positive to the negative
set in the $1$-skeleton of ${\tilde{M}}(k)$ with
$\mathrm{supp}({\tilde{S}}(k))$ removed is at most $k\ell\leq
kN/\mathrm{weight}(S)$. Indeed, this follows by the same argument as in the
above paragraph.

So, there is some path of length at most $kN/\mathrm{weight}(S)$ from the
positive to the negative set in the $k$-fold cover, and under the covering map
this defines some path in ${\tilde{M}}$ which starts on the positive set, goes
from the negative set to the positive set $k-1$ times by an edge in
${\tilde{S}}$ without ever going from positive set to negative set by an edge
in ${\tilde{S}}$, and finally ends on the negative set. Extend this path by a
single step so that it finally ends on the positive set. Call the resulting
path $P$. This path $P$ crosses from negative to positive set a total of $k$
times by an edge in ${\tilde{S}}$. Let $i_{1}$ be the start of path $P$. When
path $P$ crosses from negative set to positive set for the $m$-th time, call
that point in the positive set $i_{m+1}$. So, we have a sequence of points
$i_{1},i_{2},\ldots,i_{k+1}$ on the positive set.

Pick $k=\lceil c\cdot\mathrm{weight}(S)/\sqrt{N}\rceil$ for a constant
$c={\cal O}(1)$ chosen later, so that $P$ has length ${\cal O}(\sqrt{N})$.
Note that we may assume $\mathrm{weight}(S)=\Omega(\sqrt{N})$ as otherwise the
lemma follows.

Since the positive set is connected, and since by assumption
$\mathrm{weight}(S)=\Omega(\sqrt{N})$, then within distance $\sqrt{N}$ of any
point in the positive set there are $\Omega(\sqrt{N})$ other points in the
positive set. Picking $c={\cal O}(1)$ large enough, then, by the pigeonhole
principle, there must be some $m,n$ with $1\leq m<n\leq k$ such that some
point within distance $\sqrt{N}$ of $i_{m}$ is also within distance $\sqrt{N}$
of $i_{n}$ by a path which avoids $\mathrm{supp}({\tilde{S}})$, and so $i_{m}$
is within distance $2\sqrt{N}$ of $i_{n}$ by such a path; denote that path
from $i_{m}$ to $i_{n}$ by $Q$. Now form the following closed path $C$: use
some segment in the middle of path $P$ to get a path from $i_{m}$ to $i_{n}$
which crosses from negative set to positive set $n-m$ times and so has inner
product $n-m$ with ${\tilde{S}}$, and then concatenate that segment with $Q$.
This gives a closed path $C$ of total length at most ${\cal O}(\sqrt{N})$.
This path corresponds to a $1$-cycle of weight ${\cal O}(\sqrt{N})$ which has
inner product $n-m$ with ${\tilde{S}}$.

If we had done some subdivision at the start of the proof, we deform the this
$1$-cycle $C$ so it lies on the $1$-skeleton of $M$, avoiding any edges in
$\tilde{M}$ used to subdivide $2$-cells, leading to at most an ${\cal O}(1)$
factor increase in weight. ∎

Remark: note that the inner product of $C$ with $S$ may be even. So, if we had
considered the case of $\mathbb{Z}_{2}$ coefficients, and we had assumed that
some nontrivial cocycle $S_{0}$ with $\mathbb{Z}_{2}$ coefficients lifts to
some cocycle $S$ with integer coefficients, it is possible that $C$
constructed in the above lemma might not give a cycle with $\mathbb{Z}_{2}$
coefficients which has nontrivial inner product with $S_{0}$.

##  IV Vacancies and High Weight Vertices in Check Graph

###  IV.1 Vacancies and Check Graph

An interesting question studied by several authors is how to deal with dead
qubits in a planar quantum code. Suppose qubits are chosen randomly and
independently to be dead with some probability $P_{\rm fail}$. For small
enough $P_{\rm fail}>0$, for small enough noise probability $p$, is the
probability of a logical error vanishing in the thermodynamic limit?

We are interested in the question of “circuit level noise”. In a simple model
of this, one alternately applies noise and measures stabilizers with some
probability of error in the stabilizer measurement; the goal is to preserve
logical information for some time which diverges as the system becomes large.

To have a threshold, it is necessary to measure “super-stabilizers”. That is,
dead qubits create holes in the lattice, which create extra logical qubits.
The “super-stabilizers” measure these new logical operators. Various schemes
have been proposed in both surface and Floquet codesTang and Miao (2016);
Auger et al. (2017); Nagayama et al. (2017); Strikis et al. (2021); Siegel et
al. (2022); Aasen et al. (2023) and a threshold has been proven in one
particular schemeStrikis et al. (2021) with a carefully chosen schedule to
measure the super-stabilizers where one has long periods (with a time
depending on the size of the hole) in which the hole has one boundary
condition followed by long periods in which the hole has a different boundary
condition.

However, no threshold has been proven in what are perhaps the most natural
schemes, in which the hole alternates its boundary conditions on a time ${\cal
O}(1)$. These schemes lead a “check graph” with columns of high weight
vertices in spacetime, making a simple Peierls argument failAasen et al.
(2023). We analyze the statistical mechanics of this situation. Our goal is
not to prove a threshold; rather, our goal is to give give statistical
mechanics arguments for the correct asymptotics of decoding in this case.

First, let us say what a check graph is. We are considering the question of
using a quantum code as a memory, where it is run for some long time, and we
repeatedly measure stabilizers or checks of the code, while errors can occur
at arbitrary times. For simplicity, time is taken to be discrete. For some
codes (such as surface code or the honeycomb code), it is possible to find a
basis of Pauli errors (i.e., choosing to expand errors in a particular basis
of two of the three possible single qubit Pauli operators) such that each
error will cause one or two “detection events” to occur. If each error causes
two detection events, we can construct a check graph, where each edge of this
corresponds to some possible error location in spacetime and and some type
(i.e. Pauli $X,Y$, or $Z$) of error, and where each vertex corresponds to some
detection event, where a detection event is some particular product of
measurements that should equal some fixed value $\pm 1$ if no error occurs. An
error on an edge flips the detection events in the vertices attached to that
edge. For some given error pattern (which is a $1$-chain, i.e., a sum of
edges) that occurs, and some given resulting pattern of detection events, a
decoder finds a decoding by choosing some other error pattern such that the
sum of the two error patterns is a $1$-cycle.

We have said that an error may cause one or two detection events. This means
we also allow “dangling edges” in a check graph. A dangling edge only has a
detection event on one of its vertices, and corresponds to an error which
causes only one detection event. These will be convenient to use later. Edges
are not dangling unless otherwise specified.

In a code like the surface code, there actually are two distinct check graphs,
one for $Z$-type errors and one for $X$-type errors.

There is a useful homological description. We have associated error patterns
with $1$-chains with $\mathbb{Z}_{2}$ coefficients: the chain has a
coefficient $1$ on cells in the given error pattern. Implicitly, we also have
some $2$-cells attached to the graph, any two $1$-chains in the same homology
class describe the same decoding.

For example, let us first describe the check graph and $2$-cells for a simple
model without vacancies. Consider a square lattice (of size depending on the
number of qubits). There is a $2$-cell for each square in the lattice. Call
this the “spatial check graph”. Now take this spatial check graph and cross it
with a cellulation of the interval with $T$ $0$-cells for some integer $T$
giving the total time for which we run error correction, i.e., take the
homological product of this $2$-complex with this $1$-complex. The product
gives some graph in three dimensions. Every vertex in the product then
corresponds to a pair: a vertex in the spatial check graph and a time
coordinate. We describe edges in the product as “spacelike” or “timelike” in
the obvious way: spacelike edges connect vertices with the same time
coordinate. We use the term “time slice” to describe a subcomplex consisting
of all $0$-, $1$-, and $2$-cells at a given time coordinate.

The spatial check graph can be considered on various topologies to give
nontrivial homology, i.e., to encode logical qubits. For example, it could be
on a torus, or, to make it planar, it could correspond to a patch of surface
code with “rough” boundary conditions on one pair of opposite edges and
“smooth” boundary conditions on the opposite pair of edges. In the second
case, rough boundaries have dangling edges for one type of Pauli error, while
smooth boundaries have dangling edges for the opposite type of Pauli error,
and nontrivial homology representatives are described by chain stretching from
one face to the opposite face.

Now we describe the check graph for these planar quantum codes with vacancies.
We actually give a “cartoon” of the check graph, giving a slightly simplified
model that skips over some details. However, this model captures the essential
features of high degree vertices, and the results in this model should apply
also to more specific models with some modifications of details.

We will call the model described here the “vacancy model”.

First, a spatial check graph is obtained in a few steps starting with the
square lattice. First, remove edges, corresponding to the dead qubits. Remove
any vertices and $2$-cells attached to removed edges. This will create some
“holes” in the graph. Note our terminology: a “hole” is created by removing
one or more edges corresponding to dead qubits. At the center of each hole,
add a single vertex. We will call this vertex the “hole center” later. Attach
one edge from the hole center to each vertex around the boundary of the hole,
drawing the edges so that they do not cross, and attach $2$-cells to each
region in the spatial check graph bounded by these added edges.

Importantly, note that if there are many dead qubits, the hole center may have
high degree.

Now again we take this spatial check graph and cross it with a cellulation of
the interval with $T$ $0$-cells for some integer $T$ giving the total time for
which we run error correction, i.e., take the homological product of this
$2$-complex with this $1$-complex.

This gives some three-dimensional graph. We will call any instead of this
graph $G_{\rm bulk}$ below. The “bulk” of $G_{\rm bulk}$ refers to any area
away from a high degree vertex.

The error model that we consider has a probability of $p$ that there is an
error on each edge, independently of other edges. This includes both spacelike
and timelike edges.

Our general picture is the following. As is well-known and as we review below,
various decoders (both Monte Carlo and minimum weight decoders) lead to error
chains which are $1$-cycles by combining the actual errors with the error
pattern given by the decoder. These $1$-cycles can be decomposed into closed
paths (i.e., a single cycle may decompose into several closed paths), and a
logical error may occur if homologically nontrivial paths exist. Away from the
high degree hole centers, a Peierls argument (reviewed below) works to bound
the probability of long chains and we in fact believe that this picture is
quantitatively correct (up to subleading corrections) at small enough $p$ in
the thermodynamic limit.

However, this Peiers argument breaks down near the high degree vertices.
Further, as we show below, near a high degree vertex, even a maximum
likelihood decoder has its limitations. We begin with a simplified model in
which errors can occur only on edges very close to the vertex, and find that
even a maximum likelihood decoder has a performance which is exponentially
poor in the degree of the vertex. In the simplest problem, we just consider a
column of high degree vertices, with some nontrivial homology (induced by
either taking it periodic in the time direction or adding dangling edges at
the initial and final times), and we find that the distance in the time
direction must be exponentially large in the degree to decode significantly
better than random chance. Then, of course, if a column of high degree
vertices exists in a larger graph $G_{\rm bulk}$, the decoding can only get
worse. However, we believe that our toy model essentially captures the problem
of decoding near a high degree vertex. Our general picture then is that the
dominant way in which we can have a homologically nontrivial error chain is
that in the bulk the error chains are as short as possible, and can be
described by a Peierls argument, but near a hole center it is hard to
distinguish different error chains. We believe that an effective model is to
consider a new graph as follows. The spatial check graph is given by taking
one vertex for each hole center. In addition, we have one vertex for every
vertex in $G_{\rm bulk}$ with a dangling edge. There is an edge between every
pair of vertices. Then take the product of this spatial check graph with a
cellulation of an interval. The probability of error on each edge is as
follows: for a spacelike edge, the error probability is as given by a Peierls
argument (roughly $p$ raised to the power of half the distance between
centers), and is exponentially small in the spacing between the two hole
centers (on a torus, one takes the shortest path; if homologically
inequivalent paths have the same lengths, then the error probability is
exponentially small in system size and so is negligible in the thermodynamic
limit). For a timelike edge, the error probability is described by our
simplified models of decoding near a hole center below, and so the error
probability is exponentially close to $1/2$. Given this simplified model, it
is possible that a Peierls argument works, depending on the error
probabilities on the various edges: while the error probability is very close
to $1/2$ on timelike edges, there is only one such path and weights for the
paths to other hole centers are exponentially small. Indeed, if the hole
centers are sufficiently separated than a Peierls argument will work. However,
the Peierls argument will fail if two sufficiently high degree hole centers
are sufficiently close in space. We analyze this case in the end, and argue
that a correct description is that they are replaced by a single vertex of
higher degree. For typical disorder configurations, ultimately one ends at an
effective model that can be treated by a Peierls argument.

An Application of this Effective Model— Before explaining where the effective
model (with one vertex per hole center) arises, we give a brief application.
Consider a toric code on a square patch of linear size $\ell$, with smooth
boundaries on two opposite sides and rough boundaries on the other sides. If
there are no vacancies, then we use a Peierls argument to estimate the error
probability. After a time $T$, the error probability is $\approx T\exp(-cL)$
for some constant $c$ depending on $p$ determined by the Peierls argument. Of
course, for large enough $T$, the error probability saturates at $1/2$..
Suppose instead we have a single hole, with hole center of degree $d$, at
distance $r$ from one side and distance $\ell-r$ from the opposite side, with
$r\leq\ell/2$.

Now, we can have a path of errors from one side to the opposite side going
through the hole center. For small $T$, the error probability is $\approx
T^{2}\exp(-cL)$. The error probability on the timelike edge on the hole center
is $1/2$ minus $\approx\exp(-c^{\prime}d)$ for some some constant $c^{\prime}$
depending on $p$, Once $T$ becomes large compared to ${\rm
min}(\exp(-cr),\exp(c^{\prime}d))$, then the error probability crosses over to
linear behavior. If $\exp(-cr)\ll\exp(-c^{\prime}d)$, then the error
probability crosses over to $T\exp(c^{\prime}d)\exp(-cL)$. If
$\exp(-cr)\gg\exp(-c^{\prime}d)$, then the error probability crosses over to
$T\exp(-c(\ell-r))$.

Maximum Likelihood and Monte Carlo Decoding— Recall how maximum likelihood
decoding works for a decoding graph. Maximum likelihood decoding can be
obtained by defining a certain statistical mechanical model. In this model,
the only allowed error patterns are those which give the observed syndrome,
and each error pattern has a probability proportional to $(p/(1-p)))^{n_{E}}$,
where $n_{E}$ is the total number of errors in the given patternDennis et al.
(2002). We can then compute the probability that the error pattern is in a
given homology class, and the most likely homology class defines the maximum
likelihood decoding. This can equivalently be describing by saying: compute,
for each homology class, a “partition function in the homology class” which is
the sum over all patterns in that class with weight $(p/(1-p))^{n_{E}}$, and
take the homology class with the largest partition function. The relative
partition functions in different classes give the relative probabilities of
the different decodings.

We can give these error patterns a pictorial description that will be useful
later. Let us color edges where an error actually occurs with a red color. The
partition function in a given homology class is a weighted sum over error
patterns that give the same boundary. Consider any such error pattern and
color edges of the graph in that error pattern blue. Thus, the edges of the
graph may be colored red, blue, neither, or both. The edges which are colored
once form a closed $1$-chain.

We will refer below to the particular pattern of red colored edges as the
“quenched disorder” as that is what it is in the context of a statistical
mechanics model.

We can define a different decoder that we call a Monte Carlo (MC) decoder.
This decoder picks a random blue coloring, such that it has the same boundary
as the red coloring, with a probability proportional to $(p/(1-p)))^{n_{E}}$.

######  Lemma 4.

Suppose that the Monte Carlo decoder has some probability $P$ of making an
error in a case where there are only two homology classes. Then, the
probability that the MC decoder makes an error is $2P(1-P)$.

###### Proof.

For given $P$, the probability that the correct homology class is the one
found by the maximum likelihood decoder is $1-P$, while the probability that
the other class is correct is $P$. The MC decoder then picks from the class
found by the maximum likelihood decoder with probability $1-P$ while it picks
from the other class with probability $P$. ∎

Note then that if $P$ is exponentially small, the probability that the MC
decoder makes an error is also exponentially small.

The reason we define the MC decoder is that it is useful in results like Lemma
6 below. We will break our analysis of the decoding problem into analyzing
decoding on some subproblems, and then put those results together. This is
slightly easier to describe with the MC decoder. The reason is, we have
several probabilities to track, describing random error patterns and
describing the confidence that a maximum likelihood decoder has that it gives
the correct decoding on a subproblem (this confidence is important when
combining problems), while for the ML decoder we can combine these into a
single probability.

Peierls Arguments— Next let us recall how a Peierls argument for a threshold
works. We discuss it for both maximum likelihood and minimum weight decoders.
The Peierls argument works on graphs of bounded degree, but can break down
with unbounded degree graphs.

We begin with an MC decoder.

If there are no dangling edges in the graph, then edges colored with exactly
one color form a collection of closed loops, while if there are dangling edges
in the decoding graph there may also be paths beginning and ending at dangling
edges. If some vertices in the decoding graph have degree greater than three,
there may be some ambiguity in how to write it as loops. For example, we could
have a “figure-eight” configuration that could be regard as either one or two
loops. This ambiguity does not matter for what is below.

For a Peierls argument, consider any path $C$, which forms either a closed
loop or begins and ends at dangling edges. Let $C$ have $|C|$ edges. We
compute the probability that every edge in $C$ is colored exactly once. The
probability that we consider here is an average over disorder (which may color
some of the edges in $C$ red) of the probability (using statistical weight
proportional to $(p/(1-p))^{n_{E}}$) that the remaining edges are colored blue
and the edges colored red do not get colored blue.

Let’s first emphasize what we need to calculate by giving a _wrong_ way of
calculating this statistical weight. To upper bound this probability, one
might consider the relative statistical weight of configurations where each
edge in $C$ is colored exactly once to those where no edge is colored. There
are $2^{|C|}$ possible ways of coloring each edge in $C$ exactly once. For
each way, there is a one-to-one correspondence between configurations with
that coloring of edges in $C$ and configurations where no edge in $C$ is
colored: simply take any configuration with the given coloring of edges in
$C$, and erase the colors on all edges in $C$. One might then naively consider
the relative probability (considering again both the statistical weight of the
statistical mechanical model and the probability that we there was an error
pattern which gave the given red coloring of the edges in $C$) of these two
configurations and think that it is $(p/(1-p))^{|C|}$.

However, this is not correct! For any given quenched disorder, the statistical
weight of the blue coloring is proportional to $(p/(1-p))^{n_{E}}$, but the
weight depends upon the quenched disorder! Indeed, it should be clear that the
calculation is not correct: if slightly more than half of the edges in $C$ are
colored red, then (taking the coloring of edges not in $C$ fixed) it is likely
that the remaining edges will be colored blue, so the probability of having
all edges colored once is more like $(p/(1-p))^{|C|/2}$ rather than
$(p/(1-p))^{|C|}$.

Rather, a correct way is to consider each of the $2^{|C|}$ subsets of edges in
$C$. Call a subset $S$. We consider the probability that the edges in $S$ are
colored red and the edges in $C\setminus S$ are not colored red. Then, for
that $S$, we consider the probability of an event $E_{S}$ that the edges in
$C\setminus S$ are colored blue while those in $S$ are not colored blue; to
upper bound this probability, we consider the relative probability of two
events of configurations, one where event $E_{S}$ occurs, and the other where
event $E^{\prime}_{S}$ occurs in which the edges in $S$ are colored blue while
those in $C\setminus S$ are not colored blue. There is again a one-to-one
correspondance between such configurations: simply change which edges on $C$
are colored blue. The relative statistical weight of the two events $E_{S}$
and $E^{\prime}_{S}$ is $(p/(1-p))^{|C|-2|S|}$. So, the probability of event
$E_{S}$ occurring is at most

$\frac{(p/(1-p))^{|C|-2|S|}}{(p/(1-p))^{|C|-2|S|}+1}.$

So, Averaging over choices of $S$, with the probability of a given $S$ being
$p^{|S|}(1-p)^{|C|-|S|}$,

######  Lemma 5.

The probability that each edge in $C$ is colored exactly once in an MC decoder
is bounded by

$\sum_{m=0}^{|C|}{|C|\choose
m}p^{m}(1-p)^{|C|-m}\frac{(p/(1-p))^{|C|-2m}}{(p/(1-p))^{|C|-2m}+1},$

which is exponentially small in $|C|$.

A similar Peierls argument may be made for a minimum weight decoder. Indeed,
the minimum weight decoder may be obtained by a statistical mechanical model
where we sum over error patterns with some weight
$(p^{\prime}/(1-p^{\prime}))^{n_{E}}$ and take a limit as
$p^{\prime}\rightarrow 0$. One may use the same argument as above with this
modified weight.

We can apply these Peierls arguments to prove a threshold if the maximum
vertex degree is ${\cal O}(1)$. Consider a spatial check graph of linear size
$L$ for some $L$. Suppose all nontrivial homology representatives have length
at least $L$ and end on some boundary of the spatial decoding graph at
arbitrary time so that there are ${\cal O}(L)T$ possible starting points. If
an error is made, then there must be a path of edges colored once which gives
such a nontrivial representative. For any given path of length $\ell$, the
probability that the edges in that path are colored once is ${\cal
O}(p)^{\ell}$, while the number of paths of length $\ell$ for any $\ell$ with
a given start position is bounded by ${\cal O}(1)^{\ell}$ where the ${\cal
O}(1)$ depends on the maximum vertex degree. So, by a union bound, the
probability of an error is bounded by

$\sum_{\ell\geq L}{\cal O}(p)^{\ell}{\cal O}(L)T,$

and or small enough $p$, this is bounded by $T$ times some quantity
exponentially small in $L$.

Decoding With a Column of High Degree Vertices: Simplest Model— To begin,
consider the following toy model of a high degree check graph. We have $T$
vertices, labeled $i=0,\ldots,T-1$. We have $d$ edges from vertex $i$ to
vertex $i+1\mod T$, for all $i$, so that each vertex has degree $2d$ and there
are $Nd$ edges.

This check graph actually arises in a familiar code, a generalization of
Shor’s 9 qubit code. Take a repetition code in the $Z$ basis on $T$ qubits and
concatenate it with a repetition code in the $X$ basis on $d$ qubits. Label
qubits by pairs $(x,y)$ for $x\in 0,\ldots,T-1$ and $y\in 1,\ldots,d$. Then
there are stabilizers $X_{x,y}X_{x,y+1\mod d}$ for all $x,y$, as well as
stabilizers $(\prod_{y}Z_{x,y})(\prod_{z}Z_{x+1,z})$ for all $x$ for all $x$
(the $x$ coordinate is periodic in $T$ so $x=T$ is the same as $x=0$). The
check graph we have given describes correction of $X$ errors when errors occur
only at a single time (i.e., we use the quantum code in a communication
channel rather than as a memory). Each vertex is a single $Z$-stabilizer. This
quantum code encodes a single logical qubit.

Consider some random pattern of $X$ errors, choosing $X$ errors on each edge
of this check graph independently with some probability $p$. Thus, on each
$d$-tuple of edges between any pair of vertices $i,i+1\mod T$, we have either
an even or odd number of $X$ errors. The probability that there are an even
number of $X$ errors on that $d$-tuple equals

$\frac{1+(1-2p)^{d}}{2},$

while the probability that there are an odd number of of $X$ errors on that
$d$-tuple equals

$\frac{1-(1-2p)^{d}}{2},$

so that as $d$ becomes large, at fixed $p$, both probabilities approach $1/2$
exponentially.

A decoder then finds some other pattern of errors so that in the sum of the
two error patterns, all edges have the same parity of errors on each
$d$-tuple, either even or odd, so that the pattern of errors found by the
decoder produces the same pattern of detection events as the actual errors.
The decoder will decode correctly if the sum of the two error patterns has
even parity on all edges.

Indeed, then, all that matters is whether the decoder chooses an even or odd
number of errors on each $d$-tuple, so it suffices to have the decoder take
either $0$ or $1$ error on each $d$-tuple, say, so that there are only two
possible decodings that the decoder considers on each $d$-tuple.

This decoding problem is then the same as decoding a simpler check graph: a
check graph with $T$ vertices of degree $2$, with one edge from vertex $i$ to
vertex $i+1\mod T$, for all $i$, where there is a probability
$\frac{1-(1-2p)^{d}}{2}$ of having an error on an edge. One may see that it
requires $T$ exponentially large in $d$ for the decoder to have a decoding
probability significantly better than $1/2$. Indeed, _the probability that a
maximum likelihood or MC decoder makes an error on this check graph with $T$
vertices of degree $2d$ is exponentially small in $T(1-2p)^{d}$._ To see this,
note that this is the same as the problem of decoding a classical one-
dimensional Ising model or repetition code: we have $T$ spins, each
initialized in some unknown configuration, either all up or all down, and we
flip each spin with probability $\frac{1-(1-2p)^{d}}{2}$. Then, maximum
likelihood decoding is the same as majority decoding, with the given
probability of error. Indeed, let’s suppose that $T$ is odd. Then error occurs
if we flip more than $\lfloor T/2\rfloor$ spins, so the error probability is

$\sum_{S\geq\lfloor T/2\rfloor}{T\choose S}p_{eff}^{S}(1-p_{eff})^{T-S},$

where $p_{eff}=(1-2p)^{2}$.

We may consider a slightly modified version of this check graph which has
dangling edges. Simply “cut” the edges from vertex $0$ to vertex $T-1$, so
that those two vertices each have $d$ dangling edges, and also $d$ edges going
to other vertices. Call this graph $C_{\rm column}$ Again, _the probability
that a maximum likelihood or MC decoder makes an error on this check graph
$C_{\rm column}$ with $T$ vertices of degree $2d$ and dangling edges is
exponentially small in $T(1-2p)^{d}$._

Remark: in fact, a minimum weight matching decoder will give the _same
decoding_ as a maximum likelihood decoder for both of these check graphs.
However, the minimum weight matching decoder is, in some sense, “too
confident” in the decoding. That is, we can consider the minimum weight
decoding for a given choice of the two possible logical decodings. Both of
these minimum weight decodings have either $0$ or $1$ error on each $d$-tuple
of edges and they are complements of each other. Suppose, for example, we take
a fixed $T=1$; then, the difference in the weight of these two decodings is
always equal to $1$, independently of $d$, even though one has only
exponentially small information about the true decoding. That is, the
difference in the weights of the two different minimum weight decodings does
not accurately reflect how much information we have. Indeed, this is why we
consider minimum weight and MC decoders.

Finally, it is useful to generalize this model to the case in which the edges
in the check graph may have different error probabilities. We take $T$
vertices, labeled $i=0,\ldots,T-1$. We have $d$ edges from vertex $i$ to
vertex $i+1\mod T$, for all $i$, so that each vertex has degree $2d$ and there
are $Nd$ edges. We label the edges by a pair $(x,y)$ for $x\in 0,\ldots,T-1$
and $y\in 1,\ldots,d$ and we let the error probablity be $p_{y}$ for some $y$.
Note then that in this model the error probabilities do not depend on $x$.
Then, again on each $d$-tuple of edges between any pair of vertices $i,i+1\mod
T$, we have either an even or odd number of errors and the probability that
there are an even number of errors on that $d$-tuple equals

$\frac{1+\prod_{y=1}^{d}(1-2p_{y})}{2},$

while the probability that there are an odd number of of $X$ errors on that
$d$-tuple equals

$\frac{1-\prod_{y=1}^{d}(1-2p_{y})}{2}.$

Thus, it is the same as decoding in the case $d=1$ with an error probability
on an edge equal to $\frac{1-\prod_{y=1}^{d}(1-2p_{y})}{2}.$ So, the
probability of making an error in decoding is exponentially small in
$T\prod_{y=1}^{d}(1-2p_{y})$.

Decoding Near The Hole Center— Now we consider a model of decoding _near_ a
hole center of degree $d$ in the graph $G_{\rm bulk}$. Specifically, we assume
that all error probabilities are zero except for spacelike edges connecting
some hole center to one of its neighbors and for timelike edges attached to
either the hole center or one of its neighrbors. This decoding problem is the
same as taking the spatial check graph to contain just the hole center and its
neighbors, with only edges from the hole center to neighbors, rather than
between neighbors.

If there is no quenched disorder, then the statistical mechanics of the MC
decoder here would be easy to solve using transfer matrix methods, being a
one-dimensional system. With quenched disorder, this becomes more difficult.
So, we give an approximate treatment valid for small $p$.

First, the shortest path from the center hole, back to the center hole, but at
a different time, is length $3$. This has a spacelike edge from the center
hole to a neighbor at some time $s$, $0\leq s\leq T$, then a timelike edge
from that neighbor to itself at a different time $s+1$, then a spacelike edge
back to the center hole. It is possible that all three of these edges are
colored red. This occurs with probability $p^{3}$ for any such path. There is
some “interference” between these events: if we have such a path with some
given $s$, then it overlaps with the analogous path going to the same neighbor
at some time $s^{\prime}=s\pm-1$. However, for small $p$, we expect that this
interference is negligible. So, we expect that the effect is as if we
considered the simplified model $C_{\rm column}$ where there are $d$ edges
which each have error probability $p^{\prime}=p^{3}$.

However, it is also possible that only some of those edges are colored red but
that the decoder makes a mistake. Indeed, we observe violated checks in the
graph on some neighbor at time $s$ and at time $s+1$. This can occur if we
color red the timelike edge from that neighbor at time $s$ to itself at time
$s+1$, but do not color red any of the spacelike edges attached to it. This
occurs with probability $p-o(p^{2})$ on any given path of three edges.
Alternatively, it can occur if we color red the two spacelike edges attached
to that neighbor at times $s$ and $s+1$, which occurs with probability
$p^{2}-o(p^{3})$. So, typically for any time $s$, there will be $\approx pd$
neighbors for which we have violated checks at the time $s$ and at $s+1$. If
we color blue the timelike edge connecting those checks, then with probability
$p+o(p^{2})$ we color each edge in the length $3$ path once. So, we expect
that the effect is as if we had $\approx pd$ edges in the simplified model
$C_{\rm column}$ which each had error probability $p$. Again, some
“interference” is possible, between this path at some time $s$ and the
analogous path at times $s^{\prime}=s\pm 1$, but again for small $p$, we
expect that this interference is negligible.

Another possibility is that we observe a violated check in the graph on some
neighbor at time $s$ but no violated checks at some $s+1$ or $s-1$. This can
occur if we color red the spacelike edge from that neighbor at time $s$ to the
center hole, but do not color red any of the timelike edges attached to it.
This occurs with probability $p-o(p^{2})$ on any given path of three edges.
Alternatively, it can occur if we color red the exactly one of the two
timelike edges attached to it, going from that neighbor to itself at time
$s\pm 1$, and also color red the spacelike edge from that neighbor at time
$s\pm 1$ to the center hole. So, typically for any time $s$, there will be
$\approx pd$ neighbors for which we have violated checks at the time $s$ but
not at $s\pm 1$. If we color blue the spacelike edge from that check to the
center hole, then w with probability $2p+o(p^{2})$ we color each edge in the
length $3$ path once; note the factor of $2$ in front of $2p$ due to the two
possible ways in which we can make an error. So, we expect that the effect is
as if we had $\approx pd$ edges with error probability $2pd$. Again, some
“interference” is possible but expected to be negligible at small $p$.

Thus, an approximate description should be by a model $C_{\rm column}$ with
$d$ edges with effective error probability $p^{3}$, and $pd$ edges with
effective error probability $p$ and $pd$ edges with effective error
probability $2pd$. From the discussion above, the probability of making an
error in decoding is then exponentially small in $T\prod_{y=1}^{d}(1-2p_{y})$,
where $p_{y}$ are the error probabilities on these effective edges. In this
case, this is $\prod_{y=1}^{d}(1-2p_{y})\approx\exp(-3(p^{2}+o(p^{3}))d)$ and
so the effective error probability is exponentially small in
$T\exp(-3(p^{2}d+o(p^{3})))$.

Now suppose we wish to consider decoding with a single high degree hole in
$G_{\rm bulk}$, with dangling edges from the hole center at times $0$ and $T$.
The above analysis considered only paths of length $3$ going from the hole
center to itself. We expect that longer paths are negligible, being higher
order in $d$, and so the effective error probability will still be
exponentially small in $T\exp(-3(p^{2}d+o(p^{3})))$.

While we will not prove that the longer paths are negligible, it is possible
to give a power series treatment of their effects in the limit of small $p$.
If it could be proven that this series converges, then this would give a proof
of our conjecture for the decoding of a single high degree hole. The decoder
we analyze does the following. In the first step, it does an MC decoder on a
modified graph, where we remove the center hole, and replace all the edges
from neighbors of the center hole to the center hole with dangling edges
attached to those neighbors. Note that the degree of this modified graph is
bounded! In the second step, it takes the blue coloring that it finds, and
uses that blue coloring on the original graph $G_{\rm bulk}$, coloring each
edge the same way as on the modified graph; an edge from a neighbor of the
hole center to the hole center is colored the same way as the dangling edge.
Having done this, there are only two possible colorings of the timelike edges
on the hole center. It picks the minimum weight such pattern.

To determine whether or not the decoder makes an error, consider each time
$S$. Consider all the timelike edges from time $S$ to time $S+1$ , including
both those on the hole center and not on it. Count the number of such edges
colored red. Also count the number of such edges colored blue in the first
step. Add these two totals, modulo $2$. If the total is odd, then say that an
“overall error” occurs between times $S,S+1$. If more than $T/2$ overall
errors occur, then in the second step the decoder makes a logical error; if
less than $T/2$ occur, then it does not.

Now, can we compute the probability that more than $T/2$ overall errors occur?
First, consider the average number of overall errors. Pick any given time $S$.
For each timelike edge $e$ from $S$ to $S+1$, let $Z_{e}$ equal $-1$ if edge
$e$ is colored an odd number of times, and $+1$ otherwise. If we can compute
the average of $\prod_{e}Z_{e}$, then we can straightforwardly compute the
probability that there is an overall error between times $S,S+1$, as this
product is $-1$ if there is an overall error.

This average is a correlation function in a statistical mechanical model with
quenched disorder. If we wanted to compute the product of the average instead
of the average of the product, this would be much easier as we would be
computing a product of correlation functions each involving a single degree of
freedom. This, indeed, is what happens in the graph $G_{\rm column}$: we just
need to compute whether or not there are an odd number of red edges from one
time to the next, and the probability that a given edge is red is independent
of the other edges.

However, we can expand this correlation function (the average of
$\prod_{e}Z_{e}$) as a sum of connected correlation functions. We expect that
connected correlation functions involving more degrees of freedom are
suppressed in powers of $p$. Hence, while the sum of connected correlation
functions is likely not to have a well-behaved power series, we believe that
the power series in $p$ for the _logarithm_ of the average of $\prod_{e}Z_{e}$
is a convergent expansion; the leading term of this series is the quantity
$-3p^{2}d$ found above.

Even once we have computed the average of $\prod_{e}Z_{e}$, this is not yet
sufficient, as the probability of having an overall error between times
$S,S+1$ is not independent of having overall errors at other times. However,
again we believe that the power series expansion of logarithms quantities such
as $\prod_{e}Z_{e}\prod_{e^{\prime}}Z_{e^{\prime}}$, where edges $e$ are from
times $S$ to $S+1$ and edges $e^{\prime}$ are from times $S^{\prime}$ to
$S^{\prime}+1$ is a convergent expansion.

More importantly, we believe that the correlations between the overall errors
at different times are negligible. To see this, let’s consider another
effective model. In this model, we consider a model of Ising spins, labelled
$1,\ldots,T$, each initialized to the state $+1$, then we flip each spin
independently with probability $1/2-\epsilon$ for some small $\epsilon$, and
then for each pair of neighboring spins we flip both spins in that pair with
probability $1/2-\epsilon^{\prime}$ for some small $\epsilon^{\prime}$,
independently of the other pairs. This is an effective model of the following
situation: the shortest paths (of length $3$) considered above can create an
overall error at some time. However, length $4$ paths can create an overall
error at two neighboring times at a higher order in $p$; we’ll ignore the
possibility of even further paths because they are further suppressed in $p$,
but the treatment is similar to the case here. The quantity $\epsilon$ is then
exponentially small in $p^{2}d$, while the quantity $\epsilon^{\prime}$ is
exponentially small in $p^{3}d$ and so $\epsilon\ll\epsilon^{\prime}$.
Consider any given configuration $s_{1},s_{2},\ldots,s_{T}$ of Ising spins. We
will compute the probability that this can arise in this effective model. This
can be computed with a transfer matrix technique. Let $b_{1},\ldots$ be binary
variables corresponding to the Ising spins with $b_{j}=(1-s_{j})/2$. Let
$f_{1},f_{2},\ldots$ be binary variables, such that if $f_{i}=1$, we flip
Ising spins $i,i+1$ in the above process.

Then, the probability of any given $b_{1},b_{2},\ldots$ is given by

$c^{-1}\sum_{\\{f_{i}\\}}\prod_{j}z^{b_{j}\oplus f_{j-1}\oplus
f_{j}}y^{f_{j}}$

, where $y=(1/2-\epsilon^{\prime})/(1/2+\epsilon^{\prime})$ and
$z=(1/2-\epsilon)/(1/2+\epsilon)$ and where the normalization factor
$c=(1/2+\epsilon)^{T}(1/2+\epsilon^{\prime})^{T-1}$. Introduce matrices

$M_{0}=\begin{pmatrix}1&z\sqrt{y}\\\ \sqrt{y}z&y\end{pmatrix},$

and

$M_{1}=\begin{pmatrix}z&\sqrt{y}\\\ \sqrt{y}&zy\end{pmatrix},$

so that the probability of given $b_{1},b_{2},\ldots$ is given by
$\langle\psi_{L}|M|\psi_{R}\rangle$, where

$M=M_{b_{2}}M_{b_{3}}M_{b_{4}}\ldots M_{b_{T-1}},$

and where the vectors $\psi_{L},\psi_{R}$ depend on the spins $s_{1},s_{T}$,
respectively. The exact form of the vectors $\psi_{L},\psi_{R}$ is not so
important, and we omit it (with periodic boundary conditions we replace this
with a trace). Then, it is convenient to change basis to compute the matrix
product. Introduce a new basis of vectors

$\frac{1}{\sqrt{1+y}}(1,\sqrt{y}),\quad\frac{1}{\sqrt{1+y}}(\sqrt{y},-1).$

This is a basis of eigenvectors of both $M_{0}$ and $M_{1}$ at $z=1$. In this
basis, we have

$M_{0}=\frac{1}{1+y}\begin{pmatrix}1+2zy+y^{2}&(1-y)(1-z)\sqrt{y}\\\
(1-y)(1-z)\sqrt{y}&1-2zy+y^{2}\end{pmatrix},$

and

$M_{1}=\frac{1}{1+y}\begin{pmatrix}z+2y+zy^{2}&-(1-y)(1-z)\sqrt{y}\\\
-(1-y)(1-z)\sqrt{y}&2(z-1)y\end{pmatrix}.$

Note that in this basis, for both matrices, the off diagonal terms are ${\cal
O}(\epsilon\epsilon^{\prime})$, and the term in the lower right is ${\cal
O}(\epsilon+\epsilon^{\prime 2})$ for $M_{0}$ and ${\cal O}(\epsilon)$ for
$M_{1}$. At the same time, the term in the upper left is off order unity.
Thus, so long as $T$ is small compared to
$\epsilon^{-2}\epsilon^{-2}(\epsilon+\epsilon^{\prime 2})^{-1}$, _we can
approximate the matrix product as the product of terms in the upper left
corner_ ; at the same time, we will see from the solution in this regime that
if $T$ is not small compared to this quantity, then the probability of a
decoding error is negligible. So, we approximate the probability as (putting
in the correct normalization)

$\frac{\Bigl{(}1+2zy+y^{2}\Bigr{)}^{n_{\uparrow}}\Bigl{(}z+2y+zy^{2}\Bigr{)}^{n_{\downarrow}}}{\Bigl{(}1+2zy+y^{2}+z+2y+2y^{2}\Bigr{)}^{T}},$

where $n_{\uparrow}$ and $n_{\downarrow}$ are the number of Ising spins in the
$+1$ and $-1$ states, respectively. One may recognize that this is the
probability corresponding to a process where we first flip each spin
independently with probability $z/(1+z)$, then flip each spin again
independently with probability $y/(1+y)$, and finally again flip each spin
independently with probability $y/(1+y)$. This of course is correct for any
given spin in the original effective model: each spin is subject to those
three possible spin flips, however the important thing is that we can ignore
any correlation between flips of neighboring spins.

Gluing Together— Next we have a general principle. We have discussed decoding
in various cases with dangling edge, either considering decoding near a hole
with dangling edges at some time, or considering Peierls arguments for some
path with dangling edges. Now suppose we have two such decoding problems.

######  Lemma 6.

Consider two separate decoding graphs $G_{1},G_{2}$, each with dangling edges.
Suppose the probability that an MC decoder makes an error on graph $G_{1}$ is
at most some probability $P_{1}$, and similarly the probability that it makes
on error on graph $G_{2}$ is at most some $P_{2}$. Consider the graph obtained
by attaching some dangling edge $e_{1}$ of $G_{1}$ to some other dangling edge
$e_{2}$ of $G_{2}$, and assume there are only two homology classes on $G_{1}$,
and on $G_{2}$, and on the combined graph, so that making any error on the
combined graph requires coloring $e_{1}$ and $e_{2}$ both once. . The
probability that it makes an error on that graph is at most $2P_{1}P_{2}$.

###### Proof.

Consider some fixed quenched disorder on each graph. Suppose for that given
quenched disorder, the MC decoder makes an error with probability $Q_{1}$ on
the first graph and probability $Q_{2}$ on the second graph. The MC decoding
is two separate decoding problems, constrained by the requirement that $e_{1}$
must be colored the same, mod $2$, as $e_{2}$. So, the probability of an error
on the combined graph is

$\frac{Q_{1}Q_{2}}{Q_{1}Q_{2}+(1-Q_{1})(1-Q_{2})}\leq 2Q_{1}Q_{2}.$

Further, we know that the average of $Q_{1}$ over quenched disorder is equal
to $P_{1}$ and the average of $Q_{2}$ is equals to $P_{2}$. So, the average of
$2Q_{1}Q_{2}$ equals $2P_{1}P_{2}$.

Remark: this worst case is achieved if there is a probability $2P_{1}$ that
the quenched disorder is such that $Q_{1}=1/2$ and similarly a probability
$2P_{2}$ that $Q_{2}=1/2$. ∎

Then, in our general picture at the start, we believe that we can use the
Peierls argument for paths between columns of high degree vertices, use the
effective model $C_{\rm column}$ above for high degree vertices with dangling
edges on the vertices where a Peierls path arrives at a vertex, and use this
lemma to glue the paths, to get the effective with weak edges connecting
different hole centers discussed at the start.

Two Nearby High Degree Vertices— Finally, suppose we have two nearby high
degree vertices in our effective model with one vertex per hole center and
edges between every pair of vertices. We can describe these two nearby high
degree vertices by a check graph with a “ladder” shape. The “rungs” of the
ladder are the spacelike edges between vertices. Suppose we have some error
probability $r$ on this edge, while we have error probabilities
$p_{1}=1/2-\epsilon_{1}$ and $p_{2}=1/2-\epsilon_{2}$ on timelike edges
attached to one or the other hole center.

If $r\ll\epsilon_{1}^{-1}$ or $r\ll\epsilon_{2}^{-1}$, then we can use a
Peierls argument on this effective ladder model. However, suppose
$r\gg\epsilon_{1}$ and $r\gg\epsilon_{2}$. Then, a Peierls argument does not
work. In this case, in the limit of large $r\epsilon_{1}^{-1}$ and large
$r\epsilon_{2}^{-1}$, we cannot effectively determine whether or not any of
the spacelike edges are colored red. Then, we arrive at an effective model
$C_{\rm column}$ with $d=2$ and with error probabilities
$p_{1}=1/2-\epsilon_{1}$ and $p_{2}=1/2-\epsilon_{2}$. Thus, this is the same
as a model $C_{\rm column}$ with $d=1$ and error probability

$\frac{1-\prod_{y=1}^{2}(1-2p_{y})}{2}=1/2-2\epsilon_{1}\epsilon_{2}.$

##  Appendix A Chain Maps

Many constructions in homological algebra have some relationship to some
construction in quantum error correcting codes. Most obviously, quantum codes
correspond to chain complexes over $\mathbb{F}_{2}$, and logical $X$ and $Z$
operators correspond to homology or cohomology classes.

Here we will discuss an interesting relationship between measurements on
quantum codes and chain maps.

Consider the case of a CSS quantum code $C$. We may define a corresponding
chain complex ${\cal C}$ with three degrees, which we label by $Z,X,Q$, with
$Z\rightarrow X\rightarrow Q$, and two boundary operators,
$\partial_{Z}:Z\rightarrow Q$ and $\partial_{Q}:Q\rightarrow X$. The different
degrees are each given some preferred basis and $Z$-stabilizer generators
correspond to basis elements of $Z$, qubits to basis elements of $Q$, and
$X$-stabilizer generators to basis elements of $X$, with the boundary operator
determined by the stabilizers of the quantum code. See Ref. Bravyi and
Hastings (2014) for a review and a dictionary between these languages.

Remark: this reverses the order we used previously, where we used
$Z$-stabilizers for $0$-cells and $X$-stabilizers for $2$-cells. It is chosen
for consistency with other literature.

While this mapping to stabilizers seems restricted to the case of CSS codes,
given any more general quantum stabilizer code on qubits, we may construct a
corresponding CSS code which is self-dual. See Ref. Bravyi et al. (2010) for
the general construction. Roughly, this is done by regarding such a more
general code as an instance of a code whose stabilizers are products of
Majorana operators, encoding each qubit into $4$ Majoranas; then, the
stabilizers of this Majorana code can be interpreted as defining both the
$X$\- and $Z$-stabilizers of some self-dual CSS code.

So, we will consider just this case of CSS codes.

Now, suppose we measure some operator $O$ which is a product of Pauli $X$ and
is not in the stabilizer group; the case of measuring a product of Pauli $X$
is similar. Suppose $O$ does not commute with one of the $Z$-stabilizers (so
$O$ is not a logical operator of the code). As a result, this measurement of
$O$ does not increase the rank of the stabilizer group: it increases the rank
of the group generated by $X$-stabilizers by one but it decreases the rank of
the group generated by $Z$-stabilizers by one. Of course, in the case of a
self-dual code derived as above, a measurement of an arbitrary operator would
map to a measurement of some product of Pauli $X$ and “the same” product of
Pauli $Z$; since these two measurements commute (necessarily it is an even
weight product) we could do them in an arbitrary order.

We identify this operator $O$ with some vector $w\in Q$. This vector is a sum
of basis elements corresponding to qubits in the product defining $O$. By
assumption, there is some $Z$-stabilizer which anticommutes with $O$; choose
an arbitrary such $Z$ stabilizer and identify that $Z$-stabilizer with some
vector $v\in Q$, that vector being a sum of basis elements in the product
defining the given $Z$-stabilizer. Then, the anticommutation can be expressed
as

$\langle v,w\rangle=1,$

where the angle brackets denote an inner product.

After this measurement, we have some new stabilizers of some new code
$C^{\prime}$ and some corresponding chain complex ${\cal C}^{\prime}$,
$Z^{\prime}\rightarrow X^{\prime}\rightarrow Q^{\prime}$, with boundary
operators $\partial^{\prime}_{Z^{\prime}}$ and
$\partial^{\prime}_{Q^{\prime}}$. Of course, $Q^{\prime}$ and $Q$ are of the
same dimension.

We will define a chain map $f$ from ${\cal C}$ to ${\cal C}^{\prime}$. A chain
map is a collection of maps, $f_{Z}:Z\rightarrow Z^{\prime}$,
$f_{Q}:Q\rightarrow Q^{\prime}$, and $f_{X}:X\rightarrow X^{\prime}$, such
that the chain map commutes with the boundary operators.

We define, for $q\in Q$, that

$f_{Q}(q)=q+\langle q,w\rangle v.$ (3)

This map is such that $f_{Q}(v)=0$, so it “kills” the corresponding $Z$
stabilizer.

To define $f_{Z}$, let us first define $Z^{\prime}$. In a basis independent
fashion, we define $Z^{\prime}$ to be the subspace of $Z$ containing vectors
$z$ such that $\langle\partial_{Z}z,w\rangle=0$. We may give it a basis by
picking a basis for $Z$ that corresponds to a choice of $Z$-stabilizer
generators where all generators commute with $O$, except for one generator
corresponding to vector $v$, and then a basis for $Z^{\prime}$ is chosen in
the obvious way: the $Z$-stabilizer generators of $C^{\prime}$ can be chosen
to be the $Z$-stabilizer generators of $C$ which commute with $O$.

The boundary operator $\partial^{\prime}_{Z^{\prime}}$ is defined in the
obvious way from the stabilizers of $C$. In the basis independent definition
of $Z^{\prime}$, the boundary operator $\partial^{\prime}_{Z^{\prime}}$ is the
boundary operator $\partial_{Z}$ on the given subspace.

In the first, basis independent method, we define

$f_{Z}(z)=z+\langle\partial_{Z}z,w\rangle\partial^{-1}v,$ (4)

where $\partial^{-1}v$ is any vector in the pre-image of $v$, chosen
arbitrarily (of course, we make this choice one time, and then use the same
choice for all $z$). Note that if there is no redundancy among the stabilizer
generators then $\partial^{-1}v$ is

In the second, basis dependent method, we define $f_{Z}$ in the obvious way:
each basis element of $Z$ corresponding to a generator which commutes with $O$
is mapped to the corresponding basis element of $Z^{\prime}$, while the basis
element which does not commute with $O$ is mapped to zero. One may verify that
Eq. 4 indeed defines this map on the basis elements of $Z$ if we choose
$\partial^{-1}v$ to be the basis element .

One may verify the chain map condition that

$\partial^{\prime}_{Z^{\prime}}f_{Z}(z)=f_{Q}(\partial_{Z}z).$ (5)

We may define $X^{\prime}$ to be the direct sum of $X$ with a $1$-dimensional
vector space, corresponding to the one additional $X$-stabilizer in
$C^{\prime}$. Thus, $X^{\prime}$ is defined by ordered pairs $(x,b)$ where
$x\in X$ and $b\in\\{0,1\\}$. We define $\partial^{\prime}_{Q^{\prime}}$ in
the obvious way:

$(\partial^{\prime}_{Q^{\prime}})^{T}(x,b)=(\partial_{X})^{T}x+bw,$

where the superscript $T$ denotes the adjoint, so

$\partial^{\prime}_{Q^{\prime}}q=(\partial_{Q}q,\langle q,w\rangle).$

Then define $f_{X}$ to be the obvious map from $X$ to $X^{\prime}$:

$f_{X}(x)=(x,0).$ (6)

We claim that we also have the chain map condition

$\partial^{\prime}_{Q^{\prime}}f_{Q}(q)=f_{X}(\partial_{Q}q).$ (7)

That is, we claim $\partial^{\prime}_{Q^{\prime}}q+\langle
q,w\rangle\partial^{\prime}_{Q^{\prime}}v=\langle(\partial_{Q}q),0\rangle$. We
have $\partial^{\prime}_{Q^{\prime}}v=(0,1)$ since, by assumption, $\langle
v,w\rangle=1$ and $\partial_{Q}v=0$ since ${\cal C}$ is a chain complex (i.e.,
$v$ corresponds to a $Z$-stabilizer), and then the claim follows from the
definition of $\partial^{\prime}_{Q^{\prime}}$.

##  Appendix B Toy Model of Vacancies Without Measuring Superstabilizers

We now consider a toy model of decoding in the presence of vacancies, but
_without_ measuring superstabilizers (i.e., without measuring logical
operators of the code created by the vacancies). In this case, anyons can move
onto the holes created by the defects without being detected, destroying the
error correction properties of the code. Logical information can be lost in
time ${\cal O}(1)$, independently of system size, even if all the holes are
size ${\cal O}(1)$, so long as many holes are present. We are interested in
how the logical error probability grows with time if we start from some state
with no anyons anywhere and then evolve for some time in the presence of noise
without measuring superstabilizers. We argue that the growth can be
superlinear with time in some cases.

While our main interest is in decoding quantum codes in two dimensions (e.g.,
surface codes, Floquet codes such as the honeycomb code, and so on), we
consider here a simpler toy model of decoding _classical_ information in a
one-dimensional Ising model with vacancies. To motivate this model, and argue
that its behavior should be analogous to that of quantum codes with defects in
two dimensions, note that in many stabilizer codes, the defects of the code
have certain integer spatial dimensions. For example, anyons in the two-
dimensional toric code are pointlike particles (dimension $=0$), while the
three-dimensional toric code has both pointlike (dimension $=0$) and looplike
(dimension $=1$) excitations. The classical Ising model in two-dimensions has
one-dimensional domain walls but the one-dimensional Ising model, like the
two-dimensional toric code, has pointlike excitations. Thus, the two-
dimensional toric code and the one-dimensional Ising model are in some way
similar as the defects in both are pointlike. Similarly, vacancies in a theory
could be pointlike (sites are randomly deleted from a system), linelike (lines
are randomly removed), and so on, so vacancies can also be $0,1,2,\ldots$
dimensional. The questions we consider here arise when the vacancy dimension
matches the defect dimension.

We consider the following model of a one-dimensional Ising model with
vacancies. We have $N$ spins, labeled $1,2,\ldots,N$. Each spin $i$
corresponds to some classical variable $Z_{i}=\pm 1$. We assume that the
system is initialized in some unknown state, either all spins $+1$ or all
spins $-1$, with equal probability for each choice. Then, the system proceeds
through $T$ rounds of errors. In each round, each spin is flipped
independently with some probability $p$. Then, checks $Z_{i}Z_{i+1}$ are
measured, for each $i\in\\{1,2,\ldots,N-1\\}\setminus V$, where $V$ is some
set of “vacancies”. That is, we measure checks on every neighboring pair of
spins, except for certain vacancies. Finally, after $T$ rounds, all spins are
measured perfectly (i.e., with no error), and we attempt to reconstruct the
initial state from those final spin measurements and from the check
measurements.

_Vacancies Everywhere—_ As a warmup, we begin with a simple case where
$V=\\{1,2,\ldots,N-1\\}$. That is, there are vacancies everywhere and no
checks are measured. After $T$ rounds of flips, each spin is flipped from its
initial state with probability

$P_{flip}=\frac{1-(1-2p)^{T}}{2}.$ (8)

We can regard this as defining some biased coin, which is tails with
probability $P_{flip}$ and heads with probability $1-P_{flip}$. Maximal
likelihood decoding in this case is simply majority decoding: we assume that
the initial state is where all spins had the value given by the majority after
$T$ rounds. Thus, decoding gives the correct answer if $N$ flips of this
biased coin have more than $N/2$ heads and fails if $N$ flips have more than
$N/2$ tails. If $N$ is even and there are exactly $N/2$ heads, then maximum
likelihood decoding returns that no decoding is possible: both initial states
are equally likely.

Taking the case of odd $N$ for simplicity, the probability of an error is then
equal to

$P_{err}=\sum_{j=\lfloor N/2\rfloor+1}^{N}{N\choose
j}P_{flip}^{j}(1-P_{flip})^{N-j}.$ (9)

For $P_{flip}\ll 1$, this is approximated by

$(P_{flip})^{\lfloor N/2\rfloor+1}{N\choose\lfloor
N/2\rfloor+1}\sim\frac{2^{N}}{\sqrt{N}}(P_{flip})^{\lfloor N/2\rfloor+1},$

and for $pT\ll 1$ we have $P_{flip}=pT-cO(T^{2})$ so the error probability
$P_{err}$ grows _superlinearly_ in $T$. Indeed, it grows as a power $\lfloor
N/2\rfloor+1$.

_Intervals: Generalities—_ We next consider the general case, of arbitrary
vacancy locations. We can describe this by saying that there are intervals of
lengths $\ell_{1},\ell_{2},\ldots,\ell_{k}$ for some $k$, i.e.
$N=\sum_{i=1}^{k}\ell_{i}$ and
$V=\\{\ell_{1},\ell_{1}+\ell_{2},\ell_{1}+\ell_{2}+\ell_{3},\ldots\\}$.
Consider a given interval of some length $\ell$. In a given round, the
probability of $m$ errors in that interval is

$P(m,\ell)=p^{m}(1-p)^{\ell-m}{\ell\choose m}.$

Because all checks are present in an interval, the decoder can determine that
either $m$ or $\ell-m$ errors occurred; indeed, it knows that either some
specific pattern of $m$ errors occurred or the “complementary” pattern of
$\ell-m$ errors occurred. The decoder can then correct the errors that
occurred, up to possibly an overall flip of all spins in the interval; if the
decoder chooses to correct the minimal number of errors (i.e., for $m<\ell/2$,
it assumes $m$ errors rather than $\ell-m$ occurred), then this can be
described by flipping a biased coin: with probability
$P(\ell-m,\ell)/(P(m,\ell)+P(\ell-m,\ell))$ the value of all spins in the
interval gets flipped.

Thus, we can describe this by the following effective model (and we emphasize
that a maximal likelihood decoding of this effective model will give a maximum
likelihood decoding of the original model, so that no meaningful information
is lost when going to the effective model). We describe the state of each
interval by a single _effective spin_ , $\pm 1$. We then draw some integer $m$
at random, $0\leq m\leq\ell/2$, from the following distribution. For
$m<\ell/2$, the probability of having that given $m$ is
$P(m,\ell)+P(\ell-m,\ell)$, while for $m=\ell/2$, which is possible if $\ell$
is even, the probability of having that given $m$ is $P(m,\ell)$. The decoder
knows the value of this $m$. Then, for $m<\ell/2$, we toss a biased coin and
flip the effective spin in that interval with probability
$P(\ell-m,\ell)/(P(m,\ell)+P(\ell-m,\ell))$. If $m=\ell/2$, we flip the
effective spin with probability $1/2$. We emphasize, there is only a single
effective spin for each interval.

Thus, in this effective model, each interval behaves independently over the
$T$ rounds. Each interval is subject to a sequence of biased coin tosses, with
the bias known to the decoder, flipping the effective spin in the interval if
the coin is tails.

Let $P_{flip}(i,t)$ denote the probability of flipping the effective spin in
the $i$-th interval on the $t$-th round. Remark: in the previous case where we
had vacancies everywhere, all $P_{flip}(i,t)$ are equal to each other (indeed,
they equal $p$), but now we allow them to vary from round to round and from
interval to interval. Thus, the effect of $T$ rounds of flips on a given
effective spin is that it is flipped, from its initial state at round $0$,
with probability

$P_{flip}(i)=\frac{1-\prod_{t=1}^{T}\Bigl{(}1-2P_{flip}(i,t)\Bigr{)}}{2}.$
(10)

This reduces to Eq. 8 if $P_{flip}(i,t)=p$ for all $i,t$. Again, these
probabilities $P_{flip}(i)$ are known to the decoder.

Finally, we apply maximum likelihood decoding after $T$ rounds. The decoder
can determine that either some given pattern of errors on the _effective_
spins occurred (i.e., some specific set of effective spins are flipped) or
that the complementary pattern of errors occured (i.e., that the complement of
that set of effective spins is flipped). Maximum likelihood decoding gives an
error if some pattern occurs but the complementary pattern is more likely. If
the complementary pattern is equally likely, then maximum likelihood decoding
knows that both initial states were equally likely.

_Two Intervals—_ The above analysis of intervals gives some general results
reducing to an effective model. However, this effective model still must be
analyzed: to determine asymptotics, we need to determine which sequences of
biased coin flips are most likely. We work now on the case of two intervals,
of lengths $\ell_{1},\ell_{2}$.

We assume without loss of generality that $\ell_{1}\leq\ell_{2}$.

There are two ways in which an error can occur. One way is when the effective
spin in both intervals is flipped after $T$ time steps. The second way is when
the effective spin in one interval is flipped while the other is not flipped,
but the decoder still makes an error as it determines that it is more likely
that the other effective spin flips. Remark: we say “is flipped” rather than
“flips” to emphasize that the important thing is whether there is a total of
an odd number of flips after $T$ rounds.

Let us consider the first way first. Eq. 10 gives the probablity of this
occuring for each choice of $P_{flip}(i,t)$. However, since Eq. 10 is linear
in each $P_{flip}(i,t)$, we can compute the probability that the effective
spin is flipped for random choice of $P_{flip}(i,t)$ by replacing
$P_{flip}(i,t)$ with its average. Thus, the probability that the effective
spin in an interval of length $\ell$ is flipped is given by

$\frac{1-(1-2P_{eff})^{T}}{2},$

where for odd $\ell$ we have

$P_{eff}=\sum_{0<=m<\ell/2}\Bigl{(}P(m,\ell)+P(\ell-m,\ell)\Bigr{)}\Bigl{(}\frac{P(\ell-m,\ell)}{(P(m,\ell)+P(\ell-m,\ell))}\Bigr{)}=\sum_{0<=m<\ell/2}P(\ell-m,\ell).$

From now on, we consider the limiting case $p\ll 1$, where this is dominated
by the contribution with $m=\lfloor\ell/2\rfloor$, so in this case

$P_{eff}\approx Cp^{\lfloor\ell/2\rfloor+1}2^{\ell}\ell^{-1/2},$

where the factor of $C2^{\ell}\ell^{-1/2}$ is an approximation to
${\ell\choose\lfloor\ell/2\rfloor}$ and $C=\sqrt{2}/\pi$ from Stirling’s
formula.

Let

$P_{eff}^{1}=Cp^{\lfloor\ell_{1}/2\rfloor+1}2^{\ell_{1}}\ell_{1}^{-1/2},$

and

$P_{2,eff}=Cp^{\lfloor\ell_{2}/2\rfloor+1}2^{\ell_{2}}\ell_{2}^{-1/2}.$

Since $\ell_{1}\leq\ell_{2}$, $P_{2,eff}\leq P_{1,eff}$. We will consider
three different asymptotic time regimes below: first, $TP_{1,eff}\ll 1$;
second, $TP_{2,eff}\ll 1\ll TP_{1,eff}$; and finally, $1\ll TP_{2,eff}$.

The probability that both effective spins are flipped is

$P_{both}\approx\Bigl{(}\frac{1-(1-2P_{1,eff})^{T}}{2}\Bigr{)}\Bigl{(}\frac{1-(1-2P_{2,eff})^{T}}{2}\Bigr{)}.$
(11)

Each term in the product in Eq. 11 asymptotes as $T\rightarrow\infty$ at $1/2$
so the product asymptotes at $1/4$. The first term displays a linear behavior
for $P_{1,eff}T\ll 1$, and is roughly constant for $P_{1,eff}T\gg 1$ and
similarly for the second term.