# Optimal Synthesis of Stabilizer Codes via MaxSAT

Keyi Yin<EMAIL_ADDRESS>University of California, San Diego, CA, USA  Hezi
Zhang<EMAIL_ADDRESS>University of California, San Diego, CA, USA  Yunong Shi
<EMAIL_ADDRESS>Amazon Braket, New York, NY, USA  Travis Humble
<EMAIL_ADDRESS>Oak Ridge National Laboratory, Oak Ridge, TN, USA  Ang Li
<EMAIL_ADDRESS>Pacific Northwest National Laboratory, Richland, WA, USA
Yufei Ding<EMAIL_ADDRESS>University of California, San Diego, CA, USA

###### Abstract

Quantum Error Correction (QEC) codes are crucial for achieving fault-tolerant
quantum computing in the long term. However, efficiently implementing these
codes on hardware poses significant challenges, including hardware
connectivity matching, efficient circuit scheduling, and fault-tolerance
enforcement. In this study, we present an optimal synthesizer that stitches
generic stabilizer codes onto diverse hardware structures via MaxSAT. Our
evaluation demonstrates (1) the capability of our approach to be applied for
various codes and devices and (2) the consistently better efficiency than the
best prior heuristic approaches that only target specific QEC codes. By
bridging the gap between high-level QEC code design and low-level hardware
constraints, this work paves the way toward achieving long-term fault-tolerant
quantum computing goals. We will open-source our code and provide the GitHub
link in the final version.

##  I Introduction

In recent years, the field of quantum computing has witnessed a rapid scale-up
in hardware capabilities. For instance, IBM has achieved an impressive
milestone of 400+ qubits [1], with plans to surpass 1000+ qubits in 2023 [2].
To unleash the full potential of quantum computation, quantum error correction
(QEC) for fault tolerance has become the next frontier in the pursuit of
”quantum supremacy” [3, 4]. Notably, significant strides have been made in
recent QEC experiments, showcasing the implementation of logical operations on
a distance-2 surface code [5], the performance improvement by scaling a
surface code from distance 3 to 5 [6], and the realization of real-time QEC
beyond break-even [7].

Among the diverse range of QEC codes, stabilizer codes stand out as an
essential class encompassing a vast majority of known quantum codes [8, 9].
These codes possess distinct mathematical structures, such as the Abelian
group [10] property, which facilitate the construction of encoding, decoding,
and error-correction procedures [11, 12]. Various stabilizer codes, including
the repetition code [13], Steane code [14], and surface code [15, 16, 17],
have been developed to advance theoretical aspects, such as achieving higher
error thresholds [18, 19, 20]. However, early efforts in their design largely
overlooked the constraints imposed by the underlying hardware [21, 22],
especially the limited qubit connectivity. This oversight has led to a
substantial gap between theoretical design and practical realization,
significantly impacting the effectiveness and efficiency of these codes in
achieving large-scale, fault-tolerant quantum computing [23].

One recent effort by Anbang et al. [24] represents an initial step towards
bridging the code-architecture gap. Notably, they address the challenge of
mapping surface code [15, 16, 17], which is traditionally believed to require
square architectures, onto sparser quantum architectures, such as heavy
hexagons and heavy squares. The automatic framework is built on a clever
exploitation of the unique characteristic of the surface code. Specifically,
it takes advantage of the fact that all X- or Z-stabilizers in surface codes
connect to four data qubits, leading to a uniform 2-D stabilizer layout. Their
framework correspondingly starts by embedding the sparsely-connected coupling
graph into a virtual 2D grid. Subsequently, it performs a search on this grid
to identify ”rectangles” that satisfy the 4-degree stabilizer layout. However,
it should be noted that this approach is limited to stabilizer circuits
structured as ”rectangles” on the embedded grid, making it challenging to
generalize to other stabilizer codes lacking this feature. Moreover, due to
its heuristic nature, the method may not always guarantee to find the optimal
solution.

Our ambitious goal is to create a framework that can effectively handle a wide
range of stabilizer codes, going beyond the limitations imposed by specific
circuit structures [25] or architectures [26]. In our initial investigation,
this task may seem like a mission impossible, as different stabilizer codes
often present varying numbers and structures of stabilizers [27]. These
individual stabilizers also act on different data qubits and involve varying
numbers of them, lacking specific structure information to capitalize on.
Additionally, diverse fault-tolerant syndrome extraction methods [28, 29, 30]
contribute to the complexity of the code synthesis problem.

The good news is that our further investigation reveals that while finding
universal heuristics to leverage the intrinsic structure of diverse codes can
be challenging, constraints-based optimizations [31, 32] provide a systematic
and rigorous means to guide the synthesis process and explore the larger
solution space. By treating each stabilizer as a syndrome extraction circuit
that satisfies constraints for mapping data and ancilla qubits [33, 34], and
viewing the stabilizer code as the co-mapping and co-scheduling of these
individual stabilizers synergistically, we aim to devise a versatile and
powerful framework to tackle the code-architecture gap in quantum computing.
In addition to its versatility, the constraint-based approach offers the
potential for optimality in synthesizing stabilizer codes.

We further illuminate the primary challenges in bridging the code-architecture
gap, each of which will be addressed by formulating them as a set of
constraints. Connection Disparity: Densely interconnected stabilizer
measurement circuits clash with sparsely connected quantum hardware, hindering
direct execution on the hardware. Addressing this requires thoughtful mapping
of data and syndrome qubits, along with allocating additional ancilla qubits
to resolve the connection mismatch. Co-Scheduling Complexities: Co-scheduling
different stabilizer measurements presents a barrier to achieving the ideal
assumption of full parallelism when these measurements are scheduled
separately. This challenge arises from both the shared ancilla qubits,
resulting in _incompatible_ stabilizers that cannot be executed in parallel,
and the the shared data qubits, necessitating a proper arrangement of gate
orders within the circuit to ensure the measurement correctness. Fault-
Tolerant Execution: Achieving fault-tolerant execution of stabilizer
measurement circuits proves intricate due to error propagation from two-qubit
gates. While various studies [26, 35, 36] delve into the error-correction
scheme with the potential for fault-tolerance, they often come with the trade-
off of introducing additional constraints on the stabilizer circuits.

To this end, we propose CodeStitch, a novel constraint-based approach for
fault-tolerant stabilizer code synthesis. Our approach formulates and solves
the synthesis task as a two-stage optimization problem based on MaxSAT [32].
The first stage focuses on stabilizer mapping to address the connection
disparity challenge, while the second stage involves stabilizer operation
scheduling to resolve co-scheduling complexities. In the stabilizer mapping
stage, we tackle the issue of limited hardware connectivity by mapping each
data qubit to a physical qubit and each syndrome qubit to a connected block of
ancilla qubits adjacent to the data qubits. This is achieved through a SAT-
encoded breadth-first traversal (BFT) algorithm [37]. The goal is to minimize
the $CNOT$ gate number and maximize the compatibility between stabilizers,
reducing ancilla qubit overhead and enabling parallel scheduling in the next
stage. In the stabilizer scheduling stage, we optimize the parallelism of
stabilizer measurement circuits by scheduling each stabilizer as a five-phase
circuit and enforcing pipeline constraints to address conflicts between
stabilizers and ensure measurement correctness. We use an iterative query to
the SAT solver, gradually increasing the circuit depth limit in each iteration
until a solution is found. To meet the fault-tolerance requirement, we add
scheme-specific constraints in both stages. For generic stabilizer codes, we
adopt Shor’s scheme [28] as the default measurement scheme. Alternatively, if
fault-tolerance is guaranteed by an elaborate manual design of stabilizer
circuits [26, 35, 38], we can accommodate them by imposing their design-
specific constraints.

Overall, we make the following contributions:

  * •

We identify and formulate three critical challenges for implementing generic
stabilizer codes on the underlying hardware with diverse coupling structures,
including hardware constraints, efficient circuit scheduling, and fault-
tolerance enforcement.

  * •

We tackle these challenges by proposing a constraint-based approach, which
systematically formulates the synthesis problem of stabilizer codes as a two-
stage MaxSAT problem and efficiently explores the vast optimization space with
the state-of-the-art MaxSAT solver.

  * •

Our evaluation demonstrates the versatility of our framework across a range of
stabilizer codes and device architectures, as well as its optimality to
significantly enhance fidelity when compared to heuristic approaches.

##  II Background and Motivation

In this section, we provide an introduction to stabilizer codes and shed light
on the challenges encountered when synthesizing them on quantum hardware
through examples.

###  II-A Stabilizer Codes

Stabilizer codes are essential quantum codes [39] represented through the
stabilizer formalism [40]. An $[\\![n,k,d]\\!]$ stabilizer code stores $k$
logical qubits in $n$ data qubits, with $d$ denoting the minimum number of
physical qubits required to convert codewords. Stabilizer codes use $n-k$
stabilizers, each represented by a tensor product of Pauli operators $P$. The
weight of a stabilizer generator is defined as
$wt(s_{k})=\text{count}(P_{i}\neq I)$, which represents the number of qubits
it needs to operate on.

$\displaystyle Stabs$ $\displaystyle=\\{s_{1},s_{2},...,s_{n-k}\\}$
$\displaystyle s_{k}=P_{1}P_{2}\dots$ $\displaystyle
P_{n}\text{,~{}where~{}}P_{i}\in\\{I,X,Y,Z\\}$

A codeword is stabilized by all the stabilizers of the code, implying it is a
simultaneous eigenstate of all stabilizers with an eigenvalue of $+1$ [39]. By
checking this ”stabilizing” property, stabilizer codes enable the detection
and correction of errors in a quantum system. The set of all such legitimate
states forms the codespace. For the codespace to be non-trivial, all
stabilizers (also known as generators) of the codespace must commute with each
other, forming an Abelian group [40].

###  II-B Error Syndrome Extraction Circuits

The error syndrome extraction circuit is used to measure whether the input
quantum state is an eigenstate of a stabilizer with an eigenvalue of $+1$.
Fig. 1(b) depicts such a circuit for measuring the stabilizer
$s=X_{a}X_{b}X_{c}X_{d}$. The measurement outcome of the syndrome qubit
(_i.e., error syndrome_) reveals whether an error has occurred on data qubit,
assuming the original quantum state is a valid codeword.

Figure 1: Error syndrome extraction circuit for stabilizer $X_{abcd}$ with a
single syndrome qubit. (a) The stabilizer structure. (b) The syndrome
extraction circuit. A single fault $X_{s}$ after the second $CNOT$ gate could
result in the correlated 2-qubit error $X_{c}X_{d}$ on the data qubits, which
is possibly uncorrectable.

While this measurement scheme is effective in theory, it may fail to meet the
specific hardware constraints and account for detailed error propagation
toward fault-tolerant execution.

Connection Disparity. Using a single syndrome qubit for stabilizer
measurement, as shown in Fig. 1, requires the ancilla qubit to connect to all
data qubits the stabilizer operates on. This necessitates mapping it to a
physical qubit with at least $wt(s)$ neighboring qubits. However, real quantum
devices [2] lack such highly-connected qubits. For example, the latest IBM
quantum device [1] exhibits a heavy hexagonal structure with nodes having only
degrees of 2 and 3, posing challenges for direct circuit mapping due to
connectivity limitations.

Fault-Tolerant Execution. Moreover, the measurement circuit depicted in Fig. 1
can potentially raise fault-tolerant concerns. If an $X$ error occurs on the
syndrome qubit after the first two $CNOT$ gates, it can propagate onto two
data qubits $c$ and $d$. This correlated error, denoted as $X_{c}X_{d}$, may
share the same error syndrome as some single-qubit errors in certain low-
distance QEC codes. For example, in a stabilizer code with $d=3$, this two-
qubit error could surpass the error correction capability of the code.
Consequently, in the next round of syndrome measurements, a single-qubit error
might be misidentified instead of the original two-qubit error, resulting in a
logical qubit error.

An Example that Resolves Both Concerns. Fig. 2 depicts a fault-tolerant
syndrome extraction circuit for the stabilizer $s=X_{a}X_{b}X_{c}X_{d}$. It is
both fault-tolerant and requires only a block of syndrome qubits with degrees
2 and 3. We provide a simple example to illustrate the fault tolerance of this
scheme. If an $X$ error occurs on ancilla qubit $s_{3}$ just before the last
$CNOT$ gate in the Encoding phase, it will propagate to the correlated error
$X_{c}X_{d}$ on data qubits. However, this $X$ error will also cause the
multi-qubit error $X_{s_{1}}X_{s_{2}}Z_{s_{3}}$ after the Decoding phase,
resulting in both $Z$ measurements on $s_{1}$ and $s_{2}$ returning non-
trivial result $1$ during the Measurement phase. With this additional
information, we can diagnose the error $X_{c}X_{d}$. The method we employ here
for ensuring fault tolerance is also referred to as Shor’s scheme [28]. For
more details about the error decoding and correction, we recommend reference
[41].

Figure 2: Error syndrome extraction circuit for stabilizer $X_{abcd}$ with a
block of ancilla qubits under Shor’s fault-tolerant measurement scheme [28].
(a) The stabilizer structure, with ancilla qubits in red forming a block, and
yellow edges indicating controlled-$P_{i}$ gates (CX for $X_{abcd}$). (b) The
five-phase syndrome extraction circuit. The red $X$ and $Z$ letters indicate a
possible error propagation, with red $1$s representing the measurement return
a non-trivial result.

A Five-Stage Circuit Pipeline Abstraction. Indeed, we observe that any error
syndrome extraction circuit $Circuits[s_{k}]$ of a stabilizer $s_{k}$ can be
represented as a five-stage pipeline, Initialization, Encoding, Control,
Decoding, and Measurement:

$\displaystyle Circuits[s_{k}]$
$\displaystyle=Init[s_{k}]~{}\cup~{}Enc[s_{k}]~{}\cup~{}Ctrl[s_{k}]$
$\displaystyle~{}\cup~{}Dec[s_{k}]~{}\cup~{}Meas[s_{k}]$

In particular, the interaction between ancilla qubits and data qubits happens
in the Control phase through controlled-$P_{i}$ gates. We denote these gates
as $ctrl(P_{i},s_{i},q_{i})$, where ancilla qubit $s_{i}$ is the control
qubit, data qubit $q_{i}$ is the target qubit, and $P_{i}$ is the Pauli
operator of the stabilizer $s_{k}$ acting on $q_{i}$. Since $CY$ and $CZ$
gates can be transformed into $CX$ (i.e., $CNOT$) gates with single-qubit
gates, we use $CNOT$ gates to denote general controlled-$P_{i}$ gates in the
paper.

###  II-C Error Syndrome Extraction Scheduling

This section focuses on the key challenges of co-scheduling all stabilizer
measurements in a stabilizer code. The pipelined view of each individual error
syndrome extraction circuit provides a foundation for circuit scheduling.
However, co-scheduling multiple stabilizers can be significantly more complex.
We will now highlight two key challenges in this context.

Figure 3: Surface code stabilizers with S-shaped order of $CNOT$ gates. (a)
Structure of two adjacent $X$ and $Z$ stabilizer. (b) Circuit to measure the
operators $X_{a}X_{b}$ and $Z_{a}Z_{b}$ in the dashed box. The two identity
$I$ operators on syndrome qubit $Z$ are performed to ensure that the
measurement timing of two stabilizer matches. Figure 4: Synthesizing Steane
Code (a) by mapping the qubits onto a 5x5 square lattice (b) and scheduling
the syndrome extraction circuits with 5 phases (c). Data qubits are depicted
in blue and ancilla qubits are depicted in red, with the ancilla qubits of
each stabilizer in (b) forming an ancilla block. Syndrome extraction circuits
of $X_{abcd}$ and $Z_{bdef}$ are scheduled concurrently in (c), with the gate
order managed appropriately in the Control phase. The scheduling process can
be affected by different ways of preparing GHZ states on ancilla blocks, with
(d) showing two equivalent circuits of preparing GHZ states on the S-shaped
ancilla block.

Shared Ancilla Qubits: Error syndrome extraction circuit for stabilizer with
shared ancilla qubits may not be able to execute in parallel. For example,
since the qubit $s$ in Fig. 1 is occupied throughout all the five stages,
circuits for any other stabilizers would have to wait if they also need to
utilize this qubit. This significantly affect the latency of the QEC circuit
since most syndrome extraction circuits would require highly connected ancilla
qubits similar to $s$. To maximize the parallelism, we would prefer different
stabilizers to acquire non-overlapping qubits, for which case we say their
circuits are _compatible_.

Shared Data Qubits: Error syndrome extraction circuit for stabilizer with
common data qubits need to follow appropriate orders to ensure the correctness
of the syndrome extraction. Otherwise, the final measurements will just return
random results. For example, as demonstrated in Fig. 3, in the surface code
setup, the order of $CNOT$ gates is important. The X- and Z-type stabilizers
must adhere to a specific sequence: either a Z-shaped pattern
($C_{1}\rightarrow C_{3}\rightarrow C_{2}\rightarrow C_{4}$) or an S-shaped
pattern ($C_{1}\rightarrow C_{2}\rightarrow C_{3}\rightarrow C_{4}$) [35].
Deviating from this proper order, such as in a clock sequence
($C_{2}\rightarrow C_{1}\rightarrow C_{3}\rightarrow C_{4}$), will lead to the
measurement of operators $X_{a}X_{b}X_{z}$ and $Z_{x}Z_{a}Z_{b}$ instead of
the intended $X_{a}X_{b}$ and $Z_{a}Z_{b}$ [42].

##  III Overview

In this section, we present an example of applying CodeStitch to synthesize
the Steane Code onto a 2-D grid hardware, as shown in Fig. 4. The example
focuses on providing an overview of CodeStitch, especially inputs/outputs in
different stages. Detailed technical aspects are in Section IV.

###  III-A Overview of Stage 1: Stabilizer Mapping

Input1: Our first input is the stabilizer code to be synthesized. The
stabilizer code is encoded as a list of Pauli operator strings. For instance,
the $[\\![7,1,3]\\!]$ Steane code, whose code layout is depicted in Fig. 4(a),
can be encoded as follows:

$\displaystyle Stabs=\\{\ $ $\displaystyle X_{a}X_{b}X_{c}X_{d},$
$\displaystyle X_{b}X_{d}X_{e}X_{f},$ $\displaystyle X_{c}X_{d}X_{f}X_{g},$
$\displaystyle Z_{a}Z_{b}Z_{c}Z_{d},$ $\displaystyle Z_{b}Z_{d}Z_{e}Z_{f},$
$\displaystyle Z_{c}Z_{d}Z_{f}Z_{g}\ \\}$

For simplicity, we will use the notations $s_{1}$ to refer to the first
stabilizer $X_{a}X_{b}X_{c}X_{d}$ and $s_{i}$ to denote the $i$th stabilizer.

Input2: Our second input is the quantum hardware to be deployed. We adopt a
general device coupling graph, $Graph=(Phys,Edges)$, to encode the coupling
constraints on the quantum hardware. Here $Phys=\\{p_{1},p_{2},...\\}$ denotes
the set of physical qubits, and $Edges=\\{e_{1},e_{2},...\\}$ represents the
set of direct physical coupling between the physical qubits. Fig. 4(b)
illustrates a device with 25 physical qubits, forming a $5\times 5$ squared
lattice. The edges between qubits indicate whether we can perform two-qubit
operations between them. For example, we can perform a controlled-$Z$ gate
directly over $p_{1,1}$ and $p_{1,2}$, but not between $p_{1,1}$ and
$p_{2,2}$. We also use $Adj(p_{i})$ to represent all the physical qubits that
are adjacent to $p_{i}$.

Output: The output of Stage 1 comprises three parts, as shown in Fig. 4(b). 1
Data qubits mapping (in blue), $\Pi:Data\rightarrow Phys$, e.g.,
$\Pi(a)=p_{1,3}$ and $\Pi(b)=p_{3,2}$. 2 Ancilla block allocation (in red),
$Anc:Stabs\rightarrow P[Phys]$, where $P[Phys]$ stands for a collection of
physical qubits. We allow partial/exact overlapping between ancilla blocks of
different stabilizers, e.g.,
$Anc[s_{1}]=Anc[s_{4}]=\\{p_{2,2},p_{2,3},p_{2,4},p_{3,3}\\}$. 3 Coupling
relation between data qubit and ancilla qubit (yellow edges), $CP:Stab\times
Data\rightarrow Phys$, indicating which ancilla qubit of the stabilizer is
used to couple with the data qubit, e.g., $CP(s_{1},a)=p_{2,3}$ and
$CP(s_{2},e)=p_{4,1}$.

###  III-B Overview of Stage 2: Stabilizer Scheduling

Stage 2 exclusively takes inputs from the outputs derived from Stage 1. Its
outputs encompass 1) the error syndrome extraction circuits for all
stabilizers and 2) the corresponding time schedule of each gate within these
circuits. Fig. 4(c) provides an example output for the Steane Code, with only
the co-scheduling of $s_{1}$ and $s_{5}$ plotted out and the detailed gates
within the circuits omitted for simplicity. We next provide more details about
these two outputs.

Output 1: Syndrome extraction circuit for each stabilizer $s$. The five stages
of the circuit are treated separately. For $Init[s]$, $Ctrl[s]$, and
$Meas[s]$, circuits can be determined using the output from Stage 1. For
instance, in the Control phase of stabilizer $s_{1}=X_{a}X_{b}X_{c}X_{d}$, the
required gates between ancilla and data qubits can be deduced from the
coupling relation, i.e., $CNOT$ gates between all pairs of qubits connected by
yellow edge for $s_{1}$ in Fig. 4(b), such as that between data qubit $a$ and
ancilla qubit $p_{2,3}$. In contrast, for $Enc[s]$ and $Dec[s]$, circuits
exist design flexibility. As shown in Fig. 4(d), multiple circuit options are
equivalent for preparing the GHZ state on the S-shaped ancilla block during
the Encoding phase of $s_{5}$, each employing distinct sets of gates and
requiring different length of time. For further information, please refer to
Section 4.2.

Output 2: Time schedule of each gate. With the syndrome extraction circuits
for each stabilizer $s$ obtained in Output 1, this step further determines the
co-scheduling of all stabilizers. The time schedule can be represented as a
mapping from all gates in the circuits to time steps:
$Circuits\rightarrow\\{1,2,3,\dots\\}$. For any gate $g\in Circuits$, its time
coordinate is denoted as $t_{g}$. In Fig. 4(c), the time axis illustrates the
time slots assigned to each of the five phases of the syndrome extraction
circuits, such as time steps 2-5 for the Encoding phase. For further clarity,
Fig. 4(d) provides comprehensive details about the gates scheduled at
different time slots in the Encoding phase.

###  III-C Overview of Fault Tolerance Schemes

We embrace Shor’s scheme [28] as our default fault-tolerance approach due to
its broad applicability. As elaborated in section II, this scheme only
requires the straightforward and code-agnostic GHZ state
$|+\rangle_{Anc[s]}+|-\rangle_{Anc[s]}$ in the Encoding phase and the
transversal $CNOT$ gate in Control phase. These requirements can be introduced
as special fault-tolerant constraints in our synthesizer.

In addition to Shor’s scheme, we also accommodate different manual designs of
fault-tolerant error syndrome extraction circuits for some specific QEC codes,
such as the surface code [35] and the flag-bridged Steane Code [38]. These
designs possess certain mapping of qubits and order of operations, which can
be introduced as additional constraints in our synthesizer.

##  IV Constraint-Based Stabilizer Code Synthesis

In this section, we delve into the technical details of the two stages in
CodeStitch: stabilizer mapping and scheduling.

###  IV-A Stage 1: MaxSAT Encoding of Stabilizer Mapping

In this stage, we encode the mapping problem of data qubits and ancilla blocks
into a MaxSAT problem. We formulate the qubit position constraints as hard
constraints, and formulate the objectives of minimizing total ancilla block
size and incompatible stabilizer count as soft constraints, denoted as
$(Hard,Soft)$. The so Additionally, we incorporate extra hard constraints
based on the measurement scheme to fulfill the fault-tolerance requirement.

####  IV-A1 Variables

Boolean variables: We use the following Boolean variables, matching the three
outputs of stage 1 as described in section III:

1

$map(q,p)$: Indicates the mapping of data qubit $q$ to physical qubit $p$ in
$\Pi$. For example, in Fig. 4(b), the data qubit $a$ is mapped to $p_{1,3}$,
which is represented by $map(a,p_{1,3})=True$.

2

$anc(s,p)$: Denotes the allocation of ancilla qubits for stabilizer $s$. For
instance, in Fig. 4(b), the allocation $p_{2,4}\in Anc[s_{1}]$ is represented
by $anc(s_{1},p_{2,4})=True$.

3

$cp(s,q,p)$: Represents the coupling relation of stabilizer $s$ between data
qubit $q$ and physical qubit $p$. For example, in Fig. 4(b), both
$cp(s_{1},a,p_{2,3})$ and $cp(s_{5},b,p_{3,1})$ are assigned a value of
$True$, indicating the coupling between the data qubit that the stabilizer
acts on and its corresponding ancilla qubit.

Other Variables: We introduce additional variables to address performance
concerns for the solver. These variables represent the upper bound size of the
ancilla block for each stabilizer $s\in Stabs$, denoted as $L[s]$. In Fig. 4,
for example, we have $L[s_{1}]=\dots=L[s_{6}]=4$. Setting $L[s]$ to $|Phys|$
avoids a maximum size constraint, but a smaller bound improves the MaxSAT
solver’s efficiency.

To optimize resource usage and solver performance, we iteratively set the
upper bound size $L[s]$ for each stabilizer $s\in Stabs$. Initially, $L[s]$ is
set to the lower bound based on the measurement scheme: $wt(s)$ for Shor’s
scheme and $1$ for the partial Flag-Bridge scheme. If the MaxSAT solver
returns ”UNSATISFIABLE” or fails to find a solution within a limited time, we
increment each $L[s]$ by $1$ to explore a larger search space. This iterative
refinement finds suitable sizes for ancilla blocks that yield better results.

####  IV-A2 Hard Constraints

Hard A. Injective data qubit mapping. This set of constraints ensures that the
$map$ variables represent an injective function, meaning that each data qubit
is mapped to a unique physical qubit:

$\displaystyle\sum_{p\in Phys}map(q,p)=1\text{,~{}for~{}}q\in Data$
$\displaystyle\sum_{q\in Data}map(q,p)\leq 1\text{,~{}for~{}}p\in Phys$

These constraints can be encoded by the exactly-one (EO) and at-most-one (AMO)
encoding [43], which use $O(n)$ auxiliary variables consisting a ”ladder” to
propagate the information of $True$ value between all the $n$ variable in the
summation.

Hard B. No ancilla-data mapping collision. This set of constraints ensures
that a physical qubit $p\in Phys$ cannot serve as both a data qubit and an
ancilla qubit simultaneously:

$\displaystyle\neg map(q,p)\bigvee\neg anc(s,p)\text{,~{}for~{}}q,~{}s\in
Data\times Stabs$

Hard C. Maximum size for ancilla blocks. This set of constraints guarantees
that an ancilla block $Anc[s]$ is allocated at most $L[s]$ ancilla qubits. To
achieve this, we introduce auxiliary boolean variables $A(k,s,p)$, where
$k\in\\{1,...,L[s]\\}$. It is set to $True$ only when the $k$-th ancilla qubit
of $Anc[s]$ is mapped to physical qubit $p$:

$\displaystyle anc(s,p)\leftrightarrow\bigvee_{1\leq k\leq L[s]}A(k,s,p)$

Thus, the ”at-most-$N$” constraint can be encoded into $N$ at-most-one
constraints:

$\displaystyle\sum_{p\in Phys}A(k,s,p)\leq 1\text{,~{}for~{}}s\in
Stabs\text{~{}~{}and~{}}k\in\\{1,~{}...,~{}L[s]\\}$

Since ancilla qubits are not required to be mapped to unique physical qubits,
it’s possible for some of them to overlap on the device, resulting in an
ancilla block with a size smaller than $L[s]$.

Hard D. Connectivity of ancilla block. This set of constraints guarantees that
each mapped ancilla block forms a connected graph. Connectivity of induced
subgraph $Graph[Anc[s]]$, which consists of all qubits in $Anc[s]$ and
associated edges between them, ensures the preparation of the ancilla state on
the block.

To encode the connectivity constraint of $Anc[s]$ with Boolean variables
$anc(s,p)$, we employ the idea of breadth-first traversal (BFT) [37]. Given
that $|Anc[s]|\leq L[s]$, all the physical qubits in $Graph[Anc[s]]$ can be
visited within a maximum of $L[s]$ time steps. To represent the traversal of
$Graph[Anc[s]]$ starting from physical qubit $p$, we introduce auxiliary
variables $v_{s,p}(p_{i},t)$, where $p_{i}\in Phys$ and
$t\in\\{1,~{}\dots,~{}L[s]\\}$. The variable $v_{s,p}(p_{i},t)$ indicates
whether the physical qubit $p_{i}$ has been visited after $t$-th round. In the
initial round, we only visit the starting vertex $p$:

$\displaystyle v_{s,p}(p,1)\bigwedge_{p_{i}\neq p}\neg v_{s,p}(p_{i},1)$

In the $t$-th round of the traversal, a unvisited physical qubit $p_{i}\in
Anc[s]$ will be visited if and only if at least one of its adjacent qubits
$p_{j}\in Adj(p_{i})$ has been visited in the previous $t-1$ rounds:

$\displaystyle v_{s,p}(p_{i},t)$ $\displaystyle\rightarrow~{}anc(s,p_{i})$
$\displaystyle\wedge\left[v_{s,p}(p_{i},t-1)\bigvee_{p_{j}\in
Adj(p_{i})}v_{s,p}(p_{j},t-1)\right]$

Since the specific physical qubits that belong to $Anc[s]$ and can serve as
the starting point for the Breadth-First Search (BFS) are undecided, it
becomes necessary to enforce constraints for every $p\in Phys$, requiring
that:

$\displaystyle anc(s,p)\rightarrow\bigwedge_{p_{i}\in Phys}(\neg
anc(s,p_{i})\vee v_{s,p}(p_{i},L[s]))$

Hard E. Coupling between data qubits and ancilla block. This set of
constraints ensures that each data qubit for stabilizer $s$ is physically
connected directly to some ancilla qubits in the ancilla block $Anc[s]$.
Specifically, it enforces the following conditions:

1) Exactly one ancilla qubit $p$ is used to be coupled with data qubit $q$:

$\displaystyle\sum_{p\in Phys}cp(s,q,p)=1\text{,~{}for~{}}q\in Data[s]$

2) The coupling relation $CP(s,q)=p$ requires $q$ to be mapped to some qubits
$p_{i}$ adjacent to $p$:

$\displaystyle cp(s,q,p)\rightarrow\bigvee_{p_{i}\in
Adj(p)}map(q,p_{i})\bigwedge anc(s,p)$

Hard F. Fault tolerance constraints: transversal $CNOT$ gates. This set of
constraints ensures that the synthesized stabilizer code satisfies the
requirements of our default measurement protocol, Shor’s scheme [28], meaning
that all the $CNOT$ gates in the Control phase are transversal on the ancilla
block. In other words, in any stabilizer $s$, there is at most one $CNOT$ gate
$g_{i}\in Ctrl[s]$ on each ancilla qubit $p\in Anc[s]$:

$\displaystyle\sum_{q\in Data[s]}cp(s,q,p)\leq 1\text{,~{}for~{}}s\in
Stabs\text{~{}~{}and~{}}p\in Phys$

Nevertheless, in the case of other manually designed stabilizer codes,
constraints might be different. For example, the flag-bridge scheme [38]
requires that each ancilla block must contain at least one flag qubit, denoted
by the condition $|Anc[s]|\geq 2$.

If Hard F is excluded from the set of hard constraints, we refer to this
measurement scheme as the ”partial flag-bridge”. The term ”partial” is used
because this scheme can be viewed as a hybrid approach, combining elements
from both the bare ancilla and flag-bridge schemes.

####  IV-A3 Soft Constraints

We next introduce a set of soft constraints to optimize the performance of
synthesized stabilizer code. Each soft clause will be assigned a non-negative
weight to indicate its priority. With a MaxSAT solver, we can obtain a
solution that maximizes the combined weight of the satisfied soft clauses.

Soft P1. Minimizing the total ancilla block size. This set of constraints
ensures he measurement circuit remains small, as a larger circuit tends to be
more error-prone. Since the ancilla block for a stabilizer $s$ can be
represented as $\\{p\in Phys\mid anc(s,p)=True\\}$, minimizing the total
ancilla block size is equivalent to maximizing the number of Boolean variables
$anc(s,p)$ that are set to $False$. Thus, we add the following soft
constraints assigned with weight $P1$:

$\displaystyle\neg anc(s,p)\text{,~{}for~{}}s,p\in Stabs\times Phys$

Soft P2. Mitigating the stabilizer conflicts. This set of constraints ensures
that the mapped stabilizers can be efficiently executed in parallel.
Stabilizers $s$ and $s^{\prime}$ can be measured concurrently only if their
corresponding ancilla blocks do not overlap. Stabilizers that meet this
condition are considered compatible. Therefore, our objective is to maximize
the count of compatible ancilla block pairs. Thus, we introduce the following
soft constraints assigned with weight $P2$:

$\displaystyle\bigwedge_{p\in Phys}\neg anc(s,p)\vee\neg
anc(s^{\prime},p)\text{, for }s,s^{\prime}\in Stabs$

Figure 5: Different mappings for stabilizer $s$ and $s^{\prime}$ under
different measurement schemes (partial flag-bridge $vs.$ fault-tolerant Shor’s
scheme) and objectives (Soft P1: minimizing the total ancilla block size $vs.$
Soft P2: mitigating the stabilizer conflicts).

In Fig. 5, we present the impact of diverse measurement schemes and
optimization objectives on the resulting mappings. We illustrate four
different mappings of the code $Stabs={X_{1}X_{2}X_{3},Z_{2}Z_{3}}$ to a heavy
square architecture. In the second row, for instance, Soft P2 is chosen as the
objective with first priority, indicating that the weight $P_{2}$ is
significantly greater than $P_{1}$. As shown in the table, varying the
priority leads to different data qubit mappings and ancilla block allocations.
As discussed in Section V, we generally prioritize the total size of ancilla
blocks (P1) over the number of incompatible stabilizers (P2), as the former
has a more significant impact on the overall error correction performance.

###  IV-B Stage 2: SAT Encoding of Stabilizer Scheduling

In this stage, we formulate the scheduling problem of syndrome extraction
circuits into a SAT problem. We identify all operations within the syndrome
extraction circuits from the output of stage 1, and introduce constraints by
analyzing the dependence of operations from the perspective of relations
within or between the five phases of stabilizer.

####  IV-B1 Error Syndrome Extraction Circuits

Before addressing scheduling, it is necessary to determine all the operations,
which means to establish the set $Circuits$ from the results of the stabilizer
mapping. As outlined in Section III, when considering a stabilizer $s$, only
the operations in Initialization, Control, Measurement phases have been
identified:

$\displaystyle Init[s]$ $\displaystyle=\\{init(p)\mid p\in Anc[s]\\}$
$\displaystyle Ctrl[s]$ $\displaystyle=\\{ctrl(P_{q},CP(s,q),\Pi(q))\mid
P_{q}\neq\text{I}\in s\\}$ $\displaystyle Meas[s]$ $\displaystyle=\\{Mz(p)\mid
p\in Anc[s]\\}$

For the gates in Encoding and Decoding phases, if the H gate is treated as an
$CNOT$ with both control and target on itself, there is exactly one $CNOT$
targeted at each ancilla qubit. So we can represent $Enc[s]$ and $Dec[s]$ as:

$\displaystyle Enc[s]$ $\displaystyle=\\{CX_{e}(p)\mid p\in Anc[s]\\}$
$\displaystyle Dec[s]$ $\displaystyle=\\{CX_{d}(p)\mid p\in Anc[s]\\}$

where $g=\text{CX}_{e(d)}(p)$ represent a $CNOT$ gate with $p$ as a target
qubit in the Encoding (Decoding) phase, the control qubit $g$.ctrl need to be
determined in Stage 2.

####  IV-B2 Variables

Boolean variables: We use the following Boolean variables, matching the two
outputs of stage 2 as described in Section III:

1

$enc(s,p,p^{\prime})$ and $dec(s,p,p^{\prime})$: Indicates the encoding and
decoding circuits in $Enc[s]$ and $Dec[s]$. For example, consider Fig. 4(d),
in the left circuit design of $Enc[s_{5}]$, a $CNOT$ gate is applied from
$q_{1}$ to $q_{2}$, represented by $enc(s_{5},q_{1},q_{2})=True$. This
indicates that $\text{CX}_{e}(q_{2})\text{.ctrl}=q_{1}$.

2

$time(g,t)$: Denotes the time assignment of operations $g$ in the entire
$Circuits$. For instance, in Fig. 4(d), in the right circuit design of
$Enc[s_{5}]$, a $CNOT$ gate $g=CX_{e}(q_{3})$ is executed at time step 2,
which is represented by $time(g,2)=True$.

Other variables: We introduce additional variable $T$ to represent the upper
limit of time steps, with $t$ ranging in $\\{1,2,...,T\\}$. To find a depth-
optimal solution, the scheduler engages in an iterative process that queries
the SAT solver repeatedly to determine if it is possible to schedule the
syndromes extraction circuit within an overall circuit depth less than $T$. If
the result is ”UNSATISFIABLE”, $T$ will be augmented by multiplied with a
factor $\epsilon>1$.

####  IV-B3 Hard Constraints

In this sections, we will present a comprehensive outline of our constraints
from four perspectives: time assignment constraints, within-phase constraints,
between-phase constraints and fault-tolerant constraints.

1) Time Assignment Constraints:

Hard A. All operations are executed. Since each operation can only be mapped
to one time slot, indicating that exactly one element in the set
$\\{time(g,t)\ |\ t\in\\{1,...,T\\}\\}$ will be assigned the $True$ value in
the solution:

$\displaystyle\sum_{t}time(g,t)=1\text{, for }g\in Circuits$

Hard B. No operation collision. To prevent collision of operations, we enforce
that if two operations $g$ and $g^{\prime}$ act on the same physical qubit,
they cannot be executed at the same time. In other words, for any physical
qubit $p$, at most one operation acting on $p$ can be executed at time $t$:

$\displaystyle\sum_{g\in Act[p]}time(g,t)\leq 1\text{, for }t\in\\{1,...,T\\}$

where $Act[p]$ denotes all the operations that act on $p$. If the operation is
not determined but has the potential to act on $p$, i.e.
$g=\text{CX}_{e}(p^{\prime})$ when $p\in Anc[s]$, $time(g,t)$ will be replaced
by $time(g,t)\wedge enc(s,p,p^{\prime})$.

2) Within-Phase Constraints:

Hard C. Valid $Enc[s]$ and $Dec[s]$ circuits. This set of constraints ensures
that the circuits in the Encoding phase and Decoding phase can function as the
encoding and decoding of a GHZ state. In the Encoding phase, an ancilla qubit
$p$ can only be prepared after an H gate or a $CNOT$ gate controlled by
another prepared ancilla qubit targeting $p$. If the H gate is treated as
visiting the root node and $CNOT(p_{i},p_{j})$ is treated as visiting $p_{j}$
through the edge $(p_{i},p_{j})$, $Enc[s]$ can be considered as a transversal
starting at the root of the tree on $Anc[s]$ In other words, whether $Enc[s]$
and $Dec[s]$ are valid circuits is equivalent to $Enc[s]$ and the mirror of
$Dec[s]$ forming a tree transversal. The following parts outline the
constraints for $Enc[s]$, while a similar formulation can be applied to
$Dec[s]$.

(1) The transversal tree has exactly one root, which means only the root
ancilla qubit have $\text{CX}_{e}(root)=\text{H}$:

$\displaystyle\sum_{p\in Anc[s]}enc(s,p,p)=1$

(2) Each node within the transversal is visited exactly once, ensuring that
every ancilla qubit $p\in Anc[s]$ is subjected to exactly one $CNOT$ gate
targeting it:

$\displaystyle\sum_{p_{i}\in Anc[s]}enc(s,p_{i},p)=1$

(3) If $g_{j}=CX_{e}[p_{j}]=CNOT(p_{i},p_{j})$, it must be executed after
$p_{i}$ has been prepared. In other words, $g_{j}$ must be executed after
$g_{i}=CX_{e}[p_{i}]$:

$\displaystyle
enc(s,p_{i},p_{j})\rightarrow\left(t_{g_{i}}<t_{g_{j}}\right)\text{, for
}p_{i}\neq p_{j}\in Anc[s]$

Although the clause $t_{g_{i}}<t_{g_{j}}$ can be easily encoded by pairwise
encoding when the upper bound $T$ is given, we implement a ladder structure
akin to that of AMO and EO encoding, which minimizes the total count of
clauses.

Hard D. Correct order of $Ctrl[s]$ circuits. As discussed in Section II, the
order of anti-commutable controlled-$P_{i}$ gates in the Control phase affects
the measurement property. In fact, the order is correct if and only if the
count of anti-commutable gate pairs $(c,c^{\prime})$ satisfying
$t_{c}<t_{c^{\prime}}$ is an even number. This is due to the fact that two
anti-commutable controlled-$P_{i}$ gates together are commutable, allowing us
to switch their order. The even number means that the order is equivalent to
the trivial sequential order, which is always a correct order since it means
that stabilizer $s$ finishes before stabilizer $s^{\prime}$ begins. As a
result, we enforce the constraint:

$\displaystyle\bigoplus_{Anti(c,c^{\prime})}(t_{c}<t_{c}^{\prime})=0\text{,
for }c\in Ctrl[s]\text{~{}~{}and~{}}c^{\prime}\in Ctrl[s^{\prime}]$

where $\bigoplus$ means the mod 2 addition and $Anti(c,c^{\prime})$ means $c$
and $c^{\prime}$ are anti-commutable. The mod 2 addition can also be encoded
effectively by using the a ladder structure similar to those in AMO and EO
encoding.

3) Between-Phase Constraints:

Hard E. Operation pipelining. For the five phases in a stabilizer, they must
be executed in a strict sequential order, which means that operations in the
succeeding phases must wait for the operations in the preceding phases to
finish. Consequently, if $g\in Phase_{i}[s]$ and $g^{\prime}\in
Phase_{i+1}[s]$ act on the same qubit, we enforce the constraints
$t_{g}<t_{g^{\prime}}$.

Hard F. Incompatible stabilizers. When two stabilizer circuits, $s$ and
$s^{\prime}$, have shared ancilla qubits, their ancilla states cannot exist
simultaneously. This constrain can be realized by requiring $Init[s]$ after
$Meas[s^{\prime}]$, $Init[s^{\prime}]$ after $Meas[s]$:

$\displaystyle\left[\bigwedge\limits_{p\in
Share}(t_{Mz^{\prime}[p]}<t_{Init[p]})\right]\bigvee\left[\bigwedge\limits_{p\in
Share}(t_{Mz[p]}<t_{Init^{\prime}[p]})\right]$

where $Share=Anc[s]\cap Anc[s^{\prime}]$ represent all physical qubit that
shared by two stabilizer’s ancilla block.

4) Fault Tolerance Constraints:

Hard H. Designed order of $Ctrl[s]$ circuits. This set of constraints is
utilized to accommodate existing manually designed stabilizer code. Some
manually designed code may have special execution order for the data-ancilla
$CNOT$ gates in the Control phase. For instance, [44] proposed a fault
tolerant syndrome extraction approach for $[\\![2^{r}-1,2^{r}-1-2r,3]\\!]$
Hamming code, which have a permutation to reorder the $CX$ or $CZ$ gates in
each stabilizer to make possible errors have distinct syndromes. Similarly,
[35] improved stabilizer measurement circuits of surface code, where the
X-type and Z-type stabilizer follows different measurement order. Based on
these designed order of the $CNOT$ gates in the $Ctrl[s]$, we can create a
directed graph to show the dependence between $CNOT$ gates, indicating which
gates should be executed first. So for any direct edge $(g,g^{\prime})$ in the
graph, we enforce the constraint $t_{g}<t_{g^{\prime}}$.

##  V IMPLEMENTATION AND EVALUATION

###  V-A Experimental Setup

Evaluation setting: We use the state-of-the-art MAXSAT solver, NuWLS-c [45]
and SAT solver, PySAT [46] for the synthesis problem, both with a time limit
of $7,200$ seconds for solving. The increment factor $\epsilon$ for $T$ is
designated as 1.3. The weight assigned to the Soft P1 clauses is determined as
the total count of all Soft P2 clauses with a weight of 1. For error threshold
and logical error analysis, we utilize stim [47], a fast stabilizer circuit
simulator, and PyMatching [48], a decoder of Minimum Weight Perfect Matching
(MWPM) algorithm, and general error model used in previous study [42, 24].

Hardware architectures: We use different device architectures to execute the
stabilizer codes, showed in Fig. 6. To represent the connectivity limitations,
we use the average degree denoted as $Density(G)=2|Edge|/|Phys|$. The selected
architectures are sourced from latest quantum machines, such as Google’s
Sycamore [4], IBM’s Osprey and IBM Q Tokyo [1], with densities ranging from
$2.4$ to $6$. We also choose alternative architectures with matching densities
to investigate the impact of structural differences.

Figure 6: Overview of device architectures.

Stabilizer codes: In our experiments, we synthesize a diverse set of
stabilizer codes with distinct features, including classical codes such as the
$[\\![9,1,3]\\!]$ surface code and the $[\\![7,1,3]\\!]$ Steane code, color
codes like the $[\\![16,4,3]\\!]$ 2D color code and the $[\\![8,3,2]\\!]$ 3D
color code, as well as more generic non-CSS codes such as the five-qubit
$[\\![5,1,3]\\!]$ code. We select these codes for evaluation based on several
reasons: 1) Many stabilizer codes can be seen as extensions or combinations of
these foundational codes. For example, larger distance surface codes can be
constructed from the 3-distance surface code [49], and the $[\\![22,4,3]\\!]$
and $[\\![12,2,3]\\!]$ color codes can be obtained by merging Steane codes
[26]; 2) Code layout difference is considered by the synthesis of both 2D and
3D color codes onto the devices with 2D planar coupling graphs; 3)
Synthesizing more generic codes is demonstrated through the case of the non-
CSS five-qubit code, which is also the most dense code. The measurement scheme
is also taken into account. We use the ”Partial Flag-Bridge” scheme for the
$[\\![16,4,3]\\!]$ 2D color code and the $[\\![9,1,3]\\!]$ surface code since
they have special manual design where syndromes can be extracted fault-
tolerantly without flag qubits. For the rest of the codes, we use Shor’s
scheme.

To quantify the level of interconnectivity for each stabilizer code, we define
the density of a stabilizer code, denoted as $Density(C)$, as follows:

$\displaystyle Density(C)=\frac{\sum_{s\in
Stabs}wt(s)}{\left|Stabs\right|+\left|Data\right|}$

TABLE I: Results of CodeStitch and the ”ideal” baseline for various stabilizer
codes across different device architectures.

Code | Density |  Metrics Arch | Ideal | Square | Hexagon | Octagon | H-Square | H-Hexagon | Tokyo
---|---|---|---|---|---|---|---|---|---
$[\\![7,1,3]\\!]$ Steane Code | 3.69 | # $CNOT$ gate | 60 | 60 | 64 | 68 | 68 | 96 | 60
Circuit depth | 9 | 17 | 24 | 27 | 30* | 30 | 17
# physical qubit | 31 | 19 | 20 | 19 | 19 | 25 | 19
$[\\![16,4,3]\\!]$ 2D Color Code | 4.29 | # $CNOT$ gate | 60 | 80 | 120 | 152 | 132 |  240* | 76
Circuit depth | 10 | 17 | 18 | 24 | 26 | 30 | 19
# physical qubit | 28 | 27 | 37 | 44 | 37 |  61* | 26
$[\\![8,3,2]\\!]$ 3D Color Code | 3.69 | # $CNOT$ gate | 62 | 62 | 66 | 66 |  76* | 100 |  62*
Circuit depth | 11 | 20 | 31 | 31 | 30 | 33 | 19
# physical qubit | 32 | 26 | 16 | 16 |  24* | 21 |  28*
$[\\![5,1,3]\\!]$ Five-Qubit Code | 3.56 | # $CNOT$ gate | 40 | 40 | 44 | 44 | 50 | 60 | 40
Circuit depth | 9 | 24 | 30 | 30 |  33* | 32 | 16
# physical qubit | 31 | 15 | 10 | 10 | 11 | 12 | 18
$[\\![9,1,3]\\!]$ Surface Code | 2.82 | # $CNOT$ gate | 24 | 24 | 38 | 56 | 48 | 84 | 24
Circuit depth | 8 | 8 | 19 | 21 | 20 | 16 | 8
# physical qubit | 17 | 17 | 19 | 24 | 25 | 37 | 17

Metrics: In this work, we consider three key metrics. First, we evaluate the
$CNOT$ gate count of the synthesized QEC codes to demonstrate the performance
of the generated code. The high sensitivity to two-qubit gate errors in the
stabilizer code makes the count of $CNOT$ gates in the entire circuits a
crucial factor that significantly affects the fidelity of syndrome extraction.
Second, We assess the Circuit Depth of entire error syndrome extraction
circuit, which is the maximum time coordinates of all operations. Due to the
limitation of current quantum computing technology, physical qubits can only
function well up to a short ‘lifetime’. Thus, minimizing depth becomes crucial
to ensure efficiency. A larger time-step count would introduce more
decoherence errors that accumulate, eventually surpassing the fault tolerance
threshold of the error correction procedure. Finally, we examine Physical
Qubit Count to illustrate the resource overhead of the synthesized surface
codes. Since real quantum devices only provide a finite number of physical
qubits, for more logical qubits to be allocated, an efficient synthesis should
utilize fewer qubits.

###  V-B Synthesis of Various Stabilizer Codes

We begin by employing CodeStitch to synthesize a wide array of stabilizer
codes and explore various architectures. The results are presented in Table I.
The ”Ideal” column is used as a baseline, which represents a fully-connected
architecture. By comparing with the ideal situation, we discuss the influence
of architecture and stabilizer code on the synthesized result. The ”$*$”
symbol following the number indicates that it represents a satisfactory (but
not optimal) solution returned by the solver within the limited time allotted
for computation.

The influence of architectures: (1) In general, high-density architectures are
more effective for stabilizer code synthesis compared to low-density
architectures. When comparing hexagon architectures to square architectures,
the former exhibits an average increase of 26.3% in the number of 2-qubit
gates and an average increase of 47.9% in the circuit depth. (2) Density of
the architecture is not the sole factor affecting synthesis. For example, in
the synthesis of the $[\\![16,4,3]\\!]$ code, transitioning from a hexagon
architecture to an octagon architecture results in a significant increase in
the number of 2-qubit gates, circuit depth, and the count of physical qubits
cost. Despite both architectures having the same density of 3, the matching
degree between the native stabilizer structure and the target architecture
proves to be the key factor that impacts code synthesis. (3) Physical qubit
requirements can sometimes be lower on sparse architectures compared to dense
architectures. For example, with the $[\\![5,1,3]\\!]$ code, the sparse Tokyo
architecture requires 18 qubits, while the ideal architecture needs 31 qubits.
This is because our solver prioritizes optimizing the number of $CNOT$ gates
during the synthesis process. Consequently, on a sparse architecture, it
encourages extensive sharing between adjacent ancilla blocks, leading to a
decrease in overall qubit usage. Yet, sharing reduces parallelism among the
blocks, resulting in a higher circuit depth and diminishing overall error
protection effectiveness.

The influence of stabilizer code: (1) In general, high-density code needs
high-density architecture. For instance, $[\\![9,1,3]\\!]$ surface code reach
the ideal situation on Square while there is still optimization space for the
$[\\![16,4,3]\\!]$ color code on Square. (2) Stabilizer codes are influenced
to varying degrees by architecture density, and there is an upper bound on
architecture density that can substantially improve the performance and cost
of stabilizer code synthesis. For instance, when comparing the
$[\\![7,1,3]\\!]$ Steane code synthesized on Square and Tokyo architectures,
both demonstrate similar performance and cost, closely approaching the ideal
situation. (3) It is not just the stabilizer code but also the specific fault-
tolerance scheme used that can impact hardware requirements. For instance,
when employing Shor’s scheme-based synthesis, it guarantees transversal data-
ancilla interaction, resulting in lower degree requirements for ancilla qubits
and allowing near-optimal deployment on low-density architectures.

###  V-C Compared to Heuristic Approach on Surface Code

We compared our Stab-Stitch approach with Surf-Stitch [24], a heuristic method
proposed just for synthesizing surface codes. Fig. 7 gives error thresholds,
which are calculated based on the synthesized surface codes at different
distances, while Table II provides comprehensive details for the synthesized
surface codes of distance 3.

Figure 7: Error threshold comparison of CodeStitch and Surf-Stitch on various
architectures (A higher threshold implies a stronger error protection
capability of the synthesized QEC code). TABLE II: Detailed information about
the synthesized surface codes.

Arch Metrics |  # $CNOT$ gate |  Circuit depth |  # physical qubit
---|---|---|---
Square | CodeStitch | 24 | 8 | 17
Surf-Stitch | 24 | 8 | 17
Hexagon | CodeStitch | 38 | 19 | 19
Surf-Stitch | 60 | 26 | 21
Octagon | CodeStitch | 56 | 21 | 24
Surf-Stitch | 80 | 28 | 27
Heavy Square | CodeStitch | 48 | 20 | 25
Surf-Stitch | 48 | 24 | 25
Heavy Hexagon | CodeStitch | 84 | 16 | 37
Surf-Stitch | 88 | 40 | 31

Overall, our CodeStitch in Fig. 7 demonstrates consistently better error
correction capabilities in all settings. In particular, we highlight the
following four results.

(1) The primary metric influencing the error threshold is the count of $CNOT$
gates. The substantial improvement in the threshold, observed in the Hexagon
and Octagon architectures in Fig. 7, can be attributed to an approximate 30%
reduction in the utilization of $CNOT$ gates.

(2) When two synthesized circuits have an equivalent or nearly similar count
of $CNOT$ gates, circuit depth can also profoundly affect the error threshold.
For instance, consider the comparison between CodeStitch and Surf-Stitch on
the Heavy Square architecture, both employing the same surface code mappings.
However, due to a more concurrent scheduling strategy, CodeStitch achieves a
remarkable 0.07% increase in the error threshold by reducing 16.7% of circuit
depth.

(3) An unapparent element influencing the error threshold, not presented in
Table II, is the sequence in which measurements are conducted for $CNOT$
gates. For instance, in comparison to Surf-Stitch on Square architecture, our
synthesized code exhibits a slightly higher threshold, despite both utilizing
the same stabilizer mapping. This difference can be attributed to our
incorporation of S2.Hard H, inspired by [35], to employ distinct measurement
orders for X- and Z-type stabilizers. In contrast, Surf-Stitch only utilizes a
consistent S-shaped order for both categories of stabilizers.

(4) While CodeStitch may require more qubits than Surf-Stitch in cases like
Heavy Hexagon for parallel stabilizer mapping, this doesn’t necessarily
enlarge the total resource cost. Given the exponential impact of the error
threshold on the logical error rate, it is worthwhile to trade increased qubit
usage for reduced circuit depth in order to achieve a lower final cost of
physical qubits while reaching the target logical error rate.

###  V-D More Error Threshold Analysis

This study provides a breakdown analysis of how the error threshold shifts
across two vital error types: two-qubit $CNOT$ gate errors and device idle
errors. The simulation focuses on surface codes on 2-D grid hardware, but the
conclusion can be readily extrapolated to broader contexts. This analysis
provides additional support for the rationale behind prioritizing the
reduction of # $CNOT$ gates (linked to accumulated $CNOT$ errors) over circuit
depth (linked to accumulated idle errors) when optimizing QEC code synthesis.

The results are shown in Figure 8. The figure highlights the error threshold,
which is the convergence point of curves representing surface codes of
different distances. When analyzing the two-qubit gate error, the idle error
is set to 0, and vice versa. As shown, pure $CNOT$ gate error exhibits a per-
step threshold of 1.3%, while pure idle error showcases that of 3.1%. The much
lower threshold for $CNOT$ errors substantiates both the decreased tolerance
for this type of error and its amplified impact on the ultimate logical error
rate. This underscores the significance of prioritizing the objective of
reducing the overall $CNOT$ gate count within the circuits.

Figure 8: Error Threshold Breakdown Analysis.

###  V-E Scalability Discussion

Our empirical evaluation confirms the effectiveness of CodeStitch across a
diverse set of generic stabilizer codes. Our CodeStitch successfully finds
optimal solutions for many of these QEC codes within the time limit and
provides viable alternatives for others. We also observe that synthesis time
is not solely determined by the scale of the code; the degree of mismatch
between the code and architecture also significantly impacts it. For instance,
synthesizing the $[\\![9,1,3]\\!]$surface code on a 2D lattice takes 2-3
minutes, while the $[\\![8,3,2]\\!]$ code requires hours. The discrepancy
arises because the mismatch introduces a substantial synthesis space to
explore, making it challenging to find an optimal solution.

Looking ahead, we acknowledge the consideration surrounding the scalability of
our framework, given the inherent challenges posed by the solver’s
scalability. Nonetheless, we maintain optimism due to the potential of
integrating these modestly-sized, generic codes toward a hierarchical QEC code
synthesize approach. As such, we anticipate that upcoming innovations,
especially the integration of heuristic slicing techniques, will significantly
enhance CodeStitch’s capabilities, enabling its seamless application to more
extensive scenarios.

##  VI Related Work

Manually designed QEC code implementation: Prior studies have proposed
intricate fault-tolerant designs for specific codes, such as color code [26],
surface code [35] or subsystem code [50]. However, these designs overlook
connectivity constraints and make assumptions about the device’s ability to
accommodate such designs. In [38], a flexible fault-tolerant circuit design
was introduced, theoretically capable of accommodating diverse hardware
structures. However, its focus remains at the individual circuit level and
cannot be applied to solve the code-architecture gap, where interactions among
different stabilizer circuits significantly complicate the design space. To
bridge the code-architecture gap, specific QEC codes are still being manually
designed [51]. For instance, in [25], stitched surface codes were introduced
to address the requirements of heavy architecture devices.

Automatic Heuristic-based Approaches: Automating QEC code synthesis is still a
new area with only some preliminary study. Recent study [24] employs heuristic
methods to stitch surface codes onto various hardware structures. The
automatically synthesized QEC codes from their framework demonstrate
comparable or superior error correction capablity to prior manually designed
QEC codes [25]. However, these heuristic-based approaches are specialized for
surface codes, rendering lacking the extensibility to generic QEC codes.

##  VII Conclusion

In this paper, we conduct a comprehensive analysis and in-depth discussion of
the challenges for stitching generic stabilizer codes to diverse underlying
hardware. We formulate the fault-tolerant stabilizer code synthesis as a
MaxSAT problem and propose an optimal approach that solves the stabilizer
mapping and scheduling tasks in two stages. By exploring a vast design and
optimization space efficiently with the state-of-the-art MaxSAT solver, our
framework demonstrates remarkable versatility across a range of stabilizer
codes and device architectures, and reaches a consistently better efficiency
than the circuits designed by code-specific heuristic approach.

## References

  * [1] Jerry Chow, Oliver Dial, and Jay Gambetta.  Ibm quantum breaks the 100-qubit processor barrier.  IBM Research Blog, 2, 2021.
  * [2] Jay Gambetta.  Ibm’s roadmap for scaling quantum technology.  IBM Research Blog (September 2020), 2020.
  * [3] Exponential suppression of bit or phase errors with cyclic error correction.  Nature, 595(7867):383–387, 2021.
  * [4] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, 2019.
  * [5] JF Marques, BM Varbanov, MS Moreira, Hany Ali, Nandini Muthusubramanian, Christos Zachariadis, Francesco Battistel, Marc Beekman, Nadia Haider, Wouter Vlothuizen, et al.  Logical-qubit operations in an error-detecting surface code.  Nature Physics, 18(1):80–86, 2022.
  * [6] Suppressing quantum errors by scaling a surface code logical qubit.  Nature, 614(7949):676–681, 2023.
  * [7] VV Sivak, Alec Eickbusch, Baptiste Royer, Shraddha Singh, Ioannis Tsioutsios, Suhas Ganjam, Alessandro Miano, BL Brock, AZ Ding, Luigi Frunzio, et al.  Real-time quantum error correction beyond break-even.  Nature, 616(7955):50–55, 2023.
  * [8] Michael A Nielsen and Isaac L Chuang.  Quantum computation and quantum information.  Cambridge university press, 2010.
  * [9] Ivan B Djordjevic.  Quantum information processing, quantum computing, and quantum error correction: an engineering approach.  Academic Press, 2021.
  * [10] László Fuchs, JP Kahane, AP Robertson, and S Ulam.  Abelian groups, volume 960.  Springer, 1960.
  * [11] Jean-Pierre Françoise, Gregory L Naber, and Sheung Tsun Tsou.  Encyclopedia of mathematical physics, volume 2.  Elsevier Amsterdam, 2006.
  * [12] A Robert Calderbank, Eric M Rains, Peter M Shor, and Neil JA Sloane.  Quantum error correction via codes over gf (4).  IEEE Transactions on Information Theory, 44(4):1369–1387, 1998\.
  * [13] Asher Peres.  Reversible logic and quantum computers.  Physical review A, 32(6):3266, 1985.
  * [14] 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.
  * [15] A Yu Kitaev.  Quantum computations: algorithms and error correction.  Russian Mathematical Surveys, 52(6):1191, 1997.
  * [16] A Yu Kitaev.  Quantum error correction with imperfect gates.  In Quantum communication, computing, and measurement, pages 181–188. Springer, 1997.
  * [17] A Yu Kitaev.  Fault-tolerant quantum computation by anyons.  Annals of physics, 303(1):2–30, 2003.
  * [18] David K Tuckett, Stephen D Bartlett, and Steven T Flammia.  Ultrahigh error threshold for surface codes with biased noise.  Physical review letters, 120(5):050505, 2018.
  * [19] Helmut G Katzgraber, Héctor Bombín, and Martin A Martin-Delgado.  Error threshold for color codes and random three-body ising models.  Physical review letters, 103(9):090501, 2009.
  * [20] Daniel Crow, Robert Joynt, and Mark Saffman.  Improved error thresholds for measurement-free error correction.  Physical review letters, 117(13):130503, 2016.
  * [21] 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.  In APS March Meeting Abstracts, volume 2021, pages F30–007, 2021\.
  * [22] 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.
  * [23] Gushu Li, Yufei Ding, and Yuan Xie.  Towards efficient superconducting quantum processor architecture design.  In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1031–1045, 2020.
  * [24] Anbang Wu, Gushu Li, Hezi Zhang, Gian Giacomo Guerreschi, Yufei Ding, and Yuan Xie.  A synthesis framework for stitching surface code with superconducting quantum devices.  In Proceedings of the 49th Annual International Symposium on Computer Architecture, ISCA ’22, page 337–350, New York, NY, USA, 2022. Association for Computing Machinery.
  * [25] Christopher Chamberland, Guanyu Zhu, Theodore J Yoder, Jared B Hertzberg, and Andrew W Cross.  Topological and subsystem codes on low-degree graphs with flag qubits.  Physical Review X, 10(1):011022, 2020.
  * [26] Ben W Reichardt.  Fault-tolerant quantum error correction for steane’s seven-qubit color code with few or no extra qubits.  Quantum Science and Technology, 6(1):015007, nov 2020.
  * [27] Kristina R Colladay and Erich J Mueller.  Rewiring stabilizer codes.  New Journal of Physics, 20(8):083030, 2018.
  * [28] Peter W Shor.  Fault-tolerant quantum computation.  In Proceedings of 37th conference on foundations of computer science, pages 56–65. IEEE, 1996.
  * [29] Andrew M Steane.  Active stabilization, quantum computation, and quantum state synthesis.  Physical Review Letters, 78(11):2252, 1997.
  * [30] Emanuel Knill.  Quantum computing with realistically noisy devices.  Nature, 434(7029):39–44, 2005.
  * [31] Leonardo De Moura and Nikolaj Bjørner.  Z3: An efficient smt solver.  In International conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 337–340. Springer, 2008.
  * [32] Chu Min Li and Felip Manya.  Maxsat, hard and soft constraints.  In Handbook of satisfiability, pages 903–927. IOS Press, 2021.
  * [33] Shilin Huang and Kenneth R Brown.  Between shor and steane: A unifying construction for measuring error syndromes.  Physical review letters, 127(9):090505, 2021.
  * [34] Shilin Huang and Kenneth R Brown.  Constructions for measuring error syndromes in calderbank-shor-steane codes between shor and steane methods.  Physical Review A, 104(2):022429, 2021.
  * [35] Yu Tomita and Krysta M Svore.  Low-distance surface codes under realistic quantum noise.  Physical Review A, 90(6):062320, 2014.
  * [36] Noah Shutty and Christopher Chamberland.  Decoding merged color-surface codes and finding fault-tolerant clifford circuits using solvers for satisfiability modulo theories.  Physical Review Applied, 18(1):014072, 2022.
  * [37] Chin Yang Lee.  An algorithm for path connections and its applications.  IRE transactions on electronic computers, (3):346–365, 1961.
  * [38] Lingling Lao and Carmen G. Almudever.  Fault-tolerant quantum error correction on near-term quantum processors using flag and bridge qubits.  Phys. Rev. A, 101:032333, Mar 2020.
  * [39] Daniel Gottesman.  Stabilizer codes and quantum error correction.  California Institute of Technology, 1997.
  * [40] David Poulin.  Stabilizer formalism for operator quantum error correction.  Physical review letters, 95(23):230504, 2005.
  * [41] David P DiVincenzo and Panos Aliferis.  Effective fault-tolerant quantum computation with slow measurements.  Physical review letters, 98(2):020501, 2007.
  * [42] 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.
  * [43] Ian P Gent and Peter Nightingale.  A new encoding of alldifferent into sat.  In International Workshop on Modelling and Reformulating Constraint Satisfaction, volume 3, pages 95–110, 2004.
  * [44] Rui Chao and Ben W Reichardt.  Quantum error correction with only two extra qubits.  Physical review letters, 121(5):050502, 2018.
  * [45] Jiongzhi Zheng, Kun He, Jianrong Zhou, Yan Jin, Chumin Li, and Felip Manyà.  Incorporating multi-armed bandit with local search for maxsat.  ArXiv, abs/2211.16011, 2022.
  * [46] Alexey Ignatiev, Antonio Morgado, and Joao Marques-Silva.  PySAT: A Python toolkit for prototyping with SAT oracles.  In SAT, pages 428–437, 2018.
  * [47] Craig Gidney.  Stim: a fast stabilizer circuit simulator.  Quantum, 5:497, 2021.
  * [48] Oscar Higgott.  Pymatching: A python package for decoding quantum codes with minimum-weight perfect matching.  ACM Transactions on Quantum Computing, 3(3):1–16, 2022.
  * [49] Clare Horsman, Austin G Fowler, Simon Devitt, and Rodney Van Meter.  Surface code quantum computing by lattice surgery.  New Journal of Physics, 14(12):123011, 2012.
  * [50] Panos Aliferis and Andrew W Cross.  Subsystem fault tolerance with the bacon-shor code.  Physical review letters, 98(22):220502, 2007.
  * [51] Maxime A Tremblay, Nicolas Delfosse, and Michael E Beverland.  Constant-overhead quantum error correction with thin planar connectivity.  Physical Review Letters, 129(5):050504, 2022.