# An interpretation of Union-Find Decoder on Weighted Graphs

Yue Wu, Namitha Liyanage, and Lin Zhong
Department of Computer Science, Yale University, New Haven, CT

###### Abstract

Union-Find (UF) and Minimum-Weight Perfect Matching (MWPM) are popular decoder
designs for surface codes. The former has significantly lower time complexity
than the latter but is considered somewhat inferior, in terms of decoding
accuracy. In this work we present an interpretation of UF decoders that
explains why UF and MWPM decoders perform closely in some cases: the UF
decoder is an approximate implementation of the blossom algorithm used for
MWPM. This interpretation allows a generalization of UF decoders for weighted
decoding graphs and explains why UF decoders achieve high accuracy for certain
surface codes.

##  Introduction

Fast and accurate quantum error correction is necessary for fault-tolerant
quantum computing. Surface codes have emerged as one of the leading choices
for quantum error correction. A surface code interleaves data and ancilla
qubits on a surface such that an error in a data quit will impact the
measurement outcome of its neighboring ancillas. The decoder’s job is to
determine the error pattern, i.e., which data qubits experience errors, based
on the syndrome, i.e., measurement outcomes of all ancillas.

Union-find (UF) [1] and Minimum-Weight Perfect Matching (MWPM) are two popular
decoder designs. Both leverage graph representations of surface code and its
syndromes. A UF decoder works on the model graph where vertices correspond to
measurement qubits and edges correspond to data qubits with weights determined
by the error probability. An MWPM decoder works on the syndrome graph, a
fully-connected graph generated from the model graph in which vertices
correspond to nontrivial measurement outcomes and an edge corresponds to
minimum-weight paths in the model graph. As its name suggests, an MWPM decoder
finds a minimum-weight perfect matching of the syndrome graph and uses it as
its guess for the error pattern. Union-Find is known to be much faster than
MWPM decoders but in general, achieves lower decoding accuracy.

The primary contribution of this work is to reveal a hidden link between UF
and MWPM decoders. By adapting UF decoders to work on the syndrome graph, we
show that its working principles approximate those of the blossom algorithm, a
highly optimized algorithm that finds an MWPM. Both UF and Blossom algorithm
decompose a syndrome graph into non-overlapping subgraphs. Both start with the
syndrome graph with each subgraph including a single vertex and grow these
subgraphs such that each can be “solved” on its own. While the blossom
algorithm finds an MWPM for each subgraph, a UF decoder finds a logical
equivalent to a PM for it. We show that under many circumstances, a UF decoder
and the blossom algorithm may end up decomposing the syndrome graph in the
same way and their solutions for subgraphs may be logically equivalent.

Once revealed, the link between UF and MWPM decoders not only allows us to
improve the accuracy of UF decoders and generalize them for weighted decoding
graphs but also explain why UF decoders achieve similar accuracy as MWPM
decoders for certain surface codes, such as the XZZX surface code [2] when
noise is infinitely biased and measurements are perfect. Specifically, we
devise a more general UF decoder that works for surface codes without assuming
identical error probability for data qubits.

We presented the interpretation and its implications at [3]. Since then we
have learned that others had reached similar interpretations independently
[4]. At the same time, we have also learned that many are still unaware of the
link between the UF and blossom algorithms. Therefore, our motivations in
writing this article are two. First, to share the interpretation with the
community in hope to foster the development of fast quantum error decoders.
Second, to formalize the interpretation as rigorous as we could.

In the rest of the paper, we provide necessary background in §2; we describe
how a UF decoder approximates the blossom algorithm in §4. Using this
interpretation, we explain why a UF decoder behaves the same as an MWPM
decoder for two examples in §5. We derive weighted union-find decoders based
on the interpretation in §6. We have open-sourced their implementations at
[5]. Mathematical details of proofs can be found in the Appendix.

##  Background

###  Surface code

A surface code is a lattice of interleaved ancilla and data qubits arranged on
a surface in which each ancilla qubit entangles with neighboring data qubits.
In this work, we focus on surface codes with open boundaries. That is, the
surface is a bounded plane. Measuring an ancilla qubit is equivalent of
performing a _stabilizer_ operation on its entangled data qubits. We assume
the stabilizer measurements are noiseless for simplicity, and will generalize
to noisy stabilizer measurements in §3.3. Figure 1 shows an instance of the
popular CSS surface code. The stabilizer is either $\otimes^{4}X$ (X-type
ancilla) or $\otimes^{4}Z$ (Z-type ancilla) on adjacent data qubits as shown
in 1(b) and 1(c), respectively. An X (or Z) error in a data qubit will flip
the measurement outcomes between +1 and −1 of its Z-type (or X-type) ancillas.

A qubit, logical or physical, can be represented by a vector in a
2-dimensional Hilbert space. The array of $N$ data qubits is therefore
represented by a vector in a $2^{N}$-dimensional Hilbert space. An error-
correction code identifies a subspace of this huge space, called _code space_.
Each state in the code space corresponds to a state in the 2-dimensional
Hilbert space, i.e., a _logical_ state. That is, a code space state encodes a
_logical_ qubit. In an error-free world, as the array functions as a logical
qubit, it will remain in the code space. An error in a data qubit will bring
the array outside the code space.

Because direct measurement is destructive, QEC relies on the measurement
outcomes of ancilla qubits, i.e., the _syndrome_ , to detect errors and then
correct them, to bring the array back the code space, hopefully to the same
_logical_ state. If the array ends up in a different logical state, a logical
error happens.

Both an error pattern, denoted by $\mathcal{E}$, and a correction, $C$, can be
considered as an operator $\hat{\mathcal{E}}$ and $\hat{\mathcal{C}}$ that
changes the states of the corresponding data qubits. Any error pattern or
multi-qubit operator can be written as a linear combination of Pauli errors
(operators). Hence, we only look at decoding a tensor product of identity
operators $\hat{I}$ or Pauli operators ($\hat{X}$, $\hat{Y}$, and $\hat{Z}$),
which directly leads to $\hat{\mathcal{E}}\hat{\mathcal{E}}=\hat{I}$. That is,
$C=\mathcal{E}$ corrects the error pattern $\mathcal{E}$. However, there are
usually more than one correction $C$ that could avoid the logical state change
under $\mathcal{E}$. We denote the set of such corrections as
$\mathbf{C}_{\mathcal{E}}$.

Error correction is challenging because different error patterns may have the
same syndrome. Two classes of error patterns have no syndrome at all, which
means they are not detectable and can be considered as the _logical operators_
of the surface code. In the first class, errors of the same type (X or Z) form
a closed circle. Such a pattern (and its corresponding operator) does not
affect the logical state of the surface code. That is, it is a trivial logical
operator, i.e., identity. Apparently, any $C\in\mathbf{C}_{\mathcal{E}}$,
$\hat{C}\hat{\mathcal{E}}$ must be a trivial logical operator. In the second
class, errors of the same type (X or Z) form a continuous chain connecting the
respective boundaries, as shown 2(f). Such a pattern (and its corresponding
operator) changes the logical state of the surface code. That is, it is a
nontrivial logical operator (X or Z) of the surface code. We note these
classes exist for general surface codes but involve more nuanced topology of
the surface and error patterns [6].

(a)

(b)

(c)

Figure 1: (a) : distance-3 CSS surface code. The data qubits are shown in
white circles and the Z-type and X-type ancillas are shown in black circles.
(b) and (c) : Measurement circuit of Z-type and X-type ancillas. Excluding the
ancillas in the border, each Z-type and X-type ancilla interacts with 4
adjacent data qubits. Z-type and X-type ancillas have different gate orders to
prevent certain type of hook error [7, 8].

(a)

(b)

(c)

(d)

(e)

(f)

Figure 2: Visualization of multiple error patterns on d = 3 surface code. The
physical qubit errors are marked by X and Z. Ancillas reporting nontrivial
measurements are shown in red. The red lines are to visualize error chains.
(a) isolated X error (b) isolated Z error (c) isolated Y error (d) X error
generating single nontrivial measurement (e) error chain of three X errors (f)
error chain introducing a logical error. Note that even though (a) and (e) are
different error patterns, they produce the same syndrome.

###  Decoding and its challenges

Generally speaking, a decoder starts with the syndrome, denoted by $S$, and
the error model, denoted by the probability distribution of error patterns
$P(\mathcal{E})$, and computes a correction, denoted by $C$, which is an
operator on the surface code. The error model $P(\mathcal{E})$ is determined
by the code and the hardware; it can be acquired offline. In contrast, the
syndrome $S$ is measured at runtime.

Given the syndrome $S$, we can compute the probability of not having a logical
error if correction $C$ is applied as

$P(C,S)=\sum\limits_{\mathcal{E}|C\in{\mathbf{C}_{\mathcal{E}}}}P(\mathcal{E}|S)$
(1)

Both $P(\mathcal{E}|S)$ and $\mathbf{C}_{\mathcal{E}}$ can be computed
offline.

Then we can compute the best correction $C(S)$, in terms of lowest probability
of logical error as

$\displaystyle C(S)=\arg\max\limits_{C}P(C,S)$ (2)
$\displaystyle=\arg\max\limits_{C}\sum\limits_{\mathcal{E}|C\in{\mathbf{C}_{\mathcal{E}}}}P(\mathcal{E}|S)$

Note that the optimal correction $C(S)$ is generally not unique, and we denote
the set of the best corrections for $S$ with $\mathbf{C}(S)$.

Challenges The above process, however, faces scaling challenges in both
storage and computation. (i) First, there are about $4^{2d^{2}}$ different
error patterns given about $2d^{2}$ data qubits each can have no error
(identity $I$) or a Pauli $X$, $Z$ or $Y$ error. As a result, a complete error
model $P(\mathcal{E})$ requires $4^{2d^{2}}$ entries. (ii) Second, given $S$
and $P(\mathcal{E})$, the computational complexity for $\mathbf{C}(S)$ is
$O(d^{2}(4^{2d^{2}})^{2})$ using Equation 2.

Lookup table decoder tackles Challenge (ii) above by pre-computing an optimal
$C(S)$ for every possible syndrome $S$ offline, storing them in a table, and
looking it up at runtime, with constant decoding time. It does not address
Challenge (i), which makes the offline computation non-scalable. Moreover, the
table has one entry per syndrome and there are about $2^{2d^{2}}$ possible
syndromes. Even for $d=5$, the table will have over a quadrillion ($10^{15}$)
entries.

##  Graph Based Decoding

In contrast, graph-based decoding tackles both challenges, in two stages. The
first stage constructs a graph that approximates the _error model_
$P(\mathcal{E})$. The second stage then uses this graph and the syndrome to
compute a correction. Both stages can employ heuristics to simplify the
computation, finding a “good” correction within polynomial time. Because the
error model is usually known given the hardware and code, i.e., offline, and
the syndrome is only observed at runtime, i.e., online, only the second stage
needs to be computed at runtime.

###  Graph Construction

The first stage constructs a weighted graph that represents an approximation
of the error model $P(\mathcal{E})$, which we call the model graph. We first
describe how to construct the model graph assuming that errors happen
independently and only with data qubits. We will discuss how the graph can be
extended to consider other types of errors in §3.3. Under the independence
assumption, one can reduce $P(\mathcal{E})$ into

$\begin{split}P(\mathcal{E})&=\prod_{\mathcal{E}_{i}\in\mathcal{E}}P(\mathcal{E}_{i})\prod_{\mathcal{E}_{i}\notin\mathcal{E}}\left(1-P(\mathcal{E}_{i})\right)\\\
&=\prod_{\mathcal{E}_{i}\in\mathcal{E}}\frac{P(\mathcal{E}_{i})}{1-P(\mathcal{E}_{i})}\prod_{\mathcal{E}_{i}}\left(1-P(\mathcal{E}_{i})\right)\\\
&\propto\prod_{\mathcal{E}_{i}\in\mathcal{E}}\frac{P(\mathcal{E}_{i})}{1-P(\mathcal{E}_{i})}\end{split}$
(3)

where $\mathcal{E}_{i}$ indicates the $i$th independent error. If the
independence assumption is true for single data qubit Pauli X and Z errors,
one can construct two separate graphs to represent the X and Z error models.

A vertex in the model graph represents an ancilla in the code. An edge between
two vertices represents an independent error (e.g., X or Z error) of the
corresponding data qubit that could result in nontrivial measurements of the
corresponding ancillas. For example, 3(b) shows those edges in the model
graphs for X and Z errors of CSS surface code.

An error on a data qubit at the border of the code may result in nontrivial
measurement of a single ancilla, such as 2(d). One can add a virtual _boundary
vertex_ and use the edge connecting it with the ancilla vertex to represent
this error. We call the boundary vertices on the left and right the X boundary
vertices because they deal with X errors; similarly, we call the top and
bottom boundary vertices the Z boundary vertices. 3(c) visualizes these edges
that connect one real vertex and one virtual boundary vertex. The final model
graph for the surface code of 3(a) is shown in 3(d).

The weight of an edge in a model graph represents the probability of the
corresponding independent error, i.e.,
$w_{i}=-\log\frac{P(\mathcal{E}_{i})}{1-P(\mathcal{E}_{i})}$. A set of edges
corresponds to a set of independent errors; the probability of this set of
errors is determined by the sum of the corresponding weights, per the
independence assumption (Equation 3).

(a)

(b)

(c)

(d)

Figure 3: The process of generating a model graph for the graph for d = 3 CSS
surface code. (a) The surface code patch with ancilla qubits numbered. (b) A
graph showing all independent X and Z errors having two nontrivial
measurements (c) A graph showing all independent X and Z errors having single
nontrivial measurement (d) The model graph showing all independent X and Z
errors. The dotted circles in (c) and (d) are virtual boundary vertices. In
(b) (c) and (d), X and Z errors are shown blue and yellow respectively.

##### Decoding Graph

Once a measurement is performed on the surface code, some of the ancillas may
report nontrivial measurement. The set of the corresponding vertices in the
model graph is called the _syndrome_. The model graph and the syndrome are the
basis of error decoding. Marking the vertices from the syndrome in the model
graph, one derives the _decoding graph_ , which is the basis of error
decoding. 4(a) shows the decoding graph for the model graph from 3(d).

##### Syndrome Graph

Given the syndrome $S$, we can construct the syndrome graph $G(V,E)$ as shown
in 4(b). $V$ is the set of nontrivial measurement vertices from the model
graph. $e\in E$ represents the set of the minimum-weight paths between two
nontrivial measurement vertices in the model graph. Because each path in the
model graph corresponds to an error pattern, $e$ also defines a set
$\mathbf{e}$ of error patterns each corresponding to a minimum-weight path.

In a syndrome graph, we say two vertices are adjacent to each other if the
edge connecting them has a small weight. Otherwise, we say they are far from
each other.

A subgraph of the syndrome graph is defined by a subset of $E$, $E^{\prime}$.
It defines a set of error patterns $\mathbf{E^{\prime}}$ according to
$\mathbf{E}^{\prime}=\\{\mathcal{E}|\mathcal{E}=\sum_{e\in
E^{\prime}}\mathcal{E}_{e},\forall\mathcal{E}_{e}\in\mathbf{e}\\}$.

##### Logical Equivalence

Given two subgraphs of the syndrome graph defined by $E_{1}$, $E_{2}\subseteq
E$, respectively, we say they are logically equivalent if
$\forall\mathcal{E}_{1}\in\mathbf{E}_{1}$ and
$\forall\mathcal{E}_{2}\in\mathbf{E}_{2}$,
$\mathcal{E}_{1}+\mathcal{E}_{2}$111Here $+$ is the symmetric difference,
defined in Appendix A. is a trivial logical operator.

Table 1: Mathematical symbols Symbol | Meaning
---|---
$e$ | edge
$E$ | set of edges
$\mathcal{E}$ | an error pattern
$\hat{\mathcal{E}}$ | the operator form of $\mathcal{E}$
$\mathbf{E}$ | set of error patterns

###  Perfect Matching

(a)

(b)

Figure 4:  Example decoding (a) and syndrome (b) graphs for the model graph in
3(d). The decoding graph is the model graph with with nontrivial measurement
vertices marked (red). The syndrome graph is constructed by computing the
minimum-weight paths between nontrivial measurement vertices from the model
graph and removing trivial ones.

Given the syndrome $S$, the second stage seeks to identify the error pattern
that caused it. That is, it solves the following problem, often approximately.

$\mathcal{E}(S)=\arg\max\limits_{\mathcal{E}}P(\mathcal{E}|S)$ (4)

Once $\mathcal{E}(S)$ is identified, a correction $C^{\prime}$ can be applied,
to avoid a logical error, i.e., $C^{\prime}(S)\in\mathbf{C}_{\mathcal{E}(S)}$,
or to perfectly cancel $\mathcal{E}(S)$, i.e.,
$\hat{C}^{\prime}=\hat{\mathcal{E}}(S)^{\dagger}$.

Graph-based decoding solves Equation 4 by finding a _perfect matching_ in the
syndrome graph. A perfect matching is a subgraph in which all vertices of the
syndrome graph are incident to one and only one edge. It presents the set of
error patterns $\mathbf{E}$ such that $\mathcal{E}\in\mathbf{E}$ produces the
syndrome. $P(\mathcal{E}|S)$ for $\mathcal{E}\in\mathbf{E}$ is determined by
the sum of the weights of edges in the perfect matching. The larger the sum,
the lower $P(\mathcal{E}|S)$. Therefore, a most likely error pattern given the
syndrome, i.e., maximizing $P(\mathcal{E}|S)$, corresponds to a minimum weight
perfect matching of the syndrome graph.

Some useful properties of perfect matchings of a syndrome graph can be found
in §A.4.

Comparing Equation 4 with Equation 2, one can see that graph-based decoding is
missing the summation $\sum$. That is, it selects the most likely error and
intends to correct it, while the optimal decoder should select the correction
that will most likely correct the error. As a result, graph-based decoding is
sub-optimal in terms of logical error rate.

We note that virtual boundary vertices are treated specially when finding a
perfect matching in the syndrome graph: they do not have to be matched.

We care about two classes of graph-based decoders that differ in how they find
a perfect matching given a syndrome graph.

  * •

A Minimum Weight Perfect Matching (MWPM) decoder finds a minimum-weight
perfect matching for the syndrome graph. The best implementation of the MWPM
decoder has a worst-case time complexity of $O(d^{5})$ [9, 10, 11], not
scalable for large surface codes.

  * •

A Union-Find (UF) decoder [1] does not find a minimum-weight perfect matching.
It does not even find a perfect matching. Rather, it finds a subgraph that is
logically equivalent to a perfect matching of low weight. Because of this, UF
decoders can be much faster and more scalable than MWPM decoders. Notably, the
original UF decoder uses the decoding graph with $O(d^{2})$ worst-case time
complexity, instead of the syndrome graph (See Appendix B).

We will explain how these two classes are related further in §4.

###  More Error Types

We now extend the graph-based decoding described above to deal with
measurement errors and to approximate indirect errors, such as Pauli Y error.

Figure 5: Decoding graph along with an error pattern on d = 3 surface code
with 3 rounds of measurements. This includes measurement errors and X or Z
errors in ancillas propagating to data qubits. Measurement errors as well as
errors propagating from ancilla to data qubits are represented by edges
connecting adjacent layers (rounds). The error pattern shown has an isolated X
error, isolated Z error, isolated measurement error (shown by M), an isolated
X error in an ancilla propagated to data qubits (shown as a diagonal X edge )
and an error chain of X error and a measurement error. Error chains spanning
multiple rounds make decoding even more complicated.

Measurement errors: Since ancilla qubits are error prone and the quantum gates
to implement the stabilizer measurements are noisy, multiple rounds of ancilla
measurements are required to perform decoding in a fault-tolerant manner.
Thus, the syndrome can be represented by a sparsely populated 3D tensor, where
first layer indicate the ancilla values from the first round of measurement
and subsequent layers indicate the difference of ancilla values in each round
of measurement compared to the previous round of measurements. The difference
of ancilla values are chosen to ensure nontrivial measurements corresponding
to each error is indicated only once in the 3D tensor. Due to measurement
errors, error chains can spread over multiple measurement rounds, thus
increasing the space of total possible error patterns for a given syndrome as
shown in Figure 5. This further complicates the decoding process, resulting in
$2^{2d^{3}}$ different possible syndromes given $d$ noisy measurement rounds
compared to $2^{2d^{2}}$ without these errors.

Indirect errors are errors that each impact more than two ancillas but can be
approximated by multiple independent errors. For example, Paul Y error in 2(c)
can be decomposed as Pauli X error and Pauli Z error in 2(a) and 2(b), and
thus can be decoded using the existing graph. This decomposition implies that
the probability of an indirect error is the product probabilities of its
decomposed parts, which leads to inaccurate decoding results. In the example
above, if we assume the depolarizing error model where $P(X)=P(Y)=P(Z)=p$, the
assigned probability $P^{\prime}(Y)=P(X)P(Z)=p^{2}$ can be substantially
smaller than the actual $P(Y)=p$ for small $p$. As a result, graph-based
decoding can only approximately solve the most likely error pattern in the
existence of indirect errors.

##  Interpretation of UF Decoder

We next reveal the relationship between a union-find decoder [12] and the
famous blossom algorithm [13, 14] that solves MWPM problems.

We will first introduce some necessary concepts in the blossom algorithm in
§4.1 and then show how it solves the surface code decoding problem in §4.2. In
§4.3, we demonstrate that union-find decoders are close relatives of MWPM
decoders. Inspired by this, we describe a novel, general weighted union-find
decoder in §6.

###  Blossom Algorithm

The blossom algorithm uses linear programming (LP) to solve the MWPM problem
[13, 14] for a graph defined by $G(V,E)$ where $V$ is the set of vertices with
even cardinality, and $E$ that of edges. A matching $M$ of $G$ is a subset of
$E$ in which no edges share a vertex. A perfect matching $M_{p}$ is a matching
whose elements cover all vertices of $G$. $\mathcal{O}$ is the set of subsets
of $V$ with odd cardinaility, i.e. $\mathcal{O}=\\{S|S\subset
V;|S|\mathrm{\leavevmode\nobreak\ is\leavevmode\nobreak\ odd.}\\}$. For
$e=(u,v)\in E$, if $u\in S$ and $v\notin S$, we say $S$ and $e$ are incident
to each other.

In the primal problem of the linear programming formulation, a primal variable
$x_{e}$ corresponds to $e\in E$. For each $S\in\mathcal{O}$, there is a primal
constraint. If $|S|=1$, exactly one edge incident to $S$ is in the solution.
If $|S|>1$, at least one edge incident to $S$ is in the solution. While
$x_{e}$ is non-negative real, the primal constraints ensure that in one
optimal solution, $x_{e}$ is either $1$ or $0$ $\forall e\in E$, representing
a _perfect matching_ : $x_{e}=1$ if $e$ is in the solution. The primal
objective function $\sum_{e}w_{e}x_{e}$ is the total weight of the edges in
the solution, to be minimized.

In the dual of the above problem [15, p. 81], a dual variable $y_{S}$ is
defined for $S\in\mathcal{O}$, corresponding to a primal constraint. Each dual
constraint corresponds to an edge $e\in E$ (and its primal variable $w_{e}$):
$\sum_{S\in\delta(e)}y_{S}\leq w_{e}$ where $\delta(e)$ =
$\\{S|S\in\mathcal{O};S\mathrm{\leavevmode\nobreak\
incident\leavevmode\nobreak\ to\leavevmode\nobreak\ }e\\}$. The dual objective
is to maximize $\sum_{S\in\mathcal{O}}y_{S}$.

The blossom algorithm leverages two insights, both based on the complementary
slackness relationship between the primal and dual problems [15, p. 204].
First, if $x_{e}>0$, i.e., $e$ is selected in the matching solution, the
corresponding dual constraint must be _tight_ , i.e.,
$\sum_{S\in\delta(e)}y_{S}=w_{e}$. That is, the solution to the primal problem
can only consist of _tight_ edges. Second, if $y_{S}>0$ for $S\in\mathcal{O}$
and $|S|>1$, the corresponding primal constraint must be tight: exactly one
edge incident to $S$ is in the solution.

The second insight allows the algorithm to treat $S\in\mathcal{O}$ and $|S|>1$
like a vertex when $y_{S}>0$. Such $S$ are the eponymous _blossoms_.
Therefore, we use “vertex” to refer to both ordinary vertex and blossom below.

The first insight allows the algorithm to work on the primal and dual problems
in an interleaving manner. When it works on the primal problem, it only
considers the tight edges as candidates for the matching solution. It
identifies blossoms, odd number ($>1$) of “vertices” connected by tight edges
in a circle, and alternating trees, odd number of “vertices” connected by
tight edges in a tree where all leaves and nodes with multiple children are
connected to the root through an even number of tight edges. When it works on
the dual problem, it adjusts $y_{S}$ to grow the dual objective function $\sum
y_{S}$ while maintaining the tightness of edges in a blossom or alternating
tree. In doing so, it turns a dual constraint tight, that is
$\sum_{S\in\delta(e)}y_{S}=w_{e}$, resulting in a new tight edge $e$. With
this new tight edge, the algorithm switches to work on the primal problem.

###  Blossom for Decoding Surface Code

When applying the blossom algorithm to a graph, we can imagine two vertices
are separated by a distance of $w_{e}$, the weight of the edge incident to
them. We can imagine that a region covers a “vertex” $v$; for each edge
incident to $v$, the region covers it by $y_{v}$, which is the dual variable.
The dual constraints dictate that the regions would never overlap. When two
regions $u$ and $v$ meet on an edge $e=(u,v)$, $e$ becomes tight, i.e.,
$w_{e}=y_{u}+y_{v}$. We could also imagine a cluster, called _dual cluster_ ,
started with a single region. When two regions each from a different dual
cluster touch, the two dual clusters merge. Like regions, dual clusters do not
overlap (i.e., share any vertices). A dual cluster includes multiple regions
that touch each other in one way or another. Because each region $v$
corresponds to a non-zero dual variable $y_{v}$, we call the sum of the dual
variables of the regions $\sum y_{v}$ within a dual cluster the size of the
dual cluster. We say a dual cluster is even/odd if it contains an even/odd
number of regions. If a dual cluster covers virtual vertices from both left
and right, we say it is _attached_ ; otherwise, it is _detached_. For example,
in 7(3) there are three dual clusters, namely $\\{A,B,C\\}$, $\\{D\\}$, and
$\\{E\\}$, all detached.

When the model graph is unweighted, this imagination can be conveniently
visualized by the _Fowler diagram_ [16]. In this diagram, the Manhattan
distance between two vertices is the weight of the corresponding edge, i.e.,
$w_{e}$, as illustrated by Figure 7. We note that the model graph of a surface
code is unweighted if the data qubits have i.i.d. (independent and identically
distributed) Pauli-X errors.

This imagination allows us to explain how the blossom algorithm works
visually. Notably the algorithm actively operates on the internal of dual
cluster. When it works on the dual problem, it adjusts regions to increase the
size of each dual cluster. For example, 7(5) to 7(6). Increasing the dual
clusters may create a new tight edge and result in two dual clusters merging
into a “larger” one, in terms of the size and the number of vertices covered.
During the adjustment, the algorithm tries to keep tight edges within blossoms
and alternating trees tight.

When the algorithm works on the primal problem, it only considers the tight
edges. It will try to find a perfect matching inside each dual cluster using
only tight edges. When successful, it will mark that dual cluster as _solved_
and will not work on it (and its regions) unless the dual cluster merges with
another. The algorithm may identify a blossom within a dual cluster: an odd
number of tight edges forming a circle, e.g., 7(3). The algorithm then
switches to work on the dual problem again by treating the blossom as a vertex
and adjusting its own dual variable, e.g., $y_{\\{A,B,C\\}}$ in 7(3) to 7(6),
along with other dual variables. The process repeats until all dual clusters
are solved.

By definition, a tight edge must be inside a dual cluster because a tight edge
corresponds to two touching regions. As a result, a matching solution to the
primal problem must only include edges _inside_ dual clusters.

###  Union-Find Decoder

We next show that a union-find (UF) decoder works on the syndrome graph to
draw direct comparison with the blossom algorithm, using a similar
visualization as used above. It is an adaptation from the original UF decoder
[12] that is based on the decoding graph. (See Appendix B)

Unlike the blossom algorithm, which maintains the internal structure, i.e.,
regions, for each dual cluster, UF decoders only care about the number of
vertices inside each cluster, i.e., whether a cluster is even or odd, and it
only grows odd clusters. In each step of growth, a UF decoder grows all odd
clusters by the same amount: it makes sure the clusters do not overlap after
growth. When two clusters touch, they get merged. It stops growing a cluster
when the cluster covers a virtual boundary vertex or becomes even. When no
growth is possible, a UF decoder finds a subgraph as the solution for each
cluster using only fully-grown edges. This solution is logically equivalent to
a perfect matching for the cluster that may use not-fully-grown edges. Taken
together, the solutions for all clusters form the solution for the syndrome
graph, which is logically equivalent to a perfect matching. Figure 8
illustrates this procedure with the same Fowler diagram from Figure 7.
Different UF decoders may find different solutions within a cluster and as a
result, may produce different solutions for the syndrome graph.

A UF decoder grows an odd cluster in the same way as the blossom algorithm
grows a dual cluster with a single “vertex”. It stops updating the even
clusters while the blossom algorithm stops updating the solved dual clusters
for which a perfect matching with tight edges is found internally. Notably
only a dual cluster with an even number of “vertices” can be solved.

###  Relationship between Blossom and UF

At a high level, the blossom algorithm-based MWPM decoder and a UF decoder
appear to be similar in that both decomposes the syndrome graph into non-
overlapping subgraphs, i.e., clusters; both find the solution to the syndrome
graph by aggregating the solutions of the subgraphs. Yet there are two key
differences, which are behind the MWPM decoder’s superiority in decoding
accuracy and poor scalability. First, the MWPM decoder has a more
sophisticated way to decompose the syndrome graph, or grow its dual clusters.
Second, it finds a minimum-weight perfect matching within a subgraph (dual
cluster) while the UF decoder is satisfied with finding a logical equivalent
of a perfect matching. Intuitively, we have:

Observation (UF/Blossom Similarity): given a syndrome graph, a UF decoder
approximates the blossom-based MWPM decoder in accuracy, if the following two
conditions are true.

  * •

Condition 1: They decompose the syndrome graph in a similar way. In the
extreme case, there is a bijective mapping between their clusters such that
the mapped clusters cover the same subset of vertices.

  * •

Condition 2: Whether a perfect matching inside a cluster is minimum-weight
does not matter.

We next examine situations when these two conditions may be true or close to
be true.

####  4.4.1 Syndrome graph decomposed

We first examine how they decompose the syndrome graph. While there are an
enormous number of ways to decompose the graph, a number of factors constrain
both the UF decoder and blossom algorithm so that they may end up decomposing
the graph in a similar way.

First of all, they have the same starting point: the same syndrome graph and
the same set of clusters, each with a single vertex.

Second, when they terminate, their clusters must satisfy the following
requirements: they must not overlap; each of them must have an even number of
vertices because only even clusters can be solved; and a vertex is likely (but
not always) to be in the same cluster as its nearest neighbor. The last is
true because both grow all clusters by the same amount in each step of growth
and merge clusters when they meet, forming literally clusters of vertices.

Third, syndrome graphs that get decomposed into small (and therefore similar)
clusters by both the UF decoder and blossom algorithm are more likely. This is
due to the assumption that data qubit errors happen randomly and
independently. As a result, nontrivial measurement outcomes are more likely to
be randomly scattered in the model graph in pairs, resulting in a syndrome
graph in which these pairs are much farther from each other than the two
vertices within a pair. Such syndrome graphs are likely to get decomposed by
both the UF decoder and blossom algorithm into small clusters each covering a
pair or two.

Condition 1 also provides insight into why some revisions of UF decoders
improve their accuracy [12, 17]: these revisions allow a UF decoder to
decompose a syndrome graph in a way closer to that the blossom algorithm would
do.

Cluster vs. subgraph: Given a syndrome graph, clusters (and dual clusters) are
defined by the vertices they cover while a subgraph is defined by the edges it
includes. Given a cluster, one can uniquely construct a subgraph, using the
edges connecting any pair of vertices covered by the cluster. Likewise, given
a subgraph, one can uniquely construct a cluster, using the vertices
incidental to edges from the subgraph. Therefore, we use cluster and subgraph
in an inter-exchangeable manner below, unless otherwise indicated. For
example, when we say a perfect matching for a cluster or inside a cluster, we
are talking about the perfect matching for its corresponding subgraph.
Interesting, if two clusters do not overlap, i.e., not sharing any vertex,
their subgraphs do not overlap either, i.e., not sharing any edge.

####  4.4.2 Equivalent matchings

Assume the syndrome graph has been decomposed into non-overlapping clusters
each with an even number of vertices. Two perfect matchings $P_{1}$ and
$P_{2}$ for the syndrome graph are found by finding perfect matchings inside
each cluster.

We know that a logical error happens when a chain of error connects left and
right virtual vertices [18], forming a nontrivial logical operator. Since a
detached cluster cannot have such a chain in itself by definition, a subgraph
of the cluster cannot represent a nontrivial logical operator. Therefore, we
have the following Lemma and Theorem. See Appendix A for their proofs.

Lemma (Equivalent Matchings) if a cluster is detached, its perfect matchings
are logically equivalent.

Theorem (Equivalent Matchings) if $P_{1}$ and $P_{2}$ are different only
inside detached clusters, they are logically equivalent.

When some dual clusters are attached, the above cluster-based method will lead
to a higher logical error rate than the MWPM decoders. On the other hand,
because usually most dual clusters are detached, the difference in logical
error rate can be small. Attached clusters are exponentially less likely with
increasing code distance ($d$).

##  Examples

We next provide two examples in which the two conditions described above are
true and as a result, a UF decoder will be as accurate as an MWPM decoder.

###  No adjacent errors

When no errors are present in two adjacent data qubits, both conditions of the
Observation are true and a UF decoder will achieve the same accuracy as MWPM
decoders. This is because when no errors are present in two adjacent data
qubits, vertices in the syndrome graph always appear in pairs that are far
from each other or a single vertex adjacent to a virtual boundary vertex. As a
result, both a UF decoder and the blossom algorithm will decompose the
syndrome graph into clusters each covering such a pair.

###  XZZX code

The XZZX surface code is a variant of the CSS surface code [2]. It employs a
single type of stabilizer that measures $X\otimes Z\otimes Z\otimes X$. Thus
in the XZZX surface code, a single $X$ (or $Z$) error always generates a pair
of nontrivial measurements horizontally (or vertically).

We next show the two conditions presented in §4 are true for the XZZX code
with infinite noise bias and noiseless stabilizers, known as the code capacity
noise model [19]. We note the two conditions are not true with the circuit-
level noise model [20].

Without loss of generality, we assume there are only Z errors on data qubits.
The model graph now becomes a set of disjoint subgraphs: each is a line (or 1D
chain). As a result, the syndrome graph also becomes a set of parallel lines.
A perfect matching of the syndrome graph must comprise of perfect matchings
for all such lines, each found separately.

##### Identical Clusters.

An MWPM decoder grows an odd dual cluster at the same pace due to the use of
the multiple tree approach [14]. When the dual cluster is 1D, it grows left
and right at the same pace, exactly like how an odd cluster grows in a UF
decoder. In general, an MWPM decoder may not find a perfect matching with only
tight edges inside an even dual cluster. However, inside a 1D even dual
cluster, an edge between two adjacent vertices must be tight because of how
these two vertices got merged into one cluster. As a result, an MWPM decoder
can always find a perfect matching with tight edges by selecting edges between
pairs of adjacent vertices. That is, in a 1D chain, an MWPM decoder always
consider an even dual cluster solved, exactly like how a UF decoder treats an
even cluster. Thus, the MWPM and UF decoders update clusters in exactly the
same way and terminate at the same clusters when the clusters are 1D.

##### Equivalent Matchings

When a cluster is detached, the solutions from the UF decoder and the MWPM
decoder never differ by a nontrivial logical operator, according to Lemma
(Equivalent Matchings). Otherwise, if the cluster is attached, there are only
two complementary perfect matchings of the cluster. Because a cluster grows
left and right at the same rate, these two complementary perfect matchings
must have the same weight and therefore both are MWPM. Because a UF decoder
must select one of them, it will select a MWPM for the cluster and as a
result, behave the same as an MWPM decoder for this cluster.

##  Weighted Union-Find Decoder

An astute reader will point out that the original union-find decoder [12]
works on the decoding graph. Yet the interpretation provided above works on
the syndrome graph. This difference is only cosmetic as we purposefully adapt
the union-find decoder for the syndrome graph in order to juxtapose it with
the blossom algorithm. Implementation-wise, the decoding graph is preferred
for lower time complexity. See Appendix B for more explanation.

Another, more substantial difference is that the original UF decoder works on
an _unweighted_ decoding graph, assuming identical error probability for all
data qubits. As a result, it grows all odd clusters by half a unit each step.
Yet the interpretation above does not need this assumption. Rather, it must
compute the safe amount of growth for the odd clusters at each step. This
leads to a more general union-find decoder that works with weighted model
graphs, described below.

Huang, Newman and Brown [17] already report a UF decoder design that uses
weighted model graphs, without explicitly identifying the link between the UF
and MWPM decoders presented above. They compute the weight as $\ln((1-p)/p)$
where $p$ is the error probability, which is similar to the integer-weighted
UF decoder described below.

##### Real-Weighted Union-Find Decoder

A real-weighted union-find decoder has a time complexity no worse than
$O(N^{2})$, $N$ being the number of vertices in the model graph. This is due
to two factors: first, in each step, it has a time-complexity of at most
$O(N)$ to compute the maximum safe growth such that when all odd clusters grow
by that much, they will not overlap. The maximum safe growth is calculated
such that at least one more edge is fully covered by clusters, i.e., becomes
fully grown, to use the language of Delfosse and Nickerson [12]. Second, it
takes at most $O(N)$ steps to finish grow all clusters because each step will
get at least one edge covered by the clusters while there are $O(N)$ uncovered
edges to begin with.

A real-weighted union-find decoder should have better time complexity, worst-
case and average, than the blossom algorithm, for three reasons. First, the
blossom algorithm works on the syndrome graph, which has $O(N^{2})$ edges,
while the union-find decoder works on the model graph, which has $O(N)$ edges.
Second, the dual clusters in the blossom algorithm may shrink, while the
clusters in the union-find decoder only grow. The possibility of shrinking may
lead to more steps before finish growing all clusters. Finally, the blossom
algorithm maintains the structure inside each cluster. As a result, it merges
two clusters with a time complexity proportional to the cluster size, while
the real-weighted UF decoder merges two clusters within constant time.

##### Integer-Weighted Union-Find Decoder

When the weights of the model graph are small integers, union-find decoders
can be much faster in terms of the worst-case time complexity. This is because
the safe growth computation becomes trivial: all odd clusters grow by half a
unit each step, just like in the original union-find decoder. Each edge with
weight $w_{e}$ in the model graph is at most visited $O(w_{e})$ times. Given
the maximum weight $w_{\max}$, the overall worst-case time complexity of
integer-weighted union-find decoder is $O(N\cdot(\alpha(N)+w_{\max}))$ where
$\alpha(N)$ is an almost constant inverse Ackermann’s function [12]. As a
result, the average decoding time complexity must be between $O(N)$ and
$O(N\cdot(\alpha(N)+w_{\max}))$, which is almost linear.

On the other hand, we can see the worst time complexity of an integer-weighted
UF decoder grows with $w_{\max}$ while that of a real-weighted union-find
decoder does not. Therefore, when $w_{\max}$ is large, a real-weighted union-
find decoder can be faster than an integer-weighted one when the integer
weights are too large.

##### Implementation

We have implemented and open-sourced both weighted UF decoders described above
[5]. Our implementation of the real-weighted UF decoder uses the integer data
type (64-bit signed integer) to avoid rounding errors in the floating point
data type, a strategy borrowed from the blossom V algorithm implementation
[14]. For both weighted UF decoders, we use an integer $w_{\max}$ to represent
the largest weight $W=\max_{e}{w_{e}}$ and compute the integer weight for an
edge of weight $w_{e}$ as $\lfloor w_{e}/W*w_{\max}\rfloor$. The only
difference between our implementations of the real-weighted and integer-
weighted UF decoders lies in how they compute the growth when growing the odd
clusters: the real-weighted UF decoder computes the maximum safe growth while
the integer-weighted one grows them by one each time, as explained in §6. As a
result, they have the same accuracy given the same scaling $w_{\max}$.

##  Discussion

In this paper, we limit the discussion to open-boundary surface codes.
Nevertheless, we believe the same interpretation works on other surface codes
as well with proper generalization of notions. For example, “attached cluster”
can be generalized to a subgraph whose edges constitute a nontrivial logical
operator. The relationship between UF decoders and the blossom algorithm also
suggests that UF decoders can be adapted to solve any decoding problem that
can be solved by a MWPM of the syndrome graph, e.g., the color code [21].

The revealed relationship between UF decoder and the blossom algorithm further
suggests ways of cross-pollination between the blossom algorithm and UF
decoders. We have already showed that it can lead to new UF decoder designs in
§6. One can borrow more ideas from the blossom algorithm to make UF decoders
better. For example, one can keep the internal structures of small clusters so
that they grow like the dual clusters in the blossom algorithm. On the other
hand, one could also bring ideas from UF decoders into the blossom algorithm
to improve the latter’s speed. For example, we have recently shown that
instead of the syndrome graph, MWPM decoders can be made faster [22] by
adopting the decoding graph used by UF decoders, which has also been
independently discovered by Higgott and Gidney [23].

## References

  * [1] Delfosse, N. & Zémor, G.  Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel.  _Physical Review Research_ 2, 033042 (2020).
  * [2] Bonilla Ataides, J. P., Tuckett, D. K., Bartlett, S. D., Flammia, S. T. & Brown, B. J.  The xzzx surface code.  _Nature communications_ 12, 1–12 (2021).
  * [3] Wu, Y., Liyanage, N., Puri, S. & Zhong, L.  Interpretation of union find decoder on weighted graphs and application to xzzx surface code (2022).  URL https://www.youtube.com/watch?v=BbhqUHKPdQk.  APS March Meeting.
  * [4] Oscar, H. & Gidney, C.  Personal communication.  _Google Quntum AI Team_ (September, 2022).
  * [5] QEC-playground: a decoder testbed for quantum error correction.  URL https://github.com/yale-paragon/QEC-Playground.
  * [6] Bombín, H.  An introduction to topological quantum codes.  _arXiv preprint arXiv:1311.0277_ (2013).
  * [7] Yoder, T. J. & Kim, I. H.  The surface code with a twist.  _Quantum_ 1, 2 (2017).
  * [8] Tomita, Y. & Svore, K. M.  Low-distance surface codes under realistic quantum noise.  _Physical Review A_ 90, 062320 (2014).
  * [9] Micali, S. & Vazirani, V. V.  An o (v— v— c— e—) algoithm for finding maximum matching in general graphs.  In _21st Annual Symposium on Foundations of Computer Science (sfcs 1980)_ , 17–27 (IEEE, 1980).
  * [10] Gabow, H. N. & Tarjan, R. E.  Faster scaling algorithms for general graph matching problems.  _Journal of the ACM (JACM)_ 38, 815–853 (1991).
  * [11] Goldberg, A. V. & Karzanov, A. V.  Maximum skew-symmetric flows and matchings.  _Mathematical Programming_ 100, 537–568 (2004).
  * [12] Delfosse, N. & Nickerson, N. H.  Almost-linear time decoding algorithm for topological codes.  _Quantum_ 5, 595 (2021).
  * [13] Edmonds, J.  Paths, trees, and flowers.  _Canadian Journal of Mathematics_ 17, 449–467 (1965).
  * [14] Kolmogorov, V.  Blossom V: a new implementation of a minimum cost perfect matching algorithm.  _Mathematical Programming Computation_ 1, 43–67 (2009).
  * [15] Matousek, J. & Gärtner, B.  _Understanding and using linear programming_ (Springer Science & Business Media, 2006).
  * [16] Fowler, A. G.  Minimum weight perfect matching of fault-tolerant topological quantum error correction in average $o(1)$ parallel time (2014).  1307.1740.
  * [17] Huang, S., Newman, M. & Brown, K. R.  Fault-tolerant weighted union-find decoding on the toric code.  _Physical Review A_ 102 (2020).  URL http://dx.doi.org/10.1103/PhysRevA.102.012419.
  * [18] Bravyi, S. B. & Kitaev, A. Y.  Quantum codes on a lattice with boundary.  _arXiv preprint quant-ph/9811052_ (1998).
  * [19] Landahl, A. J., Anderson, J. T. & Rice, P. R.  Fault-tolerant quantum computing with color codes.  _arXiv preprint arXiv:1108.5738_ (2011).
  * [20] Darmawan, A. S., Brown, B. J., Grimsmo, A. L., Tuckett, D. K. & Puri, S.  Practical quantum error correction with the xzzx code and kerr-cat qubits.  _PRX Quantum_ 2, 030345 (2021).
  * [21] Sahay, K. & Brown, B. J.  Decoder for the triangular color code by matching on a möbius strip.  _PRX Quantum_ 3, 010310 (2022).
  * [22] Fusion Blossom: a fast minimum-weight perfect matching (mwpm) solver for quantum error correction (QEC).  URL https://github.com/yale-paragon/fusion-blossom.
  * [23] Higgott, O. & Gidney, C.  Pymatching v2.  https://github.com/oscarhiggott/PyMatching (2022).
  * [24] Lamport, L.  How to write a 21st century proof.  _Journal of fixed point theory and applications_ 11, 43–63 (2012).

## Acknowledgements

We thank Shruti Puri for fruitful discussion and insightful feedback. This
work was supported in part by Yale University and NSF MRI Award #2216030.

Appendix

##  Appendix A Surface Code, Syndrome Graph, and Perfect Matching

###  Structured Proof

We opt for the style of proof known as structured [24] for its clarity. A
structured proof employs a hierarchical structure that provides both the high-
level idea and low-level details. The proof consists of steps organized in
multiple layers. Each step is prefixed with $\langle n\rangle m$, which means
it is the $m$-th step of the $n$-th layer. Every step comes with a proof,
either a single sentence prefixed with Proof: or a sub layer ending with
Q.E.D..

###  Error Pattern, Syndrome, and Parity

A surface code can be represented by the model graph $G(U,F)$, where $U$ is
the set of vertices, each representing a stabilizer, and $F$ is the set of
edges, each representing an independent error source, including data qubit.
$\forall u\in U$, let $F(u)$ denote the set of edges that are incident to $u$;
likewise, $\forall f\in F$, $U(f)$ denotes the set of vertices that are
incident to $f$.

##### Error Pattern

In this work, we only consider Pauli errors. Therefore, an error to $f\in F$
can be regarded as an operator $\hat{f}$ that “flips” the state of $f$.
Obviously $\hat{f}\hat{f}=I$. An error pattern $\mathcal{E}$ is a subset of
error sources (edges) in which error happens. On the model graph, it can be
denoted as $E\subseteq F$. An error pattern can also be considered as an
operator $\hat{\mathcal{E}}$ that flips the corresponding error sources:
$\hat{\mathcal{E}}=\prod_{f\in E}\hat{f}$. Because there is a bijective
mapping between error patterns and operators, we often use an error pattern
$\mathcal{E}$ and its operator $\hat{\mathcal{E}}$ in an interchangeable
manner.

Borrowing the notations from [6], we can represent $\mathcal{E}$ as a sum over
all edges: $\mathcal{E}=\sum_{f\in E}f$.

With this sum form, two error patterns can be added together to form a new one
with $f+f=0$, because an error flips the state of error source $f$. Given two
error patterns, $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$, we define their sum
as

$\mathcal{E}_{1}\oplus\mathcal{E}_{2}=\sum_{f\in E_{1}}f+\sum_{f\in
E_{2}}f=\sum_{f\in E_{1}\triangle E_{2}}f$

The error patterns and $\oplus$ constitute an Abelian group. The inverse of an
error pattern is simply itself. For simplicity, we use $+$ in place of
$\oplus$.

A special type of error pattern is a path of contiguous edges that starts with
one vertex and ends with another. A circle is a path that starts and ends with
the same vertex.

##### Syndrome

For a stabilizer $u\in U$, it gives a nontrivial measurement outcome if an odd
number of edges it connects with experience error. Intuitively, one can
consider an error in an edge incidental to $u$ “flips” the stabilizer
measurement outcome.

For error patterns of a single error, $\forall f\in F$, we can represent its
syndrome in a similar sum form

$S(\\{f\\})=\sum_{u\in U(f)}u.$

That is, a single error in $f$ causes nontrivial measurement outcomes in all
stabilizers it is connected with.

Given an error pattern $\mathcal{E}$, its syndrome $S$ includes all the
nontrivial measurement outcomes. We can represent $S$ as a sum over the
syndromes of all its errors.

$S(\mathcal{E})=\sum_{f\in E}S(\\{f\\})$ (5)

where $\forall u\in U$, $u+u=0$, because a stabilizer gives a nontrivial
measurement outcome if an odd number of edges it connects with experience
error.

Given two error patterns $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$, we have

$S(\mathcal{E}_{1}+\mathcal{E}_{2})=S(\mathcal{E}_{1})+S(\mathcal{E}_{2}).$

Given a path $\mathcal{P}$ in the model graph connecting two vertices $u$ and
$v$, we have $S(\mathcal{P})=u+v$.

##### Parity

For $u\in U$, let $V_{L}(u)$ indicate whether $u$ is a left virtual boundary
vertex: 1 if yes; 0 if not.

For error patterns of a single error, $\forall f\in F$, its left parity
$P_{L}(\\{f\\})$ is defined as parity of how many left virtual boundary
vertices $f$ is incident to.

$P_{L}(\\{f\\})=\sum_{u\in U(f)}V_{L}(u)$

where $V_{L}(u)+V_{L}(u)=0$. Given an error pattern $\mathcal{E}$, its left
parity $P_{L}$ is the sum of the parity of all its single errors.

$P_{L}(\mathcal{E})=\sum_{f\in E}P_{L}(\\{f\\}).$ (6)

where $1+1=0$. Given two error patterns $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$, we have

$P_{L}(\mathcal{E}_{1}+\mathcal{E}_{2})=P_{L}(\mathcal{E}_{1})+P_{L}(\mathcal{E}_{2}).$

Given a path $\mathcal{P}$ in the model graph connecting two vertices $u$ and
$v$, we have $P_{L}(\mathcal{P})=V_{L}(u)+V_{L}(v)$.

The parity on the right boundary $P_{R}(\mathcal{E})$ is similarly defined.
For open-boundary surface code, we have:

$P_{L}(\mathcal{E})+P_{R}(\mathcal{E})=|S(\mathcal{E})|\ (\mathrm{mod}\ 2).$
(7)

We provide some intuition behind this property that links the parity with the
syndrome. When the error pattern is empty,
$P_{L}(\mathcal{E})+P_{R}(\mathcal{E})=|S(\mathcal{E})|\ (\mathrm{mod}\ 2)=0$.
Otherwise, $\forall f=\langle u,v\rangle\in E$, if $V_{L}(u)=1$, i.e., $f$ is
incidental to the left virtual boundary, $v$ must be a stabilizer. We have
$P_{L}(\\{f\\})=1$ and $S(\\{f\\})=v$. That is, $f$ will flip both
$P_{L}(\mathcal{E})$ and $|S(\mathcal{E})|(\mathrm{mod}\ 2)$. The same can be
said about edges incidental to the right virtual boundary. if $f$ is not
incidental to either virtual boundary, $P_{L}(\\{f\\})=P_{R}(\\{f\\})$=0 and
$f$ will flip the states of both $u$ and $v$ and as a result, leave
$|S(\mathcal{E})|(\mathrm{mod}\ 2)$ unchanged.

##### Logical operator and trivial logical operator

When an operator is applied to the surface code, a subset of the stabilizers
may have nontrivial measurement outcomes. When the subset is empty, i.e., all
measurement outcomes are trivial, the operator is a _logical operator_. That
is, a logical operator does not produce any syndrome.

_Definition (Logical Operator)_ : an error pattern $\mathcal{E}$ is a logical
operator if and only $S(\mathcal{E})=0$.

If $\mathcal{E}$ is a logical operator, we have $S(\mathcal{E})=0$ and
therefore $P_{L}(\mathcal{E})=P_{R}(\mathcal{E})$. Therefore, when we know
$\mathcal{E}$ is a logical operator, we will use $P(\mathcal{E})$ as a short-
hand for both $P_{L}(\mathcal{E})$ and $P_{R}(\mathcal{E})$.

A trivial logical operator does not change the logical state of the surface
code. In §2.1, we introduced the notion of trivial logical operator and
mentioned that error patterns that form closed circles are trivial logical
operators. We define it formally below.

_Definition (Trivial Logical Operator)_ : A logical operator $\mathcal{E}$ is
trivial iff $P(\mathcal{E})=0$.

A circle on the model graph is a trivial logical operator. This is because a
circle $\mathcal{C}$ starts and ends with the same vertex $u$:
$S(\mathcal{C})=u+u=0$ and $P(\mathcal{C})=V_{L}(u)+V_{L}(u)=0$.

Given any trivial logical operator $\mathcal{T}$ and $\mathcal{E}$ an error
pattern, we have $S(\mathcal{E}+\mathcal{T})=S(\mathcal{E})$ and
$P(\mathcal{E}+\mathcal{T})=P(\mathcal{E})$. That is, adding a trivial logical
operator to any error pattern will not change the syndrome or parity.

###  Syndrome Graph

Given the surface code, represented by the model graph $G(U,F)$, and its
measurement, we can construct the syndrome graph $G(V,E)$ as follows.
$V\subseteq U$ includes all the model graph vertices that have nontrivial
measurement outcomes; $E=\\{e=\langle u,v\rangle|\forall u,v\in V\\}$. For
$e=\langle u,v\rangle\in E$, the weight $w_{e}$ is computed as the weight of
the minimum-weight path between $u$ and $v$ in the model graph.

Because there may be multiple minimum-weight paths between $u$ and $v$,
$e=\langle u,v\rangle$ may represent multiple error patterns, which is denoted
by the set $\mathbf{e}$. $\forall\mathcal{E}\in\mathbf{e}$, it can be
considered a collection of single qubit errors, corresponding to the model
graph edges in a minimum-weight path $\mathcal{P}$. That is,
$\mathcal{E}=\sum_{f\in\mathcal{P}}f$.

Lemma (O) $\forall e\in E$, $\mathcal{E}_{1}$, $\mathcal{E}_{2}\in\mathbf{e}$,
$\mathcal{E}_{1}+\mathcal{E}_{2}$ is a trivial logical operator.

$S(\mathcal{E}_{1}+\mathcal{E}_{2})=0$ and
$P(\mathcal{E}_{1}+\mathcal{E}_{2})=0$.

Proof: By definition of trivial logical operator.

$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ are paths connecting the same two
vertices $u$ and $v$ in the model graph.

Proof: By definition of $e$.

$S(\mathcal{E}_{1}+\mathcal{E}_{2})=0$

$S(\mathcal{E}_{1})=u+v$; $S(\mathcal{E}_{2})=u+v$

$S(\mathcal{E}_{1}+\mathcal{E}_{2})=S(\mathcal{E}_{1})+S(\mathcal{E}_{2})$
$=(u+u)+(v+v)=0$;

Q.E.D.

$P(\mathcal{E}_{1}+\mathcal{E}_{2})=0$

$P(\mathcal{E}_{1})=V_{L}(u)+V_{L}(v)$,
$P(\mathcal{E}_{2})=V_{L}(u)+V_{L}(v)$

$P(\mathcal{E}_{1}+\mathcal{E}_{2})=P(\mathcal{E}_{1})+P(\mathcal{E}_{2})=\\\
(V_{L}(u)+V_{L}(u))+(V_{L}(v)+V_{L}(v))=0$

Q.E.D.

Q.E.D.

##### Subgraph

A subgraph of the syndrome graph $G(V,E)$ is defined by a subset of $E$,
$E^{\prime}\subseteq E$. $E^{\prime}$ defines a set of error patterns
$\mathbf{E}^{\prime}$.

$\mathbf{E}^{\prime}=\\{\mathcal{E}|\mathcal{E}=\sum_{e\in
E^{\prime}}\mathcal{E}_{e},\forall\mathcal{E}_{e}\in\mathbf{e}\\}$

Therefore, $\forall\mathcal{E}\in\mathbf{E}^{\prime}$,
$\exists\mathcal{E}_{e}\in\mathbf{e}$ for $\forall e\in E^{\prime}$ such that
$\mathcal{E}=\sum_{e\in E^{\prime}}\mathcal{E}_{e}$. That is, an error pattern
represented by the subgraph can be “decomposed” into error patterns
represented by its edges.

Using the familiar sum form, we can represent $E^{\prime}$ as $\sum_{e\in
E^{\prime}}e$. Two subgraphs can be “added” together to form a new one with
$e+e=0$. The symmetric difference between two subgraphs $E_{1}$ and $E_{2}$
can be simplified as $E_{1}\triangle E_{2}=E_{1}+E_{2}$.

###  Perfect matchings

Given a syndrome graph $G(V,E)$, a perfect matching is a subgraph in which
every vertex from $V$ is incident to one and only one edge from $E$. It
represents a set of error patterns $\mathbf{E}$ such that
$\mathcal{E}\in\mathbf{E}$ produces the syndrome. That is, $S(\mathcal{E})=V$.
We note that $\mathbf{E}$ does not include all the error patterns for the
syndrome.

Lemma (I) Given a syndrome graph and its perfect matching represented by
$\mathbf{E}$ and $\mathcal{E}_{1}$, $\mathcal{E}_{2}\in\mathbf{E}$,
$\mathcal{E}_{1}+\mathcal{E}_{2}$ is a trivial logical operator.

$S(\mathcal{E}_{1}+\mathcal{E}_{2})=0$ and
$P(\mathcal{E}_{1}+\mathcal{E}_{2})=0$.

$S(\mathcal{E}_{1}+\mathcal{E}_{2})=0$

$S(\mathcal{E}_{1})=S(\mathcal{E}_{2})$=V

Proof: By definition of perfect matching.

$S(\mathcal{E}_{1})+S(\mathcal{E}_{2})=V+V=0$

Q.E.D.

$P(\mathcal{E}_{1}+\mathcal{E}_{2})=0$

Let $E^{\prime}\subseteq E$ denote the edges of the perfect matching

$\exists\mathcal{E}^{1}_{e}\in\mathbf{e}$ for $\forall e\in E^{\prime}$ such
that $\mathcal{E}_{1}=\sum_{e\in E^{\prime}}\mathcal{E}^{1}_{e}$;
$\exists\mathcal{E}^{2}_{e}\in\mathbf{e}$ for $\forall e\in E^{\prime}$ such
that $\mathcal{E}_{2}=\sum_{e\in E^{\prime}}\mathcal{E}^{2}_{e}$.

Proof: By subgraph decomposition.

$P(\mathcal{E}_{1}+\mathcal{E}_{2})=P(\mathcal{E}_{1})+P(\mathcal{E}_{2})\\\
=P(\sum_{e\in E^{\prime}}\mathcal{E}^{1}_{e})+P(\sum_{e\in
E^{\prime}}\mathcal{E}^{2}_{e})\\\ =\sum_{e\in
E^{\prime}}P(\mathcal{E}^{1}_{e})+\sum_{e\in
E^{\prime}}P(\mathcal{E}^{2}_{e})\\\ =\sum_{e\in
E^{\prime}}(P(\mathcal{E}^{1}_{e})+P(\mathcal{E}^{2}_{e}))\\\ =\sum_{e\in
E^{\prime}}(P(\mathcal{E}^{1}_{e}+\mathcal{E}^{2}_{e}))=0$

Proof: By Lemma (O).

Q.E.D.

Lemma (II) Given a syndrome graph, let $\mathbf{E}_{1}$ and $\mathbf{E}_{2}$
denote two perfect matchings. For $\mathcal{E}_{1}\in\mathbf{E}_{1}$,
$\mathcal{E}_{2}\in\mathbf{E}_{2}$, $\mathcal{E}_{1}+\mathcal{E}_{2}$ is a
logical operator.

$S(\mathcal{E}_{1}+\mathcal{E}_{2})=0$

$S(\mathcal{E}_{1})=S(\mathcal{E}_{2})=V$

Proof:by definition of perfect maching

$S(\mathcal{E}_{1}+\mathcal{E}_{2})=S(\mathcal{E}_{1})+S(\mathcal{E}_{2})=V+V=0$

Q.E.D.

####  A.4.1 Cluster decomposition

Given a cluster defined by an even subset of $V$. The above lemmas are also
true for perfect matchings inside the cluster. We will refer to them as Lemma
(Cluster) in the following.

###  Equivalent Matchings

Assume the syndrome graph has been decomposed into non-overlapping clusters
each with an even number of vertices $C_{i}$, $i=1,2,...,n$. Let $G_{i}$,
$i=1,2,...,n$ denote the corresponding subgraphs. $P_{i}^{1}$ and $P_{i}^{2}$
denote two perfect matchings for $G_{i}$. $P_{1}=\sum_{i}P_{i}^{1}$ and
$P_{2}=\sum_{i}P_{i}^{2}$ are two perfect matchings for the syndrome graph.

Let $\mathbf{E}_{i}^{1}$ and $\mathbf{E}_{i}^{2}$ denote sets of error
patterns represented by $P_{i}^{1}$ and $P_{i}^{2}$, respectively. Let
$\mathbf{E}_{1}$ and $\mathbf{E}_{2}$ denote sets of error patterns
represented by $P_{1}$ and $P_{2}$, respectively.
$\forall\mathcal{E}_{1}\in\mathbf{E}_{1}$,
$\exists\mathcal{E}_{i}^{1}\in\mathbf{E}_{i}^{1}$, such that
$\mathcal{E}_{1}=\sum_{i}\mathcal{E}_{i}^{1}$. Similarly,
$\forall\mathcal{E}_{2}\in\mathbf{E}_{2}$,
$\exists\mathcal{E}_{i}^{2}\in\mathbf{E}_{i}^{2}$, such that
$\mathcal{E}_{2}=\sum_{i}\mathcal{E}_{i}^{2}$.

Lemma (Equivalent Matchings) if a cluster is detached, its perfect matchings
are logically equivalent.

$\forall\mathcal{E}_{1}\in\mathbf{E}_{1}$ and
$\forall\mathcal{E}_{2}\in\mathbf{E}_{2}$, $\mathcal{E}_{1}+\mathcal{E}_{2}$
is a trivial logical operator

By definition of _Logical Equivalence_ for subgraphs

$S(\mathcal{E}_{1}+\mathcal{E}_{2})=0$

$S(\mathcal{E}_{1}+\mathcal{E}_{2})=S(\mathcal{E}_{1})+S(\mathcal{E}_{2})=0$

Proof: $S(\mathcal{E}_{1})=S(\mathcal{E}_{2})$ because both perfect matchings
produce the syndrome inside the same cluster.

Q.E.D.

$P(\mathcal{E}_{1}+\mathcal{E}_{2})=0$

Either $P_{L}(\mathcal{E}_{1})=P_{L}(\mathcal{E}_{2})=0$ or
$P_{R}(\mathcal{E}_{1})=P_{R}(\mathcal{E}_{2})=0$

Proof: by definition of _Detached cluster_.

$P_{R}(\mathcal{E}_{1}+\mathcal{E}_{2})=P_{L}(\mathcal{E}_{1}+\mathcal{E}_{2})$

Proof: by Equation 7 and Step $\langle 1\rangle 1$.

Q.E.D.

Q.E.D.

Theorem (Equivalent Matchings) if $P_{1}$ and $P_{2}$ are different only
inside detached clusters, they are logically equivalent.

$\forall\mathcal{E}_{1}\in\mathbf{E}_{1}$ and
$\forall\mathcal{E}_{2}\in\mathbf{E}_{2}$,
$S(\mathcal{E}_{1}+\mathcal{E}_{2})=0$ and
$P(\mathcal{E}_{1}+\mathcal{E}_{2})=0$.

Proof: By definition of trivial logical operator and definition of logical
equivalence.

$S(\mathcal{E}_{1}+\mathcal{E}_{2})=0$

$S(\mathcal{E}_{1}+\mathcal{E}_{2})=S(\sum_{i}(\mathcal{E}_{i}^{1}+\mathcal{E}_{i}^{2}))\\\
=\sum_{i}S(\mathcal{E}_{i}^{1}+\mathcal{E}_{i}^{2})=0$

Proof: $S(\mathcal{E}_{i}^{1}+\mathcal{E}_{i}^{2})=0$ by Lemma (II).

Q.E.D.

$P(\mathcal{E}_{1}+\mathcal{E}_{2})=0$

$P(\mathcal{E}_{1}+\mathcal{E}_{2})=P(\sum_{i}(\mathcal{E}_{i}^{1}+\mathcal{E}_{i}^{2}))\\\
=\sum_{i}P(\mathcal{E}_{i}^{1}+\mathcal{E}_{i}^{2})=0$

If cluster $i$ is detached, $P(\mathcal{E}_{i}^{1}+\mathcal{E}_{i}^{2})=0$

Otherwise, cluster is attached. $P_{i}^{1}=P_{i}^{2}$ by assumption and then
$P(\mathcal{E}_{i}^{1}+\mathcal{E}_{i}^{2})=0$

Proof: by Lemma (II) (Cluster).

Q.E.D.

Q.E.D.

Q.E.D.

##  Appendix B UF Decoder on Syndrome Graph

(1) Decoding Graph

(2) Syndrome Graph

Figure 6: Clusters on syndrome graph and decoding graph always touch at
simultaneously.

While the original UF decoder works on the decoding graph [12], we show that
the UF decoder works on the syndrome graph equivalently in terms of decoding
accuracy.

The difference between the decoding graph and the syndrome graph is two-fold:
the syndrome graph only have syndrome vertices $V^{S}$ while the decoding
graph have all measurement vertices $V^{D}\supseteq V^{S}$; the syndrome graph
is a complete graph where there is an edge between any pair of vertices
$u,v\in V^{S}$. Every edge $e=\langle u,v\rangle$ in the syndrome graph
corresponds to the minimum-weight paths between $u$ and $v$ in the decoding
graph. We define the distance $d(u,v)$ between vertices $u,v$ in a graph as
the weight of a minimum-weight path between them. A point $k$ is either a
vertex or a point on an edge. Similarly we can define $d(u,k)$ as the weight
of a minimum-weight path from vertex $u$ to a point $k$.

In order to show that UF decoders on both graphs have the same decoding
accuracy, we only need to show that the final clusters are the same, i.e.
covering the same set of syndrome vertices. The UF decoder logic is the same:
it grows a cluster uniformly over all possible directions, and stops when it
becomes even or touches a virtual boundary. Using mathematical induction, if
we can show that during the algorithm clusters always touch simultaneously on
two graphs, then the final clusters are the same. Figure 6 shows an example of
clusters touching simultaneously on the decoding graph and the syndrome graph.

##  Appendix C Examples using the Fowler diagram

(1) $\sum y=0$

(2) $\sum y=4.5$

(3) $\sum y=6.2$

(4) $\sum y=7.3$

(5) $\sum y=7.6$

(6) $\sum y=7.9$

(7) $\sum y=8.3$

(8) $\sum y=9$

Figure 7: The blossom algorithm with multiple tree approach [14]. The primal
variables are drawn as blue lines connecting vertices. The dual variables are
drawn as the “radius” of the colored regions. When two regions touch, a tight
edge is formed between two vertices from each region. (1) The initial state
with all dual variables initialized to 0. (2) The dual variable of each vertex
grows simultaneously. (3) When the regions of vertices $A$, $B$, $C$ touch
each other, they form a blossom marked in dotted blue lines. The dual variable
of this blossom $y_{\\{A,B,C\\}}$ (green) grows but individual dual variables
$y_{A}$, $y_{B}$ and $y_{C}$ stop growing. (4) When the regions of vertices
$D$ and $E$ touch each other, they form a solved dual cluster marked in solid
blue line. The dual variables $y_{D}$, $y_{E}$ stop growing. (5) When the
blossom $\\{A,B,C\\}$ touches the solved cluster $\\{D,E\\}$, it forms an
alternating tree marked in dashed and solid blue lines. (6) In this
alternating tree, $y_{\\{A,B,C\\}}$ and $y_{E}$ grows as usual, but $y_{D}$
shrinks at the same speed. In this way, they still keep touch with each other.
(7) A bigger blossom is formed and its dual variable $y_{\\{A,B,C,D,E\\}}$
(purple) starts growing. Individual dual variables $y_{\\{A,B,C\\}}$, $y_{D}$
and $y_{E}$ stop growing. (8) This blossom touches a left virtual boundary
vertex and breaks into three temporary matches: $A$ matches to the left
virtual boundary vertex, $B$ matches to $C$, $D$ matches to $E$. The cluster
is now solved, so the blossom algorithm terminates. The minimum-weight perfect
matching is the collection of all those matchings with only tight edges.

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

Figure 8: The union-find decoder. A grown edge is fully covered by regions
(yellow). A half-grown edge is partly covered by regions. An unoccupied edge
is not covered by any region. (1) Initially all edges are unoccupied. (2) Each
vertex is an odd cluster and grows uniformly. Odd (even) cluster consists of
odd (even) number of vertices. (3) Clusters merge together. The new cluster
$\\{A,B,C\\}$ is still an odd cluster and keeps growing. (4) Two odd clusters
$D$ and $E$ merge into an even cluster and stop growing. (5) The odd cluster
$\\{A,B,C\\}$ merges with the even cluster $\\{D,E\\}$ and becomes a bigger
odd cluster $\\{A,B,C,D,E\\}$. This bigger cluster grows uniformly even though
the cluster $\\{D,E\\}$ has been stopped for a while. (6)(7)(8) The odd
cluster $\\{A,B,C,D,E\\}$ keeps growing until it touches a left virtual
boundary vertex and terminates. After all clusters stop growing, the union-
find decoder applies the peeling algorithm to find an error pattern that
generates this syndrome using single-qubit errors only inside each cluster.
This error pattern corresponds to a perfect matching marked in blue lines in
(8), though generally not a minimum-weight perfect matching. Note that each
sub-figure corresponds to one in Figure 7, with similar shape of regions.