# Color code decoder with improved scaling for correcting circuit-level noise

Seok-Hyung Lee<EMAIL_ADDRESS>Centre for Engineered Quantum
Systems, School of Physics, The University of Sydney, Sydney, NSW 2006,
Australia  Andrew Li  Centre for Engineered Quantum Systems, School of
Physics, The University of Sydney, Sydney, NSW 2006, Australia  Stephen D.
Bartlett<EMAIL_ADDRESS>Centre for Engineered Quantum
Systems, School of Physics, The University of Sydney, Sydney, NSW 2006,
Australia

###### Abstract

Two-dimensional color codes are a promising candidate for fault-tolerant
quantum computing, as they have high encoding rates, transversal
implementation of logical Clifford gates, and high feasibility of magic state
constructions. However, decoding color codes presents a significant challenge
due to their structure, where elementary errors violate three checks instead
of just two (a key feature in surface code decoding), and the complexity in
extracting syndrome is greater. We introduce an efficient color-code decoder
that tackles these issues by combining two matching decoders for each color,
generalized to handle circuit-level noise by employing detector error models.
We provide comprehensive analyses of the decoder, covering its threshold and
sub-threshold scaling both for bit-flip noise with ideal measurements and for
circuit-level noise. Our simulations reveal that this decoding strategy nearly
reaches the best possible scaling of logical failure ($p_{\mathrm{fail}}\sim
p^{d/2}$) for both noise models, where $p$ is the noise strength, in the
regime of interest for fault-tolerant quantum computing. While its noise
thresholds are comparable with other matching-based decoders for color codes
($8.2\%$ for bit-flip noise and $0.46\%$ for circuit-level noise), the scaling
of logical failure rates below threshold significantly outperforms the best
matching-based decoders.

##  1 Introduction

Two-dimensional (2D) color codes [1, 2] are a family of stabilizer quantum
error-correcting codes that can be realized with local interactions on a 2D
plane, and provide a promicing pathway for implementing fault-tolerant quantum
computation. Compared to surface codes [3, 4], color codes have several
noteworthy advantages: (i) They have higher encoding rates for the same code
distance [5], (ii) all the Clifford gates can be implemented transversally
[1], and (iii) an arbitrary pair of commuting logical Pauli product operators
can be measured in parallel via lattice surgery [6]. In addition, the well-
studied Steane code is a small instance of a color code, and recently a number
of fault-tolerant operations including transversal logic gates and magic state
injection have been demonstrated using color codes [7, 8, 9, 10, 11].

For these desirable features to be exploited for fault-tolerant quantum
computing in practice, we need better decoders for color codes. Surface codes
benefit from the many advantages of a decoding approach based on ‘matching’,
which is a standard method to handle errors in codes that can only have _edge-
like_ errors (namely, elementary errors violate at most two checks). Matching-
based decoders can operate both efficiently and near-optimally, and are
readily adapted to handle noisy syndrome extraction circuits. In color codes,
an elementary error, which is a single-qubit $X$ or $Z$ error, is generally
involved in three checks (or stabilizer generators), and so a matching decoder
cannot directly be used. Moreover, considering realistic circuit-level noise
makes decoding more difficult because the color code syndrome extraction
circuits are more complex than for the surface code. As a result of these
deficiencies, existing decoders for the color code do not perform as well as
expected either in terms of error thresholds or for sub-threshold scaling of
the logical failure rate.

Several approaches to decode errors in color codes have been proposed. The
most widely studied methods are the projection decoder and its variants [12,
13, 14, 15, 16], which apply minimum-weight perfect matching (MWPM) on two or
three restricted lattices (which are specific sub-lattices of the dual lattice
of the color code) and then deduce the final correction by a procedure called
‘lifting’. These approaches can achieve thresholds of around 8.7% for bit-flip
noise [12] and around 0.47% for circuit-level noise [16]. However, they have a
fundamental limitation that the logical failure rate $p_{\mathrm{fail}}$
scales like $p^{d/3}$ below threshold [14, 17, 16], not $p^{d/2}$, where $p$
is a physical noise strength and $d$ is the code distance. This is because
there exist errors with weights $O(d/3)$ that are uncorrectable via the
decoder (noting that, in principle, an optimal decoder can correct any error
with weight up to $d/2$). Such a drawback may significantly hinder resource
efficiency of quantum computing, necessitating a larger code distance to
maintain the same logical failure rate, compared to a scenario using a decoder
with the expected optimal scaling of $p^{d/2}$. Roughly speaking, it demands
$9/4$ times as many qubits if other factors are the same.

The Möbius MWPM decoder [17] is another matching-based decoder processed by
applying the MWPM algorithm on a manifold built by connecting the three
restricted lattices, which has the topology of a Möbius strip. It achieves a
higher threshold of 9.0% under bit-flip noise and, more importantly, a better
scaling of $p_{\mathrm{fail}}\sim p^{3d/7}$. The decoder has subsequently been
improved to accommodate circuit-level noise and general color-code lattices
[18].

Besides these matching-based decoders, there are tensor network decoders
(achieving a threshold of 10.9% under bit-flip noise) [19], simulated
annealing (10.4%) [20], MaxSAT problem (10.1%) [21], trellis (10.1%) [22],
neural network (10.0%) [23], union-find (8.4%) [24], and renormalization group
(7.8%) [25]. All of these reported thresholds are for the 6-6-6 (or hexagonal)
color-code lattice except that of the decoder based on simulated annealing
[20], which is for the 4-8-8 lattice. However, it is currently unclear how
these decoders can be adapted to circuit-level noise and how their performance
will be. We note that the tensor network decoder can be adapted to treat noisy
syndrome measurements in a phenomenological or circuit-level noise model, but
it is highly inefficient due to the difficulty of 3D tensor network
contraction [26].

In this work, we propose a matching-based color-code decoder, which we call
the _concatenated MWPM decoder_ , that demonstrates exceptional sub-threshold
scaling of the logical failure rate in regimes of interest for fault-tolerant
quantum computing. Our decoder functions by ‘concatenation’ of two MWPM
decoders per color, for a total of six matchings. Roughly speaking, this
decoder is based on the idea that decoding syndrome on a specific (say, red)
restricted lattice returns a prediction of red edges with odd-parity errors,
which can be combined with the syndrome data of red checks (specifying red
faces with odd-parity errors) and decoded again to predict errors. This
process is repeated for each of the three colors and the most probable
prediction is selected as the final prediction. We demonstrate that this
decoder can be generalized to handle circuit-level noise by using the concept
of _detector error model_. This approach to color-code decoding was inspired
by a decoding approach for measurement-based quantum computing [27], and here
we develop and generalize it further for gate-based quantum computing.

We analyze the performance of the concatenated MWPM decoder against bit-flip
and circuit-level noise models by evaluating its noise thresholds and
investigating the sub-threshold scaling of logical failure rates. Notably, the
logical failure rates of the concatenated MWPM decoder below threshold is
shown to be well-described by the scaling $p_{\mathrm{fail}}\sim p^{d/2}$ for
both of the noise models within the range of our simulations ($d\leq 31$ for
bit-flip noise and $d\leq 21$ for circuit-level noise). Thanks to this
improvement, although it has comparable or slightly lower thresholds (8.2% for
bit-flip noise and 0.46% for circuit-level noise), its sub-threshold
performance significantly surpasses the projection decoder. Compared to the
Möbius decoder, our decoder has a similar scaling factor against $d$ but
achieves approximately 3–7 times lower logical failure rates for circuit-level
noise when $10^{-4}\lessapprox p\lessapprox 5\times 10^{-4}$.

A python module for simulating color code circuits and running the
concatenated MWPM decoder is publicly available on Github [28].

This paper is structured as follows: In Sec. 2, we provide a brief overview of
color codes and their decoding problem, and describe our methodology of
analysis including the settings, noise models, and criteria for evaluating
decoder performance. In Sec. 3, we introduce the 2D variant of the
concatenated MWPM decoder that works when syndrome measurements are perfect
and analyze it numerically for bit-flip noise. In Sec. 4, we generalize the
decoder by using detector error models to accommodate circuit-level noise
including faulty syndrome measurements and present the outcomes of its
numerical analyses as well. We conclude with final remarks in Sec. 5.

##  2 Preliminaries

###  2.1 Color codes

Figure 1:  Example of a triangular color code and its restricted lattice. (a)
The triangular color code with code distance $d=7$ based on a hexagonal
lattice with three boundaries of different colors is displayed. Each hexagonal
face is associated with a pair of $Z$-type and $X$-type checks, exemplified by
$S_{f_{\texttt{r}}}^{Z}$ on a red face and $S_{f_{\texttt{b}}}^{X}$ on a blue
face, respectively. Logical operators $X_{L}$ and $Z_{L}$ can be supported on
one of the three boundaries. Each edge is colored by the color of the faces
connected by it, as exemplified by the red edge highlighted. (b) The red-
restricted lattice of the code is illustrated, where vertices and edges are
shown as circles and purple lines, respectively. Its vertices consist of blue
faces (blue circles), green faces (green circles), and an additional boundary
vertex $v_{\mathrm{bdry}}$ (purple circle). Each of its edges corresponds to a
red edge of the original lattice, which are highlighted as thick red lines.

A 2D color-code lattice indicates a lattice satisfying the following two
conditions:

  * •

3-valent: Each vertex is connected with three edges.

  * •

3-colorable: One of three colors can be assigned to each face in a way that
adjacent faces do not have the same color.

Following the usual convention, we use red (r), green (g), and blue (b) as
these three colors assigned to faces. Note that each edge is also colorable by
the color of the faces that it connects. There are various types of color-code
lattices, among which hexagonal (or 6-6-6) lattices are used to test the
concatenated MWPM decoder in this work. Nonetheless, since our decoder is
described in a form that does not depend on the lattice type, it can also be
applied to other color-code lattices such as 4-8-8 lattices [29].

Given a 2D color-code lattice, a 2D color code [1] is defined on qubits placed
at the vertices of the lattice. The code space of the color code is stabilized
by two types of _checks_ $S_{f}^{X}$ and $S_{f}^{Z}$ for each face $f$, which
are defined as

$\displaystyle S_{f}^{X}\coloneqq\prod_{v\in f}X_{v},\qquad
S_{f}^{Z}\coloneqq\prod_{v\in f}Z_{v},$ (1)

where $X_{v}$ and $Z_{v}$ are the Pauli-X and Z operators on the qubit placed
at $v$ and the notation ‘$v\in f$’ means that the vertex $v$ is included in
$f$. In other words, the code space is the common $+1$ eigenspace of these
operators. We categorize checks according to their Pauli types and the colors
of the corresponding faces; for example, if $f$ is a red face, $S_{f}^{X}$
($S_{f}^{Z}$) is a red $X$-type ($Z$-type) check.

To define a single logical qubit with a color code, we can use a triangular
patch possessing three boundaries of different colors, as shown in Fig. 1(a)
for the code distance of $d=7$ with several examples of its checks and
logical-$Z$ operator. Here, we say that a boundary has a specific color (e.g.,
red) if and only if it is adjacent to only faces of other two colors (e.g.,
green and blue). In addition, an edge connecting a boundary and a face is
regarded to have the same color as them. The logical Pauli-$X$ ($Z$) operator,
denoted as $\overline{X}$ ($\overline{Z}$), is defined as the product of $X$
($Z$) operators on qubits placed along one of the three boundaries. The weight
of each of these logical Pauli operators is the code distance of the code.

###  2.2 Decoding problem

For detecting and correcting errors, the checks of Eq. (1) are measured,
repeatedly. These measurements consist of multiple rounds, each round being a
subroutine to measure all the commuting checks in parallel without duplication
(see Sec. 4.1 for the circuit implementing this). Each measurement outcome of
a check is referred to as a _check outcome_ and, if it is $-1$, we say that
the check is _violated_. The collection of check outcomes of a single round is
called a _syndrome_.

_Decoding_ is the process of predicting errors from syndromes of a single or
multiple rounds. If the residual errors after decoding incurs a logical error,
we say that the decoding fails. Ideal decoding using maximum likelihood is
generally known to be #P-complete [30], thus alternative decoders that are
less precise but more efficient are necessary for practical quantum computing.
For Calderbank-Shor-Steane (CSS) codes where $X$-type and $Z$-type checks are
separately defined, these two types of checks can be decoded independently by
regarding $Y$ errors as combinations of $X$ and $Z$ errors.

Assuming that syndrome measurements are perfect, meaning each check outcome is
obtained without error, the minimum-weight perfect matching (MWPM) algorithm
[31] can be used directly for decoding Pauli errors on data qubits when each
of elementary Pauli errors (which typically consist of the Pauli-$X$ and $Z$
operators of all data qubits) anticommutes with at most two checks of the
code. This is the situation for surface codes [3]. In such a case, we consider
a _matching graph_ $G_{\mathrm{mat}}=(V,E)$ whose vertices $V$ consist of
checks and an additional ‘boundary vertex’ $v_{\mathrm{bdry}}$. For each
elementary error $P$, two checks anticommuting with $P$ (or
$v_{\mathrm{bdry}}$ and a single check anticommuting with $P$) are connected
within $G_{\mathrm{mat}}$. A weight is assigned to each edge either uniformly
or as $\log[(1-q)/q]$, where $q$ is the probability of the corresponding
error. Denoting the set of violated checks as $\sigma$, the MWPM algorithm
identifies a minimal-total-weight set of edges, denoted as
$\operatorname{MWPM}\quantity(\sigma;G_{\mathrm{mat}},v_{\mathrm{bdry}})$,
that meet each violated check an odd number of times and each unviolated check
an even number of times. In other words,
$E_{\mathrm{MWPM}}\coloneqq\operatorname{MWPM}\quantity(\sigma;G_{\mathrm{mat}},v_{\mathrm{bdry}})\subset
E$ satisfies

$\displaystyle\forall v\in\sigma,\;\absolutevalue{\quantity{e\in
E_{\mathrm{MWPM}}\mid v\in e}}\equiv 1\pmod{2},$ $\displaystyle\forall v\in
V\setminus\quantity(\sigma\cup\quantity{v_{\mathrm{bdry}}}),\;$
$\displaystyle\qquad\absolutevalue{\quantity{e\in E_{\mathrm{MWPM}}\mid v\in
e}}\equiv 0\pmod{2}$

and have the smallest sum of weights. The final prediction is then the set of
elementary errors corresponding to the edges in $E_{\mathrm{MWPM}}$.

However, the above method is not applicable to color codes since each of the
Pauli-$X$ and $Z$ operators of their physical qubits can anticommute with
three checks. To obviate this problem, we can instead consider three
_restricted lattices_ visualized in Fig. 1(b), which are derived from the
color-code lattice $\mathcal{L}_{\mathrm{2D}}$ as follows: The red-restricted
lattice $\mathcal{L}_{\neg\texttt{r}}^{*}$ contains the green and blue faces
and an additional ‘boundary vertex’ $v_{\mathrm{bdry}}$ as its vertices and,
for each red edge $e^{(\texttt{r})}$ of $\mathcal{L}_{\mathrm{2D}}$, the green
and blue faces divided by $e^{(\texttt{r})}$ (or $v_{\mathrm{bdry}}$ and $f$
if $e^{(\texttt{r})}$ belongs to only one face $f$) are connected within
$\mathcal{L}_{\neg\texttt{r}}^{*}$ by an edge.111In the literature, the
restricted lattice is more often defined to have two boundary vertices
(connected with each other), which respectively correspond to two among the
three boundaries except the boundary of the restricted color. Although it may
be mathematically more natural, it is not necessary for MWPM since the edge
between the two boundary vertices is regarded to have zero weight. See
Appendix A.3 for more details. The green- and blue-restricted lattices
$\mathcal{L}_{\neg\texttt{g}}^{*}$, $\mathcal{L}_{\neg\texttt{b}}^{*}$ are
defined analogously. Importantly, any single-qubit $X$ and $Z$ errors
respectively affect checks on at most two vertices in each restricted lattice.
Therefore, we can apply MWPM on (all or some of) these three restricted
lattices individually and combine these outcomes through a specific method,
which is the basic idea of the projection decoder [12]. Alternatively, MWPM
can be performed on a manifold built by connecting the three restricted
lattices appropriately as in the Möbius MWPM decoder [17]. In this work, we
take another approach to perform MWPM twice in a concatenated way, where the
first one is applied on a restricted lattice but the second one is applied on
another useful lattice derived from $\mathcal{L}_{\mathrm{2D}}$ in a different
way.

We note that we have assumed perfect syndrome extraction in the above
discussions. If syndrome extraction is noisy, we can generally employ detector
error models [32], which will be elaborated on in Sec. 4.

###  2.3 Noise models and settings

We consider one of the two types of noise models: bit-flip and circuit-level
noise models. In the bit-flip noise model of strength $p$, every data qubit
undergoes an $X$ error with probability $p$ at the start of each round. There
are no errors in other steps including initialization and measurement. A more
sophisticated noise model is the circuit-level noise model of strength $p$,
defined as follows:

  * •

Every measurement outcome is flipped with probability $p$.

  * •

Every preparation of a qubit produces an orthogonal state with probability
$p$.

  * •

Every single- or two-qubit unitary gate (including the idle gate $I$) is
followed by a single- or two-qubit depolarizing noise channel of strength $p$.
We here regard that, for every time slice of the circuit, idle gates $I$ are
acted on all the qubits that are not involved in any non-trivial unitary gates
or measurements.

Here, the single- and two-qubit depolarizing channels of strength $p$ are
respectively defined as

$\displaystyle\mathcal{E}_{p}^{(1)}:\;\rho^{(1)}\mapsto(1-p)\rho^{(1)}+\frac{p}{3}\sum_{P\in\quantity{X,Y,Z}}P\rho^{(1)}P,$
$\displaystyle\mathcal{E}_{p}^{(2)}:\;\rho^{(2)}\mapsto(1-p)\rho^{(2)}+\frac{p}{15}$
$\displaystyle\qquad\quad\times\sum_{\begin{subarray}{c}P_{1},P_{2}\in\quantity{I,X,Y,Z}\\\
P_{1}\otimes P_{2}\neq I\otimes I\end{subarray}}\quantity(P_{1}\otimes
P_{2})\rho^{(2)}\quantity(P_{1}\otimes P_{2}),$

where $\rho^{(1)}$ and $\rho^{(2)}$ are arbitrary single- and two-qubit
density matrices, respectively.

To evaluate the performance of our decoder, we simulate $T$ rounds of the
logical idling gate acting on the triangular color code of code distance $d$,
which is preceded by logical initialization (to the $+1$ eigenstate
$\ket{\overline{0}}$ of $\overline{Z}$) and followed by a measurement in the
$\overline{Z}$ basis. The logical initialization and measurement are done by
initializing all the data qubits to $\ket{0}$ and measuring them in the $Z$
basis, respectively. From this scenario, we can identify whether the
$\overline{Z}$ observable fails (i.e., a $\overline{X}$ or $\overline{Y}$
error occurs) during the idling gate. While it is sufficient for bit-flip
noise models, the $\overline{X}$ observable also can fail under circuit-level
noise models. To cover this, we simulate again by swapping the $X$\- and
$Z$-type parts from the cnot schedule (see Sec. 4.3 for more details). The
logical failure rate $p_{\mathrm{fail}}$ is computed as
$p_{\mathrm{fail}}=p_{\mathrm{fail}}^{(X)}+p_{\mathrm{fail}}^{(Z)}-p_{\mathrm{fail}}^{(X)}p_{\mathrm{fail}}^{(Z)}$,
where $p_{\mathrm{fail}}^{(X)}$ and $p_{\mathrm{fail}}^{(Z)}$ are respectively
the failure rates of the $\overline{X}$ and $\overline{Z}$ observables, by
assuming that these two observables fail independently.

###  2.4 Assessment of decoder performance

We assess the performance of the decoder from two perspectives: (i) what the
noise threshold $p^{\times}_{\mathrm{}}$ of the decoder is and (ii) how the
logical failure rate behaves when the noise strength $p$ is well below the
threshold (namely, $p\lessapprox p^{\times}_{\mathrm{}}/2$).

For a given value of $T$, the (cross) noise threshold
$p^{\times}_{\mathrm{}}(T)$ is defined by the noise strength at which the
curves of the logical failure rates $p_{\mathrm{fail}}$ for different code
distances (which are sufficiently large) cross each other. We also define the
_long-term cross threshold_ as
$p^{\times,\mathrm{LT}}_{\mathrm{}}\coloneqq\lim_{T\rightarrow\infty}p^{\times}_{\mathrm{}}(T)$
and predict it by fitting data into the ansatz

$\displaystyle
p^{\times}_{\mathrm{}}(T)=p^{\times,\mathrm{LT}}_{\mathrm{}}\quantity[1-\quantity(1-\frac{p^{\times}_{\mathrm{}}(1)}{p^{\times,\mathrm{LT}}_{\mathrm{}}})T^{-\gamma}],$
(2)

following the method used in Ref. [14].

To investigate the sub-threshold scaling, we fit data into the ansatz

$\displaystyle\frac{p_{\mathrm{fail}}}{T}=\alpha\quantity(\frac{p}{p^{\star}_{\mathrm{}}})^{\beta\quantity(d-d_{0})+\eta}$
(3)

with five parameters $p^{\star}_{\mathrm{}}$, $\alpha$, $\beta$, $\eta$ and
$d_{0}$, where $d_{0}$ is a number determined appropriately to minimize the
uncertainties of $\alpha$ and $\eta$. Equation (3) can be equivalently written
as

$\displaystyle\log\quantity(\frac{p_{\mathrm{fail}}}{T})=G(d)\log p+C(d),$ (4)

where

$\displaystyle G(d)$ $\displaystyle=\beta(d-d_{0})+\eta,$ $\displaystyle C(d)$
$\displaystyle=-(\beta\log
p^{\star}_{\mathrm{}})(d-d_{0})+\quantity(\log\alpha-\eta\log
p^{\star}_{\mathrm{}}).$

Hence, we can determine these parameters by two steps of linear regressions:
first computing $G(d)$ and $C(d)$ by fitting $\log(p_{\mathrm{fail}}/T)$
against $\log p$ for each $d$ and then fitting $G(d)$ and $C(d)$ against $d$,
respectively. We select $d_{0}$ such that the uncertainties of the constant
terms (i.e., $\eta$ and $\log\alpha-\eta\log p^{\star}_{\mathrm{}}$) of $G(d)$
and $C(d)$ are minimized. (If such values of $d_{0}$ differ for $G(d)$ and
$C(d)$, select their average.)

Since $p_{\mathrm{fail}}/T$ is expected to be constant when
$p=p^{\star}_{\mathrm{}}$, we regard $p^{\star}_{\mathrm{}}$ as a ‘noise
threshold’ as well. To distinguish the two types of thresholds
$p^{\times}_{\mathrm{}}$ and $p^{\star}_{\mathrm{}}$, we refer to them as the
_cross threshold_ and _scaling threshold_ , respectively. Additionally, we
specify the noise model (bit-flip or circuit-level) on the subscripts of the
thresholds such as $p^{\times}_{\mathrm{bitflip}}$,
$p^{\times}_{\mathrm{circuit}}$, $p^{\star}_{\mathrm{bitflip}}$, and
$p^{\star}_{\mathrm{circuit}}$.

##  3 Concatenated MWPM decoder without faulty measurements

Figure 2:  Example of executing the concatenated MWPM decoder on the
triangular color code of distance 7. (a) First-round MWPM is performed on the
red-restricted lattice $\mathcal{L}_{\neg\texttt{r}}^{*}$, where the vertices
are the green and blue faces of the original lattice
$\mathcal{L}_{\mathrm{2D}}$ (marked as green and blue empty/filled circles)
and a boundary vertex $v_{\mathrm{bdry}}$ (marked as a purple filled circle)
connected by purple solid lines. The green/blue faces with violated checks are
highlighted as green/blue filled circles. The obtained matching is drawn as
purple thick lines, which correspond to a set of red edges
$E_{\mathrm{pred}}^{(\texttt{r})}$. (b) Second-round MWPM is performed on the
red-only lattice $\mathcal{L}_{\texttt{r}}^{*}$, where the vertices are the
red faces and edges of $\mathcal{L}_{\mathrm{2D}}$ and a boundary vertex
$v_{\mathrm{bdry}}$ (marked as red empty/filled circles) connected by red
lines. The red edges in $E_{\mathrm{pred}}^{(\texttt{r})}$ and the red faces
with violated checks are highlighted as red filled circles. The obtained
matching is drawn as red thick lines, which corresponds to a set of vertices
$V_{\mathrm{pred}}^{(\texttt{r})}$ predicted to have errors. (c) Residual
errors after correcting $V_{\mathrm{pred}}^{(\texttt{r})}$ are marked as black
dots, which is equivalent to a stabilizer. The above process is repeated two
more times while varying colors and the smallest one among
$V_{\mathrm{pred}}^{(\texttt{r})}$, $V_{\mathrm{pred}}^{(\texttt{g})}$, and
$V_{\mathrm{pred}}^{(\texttt{b})}$ is selected as the outcome.

In this section, we describe the 2D variant of the concatenated MWPM decoder
that is applicable only when every syndrome measurement is perfect. Let us
consider the 2D color code on a lattice $\mathcal{L}_{\mathrm{2D}}$, which may
have boundaries. The decoder to predict $X$ errors in a single round can be
briefly depicted as follows (see Fig. 2 for an example):

  1. 1.

(First-round MWPM) Input violated blue and green $Z$-type checks to the MWPM
algorithm on the red-restricted lattice $\mathcal{L}_{\neg\texttt{r}}^{*}$,
which returns a set of edges of $\mathcal{L}_{\neg\texttt{r}}^{*}$. This set
corresponds to a set $E_{\mathrm{pred}}^{(\texttt{r})}$ of red edges of
$\mathcal{L}_{\mathrm{2D}}$, each of which is predicted to contain one $X$
error. See Fig. 2(a).

  2. 2.

(Second-round MWPM) Input $E_{\mathrm{pred}}^{(\texttt{r})}$ and violated red
$Z$-type checks to the MWPM algorithm on the ‘red-only lattice’
$\mathcal{L}_{\texttt{r}}^{*}$, which is constructed according to the
connection structure of red edges and faces in $\mathcal{L}_{\mathrm{2D}}$.
The algorithm returns a set of edges of $\mathcal{L}_{\texttt{r}}^{*}$, which
correspond to a set of vertices $V_{\mathrm{pred}}^{(\texttt{r})}$ of
$\mathcal{L}_{\mathrm{2D}}$ that are predicted to have errors. See Fig. 2(b).

  3. 3.

Repeat the above two steps (together referred to as the red sub-decoding
procedure) while varying the color to green and blue, obtaining
$V_{\mathrm{pred}}^{(\texttt{g})}$ and $V_{\mathrm{pred}}^{(\texttt{b})}$.
Select the smallest one $V_{\mathrm{pred}}$ among
$V_{\mathrm{pred}}^{(\texttt{r})}$, $V_{\mathrm{pred}}^{(\texttt{g})}$, and
$V_{\mathrm{pred}}^{(\texttt{b})}$ as the final outcome.

Figure 2(c) presents a set of residual errors after correction, which is
equivalent to a stabilizer thus does not cause a logical failure. $Z$ errors
can be predicted by decoding $X$-type check outcomes in an analogous way.

To formally describe the above procedure, let us first define some notations.
For a lattice $\mathcal{L}$, the sets of its vertices, edges, and faces are
respectively denoted as $\Delta_{0}\quantity(\mathcal{L})$,
$\Delta_{1}\quantity(\mathcal{L})$, and $\Delta_{2}\quantity(\mathcal{L})$.
For each color $\texttt{c}\in\quantity{\texttt{r},\texttt{g},\texttt{b}}$, we
denote the sets of c-colored edges and faces in $\mathcal{L}_{\mathrm{2D}}$ as
$\Delta_{1}^{(\texttt{c})}\quantity(\mathcal{L}_{\mathrm{2D}})$ and
$\Delta_{2}^{(\texttt{c})}\quantity(\mathcal{L}_{\mathrm{2D}})$. The set of
faces with violated $Z$-type checks is denoted as
$\sigma_{Z}\in\Delta_{2}\quantity(\mathcal{L})$. We partition $\sigma_{Z}$
into
$\sigma_{Z}=\sigma_{Z}^{(\texttt{r})}\cup\sigma_{Z}^{(\texttt{g})}\cup\sigma_{Z}^{(\texttt{b})}$
such that
$\sigma_{Z}^{(\texttt{c})}\subseteq\Delta_{2}^{(\texttt{c})}\quantity(\mathcal{L}_{\mathrm{2D}})$
for each $\texttt{c}\in\quantity{\texttt{r},\texttt{g},\texttt{b}}$. The
restricted and monochromatic lattices are then formally defined as follows:

######  Definition 1 (Restricted lattices).

The _red-restricted lattice_ $\mathcal{L}_{\neg\texttt{r}}^{*}$ is defined to
have vertices of
$\Delta_{0}\quantity(\mathcal{L}_{\neg\texttt{r}}^{*})=\Delta_{2}^{(\texttt{g})}\quantity(\mathcal{L}_{\mathrm{2D}})\cup\Delta_{2}^{(\texttt{b})}\quantity(\mathcal{L}_{\mathrm{2D}})\cup\quantity{v_{\mathrm{bdry}}}$,
where $v_{\mathrm{bdry}}$ is an additional boundary vertex. For each red edge
$e\in\Delta_{1}^{(\texttt{r})}\quantity(\mathcal{L}_{\mathrm{2D}})$, we create
an edge denoted as $\epsilon_{\neg\texttt{r}}(e)$ within
$\mathcal{L}_{\neg\texttt{r}}^{*}$ as follows: If $e$ belongs to two faces
$f_{\texttt{g}}\in\Delta_{2}^{(\texttt{g})}\quantity(\mathcal{L}_{\mathrm{2D}})$
and
$f_{\texttt{b}}\in\Delta_{2}^{(\texttt{b})}\quantity(\mathcal{L}_{\mathrm{2D}})$,
$\epsilon_{\neg\texttt{r}}(e)$ connects $f_{\texttt{g}}$ and $f_{\texttt{b}}$.
If $e$ belongs to only one face
$f\in\Delta_{2}^{(\texttt{g})}\quantity(\mathcal{L}_{\mathrm{2D}})\cup\Delta_{2}^{(\texttt{b})}\quantity(\mathcal{L}_{\mathrm{2D}})$,
$\epsilon_{\neg\texttt{r}}(e)$ connects $f$ and $v_{\mathrm{bdry}}$. Note that
$\epsilon_{\neg\texttt{r}}$ is a bijection between
$\Delta_{1}^{(\texttt{r})}\quantity(\mathcal{L}_{\mathrm{2D}})$ and
$\Delta_{1}\quantity(\mathcal{L}_{\neg\texttt{r}}^{*})$. For
$E\subseteq\Delta_{1}^{(\texttt{r})}\quantity(\mathcal{L}_{\mathrm{2D}})$, we
denote
$\epsilon_{\neg\texttt{r}}(E)\coloneqq\quantity{\epsilon_{\neg\texttt{r}}(e)\mid
e\in E}$. The green- and blue-restricted lattices
$\mathcal{L}_{\neg\texttt{g}}^{*}$, $\mathcal{L}_{\neg\texttt{b}}^{*}$ (with
bijections $\epsilon_{\neg\texttt{g}}$ and $\epsilon_{\neg\texttt{b}}$) are
defined similarly.

######  Definition 2 (Monochromatic lattices).

The _red-only lattice_ $\mathcal{L}_{\texttt{r}}^{*}$ is defined to have
vertices of
$\Delta_{0}\quantity(\mathcal{L}_{\texttt{r}}^{*})=\Delta_{1}^{(\texttt{r})}\quantity(\mathcal{L}_{\mathrm{2D}})\cup\Delta_{2}^{(\texttt{r})}\quantity(\mathcal{L}_{\mathrm{2D}})\cup\quantity{v_{\mathrm{bdry}}}$,
where $v_{\mathrm{bdry}}$ is an additional boundary vertex. For each vertex
$v\in\Delta_{0}\quantity(\mathcal{L}_{\mathrm{2D}})$, we connect an edge
denoted as $\epsilon_{\texttt{r}}(v)$ within $\mathcal{L}_{\texttt{r}}^{*}$ as
follows: If $v$ is commonly included in a red edge
$e\in\Delta_{1}^{(\texttt{r})}\quantity(\mathcal{L}_{\mathrm{2D}})$ and a red
face $f\in\Delta_{2}^{(\texttt{r})}\quantity(\mathcal{L}_{\mathrm{2D}})$,
$\epsilon_{\texttt{r}}(v)$ connects $e$ and $f$. If $v$ is only included
either in a red face $f$ or in a red edge $e$, $\epsilon_{\texttt{r}}(v)$
connects $f$ or $e$ with $v_{\mathrm{bdry}}$. Note that
$\epsilon_{\texttt{r}}$ is a bijection between
$\Delta_{0}\quantity(\mathcal{L}_{\mathrm{2D}})$ and
$\Delta_{1}\quantity(\mathcal{L}_{\texttt{r}}^{*})$. For
$V\subseteq\Delta_{0}\quantity(\mathcal{L}_{\mathrm{2D}})$, we denote
$\epsilon_{\texttt{r}}(V)\coloneqq\quantity{\epsilon_{\texttt{r}}(v)\mid v\in
V}$. The green- and blue-only lattices $\mathcal{L}_{\texttt{g}}^{*}$,
$\mathcal{L}_{\texttt{b}}^{*}$ (with bijections $\epsilon_{\texttt{g}}$ and
$\epsilon_{\texttt{b}}$) are defined similarly.

Upon the above definitions, the decoding process can be formally described as
follows:

  1. 1.

For each $\texttt{c}\in\quantity{\texttt{r},\texttt{g},\texttt{b}}$, execute
the c-colored sub-decoding procedure as follows:

    1. (a)

Perform the MWPM algorithm to identify a set
$\widetilde{E}_{\mathrm{pred}}^{(\texttt{c})}\coloneqq\operatorname{MWPM}\quantity(\sigma_{Z}^{(\texttt{c}_{1})}\cup\sigma_{Z}^{(\texttt{c}_{2})};\mathcal{L}_{\neg\texttt{c}}^{*},v_{\mathrm{bdry}})\subseteq\Delta_{1}\quantity(\mathcal{L}_{\neg\texttt{c}}^{*})$,
where $\texttt{c}_{1}$ and $\texttt{c}_{2}$ are the other two colors besides
c. Define
$E_{\mathrm{pred}}^{(\texttt{c})}\coloneqq\epsilon_{\neg\texttt{r}}^{-1}\quantity(\widetilde{E}_{\mathrm{pred}}^{(\texttt{c})})\in\Delta_{1}^{(\texttt{c})}\quantity(\mathcal{L}_{\mathrm{2D}})$.

    2. (b)

Perform the MWPM algorithm to identify a set
$\widetilde{V}_{\mathrm{pred}}^{(\texttt{c})}\coloneqq\operatorname{MWPM}\quantity(\sigma_{Z}^{(\texttt{c})}\cup
E_{\mathrm{pred}}^{(\texttt{c})};\mathcal{L}_{\texttt{c}}^{*},v_{\mathrm{bdry}})\subseteq\Delta_{1}\quantity(\mathcal{L}_{\texttt{c}}^{*})$
and define
$V_{\mathrm{pred}}^{(\texttt{c})}\coloneqq\epsilon_{\texttt{r}}^{-1}\quantity(\widetilde{V}_{\mathrm{pred}}^{(\texttt{c})})\in\Delta_{0}\quantity(\mathcal{L}_{\mathrm{2D}})$

  2. 2.

Return the smallest one $V_{\mathrm{pred}}$ among
$V_{\mathrm{pred}}^{(\texttt{r})}$, $V_{\mathrm{pred}}^{(\texttt{g})}$, and
$V_{\mathrm{pred}}^{(\texttt{b})}$.

In Appendix A, we formally prove that the above process always returns a valid
error prediction consistent with the syndrome. Additionally, we confirm that
any outcome obtained from the projection decoder is a valid matching for the
concatenated MWPM decoder, which implies that the former cannot outperform the
latter.

In Fig. 13 of Appendix C, we numerically verify that our color-selecting
strategy of executing the sub-decoding procedures for all the three colors and
selecting the best one is indeed necessary to maximize the performance of the
decoder. If only one or two colors are considered in this process, the failure
rate of the decoder significantly increases.

###  3.1 Performance analysis

To assess the performance of the decoder, we consider the setting in Sec. 2.3
under the bit-flip noise model of strength $p$. Since the bit-flip noise is
independently applied to each round, the cross threshold is invariant under
$T$, thus we simply denote $p^{\times}_{\mathrm{bitflip}}\coloneqq
p^{\times}_{\mathrm{bitflip}}(T)=p^{\times,\mathrm{LT}}_{\mathrm{bitflip}}$
and consider only the case of $T=1$. We employ the PyMatching library [33] to
run the MWPM algorithm.

Figure 3:  Numerical analysis of the concatenated MWPM decoder under bit-flip
noise. We consider a single round of QEC on a triangular patch with code
distance $d$ under the bit-flip noise model of strength $p$. The logical
failure rates $p_{\mathrm{fail}}$ are plotted over $p$ (a) near the threshold
and (b) in a sub-threshold region for various code distances
($d=3,5,7,\cdots,31$). In (a), the solid lines are the LOWESS regressions with
fraction $2/3$. The obtained cross threshold is
$p_{\mathrm{bitflip}}^{\times}=8.2\%$. In (b), the solid lines are the linear
regressions in the logarithmic scale, each of which is in the form of Eq. (4).
The 99% confidence intervals (CIs) of the regression estimates are depicted as
shaded regions around the solid lines. The number of samples for obtaining
each data point is selected so that the 99% CI of $p_{\mathrm{fail}}$ is $\pm
10^{-3}$ for (a) and $\pm 0.05p_{\mathrm{fail}}$ for (b). In (c), the 99% CIs
of $G(d)$ and $C(d)$ in Eq. (4) are plotted over $d$ with their linear
regressions. From the regression parameters, we obtain the parameters of the
ansatz of Eq. (3) as presented in Eq. (5).

In Fig. 3(a) and (b), we present the logical failure probabilities
$p_{\mathrm{fail}}$ computed for various code distances $d$ when $p$ is near
the threshold and when $p$ is sufficiently lower than the threshold,
respectively. From Fig. 3(a), we can clearly observe that the cross threshold
is $p^{\times}_{\mathrm{bitflip}}\approx 8.2\%$. In Fig. 3(b), the data points
are linearly fitted for each $d$ in the logarithmic scale, where the slopes
$G(d)$ and constant terms $C(d)$ are plotted over $d$ in Fig. 3(c). The
regression parameters of $G(d)$ and $C(d)$ are estimated as

$\displaystyle G(d)=(0.488\pm 0.006)(d-17)+(8.53\pm 0.05),$ $\displaystyle
C(d)=(1.30\pm 0.02)(d-17)+(20.6\pm 0.2),$

by selecting $d_{0}=17$, where the error terms are the 99% confidence
intervals (CIs) estimated based on Students’ $t$-distribution by using the
python module statsmodels [34]. The corresponding ansatz parameters in Eq. (3)
are estimated as

$\displaystyle\begin{split}&p^{\star}_{\mathrm{bitflip}}\approx
0.069,\quad\alpha\approx 0.12,\quad\beta\approx 0.49,\\\ &\eta\approx
8.5,\quad d_{0}=17.\end{split}$ (5)

Figure 4:  Comparison of three matching-based decoders under bit-flip noise.
Logical failure rates $p_{\mathrm{fail}}$ estimated from the ansatz of Eq. (3)
are plotted over $p$ for two code distances $d\in\quantity{15,31}$ and three
decoders: the concatenated (Concat.), projection (Proj.) [12, 14], and Möbius
MWPM decoders [17]. The parameter values used for the estimation are those in
Eq. (5) for the concatenated MWPM decoder,
$(p^{\star}_{\mathrm{bitflip}},\alpha,\beta,\eta,d_{0})=(0.087,0.1,1/3,2/3,0)$
for the projection decoder (estimated optimistically by assuming
$p^{\star}_{\mathrm{bitflip}}=p^{\times}_{\mathrm{bitflip}}$), and
$(p^{\star}_{\mathrm{bitflip}},\alpha,\beta,\eta,d_{0})=(0.0801,0.148,0.422,0.488,0)$
for the Möbius decoder (reported in Ref. [17]). The intersections of the
curves of the concatenated MWPM decoder and the other two decoders are
$3.12\%$ ($d=15$) and $3.69\%$ ($d=31$) for the projection decoder and
$2.31\%$ ($d=15$) and $2.52\%$ ($d=31$) for the Möbius decoder.

Although the obtained cross threshold $p^{\times}_{\mathrm{bitflip}}=8.2\%$ is
lower than 8.7% of the projection decoder [12] and 9.0% of Möbius decoder
[17], the concatenated MWPM decoder has a significant advantage in terms of
the scaling of the failure rate over $d$ and $p$. Namely, $\beta\approx 1/2$
for our decoder within our simulation range of $d\leq 31$, while $\beta\approx
1/3$ for the projection decoder [14] and $\beta\approx 3/7$ for the Möbius
decoder [17]. The impact of this improvement is numerically presented in Fig.
4, where logical failure rates $p_{\mathrm{fail}}$ are estimated using the
ansatz of Eq. (3) for these three decoders and two code distances
$d\in\quantity{15,31}$. The values of the parameters
$(p^{\star}_{\mathrm{bitflip}},\alpha,\beta,\eta,d_{0})$ that we use for the
estimation are $(0.087,0.1,1/3,2/3,0)$ for the projection decoder (which are
optimistically guessed by assuming
$p^{\star}_{\mathrm{bitflip}}=p^{\times}_{\mathrm{bitflip}}$) and
$(0.0801,0.148,0.422,0.488,0)$ for the Möbius decoder (which are reported in
Ref. [17]). We observe that the concatenated MWPM decoder outperforms the
other two decoders when $p\lessapprox 2\%\approx
p^{\times}_{\mathrm{bitflip}}/4$.

We note that the value of $\beta$ is closely related to the least-weight
uncorrectable errors; namely, a decoder may be able to correct any error of
weight smaller than $O(\beta d)$ for a color code with code distance $d$. The
projection decoder cannot correct specific types of errors with weights
$O(d/3)$ [14, 17], which are correctable via the concatenated MWPM decoder as
shown in Appendix B.1. Likewise, we can find weight-$O(3d/7)$ uncorrectable
errors for the Möbius decoder [17].

One may be led to guess that the concatenated MWPM decoder can correct any
error of weight smaller than $O(d/2)$. Surprisingly, however, there exist
uncorrectable errors with weights $O(3d/7)$ just as with the Möbius decoder,
as illustrated in Appendix B.2. Then how could we obtain $\beta\approx 1/2$
from the above numerical analysis? We speculate that small-weight
uncorrectable errors with weights $<O(d/2)$ may exist only when $d$ is
sufficiently large. As evidence, weight-$O(3d/7)$ uncorrectable errors of the
type described in Appendix B.2 exist only when $d\geq 25$. Hence, we
conjecture that $\beta$ may approach a limit of $3/7$ for sufficiently large
values of $d$, although its confirmation would demand extensive computational
resources. Nonetheless, the concatenated MWPM decoder is still beneficial
compared to the Möbius decoder, where $\beta$ is computed to be about $3/7$
even for small values of $d<25$. Note that Ref. [17] also suggests a
modification of the Möbius decoder that manually compares inequivalent
recovery operators, which is proved to correct every error with weight less
than $d/2$ when $d\leq 13$. This improvement has not been considered in Fig.
4.

An additional numerical analysis for bit-flip noise is presented in Fig. 13 of
Appendix C, showing that our strategy of comparing the outcomes from the sub-
decoding procedures of all the three colors is indeed effective compared to
performing only one or two sub-decoding procedures.

##  4 Generalized concatenated MWPM decoder for circuit-level noise

The bit-flip noise model considered in the previous section is adequate for
assessing basic performance features of decoders, but it does not represent
realistic noise that is relevant to fault-tolerant quantum computing. In
practice, syndrome measurements are not perfect. We thus need to modify our
decoder appropriately to accommodate circuit-level noise. We adapt our
concatenated MWPM decoder to a circuit-level noise model defined in Sec. 2.3
by using the concept of _detector error model_ (DEM) [32], which is a list of
independent error mechanisms. We generalize the three steps of the
concatenated MWPM decoder in Sec. 3 using DEMs and employ the _Stim_ library
[32] to implement and analyze the decoder.

###  4.1 Circuit and detectors

Figure 5:  Syndrome extraction circuit for color codes. (a) Circuits for
measuring checks on hexagonal faces, which are composed of multiple cnot
gates. The left (right) circuit followed by a $Z$ ($X$) measurement on the
center ancillary qubit measures the $Z$-type ($X$-type) checks. Twelve
variables $a,b,\cdots,l$ are positive integers specifying the time slices that
the corresponding cnot gates are applied. (b) Faces located along the
boundaries and corresponding time-slice variables of the cnot gates, colored
in purple (orange) for the measurements of $Z$-type ($X$-type) checks. The
syndrome extraction circuits are in the same form as (a), and are therefore
omitted from the figure for simplicity.

We first need to clarify the circuit implementing a color code, especially its
syndrome extraction. We suppose that each face of the lattice contains two
ancillary qubits (referred to as $Z$-type and $X$-type ancillary qubits),
which are respectively used to extract the measurement outcomes of the
$Z$-type and $X$-type checks on the face. We consider the scenario of $T$
rounds of the logical idling gate with logical initialization and measurement,
as described in Sec. 2.3.

In each round of syndrome extraction, $Z$-type ($X$-type) ancillary qubits are
first initialized to $\ket{0}$ ($\ket{+}$), followed by cnot gates between the
ancillary and data qubits, concluding with the $Z$-basis ($X$-basis)
measurement of the ancilla. The arrangement of these cnot gates are presented
in Fig. 5(a), where the left (right) circuit followed by a $Z$ ($X$)
measurement on the center $Z$-type ($X$-type) ancillary qubit measures the
$Z$-type ($X$-type) check on the face. We have a degree of freedom on choosing
the cnot schedule (i.e., the order of applying these cnot gates), which will
be discussed later in Sec. 4.3.

We group the operations in the circuit in a way that each group (called a
_time slice_) is composed of consecutive operations applied on distinct qubits
that can be performed simultaneously. As stated in Sec. 2.3, we regard that,
in each time slice, idle gates $I$ are applied on all the qubits that are not
involved in any non-trivial operations.

Let $m_{f,Z}^{(t)},m_{f,X}^{(t)}\in\quantity{\pm 1}$ denote the measurement
outcomes of the $Z$-type and $X$-type ancillary qubits, respectively, of a
face $f$ in the $t$-th round, where $1\leq t\leq T$. We also define
$\widetilde{m}_{v}\in\quantity{\pm 1}$ as the final measurement outcome of the
data qubit located at a vertex $v$. For every face $f$ and every pair of
integers $t\in\quantity{1,2,\cdots,T+1}$ and $s\in\quantity{2,3,\cdots,T}$,
the values

$\displaystyle D_{f,Z}^{(t)}$
$\displaystyle\coloneqq\begin{cases}m_{f,Z}^{(1)}&\text{if }t=1,\\\\[5.0pt]
m_{f,Z}^{(t-1)}m_{f,Z}^{(t)}&\text{if }2\leq t\leq T,\\\\[5.0pt]
m_{f,Z}^{(T)}\prod_{v\in f}\widetilde{m}_{v}&\text{if }t=T+1,\end{cases}$ (6a)
$\displaystyle D_{f,X}^{(s)}$ $\displaystyle\coloneqq
m_{f,X}^{(s-1)}m_{f,X}^{(s)},$ (6b)

must be $+1$ when there are no errors. We refer to these values as _detectors_
and classify them by their Pauli types and the colors of the faces; for
example, $D_{f,Z}^{(t)}$ is a red $Z$-type detector if $f$ is a red face. If a
detector is $-1$, we say it is violated.

Lastly, the final measurement of the logical-$Z$ operator always has an
outcome of $+1$ when there are no errors. Thus, if
$V_{\mathrm{bdry}}^{(\texttt{r})}$ is defined by the set of the vertices
placed along the red boundary, the value

$\displaystyle L_{Z}=\prod_{v\in
V_{\mathrm{bdry}}^{(\texttt{r})}}\widetilde{m}_{v}$ (7)

must be $+1$ when there are no errors. We refer to $L_{Z}$ as the _logical
observable_ of our scenario. After decoding, a correction
$L_{Z}^{(\mathrm{corr})}$ is obtained and the decoding succeeds if and only if
$L_{Z}=L_{Z}^{(\mathrm{corr})}$.

###  4.2 Generalization of the concatenated MWPM decoder

A _detector error model_ (DEM) is defined by a set of independent error
mechanisms. Each error mechanism, which is formally described as a 3-tuple
$(q,\mathcal{D},\mathcal{O})$, specifies the probability ($q$) that the error
occurs and the set of detectors ($\mathcal{D}$) and logical observables
($\mathcal{O}$) flipped by the error. The elements of
$\mathcal{D}\cup\mathcal{O}$ are referred to as the _targets_ of the error
mechanism. We say that an error mechanism $(q,\mathcal{D},\mathcal{O})$ is
_edge-like_ if and only if $\absolutevalue{\mathcal{D}}\leq 2$.

The Stim library [32] can be used to extract a DEM from a noise Clifford
circuit (which is composed of Clifford gates, Pauli
initializations/measurements, and Pauli noise channels) provided that
detectors and logical observables are annotated appropriately. It works as
follows: If the circuit has a single-Pauli error channel
$\mathcal{E}_{q}^{(P)}$, which applies a specific Pauli product operator $P$
with probability $q$, we can get its effect by commuting $P$ to the end of the
circuit and checking the detectors and logical observables flipped by it. If
the circuit has a depolarizing channel $\mathcal{E}_{p}^{(1)}$ or
$\mathcal{E}_{p}^{(2)}$, we can convert it into a sequence of single-Pauli
error channels as

$\displaystyle\mathcal{E}_{p}^{(1)}$
$\displaystyle=\mathcal{E}_{q_{1}}^{(X)}\circ\mathcal{E}_{q_{1}}^{(Y)}\circ\mathcal{E}_{q_{1}}^{(Z)},$
$\displaystyle\mathcal{E}_{p}^{(2)}$
$\displaystyle=\mathcal{E}_{q_{2}}^{(X\otimes
I)}\circ\mathcal{E}_{q_{2}}^{(X\otimes X)}\circ\mathcal{E}_{q_{2}}^{(X\otimes
Y)}\circ\cdots\circ\mathcal{E}_{q_{2}}^{(Z\otimes Z)},$

where $q_{1}\coloneqq(1-\sqrt{1-4p/3})/2$ and
$q_{2}\coloneqq[1-(1-16p/15)^{1/8}]/2$. We can then take account of these
single-Pauli error channels individually. Note that such exact decomposition
might be not possible for general Pauli noise channels, but it is not
important in our discussions.

In the 2D variant of the decoder presented in Sec. 3, we consider two sub-
lattices (c-restricted lattice $\mathcal{L}_{\neg\texttt{c}}^{*}$ and c-only
lattice $\mathcal{L}_{\texttt{c}}^{*}$) for each sub-decoding procedure of
color c. Analogously, for each color c, we deform and decompose the DEM
$\mathcal{M}$ obtained from a color-code circuit into the _c -restricted DEM_
$\mathcal{M}_{\neg\texttt{c}}$ and _c -only DEM_ $\mathcal{M}_{\texttt{c}}$.

Input: A DEM
$\mathcal{M}=\quantity{(q_{i},\mathcal{D}_{i},\mathcal{O}_{i})}_{i}$
A color $\texttt{c}\in\quantity{\texttt{r},\texttt{g},\texttt{b}}$

Output: A c-restricted DEM $\mathcal{M}_{\neg\texttt{c}}$
A c-only DEM $\mathcal{M}_{\texttt{c}}$
A set of new ‘virtual’ detectors
$\quantity{D_{e}}_{e\in\mathcal{M}_{\neg\texttt{c}}}$

/* Separating $Z$\- and $X$-type detectors */

1 $\mathcal{M}_{ZX}\leftarrow\emptyset$;

2 foreach  _$(q,\mathcal{D},\mathcal{O})\in\mathcal{M}$_ do

3 foreach  _$P\in\quantity{Z,X}$_ do

4 $\mathcal{D}_{P}\leftarrow\quantity{\text{$P$-type detectors in
$\mathcal{D}$}}$;

5 $\mathcal{O}_{P}\leftarrow\mathcal{O}\text{ {if} }P=Z\text{ {else}
}\emptyset$;

6 if  _$\mathcal{D}_{P}\neq\emptyset$_ then

7 Add $(q,\mathcal{D}_{P},\mathcal{O}_{P})$ to $\mathcal{M}_{ZX}$;

8

9

10 end foreach

11

12 end foreach

13Compress $\mathcal{M}_{ZX}$ (i.e., successively merge a pair of error
mechanisms of $\mathcal{M}_{ZX}$ that have the same targets while updating the
probability as $q=q_{1}+q_{2}-2q_{1}q_{2}$, where $q_{1}$ and $q_{2}$ are
respectively the probabilities of the two error mechanisms);

/* Constructing $\mathcal{M}_{\neg\texttt{c}}$ */

14 $\mathcal{M}_{\neg\texttt{c}}\leftarrow\emptyset$;

15 foreach  _$(q,\mathcal{D},\mathcal{O})\in\mathcal{M}_{ZX}$_ do

16 $\mathcal{D}_{\mathrm{\neg\texttt{c}}}\leftarrow\quantity{\text{Detectors
in $\mathcal{D}$ that are not {c}-colored}}$;

17 if  _$0 <\absolutevalue{\mathcal{D}_{\mathrm{\neg\texttt{c}}}}\leq 2$_ then

18 Add $(q,\mathcal{D}_{\mathrm{\neg\texttt{c}}},\emptyset)$ to
$\mathcal{M}_{\neg\texttt{c}}$;

19

20

21 end foreach

22Compress $\mathcal{M}_{\neg\texttt{c}}$;

23 $\quantity{D_{e}}_{e\in\mathcal{M}_{\neg\texttt{c}}}\leftarrow\text{A set
of new detectors}$;

/* Constructing $\mathcal{M}_{\texttt{c}}$ */

24 $\mathcal{M}_{\texttt{c}}\leftarrow\emptyset$;

25 foreach  _$(q,\mathcal{D},\mathcal{O})\in\mathcal{M}_{ZX}$_ do

26 $\mathcal{D}_{\mathrm{\neg\texttt{c}}}\leftarrow\quantity{\text{Detectors
in $\mathcal{D}$ that are not {c}-colored}}$;

27 if  _$\mathcal{D}_{\mathrm{\neg\texttt{c}}}=\emptyset$ and
$\absolutevalue{\mathcal{D}}\leq 2$_ then

28 Add $(q,\mathcal{D},\mathcal{O})$ to $\mathcal{M}_{\texttt{c}}$;

29

30 else if  _$0 <\absolutevalue{\mathcal{D}_{\mathrm{\neg\texttt{c}}}}\leq 2$
and
$\absolutevalue{\mathcal{D}\setminus\mathcal{D}_{\mathrm{\neg\texttt{c}}}}\leq
1$_ then

31 $e\leftarrow\text{An element of $\mathcal{M}_{\neg\texttt{c}}$ with
detectors $\mathcal{D}_{\mathrm{\neg\texttt{c}}}$}$ (which uniquely exists);

32 Add
$(q,\mathcal{D}\setminus\mathcal{D}_{\mathrm{\neg\texttt{c}}}\cup\quantity{D_{E}},\mathcal{O})$
to $\mathcal{M}_{\texttt{c}}$;

33

34 end if

35

36 end foreach

Algorithm 1 Decomposition of a color-code detector error model (DEM)

The step-by-step instructions to construct $\mathcal{M}_{\neg\texttt{c}}$ and
$\mathcal{M}_{\texttt{c}}$ from $\mathcal{M}$ are presented in Algorithm 1.
These can be outlined for $\texttt{c}=\texttt{r}$ as follows: First (in lines
1–10), we define $\mathcal{M}_{ZX}$ from $\mathcal{M}$ by separating each
error mechanism that affects both $Z$\- and $X$-type detectors into two
independent mechanisms, ensuring every error mechanism affects only one
detector type. If the logical observable $L_{Z}$ is a target of an error
mechanism to be separated, $L_{Z}$ is included only in the $Z$-type part after
the separation. It is because no measurement outcome can affect both $L_{Z}$
and an $X$-type detector; see Eqs. (6b) and (7). Note that this process is
equivalent to ignoring correlations between $X$ and $Z$ errors originated from
$Y$ errors or two-qubit errors such as $X\otimes Z$. We then compress
$\mathcal{M}_{ZX}$; namely, we merge error mechanisms of $\mathcal{M}_{ZX}$
that have the same set of targets while updating the probabilities properly.
After that (in lines 11–18), $\mathcal{M}_{\neg\texttt{r}}$ is constructed by
removing red detectors and logical observables from each error mechanism of
$\mathcal{M}_{ZX}$ and compressing it. Importantly, we introduce a new
_virtual detector_ $D_{e}$ for each error mechanism $e$ in
$\mathcal{M}_{\neg\texttt{r}}$. Lastly (in lines 19–28), we build
$\mathcal{M}_{\texttt{r}}$ by replacing the green and blue detectors of each
error mechanism of $\mathcal{M}_{ZX}$ with the corresponding virtual detector.
As a consequence, only red detectors, virtual detectors, and logical
observables are involved in $\mathcal{M}_{\texttt{r}}$.

In addition to the above description, Algorithm 1 also contains processes to
leave only edge-like mechanisms in the decomposed DEMs (see the conditions in
lines 14, 22, and 24). By doing so, each of the DEMs can be expressed as a
weighted graph $G$ whose vertices comprise detectors and an additional
boundary vertex $v_{\mathrm{bdry}}$. Namely, each error mechanism
$(q,\mathcal{D},\mathcal{O})$ corresponds to an edge of $G$ with weight
$\log\quantity[(1-q)/q]$, which connects the two detectors in $\mathcal{D}$
(if $\absolutevalue{\mathcal{D}}=2$) or the only detector in $\mathcal{D}$ and
$v_{\mathrm{bdry}}$ (if $\absolutevalue{\mathcal{D}}=1$). This graph can be
used to perform the MWPM algorithm that predicts one of the most probable
combinations of error mechanisms consistent with given violated detectors. If
a logical observable is flipped by an odd number of these error mechanisms,
its correction is $-1$; otherwise, it is $+1$.

Figure 6:  Performance comparison of 292 length-7 CNOT schedules. (a) The
failure rate $p_{\mathrm{fail}}$ of $T=7$ rounds of the logical idling gate
when using the concatenated MWPM decoder is evaluated for code distance $d=7$
under the circuit-level noise model of strength $p=10^{-3}$ for each of these
cnot schedules (sorted by the values of $p_{\mathrm{fail}}$ in ascending
order). The error bars correspond to the 99% CIs. The selected optimal
schedule is $[2,3,6,5,4,1;3,4,7,6,5,2]$, which is marked as a red dot. (b) The
$Z$\- and $X$-failure rates $p_{\mathrm{fail}}^{(Z)}$,
$p_{\mathrm{fail}}^{(X)}$ for these cnot schedules are visualized as a scatter
plot. The dashed line plots $p_{\mathrm{fail}}^{(X)}=p_{\mathrm{fail}}^{(Z)}$
and the gray area indicates the region of
$\absolutevalue{R_{\mathrm{bias}}}\leq 0.02$. The selected optimal schedule is
marked as a red dot.

With the above ingredients, we can finally describe how the concatenated MWPM
decoder works. Denoting the set of violated c-colored detectors as
$\sigma^{(\texttt{c})}$ for each
$\texttt{c}\in\quantity{\texttt{r},\texttt{g},\texttt{b}}$, the decoder works
as follows:

  1. 1.

Obtain the red-restricted DEM $\mathcal{M}_{\neg\texttt{r}}$, red-only DEM
$\mathcal{M}_{\texttt{r}}$, and set of virtual detectors
$\quantity{D_{e}}_{e\in\mathcal{M}_{\neg\texttt{r}}}$ from the DEM of the
original circuit through Algorithm 1.

  2. 2.

Perform the MWPM algorithm on $\mathcal{M}_{\neg\texttt{r}}$ with the input
$\sigma^{(\texttt{g})}\cup\sigma^{(\texttt{b})}$ and obtain a least-weight
error set $E_{\texttt{r}}\subseteq\mathcal{M}_{\neg\texttt{r}}$.

  3. 3.

Perform the MWPM algorithm on $\mathcal{M}_{\texttt{r}}$ with the input
$\sigma^{(\texttt{r})}\cup\quantity{D_{e}\mid e\in E_{\texttt{r}}}$ and obtain
a correction $L_{Z}^{(\mathrm{corr},\texttt{r})}\in\quantity{\pm 1}$ and the
corresponding total weight $w_{\texttt{r}}$ of predicted errors.

  4. 4.

Repeat the above steps for the other two colors and obtain
$L_{Z}^{(\mathrm{corr},\texttt{g})}$ and $L_{Z}^{(\mathrm{corr},\texttt{b})}$
with the corresponding total weights $w_{\texttt{g}}$ and $w_{\texttt{b}}$.

  5. 5.

Return $L_{Z}^{(\mathrm{corr},\texttt{c})}$ where
$\texttt{c}\coloneqq\operatorname{argmin}_{\texttt{c}^{\prime}\in\quantity{\texttt{r},\texttt{g},\texttt{b}}}w_{\texttt{c}^{\prime}}$.

###  4.3 Optimization of the CNOT schedule

The time order of cnot gates for syndrome extraction, called the cnot
schedule, needs to be optimized carefully before analyzing the performance of
the decoder. We use a similar method as Ref. [14] to determine it. A brief
review of this is as follows: The cnot schedule can be specified by a tuple of
twelve positive integers $\mathcal{A}=\quantity[a,b,c,d,e,f;g,h,i,j,k,l]$,
which contains all the integers from 1 to $\max\mathcal{A}$ (called the length
of the schedule). Each integer indicates the time slice at which the
corresponding cnot gate presented in Fig. 5 is applied; that is, we first
apply the cnot gates with integer 1, then apply those with integer 2, and so
on. Several conditions need to be imposed on $\mathcal{A}$ since each qubit
can be involved in at most one cnot gate per time slice and $Z$-type and
$X$-type syndrome measurements should not interfere each other; see Sec. II C
of Ref. [14] for their explicit descriptions. No cnot schedules with length
less than 7 satisfy these conditions. However, there are 876 valid length-7
schedules and we can leave only 292 among them by removing every schedule
equivalent to another schedule up to a symmetry.222This number (292) of valid
length-7 schedules is inconsistent with the number (234) reported in Ref.
[14]. We discussed it with the first author of Ref. [14], but could not
identify the precise reason of this discrepancy. We have verified using Stim
that all of the 292 schedules that we identify give the same detectors as
intended. We also note that, should we have mistakenly included additional
redundant schedules, this would not affect finding an optimal schedule.

We note that our simulating scenario described in Sec. 2.3 is only for
computing the $\overline{Z}$-failure rate $p_{\mathrm{fail}}^{(Z)}$ (i.e.,
failure rate of the $Z$ observable). Nonetheless, we can utilize the fact that
the $\overline{X}$-failure rate $p_{\mathrm{fail}}^{(X)}$ is equal to the
$\overline{Z}$-failure rate when using the cnot schedule with the “$Z$-part”
(i.e., first six integers) and “$X$-part” (i.e., last six integers) reversed
from the original one. For example, the $\overline{X}$-failure rate for the
schedule $[2,3,6,5,4,1;3,4,7,6,5,2]$ can be computed from our scenario by
instead using the schedule $[3,4,7,6,5,2;2,3,6,5,4,1]$. For a given cnot
schedule, we compute the logical failure rate as

$\displaystyle
p_{\mathrm{fail}}=p_{\mathrm{fail}}^{(X)}+p_{\mathrm{fail}}^{(Z)}-p_{\mathrm{fail}}^{(X)}p_{\mathrm{fail}}^{(Z)}$

by assuming that $\overline{X}$ and $\overline{Z}$ fail independently and
quantify the bias between them as

$\displaystyle
R_{\mathrm{bias}}\coloneqq\log_{10}\frac{p_{\mathrm{fail}}^{(Z)}}{p_{\mathrm{fail}}^{(X)}},$
(8)

which is zero when there is no bias.

To find the optimal cnot schedule, we evaluate $p_{\mathrm{fail}}$ by using
the concatenated MWPM decoder when $d=T=7$ for the above 292 valid length-7
cnot schedules under the circuit-level noise model of strength $p=10^{-3}$. We
select $p=10^{-3}$ since we mainly concern the sub-threshold performance of
our decoder when $p\leq 10^{-3}$. The evaluated values of $p_{\mathrm{fail}}$
are plotted in ascending order in Fig. 6(a). In addition, Fig. 6(b) shows the
distribution of $p_{\mathrm{fail}}^{(Z)}$ and $p_{\mathrm{fail}}^{(X)}$ for
these schedules. We select the optimal cnot schedule as the one that gives the
smallest $p_{\mathrm{fail}}$ among the schedules having
$\absolutevalue{R_{\mathrm{bias}}}\leq 0.02\approx\log_{10}1.05$, which is
visualized as a gray area in Fig. 6(b). The selected cnot schedule is

$\displaystyle\mathcal{A}=[2,3,6,5,4,1;3,4,7,6,5,2],$ (9)

which is marked as red dots in Fig. 6. The corresponding failure rates and
bias (99% CI) are

$\displaystyle p_{\mathrm{fail}}={}$ $\displaystyle(1.437\pm 0.005)\times
10^{-3},$ $\displaystyle p_{\mathrm{fail}}^{(Z)}=p_{\mathrm{fail}}^{(X)}={}$
$\displaystyle(7.19\pm 0.04)\times 10^{-4},$ $\displaystyle
R_{\mathrm{bias}}={}$ $\displaystyle 0.000\pm 0.003.$

Note that the failure rate for the worst-performing cnot schedule is
$p_{\mathrm{fail}}=(2.9\pm 0.1)\times 10^{-3}$, which is approximately twice
that of the best case.

Although we here choose the schedule to have a sufficiently small bias, biased
schedules may be intentionally used depending on the task. For instance,
ancillary logical qubits for the 15-to-1 magic state distillation scheme [35]
are more detrimental to $\overline{X}$ errors than to $\overline{Z}$ errors as
$\overline{Z}$ errors are detectable by the final $\overline{X}$ measurements
[36], thus we can benefit from using cnot schedules biased to $\overline{Z}$
errors (i.e., $R_{\mathrm{bias}}>0$) for these qubits.

###  4.4 Performance analysis

Figure 7:  Numerical analysis of the decoder under near-threshold circuit-
level noise. We consider $T\in\quantity{1,2,4,8,16,32}$ rounds of the logical
idling gate of the triangular color code with code distance
$d\in\quantity{3,5,7,\cdots,29}$ under the circuit-level noise model of
strength $p$. (a) Logical failure rates $p_{\mathrm{fail}}$ are plotted over
$p$ for each $T$ and $d$. Each data point (marked as ‘X’) has the 99% CI of
$\pm 10^{-3}$. For each $d$, the LOWESS regression of $p_{\mathrm{fail}}$ with
fraction $2/3$ is drawn as a solid line. For each
$d_{1}\in\quantity{13,17,21,25,29}$, the crossing of the two regression lines
of $d=d_{1}$ and $d=\quantity(d_{1}+1)/2$ is highlighted in dark color. (b)
The values of $p$ at these crossings
$\widetilde{p}^{\times}_{\mathrm{circuit}}(d_{1},T)$ are plotted over
$1/d_{1}$ for each $T$ with their linear regressions. The cross thresholds
$p^{\times}_{\mathrm{circuit}}(T)$ are estimated by the intersections of these
regressions with the vertical axis. (c) The 99% CIs of the estimations of
$p^{\times}_{\mathrm{circuit}}(T)$ are presented with a fitted curve in the
form of Eq. (2), where $p^{\times,\mathrm{LT}}_{\mathrm{circuit}}\approx
0.456\%$ and $\gamma\approx 1.02$. The orange dashed line plots
$p^{\times}_{\mathrm{circuit}}(T)=p^{\times,\mathrm{LT}}_{\mathrm{circuit}}$.

We now analyze the performance of the decoder under circuit-level noise models
when the cnot schedule is set to the optimal one in Eq. (9). As in Sec. 3.1,
we first examine the near-threshold region to determine the cross threshold
and then investigate the sub-threshold scaling of the logical failure rate.

For near-threshold simulations, we consider $T\in\quantity{1,2,4,8,16,32}$
rounds of the logical idling gate with code distance
$d\in\quantity{3,5,7,\cdots,29}$. The evaluated logical failure rates
$p_{\mathrm{fail}}$ are plotted over the noise strength $p$ in Fig. 7(a) for
each $T$ and $d$. Unlike the case of bit-flip noise plotted in Fig. 3(a), the
regression lines for each value of $T$ do not clearly intersect at a single
point. Therefore, to determine the cross threshold
$p^{\times}_{\mathrm{circuit}}(T)$, we evaluate
$\widetilde{p}^{\times}_{\mathrm{circuit}}(d_{1},T)$, which is the crossing of
the two lines of $d=d_{1}$ and $d=(d_{1}+1)/2$ for $d_{1}\equiv 1\pmod{4}$,
while varying $d_{1}$ and fit the data into the ansatz

$\displaystyle\widetilde{p}^{\times}_{\mathrm{circuit}}(d_{1},T)=\frac{A}{d_{1}}+p^{\times}_{\mathrm{circuit}}(T),$

where $A$ is a free parameter. The values of
$\widetilde{p}^{\times}_{\mathrm{circuit}}(d_{1},T)$ for
$d_{1}\in\quantity{13,17,21,25,29}$ are highlighted in dark color in Fig. 7(a)
and plotted in Fig. 7(b) against $1/d_{1}$ with their linear regressions. The
obtained cross thresholds $p^{\times}_{\mathrm{circuit}}(T)$ are visualized in
Fig. 7(c). By fitting them into Eq. (2), we get the long-term cross threshold
$p^{\times,\mathrm{LT}}_{\mathrm{circuit}}\approx 0.456\%$ with $\gamma\approx
1.02$.

Figure 8:  Numerical analysis of the decoder under sub-threshold circuit-level
noise. We consider $T=4d$ rounds of the logical idling gate of the triangular
color code with code distance $d\in\quantity{3,5,\cdots,21}$ under the
circuit-level noise model of strength $p$. (a) Logical failure rates per round
($p_{\mathrm{fail}}/T$) are plotted over $p$ for various code distances. Each
data point is marked as an error bar indicating its 99% CI or as an ‘X’ symbol
if its relative margin of error (i.e., the ratio of half the width of its CI
to its center) is less than 10%. For each $d$, the data within the range of
$p\leq 10^{-3}$ are used for the regression in the form of Eq. (4), which is
drawn as a solid line. The 99% CIs of the regression estimates are depicted as
shaded regions around the lines. (b) The 99% CIs of $G(d)$ and $C(d)$ in Eq.
(4) are plotted over $d$. Their linear regressions are shown as solid/dashed
lines with shaded regions indicating the 99% CIs of the estimates.

We next analyze the sub-threshold scaling of logical failure rates. We
consider $T=4d$ rounds of the logical idling gate with code distance
$d\in\quantity{3,5,7,\cdots,21}$ and compute its logical failure rate per
round ($p_{\mathrm{fail}}/T$) as presented in Fig. 8(a). For each $d$, the
data with $p\leq 10^{-3}$ are fitted into the ansatz of Eq. (4), whose
gradient $G(d)$ and constant $C(d)$ are plotted in Fig. 8(b). We obtain the
regressions of $G(d)$ and $C(d)$ against $d$ as

$\displaystyle G(d)={}$ $\displaystyle(0.50\pm 0.04)(d-12)+(5.4\pm 0.2),$
$\displaystyle C(d)={}$ $\displaystyle(2.9\pm 0.4)(d-12)+(26\pm 2),$

by selecting $d_{0}=12$, where the error terms are the 99% CIs of the
estimations. The corresponding ansatz parameters in Eq. (3) are

$\displaystyle\begin{split}&p^{\star}_{\mathrm{circuit}}\approx 3.2\times
10^{-3},\quad\alpha\approx 9.3\times 10^{-3},\\\ &\beta\approx
0.50,\quad\eta\approx 5.4,\quad d_{0}=12.\end{split}$

Figure 9:  Comparison of three matching-based decoders under circuit-level
noise. Logical failure rates per round $p_{\mathrm{fail}}/T$ are estimated by
using three different decoders (projection, Möbius, and concatenated MWPM
decoders) across different code distances $d$ at varying noise strengths
$p\in\quantity{10^{-3},5\times 10^{-4},10^{-4}}$. The data for the projection
decoder are from Fig. 17 of Ref. [14]. The data for the Möbius decoder are
from Figs. 11 and 12 of Ref. [18], which respectively correspond to the
superdense and middle-out color code circuits (two types of syndrome
extraction circuits proposed in Ref. [18]). The solid lines represent the
linear regressions of $\log p_{\mathrm{fail}}$ against $d$.

We lastly compare the performance of the concatenated MWPM decoder with that
of previous decoders: the projection and Möbius decoders. In Fig. 9, we
present the logical failure rates per round $p_{\mathrm{fail}}/T$ estimated by
using these decoders across different code distances $d$ at three noise
strengths $p\in\quantity{10^{-3},5\times 10^{-4},10^{-4}}$. The data for the
projection and Möbius decoders are originated from Refs. [14] and [18],
respectively. The figure shows that the projection decoder significantly
underperforms the other two due to its suboptimal scaling against $d$. The
scaling against $d$ is comparably similar for the other two decoders (when
$p\lessapprox 5\times 10^{-4}$); however, the concatenated MWPM decoder
achieves logical failure rates that are approximately 3–7 times lower than the
Möbius decoder.

In Figs. 14–16 of Appendix C, we present separate analyses of the
$\overline{Z}$\- and $\overline{X}$-failure rates of the decoder, together
with analysis of the bias $R_{\mathrm{bias}}$ defined in Eq. (8). To
summarize, this is as follows: The long-term cross thresholds are estimated as
$0.460\%$ for the $\overline{Z}$-failure and $0.452\%$ for the
$\overline{X}$-failure, which differ by about 1.8%. The 99% CIs of the
estimations of $R_{\mathrm{bias}}$ almost always include zero except for
$d=3$, which implies that we cannot reject the null hypothesis of
$R_{\mathrm{bias}}=0$ at the 99% significance level for these cases.

##  5 Remarks

In this work, we introduced the concatenated minimum-weight perfect matching
(MWPM) decoder processed by the concatenation of two rounds of MWPM per color,
which is applicable not only to simple bit-flip noise but also to realistic
circuit-level noise. The decoder is based on the idea that the outcome
obtained from decoding on a restricted lattice can serve as additional
‘virtual syndrome data’, which undergo a subsequent decoding round in
conjunction with remaining syndrome data.

We numerically analyzed the performance of the decoder in various aspects: We
considered both bit-flip and circuit-level noise models and investigated near-
threshold and sub-threshold behaviors of the logical failure rate
$p_{\mathrm{fail}}$. We found that the decoder has the thresholds of 8.2% for
bit-flip noise and 0.46% for circuit-level noise, which are comparable with
those of previous matching-based decoders such as the projection decoder [12,
13, 14, 15, 16] and Möbius MWPM decoder [17, 18]. Remarkably, we verified that
the decoder approaches a scaling of $p_{\mathrm{fail}}\sim p^{d/2}$, where $p$
is the noise strength and $d$ is the code distance, at least within our
simulation range ($d\lessapprox 31$ for bit-flip noise and $d\lessapprox 21$
for circuit-level noise). As a consequence, it outperforms previous matching-
based decoders in terms of their sub-threshold failure rates across both bit-
flip and circuit-level noise, as visualized in Figs. 4 and 9. We therefore
anticipate that our decoder enhances the practicality of employing color codes
in quantum computing, which has been considered less viable than surface codes
due to its logical failure rate performance despite its advantage in resource
efficiency [6]. We distributed a python module implementing the decoder on
Github [28] so that other researchers can use it.

We consider several future directions related to this work. All the analyses
in this work are based on the logical idling gate, which is generally suitable
for initial studies of a decoder. However, to use it in real implementations,
we should also consider nontrivial operations. In particular, it will be worth
investigating how the decoder should be modified to handle domain walls
required for lattice surgery [37]. Additionally, syndrome extraction circuits
may be able to be optimized further beyond the simple circuit in Fig. 5. For
example, Ref. [18] suggests two circuits: superdense and middle-out circuits.
Superdense circuits use two ancilla qubits per face, which are prepared in a
Bell pair so that superdense coding can be employed. Middle-out circuits do
not have ancilla qubits, thereby significantly reducing resource overheads at
the cost of a slight decrease in fault tolerance. It will be interesting to
see how the concatenated MWPM decoder performs with such circuits.

## Acknowledgements

We thank Felix Thomsen, Nicholas Fazio, Sam Smith, Benjamin J. Brown, and
Michael E. Beverland for helpful discussions and comments. This work is
supported by the Australian Research Council via the Centre of Excellence in
Engineered Quantum Systems (EQUS) project number CE170100009. This article is
based upon work supported by the Defense Advanced Research Projects Agency
(DARPA) under Contract No. HR001122C0063. Any opinions, findings and
conclusions or recommendations expressed in this article are those of the
author(s) and do not necessarily reflect the views of the Defense Advanced
Research Projects Agency (DARPA).

## References

  * [1] H. Bombin and M. A. Martin-Delgado.  “Topological quantum distillation”.  Phys. Rev. Lett. 97, 180501 (2006).
  * [2] Héctor Bombín.  “Topological codes”.  In Daniel A. Lidar and Todd A. Brun, editors, Quantum Error Correction.  Chapter 19, pages 455–481.  Cambridge (2013).
  * [3] S. B. Bravyi and A. Yu. Kitaev.  “Quantum codes on a lattice with boundary” (1998).  arXiv:quant-ph/9811052.
  * [4] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill.  “Topological quantum memory”.  J. Math. Phys. 43, 4452–4505 (2002).
  * [5] Andrew J. Landahl, Jonas T. Anderson, and Patrick R. Rice.  “Fault-tolerant quantum computing with color codes” (2011).  arXiv:1108.5738.
  * [6] Felix Thomsen, Markus S. Kesselring, Stephen D. Bartlett, and Benjamin J. Brown.  “Low-overhead quantum computing with the color code” (2022).  arxiv:2201.07806.
  * [7] Lukas Postler, Sascha Heu$\beta$en, Ivan Pogorelov, Manuel Rispler, Thomas Feldker, Michael Meth, Christian D. Marciniak, Roman Stricker, Martin Ringbauer, Rainer Blatt, Philipp Schindler, Markus Müller, and Thomas Monz.  “Demonstration of fault-tolerant universal quantum gate operations”.  Nature 605, 675–680 (2022).
  * [8] C. Ryan-Anderson, N. C. Brown, M. S. Allman, B. Arkin, G. Asa-Attuah, C. Baldwin, J. Berg, J. G. Bohnet, S. Braxton, N. Burdick, J. P. Campora, A. Chernoguzov, J. Esposito, B. Evans, D. Francois, J. P. Gaebler, T. M. Gatterman, J. Gerber, K. Gilmore, D. Gresh, A. Hall, A. Hankin, J. Hostetter, D. Lucchetti, K. Mayer, J. Myers, B. Neyenhuis, J. Santiago, J. Sedlacek, T. Skripka, A. Slattery, R. P. Stutz, J. Tait, R. Tobey, G. Vittorini, J. Walker, and D. Hayes.  “Implementing fault-tolerant entangling gates on the five-qubit code and the color code” (2022).  arXiv:2208.01863.
  * [9] Dolev Bluvstein, Simon J. Evered, Alexandra A. Geim, Sophie H. Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, J. Pablo Bonilla Ataides, Nishad Maskara, Iris Cong, Xun Gao, Pedro Sales Rodriguez, Thomas Karolyshyn, Giulia Semeghini, Michael J. Gullans, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin.  “Logical quantum processor based on reconfigurable atom arrays”.  Nature 626, 58–65 (2024).
  * [10] Lukas Postler, Friederike Butt, Ivan Pogorelov, Christian D. Marciniak, Sascha Heußen, Rainer Blatt, Philipp Schindler, Manuel Rispler, Markus Müller, and Thomas Monz.  “Demonstration of fault-tolerant Steane quantum error correction” (2023).  arXiv:2312.09745.
  * [11] Yi-Fei Wang, Yixu Wang, Yu-An Chen, Wenjun Zhang, Tao Zhang, Jiazhong Hu, Wenlan Chen, Yingfei Gu, and Zi-Wen Liu.  “Efficient fault-tolerant implementations of non-Clifford gates with reconfigurable atom arrays” (2024).  arXiv:2312.09111.
  * [12] Nicolas Delfosse.  “Decoding color codes by projection onto surface codes”.  Phys. Rev. A 89, 012317 (2014).
  * [13] Christopher Chamberland, Aleksander Kubica, Theodore J. Yoder, and Guanyu Zhu.  “Triangular color codes on trivalent graphs with flag qubits”.  New J. Phys. 22, 023019 (2020).
  * [14] Michael E. Beverland, Aleksander Kubica, and Krysta M. Svore.  “Cost of universality: A comparative study of the overhead of state distillation and code switching with color codes”.  PRX Quantum 2, 020341 (2021).
  * [15] Aleksander Kubica and Nicolas Delfosse.  “Efficient color code decoders in $d\geq 2$ dimensions from toric code decoders”.  Quantum 7, 929 (2023).
  * [16] Jiaxuan Zhang, Yu-Chun Wu, and Guo-Ping Guo.  “Facilitating practical fault-tolerant quantum computing based on color codes” (2023).  arXiv:2309.05222.
  * [17] Kaavya Sahay and Benjamin J. Brown.  “Decoder for the triangular color code by matching on a Möbius strip”.  PRX Quantum 3, 010310 (2022).
  * [18] Craig Gidney and Cody Jones.  “New circuits and an open source decoder for the color code” (2023).  arXiv:2312.08813.
  * [19] Christopher T. Chubb.  “General tensor network decoding of 2D Pauli codes” (2021).  arXiv:2101.04125.
  * [20] Yugo Takada, Yusaku Takeuchi, and Keisuke Fujii.  “Highly accurate decoder for topological color codes with simulated annealing” (2023).  arXiv:2303.01348.
  * [21] Lucas Berent, Lukas Burgholzer, Peter-Jan H. S. Derks, Jens Eisert, and Robert Wille.  “Decoding quantum color codes with MaxSAT” (2023).  arXiv:2303.14237.
  * [22] Eric Sabo, Arun B. Aloshious, and Kenneth R. Brown.  “Trellis decoding for qudit stabilizer codes and its application to qubit topological codes” (2022).  arXiv:2106.08251.
  * [23] Nishad Maskara, Aleksander Kubica, and Tomas Jochym-O’Connor.  “Advantages of versatile neural-network decoding for topological codes”.  Phys. Rev. A 99, 052351 (2019).
  * [24] Nicolas Delfosse and Naomi H. Nickerson.  “Almost-linear time decoding algorithm for topological codes”.  Quantum 5, 595 (2021).
  * [25] Pradeep Sarvepalli and Robert Raussendorf.  “Efficient decoding of topological color codes”.  Phys. Rev. A 85, 022317 (2012).
  * [26] Christophe Piveteau, Christopher T. Chubb, and Joseph M. Renes.  “Tensor network decoding beyond 2D” (2023).  arXiv:2310.10722.
  * [27] Seok-Hyung Lee and Hyunseok Jeong.  “Universal hardware-efficient topological measurement-based quantum computation via color-code-based cluster states”.  Phys. Rev. Res. 4, 013010 (2022).
  * [28] Seok-Hyung Lee.  “color-code-stim”.  https://github.com/seokhyung-lee/color-code-stim (2024).
  * [29] Austin G. Fowler.  “Two-dimensional color-code quantum computation”.  Phys. Rev. A 83, 1–8 (2011).
  * [30] Pavithran Iyer and David Poulin.  “Hardness of decoding quantum stabilizer codes”.  IEEE Trans. Inf. Theory 61, 5209–5223 (2015).
  * [31] Jack Edmonds.  “Paths, trees, and flowers”.  Can. J. of Math. 17, 449–467 (1965).
  * [32] Craig Gidney.  “Stim: a fast stabilizer circuit simulator”.  Quantum 5, 497 (2021).
  * [33] Oscar Higgott.  “PyMatching: A python package for decoding quantum codes with minimum-weight perfect matching”.  ACM Trans. Quantum Comput.3 (2022).
  * [34] Skipper Seabold and Josef Perktold.  “Statsmodels: Econometric and statistical modeling with python”.  In 9th Python in Science Conference.  (2010).
  * [35] Sergey Bravyi and Alexei Kitaev.  “Universal quantum computation with ideal clifford gates and noisy ancillas”.  Phys. Rev. A 71, 022316 (2005).
  * [36] Daniel Litinski.  “Magic state distillation: Not as costly as you think”.  Quantum 3, 205 (2019-12-02).  arxiv:1905.06903.
  * [37] Markus S. Kesselring, Julio C. Magdalena de la Fuente, Felix Thomsen, Jens Eisert, Stephen D. Bartlett, and Benjamin J. Brown.  “Anyon condensation and the color code”.  PRX Quantum 5, 010342 (2024).

##  Appendix A Proof of the validity of the concatenated MWPM decoder

In this appendix, we formally prove that the 2D version of the concatenated
MWPM decoder described in Sec. 3 indeed works well. Namely, we show that the
decoder always identifies a proper prediction of $X$ errors consistent with
the syndrome. We additionally validate that any outcome obtained from the
projection decoder is a valid matching for the concatenated MWPM decoder,
which implies that the former cannot outperform the latter. We here use the
same mathematical notations as used in Sec. 3.

###  A.1 Notations and definitions

Let $\mathcal{L}$ be a trivalent three-colorable lattice. We assume that the
lattice does not have boundaries; we will consider boundaries later. We
consider the lattices: the dual lattice $\mathcal{L}^{*}$, the decoding
hypergraph $\mathcal{H}$, the red/green/blue-restricted lattice
$\mathcal{L}_{\neg\texttt{r}/\neg\texttt{g}/\neg\texttt{b}}^{*}$, the
red/green/blue-only lattice
$\mathcal{L}_{\texttt{r}/\texttt{g}/\texttt{b}}^{*}$.

Let $\mathcal{L}^{*}$ be the dual lattice of $\mathcal{L}$, whose vertices are
three-colorable so that endpoints of an edge are distinctly colored and whose
faces are of the form
$\quantity{\quantity{v_{\texttt{r}},v_{\texttt{g}}},\quantity{v_{\texttt{g}},v_{\texttt{b}}},\quantity{v_{\texttt{b}},v_{\texttt{r}}}}$,
where $v_{\texttt{r}}$, $v_{\texttt{g}}$, and $v_{\texttt{b}}$ are
respectively red, green, and blue vertices. The color of an edge is chosen to
be distinct from the colors of its endpoints. We associate with the dual
lattice its cellular homology complex
$(C_{0}(\mathcal{L}^{*}),C_{1}(\mathcal{L}^{*}),C_{2}(\mathcal{L}^{*}))$,
where $C_{0}(\mathcal{L}^{*})$ is an $\mathbbm{F}_{2}$ (binary) vector space
with the basis set $\Delta_{0}(\mathcal{L}^{*})$, and accordingly for
$C_{1}(\mathcal{L}^{*})$, $\Delta_{1}(\mathcal{L}^{*})$ and
$C_{2}(\mathcal{L}^{*})$, $\Delta_{2}(\mathcal{L}^{*})$. We equip the complex
with linear boundary maps $\partial_{1}^{*}:C_{1}(\mathcal{L}^{*})\rightarrow
C_{0}(\mathcal{L}^{*})$ and
$\partial_{2}^{*}:C_{2}(\mathcal{L}^{*})\rightarrow C_{1}(\mathcal{L}^{*})$
such that $\partial_{1}^{*}(\quantity{u,v})=u+v$ and
$\partial_{2}^{*}(\quantity{e_{1},e_{2},...,e_{m}})=e_{1}+e_{2}+...+e_{m}$.
For each color $\texttt{c}\in\quantity{\texttt{r},\texttt{g},\texttt{b}}$, we
denote
$\Delta_{0}^{(\texttt{c})}\quantity(\mathcal{L}^{*})=\quantity{v\in\Delta_{0}\quantity(\mathcal{L}^{*})\;|\;\text{$v$
is {c}-colored}}$ and accordingly for
$\Delta_{1}^{(\texttt{c})}\quantity(\mathcal{L}^{*})$.

The decoding hypergraph $\mathcal{H}$ has vertices
$\mathcal{V}=\Delta_{0}(\mathcal{L}^{*})$, hyper-edges
$\varepsilon=\quantity{\cup_{e\in f}e\;|\;f\in\Delta_{2}(\mathcal{L}^{*})}$
(such that each hyper-edge is of the form
$\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}}$), and hyper-faces
$\mathcal{F}=\quantity{\quantity{e\in\Delta_{1}(\mathcal{L}^{*})\;|\;v\in
e}\;|\;v\in\Delta_{0}(\mathcal{L}^{*})}$. On this lattice, we define a
2-complex with an $\mathbbm{F}_{2}$ vector space $C_{0}(\mathcal{H})$ spanned
by the $\mathcal{V}$, $C_{1}(\mathcal{H})$ spanned by $\varepsilon$, and
$C_{2}(\mathcal{H})$ spanned by $\mathcal{F}$. The boundary maps on this
complex are defined as

$\displaystyle\partial_{1}^{\mathcal{H}}\quantity(\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}})$
$\displaystyle=v_{\texttt{r}}+v_{\texttt{g}}+v_{\texttt{b}},$
$\displaystyle\partial_{2}^{\mathcal{H}}\quantity(\quantity{e_{1},e_{2},\cdots,e_{m}})$
$\displaystyle=e_{1}+e_{2}+\cdots+e_{m}.$

The red-restricted lattice $\mathcal{L}_{\neg\texttt{r}}^{*}$ is the subgraph
of $\mathcal{L}^{*}$ over vertices
$\Delta_{0}(\mathcal{L}_{\neg\texttt{r}}^{*})=\Delta_{0}^{(\texttt{g})}\quantity(\mathcal{L}^{*})\cup\Delta_{0}^{(\texttt{b})}\quantity(\mathcal{L}^{*})$.
We associate it with its cellular homology complex
$C_{0}(\mathcal{L}_{\neg\texttt{r}}^{*})$. We define a linear projection
operator $\pi_{0}^{(\texttt{r})}:C_{0}(\mathcal{L}^{*})\rightarrow
C_{0}(\mathcal{L}^{*})$ that satisfies

$\displaystyle\pi_{0}^{(\texttt{r})}(v)=\begin{cases}v&\text{if
}v\notin\Delta_{0}^{(\texttt{r})}\quantity(\mathcal{L}^{*}),\\\
0&\text{otherwise}\end{cases}$

for each $v\in\Delta_{0}\quantity(\mathcal{L}^{*})$ such that
$\imaginary(\pi_{0}^{(\texttt{r})})=C_{0}(\mathcal{L}_{\neg\texttt{r}}^{*})$.

The red-only lattice $\mathcal{L}_{\texttt{r}}^{*}$ is defined as

$\displaystyle\Delta_{0}\quantity(\mathcal{L}_{\texttt{r}}^{*})$
$\displaystyle=\Delta_{0}^{(\texttt{r})}\quantity(\mathcal{L}^{*})\cup\Delta_{1}^{(\texttt{r})}\quantity(\mathcal{L}^{*}),$
$\displaystyle\Delta_{1}\quantity(\mathcal{L}_{\texttt{r}}^{*})$
$\displaystyle=\quantity{\quantity{v_{\texttt{r}},\quantity{v_{\texttt{g}},v_{\texttt{b}}}}\subset\Delta_{0}\quantity(\mathcal{L}_{\texttt{r}}^{*})\;|\;\
\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}}\in\varepsilon},$
$\displaystyle\Delta_{2}\quantity(\mathcal{L}_{\texttt{r}}^{*})$
$\displaystyle=\left\\{\quantity{\quantity{v_{\texttt{r}},\quantity{v_{\texttt{g}},v_{\texttt{b}}}}\in\Delta_{1}\quantity(\mathcal{L}_{\texttt{r}}^{*})\;|\;v\in\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}}}\;\middle|\;v\in\Delta_{0}^{(\texttt{g})}\quantity(\mathcal{L}^{*})\cup\Delta_{0}^{(\texttt{b})}\quantity(\mathcal{L}^{*})\right\\},$

which respectively span $C_{0}\quantity(\mathcal{L}_{\texttt{r}}^{*})$,
$C_{1}\quantity(\mathcal{L}_{\texttt{r}}^{*})$, and
$C_{2}\quantity(\mathcal{L}_{\texttt{r}}^{*})$ that form its cellular homology
complex. Note that $C_{1}(\mathcal{L}_{\texttt{r}}^{*})$ and
$C_{1}(\mathcal{H})$ are isomorphic under the mapping of bases
$\quantity{v_{\texttt{r}},\quantity{v_{\texttt{g}},v_{\texttt{b}}}}\leftrightarrow\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}}$.
Therefore, we will treat edges in the red-only lattice as hyper-edges when
considering complexes. We also note that
$C_{0}(\mathcal{L}_{\texttt{r}}^{*})=C_{1}(\mathcal{L}_{\neg\texttt{r}}^{*})\;\oplus\;\imaginary(\mathds{1}-\pi^{(\texttt{r})}_{0})$.
We define $P_{C_{1}(\mathcal{L}_{\neg\texttt{r}}^{*})}$ and
$P_{\imaginary(\mathds{1}-\pi_{0}^{(\texttt{r})})}$ as the projectors from
$C_{0}(\mathcal{L}_{\texttt{r}}^{*})$ onto these two subspaces
$C_{1}(\mathcal{L}_{\neg\texttt{r}}^{*})$ and
$\imaginary(\mathds{1}-\pi_{0}^{(\texttt{r})})$, respectively. The boundary
map for 1-cells,

$\displaystyle\partial_{1}^{\mathcal{L}_{\texttt{r}}^{*}}\quantity(\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}})$
$\displaystyle=v_{\texttt{r}}+\quantity{v_{\texttt{g}},v_{\texttt{b}}},$

can be separated into two functions $p_{\mathrm{vert}}^{(\texttt{r})}$ and
$p_{\mathrm{edge}}^{(\texttt{r})}$ as

$\displaystyle p_{\mathrm{vert}}^{(\texttt{r})}$
$\displaystyle=P_{\imaginary(\mathds{1}-\pi_{0}^{(\texttt{r})})}\partial_{1}^{\mathcal{L}_{\texttt{r}}^{*}},$
(10a) $\displaystyle p_{\mathrm{edge}}^{(\texttt{r})}$
$\displaystyle=P_{C_{1}(\mathcal{L}_{\neg\texttt{r}}^{*})}\partial_{1}^{\mathcal{L}_{\texttt{r}}^{*}},$
(10b) $\displaystyle\partial_{1}^{\mathcal{L}_{\texttt{r}}^{*}}$
$\displaystyle=p_{\mathrm{vert}}^{(\texttt{r})}+p_{\mathrm{edge}}^{(\texttt{r})}.$

These operators act on basis elements as

$\displaystyle
p_{\mathrm{vert}}^{(\texttt{r})}(\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}})$
$\displaystyle=v_{\texttt{r}},$ $\displaystyle
p_{\mathrm{edge}}^{(\texttt{r})}(\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}})$
$\displaystyle=\quantity{v_{\texttt{g}},v_{\texttt{b}}}.$

All the above notations are naturally extended to other two colors g and b.

The decoding problem can be reformulated as follows: Given a set $\sigma$ of
syndrome vertices in $\mathcal{H}$, identify a set of hyper-edges whose
boundary is equal to the syndrome vertices.

The concatenated decoder first finds a matching $b_{\texttt{r}}\in
C_{1}(\mathcal{L}_{\neg\texttt{r}}^{*})$ in the red-restricted lattice such
that
$\partial_{1}^{\mathcal{L}^{*}_{\neg\texttt{r}}}(b_{\texttt{r}})=\pi^{(\texttt{r})}_{0}(\sigma)$.
It then lifts this matching and the red vertices from the original syndrome
into the red-only lattice to form a set of vertices
$(\mathds{1}-\pi_{0}^{(\texttt{r})})(\sigma)+b_{\texttt{r}}$, for which it
then finds a matching $x$ such that
$\partial_{1}^{\mathcal{L}_{\texttt{r}}^{*}}(x)=(\mathds{1}-\pi_{0}^{(\texttt{r})})(\sigma)+b_{\texttt{r}}$.
This is repeated for the other two colors and the least-weight correction is
selected as the final outcome, but we here only consider the red sub-decoding
procedure (without loss of generality) as our goal is showing the validity of
the decoder, not its optimality.

###  A.2 Proof of validity when no boundaries

We first show that, for a given syndrome and error, if each of the first- and
second-round decoding processes works correctly (i.e. returns a valid
matching), the concatenated MWPM decoder returns a valid matching. Namely, we
prove the following claim:

######  Claim 1.

For $\sigma\in C_{0}(\mathcal{H})$, $x\in C_{1}(\mathcal{H})$, and
$b_{\texttt{r}}\in C_{1}(\mathcal{L}_{\neg\texttt{r}}^{*})$, if

$\displaystyle\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}\quantity(b_{\texttt{r}})$
$\displaystyle=\pi_{0}^{(\texttt{r})}(\sigma),$ (11a)
$\displaystyle\partial_{1}^{\mathcal{L}_{\texttt{r}}^{*}}(x)$
$\displaystyle=\quantity(\mathds{1}-\pi_{0}^{(\texttt{r})})(\sigma)+b_{\texttt{r}},$
(11b)

then

$\displaystyle\partial_{1}^{\mathcal{H}}(x)=\sigma.$ (12)

###### Proof.

Using the projected boundary maps in Eq. (10), we rewrite Eq. (11b) as

$\displaystyle p_{\mathrm{vert}}^{(\texttt{r})}(x)$
$\displaystyle=\quantity(\mathds{1}-\pi_{0}^{(\texttt{r})})(\sigma),$
$\displaystyle p_{\mathrm{edge}}^{(\texttt{r})}(x)$
$\displaystyle=b_{\texttt{r}}.$

From the latter equation we get
$\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}p_{\mathrm{edge}}^{(\texttt{r})}(x)=\pi_{0}^{(\texttt{r})}(\sigma)$,
and thus
$(\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}p_{\mathrm{edge}}^{(\texttt{r})}+p_{\mathrm{vert}}^{(\texttt{r})})(x)=\sigma$.
It suffices to prove that
$(\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}p_{\mathrm{edge}}^{(\texttt{r})}+p_{\mathrm{vert}}^{(\texttt{r})})(x)=\partial_{1}^{\mathcal{H}}(x)$.
Since its both sides are linear in $x$, we only need to show this over the
basis of hyper-edges that span $C_{1}(\mathcal{H})$:

$\displaystyle\quantity(p_{\mathrm{vert}}^{(\texttt{r})}+\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}p_{\mathrm{edge}}^{(\texttt{r})})\quantity(\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}})$
$\displaystyle=v_{\texttt{r}}+\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}\quantity(\quantity{v_{\texttt{g}},v_{\texttt{b}}})$
$\displaystyle=v_{\texttt{r}}+v_{\texttt{g}}+v_{\texttt{b}}$
$\displaystyle=\partial_{1}^{\mathcal{H}}\quantity(\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}}).$

∎

###  A.3 Consideration of boundaries

We now assume that $\mathcal{L}$ is a color-code lattice with boundaries. To
handle them, its dual lattice $\mathcal{L}^{*}$ is augmented with three
distinctly colored boundary vertices $v_{\mathrm{bdry}}^{\texttt{r}}$,
$v_{\mathrm{bdry}}^{\texttt{g}}$, and $v_{\mathrm{bdry}}^{\texttt{b}}$.
Vertices in $\mathcal{L}^{*}$ corresponding to green and blue faces of
$\mathcal{L}$ adjacent to the red boundary are connected to
$v_{\mathrm{bdry}}^{\texttt{r}}$, and so on for the other two colors, and all
pairs of boundary vertices are connected.

Despite the existence of the boundary vertices, almost all the notations and
definitions in Appendix A.1 do not change. Denoting the set of boundary
vertices of a lattice $\mathcal{L}$ as $V_{\mathrm{bdry}}(\mathcal{L})$, the
boundary vertices of various lattices described above are set as follows:

$\displaystyle
V_{\mathrm{bdry}}\quantity(\mathcal{L}^{*})=V_{\mathrm{bdry}}\quantity(\mathcal{H})$
$\displaystyle=\quantity{v_{\mathrm{bdry}}^{\texttt{r}},v_{\mathrm{bdry}}^{\texttt{g}},v_{\mathrm{bdry}}^{\texttt{b}}},$
$\displaystyle V_{\mathrm{bdry}}\quantity(\mathcal{L}_{\neg\texttt{r}}^{*})$
$\displaystyle=\quantity{v_{\mathrm{bdry}}^{\texttt{g}},v_{\mathrm{bdry}}^{\texttt{b}}},$
$\displaystyle V_{\mathrm{bdry}}\quantity(\mathcal{L}_{\texttt{r}}^{*})$
$\displaystyle=\quantity{v_{\mathrm{bdry}}^{\texttt{r}},\quantity{v_{\mathrm{bdry}}^{\texttt{g}},v_{\mathrm{bdry}}^{\texttt{b}}}},.$

We define $C_{\mathrm{bdry}}\quantity(\mathcal{L})$ as the $\mathbbm{F}_{2}$
vector space spanned by $V_{\mathrm{bdry}}\quantity(\mathcal{L})$. Note that,
from a decoding perspective, it does not matter if we contract multiple
boundary vertices into a single boundary vertex since edges connecting them
are given zero weight when applying MWPM; we thus displayed only one boundary
vertex in Figs. 1 and 2 for simplicity. However, we here do not merge distinct
boundary vertices for mathematical clarity.

Since syndromes can be matched with the boundary vertices, the mathematical
description of MWPM in Eq. (11) and the validity condition of decoding in Eq.
(12) should be modified. The modified claim and its proof are as follows:

######  Claim 2.

For $\sigma\in C_{0}(\mathcal{H})$, $x\in C_{1}(\mathcal{H})$, and
$b_{\texttt{r}}\in C_{1}(\mathcal{L}_{\neg\texttt{r}}^{*})$, if

$\displaystyle\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}\quantity(b_{\texttt{r}})-\pi_{0}^{(\texttt{r})}(\sigma)\in
C_{\mathrm{bdry}}\quantity(\mathcal{L}_{\neg\texttt{r}}^{*}),$ (13a)
$\displaystyle\partial_{1}^{\mathcal{L}_{\texttt{r}}^{*}}(x)-\quantity(\mathds{1}-\pi_{0}^{(\texttt{r})})(\sigma)-b_{\texttt{r}}\in
C_{\mathrm{bdry}}\quantity(\mathcal{L}_{\texttt{r}}^{*}),$ (13b)

then $\partial_{1}^{\mathcal{H}}(x)-\sigma\in C_{\mathrm{bdry}}(\mathcal{H})$.

###### Proof.

Let $c\in C_{\mathrm{bdry}}(\mathcal{L}_{\neg\texttt{r}}^{*})$ and
$c^{\prime}=c^{\prime}_{\mathrm{vert}}+c^{\prime}_{\mathrm{edge}}\in
C_{\mathrm{bdry}}(\mathcal{L}_{\texttt{r}}^{*})$ denote the left-hand sides of
Eqs. (13a) and (13b), respectively, where
$c^{\prime}_{\mathrm{vert}}=P_{\imaginary(\mathds{1}-\pi_{0}^{(\texttt{r})})}c^{\prime}\in\quantity{0,v_{\mathrm{bdry}}^{\texttt{r}}}$
and
$c^{\prime}_{\mathrm{edge}}=P_{C_{1}(\mathcal{L}_{\neg\texttt{r}}^{*})}c^{\prime}\in\quantity{0,\quantity{v_{\mathrm{bdry}}^{\texttt{g}},v_{\mathrm{bdry}}^{\texttt{b}}}}$.
We rewrite Eq. (13b) as

$\displaystyle p_{\mathrm{vert}}^{(\texttt{r})}(x)$
$\displaystyle=\quantity(\mathds{1}-\pi_{0}^{(\texttt{r})})(\sigma)+c^{\prime}_{\mathrm{vert}},$
$\displaystyle p_{\mathrm{edge}}^{(\texttt{r})}(x)$
$\displaystyle=b_{\texttt{r}}+c^{\prime}_{\mathrm{edge}}.$

From the latter equation we get
$\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}p_{\mathrm{edge}}^{(\texttt{r})}(x)=\pi_{0}^{(\texttt{r})}(\sigma)+c+\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}c^{\prime}_{\mathrm{edge}}$,
and thus
$(\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}p_{\mathrm{edge}}^{(\texttt{r})}+p_{\mathrm{vert}}^{(\texttt{r})})(x)=\sigma+c+c^{\prime}_{\mathrm{vert}}+\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}c^{\prime}_{\mathrm{edge}}$.
Since
$c+c^{\prime}_{\mathrm{vert}}+\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}c^{\prime}_{\mathrm{edge}}\in
C_{\mathrm{bdry}}(\mathcal{H})$ (as
$\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}c^{\prime}_{\mathrm{edge}}$ is
either 0 or $v_{\mathrm{bdry}}^{\texttt{g}}+v_{\mathrm{bdry}}^{\texttt{b}}$),
it suffices to prove that

$\displaystyle(\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}p_{\mathrm{edge}}^{(\texttt{r})}+p_{\mathrm{vert}}^{(\texttt{r})}-\partial_{1}^{\mathcal{H}})(x)\in
C_{\mathrm{bdry}}\quantity(\mathcal{H}).$

Because of linearity, we only need to show this over the basis of hyper-edges
that span $C_{1}(\mathcal{H})$:

$\displaystyle\quantity(p_{\mathrm{vert}}^{(\texttt{r})}+\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}p_{\mathrm{edge}}^{(\texttt{r})}-\partial_{1}^{\mathcal{H}})\quantity(\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}})$
$\displaystyle={}$ $\displaystyle
v_{\texttt{r}}+\partial_{1}^{\mathcal{L}_{\neg\texttt{r}}^{*}}\quantity(\quantity{v_{\texttt{g}},v_{\texttt{b}}})-\quantity(v_{\texttt{r}}+v_{\texttt{g}}+v_{\texttt{b}})$
$\displaystyle={}$ $\displaystyle 0\in
C_{\mathrm{bdry}}\quantity(\mathcal{H}).$

∎

Figure 10:  Example of an error with weight $O(d/3)$ that is uncorrectable via
the projection decoder but correctable via the concatenated MWPM decoder. (a)
The error is drawn as red, green, and blue solid lines, which makes a blue
check and a green check marked as circles violated. The projection decoder
pairs up these checks with the green/blue boundaries (dotted lines), thus it
makes a logical error. (b) The same error is correctable via the concatenated
MWPM decoder. The microscopic picture of the vicinity of the violated checks
is described in (b-i), where black dots indicate qubits with errors. In (b-ii)
and (b-iii), MWPMs on the red-restricted and red-only lattices are schematized
with the notations used in Fig. 2, where only some of the lattice elements are
visualized for simplicity. The outcome of the second-round MWPM, which is
visualized as a red thick line ending at the boundary vertex
$v_{\mathrm{bdry}}$, coincides with the error, thus it makes no logical error.

###  A.4 Superiority of the concatenated MWPM decoder over the projection
decoder

In addition, we show that the projection decoder cannot outperform the
concatenated MWPM decoder. In other words, we analytically prove that the
matching obtained from the concatenated MWPM decoder always has a weight not
greater than that from the projection decoder. We here only consider the cases
without boundaries.

Given a syndrome $s$, the projection decoder finds matchings $b_{\texttt{r}}$,
$b_{\texttt{g}}$, and $b_{\texttt{b}}$ in the restricted lattices such that
$\partial_{1}^{\mathcal{L}^{*}_{\neg\texttt{c}}}(b_{\texttt{c}})=\pi^{(\texttt{c})}_{0}(\sigma)$
for each $\texttt{c}\in\quantity{\texttt{r},\texttt{g},\texttt{b}}$. It then
lifts the three restricted lattice matchings to find a hypergraph matching
$x\in C_{1}(\mathcal{H})$ such that
$\partial_{2}^{*}(x)=b_{\texttt{r}}+b_{\texttt{g}}+b_{\texttt{b}}$.

The following claim asserts that, for the projection and concatenated MWPM
decoders sharing the same result on the red-restricted lattice, any matching
on the projection decoder must also be a proper matching on the red-only
lattice of the concatenated MWPM decoder. Hence, running MWPM on the red-only
lattice always gives a matching whose weight is equal to or less than the
wieght of any matching obtained from the projection decoder.

######  Claim 3.

Given $\sigma\in C_{0}(\mathcal{H})$, $x\in C_{1}(\mathcal{H})$, and
$b_{\texttt{c}}\in C_{1}(\mathcal{L}_{\neg\texttt{c}}^{*})$ for each
$\texttt{c}\in\quantity{\texttt{r},\texttt{g},\texttt{b}}$, suppose

$\displaystyle\partial_{1}^{\mathcal{L}_{\neg\texttt{c}}^{*}}\quantity(b_{\texttt{c}})$
$\displaystyle=\pi_{0}^{(\texttt{c})}(\sigma)\quad\forall\texttt{c}\in\quantity{\texttt{r},\texttt{g},\texttt{b}},$
$\displaystyle\partial_{2}^{*}(x)$
$\displaystyle=b_{\texttt{r}}+b_{\texttt{g}}+b_{\texttt{b}},$
$\displaystyle\partial_{1}^{\mathcal{H}}(x)$ $\displaystyle=\sigma.$

Then
$\partial_{1}^{\mathcal{L}_{\texttt{r}}^{*}}(x)=b_{\texttt{r}}+\quantity(\mathds{1}-\pi_{0}^{(\texttt{r})})(\sigma)$.

###### Proof.

The assertion is equivalent to

$\displaystyle p_{\mathrm{vert}}^{(\texttt{r})}(x)$
$\displaystyle=\quantity(\mathds{1}-\pi_{0}^{(\texttt{r})})(\sigma)$
$\displaystyle p_{\mathrm{edge}}^{(\texttt{r})}(x)$
$\displaystyle=b_{\texttt{r}}$

As
$\partial_{2}^{*}(\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}})=\quantity{v_{\texttt{r}},v_{\texttt{g}}}+\quantity{v_{\texttt{g}},v_{\texttt{b}}}+\quantity{v_{\texttt{r}},v_{\texttt{b}}}=(p_{\mathrm{edge}}^{(\texttt{r})}+p_{\mathrm{edge}}^{(\texttt{g})}+p_{\mathrm{edge}}^{(\texttt{b})})(\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}})$,
applying linearity we get that
$\partial_{2}^{*}(x)=(p_{\mathrm{edge}}^{(\texttt{r})}+p_{\mathrm{edge}}^{(\texttt{g})}+p_{\mathrm{edge}}^{(\texttt{b})})(x)=b_{\texttt{r}}+b_{\texttt{g}}+b_{\texttt{b}}$.
As the subspaces of red, green, and blue edges are disjoint,
$p_{\mathrm{edge}}^{(\texttt{r})}(x)=b_{\texttt{r}}$. Similarly,
$\partial_{1}^{\mathcal{H}}(\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}})=v_{\texttt{r}}+v_{\texttt{g}}+v_{\texttt{b}}=(p_{\mathrm{vert}}^{(\texttt{r})}+p_{\mathrm{vert}}^{(\texttt{g})}+p_{\mathrm{vert}}^{(\texttt{b})})(\quantity{v_{\texttt{r}},v_{\texttt{g}},v_{\texttt{b}}})$.
By linearity,
$\partial_{1}^{\mathcal{H}}(x)=(p_{\mathrm{vert}}^{(\texttt{r})}+p_{\mathrm{vert}}^{(\texttt{g})}+p_{\mathrm{vert}}^{(\texttt{b})})(x)=\sigma=[(\mathds{1}-\pi_{0}^{(\texttt{r})})+(\mathds{1}-\pi_{0}^{(\texttt{g})})+(\mathds{1}-\pi_{0}^{(\texttt{b})})](\sigma)$
as $\sum_{\texttt{c}}(\mathds{1}-\pi_{0}^{(\texttt{c})})=\mathds{1}$. Again,
as the subspaces of red, green, and blue vertices are disjoint,
$p_{\mathrm{vert}}^{(\texttt{r})}(x)=(\mathds{1}-\pi_{0}^{(\texttt{r})})(\sigma)$.
∎

##  Appendix B Discussion on small-weight uncorrectable errors

In this appendix, we discuss errors with weights $<O(d/2)$ that cannot be
corrected by the concatenated MWPM decoder. We first consider weight-$O(d/3)$
errors, which may be difficult to correct via the projection decoder. We
verify that a specific family of weight-$O(d/3)$ errors that are uncorrectable
via the projection decoder are correctable via the concatenated MWPM decoder.
We then show that there exist weight-$O(3d/7)$ errors that cannot be corrected
by the concatenated MWPM decoder, which implies that the value of $\beta$ in
the ansatz of Eq. (3) may converge to $3/7$ for sufficiently large values of
$d$.

###  B.1 Small-weight errors uncorrectable via the projection decoder but
correctable via the concatenated MWPM decoder

Figure 11:  Example of an error with weight $<d/2$ that may be uncorrectable
via the concatenated MWPM decoder. (a) The error has a weight of $w=O(\xi d)$
for $\xi<1/2$ and is composed of three string operators (one for each color)
terminating at the three boundaries, whose weights are respectively
$w_{\texttt{r}}=O(\xi_{\texttt{r}}d)$,
$w_{\texttt{g}}=O([(\xi-\xi_{\texttt{r}})/2]d)$, and
$w_{\texttt{b}}=w-w_{\texttt{r}}-w_{\texttt{g}}=O([(\xi-\xi_{\texttt{r}})/2]d)$,
where $\xi_{\texttt{r}}\leq\xi$. They are arranged in a way that every pair of
violated checks (say, green and blue) is separated by
$w_{\mathrm{gap}}=O([(1-\xi)/2]d)$ edges of the third color (red). (b) If Eq.
(14) holds, the first-round MWPM on the red-restricted lattice returns a wrong
matching, which leads to a logical error. As an example, the microscopic
picture near the violated checks is illustrated for the case of
$w_{\mathrm{gap}}=3$, where the purple dotted line indicates the matching of
the first-round MWPM, the red squares are the corresponding red edges
$E_{\mathrm{pred}}^{(\texttt{r})}$, the red solid lines are the matching of
the second-round MWPM, and the black triangles indicate the final prediction.
Similarly, decoding on green or blue sub-lattices incurs a logical error if
Eq. (15) or (16) holds. The decoding eventually fails only when all of Eqs.
(14)–(16) are satisfied. (c) The region of $\xi$ and $\xi_{\texttt{r}}$ that
give uncorrectable errors is visualized. The blue dashed lines (i) and (ii)
respectively indicate the boundaries of the regions where Eqs. (14) and
(15)/(16) hold. The gray region corresponds to $\xi_{\texttt{r}}>\xi$, which
is invalid.

In Fig. 10(a), we schematize an error with weight $O(d/3)$ that is
uncorrectable via the projection decoder [13, 14, 17]. The error is composed
of a single-qubit error at the center of the triangular patch and a red string
operator connecting the center and the red boundary, which is drawn as red,
green, and blue solid lines. This error makes a blue check and a green check
(marked as circles) violated. In the green-restricted (blue-restricted)
lattice, the green (blue) check is paired up with the green (blue) boundary,
thus the decoder makes a wrong prediction that causes a logical error. See
Appendix A of Ref. [13] for an explicit example of such an error.

Notably, the above error is correctable via the concatenated MWPM decoder, as
described in Fig. 10(b). Roughly speaking, it is thanks to the strategy to
select the least-weight one among the three predictions
$\quantity{\widetilde{V}_{\mathrm{pred}}^{(\texttt{r})},\widetilde{V}_{\mathrm{pred}}^{(\texttt{g})},\widetilde{V}_{\mathrm{pred}}^{(\texttt{b})}}$,
which are obtained from the sub-decoding procedures of red, green, and blue,
respectively. Namely, MWPM on the red-restricted and red-only lattices, which
are microscopically described in (b-ii) and (b-iii), gives a correct
prediction $\widetilde{V}_{\mathrm{pred}}^{(\texttt{r})}$. Although other two
predictions $\widetilde{V}_{\mathrm{pred}}^{(\texttt{g})}$ and
$\widetilde{V}_{\mathrm{pred}}^{(\texttt{b})}$ make logical errors, their
weights are $O(2d/3)$, thus $\widetilde{V}_{\mathrm{pred}}^{(\texttt{r})}$ is
selected as the final outcome of the decoder.

###  B.2 Small-weight errors uncorrectable via the concatenated MWPM decoder

Figure 12:  Smallest example of an uncorrectable error shown in Fig. 11. The
error, marked as black dots, lies on the code of $d=25$, which is the smallest
possible code distance permitting such errors, and has the weight of
$w=12<d/2$. Three string operators (colored thick lines) constituting the
error have the same weight of $w_{\texttt{r}}=w_{\texttt{g}}=w_{\texttt{b}}=4$
and each pair of violated checks (colored circles) is separated by
$w_{\mathrm{gap}}=7$ edges. The concatenated MWPM decoder cannot correct this
error since it satisfies all of Eqs. (14)–(16).

Alike the Möbius MWPM decoder [17], the concatenated MWPM decoder fails to
overcome the limitation that $O(3d/7)$-weight errors may not be correctable.
We consider an error with weight $w=O(\xi d)$ for $\xi<1/2$ as presented in
Fig. 11(a), which is composed of three string operators (one for each color)
that terminate at the corresponding boundaries and make one check violated for
each color. These string operators have the weights of
$w_{\texttt{r}}=O(\xi_{\texttt{r}}d)$,
$w_{\texttt{g}}=O([(\xi-\xi_{\texttt{r}})/2]d)$, and
$w_{\texttt{b}}=w-w_{\texttt{r}}-w_{\texttt{g}}=O([(\xi-\xi_{\texttt{r}})/2]d)$,
where $\xi_{\texttt{r}}\leq\xi$. Additionally, they are arranged in a way that
each pair of violated checks (say, green and blue) are separated by
$w_{\mathrm{gap}}=O([(1-\xi)/2]d)$ edges of the third color (red); that is, to
move from the violated green check to the blue check, we need to pass at least
$w_{\mathrm{gap}}$ red edges. Note that, if we move the violated blue and
green checks to the violated red check and fuse them, it becomes a non-trivial
string-net operator with weight $d$. When this error occurs, we face a problem
that a first-round MWPM of a sub-decoding procedure can be wrong; for example,
as shown in Fig. 11(b), the MWPM on the red-restricted lattice gives a wrong
matching connecting the violated green and blue checks (drawn as a dotted
purple line) if and only if

$\displaystyle
w_{\mathrm{gap}}=O\quantity(\frac{1-\xi}{2}d)<w_{\texttt{g}}+w_{\texttt{b}}=O\quantity(\quantity(\xi-\xi_{\texttt{r}})d).$
(14)

Then the subsequent MWPM on the red-only lattice causes a logical error.
Similarly, the green sub-decoding fails if and only if

$\displaystyle
w_{\mathrm{gap}}=O\quantity(\frac{1-\xi}{2}d)<w_{\texttt{r}}+w_{\texttt{b}}=O\quantity(\frac{\xi+\xi_{\texttt{r}}}{2}d),$
(15)

and lastly, the blue sub-decoding fails if and only if

$\displaystyle
w_{\mathrm{gap}}=O\quantity(\frac{1-\xi}{2}d)<w_{\texttt{r}}+w_{\texttt{g}}=O\quantity(\frac{\xi+\xi_{\texttt{r}}}{2}d).$
(16)

Since we select the least-weight correction among the three colors, the
decoding eventually fails only when all of Eqs. (14)–(16) hold. The region of
such uncorrectable errors is visualized in Fig. 11(c) on the plane with the
axes of $\xi_{\texttt{r}}$ and $\xi$, while neglecting constant factors. The
minimum of $\xi$ in this region is $3/7$, which corresponds to
$\xi_{\texttt{r}}=1/7$; thus, there may exist errors with weights $\geq
O(3d/7)$ but smaller than $d/2$ that are uncorrectable via the concatenated
MWPM decoder.

We exhaustively search for errors of the above type while increasing $d$ under
the following constraints: (i) The red string operator terminates exactly at
the center qubit of the red boundary, that is, $(d-1)/2$ qubits are placed on
each of the left and right sides of the center qubit along the red boundary.
(ii) The weights of the blue and green string operators differ by up to two.
(iii) The value of $w_{\mathrm{gap}}$ is the same for every pair of the
violated checks. We find that $d=25$ is the smallest code distance that
permits such uncorrectable errors, as shown in the example visualized in Fig.
12, where $d=25$, $w=12$, $w_{\texttt{r}}=w_{\texttt{g}}=w_{\texttt{b}}=4$,
and $w_{\mathrm{gap}}=7$.

##  Appendix C Additional numerical analyses

In this appendix, we present the results of additional numerical analyses.

Figure 13:  Comparison of different color-selecting strategies. We consider
three strategies for the color-selecting step of the concatenated MWPM
decoder: using only the outcome of the sub-decoding procedure of a single
color (r) without a comparison, comparing the outcomes for two colors (r, g),
and comparing the outcomes for all the three colors (which is the original
strategy). The failure rates $p_{\mathrm{fail}}$ under the bit-flip noise
models of $p=0.02$ (left) and $p=0.04$ (right) are plotted against $d$ for
these three strategies. The solid lines indicate the linear regressions of
$\log p_{\mathrm{fail}}$ against $d$: $\log p_{\mathrm{fail}}=-0.33d-3.1$
($p=0.02$, single color), $-0.53d-2.7$ ($p=0.02$, two colors), $-0.61d-2.4$
($p=0.02$, all colors), $-0.14d-2.5$ ($p=0.04$, single color), $-0.22d-2.4$
($p=0.04$, two colors), and $-0.27d-2.3$ ($p=0.04$, all colors), respectively.

Figure 13 compares our color-selecting strategy (i.e., executing the sub-
decoding procedures for all the three colors and selecting the best one) with
two other strategies of performing only one or two sub-decoding procedures. It
plots logical failure rates under the bit-flip noise model of
$p\in\quantity{0.02,0.04}$ for these three strategies, confirming that our
original strategy of using all the three colors significantly outperforms the
others.

Figure 14:  Separate analyses for the $\overline{Z}$\- and
$\overline{X}$-failure of the decoder under near-threshold circuit-level
noise. For the $\overline{Z}$-failure, (a) and (b) are the counterparts of
Figs. 7(b) and (c), respectively. Similarly, (c) and (d) are their
counterparts for the $\overline{X}$-failure. The long-term cross thresholds
$p^{\times,\mathrm{LT}}_{\mathrm{circuit}}$ are estimated as 0.460% for the
$\overline{Z}$-failure and 0.452% for the $\overline{X}$-failure, which differ
by about 1.8%.

Figure 14 presents separate analyses for the $\overline{Z}$\- and
$\overline{X}$-failure of the decoder under near-threshold circuit-level
noise, which are analogous to Figs. 7(b) and (c). The long-term cross
thresholds $p^{\times,\mathrm{LT}}_{\mathrm{circuit}}$ are estimated as 0.460%
for the $\overline{Z}$-failure and 0.452% for the $\overline{X}$-failure,
which differ by about 1.8%. Note that
$p^{\times,\mathrm{LT}}_{\mathrm{circuit}}$ for the overall failure rate is
about 0.456%, which is the average of these two.

Figure 15:  Separate analyses for the $\overline{Z}$\- and
$\overline{X}$-failure of the decoder under sub-threshold circuit-level noise.
For the $\overline{Z}$-failure, (a) and (b) are the counterparts of Figs. 8(a)
and (b), respectively. Similarly, (c) and (d) are their counterparts for the
$\overline{X}$-failure.

Figure 15 presents separate analyses for the $\overline{Z}$\- and
$\overline{X}$-failure of the decoder under sub-threshold circuit-level noise,
which are analogous to Fig. 8. For the $\overline{Z}$-failure, the regressions
of $G(d)$ and $C(d)$ against $d$ and the corresponding ansatz parameters are

$\displaystyle G(d)=(0.48\pm 0.07)(d-12)+(5.4\pm 0.4),\quad C(d)=(2.7\pm
0.5)(d-12)+(25\pm 3),$ $\displaystyle p^{\star}_{\mathrm{circuit}}\approx
3.4\times 10^{-3},\quad\alpha\approx 5.2\times 10^{-3},\quad\beta\approx
0.48,\quad\eta\approx 5.4,\quad d_{0}=12.$

For the $\overline{X}$-failure, they are

$\displaystyle G(d)=(0.53\pm 0.05)(d-12)+(5.5\pm 0.3),\quad C(d)=(3.1\pm
0.5)(d-12)+(26\pm 3),$ $\displaystyle p^{\star}_{\mathrm{circuit}}\approx
3.1\times 10^{-3},\quad\alpha\approx 4.1\times 10^{-3},\quad\beta\approx
0.53,\quad\eta\approx 5.5,\quad d_{0}=12.$

Figure 16:  Analysis of bias between $\overline{Z}$\- and
$\overline{X}$-failure under circuit-level noise. The left figure shows the
scatter plot of the $\overline{Z}$-failure rate $p_{\mathrm{fail}}^{(Z)}$ and
the $\overline{X}$-failure rate $p_{\mathrm{fail}}^{(X)}$ for all the
simulation outcomes in Figs. 7 and 8. The right figure shows the scatter plot
of the logical failure rate $p_{\mathrm{fail}}$ and the bias
$R_{\mathrm{bias}}$ defined in Eq. (8) for all the simulation outcomes in
Figs. 7 and 8. The error bars indicate the 99% confidence intervals of
$R_{\mathrm{bias}}$. For both figures, the dots and error bars are colored
depending on the code distance $d$ (as shown in the right color bar) and the
orange dashed lines represent unbiased cases of
$p_{\mathrm{fail}}^{(Z)}=p_{\mathrm{fail}}^{(X)}$. In the right figure, a
distinct bias is present in a group of data points (enclosed by a dotted
circle), corresponding to cases of $d=3$.

Figure 16 analyzes the bias between $\overline{Z}$\- and
$\overline{X}$-failure in all the circuit-level simulation outcomes of Fig. 7
and 8. It shows two scatter plots: one for the $\overline{Z}$-failure rate
$p_{\mathrm{fail}}^{(Z)}$ and the $\overline{X}$-failure rate
$p_{\mathrm{fail}}^{(X)}$ and the other one for the total failure rate
$p_{\mathrm{fail}}$ and the bias $R_{\mathrm{bias}}$ defined in Eq. (8). We
observe that the 99% confidence intervals of $R_{\mathrm{bias}}$ almost always
include zero, which implies that we cannot reject the null hypothesis that
there is no bias. Exceptionally, bias is not negligible when $d=3$, where
$-0.31\lessapprox R_{\mathrm{bias}}\lessapprox-0.14$, meaning that
$1.4\lessapprox p_{\mathrm{fail}}^{(X)}/p_{\mathrm{fail}}^{(Z)}\lessapprox
2.0$.