# Mapping Surface Code to Superconducting Quantum Processors

Anbang Wu
Department of Computer Science
University of California, Santa Barbara
<EMAIL_ADDRESS>
&Gushu Li
Department of Electrical & Computer Engineering
University of California, Santa Barbara
<EMAIL_ADDRESS>
Hezi Zhang
Department of Computer Science
University of California, Santa Barbara
<EMAIL_ADDRESS>
Gian Giacomo Guerreschi
Intel Labs
Santa Clara, California
<EMAIL_ADDRESS>Yufei Ding
Department of Computer Science
University of California, Santa Barbara
<EMAIL_ADDRESS>
Yuan Xie
Department of Electrical & Computer Engineering
University of California, Santa Barbara
<EMAIL_ADDRESS>

###### Abstract

In this paper, we formally describe the three challenges of mapping surface
code on superconducting devices, and present a comprehensive synthesis
framework to overcome these challenges. The proposed framework consists of
three optimizations. First, we adopt a geometrical method to allocate data
qubits which ensures the existence of shallow syndrome extraction circuit. The
proposed data qubit layout optimization reduces the overhead of syndrome
extraction and serves as a good initial point for following optimizations.
Second, we only use bridge qubits enclosed by data qubits and reduce the
number of bridge qubits by merging short path between data qubits. The
proposed bridge qubit optimization reduces the probability of bridge qubit
conflicts and further minimizes the syndrome extraction overhead. Third, we
propose an efficient heuristic to schedule syndrome extractions. Based on the
proposed data qubit allocation, we devise a good initial schedule of syndrome
extractions and further refine this schedule to minimize the total time needed
by a complete surface code error detection cycle. Our experiments on
mainsstream superconducting quantum architectures have demonstrated the
efficiency of the proposed framework.

##  1 Introduction

Quantum hardware has advanced significantly in the last decade and
demonstrated ‘Quantum Supremacy’ for the first time in 2020 [1]. Among various
quantum hardware technologies [2, 3, 4, 5], the superconducting (SC) qubit is
currently one of the most promising technique candidates for building quantum
processors [6, 7] due to its low error rates, individual qubit addressability,
fabrication scalability, etc. Many latest quantum processors adopt the SC
technology, e.g., IBM’s 65-qubit heavy-hexagon-architecture chip [8],
Rigetti’s 32-qubit octagonal-architecture chip [9], Google’s 54-qubit
2D-lattice chip [1].

The low error rate of SC processors makes them an ideal platform for quantum
error correction (QEC) [10, 11, 12, 13, 14] and thus realizing fault-tolerant
(FT) quantum computation. Among various QEC codes, surface code [15] is a
popular choice as it possesses one of the best error correction capabilities
and can tolerate a high (up to 1%) physical error rate. Even on noisy near-
term devices, the surface code family can encode an arbitrarily accurate
logical qubit with a large enough array of physical qubits. This makes surface
code one of the most feasible QEC choices for demonstrating near-term FT
quantum computation.

With a readily available surface code array, many recent research efforts have
been put into improving the efficiency of FT quantum computation, varying from
compilation [16, 17], communication scheduling [18, 19], and micro-controller
design [20]. All these works are based on a nontrivial assumption: we already
find a scalable way to compose logical qubits on existing quantum devices, in
particular SC devices, with the surface code family.

Yet, implementing surface code on SC devices itself is a difficult problem.
The implementation of surface code separates physical qubits into two
categories. The first category of qubits is called “data qubits” and is used
to encode the logical qubit. Physical qubits in the second category are used
to detect errors on data qubits, and are thus called “syndrome qubits”. Each
syndrome qubit extracts error syndromes on four neighboring data qubits with a
specialized quantum circuit, named “measurement circuit” [15]. To make
measurement circuits executable, surface code requires a 2D-lattice qubit
array where each qubit is connected or coupled to four other qubits.
Nonetheless, such an architecture is not readily available on many latest
quantum processors [8, 9] as the dense connection in the 2D qubit array would
induce a high physical error rate. Previous work tackles the gap between
surface code and the sparse-connected SC device either by tailoring the
architecture with tunable coupling [5] or by designing a QEC code upon the
surface code [21]. The former method is expensive and may introduce extra
device noises while the latter method is not automated.

In this paper, we propose the first automatic synthesis framework “Surfmap”
for stitching the surface code family to various SC devices, without any
variation in device or surface code. Our framework builds upon recent
theoretical work on generating individual measurement circuits over sparse-
connected SC devices [22, 21]. These works generalize the syndrome qubit to a
tree of low-degree qubits (a.k.a bridge tree with constituent qubits called
bridge qubits) that connects to the four target data qubits. In essential,
these work trades the qubit degree with the qubit number.

Yet, these measurement circuit generation works are far from tackling the
overall surface code synthesis. These works cannot generate measurement
circuits unless the data qubits and bridge qubits for each measurement circuit
are assigned. Even all measurement circuits are generated, how to efficiently
execute them is still not answered by these works. Systematically, to tackle
the surface code synthesis problem on SC devices, we should address three key
challenges. First, the allocation of data qubits. If the four data qubits of a
measurement circuit are far away from each other, many bridge qubits will be
needed to connect these data qubits. Oppositely, if these data qubits are too
close, there will not be enough space for a bridge tree. Second, the selection
of bridge qubits. An improper selection of bridge qubits may cause conflicts
in measurement circuits that several measurement circuits contend for one
bridge qubit. Such bridge qubit conflict will cause a sequential execution of
measurement circuits thus increasing the error detection latency and degrading
the error correction performance. Third, the execution order of measurement
circuits. As indicated above, sequential execution of measurement circuits is
not acceptable and an efficient synthesis should utilize the parallelism
between measurement circuits, as much as possible.

Our framework decouples the optimization space of surface code synthesis with
a modular optimization scheme. To be specific, our framework consists of three
key steps.

In the first step, we optimize the allocation of data qubits since data qubits
are the key to gluing measurement circuits together, and once allocated their
physical mapping should not change to avoid error proliferation. As long as
allocated data qubit layout ensures the existence of measurement circuits, we
prefer a shorter total distance between data qubits since this reduces bridge
qubits overhead for constructing measurement circuits. To enable this
optimization, we search data qubits over a series of “rectangular” blocks,
with each block created by a pair of three-degree qubits or one four-degree
qubit. The key insight behind such design is that existing SC architectures
can always be embedded into a 2D lattice and the four data qubits for a
measurement circuit exactly form a rectangle in the 2D lattice. Our design
ensures the existence of measurement circuits since there are enough high-
degree qubits in each rectangle to connect data qubits. Rectangle-based search
is efficient as it enables a coarse-grained exploration over the search space.
Furthermore, to reduce the possible conflicts of measurement circuits, we
require the overlapping between rectangular blocks at most happens on
rectangle boundaries.

In the second step, it naturally comes to the optimization of bridge qubits.
The optimization goal is to reduce the conflicts between measurement circuits,
i.e., reduce the mutual bridge qubits, and minimize the bridge tree connecting
data qubits. The key insight for such optimization is that the size of the
measurement circuit is proportional to the bridge tree size and measurement
circuits without conflicts can be executed together to shorten the time window
of error correction cycles. To meet these goals, we first limit the search
scope of bridge qubits inside rectangular blocks enclosed by data qubits.
Since rectangular blocks have zero overlapping areas, such local search could
greatly reduce bridge qubit conflict. On the other hand, to find small bridge
trees, we adopt two different heuristics which complement each other. We then
pick the best results from these two methods as bridge tree candidates.

In the third step, we optimize the order of measurement circuit execution. The
reason for this optimization is that conflicts between measurement circuits
can sometimes be inevitable. In such cases, we have to execute conflicted
measurement circuits in sequential. To reduce the total time window of
measurement circuits execution in this case, we propose an iterative
refinement method. We first place conflicted measurement circuits into
different partitions, and then refine the partitions by moving large
measurement circuits into one partition while ensuring the compatibility
between measurement circuits. The key insight behind such optimization is that
when executing measurement circuits in parallel, the execution time depends on
the one with the largest circuit depth. By moving large measurement circuits
together, we can reduce the execution time of partitions consisting of small
measurement circuits.

We evaluate the proposed synthesis framework by comparing it to manually
designed QEC codes [21] on two SC architectures. The results show the surface
codes synthesized by our framework can achieve equivalent or even better error
thresholds. This result is inspiring as it unveils the possibility that
automated synthesis by machine can surpass the manual QEC code design of
experienced theorists. We also investigate our framework on various mainstream
SC architectures and present an analysis of several architecture design
options based on the investigation result. The proposed synthesis framework
would be of great interest to both QEC researchers and quantum hardware
designers. Theorists would have a baseline to compare with when designing
novel QEC codes. Hardware researchers could benefit from our framework in two
aspects: a) they could focus on improving the device without worrying about
meeting the requirements of a specific QEC code; b) they can identify
inefficient architecture designs for QEC codes with our synthesis framework.

Our contributions in this paper are summarized as follows:

  * •

We promote the importance of a synthesis framework for achieving good QEC
implementations towards different quantum hardware architectures.

  * •

We systematically formulate the surface code synthesis problem on SC devices
for the first time and identify three key challenges: data qubit allocation,
bridge qubit selection and measurement circuit execution scheduling.

  * •

We design and implement a modular synthesis framework that tackles the
identified three challenges step by step, with a series of insights extracted
from surface code and SC architectures.

  * •

Our evaluation demonstrates the effectiveness of the proposed synthesis
framework with one comparative study to manually designed QEC codes and a
comprehensive investigation on various mainstream SC architectures.

##  2 Background

In this section, we introduce the key concepts for understanding the
implementation requirements of surface code [14, 23, 24]. We do not cover the
basics of quantum computing and recommend [25] for reference.

Figure 1: Common components of the surface code. (a) Surface code lattice with
data qubits (blue dots) and syndrome qubits (red dots). (b) Z-type syndrome
extraction and its circuit. (c) X-type syndrome extraction and its circuit.

Data and syndrome qubits: Surface code encodes logical qubit information in a
2D lattice of physical qubits shown in Figure 1(a). Physical qubits in the
code lattice can be divided into two types: data qubits and syndrome qubits
(represented as blue and red dots respectively, see Figure 1(a)). The logical
information is encoded in the data qubits. The error information on these data
qubits can be extracted by applying surface code operations and measuring
syndrome qubits.

Pauli operator and stabilizer: In surface codes, the relationship between one
syndrome qubits and its neighboring data qubits is represented by the product
of an array of Pauli operators (a.k.a Pauli string) labeled on the edges
between data qubits and syndrome qubits (Figure 1(a)). For each syndrome
qubit, the Pauli string on its edges can be in one of two possible patterns.
The first one (Z-type) is shown in Figure 1(b). The connections between the
center syndrome qubit and the four data qubits are all labeled by the $Z$
operators and represented by the Pauli string $Z_{a}Z_{b}Z_{c}Z_{d}$. The
second one (X-type) in Figure 1(c) is similar but all connections are labeled
by the $X$ operators and represented by the Pauli string
$X_{a}X_{b}X_{c}X_{d}$. For these two different patterns, we will have
corresponding syndrome measurement circuits to detect errors in the data
qubits (shown on the right of Figure 1(b) and (c)). The syndrome extraction
circuits project the state of data qubits $\\{a,b,c,d\\}$ into the eigenstates
of the corresponding Pauli strings. In the context of QEC, the specific Pauli
strings that one measures are called stabilizers [26] and the syndrome
extraction circuits are also known as stabilizer measurements [27]. Without
ambiguity, we use the stabilizer notation to represent a syndrome extraction.
And we denote the stabilizer $Z_{a}Z_{b}Z_{c}Z_{d}$ ($X_{a}X_{b}X_{c}X_{d}$)
with $Z_{abcd}$ (respectively $X_{abcd}$) for simplicity.

Error detection: Surface code can detect Pauli X- and Z-errors on data qubits
by using Z- and X-type stabilizer measurement circuits, respectively. An error
on a data qubit may affect the measurement results of stabilizers associated
with this data qubit. By gathering all such stabilizer measurement results, a
surface code error correction protocol can infer what errors occurred in the
lattice and consequently apply the corresponding correction. Further details
of the error correction protocol can be found in [15].

Figure 2: Code distance and compact lattice. (a) Surface code logical
operations with distance 3. (b) Inside the rotated rectangle (dashed brown
line) is a compact surface code lattice with the same code distance.

Code distance: The error correction ability of QEC codes is measured by their
code distance [28, 12]. The code distance is defined to be the minimum number
of physical qubits in the support of logical X or Z operations on the encoded
logical qubit (denoted by $X_{L}$ or $Z_{L}$ in Figure 2). Figure 2 (a) shows
logical operations in a distance-3 surface code. It is possible to obtain a
more compact surface code lattice without changing the code distance, as shown
in Figure 2(b). In this paper, we focus on the rotated surface code in Figure
2(b).

Stabilizer synthesis: The first step of surface code synthesis is to implement
individual stabilizer measurement circuit. Various methods have been proposed
to map one single stabilizer to sparse-connected SC devices, such as the
degree-deduction technique [21], and the flag-bridge circuit [22, 29, 30, 31].
Once data qubits and needed ancillary qubits (including the syndrome qubit)
for the stabilizer measurement are appointed, these method can generate the
corresponding measurement circuit. Figure 3 shows the generated flag-bridge
circuit for stabilizer $Z_{bcid}$ with ancillary qubits $\\{e,s,f\\}$. These
work only solved the low-level circuit generation problem of one stabilizer
measurement, far from tackling the overall surface code synthesis, which is
more than a simple collection of measurement circuits.

Figure 3:  Z-type stabilizer measurement circuit synthesis: (a) The coupling
graph of data qubits (blue) and ancillary qubits (red). Qubit $s$ is the
syndrome qubit. (b) The synthesized stabilizer measurement circuit that
satisfies the coupling graph in (a).

Our framework targets at the high-level synthesis of the entire surface code
and use these low-level stabilizer synthesis methods as the backend.

Figure 4:  A motivating example for synthesizing a (rotated) distance-3
surface code: (a) An SC device based on the hexagon structure; (b) A bad data
qubit layout where the stabilizer $X_{idfe}$ cannot be measured; (c) A
promising data qubit layout that ensures stabilizer measurement for all
stabilizers; (d) An example for resolving bridge tree conflict.

##  3 Design Overview

The surface code relies on a 2D square-grid connectivity between physical
qubits, while actual superconducting (SC) processors may not satisfy this
requirement and then fail to execute the vanilla surface code. In this paper,
we aim to mitigate this gap by resynthesizing the surface code onto SC
architectures with sparse connections. We first formulate the surface code
synthesis problem and then introduce the optimization opportunities.

###  3.1 Surface code synthesis on SC architectures

We consider implementing the (rotated) surface code in Figure 2(b) on a
quantum device with a hexagon architecture (see Figure 4(a)) [21]. In this
hexagon device, each qubit connects to at most three other qubits. This
imposes a challenge to synthesize stabilizer measurement circuits of a surface
code since a syndrome qubit in either an X- or Z- type stabilizer measurement
should connect to four data qubits (see Figure 1(b) and (c)).

To resolve this constraint, we can introduce ancillary qubits when
synthesizing a stabilizer measurement circuit. Suppose a mapping of the
logical qubit in Figure 2(b) onto the hexagon architecture is shown in Figure
4(b). To measure the stabilizer $Z_{bcid}$, one needs to connect the four data
qubits $\\{b,c,i,d\\}$ with a syndrome qubit. In Figure 4(b), data qubits
$\\{b,c,i,d\\}$ are mapped to physical qubits
$\\{Q_{9},Q_{16},Q_{11},Q_{20}\\}$, and the syndrome qubit is on $Q_{18}$. To
connect $Q_{18}$ and $\\{Q_{9},Q_{16},Q_{11},Q_{20}\\}$, one can use the two
ancillary qubits $Q_{17}$ and $Q_{19}$. Qubits $Q_{17}$, $Q_{18}$ and $Q_{19}$
together form a tree that bridges the gap between data qubits
$\\{Q_{9},Q_{16},Q_{11},Q_{20}\\}$ and the syndrome qubit $Q_{18}$. Such a
tree is called bridge tree and ancillae $\\{Q_{17},Q_{19}\\}$ are called
bridge qubits. For simplicity, we regard the syndrome qubit as a special
bridge qubit.

###  3.2 Optimization opportunities

To deploy an entire surface code QEC protocol onto an SC architecture requires
synthesizing a series of non-independent stabilizer measurements, which is far
more complicated than handling one single stabilizer measurement. In this
section, we formulate the overall surface code synthesis problem into three
key steps: data qubit allocation, bridge tree construction, and stabilizer
measurement schedule. We briefly introduce the objectives and the design
considerations of each step.

Data qubit allocation: In this paper, we choose to allocate and fix the
position of data qubits first as data qubits are the key to gluing stabilizer
measurement circuits together and should not be changed once allocated.
Comparing to data qubits, bridge qubits are dynamic resources which are
initialized, used, measured and decoupled in every QEC cycle, making them
unsuitable for a pre-allocation.

The layout of the data qubits affects how efficiently stabilizer measurement
circuits can be executed. For example, we synthesize the (rotated) distance-3
surface code in Figure 2(b) with two data qubit layouts in Figure 4(b) and
Figure 4(c). In Figure 4(b), the stabilizer $X_{idfe}$ cannot be measured
without moving data qubits and inserting SWAP gates, which are not allowed to
avoid error proliferation.In contrast, all stabilizer measurements
($\\{X_{abhi},X_{idfe},X_{fg},X_{bc},Z_{bcid},Z_{higf},Z_{ah},Z_{de}\\}$) can
be executed on Figure 4(c) since bridge trees for these stabilizers are
readily available.

Bridge tree construction: After the data qubits are placed, the next step is
to select the bridge qubits and construct bridge trees for stabilizer
measurements. The first constraint in this step is that we should minimize the
number of bridge qubits since using more physical qubits results in larger
measurement circuits which are naturally more error-prone. The second
constraint is that the construction of bridge trees affects the efficiency of
error detection because two stabilizers can be simultaneously measured only if
their bridge trees do not intersect. For instance, referring to Figure 4(c),
if we measure $X_{bc}$ with bridge qubits {$r$, $s$}, these two qubits cannot
be used as bridge qubits in the measurement circuit of $X_{abhi}$ at the same
time because the bridge qubits need to be reset at the beginning of any new
measurement circuit. However, if we measure $X_{bc}$ with bridge qubits {$p$,
$q$} in Figure 4(d), we can measure $X_{bc}$ and $X_{abhi}$ in parallel. An
efficient bridge qubit selection and tree construction should enable the
concurrent measurement of as many stabilizers as possible.

Stabilizer measurement scheduling: The third step is to schedule the execution
of the stabilizer measurement circuits. It would be desirable to execute the
stabilizer measurement in parallel as much as possible since it can reduce the
execution time and mitigate the decoherence error. However, stabilizer
measurement circuits have overlapped bridge qubits (a.k.a bridge qubit
conflict) cannot be executed simultaneously. For example in Figure 4(c), the
measurement circuit of $X_{abhi}$ and $Z_{bcid}$ cannot be measured together
since they share bridge qubits $\\{q_{9},q_{10}\\}$. One possibility is to
measure $X_{abhi}$ and $X_{idhe}$ first, then measures $Z_{hgif}$ and
$Z_{bcid}$. Though seems promising, it is not optimal as these two groups of
measurements take 20 operation steps in total, using the flag-bridge circuit
[22](Figure 3) as backend. As a comparison, if we measure $X_{abhi}$ and
$Z_{hgif}$ first and measure $X_{idfe}$ and $Z_{bcid}$ second, the total
operation step number is only 18. It is usually not a simple task to schedule
the stabilizer measurements optimally. Our objective is to identify the
potential parallelism in stabilizer measurements and figure out an efficient
heuristic scheduling method to minimize the overall error detection cycle time
(running all stabilizer measurements once is a cycle in the surface code QEC
protocol).

##  4 Synthesis Algorithm Design

In this section, we introduce our surface code synthesis flow. As discussed
above, we will introduce three key steps, data qubit allocation, bridge tree
construction and stabilizer measurement scheduling.

###  4.1 Data qubit allocator

Input: Device architecture graph $G$

Output: Data qubit layout $data\\_layout$

1

2$L_{h}=$ all three- and four-degree nodes in $G$;

$bridge\\_rects=[]$ ; // the set of bridge rectangles

3 for  _$n_{a}$ in $L_{h}$_ do

4 if  _$deg(n_{a})==3$_ then

5 $n_{b}$ = the nearest high-degree node of $n_{a}$;

6 $rect=$ the minimal rectangle containing $n_{a}$, $n_{b}$ and their
neighboring qubits;

7

8 else

9 $rect=$ the minimal rectangle containing $n_{a}$ and its neighboring qubits
;

10

11 end if

12 $bridge\\_rects.append(rect)$;

13

14 end for

15$r_{0}=$ the bridge rectangle at the top left corner of $G$;

16

$bridge\\_rect\\_tuple=[]$; // tuples of compatible bridge rectangles;

17

18repeat

19 for  _$(r_{1},r_{2},r_{3})\in\otimes^{3}{bridge\\_rects}$_ do

20 if  _$r_{0},r_{1},r_{2},r_{3}$ are mutually compatible_ then

$potent\\_dqbits=$ qubits enclosed by $r_{0},r_{1},r_{2},r_{3}$; // potential
data area;

21 if  _$potent\\_dqbits\neq\emptyset$_ then

22 $bridge\\_rect\\_tuple.append((r_{0},r_{1},r_{2},r_{3}))$;

23 break;

24

25

26

27 end for

28 set $r_{0}$ to $r_{1},r_{2},r_{3}$ in turn to find new combination of
$r_{0},r_{1},r_{2},r_{3}$ that has non-empty $potent\\_dqbits$;

29

30until  _$bridge\\_rect\\_tuple$ converges_;

31$data\\_layout=[]$;

32 for  _$r_{0},r_{1},r_{2},r_{3}$ in $bridge\\_rect\\_tuple$_ do

33 $dqb$ = the qubit at the center of $potent\\_dqbits$ of
$r_{0},r_{1},r_{2},r_{3}$;

34 $data\\_layout.append(dqb)$;

35

36 end for

Algorithm 1 Data qubit allocation Figure 5:  Data qubit allocation example.
(a) A modified device from Figure 4(a). Red circles indicate physical qubits
with high degree of connectivity (i.e. with 3 or more edges). (b) Finding
compatible bridge rectangles. (c) Locating data qubits. (d) Final data qubit
layout and syndrome rectangles.

Since we decided to fix the location of data qubits, the basic requirement is
that the measurement circuits can be feasibly constructed for all stabilizers.
To ensure this property is guaranteed in the data qubit mapping we found, we
have the following proposition regarding the bridge tree construction.

######  Proposition 1.

In any bridge tree for a stabilizer having support on four data qubits, there
are at least one four-degree node or two three-degree nodes.

###### Proof.

For any graph $G(V,E)$ where $V$ is the vertex set and $E$ is the edge set, we
have $\sum_{v\in V}deg(v)=2|E|$. An $n$-vertex tree always has $n-1$ edges. A
bridge tree with four data qubits has four $1$-degree leaf nodes and all other
nodes should have degree of at least $2$. Therefore we have $4+\sum_{v\in
V\backslash\text{data qubits}}deg(v)=2n-2$ and $\sum_{v\in
V\backslash\text{data qubits}}deg(v)=2n-6=2(n-4)+2$. We only have $n-4$
vertices after removing the four leaf nodes. So we must have at least one
four-degree node or two three-degree nodes. ∎

Proposition 1 provides a necessary condition for a feasible data qubit layout.
For each stabilizer to be executable, we should ensure that there are enough
three-degree or four-degree qubits around data qubits of this stabilizer. We
then introduce a graph-based data qubit layout where we can find bridge trees
‘locally’. A local bridge tree locates inside the spatial area bounded by the
data qubits of a stabilizer. Such a bridge tree is promising as it often leads
to a shallow measurement circuit. We use the SC device shown in Figure 5(a) to
illustrate the data qubit allocation algorithm. We embed the coupling graph of
this SC device into a 2D grid so that all qubits can be referenced by the
spatial coordinates on the plane. Such embedding is possible as latest SC
processors are usually designed in a modular structure.

Since high-degree nodes are critical, we keep a list (denoted by $L_{h}$) of
all three- and four-degree nodes in the device grid and record their
coordinates. In Figure 5(a),
$L_{h}=\\{Q_{2},Q_{4},Q_{10},Q_{12},Q_{13},Q_{18},Q_{21}\\}$. We then process
the list of high degrees sequentially. For the next node $n_{a}$ in $L_{h}$,
if it is a three-degree node, we search for its nearest high-degree node
$n_{b}$ and then create a minimal rectangle that contains $n_{a}$ and $n_{b}$
as well as their neighboring qubits. If $n_{a}$ is node with degree $\geq 4$,
then we create a rectangle that contains $n_{a}$ and its neighboring qubits.
The rectangle created at this step is called “bridge rectangle”. Figure 5(a)
depicts five bridge rectangles resulted from $\\{Q_{2},Q_{10}\\}$,
$\\{Q_{10}\\}$, $\\{Q_{4},Q_{12}\\}$, $\\{Q_{13},Q_{21}\\}$ and
$\\{Q_{18},Q_{10}\\}$ , and we index them from 1 to 5. There are also other
bridge rectangles that can be identified, but we omit them here for
simplicity.

We can now determine the position of data qubits by using bridge rectangles.
As shown in Figure 1, each data qubit is shared by four stabilizers. Thus, we
can fix the position of a data qubit with four bridge rectangles. We begin
with rectangle 1 to find four compatible bridge rectangles. We can also begin
with rectangle 2 which is created from a four-degree qubit. This will create a
different surface code synthesis and we will discuss it in Section 5. Here we
focus on rectangle 1. Two bridge rectangles are said to be compatible if their
intersection area is zero. As we can see in Figure 5(b), rectangle 2 is not
compatible with rectangle 1 and rectangle 4, while rectangles 1, 3, 4, and 5
are mutually compatible. We do not use incompatible rectangles because they
may not allow a feasible data qubit mapping. We then search for data qubits in
the potential data area (black rectangle in Figure 5(c)) which is enclosed by
four compatible bridge rectangles, as shown in Figure 5(c). If the potential
data area is empty, we choose another four compatible bridge rectangles.
Otherwise, we pick the qubit at the center of the potential data area as a
data qubit.

For boundary cases, we may not have enough bridge rectangles to locate one
data qubit. For example, for rectangle 3, its bottom right corner is only
neighbored by rectangle 5. In this case, we should locate the data qubit with
constraints only from these two bridge rectangles. Specifically, a potential
data qubit should satisfy: A) its x axis value $\geq$ the largest x axis value
in rectangle 3 and 5; B) its y axis value should lie between the largest y
axis value of rectangle 3 and the smallest y axis value of rectangle 5. With
these spatial constraints, the only qubit we can find is $Q_{14}$, as shown in
Figure 5(c). Other data points are found in a similar way.

The final layout for data qubits and syndrome rectangles defined by data
qubits are shown in Figure 5(d). A syndrome rectangle is the extension of the
bridge rectangle to include allocated data qubits. We can then assign a
stabilizer to each syndrome rectangle and synthesize the corresponding
measurement circuits locally (using qubits inside each syndrome rectangle).
The syndrome rectangle ensures the existence of local bridge trees and enables
a natural data qubit assignment for the assigned stabilizer. For the
stabilizer $X_{abcd}$ (or $Z_{abcd}$) in Figure 1, we can simply assign the
topmost data qubit in a syndrome rectangle to be the data qubit ‘a’, with the
leftmost, rightmost, and bottom data qubit being data qubits ‘b’, ‘c’, ‘d’,
respectively. In the next section, we will discuss how to find an efficient
bridge tree to connect data qubits $\\{a,b,c,d\\}$.

###  4.2 Bridge tree finder

1

Input: A syndrome rectangle $R$ with data qubits $\\{a,b,c,d\\}$

Output: Candidate bridge trees

2

$star\\_trees=[]$; // bridge trees generated by the star tree method;

$branching\\_trees=[]$; // bridge trees generated by the star tree method;

3

4for  _$qb$ in $R$_ do

5 $T$ = the bridge tree by connecting qubit $qb$ to data qubits
$\\{a,b,c,d\\}$ with shortest paths;

6 update $star\\_trees$ s.t. it only contains trees no larger than $T$;

7

8 end for

9

10let $\\{a^{\prime},b^{\prime},c^{\prime},d^{\prime}\\}$ be a arrangement of
$\\{a,b,c,d\\}$ s.t.
$l_{a^{\prime}b^{\prime}}+l_{c^{\prime}d^{\prime}}=\min\\{l_{ab}+l_{cd},l_{ac}+l_{bd},l_{ad}+l_{bc}\\}$;

// $l_{ab}$ is the distance of $a\to b$;

11

12connect $a^{\prime}$ and $b^{\prime}$, $c^{\prime}$ and $d^{\prime}$ with
shortest paths, respectively;

13

14connect the path $a^{\prime}\to b^{\prime}$ and $c^{\prime}\to d^{\prime}$
with shortest paths;

15

16for  _$qb_{1}$ in $a^{\prime}\to b^{\prime}$, $qb_{2}$ in $c^{\prime}\to
d^{\prime}$_ do

17 $T$ = the bridge tree by connecting $qb_{1}$ and $qb_{2}$ by shortest
paths;

18 update $branching\\_trees$ s.t. it only contains trees no larger than $T$;

19

20 end for

21Merge $star\\_trees$ and $branching\\_trees$ to find a list of minimal
bridge trees;

Algorithm 2 Bridge tree finder Figure 6:  Finding bridge trees in a syndrome
rectangle with data qubits $\\{a,b,c,d\\}$. (a)(b) shows the case where path
merge is efficient, while (c) shows when path merge incurs extra overhead. (a)
Green edges denote the shortest paths from qubit $E$ to data qubits and these
paths form a bridge tree with length 10. (b) Blue edges form a bridge tree
with length 8. (c) An example where data qubits are close to each other.

After locating the data qubits and syndrome rectangles, we then construct the
bridge tree for each syndrome rectangle. Since syndrome rectangles only
intersect at borderlines, strict local bridge trees, whose bridge qubits all
locate within the interior of the syndrome rectangle, will enable concurrent
measurement of stabilizers naturally. Thus, we only consider finding bridge
trees in the syndrome rectangle. To enable higher stabilizer measurement
fidelity, we prefer using small bridge trees. Actually, the error correction
of the synthesized code is sensitive to the length of the bridge tree because
one more edge in the bridge tree will result in two more CNOT gates in the
measurement circuit and likely leads to a high probability of correlated
errors which are hard to detect and correct. Thus, bridge trees should be as
small as possible.

One natural way for finding small bridge trees is to first locate the bridge
tree root and then connect the tree root to data qubits with shortest paths.
We denote this method by “star tree” method. One drawback of this method is
that it may miss the opportunity of path merge. For example, in the syndrome
rectangle in Figure 6(a), the bridge tree induced by the shortest paths from
interior qubit $E$ to data qubits has a length 10 (green edges) . In contrast,
by merging paths $E\to F\to b$ and $E\to d$, we can get a bridge tree of
length 8 (blue edges in Figure 6(b)) , which reduces the number of CNOT gates
by at least 4 in the resulted stabilizer measurement circuit.

To overcome the problem above, we propose the “branching tree” method, which
first connects close data qubit pairs by shortest paths and then connects
these shortest paths to build a complete bridge tree (pseudo code in in
Algorithm 2). Suppose we are constructing the bridge tree for the syndrome
rectangle in Figure 6(a). We first find the shortest paths $a\to c$ and $b\to
d$, since $l_{ac}+l_{bd}$ ($l_{ac}$ is the length of the shortest path from
$a$ to $c$) is shorter than $l_{ab}+l_{cd}$ and $l_{ad}+l_{bc}$. We then
connect path $a\to c$ and $b\to d$ with the path $E\to F$, immediately
resulting in the small bridge tree (blue edges) in Figure 6(b). The following
proposition bounds the length of the bridge tree generated by the branching
tree method:

######  Proposition 2.

Let the total edge length of the bridge tree $T$ generated by the branching
tree method be $E(T)$, then,

$E(T)\leq\frac{1}{2}(l_{ab}+l_{ac}+l_{ad}+l_{bc}+l_{bd}+l_{cd}).$

###### Proof.

W.l.o.g., we assume $l_{ab}+l_{cd}\leq\min\\{l_{ac}+l_{bd},l_{ad}+l_{bc}\\}$.
Then in $T$, we first connect $a$ and $b$, $c$ and $d$, respectively. On the
other hand, the distance between shortest paths $a\to b$ and $c\to d$ is
smaller than $\min\\{l_{ac},l_{ad},l_{bc},l_{bd}\\}$. This proposition then
can be proved by combining these two inequality. ∎

Generally, the branching tree method is more efficient if
$\min\\{l_{ab}+l_{cd},l_{ac}+l_{bd},l_{ad}+l_{bc}\\}$ is small, as shown in
Figure 6(a)(b). In this case, the length of the resulted branching tree is
very close to $\frac{1}{2}(l_{ad}+l_{bc})$. Instead, the length of a star tree
is at least $\max\\{l_{ad},l_{bc}\\}+2$, thus leading to a larger bridge tree.
On the other hand, if $\max\\{l_{ab}+l_{cd},l_{ac}+l_{bd},l_{ad}+l_{bc}\\}$ is
small, the benefit of path merge may not cancel out its overhead for not using
shortest paths. Figure 6(c) shows an example where the star tree has shorter
length. In practice, we will run both star tree method and branching tree
method and find small bridge trees by merging the result of these two methods,
as shown in Algorithm 2. Once the bridge tree is determined, we can assign the
syndrome qubit to the center node of the bridge tree.

Overall, Algorithm 2 can generate small bridge trees that approximate the
optimal bridge tree as long as the distance between data qubits is small (by
Proposition 2). Another feature of Algorithm 2 is that it may find many
different bridge trees for a stabilizer since the shortest paths between nodes
are not unique. This feature provides some flexibility for the stabilizer
scheduling discussed in the next section.

###  4.3 Stabilizer measurement scheduler

Input: Binary tuples of stabilizer and syndrome rectangle: $\\{(s,R)\\}$.

Output: A schedule $P$ of binary tuples of stabilizer and bridge trees.

// Schedule initialization;

1 $S_{1}=$ tuples of X-stabilizers and syndrome rectangles;

2 $S_{2}=$ tuples of Z-stabilizers and syndrome rectangles;

3 if  _$exec\\_time(S_{1}) <exec\\_time(S_{2})$_ then

4 swap($S_{1}$, $S_{2}$);

5

// Iterative refinement;

6 repeat

7 $r_{2}$ = $(s,R)$ in $S_{2}$ that has longest execution time;

8 $swap\\_list=[r_{2}]$;

9 for  _$i$ in $[0:k]$_ do

10 $S=S_{i\%2+1}$;

11 for  _$r$ in $swap\\_list$_ do

12 $swap\\_list.remove(r)$; $S.append(r_{2})$;

13 for  _$r_{1}$ in $S$ in descending order _ do

14 if  _$r_{1}$ and $r$ does not have compatible bridge trees_ then

15 if  _$exec\\_time(r_{1}) >exec\\_time(r)$_ then

16 terminate the refinement loop;

17

18 $swap\\_list.append(r_{1})$;

19 $S.remove(r_{1})$;

20

21 end for

22 if  _$swap\\_list==\emptyset$_ then

23 break;

24

25

26 end for

27

28 end for

29 if  _$swap\\_list\neq\emptyset$ _ then

30 recover $S_{1}$ and $S_{2}$ to the values before this iteration;

31 break;

32

33until  _$S_{1}$ converges_;

34

Algorithm 3 Iterative stabilizer scheduler

The order of stabilizer measurements affects the time required by the error
detection protocol. Our goal is to reduce the time requirement for all
stabilizer measurements since it will naturally reduce the decoherence error
during the process of stabilizer measurements. To achieve this goal, we need
to measure as many stabilizers as possible in parallel. Yet the fact that only
compatible bridge trees that do not have common bridge qubits can be measured
simultaneously imposes a constraint for stabilizer measurement scheduling:
only stabilizers that have compatible bridge trees can be measured in the same
time. A valid schedule for the order of stabilizer measurements should avoid
executing two “conflicted” stabilizers together. To satisfy the constraint of
stabilizer measurement scheduling yet exploit the parallelism in stabilizer
measurements, we propose a heuristic scheduling approach in Algorithm 3, which
consists of two steps: schedule initialization and refinement loop.

#### Schedule initialization

the proposed data qubit allocation ensures that syndrome rectangles of the
same type do not have bridge tree conflicts, i.e., the measurements of X (or
Z) stabilizers are compatible with each other. We then initialize the
stabilizer measurement schedule by two sets $S_{1}$ and $S_{2}$ which contain
X- and Z-type stabilizers, respectively.

#### Refinement Loop

the core idea of the refinement loop in Algorithm 3 is to move stabilizers
with large bridge trees into one set. The motivation for such refinement is
that the execution time for a set of stabilizers is determined by the
stabilizer with the deepest measurement circuit. With the refinement loop,
except one stabilizer set which contains stabilizers with large bridge trees,
remaining stabilizer sets only include stabilizers with small bridge trees and
can be measured in a short time.

To illustrate how the Algorithm 3 works, suppose we are given stabilizers and
syndrome rectangles in Figure 7. Initially, we have
$S_{1}=\\{(s_{1},R_{1}),(s_{4},R_{4}),(s_{5},R_{5})\\}$ and
$S_{2}=\\{(s_{2},R_{2}),(s_{3},R_{3}),(s_{6},R_{6})\\}$. We then send the
largest element in $S_{2}$, which is $(s_{2},R_{2})$ in this case, to the
$swap\\_list$ and swap it into $S_{1}$. Since $(s_{4},R_{4})$ and
$(s_{2},R_{2})$ do not have compatible bridge trees, we will move
$(s_{4},R_{4})$ to $S_{2}$. In $S_{2}$, $(s_{6},R_{6})$ is not compatible with
$(s_{4},R_{4})$, so it will be swapped into $S_{1}$. After this swap, the
refinement loop will stop since the $swap\\_list$ is empty and every
stabilizer in $S_{1}$ has a larger bridge tree than the stabilizer in $S_{2}$.
The resulted stabilizer schedule is shown in Figure 7(b). Comparing to the
initial schedule, the refined schedule in Figure 7(b) reduces the error
detection cycle by one time step, and reduces the CNOT gate number by two.

The stabilizer measurement schedule found by the proposed heuristic should be
better than the schedule where different types of stabilizers are measured in
different rounds since every successful refinement iteration returns a better
stabilizer measurement schedule.

Figure 7:  An example of stabilizer measurement scheduling.

##  5 Evaluation

In this section, we first evaluate the proposed synthesis framework “Surfmap”
by comparing the generated surface codes with state-of-the-art manually
designed QEC codes. We then demonstrate the efficiency of the proposed
synthesis framework by analyzing the error correction performance and resource
overhead of the synthesized surface codes on mainstream SC architectures.

###  5.1 Experiment Setup

#### Evaluation setting

We use the flag-bridge circuit [22] as the backend for instantiating
stabilizer measurement circuits. We select this backend because it provides
the extra feature of fault-tolerant error correction. We implement all
numerical simulations with stim v1.5.0, which is a fast stabilizer circuit
simulator [32]. We use PyMatching v0.4.0 [33] for error decoding with
measurement signals from bridge qubits. Error rates are computed by performing
$10^{5}$ simulations, on a Ubuntu 18.04 server with a 6-core Intel E5-2603v4
CPU and 32GB RAM.

#### Metrics

We evaluate the error threshold of the synthesized surface codes to
demonstrate their error correction performance. Error threshold indicates what
hardware error rates can be tolerated and a higher error threshold is
preferred. Time-step counts in an error detection cycle can also indicate the
error correction performance [15]. The time-step counts also determines the
execution speed of the surface code. A small time-step count is preferred.
Finally, We evaluate the resource requirement of the synthesized surface codes
with CNOT counts and qubit counts. A resource-efficient synthesis should use
less CNOT gates and bridge qubits.

#### Device Architectures

we use two categories of device architectures. The architectures are shown in
Table 1. The first category architectures are built by tiling polygons and
serve as basic structures for many SC devices, _e.g._ Google’s Sycamore [1]
and IBM’s latest machines [34]. The second category architectures consist of
‘heavy’ architectures which insert one qubit for each edge of polygon devices.
Edges with one extra qubit in the middle are called “heavy edges”. Heavy
architectures have lower average qubit connectivity because of the inserted
two-degree qubits. Heavy architectures are used by IBM devices [34]. Square
and heavy square architectures can be embedded into a 2D grid naturally.
Hexagon and heavy hexagon architectures can be embedded into a 2D grid by
squashing the hexagon into the shape of a rectangle.

Table 1: Overview of device architectures.

Type |  Name |  Building blocks | Tilling Example |  Remark
---|---|---|---|---
Polygon Arch |  Square |  |  |  Each square can have at most four neighboring squares for tiling.
Hexagon |  |  |  Each hexagon can have at most six neighboring hexagons for tiling.
Heavy Arch |  Heavy square |  |  |  Heavy squares are tiled like squares.
Heavy hexagon |  |  |  Heavy hexagons are tiled like hexagons.

#### Error model

In all simulations, we assume the following circuit-level error model: For the
gate error, we assume an error probability $p_{e}$ for the single-qubit
depolarizing error channel on single-qubit gates, the two-qubit depolarizing
error channel on two-qubit gates and the Pauli-X error channel on measurement
and reset operations. For the idle decoherence error, we assume each idle
qubit is followed by a single-qubit depolarizing error channel per gate
duration with error probability $0.0002$, which is estimated by the
decoherence error formula $1-e^{-\frac{t}{T}}\approx 0.0002$, with the gate
execution time $t=20\,ns$ and the relaxation or dephasing time $T=100\,\mu s$.

These errors happen on all qubits, including data qubits and bridge qubits.

###  5.2 Comparing to manually designed QEC code

We first compare our synthesized surface code to the two manually designed QEC
codes by Chamberland et al. [21] on heavy architectures. Figure 8(a)(b) shows
the qubit layout and stabilizer measurement circuits of our synthesized
surface codes on the heavy square architecture (‘Surfmap Heavy Square’) and
the heavy hexagon architecture (‘Surfmap Heavy Hexagon’), Figure 8(c)(d) shows
the manually designed QEC codes on the heavy square architecture (‘IBM Heavy
Square’) and the heavy hexagon architecture (‘IBM Heavy Hexagon’). The error
thresholds of these codes are in Figure 9.

Overall, compared with the manually and specifically designed codes on the two
architectures, the surface codes synthesized by Surfmap can have comparable or
even better performance. On the heavy hexagon architecture, the error
threshold of ‘Surfmap Heavy Hexagon’ is 0.0033% which is 106% higher than that
of ‘IBM Heavy Hexagon’ (0.0016%), as shown in Figure 9(a). Such benefit comes
from the fact that the ‘IBM Heavy Hexagon’ code uses the Bacon-Shor scheme for
Pauli Z-error correction (Figure 8(d)) which is not as effective as the
surface code. On the heavy square architecture, the error threshold of
‘Surfmap Heavy Square’ is the same as that of ‘IBM Heavy Square’, as shown in
Figure 9(b). This is because the code synthesized by Surfmap is almost
identical to that of ‘IBM Heavy Square’ except stabilizers on boundaries, as
shown in Figure 8(a)(c). In summary, Surfmap can automatically generate QEC
codes that have similar or even better error correction performance compared
with manually designed codes on the two studied architectures.

(a) Surfmap Heavy Square(b) Surfmap Heavy Hexagon(c) IBM Heavy Square(d) IBM
Heavy Hexagon Figure 8: The synthesized distance-3 surface code by Surfmap and
the two manually designed QEC codes by IBM [21]. IBM removes some boundary
nodes (dotted) and edges (dotted) for better efficiency of stabilizer
measurements on borderline.  (a) Heavy Hexagon(b) Heavy Square Figure 9: The
simulated error thresholds of the synthesized surface codes by Surfmap and the
two manually designed QEC codes by IBM [21].

###  5.3 Synthesis on various SC architectures

(a) Surfmap Square(b) Surfmap Hexagon Figure 10: First four stabilizers of the
synthesized distance-5 surface code on square and hexagon architectures.  (a)
Surfmap Square-4(b) Surfmap Heavy Square-4 Figure 11: First four stabilizers
of the synthesized distance-5 surface code by using syndrome rectangles
induced by four-degree qubits.  Figure 12: Numerical simulation results for
the logical error rates of the synthesized surface codes on various SC
architectures.  Table 2: Error correction metrics of the synthesized surface
codes. The average numbers of bridge qubits, CNOT gates, and time steps are
computed over all X-type stabilizers.

Code |  Avg. bridge qubit # |  Avg. CNOT # |  Avg. time-step # |  Tot. time-step # |  Estimated error threshold
---|---|---|---|---|---
Surfmap Heavy Sqaure |  3 |  8 |  12 |  24 |  0.53%
Surfmap Heavy Hexagon |  7 |  19 |  20 |  40 |  0.33%
Surfmap Sqaure |  2 |  6 |  10 |  20 |  0.63%
Surfmap Hexagon |  4 |  10 |  13 |  26 |  0.47%
Surfmap Sqaure-4 |  1 |  4 |  8 |  8 |  0.70%
Surfmap Heavy Sqaure-4 |  5 |  12 |  13 |  13 |  0.42%

Table 3: Qubit utilization of the distance-5 surface codes synthesized by
Surfmap on different architectures.

Code |  data qubit % |  bridge qubit % |  unused qubit % |  Tot. qubit #
---|---|---|---|---
Surfmap Heavy Sqaure |  31.7% |  45.6% |  22.8% |  79
Surfmap Heavy Hexagon |  18.8% |  59.4% |  21.8% |  133
Surfmap Square |  55.6% |  44.4% |  0.0% |  45
Surfmap Hexagon |  30.5% |  48.8% |  20.7% |  82
Surfmap Square-4 |  43.9% |  56.1% |  0.0% |  57
Surfmap Heavy Sqaure-4 |  16.3% |  83.7% |  0.0% |  153

We then apply Surfmap on the square architecture and the hexagon architecture
to demonstrate that Surfmap can accommodate various architectures. The
synthesized surface codes on these two architectures are shown in Figure 10.
We also include another two surface code synthesis generated by using syndrome
rectangles centering around four-degree qubits, as shown in Figure 11. Table 2
and Figure 12 summarizes the error correction performance of these synthesized
surface codes. Table 3 shows the resource requirement of the synthesized
surface codes, and is obtained by finding the smallest tiling of building
blocks for each architecture that is able to support the distance-5 surface
code, and then computing the ratios of different types of qubits.

#### The effect of architecture

High-degree architectures are more effective for surface code synthesis than
low-degree architectures, both in error correction performance and resource
requirement. Comparing to polygon architectures, heavy architectures reduces
the error threshold by 26.7% on average and they increases the average time-
step number by 40.7% averagely. Heavy architectures also increase bridge qubit
number by 114% averagely, up to 400%. However, low-degree devices has a much
lower physical error rate and are easier to fabricate than high-degree
devices.

#### The effect of synthesis design

Synthesis centering four-degree qubits has higher resource overhead than the
synthesis induced by a pair of three-degree qubits. In Table 3, 26.7% and
93.7% more qubits are required for ‘Surfmap Square-4’ and ‘Surfmap Heavy
Square-4’ than ‘Surfmap Square’ and ‘Surfmap Heavy Square’, respectively.
Also, on low-degree architectures, the synthesis induced by four-degree qubits
may have lower error threshold. Comparing to ‘Surfmap Heavy Square’, ‘Surfmap
Heavy Square-4’ downgrades the error threshold by 20.8%.

In summary, not only the architecture design but also the synthesis design
have a critical impact on the resource overhead and error correction
performance of the synthesized code. By optimizing the three key steps in
surface code synthesis, our framework is able to mitigate the detrimental
effect of low-degree architectures. In fact, both using syndrome rectangles
induced by four-degree qubits, ‘Surfmap Heavy Square-4’ only achieves 60%
error correction performance of ‘Surfmap Square-4’ (the ideal surface code)
while ‘Surfmap Heavy Square’ achieves 75.7% error correction performance of
‘Surfmap Square-4’. On the other hand, comparing to the synthesized code on
the hexagon architecture whose asymptotic average node degree is 3, ‘Surfmap
Heavy Square’ on the heavy square architecture, whose asymptotic average node
degree is 2.3, achieves a 12.8% higher error threshold. These evaluation
results demonstrate the effectiveness of the proposed framework for automatic
surface code synthesis on any SC architectures.

###  5.4 Architecture Design Implications

Our synthesis results provide some insights for designing future SC quantum
architectures that can efficiently execute the surface code. Starting from the
ideal 2D qubit array equipped with the surface code in Figure 13(a), we
discuss how to reduce the connectivity of the ideal 2D qubit array while
preserving the efficiency for surface code synthesis.

(a)(b)(c)(d)(e)(f) Figure 13: An example for potential architecture design.

#### Insert two-degree nodes selectively

Heavy edges or extra two-degree nodes are harmful to the synthesized surface
code. Yet, they can be essential when lowering the device design and
fabrication complexity [35]. As a compromise, we can insert two-degree nodes
selectively.

First, we should avoid inserting two-degree nodes both in X-type syndrome
rectangles and Z-type syndrome rectangles. This is because we can confine the
detrimental effect of two-degree nodes only within one stabilizer set in this
way. Figure 13(b) gives an example where two-degree nodes are inserted into
both X- and Z-type syndrome rectangles. Comparing to the architecture in
Figure 13(c) which only inserts nodes in Z-type syndrome rectangles, the
architecture in Figure 13(b) will have two more time-steps in each error
detection cycle. Second, it may be of merit to insert two-degree nodes in
small syndrome rectangles of a scheduled stabilizer set. A stabilizer set may
have syndrome rectangles of different sizes. Inserting two-degree nodes in
small syndrome rectangles may not increase the error detection cycle time. For
example, the error detection cycle length of the architecture in Figure 13(d)
is the same as the one in Figure 13(c).

#### Remove useless structures

The unused qubits and physical connections for hexagon and heavy architectures
are not a few, as indicated by Table 3. There are several types of useless
structures in these architectures, including the architecture in Figure 13(d).
First, connections between data qubits do not provide any benefits for
constructing non-conflicted bridge trees. We can remove such connections to
lower device complexity, as shown in Figure 13(e). Second, qubits and
connections on the boundaries of these architectures may not be used by any
stabilizers and can thus be removed. For example, the qubits on the top right
and bottom left corners of Figure 13(e) can be removed and the resulted
architecture is shown in Figure 13(f).

##  6 Related Work

Circuit compilation over the surface code: Most circuit compilation work on
surface code are at the higher logical circuit level. Javadi et al. [18] and
Hua et al. [19] studied the routing congestion in circuit compilation over the
surface code. Ding et al. [16] and Paler et al. [17] studied the compilation
of magic state distillation circuits with existing surface code logical
operations. These works usually assume that the ideal surface code array is
already available and do not consider the problem of surface code synthesis on
hardware. In contrast, this paper focuses on optimizing the lower-level
surface code synthesis on various SC architectures.

QEC code and architecture: most efforts on QEC code synthesis are still on
looking for an architecture that is suitable for the target code. Reichardt
[36] proposes three possible planar qubit layouts for synthesizing the seven-
qubit color code. Chamberland et al. [31] proposes a trivalent architecture
where it is straightforward to allocate data qubits of triangular color codes.
Chamberland et al. [21] introduces heavy architectures which reduces frequency
collision while still provides support for surface code synthesis. Instead,
the synthesis framework in this paper can automatically synthesize the surface
code onto various mainstream architectures and avoid manually redesigning code
protocols for the ever-changing architectures. Another line of research
targets at compiling stabilizer measurement circuits to existing
architectures. Lao and Almudever [22] proposes the flag-bridge circuit which
can measure the stabilizer of the Steane code on the IBM-20 device. However,
their work relies on manually appointed data qubits and bridge qubits, and
focuses on the IBM-20 device. Methods in this category are orthogonal to our
work, and can be easily merged into our framework.

##  7 Discussion

Though we propose a comprehensive framework to synthesize surface code on
various SC devices, there is still much space left for potential improvements.
For example, besides heuristic data qubit allocation schemes, it is also
promising to train a neural network to allocate data qubits. Non-local bridge
trees may also be explored for better parallelism of stabilizer measurements.
It is also possible to merge bridge trees to resolve bridge qubit conflict.
However, this requires careful tuning since large bridge trees may be
detrimental for error detection. We do not include the error decoder design as
our work mainly focus on surface code synthesis. Though we can reuse previous
surface code decoders [21, 37, 38, 39], there may be some opportunities to
devise more accurate error decoders for the proposed surface code synthesis
scheme.

Another interesting future direction is to adapt our synthesis framework to
other error correction codes. Though surface code can be implemented on
various SC devices, it may not be the most efficient one. Extending our
framework to other error correction codes can help us fully exploiting
existing device architectures for FT computation. On other hand, the proposed
surface code synthesis framework can provide guidance for SC architecture
design. Using our framework as the baseline, we can compare the efficiency of
different device architectures for implementing surface code and identify the
most efficient one.

##  8 Conclusion

In this paper, we formally describe the three challenges of synthesizing
surface code on SC devices and present a comprehensive synthesis framework to
overcome these challenges. The proposed framework consists of three
optimizations. First, we adopt a geometrical method to allocate data qubits in
a way that ensures the existence of shallow measurement circuits. Second, we
only consider bridge qubits enclosed by data qubits and reduce the number of
bridge qubits by merging short paths between data qubits. The proposed bridge
qubit optimization reduces the resource conflicts between syndrome
measurement. Third, we propose an iterative heuristic to schedule the
execution of measurement circuits based on the proposed data qubit allocation.
Our comparative evaluation to manually designed QEC codes demonstrates that,
with good optimization, automated synthesis can surpass manual QEC code design
by experienced theorists.

## References

  * [1] F. Arute, K. Arya, R. Babbush, D. Bacon, J. Bardin, R. Barends, R. Biswas, S. Boixo, F. Brandão, D. Buell, B. Burkett, Y. Chen, Zijun Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, Keith Guerin, Steve Habegger, M. Harrigan, M. Hartmann, A. Ho, M. Hoffmann, Trent Huang, T. Humble, S. Isakov, E. Jeffrey, Zhang Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, Mike Lindmark, E. Lucero, Dmitry I. Lyakh, Salvatore Mandrà, J. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Niu, E. Ostby, A. Petukhov, John C. Platt, C. Quintana, E. Rieffel, P. Roushan, N. Rubin, D. Sank, K. Satzinger, V. Smelyanskiy, Kevin J. Sung, M. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. Yao, P. Yeh, Adam Zalcman, H. Neven, and J. Martinis.  Quantum supremacy using a programmable superconducting processor.  Nature, 574:505–510, 2019.
  * [2] Pieter Kok, William J. Munro, Kae Nemoto, Timothy C. Ralph, Jonathan P. Dowling, and Gerard J. Milburn.  Linear optical quantum computing with photonic qubits.  Reviews of Modern Physics, 79:135–174, 2007.
  * [3] David P. DiVincenzo and Ibm.  The physical implementation of quantum computation.  Protein Science, 48:771–783, 2000.
  * [4] Torsten Asselmeyer-Maluga.  3d topological quantum computing.  International Journal of Quantum Information, 2021.
  * [5] J. Kelly.  A Preview of Bristlecone, Google’s New Quantum Processor.  https://ai.googleblog.com/2018/03/a-preview-of-bristlecone-googles-new.html, 2017\.
  * [6] Hanhee Paik, David I. Schuster, Lev Bishop, Gerhard Kirchmair, Gianluigi Catelani, Adam P. Sears, B. R. Johnson, Matthew Reagor, Luigi Frunzio, Leonid I. Glazman, Steven M. Girvin, Michel H. Devoret, and Robert J. Schoelkopf.  Observation of high coherence in josephson junction qubits measured in a three-dimensional circuit qed architecture.  Physical review letters, 107 24:240501, 2011.
  * [7] Yu Chen, Charles J. Neill, Pedram Roushan, Nelson Leung, Michael Fang, Rami Barends, Julian Kelly, Brooks Campbell, Z Chen, Benjamin Chiaro, Andrew Dunsworth, Evan Jeffrey, Anthony Megrant, Josh Mutus, P. J. J. O’Malley, Chris Quintana, Daniel Thomas Sank, Amit Vainsencher, J. Wenner, Theodore White, Michael R. Geller, Andrew N Cleland, and John M. Martinis.  Qubit architecture with high coherence and fast tunable coupling.  Physical review letters, 113 22:220502, 2014.
  * [8] Eric J Zhang, Srikanth Srinivasan, Neereja Sundaresan, Daniela F Bogorin, Yves Martin, Jared B Hertzberg, John Timmerwilke, Emily J Pritchett, Jeng-Bang Yau, Cindy Wang, et al.  High-fidelity superconducting quantum processors via laser-annealing of transmon qubits.  arXiv preprint arXiv:2012.08475, 2020.
  * [9] Alysson Gold, Anna Stockklauser, Matt Reagor, Jean-Philip Paquette, Andrew Bestwick, Cody James Winkleblack, Ben Scharmann, Feyza Oruc, and Brandon Langley.  Experimental demonstration of entangling gates across chips in a multi-core qpu.  Bulletin of the American Physical Society, 2021.
  * [10] Peter W Shor.  Scheme for reducing decoherence in quantum computer memory.  Physical review A, 52(4):R2493, 1995.
  * [11] Andrew M Steane.  Error correcting codes in quantum theory.  Physical Review Letters, 77(5):793, 1996.
  * [12] A Robert Calderbank and Peter W Shor.  Good quantum error-correcting codes exist.  Physical Review A, 54(2):1098, 1996.
  * [13] Andrew Steane.  Multiple-particle interference and quantum error correction.  Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 452(1954):2551–2577, 1996.
  * [14] Sergey B Bravyi and A Yu Kitaev.  Quantum codes on a lattice with boundary.  arXiv preprint quant-ph/9811052, 1998.
  * [15] Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N Cleland.  Surface codes: Towards practical large-scale quantum computation.  Physical Review A, 86(3):032324, 2012.
  * [16] Yongshan Ding, Adam Holmes, Ali JavadiAbhari, Diana Franklin, Margaret Martonosi, and Frederic T. Chong.  Magic-state functional units: Mapping and scheduling multi-level distillation circuits for fault-tolerant quantum architectures.  2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 828–840, 2018.
  * [17] Alexandru Paler.  Surfbraid: A concept tool for preparing and resource estimating quantum circuits protected by the surface code.  ArXiv, abs/1902.02417, 2019.
  * [18] Ali JavadiAbhari, Pranav Gokhale, Adam Holmes, Diana Franklin, Kenneth R. Brown, Margaret Martonosi, and Frederic T. Chong.  Optimized surface code communication in superconducting quantum computers.  2017 50th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 692–705, 2017.
  * [19] Fei Hua, Yan-Hao Chen, Yuwei Jin, Chi Zhang, Ari B. Hayes, Youtao Zhang, and Eddy Z. Zhang.  Autobraid: A framework for enabling efficient surface code communication in quantum computing.  MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture, 2021.
  * [20] Swamit S. Tannu, Zachary Myers, Prashant J. Nair, Douglas M. Carmean, and Moinuddin K. Qureshi.  Taming the instruction bandwidth of quantum computers via hardware-managed error correction.  2017 50th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 679–691, 2017.
  * [21] C. Chamberland, Guanyu Zhu, Theodore J. Yoder, J. Hertzberg, and A. Cross.  Topological and subsystem codes on low-degree graphs with flag qubits.  Physical Review X, 10, 2020.
  * [22] L. Lao and C. G. Almudéver.  Fault-tolerant quantum error correction on near-term quantum processors using flag and bridge qubits.  Physical Review A, 101:032333, 2020.
  * [23] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill.  Topological quantum memory.  Journal of Mathematical Physics, 43(9):4452–4505, 2002.
  * [24] Rami Barends, Julian Kelly, Anthony Megrant, Andrzej Veitia, Daniel Sank, Evan Jeffrey, Ted C White, Josh Mutus, Austin G Fowler, Brooks Campbell, et al.  Superconducting quantum circuits at the surface code threshold for fault tolerance.  Nature, 508(7497):500–503, 2014.
  * [25] Michael A Nielsen and Isaac Chuang.  Quantum computation and quantum information, 2002.
  * [26] Daniel Gottesman.  Class of quantum error-correcting codes saturating the quantum hamming bound.  Physical Review A, 54(3):1862, 1996.
  * [27] A Robert Calderbank, Eric M Rains, Peter W Shor, and Neil JA Sloane.  Quantum error correction and orthogonal geometry.  Physical Review Letters, 78(3):405, 1997.
  * [28] Emanuel Knill, Raymond Laflamme, and Lorenza Viola.  Theory of quantum error correction for general noise.  Physical Review Letters, 84(11):2525, 2000.
  * [29] R. Chao and B. Reichardt.  Flag fault-tolerant error correction for any stabilizer code.  arXiv: Quantum Physics, 2019.
  * [30] C. Chamberland and M. Beverland.  Flag fault-tolerant error correction with arbitrary distance codes.  arXiv: Quantum Physics, 2:53, 2017.
  * [31] C. Chamberland, Aleksander Kubica, Theodore J. Yoder, and Guanyu Zhu.  Triangular color codes on trivalent graphs with flag qubits.  arXiv: Quantum Physics, 2019.
  * [32] Craig Gidney.  Stim: a fast stabilizer circuit simulator.  Quantum, 5:497, July 2021.
  * [33] Oscar Higgott.  PyMatching: A python package for decoding quantum codes with minimum-weight perfect matching.  arXiv preprint arXiv:2105.13082, 2021.
  * [34] P. Jurcevic, Ali Javadi-Abhari, L. Bishop, I. Lauer, D. Bogorin, M. Brink, L. Capelluto, O. Günlük, Toshinari Itoko, Naoki Kanazawa, A. Kandala, G. Keefe, Kevin D Krsulich, W. Landers, E. Lewandowski, D. McClure, G. Nannicini, Adinath Narasgond, H. Nayfeh, E. Pritchett, M. Rothwell, S. Srinivasan, N. Sundaresan, Cindy Wang, K. X. Wei, C. J. Wood, J. Yau, E. Zhang, O. Dial, J. Chow, and J. Gambetta.  Demonstration of quantum volume 64 on a superconducting quantum computing system.  Quantum Science & Technology, 6, 2020.
  * [35] Gushu Li, Yufei Ding, and Yuan Xie.  Towards efficient superconducting quantum processor architecture design.  Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, 2020.
  * [36] B. Reichardt.  Fault-tolerant quantum error correction for steane’s seven-qubit color code with few or no extra qubits.  arXiv: Quantum Physics, 2018.
  * [37] S. Varsamopoulos, B. Criger, and K. Bertels.  Decoding small surface codes with feedforward neural networks.  arXiv: Quantum Physics, 2017.
  * [38] Stefan Krastanov and Liang Jiang.  Deep neural network probabilistic decoder for stabilizer codes.  Scientific Reports, 7, 2017.
  * [39] P. Baireuther, T. O’Brien, B. Tarasinski, and C. Beenakker.  Machine-learning-assisted correction of correlated qubit errors in a topological code.  arXiv: Quantum Physics, 2017.