# Universal resource-efficient topological measurement-based quantum
computation via color-code-based cluster states

Seok-Hyung Lee  Department of Physics and Astronomy, Seoul National
University, Seoul 08826, Republic of Korea  Hyunseok Jeong
<EMAIL_ADDRESS>Department of Physics and Astronomy, Seoul National
University, Seoul 08826, Republic of Korea

###### Abstract

Topological measurement-based quantum computation (MBQC) enables one to carry
out universal fault-tolerant quantum computation via single-qubit Pauli
measurements with a family of large entangled states called cluster states as
resources. Raussendorf’s three-dimensional cluster states (RTCSs) based on the
surface codes are mainly considered for topological MBQC. In such schemes,
however, the fault-tolerant implementation of the logical Hadamard, phase
($Z^{1/2}$), and $T$ ($Z^{1/4}$) gates which are essential for building up
arbitrary logical gates has not been achieved to date without using state
distillation, while the controlled-not (cnot) gate does not require it, to
best of our knowledge. State distillation generally consumes many ancillary
logical qubits, thus it is a severe obstacle against practical quantum
computing. To solve this problem, we suggest an MBQC scheme via a family of
cluster states called color-code-based cluster states (CCCSs) based on the
two-dimensional color codes instead of the surface codes. We define logical
qubits, construct elementary logical gates, and describe error correction
schemes. We show that all the logical Clifford gates including the cnot,
Hadamard, and phase gates can be implemented fault-tolerantly without state
distillation, although the fault-tolerant $T$ gate still requires it. We
further prove that the minimal number of physical qubits per logical qubit in
a CCCS is at most approximately 1.8 times smaller than the case of an RTCS. We
lastly show that the error threshold of MBQC via CCCSs for logical-$Z$ errors
is 2.7–2.8%, which is comparable to the value for RTCSs, assuming a simple
error model where physical qubits have $X$-measurement or $Z$ errors
independently with the same probability.

##  I Introduction

Three major theoretical challenges for quantum computation (QC) are
universality, fault-tolerance, and resource-efficiency. Universality indicates
the ability of a quantum computer to initialize logical qubits to the
computational basis state, perform any unitary gate, and measure them in the
computational basis. It is known that the controlled-not (cnot), Hadamard, and
phase ($Z^{1/2}$) gates completely generate the Clifford group, and together
with the $T$ ($Z^{1/4}$) gate, any unitary gate may be approximated to an
arbitrary accuracy [1, 2].

To achieve fault-tolerance, various quantum error-correcting (QEC) codes have
been proposed from simple codes with few physical qubits [3, 4, 5, 6, 7] to
topological stabilizer codes defined on lattice structures of qubits allowing
only local interactions which are easily scalable [8]. Several simple codes
also have been demonstrated experimentally in assorted systems for small code
distances [9, 10, 11, 12, 13, 14, 15, 16, 17]. Particularly, the surface codes
[18, 19, 20, 21, 22, 23, 24, 25], a family of topological codes defined on
two-dimensional (2D) lattices, have high error thresholds up to about 12%
[24], thus they are one of the most promising candidates for fault-tolerant
QC. The 2D color codes is another family of topological codes [26, 27, 8, 28]
which enable transversal 111 That a logical gate $U$ is transversal means that
$U$ can be expressed as $U=U_{1}U_{2}\cdots$ such that a unitary operator
$U_{i}$ acts only on the $i$th physical qubit for each logical qubit for all
$i$’s. For example, if $X_{L}:=X_{1}\cdots X_{n}$ for $[[n,1,d]]$ code where
$X_{i}$ is the $X$ operator on the $i$th physical qubit, $X_{L}$ is
transversal. Specific 2D color codes implement the logical Hadamard gate by
the combination of the Hadamard gate on every physical qubit, and similarly
for the logical phase gate [26, 27].  implementation of the logical cnot,
Hadamard, and phase gates thanks to their self-duality. Moreover, three-
dimensional (3D) gauge color codes even allow transversal implementation of
the logical $T$ gate as well as the Clifford gates, thus have been getting
much attention recently [30, 31, 32, 33, 34, 35, 36, 37].

Lastly, fault-tolerant QC typically requires enormous resource overheads,
which makes it tough to realize it. It is not only because a single logical
qubit is composed of multiple physical qubits, but also because state
distillation, which generally demand many ancillary logical qubits, is
required for non-Clifford gates and sometimes for several Clifford gates to be
fault-tolerant [38, 22, 24, 39], e.g., one round of a typical protocol to
distill an
$\ket{A_{L}}:=\frac{1}{\sqrt{2}}\quantity(\ket{0_{L}}+e^{i\pi/4}\ket{1_{L}})$
state for the logical $T$ gate requires 15 ancillary logical qubits [38, 40,
24]. It is therefore desirable to find QC schemes minimizing the need for
state distillation.

Measurement-based QC (MBQC) is an alternative of conventional circuit-based QC
(CBQC), processed only by single-qubit Pauli measurements with a family of
large entangled states called cluster states as resources [41, 42, 43, 44, 40,
45]. The ingredients for generating Cluster states are physical qubits
initialized to the $X$ basis and controlled-$Z$ (cz) gates on them, thus MBQC
requires much fewer types of physical-level operations than typical CBQC. The
initial MBQC schemes via cluster states on 2D planes [41, 42] were universal
but not fault-tolerant. To achieve fault-tolerance, the space should be 3D;
Raussendorf’s 3D cluster states (RTCSs) allow universal and fault-tolerant
MBQC with topologically-encoded logical qubits [43, 44, 40, 45]. Additionally,
it was shown that it can tolerate imperfect preparation of cluster states such
as qubits losses or failed cz gates [46, 47, 48]. MBQC via cluster states is
regarded as one of the suitable candidates for practical fault-tolerant QC,
especially in optical systems [49, 50, 51, 52, 53, 48, 54, 55, 56, 57, 58,
59].

MBQC via RTCSs is powerful from the point of view of universality and fault-
tolerance, but has a significant drawback: the fault-tolerant implementation
of the logical Hadamard, phase, and $T$ gates has not been achieved to date
without using costly state distillation, while the cnot gate does not require
it [43, 44, 40, 45], to best of our knowledge. Fault-tolerant non-Clifford
gates (including the $T$ gate) demand state distillation for most topological
QEC codes, but it is uncommon that it is needed even for some Clifford gates
(the Hadamard and phase gates), which is fatal to resource-efficiency. To
solve this problem, we consider recent studies on generalizing the relation
between RTCSs and surfaces codes to any Calderbank-Steane-Shor (CSS) codes
[60, 61] and later to any stabilizer codes [62]. We also consider Ref. [27] on
2D color code computation introducing “defects” for logical operations since a
similar approach on the surface codes leads to the protocol for MBQC via
RTCSs. Motivated by these works, we propose a new MBQC scheme via a family of
cluster states based on the 2D color codes instead of the surface codes,
called color-code-based cluster states (CCCSs).

Throughout this paper, we show that MBQC via CCCSs is a competitive candidate
on realistic QC, regarding the three challenges mentioned at the very first.
We describe the fault-tolerant implementation of the logical cnot, Hadamard,
and phase gates without state distillation, thus show that arbitrary Clifford
gates do not require it to be fault-tolerant unlike MBQC via RTCSs, although
non-Clifford gates still demand it. We then prove that it requires a smaller
amount of physical qubits per logical qubits than the case of RTCSs, which
makes it resource-efficient even more. Finally, we show that they have a
similar level of fault-tolerance by comparing their error thresholds.

This paper is structured as follows. In Sec. II, we review the concept of
cluster states and the general process of MBQC. In Sec. III, we construct
CCCSs and describe their properties, especially about their stabilizers called
correlation surfaces. In Sec. IV, we define logical qubits and suggest the
schemes for their initialization and measurements, elementary logical gates,
and state injection for state distillation. In Sec. V, we present the methods
for error correction. In Sec. VI, we calculate resource overheads and error
thresholds of MBQC via CCCSs and compare them with the results for RTCSs. We
conclude with final remarks in Sec. VII.

##  II Cluster states and measurement-based quantum computation

Figure 1:  Examples of cluster states. Orange dots and lines indicate vertices
and edges of the graphs, respectively. To construct a cluster state, qubits
initialized to the $\ket{+}=\frac{1}{\sqrt{2}}\quantity(\ket{0}+\ket{1})$
states are placed on the vertices, then a cz gate is applied on the qubits
connected by each edge. (a) A cluster state on a simple graph. The presented
“$XZZZ$” operator indicates an example of a stabilizer generator given in Eq.
(1). (b) A unit cell of a Raussendorf’s 3D cluster state (RTCS). A vertex is
located on each edge and face of the cell.

To define a cluster state, we consider a graph $G=(V,~{}E)$, where $V$ and $E$
are the sets of vertices and edges, respectively. The cluster state $\ket{G}$
is constructed by attaching a qubit to every vertex in $V$, initializing them
to the $\ket{+}$ states where
$\ket{\pm}:=\quantity(\ket{0}\pm\ket{1})/\sqrt{2}$, then applying a
controlled-$Z$ (cz) gate on every pair of qubits connected by an edge.

The constructed cluster state has a stabilizer generator (SG) $S(v)$ for each
vertex $v\in V$ defined as

$\displaystyle S(v):=X(v)\prod_{v^{\prime}\in\mathrm{adj}(v)}Z(v^{\prime}),$
(1)

where $\mathrm{adj}(v):=\quantity{v^{\prime}\in V\mid(v,v^{\prime})\in E}$ is
the set of adjacent vertices of $v$ and $X(v)$ and $Z(v)$ are the $X$ and $Z$
operators, respectively, on the qubit at the vertex $v$ denoted by $Q(v)$. In
other words, $g\ket{G}=\ket{G}$ holds for all $g\in\mathcal{S}$, where
$\mathcal{S}$ is the stabilizer group generated by $\quantity{S(v)|v\in V}$.
We say that $S(v)$ is around $v$ or $Q(v)$, called its center vertex or qubit,
respectively. Examples of cluster states are presented in Fig. 1.

For MBQC, modified versions of cluster states are used, where some qubits do
not need to be initialized to the $\ket{+}$ states. $S(v)$ where $Q(v)$ is
each of such qubits is then no longer a stabilizer, but others still remain as
SGs.

General MBQC via a cluster state to implement a quantum circuit is processed
through the following three steps [41, 42, 44, 40, 45]:

  1. 1.

Preparation. For a given graph $G(V,E)$, a qubit is attached to each vertex.
$Q(V)$ is divided into three subsets: the input qubits $Q_{\mathrm{IN}}$, the
output qubits $Q_{\mathrm{OUT}}$, and the others. $Q_{\mathrm{OUT}}=\emptyset$
if the desired circuit does not produce any output state or ends with
measurements. The input logical states are prepared in $Q_{\mathrm{IN}}$. All
qubits except those in $Q_{\mathrm{IN}}$ are initialized to the $\ket{+}$
states. A cz gate is then applied on every pair of qubits connected by an
edge.

  2. 2.

Measurement. For each physical qubit except those in $Q_{\mathrm{OUT}}$, a
single-qubit Pauli measurement, selected by a measurement pattern with a
classical computer, is performed. The measurement pattern is determined by the
desired circuit. Let the measurement results be $M$. If possible, errors in
$M$ are corrected by decoding the parity-check outcomes.

  3. 3.

Obtaining the results. The output logical state is obtained from
$Q_{\mathrm{OUT}}$ up to logical Pauli operators called byproduct operators
determined by $M$. If $Q_{\mathrm{OUT}}=\emptyset$, the results of the final
logical measurements are determined by $M$.

Note that the preparation and measurement steps may be performed
simultaneously; after a qubit $q$ and its neighbors are prepared and cz gates
are applied on them, it is allowed that $q$ is measured before the other
qubits are prepared. One of the spatial axes may be regarded as the simulating
time axis, or simply the time axis, along which qubits are prepared and then
measured in order. It is thus possible to minimize the number of unmeasured
physical qubits in a moment by measuring each qubit as soon as possible after
preparing it.

The cores of MBQC are the structure of the cluster state and the measurement
pattern. We illustrate them one by one over the next two sections.

##  III Color-code-based cluster states

In this section, we define color-code-based cluster states and describe their
properties. Based on the work on the foliation of CSS codes [60], we consider
a particular family of cluster states derived from a 2D color-code lattice,
called color-code-based cluster states (CCCSs).

###  III.1 Two-dimensional color-code lattices

Figure 2:  Two typical examples of color-code lattices: the (a) 4-8-8 and (b)
6-6-6 lattices. The lattices are 3-valent and have 3-colorable faces.

We first present 2D color-code lattices on which CCCSs are based. We consider
a lattice $\mathcal{L}_{2D}$ on a 2D plane which is 3-valent and has
3-colorable faces; namely, three edges meet at each vertex and one of the
three colors (red, green, or blue) is assigned to each face in such a way that
neighboring faces have different colors. Note that each edge, called link, is
also colorable with the color of the faces it connects. Two typical examples
(4-8-8 and 6-6-6) of such lattices are shown in Fig. 2. In the original 2D
color codes, a qubit is attached to each vertex and two SGs ($X$\- and
$Z$-type) correspond to each face. Details on the codes are described in Ref.
[26, 8].

Figure 3:  (a) Red and (b) blue shrunk lattices of the 4-8-8 color-code
lattice. Red or blue dots (lines) indicate their vertices (edges), which
corresponds to red or blue faces (links) of the original lattices.

Regarding a color-code lattice $\mathcal{L}_{2D}$, three shrunk lattices are
defined, one for each color by shrinking all the faces of that color, as shown
in Fig. 3. For example, in the red shrunk lattice, each vertex corresponds to
a red face in $\mathcal{L}_{2D}$ and each face corresponds to a blue or green
face in $\mathcal{L}_{2D}$. Edges of the red shrunk lattice then correspond to
red links in $\mathcal{L}_{2D}$. The blue and green shrunk lattices are also
defined analogously.

###  III.2 Construction of color-code-based cluster states

Figure 4:  Structure of a color-code-based cluster state (CCCS) based on the
4-8-8 color-code lattice $\mathcal{L}_{2D}$. (a) Structure of a single layer.
Each black circle is a code qubit (CQ) located at a vertex of
$\mathcal{L}_{2D}$. Each colored square is an ancilla qubit (AQ) with that
color, located at the center of a face of $\mathcal{L}_{2D}$ with that color.
Each AQ is connected with surrounding CQs by edges (cz gates), some of which
are drawn as black solid lines. Two adjacent CQs are connected by a link, some
of which are drawn as colored lines. (b) Stack of multiple identical layers
along the simulating time axis. Each pair of two CQs adjacent along the time
axis is connected by an edge, some of which are presented as black solid
lines. One of the primalities (“primal” and “dual”) is alternatively assigned
to each layer. An AQ (a CQ or link) is primal (dual) if it is in a primal
layer, and vice versa for a dual layer. Labels of some elements defined in
Sec. III.2 are shown.

The graph $G$ for a CCCS based on a color-code lattice $\mathcal{L}_{2D}$ has
a 3D structure composed of multiple identical 2D layers stacked along the
simulating time ($t$) axis. The layer of $t=t_{0}$ is referred to as the
$t_{0}$-layer.

The structure of each layer is originated from $\mathcal{L}_{2D}$, as
illustrated in Fig. 4(a) for the case of the 4-8-8 lattice. Each vertex in the
layer is located at either a vertex of $\mathcal{L}_{2D}$ or the center of a
face of $\mathcal{L}_{2D}$; the corresponding qubit is called a code qubit
(CQ) or an ancilla qubit (AQ), respectively. Each AQ is colorable with the
color of the corresponding face in $\mathcal{L}_{2D}$. For each face in
$\mathcal{L}_{2D}$, the layer has an edge connecting the corresponding AQ and
each surrounding CQ, on which a cz gate is applied. Each pair of CQs connected
by a link in $\mathcal{L}_{2D}$ is called link here as well. Note that links
are not edges of $G$.

Next, we stack multiple identical layers along the time axis as shown in Fig.
4(b). Every pair of CQs adjacent along the time axis is connected by an edge
in $G$. The vertices (CQs and AQs) and edges (between CQs and AQs in the same
layer and between CQs in the adjacent layers) constructed above finally
complete the graph $G$ of the cluster state.

We assign each layer, qubit or link a “primality”: either primal or dual. Each
layer is primal (dual) if it has an even (odd) time. An AQ is primal (dual) if
it is in a primal (dual) layer, while a CQ or link is primal (dual) if it is
in a dual (primal) layer. We label each qubit or link in an abbreviated form
with its primality (“p” for primal and “d” for dual), color (“r” for red, “g”
for green, and “b” for blue; omitted for CQs), and type (“AQ,” “CQ,” and “L”
for a link). For example, a pgAQ means a primal green ancilla qubit. We also
frequently use “c” instead of a specific color (r, g, or b) for a variable on
colors.

###  III.3 Stabilizer generators

Figure 5:  Four types of stabilizer generators (SGs) in a CCCS defined in
Definition 1–3: (a) A-, (b) C-, (c) L-, and (d) J-type. Each grey square
indicates a layer. An SG of each type is the tensor product of the marked $X$
or $Z$ operators on the qubits.

We now present stabilizer generators (SGs) of a CCCS. Remark that, for each
vertex $v$ in $G$, $S(v)$ given in Eq. (1) is a SG if $Q(v)$ is initialized to
$\ket{+}$. We define A- and C-type SGs shown in Fig. 5(a) and (b) as follows.

######  Definition 1 (A- and C-type SGs).

An A- or C-type SG is the SG given in Eq. (1) around an AQ or a CQ,
respectively.

The support 222The support of an operator $O$, written as $\mathrm{supp}(O)$,
is the set of qubits on which $O$ applies non-trivially. of a C-type SG is
distributed in three adjacent layers, while that of an A-type SG is contained
in a layer.

Although these two types of SGs completely generate the stabilizer group, we
need another two types of SGs: L- and J-type SGs in Fig. 5(c) and (d).

######  Definition 2 (L-type SG).

The L-type SG around a link $l$ is the product of two C-type SGs whose center
qubits constitute $l$.

######  Definition 3 (J-type SG).

Let $S_{i}:=S\quantity(v_{i})$ for each $i\in\quantity{0,1,2,3}$ be a C-type
SG such that $\quantity(v_{0},v_{1})$, $\quantity(v_{0},v_{2})$, and
$\quantity(v_{0},v_{3})$ are links with different colors.
$S_{I}:=S_{1}S_{2}S_{3}$ is then the J-type SG around the CQ
$Q\quantity(v_{0})$.

A-, L-, and J-type SGs together generate the stabilizer group over-completely.
To see this, regarding a J-type SG $S_{I}$, we consider an L-type SG
$S_{Li}:=S_{0}S_{i}$ for each $i\in\quantity{0,1,2,3}$, where $S_{i}$’s are
defined in Definition 3. Then $S_{0}=S_{L1}S_{L2}S_{L3}S_{I}$ holds, thus any
C-type SG can be written as the product of L- and J-type SGs.

Let the $P$-support $\mathrm{supp}_{P}(O)$ of a multi-qubit Pauli operator $O$
for $P\in\quantity{X,Y,Z}$ be the subset of $\mathrm{supp}(O)$ corresponding
to the $P$ operator. Note that, for every SG regardless of its type, qubits in
its $X$\- and $Z$-support always have different primalities.

###  III.4 Shrunk lattices and correlation surfaces

Almost every discussion from now on is symmetric between the two primalities.
Thus, throughout the rest of this paper, we frequently discuss only one of
them, which implies that the other side can be treated similarly.

We now construct the shrunk lattices of a CCCS, which are analogous to those
of the 2D color codes in Fig. 3. We then define correlation surfaces [43, 44,
40] within each shrunk lattice, through which logical gates are built for
MBQC.

Figure 6:  Unit cells of the primal shrunk lattices of an 4-8-8 CCCS: (a) a
blue cell in the primal red shrunk lattice $\mathcal{L}^{\textup{{pr}}}$ (a
green cell is identical except the colors of AQs) and (b) red and green cells
in the primal blue shrunk lattice $\mathcal{L}^{\textup{{pb}}}$. p$t$s and
d$t$s indicate primal and dual layers, respectively. Some qubits on the last
layer are not displayed. All the pcAQs are vertices of
$\mathcal{L}^{\textup{{pc}}}$. Each spacelike (or timelike) edge, visualized
as red or blue solid lines, connects two adjacent vertices in a layer (or
different layers) and corresponds to a pcL (or dcAQ). Faces and cells are
defined naturally with the edges.

The primal c-colored shrunk lattice $\mathcal{L}^{\textup{{pc}}}$ is a 3D
lattice containing every pcAQ as a vertex. Note that the vertices are only in
primal layers. There are two types of edges connecting them: “spacelike” and
“timelike” edges. Each spacelike edge corresponds to a pcL and connects two
vertices in a layer. Each timelike edge connects two vertices adjacent along
the time axis and contains a dcAQ between them. Faces and cells are then
naturally defined by the vertices and edges. Cells in each primal shrunk
lattice are visualized in Fig. 6 for 4-8-8 CCCSs. Note that each primal layer
in $\mathcal{L}^{\textup{{pc}}}$ is identical with the c-colored shrunk
lattice of the 2D color code on which the CCCS is based.

Table 1:  Qubits $Q(b)$ corresponding to each element (vertex, edge, face, or cell) $b$ in $\mathcal{L}^{\textup{{pc}}}$. The results for $\mathcal{L}^{\textup{{dc}}}$ can be obtained by changing each p or d.  Element $b$ in $\mathcal{L}^{\textup{{pc}}}$ | Qubits $Q(b)$
---|---
Vertex ($\in\mathcal{B}^{\textup{{c}}}_{0}$) | pcAQ
Edge ($\in\mathcal{B}^{\textup{{c}}}_{1}$) | Timelike | dcAQ
Spacelike |  dcL (two dCQs)
Face ($\in\mathcal{B}^{\textup{{c}}}_{2}$) | Timelike |  pcL (two pCQs)
Spacelike |  pc′AQ ($\textup{{c}}^{\prime}\neq\textup{{c}}$)
Cell ($\in\mathcal{B}^{\textup{{c}}}_{3}$) |  dc′AQ ($\textup{{c}}^{\prime}\neq\textup{{c}}$)
Figure 7:  (a) Timelike joint of primal correlation surfaces (CSs) originated
from a J-type SG. The $X$ or $Z$ operators on the qubits indicate the support
of the resulting CS. A series of CQs along which the three faces meet is
marked as a purple dashed line. (b) Example of the construction of a spacelike
joint of three primal CSs. A primal layer of an 4-8-8 CCCS is presented. We
first assume a timelike pg-CS $S$ ending at the green dashed line. We then
expand $S$ by multiplying the A-type SGs around the pAQs marked with purple
triangles. After the expansion, $\mathrm{supp}_{X}(S)$ contains the marked
pAQs, and $\mathrm{supp}_{Z}(S)$ contains the CQs along the red and blue solid
lines. The area above (below) the green line can be regarded as a pr(b)-CS, in
the sense that it may be expanded by multiplying ordinary pr(b)-CSs. A joint
of the three CSs is thus constructed, and $S$ is the corresponding joined CS.
The qubits in $\mathrm{supp}_{Z}S$ inside the area A or B exactly match with
the final layer of a timelike joint, thus spacelike and timelike joints may be
connected. (c) Example of a general joint, obtained by multiplying a series of
timelike and spacelike joints together with ordinary CSs.

Each element (vertex, edge, face, or cell) in a shrunk lattice corresponds to
an AQ or a link, as presented in Table 1. Here $Q(b)$ for an element $b$
denotes the set of qubits corresponding to $b$. Note that an element is
colorable with the color of AQ or link corresponding to it. In particular,
cells and spacelike faces have colors different from the color of the shrunk
lattice, e.g., $\mathcal{L}^{\textup{{pr}}}$ is composed of green and blue
cells.

We now regard the shrunk lattices as chain complexes [43, 44, 40]. Let
$\mathcal{B}_{i}^{\textup{{pc}}}$ for $i=0$, 1, 2, or 3 be the set of
vertices, edges, faces, or cells in $\mathcal{L}^{\textup{{pc}}}$,
respectively. We then consider a vector space $H_{i}^{\textup{{pc}}}$
generated by $\mathcal{B}_{i}^{\textup{{pc}}}$ over $\mathbb{Z}_{2}$. Each
primal shrunk lattice may be regarded as a chain complex:
$\mathcal{L}^{\textup{{pc}}}=\quantity{H_{3}^{\textup{{pc}}},H_{2}^{\textup{{pc}}},H_{1}^{\textup{{pc}}},H_{0}^{\textup{{pc}}}}$.
Each element $h_{i}\in H_{i}^{\textup{{pc}}}$ is called an $i$-chain and
corresponds to a set
$B\quantity(h_{i})\subseteq\mathcal{B}_{i}^{\textup{{c}}}$ where each $b\in
B\quantity(h_{i})$ has nonzero contribution in $h_{i}$. For example, if
$f_{1}$, $f_{2}$, and $f_{3}$ are faces in $\mathcal{L}_{2}^{\textup{{pc}}}$,
$h_{2}:=f_{1}+f_{2}+f_{3}$ is a 2-chain in $H_{2}^{\textup{{pc}}}$ and
$B\quantity(h_{2})=\quantity{f_{1},f_{2},f_{3}}$ holds. The correspondence is
one-to-one, thus we do not distinguish $h_{i}$ and $B\quantity(h_{i})$ from
now on if it is not confusing. The chain complex $\mathcal{L}^{\textup{{pc}}}$
has a boundary map $\partial$ which maps $h_{i}\in H_{i}^{\textup{{pc}}}$ to
$\partial h_{i}\in H_{i-1}^{\textup{{pc}}}$ corresponding to the geometrical
boundary of $h_{i}$. Note that $\partial$ is a linear map and satisfies
$\partial\circ\partial=0$.

For an $i$-chain $h_{i}$ and $P\in\quantity{X,Y,Z}$, we define a multi-qubit
Pauli operator $P\quantity(h_{i})$ by

$\displaystyle P\quantity(h_{i}):=\prod_{q\in Q(h_{i})}P(q),$

where $Q(h_{i}):=\bigcup_{b_{i}\in h_{i}}Q(b_{i})$ and $P(q)$ is the tensor
product of the $P$ operator on the qubit $q$ and the identity operator on all
the other qubits. We now define correlation surfaces (CSs), essential elements
for constructing logical operations through MBQC.

######  Definition 4 (Correlation surface).

For each 2-chain $h_{2}\in H_{2}^{\textup{{p(d)c}}}$, the operator

$\displaystyle
S_{\textup{{CS}}}\quantity(h_{2}):=X\quantity(h_{2})Z\quantity(\partial
h_{2}).$ (2)

is a primal (dual) c-colored correlation surface, referred to as a “p(d)c-CS.”

It is straightforward to see that, for a spacelike or timelike face $f$,
$S_{\textup{{CS}}}\quantity(f)$ is an A- or L-type SG around the AQ or link
corresponding to $f$, respectively. The following theorem relates general
2-chains to stabilizers of the CCCS.

######  Theorem 1 (CSs as stabilizers).

For a 2-chain $h_{2}$, $S_{\textup{{CS}}}\quantity(h_{2})$ is a stabilizer if
and only if $Q\quantity(h_{2})\cap Q_{\mathrm{IN}}=\emptyset$, where
$Q_{\mathrm{IN}}$ is the set of input qubits defined in Sec. II which are not
initialized to the $\ket{+}$ states.

###### Proof.

(If part) Since qubits outside $Q_{\mathrm{IN}}$ is initialized to the
$\ket{+}$ states, there exist the A- or C-type SG around each of them, as
discussed in Sec. II. Let
$F:=\quantity{f\in\mathcal{B}_{2}^{\textup{{pc}}}\mid Q(f)\cap
Q_{\mathrm{IN}}=\emptyset}$ be a set of faces. For a face $f\in F$,
$S_{\textup{{CS}}}\quantity(f)$ is a stabilizer; it is an A- or L-type SG. For
a 2-chain $h_{2}\in H_{2}^{\textup{{pc}}}$ where $Q\quantity(h_{2})\cap
Q_{\mathrm{IN}}=\emptyset$, $h_{2}$ can be written as a linear summation of
elements in $F$: $\exists\quantity{f_{i}}\subseteq F$, $h_{2}=\sum_{i}f_{i}$.
Since the map $\partial$ is linear and
$P(h)P\quantity(h^{\prime})=P\quantity(h+h^{\prime})$ holds for any Pauli
operator $P$,
$S_{\textup{{CS}}}\quantity(h_{2})=X\quantity(h_{2})Z\quantity(\partial
h_{2})=\prod_{i}X\quantity(f_{i})Z\quantity(\partial
f_{i})=\prod_{i}S_{\textup{{CS}}}\quantity(f_{i})$, which is a stabilizer. The
proof is analogous for dual 2-chains.

(Only if part) Since qubits in $Q_{\mathrm{IN}}$ are not initialized to the
$\ket{+}$ states, the A- and C-type SGs around each of them do not exist.
Therefore, the $X$-support of any stabilizer cannot contain qubits in
$Q_{\mathrm{IN}}$. ∎

Regarding a primal CS $S:=S_{\textup{{CS}}}\quantity(h_{2})$,
$Q\quantity(h_{2})$ is called the interior of $S$, in which every qubit is
primal and in $\mathrm{supp}_{X}(S)$. Similarly, $Q\quantity(\partial h_{2})$
is called the boundary of $S$, in which every qubit is dual and in
$\mathrm{supp}_{Z}(S)$. We say that $S$ is timelike (spacelike) if $h_{2}$ is
composed of timelike (spacelike) faces only.

CSs discussed above include all A- and L-type SGs, but not J-type SGs in Fig.
5(d). Each J-type SG can be regarded as three primal timelike CSs with
different colors “joined” along a timelike series of CQs as Fig. 7(a), in the
sense that each “wing” of a color c may be extended by multiplying ordinary
pc-CSs. Note that the CQs along the joint are not included in the support.

Figure 8:  (a) Schematic diagram of a defect (pb-D) and a db-CS $S$ ending at
the defect. The cylinder indicates the defect area and the purple lines
indicate the defect, a 1-chain $h_{1}^{\textup{{db}}}\in
H_{1}^{\textup{{db}}}$. Qubits corresponding to $h_{1}^{\textup{{db}}}$ are
measured in the $Z$ basis. (b) Schematic diagram of a pg-CS surrounding a
pb-D. (c) A primal layer in a 4-8-8 CCCS penetrated by a timelike pb-D. The
cross-section of the defect area is displayed as a checkered pattern. Each
purple triangle with a solid (dashed) border indicates a defect pbAQ (pCQ) in
the layer (next layer) measured in the $Z$ basis. The cross-sections of a
timelike db-CS ending at the defect and a timelike pg-CS surrounding it are
presented as a blue solid line and a green dashed line, respectively. The
solid (or dashed) lines indicate faces bisected by the layer (or ending at the
layer). That is, the corresponding qubits are on the layer (or an adjacent
layer). (d) A dual layer in a 4-8-8 CCCS containing a spacelike pb-D. The
defect area is displayed as a checkered pattern. A db-CS ending at the defect
is visualized as a blue surface, where the blue line corresponds to its
boundary.

A question arising naturally may be about “spacelike” joints, and those are
also possible as presented in Fig. 7(b). A timelike pc-CS and two spacelike
primal CSs with the other two colors may be joined along a spacelike series of
pcLs. Such a joint can be obtained by multiplying several A-type SGs along a
spacelike boundary of the timelike CS. Note that the ends of spacelike and
timelike joints may fit perfectly with each other, in the sense that all the
$Z$ operators on the joint cancel out when multiplying them.

A general joint of CSs with different colors can be obtained as Fig. 7(c) by
multiplying several spacelike and timelike joints together with ordinary CSs.
We refer to such a primal CS with a joint as a “pj-CS.” For consistency with
ordinary CSs, we define the interior (boundary) of a pj-CS by its
$X$($Z$)-support, which is intuitive considering its visualization in Fig. 7.

##  IV Measurement-based quantum computation via color-code-based cluster
states

In this section, we describe MBQC via CCCSs. We first introduce defects and
define logical qubits using them. We then describe initialization and
measurements of logical qubits and construct elementary logical gates
including the identity, cnot, Hadamard, and phase gates, which together
generate the Clifford group. We lastly present the state injection scheme to
prepare an arbitrary logical state and implement the logical $T$ gate.

Each logical initialization, measurement, gate, or state injection process can
be regarded as an independent circuit “block” implemented by the process
presented in Sec. II. In each block, the input logical state is given in the
input qubits $Q_{\mathrm{IN}}$ ($Q_{\mathrm{IN}}=\emptyset$ for the
initialization) and the output logical state is produced in the output qubits
$Q_{\mathrm{OUT}}$ ($Q_{\mathrm{OUT}}=\emptyset$ for the logical measurements)
after the single-qubit Pauli measurements of all the qubits except
$Q_{\mathrm{OUT}}$. An arbitrary quantum circuit can be formed by connecting
multiple blocks in a way that the output qubits of each block are used as the
input qubits of the next block.

Without loss of generality, we assume that the single-qubit measurements are
performed layer by layer along the simulating time ($t$) axis. In that case,
the output qubits of an initialization, gate, or state injection block are the
last several layers of it, called the output layers. On the other hands, it is
sufficient that the input qubits of a measurement or gate block contain only
the first layer of it, called the input layer. Two subsequent blocks can be
connected in a way that the input layer of the second block overlap with the
first output layer of the first block. To see this, let us assume that the
output layers of the first block are the layers of $t_{0}\leq t\leq t_{1}$. We
first consider applying all the cz gates between qubits of $t_{0}\leq t\leq
t_{1}$ again on the post-measurement state of the first block. Since the
measurements of the qubits of $t<t_{0}$ commute with those cz gates, the
qubits of $t_{0}<t\leq t_{1}$ simply return to the initial $\ket{+}$ states.
The $t_{0}$-layer is then used for the input layer of the second block and the
cz gates in the second block restore the output state of the first block to be
used as the input state of the second block. Of course, the above argument is
just a theoretical trick to connect two blocks; it is unnecessary to apply cz
gates multiple times in a real implementation.

###  IV.1 Measurement pattern

Remark that each qubit except the output qubits is measured in a Pauli basis
determined by a predefined measurement pattern. Such a qubit is included in an
area with one of the four types: vacuum, defect, Y-plane, and injection qubit.
There may be multiple defects, Y-planes, and injection qubits, and the entire
remaining area is the vacuum. We denote the set of all vacuum (defect) qubits
as $V$ ($D$).

Defects are key ingredients for the protocol; all the logical operations
completely depend on how to place them. Y-planes are used in fault-tolerant
$Y$-measurements on physical qubits for the logical Hadamard and phase gates.
Lastly, each injection qubit is a special area for state injection and
consists of a single qubit. Qubits in each area are measured as follows:

$\displaystyle\begin{array}[]{cc}\text{A qubit is measured}\\\ \text{in the
basis of}\end{array}\left\\{\begin{array}[]{ll}X&\text{if in the vacuum}\\\
&\text{or an injection qubit,}\\\ Z&\text{if in a defect,}\\\ Y&\text{if in a
Y-plane.}\\\ \end{array}\right.$ (9)

Arranging these elements besides the vacuum properly is the key for
implementing logical qubits and gates, which is what we cover in this section.

###  IV.2 Defects and related correlation surfaces

Defects are defined as follows and visualized in Fig. 8(a) schematically.

######  Definition 5 (Defect).

Consider a defect area, a continuous area stretching along a direction. A
primal (dual) c-colored defect, referred to as a “p(d)c-D,” is the largest
1-chain $h_{1}\in H_{1}^{\textup{{d(p)c}}}$ contained completely in the defect
area. Qubits in $Q\quantity(h_{1})$ are called defect qubits and measured in
the $Z$ basis during the measurement step.

We say that a defect is timelike or spacelike if the defect area stretches
timelikely or spacelikely, respectively. Figure 8(c) and (d) illustrate the
explicit structures of timelike and spacelike defects, respectively, in an
4-8-8 CCCS.

After the measurement step, only CSs commuting with the measurement pattern
survive. We say a CS is compatible with a set of qubits if it survives after
the measurements of the qubits. If it is compatible with all the qubits except
the output qubits, we say that it is a compatible CS. The following theorem
gives the conditions which such CSs satisfy.

######  Theorem 2 (Compatible CSs).

Considering only the vacuum and defects, a CS $S$ is compatible with a set
$\widetilde{Q}$ of qubits if and only if the followings hold: $\displaystyle
Q_{\mathrm{int}}(S)\cap\widetilde{Q}\setminus Q_{\mathrm{OUT}}$
$\displaystyle\subseteq V\setminus Q_{\mathrm{IN}},$ (10a) $\displaystyle
Q_{\mathrm{bnd}}(S)\cap\widetilde{Q}\setminus Q_{\mathrm{OUT}}$
$\displaystyle\subseteq D,$ (10b) where $Q_{\mathrm{int(bnd)}}(S)$ is the
interior (boundary) of $S$ and $Q_{\mathrm{IN(OUT)}}$ is the set of input
(output) qubits.

We particularly want to emphasize that a compatible CS cannot end in the
vacuum qubits. Note that $Q_{\mathrm{IN}}$ is excluded in the right-hand side
(RHS) of Eq. (10a) due to Theorem 1.

Table 2:  Allowed positional relations between a primal defect $d$ and a
compatible CS. The relations for dual defects are analogous.  With a pc-D $d$,
a xy-CS $S$ …
---
x y | c | $\textup{{c}}^{\prime}(\neq\textup{{c}})$
p |  | can overlap with $d$
---
only if $S$ is spacelike
cannot overlap with $d$
d | can end at $d$ | cannot end at $d$

Table 2 shows allowed positional relations between a pc-D $d$ and a compatible
CS with each primality and color, derived from Theorem 10 and Table 1. Remark
that $d$ is composed of pcAQs and pCQs. A pc′-CS has primal interior qubits
which should be measured in the $X$ basis for the CS to be compatible, thus
can overlap with $d$ unless they share common qubits, which is possible only
if $\textup{{c}}^{\prime}=\textup{{c}}$ and the overlapped region of the CS is
spacelike 333 If this is the case, the interior qubits of the CS correspond to
spacelike faces in $\mathcal{L}^{\textup{{pc}}}$, which are
$\textup{{pc}}^{\prime\prime}\textup{{AQ}}$s
($\textup{{c}}^{\prime\prime}\neq\textup{{c}}$) according to Table 1. They are
surely not be in the pc-D. Otherwise, the pc′-CS and defect share at least one
qubit if they overlap. . Since its boundary qubits are dual, it cannot end at
$d$. A dc′-CS has primal boundary qubits, thus can end at $d$ if the boundary
qubits are in $d$, which is possible if $\textup{{c}}^{\prime}=\textup{{c}}$
444 The boundary qubits of a dc-CS correspond to edges in
$\mathcal{L}^{\textup{{dc}}}$, which are pcAQs or pcLs. . Since its interior
qubits are dual, it can freely pass $d$.

We mainly concern two types of CSs with respect to a pc-D: pc-CSs surrounding
the defect and dc-CSs ending at it, as shown schematically in Fig. 8(a) and
(b) and explicitly in Fig. 8(c) and (d). Each of such CSs is compatible with
all the qubits except the boundary qubits in the two ends about the direction
of the defect.

###  IV.3 Defining a logical qubit

We first define connected 1-chains as follows.

######  Definition 6 (Connected 1-chain).

A 1-chain $h_{1}$ is connected if and only if it satisfies $\quantity|\partial
h_{1}|\leq 2$. It is regarded to be closed if $\quantity|\partial h_{1}|=0$
and open otherwise.

Figure 9:  Definition of a primal logical qubit and its initialization and
measurement. (a) Schematic diagram of a primal logical qubit composed of three
parallel primal timelike defects with different colors. Blue dashed lines
indicate 1-chains $h_{1}^{X\textup{{dbr}}}$ and $h_{1}^{X\textup{{pbr}}}$,
which constitute $\mathrm{supp}_{X}\quantity(X_{L})$ and
$\mathrm{supp}_{Z}\quantity(X_{L})$, respectively. Red, green, and blue dotted
lines indicate 1-chains $h_{1}^{Z\textup{{r}}}$, $h_{1}^{Z\textup{{g}}}$, and
$h_{1}^{Z\textup{{b}}}$, respectively, which constitute
$\mathrm{supp}_{Z}\quantity(Z_{L})$ except the pCQ $q_{I}$ at which they end.
$\mathrm{supp}_{X}\quantity(X_{L})$ and $\mathrm{supp}_{Z}\quantity(Z_{L})$
meet at a pCQ $q_{\mathrm{anti}}$, thus they anticommute with each other. (b)
Structure of $Z_{L}$ near $q_{I}$ in a 4-8-8 CCCS. Colored lines are
$h_{1}^{Z\textup{{r}}}$, $h_{1}^{Z\textup{{g}}}$, and $h_{1}^{Z\textup{{b}}}$,
respectively. Purple triangles indicate $\mathrm{supp}\quantity(Z_{L})$. (c)
$X_{L}$\- and (d) $Z_{L}$-initialization. A logical qubit prepared in the
output layers $Q_{\mathrm{OUT}}$ ($t_{0}$\- and $\quantity(t_{0}+1)$-layer).
For the $X_{L}$-initialization, the defects are made to start from the
$t_{0}$-layer. For the $Z_{L}$-initialization, they are extended to meet at a
point before the layer-$t_{0}$. $X_{L}$ ($Z_{L}$) is then a part of a pb-CS
$S_{X}$ (dj-CS $S_{Z}$) which is a stabilizer. After the measurement step, the
logical qubit in $Q_{\mathrm{OUT}}$ is initialized to $\ket{\pm_{L}}$
($\ket{0_{L}}$ or $\ket{1_{L}}$), depending on the measurement result of
$X_{L}S_{X}$ ($Z_{L}S_{Z}$). (e) $X_{L}$\- and (f) $Z_{L}$-measurement of a
logical qubit inserted through the input layer ($t_{0}$-layer). Each of them
is done by reversing the corresponding initialization process. There then
exists a pb-CS $S_{X}$ (dj-CS $S_{Z}$) which is a stabilizer, such that the
measurement result of $S_{X}X_{L}$ ($S_{Z}Z_{L}$) determine the
$X_{L}$($Z_{L}$)-measurement result.

To define a logical qubit, we consider three parallel timelike defects with
different colors passing through the $t_{0}$\- and $\quantity(t_{0}+1)$-layer
for a given integer $t_{0}$, as visualized schematically in Fig. 9(a). The
constructed logical qubit is primal (dual) if the defects are primal (dual)
and $t_{0}$ is odd (even).

We define a logical qubit by specifying the logical-$X$ ($X_{L}$) and
logical-$Z$ ($Z_{L}$) operators. To define $X_{L}$, we consider two closed
connected spacelike 1-chains $h_{1}^{X\textup{{dcc}}^{\prime}}\in
H^{\textup{{dc}}}_{1}$ and $h_{1}^{X\textup{{pcc}}^{\prime}}\in
H^{\textup{{pc}}}_{1}$ for a given pair of different colors
$\quantity(\textup{{c}},\textup{{c}}^{\prime})$.
$h_{1}^{X\textup{{dcc}}^{\prime}}$ is located in the $t_{0}$-layer and
surrounding the $\textup{{pc}}^{\prime}\textup{{-D}}$.
$h_{1}^{X\textup{{pcc}}^{\prime}}$ is defined by parallelly moving
$h_{1}^{X\textup{{dcc'}}}$ one unit positively along the time axis. An example
of $X_{L}$ is shown in Fig. 9(a) for the case of
$\quantity(\textup{{c}},\textup{{c}}^{\prime})=\quantity(\textup{{b}},\textup{{r}})$.
Note that the two 1-chains consist of pcLs and dcLs, respectively. We then
define

$\displaystyle
X_{L}:=F_{X}^{\textup{{cc}}^{\prime}}\quantity(t_{0}):=X\quantity(h_{1}^{X\textup{{dcc}}^{\prime}})Z\quantity(h_{1}^{X\textup{{pcc}}^{\prime}}).$
(11)

Note that
$\mathrm{supp}_{Z}\quantity(X_{L})=Q\quantity(h_{1}^{X\textup{{pcc'}}})$ may
be in the boundary of a pc-CS since the boundary is a 1-chain in
$H^{\textup{{pc}}}_{1}$ as well. The colors c and $\textup{{c}}^{\prime}$ can
be any pair of different colors, and they are proven to be equivalent in Sec.
IV.5.2.

For the $Z_{L}$ operator, we consider an open connected spacelike 1-chain
$h_{1}^{Z\textup{{c}}}\in H^{\textup{{dc}}}_{1}$ for each color c, which is
located in the $t_{0}$-layer and connects the pc-D and a common pCQ $q_{I}$,
as shown in Fig. 9(a) and (b). Note that $h_{1}^{Z\textup{{c}}}$ is composed
of pcLs. We define

$\displaystyle Z_{L}$ $\displaystyle:=F_{Z}\quantity(t_{0})$
$\displaystyle:=Z\quantity(h_{1}^{Z\textup{{r}}})Z\quantity(h_{1}^{Z\textup{{g}}})Z\quantity(h_{1}^{Z\textup{{b}}})Z\quantity(q_{I}).$
(12)

Note that $q_{I}$ is out of $\mathrm{supp}\quantity(Z_{L})$. It is worth
noticing that $\mathrm{supp}\quantity(Z_{L})$ may be in the boundary of a dj-
CS, which is verifiable by comparing $\mathrm{supp}\quantity(Z_{L})$ and the
structure of a timelike joint of CSs shown in Fig. 7(c).

$X_{L}$ and $Z_{L}$ defined above anticommute with each other, considering
that $\mathrm{supp}_{Z}\quantity(Z_{L})$ and
$\mathrm{supp}_{X}\quantity(X_{L})$ meet at a pCQ $q_{\mathrm{anti}}$ in Fig.
9(a). A dual logical qubit is defined analogously, but now the logical
operators are defined oppositely; $\mathrm{supp}\quantity(Z_{L})$ surrounds a
defect and $\mathrm{supp}\quantity(X_{L})$ ends at each defect.

###  IV.4 Initialization and measurement of a logical qubit

We first describe initializing a primal logical qubit to an eigenstate of
$X_{L}$ or $Z_{L}$. Initialization of a dual logical qubit can be analogously
done. As mentioned at the beginning of this section, in each block of logical
initialization, there is no input layer and the initialized state is prepared
in the output layers $Q_{\mathrm{OUT}}$ ($t_{0}$\- and
$\quantity(t_{0}+1)$-layer) after the measurement step.

The $X_{L}$-initialization of a primal logical qubit is done by making the
defects start from the $t_{0}$-layer. $X_{L}$ given in Eq. (11) is then a part
of a “cup-shaped” pc-CS $S_{X}$ as shown in Fig. 9(c). Since $X_{L}S_{X}$ has
the support out of the output qubits and commutes with each single-qubit
measurement in the measurement step, the post-measurement state is an
eigenstate of $X_{L}S_{X}$. $S_{X}$ is a stabilizer both before and after the
measurement step due to Theorems 1 and 10. Therefore, the post-measurement
state is also an eigenstate of $X_{L}$ and the eigenvalue is determined by the
measurement result of $X_{L}S_{X}$.

The $Z_{L}$-initialization of a primal logical qubit is done by extending the
defects to meet at a qubit before the $t_{0}$-layer, as shown in Fig. 9(d).
$Z_{L}$ given in Eq. (12) is then a part of a dj-CS $S_{Z}$ which is a
stabilizer. From an analogous argument, the post-measurement state is an
eigenstate of $Z_{L}$ and the eigenvalue is determined by the measurement
result of $Z_{L}S_{Z}$.

The $X_{L}$\- or $Z_{L}$-measurement is done by reversing the time order from
the corresponding initialization process, as shown in Fig. 9(e) and (f). This
time, $Q_{\mathrm{IN}}$ is the $t_{0}$-layer and $Q_{\mathrm{OUT}}$ is empty.
Regarding the $X_{L}$-measurement, there exists a pb-CS $S_{X}$ which is a
stabilizer before the measurement step such that $X_{L}S_{X}$ commutes with
each single-qubit measurement in the measurement step. Therefore, $X_{L}$ is
equivalent to $X_{L}^{\prime}:=X_{L}S_{X}$; namely,
$\expectationvalue{X_{L}}{\psi}=\expectationvalue{X_{L}^{\prime}}{\psi}$ holds
for every stabilized state $\ket{\psi}$ before the measurement step, thus
redefining $X_{L}$ to $X_{L}^{\prime}$ does not change the logical state
encoded in $\ket{\psi}$. The measurement result of $X_{L}^{\prime}$ can be
directly obtained from the results of the measurement step. The
$Z_{L}$-measurement process can be verified analogously.

###  IV.5 Elementary logical gates

####  IV.5.1 Identity gate

Figure 10:  Logical identity gate of a primal logical qubit between the input
layer $Q_{\mathrm{IN}}$ ($t_{0}$-layer) and the output layers
$Q_{\mathrm{OUT}}$ ($t_{1}$\- and $\quantity(t_{1}+1)$-layer). The gate is
constructed by extending the defects from $Q_{\mathrm{IN}}$ to
$Q_{\mathrm{OUT}}$. The logical-$X$ operator in $Q_{\mathrm{IN}}$
($Q_{\mathrm{OUT}}$) is $X_{L}$ ($X^{\prime}_{L}$), and $Z_{L}$ and
$Z^{\prime}_{L}$ are defined similarly. (a) $X_{L}$ is transformed into
$X^{\prime}_{L}$ via a pb-CS $S_{X}$ surrounding the red defect, and (b)
$Z_{L}$ is transformed into $Z^{\prime}_{L}$ via a dj-CS $S_{Z}$ ending at the
three defects. Double lines indicate error chains causing logical errors
covered in Sec. V.1.

The identity gate of a primal logical qubit is constructed just by extending
the defects along the time axis between $Q_{\mathrm{IN}}$ ($t_{0}$-layer) and
$Q_{\mathrm{OUT}}$ ($t_{1}$\- and $\quantity(t_{1}+1)$-layer) as shown in Fig.
10. Let $X_{L}$ and $X^{\prime}_{L}$ be the logical-$X$ operators of the input
and output logical qubits, respectively: $X_{L}:=F_{X}^{\textup{{br}}}(t_{0})$
and $X_{L}^{\prime}:=F_{X}^{\textup{{br}}}(t_{1})$, where
$F_{X}^{\textup{{br}}}(\cdot)$ is given in Eq. (11). We consider a pb-CS
$S_{X}$ which surrounds the pr-D and ends at
$\mathrm{supp}_{Z}\quantity(X_{L})$ and
$\mathrm{supp}_{Z}\quantity(X_{L}^{\prime})$, as shown in Fig. 10(a). Since
$S_{X}$ is a stabilizer, $X_{L}$ is equivalent to

$\displaystyle\widetilde{X}_{L}:=S_{X}X_{L}=\quantity(\bigotimes_{q\in
V_{X}}X(q))X_{L}^{\prime},$ (13)

where $V_{X}:=\mathrm{supp}\quantity(S_{X}X_{L}X_{L}^{\prime})\subset
V\setminus Q_{\mathrm{OUT}}$. After the measurements of the qubits of
$t<t_{1}$, $\widetilde{X}_{L}$ is transformed into

$\displaystyle\quantity(\prod_{q\in
V_{X}}x_{q})X^{\prime}_{L}:=x_{X}X^{\prime}_{L},$

where $x_{q}$ ($z_{q}$) is the $X$($Z$)-measurement result of the qubit $q$.
In other words,

$\displaystyle\expectationvalue{\widetilde{X}_{L}}{\psi}=\expectationvalue{x_{X}X_{L}^{\prime}}{\psi^{\prime}}$
(14)

holds, where $\ket{\psi}$ and $\ket{\psi^{\prime}}$ are the states before and
after the measurements (see Appendix A for the proof).

We do a similar thing on the $Z_{L}$ operators. Denoting those of the input
and output logical qubits as $Z_{L}$ and $Z_{L}^{\prime}$, respectively, we
consider a dj-CS $S_{Z}$ ending at $\mathrm{supp}\quantity(Z_{L})$,
$\mathrm{supp}\quantity(Z^{\prime}_{L})$, and the defects, as Fig. 10(b).
$Z_{L}$ is then equivalent to

$\displaystyle\widetilde{Z}_{L}:=S_{Z}Z_{L}=\quantity(\bigotimes_{q\in
V_{Z}}X(q))\quantity(\bigotimes_{q\in D_{Z}}Z(q))Z_{L}^{\prime},$

where $V_{Z}:=\mathrm{supp}_{X}\quantity(S_{Z}Z_{L}Z_{L}^{\prime})\subset
V\setminus Q_{\mathrm{OUT}}$ and
$D_{Z}:=\mathrm{supp}_{Z}\quantity(S_{Z}Z_{L}Z_{L}^{\prime})\subseteq
D\setminus Q_{\mathrm{OUT}}$. After the measurements of the qubits of
$t<t_{1}$, $\widetilde{Z}_{L}$ transforms into $x_{Z}z_{Z}Z_{L}^{\prime}$
where $x_{Z}:=\prod_{q\in V_{Z}}x_{q}$ and $z_{Z}:=\prod_{q\in D_{Z}}z_{q}$.

The transformations of the logical operators are summarized as

$\displaystyle X_{L}\rightarrow x_{X}X_{L}^{\prime},\qquad Z_{L}\rightarrow
x_{Z}z_{Z}Z_{L}^{\prime}.$ (15)

More explicitly, they are written as

$\displaystyle\expectationvalue{X_{L}}{\psi}$
$\displaystyle=\expectationvalue{x_{X}X_{L}^{\prime}}{\psi^{\prime}},$
$\displaystyle\expectationvalue{Z_{L}}{\psi}$
$\displaystyle=\expectationvalue{x_{Z}z_{Z}Z_{L}^{\prime}}{\psi^{\prime}},$

where $\ket{\psi}$ and $\ket{\psi^{\prime}}$ are the states before and after
the measurement step, respectively. Therefore, the input logical state
$\ket{\psi_{L}}$ encoded in $\ket{\psi}$ with the logical Pauli operators
$\quantity{X_{L},Z_{L}}$ is transformed into

$\displaystyle\ket{\psi_{L}^{\prime}}=X^{(1-x_{Z}z_{Z})/2}Z^{(1-x_{X})/2}\ket{\psi_{L}}$

encoded in $\ket{\psi^{\prime}}$ with the logical Pauli operators
$\quantity{X_{L}^{\prime},Z_{L}^{\prime}}$. This transformation corresponds to
the identity gate up to some byproduct operators determined by the measurement
results. The byproduct operators can be handled by a software to be delayed to
the end of the entire circuit and finally merged with the logical measurements
[24].

The above arguments show the basic ideas for implementing logical gates.
Regarding $n$ logical qubits, let $P_{Li}$ for each $P\in\quantity{X,Z}$ and
integer $i\leq n$ denote the logical-$P$ operator of the $i$th logical qubit.
To construct a general logical gate $U$ for $n$ logical qubits, one should
find a configuration of defects (and Y-planes for some gates) where a CS
$S_{Pi}$ exists for each $P_{Li}$ satisfying the following conditions:

######  Condition 1.

$S_{Pi}$ should connect $P_{Li}$ of the input logical qubits and
$UP_{Li}U^{\dagger}$ of the output logical qubits. $X_{L}$ ($Z_{L}$) of a
logical qubit can be connected with primal (dual) CSs.

######  Condition 2.

$S_{Pi}$ should be compatible with all the qubits except the output qubits and
$\mathrm{supp}\quantity(P_{Li})$; it satisfies the relationships shown in
Table 2 in that region.

If such CSs exist, the configuration implements the desired logical gate with
some byproduct operators obtained from the measurement results.

####  IV.5.2 cnot and primality-switching gates

Figure 11:  Construction of the cnot gate between a primal logical qubit
(target) and a dual one (control). Each colored single (double) line indicates
the primal (dual) defect of the corresponding color.
$Z_{L}^{\textup{{p}}}\otimes I_{L}^{\textup{{d}}}$ is transformed into
$Z_{L}^{\textup{{p}}}\otimes Z_{L}^{\textup{{d}}}$ via the presented dj-CS.

We first consider the logical cnot gate between a primal logical qubit
(target) and a dual one (control). Figure 11 illustrates the defect
configuration, where the pg-D of the primal logical qubit and the dr-D of the
dual one are twisted one round with each other, which is commonly called
defect braiding. The logical Pauli operators are transformed as

$\displaystyle X_{L}^{\textup{{p}}}I_{L}^{\textup{{d}}}$
$\displaystyle\rightarrow X_{L}^{\textup{{p}}}I_{L}^{\textup{{d}}},\qquad
I_{L}^{\textup{{p}}}X_{L}^{\textup{{d}}}\rightarrow
X_{L}^{\textup{{p}}}X_{L}^{\textup{{d}}},$ $\displaystyle
Z_{L}^{\textup{{p}}}I_{L}^{\textup{{d}}}$ $\displaystyle\rightarrow
Z_{L}^{\textup{{p}}}Z_{L}^{\textup{{d}}},\qquad
I_{L}^{\textup{{p}}}Z_{L}^{\textup{{d}}}\rightarrow
I_{L}^{\textup{{p}}}Z_{L}^{\textup{{d}}},$ (16)

where the tensor product symbols and the sign terms such as $x_{X}$, $x_{Z}$,
and $z_{Z}$ in Eq. (15) are omitted, and each superscript p or d indicates the
primality of the logical qubit. The above transformation is exactly the
Heisenberg picture of the cnot gate where the primal logical qubit is the
target.

We need to find CSs satisfying two Conditions presented in Sec. IV.5.1 to
verify the transformations in Eq. (16). A dual CS for the transformation of
$Z_{L}^{\textup{{p}}}\otimes I_{L}^{\textup{{d}}}$ is presented schematically
in Fig. 11. Note that the “tunnel” of the CS along the dr-D must be formed
since the dr-D cannot overlap with a dg-CS (see Table 2). A CS for
$I_{L}^{\textup{{p}}}\otimes X_{L}^{\textup{{d}}}$ can be constructed
analogously; now, a tunnel of a pr-CS is made along the pg-D. The other two
transformations are straightforward.

Figure 12:  (a) Construction of the primality-switching gate changing a primal
logical qubit to a dual one. $Z_{L}^{\textup{{p}}}$ is transformed into
$Z_{L}^{\textup{{d}}}$ via the presented dj-CS. (b) Circuit equivalent to the
primality-switching gate. $M_{Z}^{\textup{{p}}}$ is the $Z_{L}$-measurement on
the primal qubit, and the result is $z_{\textup{{p}}}$.

Exploiting the cnot gate discussed above, it is possible to make the
primality-switching gate which changes a primal logical qubit to a dual one,
by “closing” the input part of the dual one and the output part of the primal
one, as shown in Fig. 12(a). Remark that these closures indicate the
$Z_{L}$-measurement of the primal one and the $X_{L}$-initialization of the
dual one. The modified configuration is thus equivalent to the circuit in Fig.
12(b) up to byproduct operators, which implements the identity or $X_{L}$ gate
while changing the primality. Alternatively, this result is directly
obtainable by finding appropriate CSs; for example, the dj-CS in Fig. 12(a)
verify the transformation of $Z_{L}^{\textup{{p}}}$ to $Z_{L}^{\textup{{d}}}$.
The primality-switching gate from a dual logical qubit to a primal one can be
made in a similar manner.

The primality-switching gate enables the cnot gate between logical qubits with
arbitrary primalities. Regardless of the primalities of the input logical
qubits, one can switch them to primal (target) or dual (control), and apply
the cnot gate in Fig. 11.

Note that the equivalence between the different definitions of the $X_{L}$
operator, related to the choice of the color pair
$(\textup{{c}},\textup{{c}}^{\prime})$ in Eq. (11), can be proven with the
primality-switching gate. We consider a chain of two primality-switching
gates: primal $\rightarrow$ dual $\rightarrow$ primal. No matter how $X_{L}$
is defined in the first primal logical qubit, it becomes symmetric about the
color in the dual one. We can thus transform it into any definition of $X_{L}$
in the final primal one.

####  IV.5.3 Hadamard gate

To construct the logical Hadamard gate, the logical Pauli operators should be
transformed as

$\displaystyle X_{L}\rightarrow Z_{L},\qquad Z_{L}\rightarrow X_{L}.$ (17)

It is simple if the gate is located just after the state injection presented
in the Sec. IV.6: injecting the unencoded state to a dual logical qubit
instead of a primal one. This method is valid since the definitions of $X_{L}$
and $Z_{L}$ are opposite for primal and dual logical qubits.

Figure 13:  Construction of the Hadamard gate from a primal logical qubit to a
dual one. Each colored single (double) line is the primal (dual) defect of
that color. The presented dj-CS $S_{Z\textup{{p}}}$ and pj-CS
$S_{X\textup{{d}}}$ end at the three primal or dual defects and the
$\quantity(t_{H}+1)$\- or $t_{H}$-layer, respectively. The presented pr-CS
$S_{X\textup{{p}}}$ and dr-CS $S_{Z\textup{{d}}}$ surround the pg-D or dg-D
and end at the $t_{H}$\- or $\quantity(t_{H}-1)$-layer, respectively.
$S_{ZX}:=S_{Z\textup{{p}}}S_{X\textup{{p}}}$ and
$S_{XZ}:=S_{X\textup{{p}}}S_{Z\textup{{d}}}$ transform the logical Pauli
operators as Eq. (17). The supports of $S_{ZX}$ and $S_{XZ}$ are marked as
colored dashed lines. For the $Y$-measurements to be fault-tolerant, a dual
Y-plane is placed on the $t_{H}$-layer and primal Y-planes are placed on the
$\quantity(t_{H}-1)$\- and $\quantity(t_{H}+1)$-layer.

If the Hadamard gate is located in the middle of the circuit, it is a bit
tricky. Since $X_{L}$ and $Z_{L}$ of a logical qubit can be connected only
with primal or dual CSs, respectively, there should be a CS having different
primalities near the input and output layers, to achieve the transformation.
To solve this problem, we construct a defect structure starting with a primal
logical qubit and ending with a dual one as shown in Fig. 13, where the primal
one stops at the primal $t_{H}$-layer and the dual one starts from the dual
$\quantity(t_{H}+1)$-layer. Each pair of defects with the same color must have
exactly the same spatial structure at $t=t_{H}$ and $t=t_{H}+1$. Note that
such a configuration is possible thanks to the self-duality of the 2D color
codes which makes primal and dual layers have exactly the same structure.

We consider two pairs of overlapping primal and dual CSs:
$\quantity(S_{Z\textup{{p}}},S_{X\textup{{d}}})$ and
$\quantity(S_{X\textup{{p}}},S_{Z\textup{{d}}})$, where $S_{X\textup{{p}}}$,
$S_{Z\textup{{p}}}$, $S_{X\textup{{d}}}$, and $S_{Z\textup{{d}}}$ are a pr-CS,
dj-CS, pj-CS, and dr-CS defined in Fig. 13, respectively.
$S_{ZX}:=S_{Z\textup{{p}}}S_{X\textup{{d}}}$ then transforms $Z_{L}$ of the
input primal logical qubit to $X_{L}$ of the output dual one. Similarly,
$S_{XZ}:=S_{X\textup{{p}}}S_{Z\textup{{d}}}$ transforms the input $X_{L}$ to
the output $Z_{L}$. Condition 1 in Sec. IV.5.1 is thus satisfied with these
two “hybrid” CSs. What remains is Condition 2. Since $S_{ZX}$ and $S_{XZ}$
contain $Y$ operators on some CQs in the overlapping regions, the qubits
should be measured in the $Y$ basis for the CSs to be compatible.

To make the $Y$-measurements fault-tolerant, we introduce Y-planes:

######  Definition 7 (Y-plane).

A primal (dual) Y-plane is the set of p(d)CQs in a continuous area contained
in a dual (primal) layer. CQs in Y-planes are measured in the $Y$ basis.

Errors in Y-planes can be corrected by an error correction procedure presented
in Sec. IV.2. Therefore, the $Y$-measurements for the Hadamard gate can be
fault-tolerantly done by placing wide enough Y-planes to cover
$\mathrm{supp}_{Y}\quantity(S_{ZX})$ and $\mathrm{supp}_{Y}\quantity(S_{XZ})$
completely.

####  IV.5.4 Phase gate

Figure 14: Circuit for the logical phase gate of a system logical qubit ($S$)
with an ancilla logical qubit ($A$). $M_{Y}^{A}$ is the $Y_{L}$-measurement on
the ancilla qubit with the result of $y_{A}$.

We now complete the generating set of the Clifford group with the construction
of the logical phase ($S_{L}$) gate. The phase gate is achieved indirectly by
utilizing an ancilla logical qubit; the circuit in Fig. 14 implements $S_{L}$
if the $Y_{L}$-measurement of the ancilla logical qubit gives the result of
$+1$ and $S_{L}Z_{L}$ if the result is $y_{A}=-1$.

Figure 15:  (a) pj-CS $S_{X}$ and (b) dj-CS $S_{Z}$ for the
$Y_{L}$-measurement of a primal logical qubit. Near the input layer, $S_{X}$
connected with $X_{L}$ of the input logical qubit has the form of a pb-CS
surrounding the pr-D. On the $t_{1}$-layer, it is divided into three CSs with
different colors through a spacelike joint. Each CS is then deformed
appropriately so that the joint is extended along the black dashed line. The
1-chains (colored dotted lines) on the $t_{2}$-layer are in the $X$-support of
$S_{X}$. On the $t_{3}$-layer, the joint becomes spacelike again. After that,
$S_{X}$ has the form of a pb-CS until the $t_{4}$-layer on which $S_{X}$ is
closed. $S_{Z}$ simply connects $Z_{L}$ and the 1-chains (colored dashed
lines) on the $t_{2}$-layer. (c) $\mathrm{supp}\quantity(S_{Z}S_{X}Y_{L})$ on
the $t_{2}$-layer. A Y-plane is placed to cover
$\mathrm{supp}_{Y}\quantity(S_{Z}S_{X}Y_{L})$. The junction of the pb-D and
the blue 1-chain is explicitly shown below.

All the elements in the circuit already have been described except the
$Y_{L}$-measurement. For the $Y_{L}$-measurement of a input primal logical
qubit, we extend the defects straight along the time axis to a layer
($t_{2}$). As shown in Fig. 15, there exists a pj-CS $S_{X}$ (connected with
$X_{L}$) and dj-CS $S_{Z}$ (connected with $Z_{L}$) which are stabilizers,
such that $S_{Z}S_{X}Y_{L}=i\quantity(S_{Z}Z_{L})\quantity(S_{X}X_{L})$
contains $X$ operators on vacuum qubits and $Y$ operators along “Y”-shaped
connected 1-chains on the $t_{2}$-layer. Hence, the $Y_{L}$-measurement can be
done by placing a Y-plane on the $t_{2}$-layer as Fig. 15(c).

We conclude that all the elements in the circuit of Fig. 14 can be implemented
fault-tolerantly, thus the fault-tolerant phase gate can be made up to
byproduct operators.

###  IV.6 State injection

Preparation of an arbitrary logical qubit $a\ket{0_{L}}+b\ket{1_{L}}$ is
essential for implementing the logical $T$ gate as well as quantum computation
with arbitrary input states. This is done in our scheme by injecting the
corresponding unencoded state into a physical qubit.

Figure 16:  State injection procedure. (a) An unencoded state is injected into
an injection qubit $q_{\mathrm{inj}}$, which is the only input qubit, in the
pr-D which is spacelike and thicknessless at $q_{\mathrm{inj}}$.
$Z\quantity(q_{\mathrm{inj}})$ is invariant when the cz gates associated with
$q_{\mathrm{inj}}$ are applied. However, $X\quantity(q_{\mathrm{inj}})$ is
transformed into $S\quantity(q_{\mathrm{inj}})$, where
$S\quantity(q_{\mathrm{inj}})$ is the C-type SG around $q_{\mathrm{inj}}$.
$S\quantity(q_{\mathrm{inj}})$ is equivalent to
$S_{\textup{{CS}}}\quantity(h_{2}^{\textup{{pb}}})$ since
$S_{\textup{{CS}}}\quantity(h_{2}^{\textup{{pb}}})=S\quantity(q_{\mathrm{inj}})S\quantity(q_{1})$,
where $h_{2}^{\textup{{pb}}}\in H_{2}^{\textup{{pb}}}$ is the timelike 2-chain
marked as a blue dashed line and $q_{1}$ is the marked CQ adjacent to
$q_{\mathrm{inj}}$. $q_{\mathrm{inj}}$ is measured in the $X$ basis during the
measurement step. (b) $S_{\textup{{CS}}}\quantity(h_{2}^{\textup{{db}}})$ is
transformed into $X_{L}$ of the output logical qubit via the pb-CS $S_{X}$.
$Z\quantity(q_{\mathrm{inj}})$ is transformed into $Z_{L}$ of the output
logical qubit via the dj-CS $S_{Z}$.  Figure 17:  (a) Explicit structure of a
parity-check operator (PC), specifically a pb-PC in a 4-8-8 CCCS. Purple
triangles indicate its $X$-support qubits. (b) A $Z$ or $X$-measurement
($M_{X}$) error on a pcAQ flips two pc-PCs sandwiching $q$. (c) A dual layer
of a 4-8-8 CCCS is presented. Purple triangles indicate the pCQs with errors.
Each c-colored face corresponds to a flipped pc-PC, where an example is shown
in (a) as a blue face on the dual layer. (d) A primal blue error chain (pb-
EC), where every qubit along a connected dual 1-chain $h_{1}^{\textup{{db}}}$
has an error, flips two pb-PCs located at its two ends. (e) Starting from an
error on a pCQ $q_{I}$, a pj-EC is constructed by multiplying a pc-EC ending
at the flipped pc-PC for each color c to the error operator. A pj-EC flips
three primal PCs located at its ends.

We start from the configuration for the $Z_{L}$-initialization of a primal
logical qubit shown in Fig. 9(c), where three defects meet at a point. First,
a qubit $q_{\mathrm{inj}}$ in the pc-D for any color c is selected as an
injection qubit which is the only input qubit in $Q_{\mathrm{IN}}$. We assume
that the defect is “thicknessless” at $q_{\mathrm{inj}}$; namely, its cross-
section at $q_{\mathrm{inj}}$ contains at most one qubit as shown in Fig.
16(a). The desired initial state is injected into $q_{\mathrm{inj}}$ in an
unencoded form $\ket{\psi}=a\ket{0}+b\ket{1}$, then the associated cz gates
are applied. Remark that $q_{\mathrm{inj}}$ is measured in the $X$ basis as
stated in Eq. (9). The $X$ ($Z$) operator on $q_{\mathrm{inj}}$ is transformed
into $X_{L}$ ($Z_{L}$) up to a sign factor as shown in Fig. 16, thus the
logical state $\ket{\psi_{L}}=a\ket{0_{L}}+b\ket{1_{L}}$ is prepared up to
byproduct operators.

Note that the state injection procedure is inherently not fault-tolerant,
since it uses an unprotected single-qubit state and the defect is
thicknessless at $q_{\mathrm{inj}}$. Therefore, magic state distillation is
essential for the faithful $T$ gate.

##  V Error correction

Now we describe error correction schemes in CCCSs. The scheme varies with the
area of the qubits: the vacuum, defects, and Y-planes.

###  V.1 Error correction in the vacuum and defects

For error correction in the vacuum, we exploit parity-check operators (PCs)
defined as follows:

######  Definition 8 (Parity-check operator).

For each cell $c$, the CS

$\displaystyle S_{\textup{{CS}}}(\partial c)=X(\partial c)$

is a parity-check operator (PC), where $S_{\textup{{CS}}}(\cdot)$ is given in
Eq. (2).

PCs are classified into six groups according to primalities and cell colors.
Here, the primality of a PC $S_{\textup{{CS}}}\quantity(\partial c)$ is that
of the shrunk lattice $\mathcal{L}$ containing the cell $c$, and its cell
color is the color of the AQ $Q\quantity(c)$. Remark that the cell color is
different from the color of $\mathcal{L}$, as shown in Table 1. We refer to a
primal c-colored PC as a “pc-PC.”

Remark that a given dcAQ $q$ corresponds to two primal cells, one for each of
$\mathcal{L}^{\textup{{pc}}_{1}}$ and $\mathcal{L}^{\textup{{pc}}_{2}}$ where
c, $\textup{{c}}_{1}$, and $\textup{{c}}_{2}$ are all different colors.
However, the PCs corresponding to the cells are indeed the same, comparing
Fig. 6(a) and (b) as an example. We can thus regard that one AQ ($q$)
corresponds to one PC, and denote it as $S_{\textup{{PC}}}(q)$. The support of
the pc-PC $S_{\textup{{PC}}}(q)$ for a dcAQ $q$ contains two pcAQs and
multiple pCQs around $q$ as shown in Fig. 17(a)

We first consider only vacuum qubits. Since they are measured in the $X$
basis, all PCs survive as stabilizers after the measurement step. Any $Z$
error before the measurement or any $X$-measurement ($M_{X}$) error flips
several PC outcomes. Note that $X$ errors do not affect the outcomes at all,
so can be ignored. The final step for error correction is to decode errors
from them and correct the errors.

An error may occur on either an AQ or a CQ. An error on a pcAQ $q$ flips two
pc-PCs sandwiching $q$ along the time axis as shown in Fig. 17(b). An error on
a pCQ $q$ flips pr-PC, pg-PC, and pb-PC surrounding $q$ spatially, as shown in
Fig. 17(c). If both the pCQs constituting a pcL $l$ have errors, the two pc-
PCs connected by $l$ are flipped.

Combining the above facts, we conclude that, if every qubit in
$Q(h_{1}^{\textup{{dc}}})$ for a connected dual 1-chain
$h_{1}^{\textup{{dc}}}\in H_{1}^{\textup{{dc}}}$ has an error, the pc-PC
$S_{\textup{{PC}}}(q)$ for each qubit $q\in Q(\partial h_{1}^{\textup{{dc}}})$
is flipped, as shown in Fig. 17(d). Such an error set in the vacuum is called
a primal c-colored error chain, referred to as a “pc-EC.” Formally, a pc-EC is
written as the tensor product of the $Z$ operators on the error qubits.
Furthermore, starting from an error on a pCQ, each flipped PC may be “moved”
by multiplying a primal error chain of the corresponding color ending at the
PC. An error set constructed by this way flips three primal PCs located at its
ends and is referred to as a “pj-EC.” General error chains are obtained by
connecting multiple pc-ECs for each color c and pj-ECs.

Figure 18:  PCs deformed or created due to a timelike pb-D in a 4-8-8 CCCS. A
cross-section of the defect on a primal layer is presented. Each purple
triangle with a solid (or dashed) border indicates a defect qubit on the layer
(or an adjacent dual layer). Although each of the two pg-PCs and one pr-PC
marked is incompatible with the defect, their product is compatible, thus it
can be used for error correction. However, the marked pb-PC cannot be merged
with other PCs in such a way, thus there is no choice but to discard it, which
makes a pb-EC ending at it (blue double solid line) undetectable. A dg-EC
surrounding the defect (green double dashed line) located in an adjacent dual
layer is another nontrivial undetectable set of errors. Some dual CSs
including the presented db-CS additionally survive and can be used to detect
errors in both the vacuum and defect.

We now investigate the effects of a pc-D $d$ to the nearby PCs. First, all
primal PCs whose supports contain any defect qubit no longer survive, while
dual PCs are unaffected. Such incompatible PCs may be multiplied with each
others to form larger compatible stabilizers, as shown in Fig. 18 where two
pg-PCs and a pr-PC are merged. Like normal PCs, these merged PCs also can
detect errors, although decoding errors from PCs may get more ambiguous. Some
PCs for which such multiplication is impossible have no choice but to be
discarded, as the pb-PC in Fig. 18. As a consequence, a pc-EC ending at $d$ is
not detected by any PC near $d$.

A pc-D may make some dual CSs survive additionally. The dc-CS
$S_{\textup{{CS}}}(f)$ for a face $f\in\mathcal{B}_{2}^{\textup{{dc}}}$, where
$Q\quantity(\partial f)$ is in the defect as shown in Fig. 18, is compatible,
thus can serve as a PC for detecting errors. We call such CSs defect PCs. A
notable thing is that they may detect not only errors on vacuum qubits but
also $X$ or $Z$-measurement ($M_{Z}$) errors on defect qubits.

We then identify nontrivial undetectable error chains, where “nontrivial” here
means that they incur logical errors. Such an error chain is closed or ends at
defects with the same primality and color. Considering the identity gate of a
primal logical qubit, the shortest error chain inducing an $X_{L}$ error is a
pj-EC ending at the three defects, and the shortest one inducing a $Z_{L}$
error is a closed dc-EC surrounding the $\textup{{pc}}^{\prime}\textup{{-D}}$
($\textup{{c}}^{\prime}\neq\textup{{c}}$), as shown schematically in Fig. 10
and explicitly in Fig. 18. Note that a closed dc-EC penetrating a defect is
detected by defect PCs, although not detected by ordinary PCs. The code
distance of a logical qubit is defined by the size of the smallest nontrivial
undetectable error set, and it increases as the defects get thicker or get
farther from each other 555 Such an error set may not be an error chain,
because errors in defects may also be nontrivial and undetectable. However,
since error correction in defects gets more accurate as the defects get
thicker, the dependency of the code distance to their thicknesses is still
valid. It can be verified that the smallest nontrivial undetectable error set
containing only defect qubits completely covers a cross-section of the defect,
thus its size is roughly a quadratic function of the circumference of the
defect. .

###  V.2 Error correction in Y-planes

Figure 19:  (a) Two types of hybrid PCs. Each cube is a pc-PC (blue solid
line) or dc-PC (orange double line) which constitutes a hybrid PC and may be
open, where the colored faces indicate the open faces. $Y$-support qubits of
the hybrid PCs are marked as purple circles, and their $X$-support qubits
originally in the p(d)c-PCs are marked as blue (orange) circles. (b) For three
consecutive Y-planes, a hybrid PC may be placed in the presented four ways.
Errors in the Y-planes may be corrected using the outcomes of such hybrid PCs
covering the entire Y-planes.

To correct errors in Y-planes, we use hybrid PCs defined with open PCs, which
are visualized in Fig. 19(a).

######  Definition 9 (Open PC).

For a cell $c$ and a face $f\in\partial c$, an open PC is
$S_{\textup{{CS}}}(\partial c)S_{\textup{{CS}}}(f)$, where $f$ determines the
direction toward which it is open.

######  Definition 10 (Hybrid PC).

A hybrid PC is the product of primal and dual PCs of the same color which are
adjacent along the time axis and may be open toward each other. It is type-1
if one of the two composing PCs is open, while it is type-2 if both of them
are open.

Figure 20:  $Z_{L}$ error probability $P_{\mathrm{log}}$ versus physical-level
error probability $p_{\mathrm{phys}}=p_{Z}+p_{M_{X}}-p_{Z}p_{M_{X}}$, where
$p_{Z}$ ($p_{M_{X}}$) is the $Z$ ($X$-measurement) error probability on vacuum
qubits, for different code distances with respect to (a) 4-8-8 CCCSs, (b)
6-6-6 CCCSs, and (c) RTCSs. The graphs in the upper row show the results for
$0.001\leq p_{\mathrm{phys}}\leq 0.1$, and those in the lower row show the
results near the threshold values. Pale areas around the lines indicate the
99% confidence intervals of $P_{\mathrm{log}}$. The error thresholds are
calculated as 2.7% for 6-6-6 CCCSs, 2.8% for 4-8-8 CCCSs, and 3.3% for RTCSs,
which are shown as grey dashed lines.

Remark that CQs in Y-planes are measured in the $Y$ basis, thus ordinary PCs
whose supports contain those CQs are incompatible with the qubits. Instead of
them, we use hybrid PCs whose $Y$-supports are on the Y-planes, as shown in
Fig. 19(b). Error correction in the Y-planes is done with a set of hybrid PCs
covering the entire Y-planes.

##  VI Calculations

###  VI.1 Resource overheads

We now calculate and compare the resource overheads of MBQC via RTCSs or
CCCSs. For each case, we consider a periodic hexagonal arrangement of parallel
timelike primal defects, where primal logical qubits with the code distances
of $d$ are compactly packed in the space. In other words, the intervals of the
arrangement are determined to minimize the number of physical qubits per
logical qubit while keeping all the possible nontrivial undetectable error
chains to contain $d$ or more qubits. We present such arrangements of defects
in Appendix B.

Table 3:  Resource overheads of MBQC via RTCSs or CCCSs, evaluated by the numbers of physical qubits ($n$) and cz gates ($N_{\mathrm{\textsc{cz}}}$) per layer in terms of the code distance ($d$) and the number of logical qubits ($k$), regarding optimal hexagonal arrangements of parallel timelike primal defects. Only the leading-order terms on $d$ are presented. Two types of color codes are considered: the 4-8-8 and 6-6-6 lattices.  Types of cluster states | $n/k$ | $N_{\mathrm{\textsc{cz}}}/k$
---|---|---
RTCS | $\approx 6.6d^{2}$ | $\approx 13.1d^{2}$
4-8-8 CCCS | $\approx 3.9d^{2}$ | $\approx 10.5d^{2}$
6-6-6 CCCS | $\approx 3.7d^{2}$ | $\approx 9.8d^{2}$

Table 3 shows the calculated numbers of physical qubits ($n$) and cz gates
($N_{\mathrm{\textsc{cz}}}$) per layer in terms of $d$ and the number of
logical qubits ($k$), considering the optimal hexagonal arrangements. It is
worth noticing that MBQC via CCCSs is definitely more resource-efficient than
MBQC via RTCSs; $n/k$ is about 1.7–1.8 times smaller for CCCSs than for RTCSs.
Note that the compact packing of logical qubits may be unrealistic; extra
spaces may be needed for implementing logical gates except the identity gate.

###  VI.2 Error thresholds

We numerically calculate and compare error thresholds of MBQC via RTCSs and
CCCSs.

####  VI.2.1 Error model

We assume a simple error model where vacuum qubits have $Z$ ($M_{X}$) errors
independently with the same probability $p_{Z}$ ($p_{M_{X}}$). Since a $Z$
error just before the measurement and an $M_{X}$ error have the same effect,
it is enough to consider the net error probability
$p_{\mathrm{phy}}:=p_{Z}+p_{M_{X}}-p_{Z}p_{M_{X}}$. Note that $X$ errors on
the vacuum qubits do not affect the $X$-measurement results at all, thus we
neglect them.

####  VI.2.2 Simulation methods

For each simulation with a code distance of $d$, we consider the logical
identity gate of a primal logical qubit covering consecutive $2T+1$ layers
with $T=4d+1$ starting from a primal layer. Simplified defect models presented
in Appendix C.1 are used, instead of considering big areas containing the
entire defects. We calculate the $Z_{L}$ error probability per layer with the
Monte Carlo method; we repeat a sampling cycle many times enough to obtain a
desired confidence interval of the $Z_{L}$ error probability. Each cycle is
structured as follows.

We first prepare a cluster state whose shape and size are determined by $d$
and $T$. Here we assume perfect preparation, namely, no qubit losses or
failures of cz gates. Errors are then randomly assigned to primal qubits with
a given probability $p_{\mathrm{phy}}$, except those in the first and final
layers to prevent error chains ending at these layers. After that, the
outcomes of primal PCs are calculated, then decoded to locate errors. Edmonds’
minimum-weight perfect matching (MWPM) algorithm [67, 68, 69] via Blossom V
software [70] is used for decoding (once for RTCSs and six times for CCCSs),
where the details are presented in Appendix C.2. We then identify primal error
chains connecting different defects which incur $Z_{L}$ errors by comparing
the assigned and decoded errors. We count such error chains while repeating
the cycles and obtain the $Z_{L}$ error probability per layer
$P_{\mathrm{log}}$. The error threshold $p_{\mathrm{thrs}}$ is obtained from
the calculated $P_{\mathrm{log}}$ results for different values of $d$ and
$p_{\mathrm{phy}}$; $P_{\mathrm{log}}$ decreases as $d$ increases if
$p_{\mathrm{phy}}<p_{\mathrm{thrs}}$ and vice versa otherwise.

####  VI.2.3 Results

Figure 20 shows the results of the simulations. The obtained error thresholds
are $p_{\mathrm{thrs}}\approx 3.0\%$ for 4-8-8 and 6-6-6 CCCSs and
$p_{\mathrm{thrs}}\approx 3.5\%$ for RTCSs. The values for CCCSs are slightly
lower than the value for RTCSs, but they have similar orders of magnitude.

##  VII Remarks

In this paper, we have proposed a new topological measurement-based quantum
computation (MBQC) scheme via color-code-based cluster states (CCCSs). We have
shown that our scheme is comparable with or even better than the conventional
scheme via Raussendorf’s 3D cluster states (RTCSs) [43, 44, 40, 45], in the
three aspects mentioned at the very beginning:

  1. 1.

Universality. Initialization and measurements of logical qubits and all the
elementary logical gates constituting a universal set of gates (cnot,
Hadamard, phase, and $T$ gates) can be implemented via appropriate placement
of defects and Y-planes. We described each one of them explicitly in Sec. IV.

  2. 2.

Fault-tolerance. We suggested the error correction scheme for each area of
qubits in Sec. V. We further verified in Sec. VI.2 that the error thresholds
for $Z$ or $X$-measurement errors have a similar order of magnitude comparing
with the value for RTCSs.

  3. 3.

Resource-efficiency. Contrary to the case of using RTCSs, the Hadamard and
phase gates do not require state distillation, which typically consumes many
ancillary logical qubits [38, 40, 22], as shown in Sec. IV.5, thanks to the
nature of the self-duality of the 2D color codes. Moreover, we found out in
Sec. VI.1 that the minimal number of physical qubits per logical qubit in our
scheme is about 1.7–1.8 times smaller than the value for RTCSs. As a
consequence, MBQC via CCCSs requires a significantly smaller amount of
resources than MBQC via RTCSs.

We particularly emphasize the last aspect on resource-efficiency as a definite
improvement from the previous schemes, which makes our scheme a more easy-to-
implement alternative to those.

Our work has several limitations. First, the logical $T$ gate still needs
costly state distillation. Some methods to significantly reduce the cost of
distillation have been proposed, such as using logical qubits with low code
distances as ancilla qubits [71] or exploiting redundant ancilla encoding and
flag qubits [72]. Moreover, 3D gauge color codes [30, 31, 32, 33, 34, 35, 36,
37] enables the implementation of a universal set of gates without
distillation. It may be possible to translate these protocols to be applicable
for our MBQC scheme. We also assume the perfect preparation of states, which
is unrealistic. It is unclear how much the fault-tolerance gets weaker if we
consider qubits losses or failures of cz gates, which is particularly related
to photon losses in optical systems. It will be interesting future works to
further investigate and resolve these problems.

Lastly, we would like to mention a recent work on a general topological MBQC
scheme using the Walker-Wang model for the 3-Fermion anyon theory [73]. It
provides a general framework on universal QC with defect braiding, which
produces the MBQC scheme via RTCSs as an example. There may be some
connections between this work and our scheme, which is worth further
investigation.

## Acknowledgments

This work was supported by the National Research Foundation of Korea
(NRF-2019M3E4A1080074, NRF-2020R1A2C1008609, NRF-2020K2A9A1A06102946) via the
Institute of Applied Physics at Seoul National University and by the Ministry
of Science and ICT, Korea, under the ITRC (Information Technology Research
Center) support program (IITP-2020-0-01606) supervised by the IITP (Institute
of Information & Communications Technology Planning & Evaluation).

##  Appendix A Verification of Eq. (14)

Here we verify Eq. (14):

$\displaystyle\expectationvalue{\widetilde{X}_{L}}{\psi}=\expectationvalue{x_{X}X_{L}^{\prime}}{\psi^{\prime}}.$
(18)

We first assume $V_{X}=\quantity{q_{0}}$ for a qubit $q_{0}$. Since there
exists a stabilizer $S_{0}$ anticommuting with $X\quantity(q_{0})$ before the
measurements, $\expectationvalue{X\quantity(q_{0})}{\psi}=0$. Thus,

$\displaystyle\ket{\psi^{\prime}}$
$\displaystyle=\norm{\frac{I+x_{q_{0}}X\quantity(q_{0})}{2}\ket{\psi}}^{-1}\frac{I+x_{q_{0}}X\quantity(q_{0})}{2}\ket{\psi}$
$\displaystyle=\frac{I+x_{q_{0}}X\quantity(q_{0})}{\sqrt{2}}\ket{\psi}$

holds. Therefore,

$\displaystyle\expectationvalue{x_{X}X_{L}^{\prime}}{\psi^{\prime}}$
$\displaystyle=\expectationvalue{\quantity[I+x_{q_{0}}X\quantity(q_{0})]x_{q_{0}}X_{L}^{\prime}}{\psi}$
$\displaystyle=x_{q_{0}}\expectationvalue{X^{\prime}_{L}}{\psi}+\expectationvalue{\widetilde{X}_{L}}{\psi}$

holds. Since $\widetilde{X}_{L}$ commutes with all the stabilizers before the
measurements, $S_{0}$ also anticommutes with
$X\quantity(q_{0})\widetilde{X}_{L}=X^{\prime}_{L}$, thus
$\expectationvalue{X^{\prime}_{L}}{\psi}$ vanishes. Hence, we get Eq. (18).
For an arbitrary $V_{X}$ with $\absolutevalue{V_{X}}>1$, we can show Eq. (18)
by simply repeating this process for every qubit in $V_{X}$.

##  Appendix B Details on calculation of resource overheads

Here we calculate the resource overheads of MBQC via RTCSs or CCCSs, namely,
the numbers of physical qubits ($n$) and required cz gates
($N_{\mathrm{\textsc{cz}}}$) per layer in terms of the code distance ($d$) and
the number of logical qubits ($k$), which are presented in Table 3 and Sec.
VI.1. We consider hexagonal arrangements of parallel timelike primal defects,
where every error chain connecting different defects or surrounding a defect
has $d$ or more qubits. We need to find the optimal intervals minimizing
$n/k$.

We first define the coordinate systems for the analysis. The $x$ and $y$ axes
are presented in Fig. 1(b) for RTCSs and Fig. 2 for the two types of CCCSs.
The unit length is the length of a side of a unit cell for RTCSs, the distance
between adjacent prAQ and pgAQ for 4-8-8 CCCSs, and half the distance between
two adjacent AQs with the same color for 6-6-6 CCCSs.

Figure 21:  Arrangements of primal defects penetrating a layer for calculating
resource overheads of MBQC via (a) RTCSs or (b) CCCSs. Each black, red, green,
or blue square is a defect, where its color means the color of the defect if
it is in (b). Each purple rectangle surrounded by dashed lines is an area
occupied by a logical qubit. Dotted lines indicate all the possible types of
error chains which may be the shortest ones, which are used for obtaining the
values of the marked intervals minimizing the area of a logical qubit. Note
that, in (b), counterparts of some error chains regarding the exchange of blue
and green defects are omitted, since the two lattices (4-8-8 and 6-6-6) which
we concern have symmetry on those defects. The optimal intervals for RTCSs are
directly presented in (a). For CCCSs, they are
$(\alpha,\beta,\gamma,\delta,\epsilon)=(\frac{1}{4}d,\frac{1}{4}d,0,\frac{1}{2}d,\frac{1}{2}d)$
for 4-8-8 and
$(\alpha,\beta,\gamma,\delta,\epsilon)\approx(0.23d,0.23d,0.38d,0.53d,0.38d)$
for 6-6-6. Here, the unit length is a side of a unit cell in RTCSs (see Fig.
1(b)), the distance between adjacent prAQ and pgAQ in 4-8-8 CCCSs (see Fig.
4(a)), and half the distance between two adjacent prAQs in 6-6-6 CCCSs (see
Fig. 2(b)).

The optimal arrangement in an RTCS is shown in Fig. 21(a). It is
straightforward to obtain the intervals, considering that the shortest error
chain connecting $(0,0)$ and $(x,y)$ contains $|x|+|y|+O(1)$ qubits. Note that
we calculate only their leading-order terms on $d$. The area occupied by a
logical qubit is thus about $\frac{35}{16}d^{2}$, and since a unit area
contains three qubits and six cz gates, we get $n/k\approx 6.6d^{2}$ and
$N_{\mathrm{\textsc{cz}}}/k\approx 13.1d^{2}$. Note that, for each CQ, we
count only one of the two related cz gates with other CQs in the adjacent
layers.

It is more tricky to obtain the optimal arrangements in 4-8-8 or 6-6-6 CCCSs.
Figure 21(b) shows the concerned hexagonal arrangement with five variables
$(\alpha,\beta,\gamma,\delta,\epsilon)$ for the intervals considering the
symmetry. We consider only the leading-order terms of their values on $d$ as
well.

We first look at 4-8-8 CCCSs. The shortest pr-EC connecting $(0,0)$ and
$(x,y)$ contains $2\max(x,y)+O(1)$ qubits, and the shortest pg-EC or pb-EC
connecting them contains $|x|+|y|+O(1)$ qubits. The thicknesses of the
defects, $\alpha$ and $\beta$, can be derived from the shortest pg-EC or pb-EC
surrounding each defect: $\alpha=\beta=\frac{1}{4}d$. The following eight
inequalities are derived from the eight possible types (A)–(H) of error chain
in Fig. 21(b):

$\displaystyle(\mathrm{A})\quad\delta\geq\frac{1}{8}d,$
$\displaystyle(\mathrm{B})\quad\delta\geq\frac{3}{8}d,$
$\displaystyle(\mathrm{C})\quad\max\quantity(\gamma+2\epsilon+\frac{1}{4}d,2\delta)\geq
d,$ $\displaystyle(\mathrm{D})\quad\gamma+2\delta+2\epsilon\geq\frac{7}{4}d,$
$\displaystyle(\mathrm{E})\quad\gamma+2\delta\geq d,$
$\displaystyle(\mathrm{F})\quad\delta+\epsilon+\frac{1}{2}\max\quantity(\gamma-\frac{1}{4}d,0)\geq
d,$ $\displaystyle(\mathrm{G})\quad\epsilon\geq\frac{3}{8}d,$
$\displaystyle(\mathrm{H})\quad\gamma+2\epsilon\geq\frac{3}{4}d.$

Note that, to get the inequalities corresponding to (E)–(H), the points at
which three error chains meet should be placed carefully. It is
straightforward to see that placing each point just next to the red defect
minimizes the length of the error chain. The area $S$ occupied by a logical
qubit is written as

$\displaystyle
S\approx\quantity(\alpha+\frac{\beta}{2}+\frac{\gamma}{2}+\epsilon)\quantity(2\delta+\alpha+\beta).$
(19)

Minimizing $S$ subject to the above inequalities, we get
$S\approx\frac{21}{16}d^{2}$ where the corresponding intervals are
$(\alpha,\beta,\gamma,\delta,\epsilon)=\quantity(\frac{1}{4}d,\frac{1}{4}d,0,\frac{1}{2}d,\frac{1}{2}d)$.
A unit area contains three qubits and eight cz gates, thus we get $n/k\approx
3.9d^{2}$ and $N_{\mathrm{\textsc{cz}}}/k\approx 10.5d^{2}$.

Figure 22:  Structure of a layer in the simplified defect model for the
simulation regarding (a) RTCSs, (b) 4-8-8 CCCSs, or (c) 6-6-6 CCCSs,
particularly when the code distance is $d=3$. In (a), blue squares (black
circles) indicate primal (dual) qubits. In (b) and (c), a colored solid line
is a boundary corresponding to that color, which can be regarded as a part of
a defect. For all of them, dashed lines are examples of primal error chains
incurring $Z_{L}$ errors. Purples triangles indicate the qubits in the error
chains, which show that the code distances are three. Defect models for $d>3$
can be constructed analogously by increasing the distances between the
boundaries while keeping their shapes.

The optimal arrangement for 6-6-6 CCCSs also can be derived similarly. The
shortest error chain connecting $(0,0)$ and $(x,y)$ for $x,y\geq 0$ contains
$\max\quantity(x+\frac{1}{\sqrt{3}}y,\frac{2}{\sqrt{3}}y)+O(1)$ qubits. We
thus get $\alpha=\beta=\quantity(\sqrt{3}-\frac{3}{2})d\approx 0.23d$,
considering an error chain surrounding a defect. The following inequalities
are derived for each type of error chain:

$\displaystyle(\mathrm{A}),(\mathrm{B})\quad\delta\geq\frac{3-\sqrt{3}}{4}d,$
$\displaystyle(\mathrm{C}),(\mathrm{D})\quad\max\quantity(\frac{1}{2}\gamma+\frac{1}{\sqrt{3}}\delta+\epsilon+\frac{1}{2}\alpha,\frac{2}{\sqrt{3}}\delta)\geq
d,$ $\displaystyle(\mathrm{E})\quad\gamma+\frac{2}{\sqrt{3}}\delta\geq d,$
$\displaystyle(\mathrm{F})\quad\epsilon+\frac{2}{\sqrt{3}}\delta\geq d,$
$\displaystyle(\mathrm{G})\quad 2\epsilon\geq d-\alpha,$
$\displaystyle(\mathrm{H})\quad\epsilon+\gamma\geq d-\alpha.$

Minimizing $S$ in Eq. (19) subject to the inequalities, we get $S\approx
1.42d^{2}$ where the corresponding intervals are
$(\alpha,\beta,\gamma,\delta,\epsilon)\approx(0.23d,0.23d,0.38d,0.53d,0.38d)$.
A unit area contains $3\sqrt{3}/2$ qubits and $4\sqrt{3}$ cz gates, thus we
get $n/k\approx 3.7d^{2}$ and $N_{\mathrm{\textsc{cz}}}/k\approx 9.8d^{2}$.

##  Appendix C Details on calculation of error thresholds

We here present some details on the calculation of error thresholds presented
in Sec. VI.2.

###  C.1 Simplified defect models

As mentioned in the main text, we simplify the defect models for efficient
simulations. Instead of considering big regions containing the entire defects,
we consider only regions surrounded by boundaries corresponding to the
defects. That is, we only take account of error chains located in the “inner”
regions surrounded by the defects. Since those error chains are strictly
shorter than error chains passing outside the regions, we conjecture that this
assumption does not affect the resulting $Z_{L}$ error probabilities much.

Figure 22 shows single layers of the three simplified defect models for the
simulations regarding RTCSs, 4-8-8 CCCSs, and 6-6-6 CCCSs, respectively. Each
layer of the concerned RTCSs has the shape of a square with a side length of
$d-1$ in the units of cells for the code distance $d$, where the boundaries
are of different types (primal and dual). Any error chain connecting the two
primal boundaries incurs a $Z_{L}$ error. For CCCSs, we consider a region
surrounded by three boundaries of different colors, where each boundary can be
regarded as a part of a defect. Any error chain connecting the three
boundaries incurs a $Z_{L}$ error.

###  C.2 Decoding methods

####  C.2.1 Raussendorf’s 3D cluster states

In an RTCS, the PC outcomes are decoded to locate errors at vacuum qubits via
Edmonds’ minimum-weight perfect matching algorithm (MWPM) [67, 68, 69], as
frequently used in the literature [43, 46, 74, 47]. Remark that an error chain
flips at most two PCs located at its ends, and if it flips one PC, it ends at
the boundary. Hence, our goal is to figure out the most probable set of error
chains based on the PC outcomes.

The decoding procedure is briefly summarized as follows. First, a graph is
constructed from the PC outcomes. The vertex set of the graph contains two
vertices for each flipped PC: one is the PC itself and the other is the
“boundary vertex.” An edge is connected between each pair of different PCs,
each pair of a PC and the corresponding boundary vertex, and each pair of
different boundary vertices. A “weight” value is assigned to each edge as
follows. If both the vertices are PCs, the weight is the number of qubits in
the shortest path between them. If only one of them is a PC, the weight is the
number of qubits in the shortest path between the PC and the closest boundary.
If both of them are boundary vertices, the weight is zero.

We use the MWPM algorithm via Blossom V software [70] to search for a set of
edges of the graph constructed above which covers all the vertices, does not
contain duplicated vertices, and minimizes the total weight. Each edge in the
resulting set corresponds to a pair of PCs flipped by an error chain or a PC
flipped by an error chain ending at the boundary, unless the edge connects two
boundary vertices, which is ignored. We can thus locate errors from the error
chain along the shortest path for each edge. Since the total weight is
minimized, we get the smallest of the sets of edges producing the same PC
outcomes, which is the most probable assuming that the error probabilities are
independent and the same between qubits.

####  C.2.2 Color-code-based cluster states

The decoding method for RTCSs is not directly applicable to CCCSs, since an
error in a CCCS flips at most three PCs, unlike the case of an RTCS. The
decoding for each sample requires the application of the MWPM algorithm six
times.

First, the outcomes of pb-PCs and pg-PCs are decoded to find the faces in
$\mathcal{L}^{\textup{{pr}}}$ with odd numbers of errors, via the method
analogous to that for RTCSs. This is possible since each of such faces flips
at most two (blue or green) PCs like an error in an RTCS. Remark that each
face in $\mathcal{L}^{\textup{{pr}}}$ corresponds to a pbAQ, pgAQ, or prL.
Errors at pbAQs and pgAQs are thus obtained from this process.

Next, the left results for prLs and the outcomes of pr-PCs are decoded to
locate errors at prAQs and pCQs, regarding the parity of the number of errors
in each prL as a PC. This is possible since an error at a prAQ or pCQ flips at
most two PCs (pr-PCs and prLs).

All the errors are finally located by the above process. However, to make the
decoding more accurate, we repeat it for $\mathcal{L}^{\textup{{pb}}}$ and
$\mathcal{L}^{\textup{{pg}}}$ analogously and select the smallest set of
decoded errors among the three results.

## References

  * Galindo and Martín-Delgado [2002] A. Galindo and M. A. Martín-Delgado, Information and computation: Classical and quantum aspects, Rev. Mod. Phys. 74, 347 (2002).
  * Nielsen and Chuang [2010] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information_ (Cambridge University Press, 2010).
  * Shor [1995] P. W. Shor, Scheme for reducing decoherence in quantum computer memory, Phys. Rev. A 52, R2493 (1995).
  * Bennett  _et al._ [1996] C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, and W. K. Wootters, Mixed-state entanglement and quantum error correction, Phys. Rev. A 54, 3824 (1996).
  * Laflamme  _et al._ [1996] R. Laflamme, C. Miquel, J. P. Paz, and W. H. Zurek, Perfect quantum error correcting code, Phys. Rev. Lett. 77, 198 (1996).
  * Calderbank and Shor [1996] A. R. Calderbank and P. W. Shor, Good quantum error-correcting codes exist, Phys. Rev. A 54, 1098 (1996).
  * Steane [1996] A. Steane, Multiple-particle interference and quantum error correction, P. Roy. Soc. Lond. A Mat. 452, 2551 (1996).
  * Bombín [2013] H. Bombín, Topological codes, in  _Quantum Error Correction_ , edited by D. A. Lidar and T. A. Brun (Cambridge, 2013) Chap. 19, pp. 455–481.
  * Cory  _et al._ [1998] D. G. Cory, M. D. Price, W. Maas, E. Knill, R. Laflamme, W. H. Zurek, T. F. Havel, and S. S. Somaroo, Experimental quantum error correction, Phys. Rev. Lett. 81, 2152 (1998).
  * Chiaverini  _et al._ [2004] J. Chiaverini, D. Leibfried, T. Schaetz, M. D. Barrett, R. B. Blakestad, J. Britton, W. M. Itano, J. D. Jost, E. Knill, C. Langer, R. Ozeri, and D. J. Wineland, Realization of quantum error correction, Nature 432, 602 (2004).
  * Schindler  _et al._ [2011] P. Schindler, J. T. Barreiro, T. Monz, V. Nebendahl, D. Nigg, M. Chwalla, M. Hennrich, and R. Blatt, Experimental repetitive quantum error correction, Science 332, 1059 (2011).
  * Reed  _et al._ [2012] M. D. Reed, L. DiCarlo, S. E. Nigg, L. Sun, L. Frunzio, S. M. Girvin, and R. J. Schoelkopf, Realization of three-qubit quantum error correction with superconducting circuits, Nature 482, 382 (2012).
  * Nigg  _et al._ [2014] D. Nigg, M. Müller, E. A. Martinez, P. Schindler, M. Hennrich, T. Monz, M. A. Martin-Delgado, and R. Blatt, Quantum computations on a topologically encoded qubit, Science 345, 302 (2014).
  * Córcoles  _et al._ [2015] A. D. Córcoles, E. Magesan, S. J. Srinivasan, A. W. Cross, M. Steffen, J. M. Gambetta, and J. M. Chow, Demonstration of a quantum error detection code using a square lattice of four superconducting qubits, Nat. Commun. 6, 1 (2015).
  * Kelly  _et al._ [2015] J. Kelly, R. Barends, A. G. Fowler, A. Megrant, E. Jeffrey, T. C. White, D. Sank, J. Y. Mutus, B. Campbell, Y. Chen, B. Chiaro, A. Dunsworth, I.-C. Hoi, C. Neill, P. J. J. O’Malley, C. Quintana, P. Roushan, A. Vainsencher, J. Wenner, A. N. Cleland, and J. M. Martinis, State preservation by repetitive error detection in a superconducting quantum circuit, Nature 519, 66 (2015).
  * Ofek  _et al._ [2016] N. Ofek, A. Petrenko, R. Heeres, P. Reinhold, Z. Leghtas, B. Vlastakis, Y. Liu, L. Frunzio, S. M. Girvin, L. Jiang, M. Mirrahimi, M. H. Devoret, and R. J. Schoelkopf, Extending the lifetime of a quantum bit with error correction in superconducting circuits, Nature 536, 441 (2016).
  * Andersen  _et al._ [2020] C. K. Andersen, A. Remm, S. Lazar, S. Krinner, N. Lacroix, G. J. Norris, M. Gabureac, C. Eichler, and A. Wallraff, Repeated quantum error detection in a surface code, Nat. Phys. 16, 875 (2020).
  * Kitaev [1997] A. Y. Kitaev, Quantum computations: algorithms and error correction, Russ. Math. Surv. 52, 1191 (1997).
  * Bravyi and Kitaev [1998] S. B. Bravyi and A. Y. Kitaev, Quantum codes on a lattice with boundary, arXiv preprint quant-ph/9811052 (1998).
  * Dennis  _et al._ [2002] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topological quantum memory, J. Math. Phys. 43, 4452 (2002).
  * Kitaev [2003] A. Y. Kitaev, Fault-tolerant quantum computation by anyons, Ann. Phys. 303, 2 (2003).
  * Fowler  _et al._ [2009] A. G. Fowler, A. M. Stephens, and P. Groszkowski, High-threshold universal quantum computation on the surface code, Phys. Rev. A 80, 052312 (2009).
  * Bombin and Martin-Delgado [2009] H. Bombin and M. A. Martin-Delgado, Quantum measurements and gates by code deformation, J. Phys. A: Math. Theor. 42, 095302 (2009).
  * Fowler  _et al._ [2012a] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Phys. Rev. A 86, 032324 (2012a).
  * Terhal [2015] B. M. Terhal, Quantum error correction for quantum memories, Rev. Mod. Phys. 87, 307 (2015).
  * Bombin and Martin-Delgado [2006] H. Bombin and M. A. Martin-Delgado, Topological quantum distillation, Phys. Rev. Lett. 97, 180501 (2006).
  * Fowler [2011] A. G. Fowler, Two-dimensional color-code quantum computation, Phys. Rev. A 83, 042310 (2011).
  * Kesselring  _et al._ [2018] M. S. Kesselring, F. Pastawski, J. Eisert, and B. J. Brown, The boundaries and twist defects of the color code and their applications to topological quantum computation, Quantum 2, 101 (2018).
  * Note [1] That a logical gate $U$ is transversal means that $U$ can be expressed as $U=U_{1}U_{2}\cdots$ such that a unitary operator $U_{i}$ acts only on the $i$th physical qubit for each logical qubit for all $i$’s. For example, if $X_{L}:=X_{1}\cdots X_{n}$ for $[[n,1,d]]$ code where $X_{i}$ is the $X$ operator on the $i$th physical qubit, $X_{L}$ is transversal. Specific 2D color codes implement the logical Hadamard gate by the combination of the Hadamard gate on every physical qubit, and similarly for the logical phase gate [26, 27].
  * Bombin and Martin-Delgado [2007a] H. Bombin and M. A. Martin-Delgado, Topological computation without braiding, Phys. Rev. Lett. 98, 160502 (2007a).
  * Bombin and Martin-Delgado [2007b] H. Bombin and M. A. Martin-Delgado, Exact topological quantum order in $d=3$ and beyond: Branyons and brane-net condensates, Phys. Rev. B 75, 075103 (2007b).
  * Bombín [2015] H. Bombín, Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes, New J. Phys. 17, 083002 (2015).
  * Kubica and Beverland [2015] A. Kubica and M. E. Beverland, Universal transversal gates with color codes: A simplified approach, Phys. Rev. A 91, 032330 (2015).
  * Watson  _et al._ [2015] F. H. E. Watson, E. T. Campbell, H. Anwar, and D. E. Browne, Qudit color codes and gauge color codes in all spatial dimensions, Phys. Rev. A 92, 022312 (2015).
  * Kubica  _et al._ [2018] A. Kubica, M. E. Beverland, F. Brandão, J. Preskill, and K. M. Svore, Three-dimensional color code thresholds via statistical-mechanical mapping, Phys. Rev. Lett. 120, 180501 (2018).
  * Bombin [2018a] H. Bombin, 2d quantum computation with 3d topological codes, arXiv preprint arXiv:1810.09571 (2018a).
  * Bombin [2018b] H. Bombin, Transversal gates and error propagation in 3d topological codes, arXiv preprint arXiv:1810.09575 (2018b).
  * Bravyi and Kitaev [2005] S. Bravyi and A. Kitaev, Universal quantum computation with ideal clifford gates and noisy ancillas, Phys. Rev. A 71, 022316 (2005).
  * Jones [2013] C. Jones, Multilevel distillation of magic states for quantum computing, Phys. Rev. A 87, 042305 (2013).
  * Raussendorf  _et al._ [2007] R. Raussendorf, J. Harrington, and K. Goyal, Topological fault-tolerance in cluster state quantum computation, New J. Phys. 9, 199 (2007).
  * Raussendorf and Briegel [2001] R. Raussendorf and H. J. Briegel, A one-way quantum computer, Phys. Rev. Lett. 86, 5188 (2001).
  * Raussendorf  _et al._ [2003] R. Raussendorf, D. E. Browne, and H. J. Briegel, Measurement-based quantum computation on cluster states, Phys. Rev. A 68, 022312 (2003).
  * Raussendorf  _et al._ [2006] R. Raussendorf, J. Harrington, and K. Goyal, A fault-tolerant one-way quantum computer, Ann. Phys. 321, 2242 (2006).
  * Raussendorf and Harrington [2007] R. Raussendorf and J. Harrington, Fault-tolerant quantum computation with high threshold in two dimensions, Phys. Rev. Lett. 98, 190504 (2007).
  * Fowler and Goyal [2009] A. G. Fowler and K. Goyal, Topological cluster state quantum computing, Quantum Info. Comput. 9, 721–738 (2009).
  * Barrett and Stace [2010] S. D. Barrett and T. M. Stace, Fault tolerant quantum computation with very high threshold for loss errors, Phys. Rev. Lett. 105, 200502 (2010).
  * Whiteside and Fowler [2014] A. C. Whiteside and A. G. Fowler, Upper bound for loss in practical topological-cluster-state quantum computing, Phys. Rev. A 90, 052316 (2014).
  * Li  _et al._ [2010] Y. Li, S. D. Barrett, T. M. Stace, and S. C. Benjamin, Fault tolerant quantum computation with nondeterministic gates, Phys. Rev. Lett. 105, 250502 (2010).
  * Nielsen [2004] M. A. Nielsen, Optical quantum computation using cluster states, Phys. Rev. Lett. 93, 040503 (2004).
  * Dawson  _et al._ [2006] C. M. Dawson, H. L. Haselgrove, and M. A. Nielsen, Noise thresholds for optical cluster-state quantum computation, Phys. Rev. A 73, 052306 (2006).
  * Menicucci  _et al._ [2006] N. C. Menicucci, P. van Loock, M. Gu, C. Weedbrook, T. C. Ralph, and M. A. Nielsen, Universal quantum computation with continuous-variable cluster states, Phys. Rev. Lett. 97, 110501 (2006).
  * Devitt  _et al._ [2009] S. J. Devitt, A. G. Fowler, A. M. Stephens, A. D. Greentree, L. C. L. Hollenberg, W. J. Munro, and K. Nemoto, Architectural design for a topological cluster state quantum computer, New J. Phys. 11, 083032 (2009).
  * Herrera-Martí  _et al._ [2010] D. A. Herrera-Martí, A. G. Fowler, D. Jennings, and T. Rudolph, Photonic implementation for the topological cluster-state quantum computer, Phys. Rev. A 82, 032332 (2010).
  * Fujii and Tokunaga [2010] K. Fujii and Y. Tokunaga, Fault-tolerant topological one-way quantum computation with probabilistic two-qubit gates, Phys. Rev. Lett. 105, 250503 (2010).
  * Myers and Ralph [2011] C. R. Myers and T. C. Ralph, Coherent state topological cluster state production, New J. Phys. 13, 115015 (2011).
  * Yao  _et al._ [2012] X.-C. Yao, T.-X. Wang, H.-Z. Chen, W.-B. Gao, A. G. Fowler, R. Raussendorf, Z.-B. Chen, N.-L. Liu, C.-Y. Lu, Y.-J. Deng, Y.-A. Chen, and J.-W. Pan, Experimental demonstration of topological error correction, Nature 482, 489 (2012).
  * Gimeno-Segovia  _et al._ [2015] M. Gimeno-Segovia, P. Shadbolt, D. E. Browne, and T. Rudolph, From three-photon greenberger-horne-zeilinger states to ballistic universal quantum computation, Phys. Rev. Lett. 115, 020502 (2015).
  * Li  _et al._ [2015] Y. Li, P. C. Humphreys, G. J. Mendoza, and S. C. Benjamin, Resource costs for fault-tolerant linear optical quantum computing, Phys. Rev. X 5, 041007 (2015).
  * Omkar  _et al._ [2020] S. Omkar, Y. S. Teo, and H. Jeong, Resource-efficient topological fault-tolerant quantum computation with hybrid entanglement of light, Phys. Rev. Lett. 125, 060501 (2020).
  * Bolt  _et al._ [2016] A. Bolt, G. Duclos-Cianci, D. Poulin, and T. M. Stace, Foliated quantum error-correcting codes, Phys. Rev. Lett. 117, 070501 (2016).
  * Bolt  _et al._ [2018] A. Bolt, D. Poulin, and T. M. Stace, Decoding schemes for foliated sparse quantum error-correcting codes, Phys. Rev. A 98, 062302 (2018).
  * Brown and Roberts [2020] B. J. Brown and S. Roberts, Universal fault-tolerant measurement-based quantum computation, Phys. Rev. Research 2, 033305 (2020).
  * Note [2] The support of an operator $O$, written as $\mathrm{supp}(O)$, is the set of qubits on which $O$ applies non-trivially.
  * Note [3] If this is the case, the interior qubits of the CS correspond to spacelike faces in $\mathcal{L}^{\textup{{pc}}}$, which are $\textup{{pc}}^{\prime\prime}\textup{{AQ}}$s ($\textup{{c}}^{\prime\prime}\neq\textup{{c}}$) according to Table 1. They are surely not be in the pc-D. Otherwise, the pc′-CS and defect share at least one qubit if they overlap.
  * Note [4] The boundary qubits of a dc-CS correspond to edges in $\mathcal{L}^{\textup{{dc}}}$, which are pcAQs or pcLs.
  * Note [5] Such an error set may not be an error chain, because errors in defects may also be nontrivial and undetectable. However, since error correction in defects gets more accurate as the defects get thicker, the dependency of the code distance to their thicknesses is still valid. It can be verified that the smallest nontrivial undetectable error set containing only defect qubits completely covers a cross-section of the defect, thus its size is roughly a quadratic function of the circumference of the defect.
  * Edmonds [1965a] J. Edmonds, Paths, trees, and flowers, Can. J. Math. 17, 449 (1965a).
  * Edmonds [1965b] J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bur. Stand. B 69, 55 (1965b).
  * Fowler [2015] A. G. Fowler, Minimum weight perfect matching of fault-tolerant topological quantum error correction in average o(1) parallel time, Quantum Info. Comput. 15, 145–158 (2015).
  * Kolmogorov [2009] V. Kolmogorov, Blossom v: a new implementation of a minimum cost perfect matching algorithm, Math. Program. Comput. 1, 43 (2009).
  * Litinski [2019] D. Litinski, Magic State Distillation: Not as Costly as You Think, Quantum 3, 205 (2019).
  * Chamberland and Noh [2020] C. Chamberland and K. Noh, Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits, npj Quant. Inf. 6, 1 (2020).
  * Roberts and Williamson [2020] S. Roberts and D. J. Williamson, 3-fermion topological quantum computation, arXiv preprint arXiv:2011.04693 (2020).
  * Fowler  _et al._ [2012b] A. G. Fowler, A. C. Whiteside, A. L. McInnes, and A. Rabbani, Topological code autotune, Phys. Rev. X 2, 041003 (2012b).