# Generating Shuttling Procedures for Constrained Silicon Quantum Dot Array

Naoto Sato, Tomonori Sekiguchi, Takeru Utsugi, and Hiroyuki Mizuno  Research &
Development Group,Hitachi, Ltd.
<EMAIL_ADDRESS>
###### Abstract

In silicon quantum computers, a single electron is trapped in a microstructure
called a quantum dot, and its spin is used as a qubit. For large-scale
integration of qubits, we previously proposed an approach of arranging the
quantum dots in a two-dimensional array and sharing a control gate in a row or
column of the array. In our array, the shuttling of electrons is a useful
technique to operate the target qubit independently and avoid crosstalk.
However, since the shuttling is also conducted using shared control gates, the
movement of qubits is complexly constrained. We therefore propose a formal
model on the basis of state transition systems to describe those constraints
and operation procedures on the array. We also present an approach to generate
operation procedures under the constraints. Utilizing this approach, we
present a concrete method for our 16 $\times$ 8 quantum dot array. By
implementing the proposed method as a quantum compiler, we confirmed that it
is possible to generate operation procedures in a practical amount of time for
arbitrary quantum circuits. We also demonstrated that crosstalk can be avoided
by shuttling and that the fidelity in that case is higher than when crosstalk
is not avoided.

##  I Introduction

Silicon quantum computing based on mature semiconductor technology is a
promising approach for the large-scale integration of qubits. A single
electron is trapped in a microstructure called a quantum dot formed in silicon
substrate, and its spin is used as a qubit. In order to execute a quantum gate
operation on those qubits, it is necessary to connect control gates
(plungers/barriers) to each quantum dot. As the number of qubits increases,
the number of control gates and their wirings also increases. Since sufficient
space is required to implement a large number of qubits, this imposes a
limitation for large-scale integration. Our approach to solving this problem
is to arrange the quantum dots in a two-dimensional array and provide a shared
control gate connected to the quantum dots in the same row or column of the
array [1][2].

There are three challenges when it comes to implementing quantum gate
operations in the quantum dot array using our approach. The first challenge is
how to connect a qubit arranged regularly in a two-dimensional array to read-
out circuits that can be placed on the rows at the end of the array. The
second challenge is how to suppress of the crosstalk during the quantum gate
operation. In a single qubit operation (e.g., spin rotation to a qubit), the
Larmor frequency of the qubit is selectively matched with the frequency of an
externally applied RF wave. However, neighboring qubits around the target
qubit also receive the effects of the RF wave from this operation, known as
crosstalk, and its spin direction is slightly disturbed. This reduces the
fidelity of the neighboring qubits. The third challenge is how to ensure the
independent quantum gate operation of a single qubit in an array where control
gates are shared by multiple quantum dots in a column or row. For example,
when a quantum gate operation is executed on a qubit using a control gate
shared by the column, another qubit in that column will also be operated on.

To overcome these challenges, we have proposed shuttling qubits [3] [4]. An
electron in a quantum dot can be shuttled to a neighboring quantum dot if
there is no electron in the dot, which is executed by applying appropriate
control voltage to the control gates. Regarding the first challenge, an
arbitrary qubit can be shuttled to the read-out circuit in the end rows of the
array. Crosstalk, the second challenge, can be suppressed by evacuating the
neighboring qubits away from the target qubit before the quantum gate
operation. For the third challenge, independent operation can be achieved by
moving other qubits away from the target qubit. To allow horizontal and
vertical shuttling of qubits, we proposed two-dimensional control gates [1].
The control gates in the first layer are shared by quantum dots in the same
column of the array. A qubit is shuttled horizontally using the column-shared
control gates in the first layer. If certain conditions are met, only one
qubit can be shuttled independently. Otherwise, all qubits in the same column
move simultaneously in the same direction. The shuttling in vertical
directions is conducted by the row-shared control gates in the second layer. A
row-shared control gate is connected to several quantum dots in the row, and
the qubits in the connected quantum dots are vertically shuttled by the row-
shared control gate simultaneously in the same direction. These complex
constraints of the quantum dot array make it difficult for the quantum
compiler to find a procedure for operating the quantum dot array in a
practical amount of time to execute arbitrary sequences of quantum gates, that
is, quantum circuits.

The first contribution of this paper is to present a formal model of quantum
dot arrays for expressing the operation procedures and constraints of the
array. We then demonstrate the usefulness of the model by formally describing
the structural and operational constraints of our 16 $\times$ 8 quantum dot
array [1][2] and the constraints to avoid crosstalk. The second contribution
is to show an approach to generate operation procedures under those complex
constraints. On the basis of this approach, we propose a concrete method to
generate operation procedures for our 16 $\times$ 8 quantum dot array as the
third contribution. By implementing the proposed method as a quantum compiler,
we confirmed that it is possible to generate operation procedures in a
practical amount of time for arbitrary quantum circuits. Furthermore,
simulations confirmed that crosstalk can be avoided in the generated operation
procedures, and that the procedure that avoids crosstalk by shuttling has
higher fidelity of the output quantum state than the procedure that does not
avoid crosstalk.

In Section II of this paper, we briefly introduce quantum circuits and silicon
quantum dot arrays. The constraints and requirements that the operation
procedures of our silicon quantum dot array should satisfy are formally
defined in Section III. The problem we tackle in this paper is described with
examples in Section IV. As an approach to solve the problem, we present a
state transition system and its conditions to search for the operation
procedure in Section V. In Section VI, we present a concrete state transition
system for our 16 $\times$ 8 silicon quantum dot array. The algorithm to
search the transition system and extract an operation procedure is shown in
Section VII. The proposed method is implemented and evaluated in Section VIII.
We discuss the improvements of the transition system to obtain more efficient
operation procedures and the effectiveness of crosstalk avoidance in Section
IX. In Section, X related work is described. The conclusions drawn from this
study are presented in Section XI.

##  II Preliminaries

###  II-A Quantum Circuit

A qubit, which is a variable in a quantum program, is in a superposition of
the basis state |0> and |1>. When a qubit is measured, 0 or 1 is observed
probabilistically, depending on its superposition state. The state of a qubit
can be expressed as $|\psi>=a_{0}|0>+a_{1}|1>$ ($|a_{0}|^{2}+|a_{1}|^{2}=1$),
where $a_{0}$ and $a_{1}$ are complex numbers and called amplitudes. The
absolute squares of the amplitudes $|a_{0}|^{2}$ and $|a_{1}|^{2}$ represent
the probabilities of obtaining 0 and 1 by a measurement. Generally, an
arbitrary quantum state consisting of $n$ qubits is represented by $2^{n}$
basis states. A quantum program is represented by a model called a quantum
circuit. Figure 1 shows an example of a quantum circuit to generate the Bell
state. Each horizontal line corresponds to a qubit, and the operations on
them, called quantum gates, are arranged from left to right.

Figure 1: Quantum circuit to generate the Bell state

In this quantum circuit, qubits $q0$ and $q1$ are both initialized to $|0>$,
respectively. Then, after the Hadamard gate is executed for $q0$, the CNOT
gate is executed on $q0$ and $q1$. Both $q0$ and $q1$ are then measured.

###  II-B Silicon Quantum Dot Array

In our silicon quantum dot array (SQDA), quantum gate operations and
measurements are conducted by control gates that are connected to quantum
dots. If one control gate is connected to each quantum dot, the number of
control gates increases with the number of qubits. Therefore, reducing the
number of control gates is a problem that needs to be solved for large-scale
integration of qubits. To this end, we proposed arranging the quantum dots in
a two-dimensional array and sharing a control gate in each row and column. The
structure of the quantum dot array presented in our prior work [1][2] is shown
in Fig. 2.

Figure 2: Structure of quantum dot array

The black circles represent quantum dots, and the thick orange lines are the
channels connecting the quantum dots. Each quantum dot is controlled by a
control gate connected to that quantum dot and its adjacent potential barrier.
The rectangles represent potential barriers between quantum dots. The red and
green lines are the column-shared and row-shared control gates for the quantum
dots (plunger gates), respectively. Similarly, the blue and purple lines are
column-shared control gates for the potential barrier between horizontally
adjacent quantum dots and row-shared control gates for the potential barrier
between vertically adjacent quantum dots (barrier gates), respectively.

When control gates are shared for each row and column of the array, the number
of control gates increases by $O(\sqrt{n})$ for the number of qubits $n$. This
is advantageous for large-scale integration compared to the case where control
gates are connected individually to each qubit. However, another problem
arises: the same operation is always conducted on quantum dots connected to
the same control gate. This problem can be solved by shuttling electrons
between quantum dots [5][6][7][8][9][10][11][12][13][14]. Before executing an
operation on a particular dot, electrons in quantum dots connected to the same
control gate as the dot can be evacuated by shuttling. This allows the
operation on a specific qubit. In addition, silicon qubits can suffer from
interference, called crosstalk [15][16][17][18][19][20], between neighboring
qubits during qubit gate operations, resulting in reduced fidelity. By
evacuating irrelevant electrons from around the qubits to be operated on in
advance, the occurrence of crosstalk can be avoided and the reduction in
fidelity can be prevented. Thus, by utilizing electron shuttling, it may be
possible to reduce both the number of control gates and the crosstalk. It
should be noted, however, that electron shuttling is also conducted by the
same control gates as quantum gate operations. In other words, the
simplification of the quantum dot array structure to reduce the number of
control gates also imposes restrictions on the shuttling of electrons. This
shuttling constraint is formulated in the next section.

The native quantum gate set of the SQDA consists of $Rx(\theta)$ and
$Ry(\theta)$ gates for arbitrary $\theta$ and a $(SWAP)^{\alpha}$ gate where
the exponent $\alpha$ is arbitrarily controlled by adjusting the strength and
duration of the Heisenberg exchange [21][22]. An arbitrary quantum circuit can
be decomposed into an equivalent quantum circuit consisting of these native
gates. We assume that the quantum circuit consists of only these native gates.
The difference between the control of the $Rx(\theta)$ and $Ry(\theta)$ gates
is the phase of the irradiated radio frequency electromagnetic wave, and the
control related to the electron transfer is the same. Therefore, in the
following, we refer to the $Rx(\theta)$ and $Ry(\theta)$ gates together as a
single-qubit gate. Similarly, the $(SWAP)^{\alpha}$ gate is referred to as a
two-qubit gate. Quantum circuits that appear in the following are assumed to
consist of only these native gates.

##  III Constraints and Requirements of Array Operation Procedure

As mentioned in Section II-B, in the SQDA shown in our prior work [1][2],
control gates are shared for each column and row. This has the constraint that
the same quantum gate operations, measurements, and shuttling operations are
executed on electrons located in the same column or row at the same time. In
this section, we formally define these SQDA constraints as properties that
array operation procedures should satisfy. Similarly, using the same formal
model, we define the requirement that the quantum gate operations be executed
as indicated by the quantum circuit as a property of the array operation
procedure.

###  III-A Formal Model of SQDA

The structure of a quantum dot array is represented as an undirected graph.
The movement of electrons on the array by shuttling is modeled as a state
transition system $M$, where the state represents the position of the
electrons on the graph. $M$ is denoted by $(S,s_{0},L,T,F)$. $S$ is a finite
set of states and $s_{0}$ is an initial state ($s_{0}\in S$). $L$ is a finite
set of labels that correspond to the operations of quantum gate, measurement,
and shuttling. $T$ is a set of transitions defined as $T\subseteq(S\times
L\times S)$. $F$ is a set of final states. Since operations on the SQDA can be
stopped at any time, $F$ includes all states in $S$, that is, $F=S$. A finite
transition path $p$ of $M$ is given as a sequence of transitions
$[t_{1},...,t_{i},...,t_{n}]$. Transition $t_{i}\in T$ is expressed as
$(s_{i-1},l_{i},s_{i})$, where $s_{i-1},s_{i}\in S$ and $l_{i}\in L$.

An arbitrary state $s_{i}$ is denoted by $(A,R,B,pos_{i})$. The $A$ represents
the topology of the array, which is invariant at any $s_{i}$ since the
topology does not change at runtime. $A$ is represented by a graph $(V,E)$
with quantum dots as vertices and the channels connecting them as edges. The
set of vertices $V$ is the set of quantum dots. The set of edges $E$ is the
set of channels, whose elements are unordered pairs of two quantum dots
connected by channels. That is, $E\subseteq\\{(x,y)|x,y\in V\land x\neq y\\}$.
In our SQDA, quantum dots are arranged in a lattice. The number of rows and
columns of the array is described as $ROW$ and $COL$, respectively. We denote
the quantum dots in row $r\leq ROW$ and column $c\leq COL$ as $V_{r,c}$. $V$
is defined using $v_{r,c}$, as in formula 1.

$\displaystyle V{\mathrm{def}}{=}\left\\{v_{r,c}|1\leq r\leq ROW\land 1\leq
c\leq COL\right\\}$ (1)

Channels are formed between particular adjacent quantum dots. That is, the
following formula 2 holds for $E$.

$\displaystyle\forall v_{r1,c1},v_{r2,c2}\cdot(v_{r1,c1},v_{r2,c2})\in E$
$\displaystyle\Rightarrow(|r1-r2|+|c1-c2|=1)$ (2)

$R:V\rightarrow Bool$ is a predicate indicating that the quantum dots are
connected to row-shared control gates. Between quantum dots that are
vertically connected in a channel, a two-qubit gate is executed using row-
shared control gates. The row-shared control gate is not connected to all the
qubits in the row. However, if a quantum dot is connected to a row-shared
control gate, all the quantum dots in the same column are connected to the
row-shared control gate located in the respective row. This constraint is
represented by formula 3.

$\displaystyle\forall r1,r2,c\cdot 1\leq r1\leq ROW\land 1\leq r2\leq ROW$
$\displaystyle\land 1\leq c\leq COL\land R(v_{r1,c})\Rightarrow R(v_{r2,c})$
(3)

The structure of quantum dots, channels, and row-shared control gates is
illustrated in Fig. 3. For the sake of simplicity, the column-shared control
gates are not shown because they are installed in all rows. More precisely, as
shown in Fig. 2, some column-shared control gates (red line) are not connected
to the quantum dots that are connected to the row-shared control gate.
However, the same control as that by the column control gate can be achieved
by the row-shared control gate (green line). Therefore, we can assume that all
quantum dots are connected to the column-shared control gate, and the column-
shared control gates are thus omitted in Fig. 3 and subsequent figures.

Figure 3: Example of row-shared control gates

The $B$ is the set of electrons on the array, and an electron is described as
$b_{j}\in B$. Function $pos_{i}$ represents the position of the electrons at
$s_{i}$. It maps each electron to the quantum dot in which it exists, i.e.,
$pos_{i}:B\rightarrow V$. For use in the following formulae, we define the set
of quantum dots $P_{i}\subseteq V$ as follows: $P_{i}=\left\\{v|b\in B\land
v=pos_{i}(b)\right\\}$. $P_{i}$ represents the quantum dots that trap an
electron in $s_{i}$.

The label $l_{i}\in L$ is represented by a set of tuples consisting of
electrons and an operation on them. There are four types of operations:
single-qubit gate, two-qubit gate, measurement, and shuttling. The operator
for the single-qubit gate operation is denoted by $g1$, and the single-qubit
gate operation on electron $b_{j}$ is denoted by $(g1,b_{j})$. Similarly, a
measurement on $b_{j}$ is denoted by $(m,b_{j})$. The two-qubit gate operation
on electrons $b_{j1}$ and $b_{j2}$ is denoted as $(g2,b_{j1},b_{j2})$. Since
electrons may move up, down, left, or right, we define $sh\text{-}u$,
$sh\text{-}d$, $sh\text{-}l$, and $sh\text{-}r$ as shuttling operators,
respectively. For example, the operation to shuttle electron $b_{j}$ in the
upward direction is denoted as $(sh\text{-}u,b_{j})$. Label $l_{i}$ is the set
of these operations, that is, multiple operations can be executed
simultaneously in a single state transition. Note that the states in $M$
represents not quantum states but the positions of electrons on the SQDA. The
operations of quantum gates and measurements in which the electron positions
do not change are represented as loop transitions from a state to the same
state. That is, if the label $l_{i}$ is a set consisting of arbitrary quantum
gate and measurement operations, $s_{i-1}=s_{i}$ at the transition
$(s_{i-1},l_{i},s_{i})$.

###  III-B Constraints of Quantum Gates and Measurements

Before defining the constraints, we introduce the predicates $SameCol_{i}$,
$SameRow_{i}$, $AdjHor_{i}$, and $AdjVer_{i}$ as predicates related to the
position of electrons on the array. The predicate $SameCol_{i}(b_{j},b_{k})$
will be True if $b_{j}$ and $b_{k}$ are in the same column in state $s_{i}$.
Similarly, $SameRow_{i}(b_{j},b_{k})$ will be True if $b_{j}$ and $b_{k}$ are
in the same row in state $s_{i}$. The predicates $AdjHor_{i}(b_{j},b_{k})$
will be True if $b_{j},b_{k}$ are horizontally adjacent and the quantum dots
that trap them are connected by channels. $AdjHor_{i}$ means that these two
electrons can be executed on by a two-qubit gate. Similarly, the predicates
$AdjVer_{i}(b_{j},b_{k})$ will be True if $b_{j},b_{k}$ are vertically
adjacent and the quantum dots that trap them are connected by channels. In
addition, it should be held that these quantum dots have to be connected to
row-shared control gates because the vertical two-qubit gate is not conducted
by column-shared gates but by row-shared control gates. The formal definitions
of these predicates are given in Appendix XI-A.

####  III-B1 Single-qubit Gates

A single-qubit gate operation is conducted using a column-shared control gate.
Therefore, when a single-qubit gate operation is executed on an electron
$b_{j}$, the same single-qubit gate operation is also executed on the other
electrons in the same column, such as $b_{k}$ in Fig. 4(a)(b). That is,
formula 4 is satisfied, where $l_{i+1}$ is the label of arbitrary transition
from state $s_{i}$.

Figure 4: Single-qubit gate operation

$\displaystyle\forall b_{j},b_{k}\in B,\forall l_{i+1}\in L\cdot(g1,b_{j})\in
l_{i+1}$ $\displaystyle\land SameCol_{i}(b_{j},b_{k})\Rightarrow(g1,b_{k})\in
l_{i+1}$ (4)

Since single-qubit gates are executed by column-shared control gates, all
electrons in adjacent columns to the right and left of the target electrons
are affected by crosstalk. For example, in Fig. 5, electrons $b_{k1}$ and
$b_{k2}$ are affected by crosstalk of the operation targeting electron
$b_{j}$. Electrons $b_{k3}$ and $b_{k4}$ are not affected.

Figure 5: Crosstalk of single-qubit gate operation

Therefore, when executing a single-qubit gate, it is necessary to ensure that
there is no electron in the adjacent quantum dot in the controlled column.
This constraint is expressed by the following formula 5.

$\displaystyle\forall b_{j}\in B,\forall l_{i+1}\in L,\forall
v_{r_{k},c_{k}}\in V\cdot(g1,b_{j})\in l_{i+1}$ $\displaystyle\land
v_{r_{j},c_{j}}=pos_{i}(b_{j})\land|c_{j}-c_{k}|=1\Rightarrow
v_{r_{k},c_{k}}\notin P_{i}$ (5)

####  III-B2 Two-qubit Gates

The two-qubit gate operation can be executed between two adjacent quantum dots
connected by a channel horizontally or vertically. This is expressed by the
following formula 6.

$\displaystyle\forall b_{j1},b_{j2}\in B,\forall l_{i+1}\in
L\cdot(g2,b_{j1},b_{j2})\in l_{i+1}$
$\displaystyle\Rightarrow\left(AdjHor_{i}(b_{j1},b_{j2})\lor
AdjVer_{i}(b_{j1},b_{j2})\right)$ (6)

When the target electrons $b_{j1}$ and $b_{j2}$ are horizontally adjacent,
column-shared control gates are used to execute a two-qubit gate. Therefore,
the two-qubit gate operation is also executed on the other two electrons
$b_{k1}$ and $b_{k2}$ that are in the same columns and are horizontally
adjacent (Fig. 6).

Figure 6: Horizontal two-qubit gate operation

The following formula 7 expresses this constraint.

$\displaystyle\forall b_{j1},b_{j2},b_{k1},b_{k2}\in B,\forall l_{i+1}\in
L\cdot(g2,b_{j1},b_{j2})\in l_{i+1}$ $\displaystyle\land
AdjHor_{i}(b_{j1},b_{j2})\land AdjHor_{i}(b_{k1},b_{k2})$ $\displaystyle\land
SameCol_{i}(b_{j1},b_{k1})\land SameCol_{i}(b_{j2},b_{k2})$
$\displaystyle\Rightarrow(g2,b_{k1},b_{k2})\in l_{i+1}$ (7)

When the target electrons $b_{j1}$ and $b_{j2}$ are vertically adjacent, row-
shared control gates are used. Therefore, the same two-qubit gate is executed
on the other two electrons $b_{k1}$ and $b_{k2}$ in the same rows and are
vertically adjacent (Fig. 7).

Figure 7: Vertical two-qubit gate operation

This constraint can be expressed by the following formula 8.

$\displaystyle\forall b_{j1},b_{j2},b_{k1},b_{k2}\in B,\forall l_{i+1}\in
L\cdot(g2,b_{j1},b_{j2})\in l_{i+1}$ $\displaystyle\land
AdjVer_{i}(b_{j1},b_{j2})\land AdjVer_{i}(b_{k1},b_{k2})$ $\displaystyle\land
SameRow_{i}(b_{j1},b_{k1})\land SameRow_{i}(b_{j2},b_{k2})$
$\displaystyle\Rightarrow(g2,b_{k1},b_{k2})\in l_{i+1}$ (8)

In the case of a two-qubit gate, i.e., $(SWAP)^{\alpha}$, it can be assumed
that no crosstalk occurs in the adjacent quantum dots [23][24]. However, if
another electron exists in a quantum dot in the target columns or rows in
which the two-qubit gate operation is executed, that electron will be affected
by the two-qubit gate operation. Therefore, it is necessary to evacuate the
other electrons from the target columns or rows before executing the two-qubit
gate. Note that if the quantum dot in which an electron exists is not
connected to the adjacent quantum dot by a channel, that electron is not
affected by the two-qubit gate operation. In Fig. 8, electron $b_{k1}$ is
affected by the two-qubit gate operation, but $b_{k2}$ is not affected.

Figure 8: Effects of two-qubit gate operation

In the case of horizontal two-qubit gates, the constraint to avoid the effect
is expressed by the following formula 9.

$\displaystyle\forall b_{j1},b_{j2}\in B,\forall l_{i+1}\in L,\forall
v_{r_{k},c_{k1}},v_{r_{k},c_{k2}}\in V\cdot$
$\displaystyle(g2,b_{j1},b_{j2})\in l_{i+1}\land AdjHor_{i}(b_{j1},b_{j2})$
$\displaystyle\land v_{r_{j},c_{j1}}=pos_{i}(b_{j1})\land
v_{r_{j},c_{j2}}=pos_{i}(b_{j2})$ $\displaystyle\land c_{k1}=c_{j1}\land
c_{k2}=c_{j2}\land(v_{r_{k},c_{k1}},v_{r_{k},c_{k2}})\in E$
$\displaystyle\Rightarrow(v_{r_{k},c_{k1}}\notin P_{i}\land
v_{r_{k},c_{k2}}\notin P_{i})$ $\displaystyle\lor(v_{r_{k},c_{k1}}\in
P_{i}\land v_{r_{k},c_{k2}}\in P_{i})$ (9)

For vertical two-qubit gates, the constraint is described as formula 10.

$\displaystyle\forall b_{j1},b_{j2}\in B,\forall l_{i+1}\in L,\forall
v_{r_{k1},c_{k}},v_{r_{k2},c_{k}}\in V\cdot$
$\displaystyle(g2,b_{j1},b_{j2})\in l_{i+1}\land AdjVer_{i}(b_{j1},b_{j2})$
$\displaystyle\land v_{r_{j1},c_{j}}=pos_{i}(b_{j1})\land
v_{r_{j2},c_{j}}=pos_{i}(b_{j2})$ $\displaystyle\land r_{k1}=r_{j1}\land
r_{k2}=r_{j2}\land(v_{r_{k1},c_{k}},v_{r_{k2},c_{k}})\in E$
$\displaystyle\Rightarrow(v_{r_{k1},c_{k}}\notin P_{i}\land
v_{r_{k2},c_{k}}\notin P_{i})$ $\displaystyle\lor(v_{r_{k1},c_{k}}\in
P_{i}\land v_{r_{k2},c_{k}}\in P_{i})$ (10)

####  III-B3 Measurements

In our SQDA, a measurement operation can be conducted on the rightmost column
of the array. If there are other electrons in the rightmost column, the same
measurement operation is executed on the other electrons, as well as the
single-qubit gate (Fig. 9).

Figure 9: Measurement operation

These constraints are represented by the following formulae 11 and 12, where
$COL$ represents the rightmost column number of the array.

$\displaystyle\forall b_{j}\in B,\forall l_{i+1}\in L\cdot(m,b_{j})\in
l_{i+1}$ $\displaystyle\Rightarrow v_{r_{j},c_{j}}=pos_{i}(b_{j})\land
c_{j}=COL$ (11) $\displaystyle\forall b_{j},b_{k}\in B,\forall l_{i+1}\in
L\cdot(m,b_{j})\in l_{i+1}$ $\displaystyle\land
SameCol(b_{j},b_{k})\Rightarrow(m,b_{k})\in l_{i+1}$ (12)

###  III-C Shuttling of Electrons

An electron in one quantum dot can be shuttled only to the adjacent quantum
dot to which the channel is connected. If an electron is moved to a quantum
dot where another electron is already trapped, the electrons collide and
quantum information is lost, so shuttling is prohibited in such cases. Since
shuttling in the vertical direction is conducted by row-shared control gates,
the quantum dot in which the target electron exists has to be connected to
row-shared control gates. These constraints are expressed by the following
formulae 13 to 16.

$\displaystyle\forall b_{j}\in B,\forall l_{i+1}\in
L\cdot(sh\text{-}u,b_{j})\in l_{i+1}$ $\displaystyle\Rightarrow
v_{r_{j},c_{j}}=pos_{i}(b_{j})\land r_{j}>1\land R(v_{r_{j},c_{j}})$
$\displaystyle\land\left(v_{r_{j},c_{j}},v_{r_{j}-1,c_{j}}\right)\in E\land
v_{r_{j}-1,c_{j}}\notin P_{i}$ (13) $\displaystyle\forall b_{j}\in B,\forall
l_{i+1}\in L\cdot(sh\text{-}d,b_{j})\in l_{i+1}$ $\displaystyle\Rightarrow
v_{r_{j},c_{j}}=pos_{i}(b_{j})\land r_{j}<ROW\land R(v_{r_{j},c_{j}})$
$\displaystyle\land\left(v_{r_{j},c_{j}},v_{r_{j}+1,c_{j}}\right)\in E\land
v_{r_{j}+1,c_{j}}\notin P_{i}$ (14) $\displaystyle\forall b_{j}\in B,\forall
l_{i+1}\in L\cdot(sh\text{-}l,b_{j})\in l_{i+1}$ $\displaystyle\Rightarrow
v_{r_{j},c_{j}}=pos_{i}(b_{j})\land c_{j}>1$
$\displaystyle\land\left(v_{r_{j},c_{j}},v_{r_{j},c_{j}-1}\right)\in E\land
v_{r_{j},c_{j}-1}\notin P_{i}$ (15) $\displaystyle\forall b_{j}\in B,\forall
l_{i+1}\in L\cdot(sh\text{-}r,b_{j})\in l_{i+1}$ $\displaystyle\Rightarrow
v_{r_{j},c_{j}}=pos_{i}(b_{j})\land c_{j}<COL$
$\displaystyle\land\left(v_{r_{j},c_{j}},v_{r_{j},c_{j}+1}\right)\in E\land
v_{r_{j},c_{j}+1}\notin P_{i}$ (16)

The shuttle operation in the horizontal direction is conducted by controlling
the column-shared control gates. Therefore, when an electron is shuttled
horizontally, other electrons in the same column are also shuttled in the same
direction. However, it is possible to block the shuttling of other electrons
in the same column, which is called block control [25]. The block control is
implemented by raising the potential barrier between the quantum dots. This
barrier prevents other electrons from moving at the same time as the target
electron. The conditions under which the shuttling of electrons in the same
column can be blocked are shown in Fig. 10.

Figure 10: Horizontal shuttling with block control

When $b_{j}$ is shuttled, electron $b_{k}$ in the same column can be blocked
if the quantum dot in the column with $b_{j}$ is connected to a row-shared
control gate and the quantum dot in the column to which $b_{j}$ is moving is
not connected to a row-shared control gate (Fig. 10(a)). This is achieved by
changing the voltage applied to the row-shared control gates of $b_{j}$ and
$b_{k}$. A high potential is formed in the row of $b_{j}$ and a low potential
in the row of $b_{k}$ (Fig. 11(a)). This makes a potential difference between
the current quantum dot of $b_{j}$ and its right quantum dot, and only $b_{j}$
is shuttled to the right. Since there is not a potential difference between
the current quantum dot of $b_{k}$ and its right quantum dot, $b_{k}$ is not
moved. Similarly, $b_{k}$ can be blocked if the quantum dot in the column with
$b_{j}$ is not connected to a row-shared control gate and the quantum dot in
the column to which $b_{j}$ is moving is connected to a row-shared control
gate (Fig. 10(b)). This is also achieved by controlling the row-shared control
gates of $b_{j}$ and $b_{k}$ separately. A low potential is formed in the row
of $b_{j}$ and a high potential in the row of $b_{k}$ (Fig. 11(b)). The high
potential prevents $b_{k}$ from shuttling to the right. Note that in both
cases, it is also possible to move $b_{k}$ at the same time as $b_{j}$ (Fig.
10(c)(d)). However, if there is another electron in the quantum dot to which
$b_{k}$ is moving, $b_{k}$ cannot be blocked. In that case, to avoid the
collision of the electrons, the shuttling operation on $b_{j}$ is prohibited
(Fig. 10(e)(f)). Even if the above conditions for block control are not
satisfied, $b_{k}$ is blocked if there is no channel between the quantum dot
of $b_{k}$ and the quantum dot to which $b_{k}$ is moving. These constraints
of shuttling are expressed by the following formulae 17 and 18. The predicate
$BC$ is defined by the formula 40 in Appendix XI-A, which will be True if the
conditions for block control are satisfied.

Figure 11: Potential control for block control

$\displaystyle\forall b_{j},b_{k}\in B,\forall l_{i+1}\in
L\cdot(sh\text{-}l,b_{j})\in l_{i+1}$ $\displaystyle\land
SameCol_{i}(b_{j},b_{k})\land v_{r_{k},c_{k}}=pos_{i}(b_{k})$
$\displaystyle\land\lnot
BC(v_{r_{k},c_{k}},v_{r_{k},c_{k}-1})\land(v_{r_{k},c_{k}},v_{r_{k},c_{k}-1})\in
E$ $\displaystyle\Rightarrow(sh\text{-}l,b_{k})\in l_{i+1}$ (17)
$\displaystyle\forall b_{j},b_{k}\in B,\forall l_{i+1}\in
L\cdot(sh\text{-}r,b_{j})\in l_{i+1}$ $\displaystyle\land
SameCol_{i}(b_{j},b_{k})\land v_{r_{k},c_{k}}=pos_{i}(b_{k})$
$\displaystyle\land\lnot
BC(v_{r_{k},c_{k}},v_{r_{k},c_{k}+1})\land(v_{r_{k},c_{k}},v_{r_{k},c_{k}+1})\in
E$ $\displaystyle\Rightarrow(sh\text{-}r,b_{k})\in l_{i+1}$ (18)

The vertical shuttling operation is conducted by the row-shared control gates.
Therefore, if a quantum dot that is in the same row as the target electron
$b_{j}$ and is connected to the row-shared control gate traps the electron
$b_{k}$, $b_{k}$ is shuttled together in the same vertical direction as
$b_{j}$ (Fig. 12(a)). If there is no channel between the quantum dot of
$b_{k}$ and the quantum dot to which it shuttles, $b_{k}$ stays (Fig. 12(b)).

Figure 12: Vertical shuttling

The constraints on the vertical shuttling are expressed by formulae 19 and 20.
Note that in the case of vertical shuttling, $b_{k}$ cannot be blocked because
the potential barrier cannot be controlled separately for each column.

$\displaystyle\forall b_{j},b_{k}\in B,\forall l_{i+1}\in
L\cdot(sh\text{-}u,b_{j})\in l_{i+1}$ $\displaystyle\land
SameRow_{i}(b_{j},b_{k})\land v_{r_{k},c_{k}}=pos_{i}(b_{k})\land
R(v_{r_{k},c_{k}})$ $\displaystyle\land(v_{r_{k},c_{k}},v_{r_{k}+1,c_{k}})\in
E\Rightarrow(sh\text{-}u,b_{k})\in l_{i+1}$ (19) $\displaystyle\forall
b_{j},b_{k}\in B,\forall l_{i+1}\in L\cdot(sh\text{-}d,b_{j})\in l_{i+1}$
$\displaystyle\land SameRow_{i}(b_{j},b_{k})\land
v_{r_{k},c_{k}}=pos_{i}(b_{k})\land R(v_{r_{k},c_{k}})$
$\displaystyle\land(v_{r_{k},c_{k}},v_{r_{k}-1,c_{k}})\in
E\Rightarrow(sh\text{-}d,b_{k})\in l_{i+1}$ (20)

In addition, we define a constraint about the simultaneous execution of
single-qubit gate, two-qubit gate, measurement, and shuttling. Since all of
these operations are conducted by control gates, they cannot be executed
simultaneously on the same electron. This constraint is shown in the following
formula 21, where $o_{b_{j}}$ denotes an operation on electron $b_{j}$, such
as $(g1,b_{j})$. The same applies to $o_{b_{k}}$.

$\displaystyle\forall o_{b_{j}},o_{b_{k}},\forall b_{j},b_{k}\in B\cdot
o_{b_{j}}\in l_{i+1}\land o_{b_{k}}\in l_{i+1}$ $\displaystyle\Rightarrow
b_{j}=b_{k}$ (21)

###  III-D Requirements of Transition Path

The arbitrary transition path of $M$ is denoted by
$p=[t_{1},...,t_{i},...,t_{n}]$, where $t_{i}=(s_{i-1},l_{i},s_{i})$. The
sequence of labels $l_{1},...,l_{i},...,l_{n}$ represents the operation
procedure of the array. If $p$ contains the operations of quantum gates and
measurements in the same order as a quantum circuit, $p$ is able to execute
the quantum circuit. A quantum circuit can be represented by a directed
acyclic graph (DAG) whose nodes correspond to operations and whose edges
indicate the order of the operations [26][27]. Figure 13(b) represents the DAG
of the quantum circuit shown in (a). For example, the $(SWAP)^{1/2}$ gate of D
is executed after the $Rx(\pi)$ gate of A and $(SWAP)^{1/4}$ gate of C.

Figure 13: Example of directed acyclic graph

A DAG consists of $Ope$ and $Ord$. $Ope$ is the set of nodes and $Ord$ is the
set of edges. A node of the DAG represents an operation. An edge from node
$o_{1}\in Ope$ to another node $o_{2}\in Ope$ is represented as
$(o_{1},o_{2})$, and $(o_{1},o_{2})\in Ord$ holds. For the target quantum
circuit $QC=(Ope,Ord)$, the path $p=[...,(s_{i-1},l_{i},s_{i}),...]$ is
required to satisfy the following formulae 22 and 23.

$\displaystyle\forall o_{1},o_{2}\in Ope,\forall l_{a},l_{b}\in
L\cdot(o_{1},o_{2})\in Ord$ $\displaystyle\land o_{1}\in l_{a}\land o_{2}\in
l_{b}\Rightarrow a<b$ (22) $\displaystyle\forall l\in L\cdot o\in l\Rightarrow
o\in Ope$ (23)

Formula 22 expresses that the order of operations in $p$ is consistent with
the order defined by the DAG. Formula 23 means that operations that do not
consist of the DAG are not included in $p$. When these formulae hold, the
transition path $p$ is an operation procedure for executing the quantum
circuit $QC$.

##  IV Problem Statement

When we can extract a transition path $p$ from $M$ that satisfies all the
constraints and requirements discussed in Section III, $p$ corresponds to a
procedure to execute a quantum circuit $QC$ with SQDA. Whether $p$ satisfying
the constraints and requirements can be extracted depends not only on the
search method of $M$ but also on the array topology $A$, the structure of the
row-shared control gates represented by $R$, and initial electron position
$s_{0}$. Depending on $A$, $R$, and $s_{0}$, there may be no $p$ that
satisfies the constraints and requirements. An example is shown in Fig. 14.

Figure 14: Example of situations with no solution

In (a), it is not possible to execute a two-qubit gate on $b_{0}$ and $b_{4}$
because the array is overfilled with electrons relative to the number of
quantum dots. If we add a third row in the array, as shown in (b), we can
execute that quantum gate. Otherwise, if the target quantum circuit includes
only a two-qubit gate on $b_{0}$ and $b_{4}$ but not a two-qubit gate on
$b_{0}$ and $b_{1}$, then the electrons should initially be placed as in (c).
This also allows the two-qubit gate on $b_{0}$ and $b_{4}$ to be executed
without adding the third row. As this example shows, certain quantum circuits
may not be executable depending on $A$, $R$, and $s_{0}$. That is, as shown in
Fig. 15(a), there may be no $p$ that satisfies the constraints and
requirements in the search space of $M$.

Figure 15: Problems in the search for operation procedures

As the scale of quantum circuits increases, it becomes difficult to execute
breadth-first search due to the limitation of memory, so $M$ is explored using
a depth-first search. However, due to the complicated constraints and
requirements, it is possible to search a space with no solution, as shown in
Fig. 15(b). An example is presented in Fig. 16.

Figure 16: Example of exploring a subspace with no solution

In this example, a two-qubit gate is executed on $b_{0}$ and $b_{1}$, followed
by a two-qubit gate on $b_{2}$ and $b_{3}$. The quantum dots in which $b_{0}$
and $b_{1}$ are trapped are not connected by channels. Therefore, in (a),
$b_{0}$ and $b_{1}$ are shuttled to the bottom row of the array to execute a
two-qubit gate. However, this results in $b_{0}$, $b_{1}$, $b_{2}$, and
$b_{3}$ being in the same row. This means that only shuttling operations that
move these four electrons upward or downward at the same time can be executed.
For example, $b_{2}$ and $b_{3}$ cannot be adjacent to each other to conduct a
two-qubit gate. On the other hand, in (b), by moving $b_{0}$ and $b_{1}$
upward to the upper quantum dot, the four electrons are avoided to line up in
the same row. As a result, a two-qubit gate for $b_{2}$ and $b_{3}$ can be
executed with the procedure shown in (b). This example suggests that certain
operations may lead to a situation in which subsequent quantum gate operations
cannot be executed. In such a case, it takes time to extract $p$ because it is
necessary to exhaustively search a subspace with no solution and then move on
to search another space by backtracking. Depending on the size of the subspace
to be searched, the search may not be completed in a practical amount of time.

Other quantum computers (e.g., superconducting quantum computers) have a
similar problem, called the qubit mapping problem, in which the constraint
that the qubits to be executed in a two-qubit gate must be adjacent is called
the nearest neighbor constraint (NN-constraint) [28][29]. In the qubit mapping
problem, the mapping between logical and physical qubits is changed by
inserting a SWAP gate so that the NN-constraint is satisfied. The SWAP gate
moves the contents of the target qubits so that they are adjacent for the two-
qubit gate operation. The problem of finding the optimal SWAP gate insertion
to satisfy the NN-constraint is NP-hard [30][31][32][33], and various methods
for solving it have been proposed [34][35][36][29][37][38][39][28][27][40]. In
contrast, in our SQDA, the complexity of the constraints makes it difficult to
extract an operation procedure to execute a given arbitrary quantum circuit,
which is the problem we address in this paper.

##  V Approach

The problem shown in Section IV will not occur if we do not get into a
situation where a particular quantum gate cannot be executed during the search
for a transition path. Therefore, we construct $M$ so that the search can
reach a state where any quantum gate operation can be executed from any
intermediate state $s_{i}(i\geq 0)$ in $p$. In more detail, we restrict the
transitions of $M$ to satisfy the following conditions C1 to C6.

$\displaystyle[C1]\forall b_{j}\in B,\exists s\in OS\cdot(s,l,s)\in T\land
l=\\{(g1,b_{j})\\}$ $\displaystyle[C2]\forall b_{j1},b_{j2}\in B,\exists s\in
OS\cdot(s,l,s)\in T$ $\displaystyle\quad\quad\land l=\\{(g2,b_{j1},b_{j2})\\}$
$\displaystyle[C3]\forall b_{j}\in B,\exists s\in OS\cdot(s,l,s)\in T\land
l=\\{(m,b_{j})\\}$ $\displaystyle[C4]\forall s_{rs}\in RS,s_{os}\in OS\cdot
Reachable(s_{rs},s_{os})$ $\displaystyle[C5]s_{0}\in RS$
$\displaystyle[C6]\forall s_{rs1}\in RS,\forall s\in S\exists s_{rs2}\in
RS\cdot Reachable(s_{rs1},s)$ $\displaystyle\quad\quad\Rightarrow
Reachable(s,s_{rs2})$

C1, C2, and C3 define the operation states ($OS$), which is the set of states
of $M$. The $OS$ includes the states in which a single qubit gate for any
electron, a two-qubit gate for any pair of electrons, and a measurement for
any electron can be independently executable. If a particular operation is
always conducted together with another operation, the executable quantum
circuits are limited. In other words, independently executable means that no
other operations are conducted simultaneously with that operation. C4 defines
the set of states called ready states ($RS$), in which the states are
reachable to all the states contained in $OS$. The predicate
$Reachable(s_{a},s_{b})$ will be True if there exists an arbitrary transition
path from state $s_{a}$ to $s_{b}$, or $s_{a}=s_{b}$. C5 means that the
initial state $s_{0}$ is contained in $RS$. C6 gives the constraint that every
state reachable from a state in $RS$ is reachable to at least one state
contained in $RS$. In other words, if a search is started from a state in
$RS$, it will never fall into a state that cannot be returned to the state in
$RS$.

By restricting $M$ to satisfy C1 to C5, the search can reach the states where
quantum gate operations and measurements can be independently executed on
arbitrary electrons from a state in $RS$. Moreover, by satisfying C6, the
search can return to a state in $RS$ from any state reached. Thus, if any
state is reached during the search, it is possible to return from that state
to a state in $RS$. From that state in $RS$, a transition path to conduct an
arbitrary operation sequence of quantum gates and measurements can be
extracted. Among the components of $M$, the set of states $S$ and the set of
transitions $T$ can be changed by the quantum compiler. On the other hand, the
topology $A$ of SQDA and the configuration of the row-shared control gate $R$
are determined when the SQDA is manufactured and cannot be changed by the
compiler. Therefore, it is necessary to design $A$ and $R$ before
manufacturing the SQDA so that $M$ satisfies conditions C1 to C6, considering
the behavior of the quantum compiler.

For example, suppose that a small array is designed as $A$ and $R$ shown in
Fig. 17. If the number of qubits used in the quantum circuit to be executed is
3, i.e., $B=\\{b_{0},b_{1},b_{2}\\}$, the state transition system $M$
satisfying conditions C1 to C6 can be constructed as shown in Fig. 18.

Figure 17: Small example of quantum dot array structure

Figure 18: State transition system $M$ of the small example

The electrons are initially placed as shown in $s_{0}$. The transition path
for conducting a single-qubit gate for $b_{0}$ is
$[(s_{0},l_{1},s_{1}),(s_{1},l_{2},s_{2}),(s_{2},l_{3},s_{2})]$. The
transition from $s_{0}$ to $s_{1}$ is caused by the shuttling of electron
$b_{2}$ to the quantum dot on the right, so $l_{1}=\\{(sh\text{-}r,b_{2})\\}$.
In state $S_{2}$, the loop transition representing the execution of a single-
qubit gate occurs, so $l_{3}=\\{(g1,b_{0})\\}$.

Figure 18 shows only three states in $OS$ as examples—single-qubit gate for
$b_{0}$ ($s_{2}$), two-qubit gates for $b_{0}$ and $b_{1}$ ($s_{7}$), and
measurement for $b_{0}$ ($s_{8}$)—but we assume that operations on other
electrons are also included in $OS$. Thus, C1, C2, and C3 are satisfied. C4
holds because the states $s_{0}$ and $s_{4}$ contained in $RS$ are reachable
to $s_{2}$, $s_{7}$, and $s_{8}$ contained in $OS$. C5 is also satisfied since
$s_{0}$ is contained in $RS$. For $s_{1}$, $s_{2}$, $s_{3}$, $s_{5}$, $s_{6}$,
$s_{7}$, and $s_{8}$ that are reachable from $s_{0}$ and $s_{4}$, they are
reachable to either $s_{0}$ or $s_{4}$ contained in $RS$. Therefore, C6 is
held.

##  VI State Transition System for 16 $\times$ 8 SQDA

We present a concrete state transition system $M$ for our 16 $\times$ 8 SQDA.
The transitions of $M$ should satisfy conditions C1 to C6 and the constraints
represented by formulae 4 to 21

###  VI-A Array Structure

We define the structure of SQDA consisting of 16 columns x 8 rows of quantum
dots as shown in Fig. 19. The structure is defined by $A=(V,E)$ representing
the array topology and $R$ representing the row-shared control gate. They
satisfy the following formulae 24 to 28.

$\displaystyle\forall v_{r,c}\in V,\exists n\in\mathbb{N}\cdot c=2n\Rightarrow
R(v_{r,c})$ (24) $\displaystyle\forall v_{r,c}\in V,\exists
n\in\mathbb{N}\cdot c=2n-1\Rightarrow\lnot R(v_{r,c})$ (25)
$\displaystyle\forall v_{r1,c1},v_{r2,c2}\in V,\exists n\in\mathbb{N}\cdot
c1=2n\land c1=c2$
$\displaystyle\land|r1-r2|=1\Rightarrow(v_{r1,c1},v_{r2,c2})\in E$ (26)
$\displaystyle\forall v_{r1,c1},v_{r2,c2}\in V,\exists n\in\mathbb{N}\cdot
c1=2n-1\land c1=c2$
$\displaystyle\land|r1-r2|=1\Rightarrow(v_{r1,c1},v_{r2,c2})\notin E$ (27)
$\displaystyle\forall v_{r1,c1},v_{r2,c2}\in V\cdot|c1-c2|=1\land r1=r2$
$\displaystyle\Rightarrow(v_{r1,c1},v_{r2,c2})\in E$ (28)

$\mathbb{N}$ is the set of natural numbers. Formula 24 represents that even-
numbered columns of quantum dots are connected to row-shared control gates.
Similarly, formula 25 represents that the quantum dots in odd-numbered columns
are not connected to the row-shared control gate. Thus, by connecting the row-
shared control gate every other column, block control is possible in all
columns based on formula 40. Formula 26 means that the vertically adjacent
quantum dots in even-numbered columns are connected by channels. Formula 27
indicates that vertically adjacent quantum dots in odd-numbered columns are
not connected by channels. Formula 28 expresses that all horizontally adjacent
quantum dots are connected by channels. Thus, by not installing vertical
channels in odd-numbered columns, even if electrons in even-numbered columns
are moved vertically, the electrons placed in odd-numbered columns are not
moved together with them from formulae 19 and 20.

###  VI-B Ready States

We define ready states $RS$ based on the above structure. A state in which all
electrons are placed in a quantum dot that is not connected to a row-shared
control gate is included in $RS$. In those states in $RS$, quantum dots in
which electrons can be placed are called seat dots. No electrons are placed in
the quantum dots of a particular row. This specific row is called the bus row
and its row number is denoted as $r_{bus}$. The bus row is utilized as a
pathway for moving electrons to another column to execute a two-qubit gate. By
using block control, electrons can be moved through the bus row while other
electrons remain in place. The columns connected to the row-shared control
gate are also used as pathways for electrons to exit the bus row. These
columns are called aisle columns. The state $s_{i}$ satisfying the following
formula 29 is contained in $RS$.

$\displaystyle\forall v_{r,c}\in V\cdot v_{r,c}\in P_{i}\Rightarrow\lnot
R(v_{r,c})\land r\neq r_{bus}$ (29)

In Fig. 19, the quantum dots filled in gray are the seat dots when
$r_{bus}=4$. If electrons are placed only in these quantum dots in $s_{i}$,
$s_{i}$ is included in $RS$. Thus, for our 16 $\times$ 8 SQDA, 56 electrons
can be used at most.

Figure 19: Quantum dots where electrons can be placed in the states of $RS$

Figure 20 shows an example of a state included in $RS$ when the number of
electrons is 7. All electrons exist in seat dots.

Figure 20: Example of a state included in $RS$

###  VI-C Transitions of Single-qubit Gates

We define the transitions from a state in $RS$ to a state in which a single-
qubit gate can be executed independently. Let $b_{j}$ be the target qubit of
the single-qubit gate. In order to execute a single-qubit gate for $b_{j}$
independently, from formula 4, it is necessary to evacuate other electrons in
the column $c_{j}$ where $b_{j}$ is located. Furthermore, according to formula
5, it is necessary to evacuate electrons outside of the adjacent columns to
avoid crosstalk. As an example, the transition from the state of $RS$ shown in
Fig. 20 to the state where a single-qubit gate on $b_{2}$ is executed is shown
in Fig. 21.

Figure 21: Example of transitions for the execution of a single-qubit gate

In order to execute a single qubit gate for $b_{2}$ in column 9, $b_{3}$ in
the same column needs to be moved out. Therefore, $b_{1}$ in column 7 is first
moved to column 6 to create the space for $b_{3}$, Next, $b_{3}$ is moved to
column 7. As a result, there are no other electrons in the same and adjacent
columns of $b_{2}$. This avoids crosstalk and allows a single-qubit gate to be
executed independently. In this example, $b_{3}$ is evacuated to the left
side, but it can also be evacuated to the right column 11.

The transitions for executing a single-qubit gate operation on an arbitrary
electron $b_{j}$ independently are shown in Fig. 22. The column where $b_{j}$
is located in state $s_{a}$ is represented by $c_{j}$. That is,
$v_{r_{j},c_{j}}=pos_{a}(b_{j})$. This figure shows only the transitions for
the case where electrons in the same column as $b_{j}$ are evacuated to the
left side. A similar transition can be performed for the case of evacuating to
the right side. If $c_{j}\leq 3$, it cannot be evacuated to the left, so it is
evacuated to the right. Similarly, if $c_{j}\geq 14$, it is moved to the left
side.

Figure 22: Transitions to execute a single-qubit gate

In the transition from $s_{a}$ to $s_{b}$, electrons in column $c_{j}-2$ are
shuttled to the left to create an evacuation area for electrons other than
$b_{j}$ in column $c_{j}$. In rows where no electrons are located in column
$c_{j}$, electrons in column $c_{j}-2$ need not be evacuated. Therefore, only
electrons in row $r$ that satisfy $v_{r,c_{j}}=pos_{a}(b)$—that is, only
electrons in the same row $r$ as $b$, which is in the same column as
$b_{j}$—are moved. Next, in the transition from $s_{b}$ to $s_{d}$, all
electrons in column $c_{j}$ except $b_{j}$ are shuttled left to column
$c_{j}-2$. These transitions satisfy the shuttling constraints represented by
formulae 13 to 21. The transition $(s_{d},l,s_{d})inT$ representing a single-
qubit gate operation, where $l=\\{(g1,b_{j})\\}$, is performed in $s_{d}$.
This transition satisfies the constraint of formula 4. In addition, since
there are no electrons in the adjacent columns, the constraint represented by
formula 5 is also satisfied. Therefore, crosstalk can be avoided.

We next define transitions from state $s_{d}$ to return to a state included in
$RS$. We use the reverse procedure of transitioning from $s_{a}$ to $s_{d}$.

Figure 23: Transitions to return to a state in $RS$ after the single-qubit
gate operation

Figure 23 represents the transitions back to $s_{a}$ in $RS$ after the
electron in the same row as $b_{j}$ is evacuated to the left as shown Fig. 22.
In the transitions from $s_{d}$ to $s_{b}$, the electrons, which are evacuated
in column $c_{j}-2$, are returned to the original column $c_{j}$. Then, in the
transition from $s_{b}$ to $s_{a}$, the electrons in column $c_{j}-3$ are
returned to the original column $c_{j}-2$. These transitions satisfy the
shuttling constraints represented by formulae 13 to 21. The same transitions
can be performed to return to the state in $RS$ when the electrons are
evacuated to the right side.

###  VI-D Transitions of Two-qubit Gates

We define the transitions from state $s_{a}$ in $RS$ to a state in which the
two-qubit gate is executed independently. Let $b_{j1},b_{j2}$ be the target
electrons and $v_{r_{j1},c_{j1}}=pos_{a}(b_{j1})$ and
$v_{r_{j2},c_{j2}}=pos_{a}(b_{j2})$. Assume $c_{j1}\leq c_{j2}$ without loss
of generality. We execute a two-qubit gate by vertically adjoining $b_{j1}$
and $b_{j2}$ and using row-sharing control gates. In a two-qubit gate
operation, the same operation may be conducted on electrons in the same row
(formula 8) or may be affected by the operation (formula 10). In any states in
$RS$, none of the seat dots where electrons are located are vertically
connected by a channel (Fig. 19). Therefore, if no electrons other than
$b_{j1}$ and $b_{j2}$ are moved, a two-qubit gate can be conducted on $b_{j1}$
and $b_{j2}$ without effects. Fig. 24 shows an example of the transition from
the state shown in Fig. 20 to a state to execute a two-qubit gate on $b_{0}$
and $b_{6}$.

Figure 24: Example of transitions for the execution of a two-qubit gate

The electron $b_{0}$ moves through the adjacent aisle column to the bus row.
It then passes through the bus row to the aisle column adjacent to $b_{6}$.
Next, $b_{6}$ moves through the adjacent aisle column to the quantum dot
vertically adjacent to $b_{0}$. Figure 25 shows the transitions to execute a
two-qubit gate on $b_{j1},b_{j2}$.

Figure 25: Transitions to execute a two-qubit gate

The transition from state $s_{a}$ to $s_{e}$ moves the electron $b_{j1}$ to
the left aisle column, and the transitions from $s_{e}$ to $s_{f}$ transfer
$b_{j1}$ through the aisle column to reach the quantum dot that intersects the
bus row. The transition from $s_{f}$ to $s_{g}$ moves $b_{j1}$ through the bus
row to the quantum dot where the bus row intersects the aisle column to the
left of the row where $b_{j2}$ is located. However, if the aisle column to the
right of $b_{j1}$ and the aisle column to the left of $b_{j2}$ are the same
($c_{j2}-c_{j1}=2$), the transition from $s_{f}$ to $s_{g}$ is not necessary.
Similarly, if electrons $b_{j1},b_{j2}$ are in the same column, we use the
aisle column adjacent to the right of them as the meeting point. Therefore,
the transition from $s_{f}$ to $s_{g}$ is unnecessary. The transition from
$s_{g}$ to $s_{h}$ moves electron $b_{j2}$ to the left aisle column (when
$b_{j1},b_{j2}$ are in the same column, they are exceptionally moved to the
right aisle column, that is, the label of the transition from $s_{g}$ to
$s_{h}$ is $\\{(sh\text{-}r,b_{j2})\\}$ ). Since $b_{j1}$ is waiting at the
quantum dot where the aisle column and the bus row intersect, the transition
from $s_{h}$ to $s_{i}$ moves $b_{j2}$ to a position adjacent to $b_{j1}$.
These transitions satisfy the shuttling constraints represented by formulae 13
to 21. The transition $(s_{i},l,s_{i})\in T$ representing a two-qubit gate
operation, where $l=\\{(g2,b_{j1},b_{j2}\\}$, is executed in $s_{i}$. This
transition satisfies the constraint of formula 8. In addition, since the
electrons in the same row as $b_{j1}$ and $b_{j2}$ are located in the seat
dots that are not connected to the neighboring dots by channels, they are not
affected by the two-qubit gate operation. This means that the constraint
represented by formula 10 is satisfied. In Fig. 25, $b_{j1}$ is moved to the
side of $b_{j2}$, but a two-qubit gate can also be executed by moving $b_{j2}$
to the side of $b_{j1}$ by a similar procedure. Therefore, we also define the
transitions for moving $b_{j2}$ to $b_{j1}$ in $M$.

Next, we give the transitions to return to a state in $RS$ after executing the
two-qubit gate. The electrons that the two-qubit gate were executed on do not
have to be returned to the original seat dots. If there is another empty seat
dot with a closer distance (distances in this paper are Manhattan distances),
it is better to return to that seat dot to reduce the number of shuttling
operations. Figure 26 shows an example.

Figure 26: Example of transitions after the two-qubit gate operation

The seat dot where $b_{6}$ was originally located is $v_{6,11}$. If there is
an empty seat dot closer than $v_{6,11}$ from $b_{6}$, $b_{6}$ should be moved
to that seat dot. The distance from $b_{6}$ to $v_{6,9}$ is the same as the
distance to $v_{6,11}$. In this case, $b_{6}$ can move to either $v_{6,9}$ or
$v_{6,11}$. Since $b_{0}$ exists in the bus row, $b_{6}$ cannot move through
the bus row to the seat dots on the other side of the bus row. Therefore, to
move to the seat dot on the other side of the bus row, it has to take a
different route. For example, it is possible to reach the other side of the
bus row by a detour route through $v_{6,9}$. However, a detour route should
always pass through a seat dot such as $v_{6,9}$. The distance to move through
$v_{6,9}$ to another seat dot is obviously longer than the distance to
$v_{6,9}$. Therefore, when returning electrons to the nearest seat dot, no
detour route needs to be considered. Suppose $b_{6}$ moves to $v_{6,11}$.
Then, if $b_{0}$ moves to an empty seat dot, it can return to the state in
$RS$. As empty seat dots that $b_{0}$ can move, $v_{3,7}$, $v_{6,7}$, and
$v_{6,9}$ are candidates. Since the shortest distance to move is $v_{6,9}$,
$b_{0}$ moves to $v_{6,9}$.

Figure 27 shows the transitions to return to a state in $RS$ after executing
the two-qubit gate. Let $v_{r_{\beta},c_{\beta}}$ be the quantum dot to which
$b_{j2}$ can return, which satisfies the following formula 30. Electron
$b_{j2}$ moves to the nearest quantum dot that satisfies this condition. The
positions of $b_{j1}$ and $b_{j2}$ in state $s_{i}$ are represented by
$r_{j1},c_{j1}$ and $r_{j2},c_{j2}$, respectively. That is,
$v_{r_{j1},c_{j1}}=pos_{i}(b_{j1})$ and $v_{r_{j2},c_{j2}}=pos_{i}(b_{j2})$.

Figure 27: Transitions to return to a state in $RS$ after the two-qubit gate
operation

$\displaystyle(r_{j2}=r_{bus}-1\Rightarrow 1\leq r_{\beta}<r_{bus})$
$\displaystyle\land(r_{j2}=r_{bus}+1\Rightarrow r_{bus}<r_{\beta}\leq ROW)$
$\displaystyle\land(c_{\beta}=c_{j2}-1\lor c_{\beta}=c_{j2}+1)$
$\displaystyle\land v_{r_{\beta},c_{\beta}}\notin P_{i}$ (30)

In Fig. 27, the transitions from $s_{i}$ to $s_{k}$ represent a move of
$b_{j2}$ to $v_{r_{\beta},c_{\beta}}$. In the transitions from $s_{i}$ to
$s_{j}$, $b_{j2}$ moves through the aisle column to the quantum dot adjacent
to $v_{r_{\beta},c_{\beta}}$. Then, $s_{k}$ moves $b_{j2}$ to
$v_{r_{\beta},c_{\beta}}$ by the transition to $s_{k}$. Similarly, let
$v_{r_{\alpha},c_{\alpha}}$ be the quantum dot to which $b_{j1}$ can return;
then, $v_{r_{\alpha},c_{\alpha}}$ satisfies the following formula 31.The
$b_{j1}$ moves to the nearest quantum dot that satisfies this condition.

$\displaystyle 1\leq r_{\alpha}\leq ROW\land 1\leq c_{\alpha}\leq
COL\land\lnot R(v_{r_{\alpha},c_{\alpha}})$ $\displaystyle\land r_{\alpha}\neq
r_{bus}\land v_{r_{\alpha},c_{\alpha}}\notin P_{i}$ (31)

In the transition from $s_{k}$ to $s_{l}$, $b_{j1}$ moves through the bus row
to the aisle column adjacent to $v_{r_{\alpha},c_{\alpha}}$ . The transition
from $s_{l}$ to $s_{m}$ moves $b_{j1}$ through the aisle column to the quantum
dot adjacent to $v_{r_{\alpha},c_{\alpha}}$. Then, in the transition to
$s_{n}$, $b_{j1}$ moves to $v_{r_{\alpha},c_{\alpha}}$. These returning
transitions satisfy the shuttling constraints represented by formulae 13 to
21.

###  VI-E Transitions of Measurements

We define the transitions from state $s_{a}$ in $RS$ to a state in which the
measurement is executed independently. Let $b_{j}$ be the qubit to be
measured, where $v_{r_{j},c_{j}}=pos_{a}(b_{j})$. From formula 12, $b_{j}$
should be moved to the rightmost column $COL=16$ for the execution of the
measurement. As an example, Fig. 28 shows the transitions for the measurement
on $b_{2}$.

Figure 28: Example of transitions for the execution of a measurement

When executing the measurement, it is necessary to evacuate other electrons in
the same column, from formula 12. In states in $RS$, no electrons are placed
in column 16 where the measurement can be conducted, so no shuttling operation
is required to evacuate the electrons from column 16.

The transitions from $s_{a}$ of $RS$ for executing the measurement for $b_{j}$
are shown in Fig. 29. As exception cases, when the target electron is in
column 15, it can be moved to column 16 simply by shuttling to the right. The
transitions of such cases are shown in Appendix XI-B.

Figure 29: Transitions to execute a measurement

The transitions from state $s_{a}$ to $s_{p}$ are similar to those for a two-
qubit gate. The electron $b_{j}$ passes through the right-neighboring aisle
column and reaches the quantum dot where the aisle column and the bus row
intersect. Then, in the transition from $s_{p}$ to $s_{q}$, $b_{j}$ goes
through the bus row and reaches the quantum dot in the rightmost column 16.
These transitions obviously satisfy the shuttling constraints represented by
formulae 13 to 21. The transition $(s_{q},l,s_{q})\in T$ representing a
measurement operation, where $l=\\{(m,b_{j})\\}$, is executed in $s_{q}$. This
transition satisfies the constraints expressed by formulae 11 and 12.

We define the transition to return to a state in $RS$ after the measurement is
executed. The electron $b_{j}$ measured in the rightmost column of the array
is ejected to the reservoir region connected to the right of the array by
shuttling to the right [2]. That is, after the measurement, $b_{j}$ disappears
from the array. Since no electrons other than $b_{j}$ are moved, the state
returns to a state in $RS$ when $b_{j}$ disappears. The transition back to the
state in $RS$ after the measurement is shown in Fig. 30.

Figure 30: Transition to return to a state in $RS$ after the measurement
operation

In $s_{q}$, the electron $b_{j}$ is located in the rightmost column 16 and the
other electrons are located in the seat dots. Therefore, when $b_{j}$
disappears from the array by shuttling it to the right, the state transits to
state $s_{r}$ that is included in $RS$. The returning transition also
satisfies the shuttling constraints represented by formulae 13 to 21.

###  VI-F Overview of All Transitions

The transitions defined in Sections VI-C to VI-E are summarized in Fig. 31. In
$s_{d}$, $s_{i}$, and $s_{q}$, a single-qubit gate, two-qubit gate, and
measurement, respectively, can be independently executed for any electron.
Therefore, $OS$ composed of those states satisfies C1, C2, and C3. Also, $M$
satisfies C4 because it can transit from any state $s_{a}$ in $RS$ to those
states. Although not shown in Fig. 31, transitions to $s_{d}$, $s_{i}$, and
$s_{q}$ are also possible from $s_{n}$ and $s_{r}$.

Figure 31: Overview of all transitions

Since $M$ is defined such that the sequence of the transitions from $s_{a}$ to
$s_{d}$ is a single path, it is guaranteed that transitions to $s_{d}$ are
possible from all states on the path from $s_{a}$ to $s_{d}$. The same is true
for transitions from $s_{a}$ to $s_{i}$, and from $s_{a}$ to $s_{q}$.
Similarly, the sequences of the transitions from $s_{d}$ to $s_{a}$, from
$s_{i}$ to $s_{n}$, and from $s_{q}$ to $s_{r}$ are defined to be single
paths. Therefore, it is guaranteed that transitions to $s_{a}$, $s_{n}$, or
$s_{r}$ in $RS$ are possible from all states on these paths. As a result, from
all states reachable from a state in $RS$, the states in $RS$ can be reached.
That is, C6 is satisfied. If a state in $RS$ is selected as the initial state
$s_{0}$, C5 is satisfied.

Finally, we define $M$ satisfying C1 to C6. By searching for $M$, we can
obtain the operation procedure for executing any quantum circuit with at most
56 qubits. Moreover, since the depth-first search does not enter a subspace
with no solution, the operation procedure can be obtained in a practical
amount of time without backtracking.

##  VII Search Algorithm

Even when restricting the transitions of $M$ as described in Section VI,
several choices arise in the search for transition paths. First, it is
necessary to decide which state in $RS$ is to be selected as the initial state
$s_{0}$. The number of shuttling operations can be reduced if the two
electrons on which a two-qubit gate is executed are placed close together.
This means that the initial placement of the electrons affects the number of
shuttling operations. Secondly, when executing a single-qubit gate, we can
choose whether to evacuate electrons to the right or to the left. Also, when
executing a two-qubit gate, we can choose whether to move electron $b_{j1}$
next to $b_{j2}$ or move $b_{j1}$ next to $b_{j2}$. In addition, after the
two-qubit gate is executed, if there are a number of nearest seat dots, we can
choose which one to move to. These selections can be arbitrarily determined to
obtain an operation procedure to execute a given quantum circuit. However, it
is better if we can choose as efficient an operation procedure as possible.
Therefore, we apply heuristics to choose efficient transitions, as shown in
Algorithm 1.

1

2

input : $A$, $R$, $QC$

output : $p$

3

4$p$, $s_{cur}$ = initial_placement($A$, $R$, $QC$)

5 $Executed\\_ops$ = $\varnothing$

6 $F$ = front_layer($QC$, $Executed\\_ops$)

7 while  _$F\neq\varnothing$_ do

8 for  _$f$ in $F$_ do

9 if  _$f.operation$ is g1_ then

10 $v_{c_{j},r_{j}}$ = pos_cur($f.electron$)

11 if  _$c_{j}\geq(COL-2)$_ then

12 $p$, $s_{cur}$ = p.update(g1_left, $f.electron$))

13

14 else if  _$c_{j}\leq 3$_ then

15 $p$, $s_{cur}$ = p.update(g1_right, $f.electron$))

16

17 else if  _count_cost(g1_left, $A$, $s_{cur}$) $>$ count_cost(g1_right, $A$,
$s_{cur}$)_ then

18 $p$, $s_{cur}$ = p.update(g1_right, $f.electron$))

19

20 else

21 $p$, $s_{cur}$ = p.update(g1_left, $f.electron$))

22

23

24 else if  _$f.operation$ is g2_ then

25 $Pao$ = placement_after_ops(f.operation, $A$, $s_{cur}$)

26 $best\\_pao$ = $Pao$[0]

27 for  _$pao$ in $Pao$_ do

28 $score$ = eval_placement($pao$, $QC$, $Executed\\_ops$)

29 if  _$score >best\\_pao.score$_ then

30 $best\\_pao$ = $pao$

31

32

33 $p$, $s_{cur}$ = p.update($best\\_pao$, $f.electron1$, $f.electron2$)

34

35 else if  _$f.operation$ is m_ then

36 $p$, $s_{cur}$ = p.update(m, $f.electron$)

37

38

39 $Executed\\_ops$ = $Executed\\_ops$ $\cup$ $\\{f\\}$

40 $F$ = front_layer($QC$, $Executed\\_ops$)

41

return $p$

Algorithm 1 Search Algorithm

The function initial_placement in line 1 determines the initial state $s_{0}$
from the array topology $A$, the structure of the row-shared control gates
$R$, and input quantum circuit $QC$. The path $p$ has a list of explored
states, i.e., $[s_{0}]$. The determined state $s_{0}$ is substituted to the
current state $s_{cur}$. The algorithm of initial_placement is based on the
approach of PAQCS [37]. An electron on which many two-qubit gates are executed
with other electrons should be placed in a seat dot that is close to as many
electrons as possible. Also, pairs of electrons on which many two-qubit gates
are executed should be placed as close together as possible. Moreover, in our
SQDA, since the measurement can be conducted only in the rightmost column, the
electrons to be measured should be placed as close to the rightmost column as
possible. In line 1, the function front_layer returns the front layer $F$
[27], which is the set of operations that can be executed next.
$Executed\\_ops$ denotes the set of operations that have been executed. In
other words, $F$ is the set of operations that do not have an unexecuted
predecessor in the DAG representing $QC$. When the operation obtained from $F$
is a single-qubit gate (line 1), check whether it is possible to secure the
evacuation space for other electrons on the right sides of the column $c_{j}$
where the electron to be operated is located. If not (line 1), the other
electrons in column $c_{j}$ are moved to column $c_{j}-2$ on the left side by
the transitions shown in Fig. 22. The method p.update in line 1 adds these
transitions to the end of $p$ and updates the current state $s_{cur}$.
Conversely, if no space can be secured on the left side (line 1), the other
electrons are moved to the right column $c_{j}+2$ (line 1). If the space can
be secured on both sides, the direction of the evacuation is determined on the
basis of the total distance traveled by the electrons, which is calculated by
the function count_cost (lines 1–1).

When the operation obtained from $F$ is a two-qubit gate (line 1), we choose
which electron is moved to the other side. Moreover, if there is more than one
nearest seat dot to which the electron is to be returned, one of them is
selected. In line 1, the function placement_after_ops extracts possible
electron placements after the execution of the two-qubit gate by simulating
all those cases. The result is saved in the variable $Pao$. In line 1,
eval_placement evaluates the electron placement in terms of the efficiency to
execute subsequent two-qubit gates, which is the same as initial_placement.
The most efficient placement is then assigned to $best\\_pao$ (line 1). The
transition from $s_{cur}$ to the state represented by $best\\_pao$ is added to
the end of $p$, and $s_{cur}$ is updated (line 1).

When the operation retrieved from $F$ is a measurement (line 1), the
transition path according to Figs. 29 and 30 is added to the end of $p$ and
$s_{cur}$ is updated (line 1). Line 1 adds the retrieved operation $f$ to the
set of executed operations $Executed\\_ops$. Front layer $F$ is updated to the
latest in line 1. If all operations comprising the quantum circuit $QC$ have
been executed, $F$ is empty. Then, the loop is broken at line 1. After $p$ is
returned at line 1, the procedure ends.

##  VIII Experimental Results

We implemented a quantum compiler (compiler 1) that searches the state
transition system $M$ constructed as in Section VI with a naive depth-first
search, using Qiskit®[41]. Compiler 1 does not evaluate possible directions to
evacuate neighboring electrons by function count_cost and possible electron
placements when returning to a ready state by function eval_placement in
Algorithm 1; rather, it adopts the first evacuation direction and electron
position it finds. We also implemented a second compiler (compiler 2) that
searches $M$ according to Algorithm 1. Quantum circuits consisting of the
native gates of our SQDA, i.e., $Rx(\theta)$, $Ry(\theta)$, and
$(SWAP)^{\alpha}$ gates, are randomly generated and input to these quantum
compilers. Then, the compilers generate operation procedures for the input
quantum circuit. Compiler 1 outputs the first transition path it finds as the
solution. The experiment was performed on an Ubuntu 20.04.2 LTS machine
equipped with two Intel® Core™ i9-9900K 3.60GHz processors with 8 cores and
62-GB memory. It also has an NVIDIA® GetForce®RTX 2080 Ti GPU.

Figure 32: Average compiling time with increasing number of quantum gates

Figure 33: Average number of operations with increasing number of quantum
gates

Figure 32 shows the average compiling time of 100 quantum circuits when the
number of quantum gates in the quantum circuit is increased from 1 to 300 for
10, 30, and 50 qubits, respectively. It is confirmed here that the operation
procedures for our SQDA can be generated in a practical amount of time, which
indicates that there is a solution in $M$ constructed by the proposed method
and that we do not spend a huge amount of time searching a subspace with no
solution. We also find that the compiling time increases with the number of
quantum gates but is not significantly affected by the number of qubits. This
is because the compilers refer to each quantum gate one by one from the
quantum circuit and generate the corresponding operation procedures. Comparing
compilers 1 and 2 in Fig. 32, we can see that the compile time of 1 is shorter
than that of 2. This is due to the fact that compiler 2 considers possible
evacuation directions and electron placements as shown in Algorithm 1. Figure
33 shows the average number of shuttling, quantum gate, and measurement
operations output by the compilers in the same experiment as in Fig. 32. This
indicate that compiler 2 with Algorithm 1 can generate a more efficient
operation procedure than compiler 1 with the naive depth-first search.
However, the effect is not significant. Improvements to generate more
efficient operation procedures are discussed in Section IX-A.

We also implemented a program to check the constraints and requirements
represented by formulae 4 to 23 and were able to confirm that the operation
procedures for our SQDA generated by compilers 1 and 2 satisfy these
constraints and requirements. This means that the generated procedures can
execute the target quantum circuits on the actual SQDA without crosstalk or
collisions of the electrons.

##  IX Discussion

###  IX-A Improvements of State Transition System

The proposed method constructs state transitions to conduct a single-qubit
gate, two-qubit gate, and the measurement independently, and restricts the
other state transitions. This guarantees that any operation can be executed in
any order. However, because of the restriction on $M$, it is not possible to
generate an operation procedure that simultaneously executes an operation on
multiple electrons at a time. For example, in the quantum circuit shown in
Fig. 13, the same $Rx(\theta)$ gate is first executed on qubit $q_{0}$ and
then on $q_{1}$. Assume the electrons corresponding to $q_{0}$ and $q_{1}$ are
$b_{0}$ and $b_{1}$, respectively. If $b_{0}$ and $b_{1}$ are initially placed
in the same column, the $Rx(\theta)$ gate can be efficiently executed on
$b_{0}$ and $b_{1}$ simultaneously by using the column-shared control gates.
However, with our current $M$, a procedure that executes the $Rx(\theta)$ gate
on $b_{0}$ followed by the same gate on $b_{1}$ is extracted. This increases
the number of operations to achieve the required quantum computation.
Similarly, some control gates can be operated in parallel, which also enables
us to execute multiple operations simultaneously. Therefore, to generate a
more efficient operation procedure, it is necessary to relax the constraints
of $M$, i.e., to allow other transitions in $M$ so that these simultaneous
operations can be extracted.

Allowing other transitions of $M$ means we can obtain a more efficient
operating procedure. In the transition discussed in Section VI-C, the
electrons move to the nearest empty seat dots after the two-qubit gate is
executed. However, to efficiently execute the subsequent two-qubit gates,
moving to a non-empty seat dot should also be considered. For example, Fig. 34
shows the state after the execution of a two-qubit gate on $b_{0}$ and
$b_{1}$. After $b_{1}$ goes back to quantum dot $v_{5,9}$, the nearest empty
seat dot from $b_{0}$ is $v_{3,7}$. We assume that the subsequent quantum gate
operations include a two-qubit gate of $b_{0}$ and $b_{2}$ and do not include
quantum gate operations using $b_{3}$. In that case, instead of moving $b_{0}$
to $v_{3,7}$, it is more efficient to first move $b_{3}$ to $v_{3,7}$ and then
move $b_{0}$ to $v_{3,9}$, as shown Fig. 34(a). By pushing $b_{3}$ out in this
way, $b_{0}$ and $b_{2}$, on which the subsequent two-qubit gate will be
executed, can be placed close together. In fact, if $b_{0}$ is moved to
$v_{3,7}$, four shuttling operations are conducted. In addition, five
shuttling operations are necessary for the execution of the subsequent two-
qubit gate on $b_{0}$ and $b_{2}$. In contrast, when moving $b_{0}$ to
$v_{3,9}$, four and three shuttling operations are required, respectively.
This means that the total number of operations can be reduced by pushing
electrons.

Figure 34: More efficient movements of electrons

If an electron utilized for a two-qubit gate is also used for the immediately
following two-qubit gate, it can move directly to the next two-qubit gate
position without returning to a seat dot. For example, in Fig. 34(b), it is
assumed that the two-qubit gate on $b_{0}$ and $b_{5}$ will be executed
immediately after the two-qubit gate on $b_{0}$ and $b_{1}$. In that case, it
is more efficient to move $b_{0}$ directly to $v_{4,8}$ than to move once back
to $v_{3,9}$ or $v_{3,7}$. Thus, we should consider direct transitions from a
state in $OS$ to the next state in $OS$ without going back to a state in $RS$.

###  IX-B Effectiveness of Shuttling for Crosstalk Avoidance

As discussed in Section VI-C, when executing a single-qubit gate, crosstalk
can be avoided if we evacuate neighboring electrons by shuttling. However, the
fidelity of the quantum state is also reduced by the shuttling operation.
Therefore, the reduction in fidelity due to the shuttling operation should be
smaller than the reduction in fidelity due to crosstalk. In this section, we
evaluate the fidelity reduction in two cases: one in which crosstalk is not
avoided (with-crosstalk) and one in which it is avoided by shuttling
(w/o-crosstalk). Examples of a single-qubit gate operation for the cases with-
crosstalk and w/o-crosstalk are shown in Figs. 35(a) and (b), respectively. In
the case of with-crosstalk, the electrons $b_{1}$, $b_{2}$, and $b_{3}$, which
were in the same row as the target electron $b_{0}$, are left in the adjacent
row and are affected by the cross-talk of the single-qubit gate. In contrast,
in the case of w/o-crosstalk, $b_{1}$, $b_{2}$, and $b_{3}$ are evacuated to
two columns away from the column of $b_{j}$, so they are not affected by the
crosstalk.

Figure 35: Single-qubit gate operation in the cases of with-crosstalk and
w/o-crosstalk

We assume that only crosstalk and shuttling operations cause the reduction in
fidelity, and do not consider other factors (e.g., quantum gate and
measurement operations). In the case of w/o-crosstalk, we estimate the number
of shuttling operations in the procedure extracted by the algorithm shown in
Section VI. Let $n$ and $m$ be the number of qubits and quantum gates
constituting the target quantum circuit, respectively. In our 16 $\times$ 8
SQDA, the electrons are placed in every row (except the bus row) and in every
two rows, as shown in Fig. 19. The lengths of the array sides are
$O((1/2)\sqrt{2n})$ and $O(2\sqrt{2n})$, respectively. The number of electrons
in each row and each column are $O(\sqrt{n})$. As defined in Fig. 22, when
executing a single-qubit gate on electron $b_{j}$ in $v_{r_{j},c_{j}}$, all
electrons in column $c_{j-2}$ are moved to column $c_{j-3}$, and then all
electrons in column $c_{j}$ (except $b_{j}$) electrons are moved to column
$c_{j-2}$. Therefore, the number of shuttling operations required before
executing the single-qubit gate is $O(3\sqrt{n})$. After the single-qubit gate
is executed, the reverse procedure is executed to return to the original state
in $RS$. Therefore, the number of shuttling operations after the single-qubit
gate is also $O(3\sqrt{n})$. The same is true when evacuating electrons to the
right side. The number of shuttling operations required for single-qubit gates
is expressed as $O(6m\sqrt{n})$.

In the case of a two-qubit gate, as defined in Fig. 25, electrons $b_{j1}$ and
$b_{j2}$ are moved through the aisle column and bus row to be adjacent. The
number of shuttling operations depends on the distance between $b_{j1}$ and
$b_{j2}$. For the sake of simplicity, we assume that the number of shuttling
operations is its median value. The maximum is the sum of the lengths of the
array sides, that is, $(1/2)\sqrt{2n}+2\sqrt{2n}$, and the minimum is 3.
Therefore, it is assumed that $O((1/4)\sqrt{2n}+\sqrt{2n})=O((5/4)\sqrt{2n})$.
Although $b_{j1}$ and $b_{j2}$ are returned to the nearest seat dot after the
two-qubit gate is executed (as defined in Fig. 27), we assume that they are
returned to the original seat dot. Therefore, the number of shuttling
operations for two-qubit gates is expressed as $O((5/2)m\sqrt{2n})$.

In the case of a measurement, if the bus row is placed approximately in the
center of the array, the average number of vertical shuttling operations to
the bus row is $O((1/8)\sqrt{2n})$. The average number of horizontal shuttling
operations is $O(\sqrt{2n})$. In the generated quantum circuits, all qubits
are measured once at the end. Therefore, the number of shuttling operations
for measurements is estimated as $O((9/8)n\sqrt{2n})$. Finally, the number of
shuttling operations in the case of w/o-crosstalk is
$O(6m\sqrt{n}+(5/4)m\sqrt{2n}+(9/8)n\sqrt{2n})$

Next, in the case of with-crosstalk, we estimate the number of shuttling
operations and crosstalk occurrences. When executing a single-qubit gate,
electrons in column $c_{j}$ (other than $b_{j}$) do not have to evacuate to
column $c_{j-2}$, where they are not affected by crosstalk. However, if they
are left on $c_{j}$, the single-qubit gate will be executed on them together
with $b_{j}$. Therefore, they are moved to column $c_{j-1}$. In this case, the
number of shuttling operations is reduced from $O(6m\sqrt{n})$ to
$O(2m\sqrt{n})$. All electrons moving from column $c_{j}$ to column $c_{j-1}$
are affected by crosstalk. The number of crosstalk occurrences is
$O(m\sqrt{n})$.

In the case of a two-qubit gate, the electrons in the same row as the target
electrons are located in the seat dots that are not connected to the
neighboring dots by channels. Therefore, they are not affected by the two-
qubit gate operation, and the number of shuttling operations is the same as in
the case of w/o-crosstalk. As for a measurement, the operation procedure is
the same as in the case of w/o-crosstalk. Finally, the number of shuttling
operations in the case of with-crosstalk is
$O(2m\sqrt{n}+(5/4)m\sqrt{2n}+(9/8)n\sqrt{2n})$, and the number of crosstalk
occurrences is $O(m\sqrt{n})$.

Denote the fidelity of a shuttling operation as $f_{sh}$ and the fidelity of
crosstalk as $f_{ct}$. The fidelity reduction due to shuttling can be
estimated by multiplying the fidelity of one shuttling operation by the number
of shuttling operations. The same is true for crosstalk. The fidelity in the
case of w/o-crosstalk is estimated as
$O(f_{sh}^{6m\sqrt{n}+(5/4)m\sqrt{2n}+(9/8)n\sqrt{2n}})$. Similarly, the
fidelity in the case of with-crosstalk is
$O(f_{sh}^{2m\sqrt{n}+(5/4)m\sqrt{2n}+(9/8)n\sqrt{2n}}\cdot
f_{ct}^{m\sqrt{n}})$. Let
$f_{sh}^{2m\sqrt{n}+(5/4)m\sqrt{2n}+(9/8)n\sqrt{2n}}$ be $a$; then, we can
express them as $O(a\cdot f_{sh}^{4m\sqrt{n}})$ and $O(a\cdot
f_{ct}^{m\sqrt{n}})$, respectively. Thus, if $f_{sh}^{4}>f_{ct}$ holds, the
fidelity of w/o-crosstalk will be higher than that of with-crosstalk.

We experimentally calculated fidelities for the quantum circuits used in
Section VIII in the cases of w/o-crosstalk and with-crosstalk by compiler 2.
Figure 36 shows the fidelities when the number of qubits of the quantum
circuits is 10, 30, and 50, respectively, assuming $f_{sh}=0.996$ [14] and
$f_{ct}=0.905$ [15]111In their previous study, the crosstalk of the Rabi
oscillation causes oscillations in the neighboring qubits, whose magnitude is
at most 0.2. The fidelity of the crosstalk is then assumed to be
$cos^{2}((0.2*\theta)/2)$, where $\theta$ is the rotation angle of a single-
qubit gate. Assume that $\theta$ is $\pi$, where the effect of the crosstalk
is maximized.. The horizontal axes represent the number of quantum gates.

Figure 36: Fidelity with increasing number of quantum gates

When $f_{sh}=0.996$ and $f_{ct}=0.905$, $f_{sh}^{4}>f_{ct}$ is held; thus,
higher fidelity is expected in the w/o-crosstalk cases. In fact, we confirmed
that the fidelities of the w/o-crosstalk cases are higher than those of the
with-crosstalk cases.

The fidelity in the case of w/o-crosstalk is estimated as
$O((0.996)^{6m\sqrt{n}+(5/4)m\sqrt{2n}+(9/8)n\sqrt{2n}})$. Similarly, the
fidelity in the case of with-crosstalk is
$O((0.996)^{2m\sqrt{n}+(5/4)m\sqrt{2n}+(9/8)n\sqrt{2n}}\cdot(0.905)^{m\sqrt{n}})$.
The logarithms for these orders are as follows.

$\displaystyle
O(log((0.996)^{6m\sqrt{n}+\frac{5}{4}m\sqrt{2n}+\frac{9}{8}n\sqrt{2n}}))$
$\displaystyle=O((6m\sqrt{n}+\frac{5}{4}m\sqrt{2n}+\frac{9}{8}n\sqrt{2n})\cdot(-0.00174))$
(32) $\displaystyle\simeq O(8m\sqrt{n}\cdot(-0.00174))$ (33) $\displaystyle
O(log((0.996)^{2m\sqrt{n}+\frac{5}{4}m\sqrt{2n}+\frac{9}{8}n\sqrt{2n}}\cdot(0.905)^{m\sqrt{n}}))$
$\displaystyle=O((2m\sqrt{n}+\frac{5}{4}m\sqrt{2n}+\frac{9}{8}n\sqrt{2n})\cdot(-0.00174)$
$\displaystyle\quad+m\sqrt{n}\cdot(-0.0434))$ (34) $\displaystyle\simeq
O(4m\sqrt{n}\cdot(-0.00174)+m\sqrt{n}\cdot 25(-0.00174))$
$\displaystyle=O(29m\sqrt{n}\cdot(-0.00174))$ (35)

From formulae 33 and 35, we estimate that the gradient of the fidelity for $m$
in the case of with-crosstalk is almost 3.6 times that of w/o-crosstalk. In
fact, the gradients in the case of with-crosstalk are 4.1, 3.9, and 3.7 times
those of w/o-crosstalk in Fig. 36, respectively. These experimental results
are consistent with the theoretical estimation. When focusing on the number of
qubits $n$, formulae 32 and 34 are approximated as
$O((1.6n+7.8m)\sqrt{n}\cdot(-0.00174))$ and
$O((1.6n+28.8m)\sqrt{n}\cdot(-0.00174))$, respectively.They are of higher
order for $n$ than for $m$, but the coefficient of $m$ is larger than that of
$n$. Therefore, when $n$ is small, $m$ contributes more strongly to the
decrease in fidelity. However, as $n$ becomes larger, it has a greater impact
to the decrease in fidelity than $m$.

Figure 37 shows the results when $f_{sh}=0.996$ and $f_{ct}=0.984$, so that
$f_{sh}^{4}=f_{ct}$.

Figure 37: Fidelity with increasing number of quantum gates when
$f_{sh}^{4}=f_{ct}$

The fidelities of with-crosstalk and w/o-crosstalk are almost equal, as
expected. From formulae 32 and 34, the errors in the number of shuttling
operations and crosstalk increase exponentially with the increase in the
number of quantum gates $m$. Therefore, in Fig. 37, the difference between
with-crosstalk and w/o-crosstalk increases with the number of quantum gates
$m$ (note that the fidelity is plotted on a logarithmic scale). This confirms
that if $f_{sh}^{4}>f_{ct}$ is satisfied, avoiding crosstalk will result in
higher fidelity.

Figure 38 shows the fidelities of w/o-crosstalk when $f_{sh}=0.99999$ and
$f_{ct}=0.905$. In this case, even when the number of qubits is 50 and the
number of quantum gates reaches 300, the fidelity is maintained over 0.95.
This suggests that the improvement in shuttling fidelity is necessary for
future practical use. Moreover, as discussed in Section IX-A, the proposed
method should also be improved to reduce the number of shuttling operations.

Figure 38: Fidelity with increasing number of quantum gates when
$f_{sh}^{4}=0.99999$

##  X Related Work

We have explaind how to generate operation procedures to execute an arbitrary
quantum circuit in a strictly constrained silicon quantum dot array. As
mentioned in Section IV, there is a similar problem called qubit mapping
problem [42][43][27] in superconducting quantum computing, which minimizes the
number of SWAP gates to be inserted to satisfy the NN-constraint. In the array
of a superconducting quantum computer, the target qubits must be adjacent to
each other to execute a two-qubit gate. When the target qubits are not
adjacent, the contents of the qubits are transferred by inserting SWAP gates.
The number of SWAP gates inserted to satisfy the NN-constraint is called the
nearest neighbor cost (NN-cost) [35][27]. The route to transfer the contents
of the qubits should be selected so that the NN-cost is as small as possible.
If the target qubits are located far apart, a lot of SWAP gates are inserted,
so it is desirable to initially position the target qubits of the two-qubit
gate as close together as possible. Moreover, transferring the content of the
target qubit by inserting SWAP gates also changes the contents of other qubits
on the route. If those other qubits are used in a subsequent quantum gate, it
is necessary to take the subsequent quantum gates into consideration when
determining the movement route of the qubit. Various methods for optimizing
the initial placement and movement routes of qubits have been proposed for
1-dimensional arrays [44][45][46][47][26][48][49][50] and 2-dimensional arrays
[34][29][37][35][40][36][38][28][51][27][39][52][53]. These studies tackled
the optimization problem of minimizing the NN-cost, i.e., the number of SWAP
gates to be inserted. Most of them presented heuristics to find an efficient
operation procedure from among a huge number of candidates. Only executing the
target quantum circuit by inserting SWAP gates is not difficult as long as its
efficiency is not a concern. In contrast, in our SQDA, the procedure to
execute the target quantum circuit is non-trivial due to the complex
constraints of the array (as formally described in Section III). Therefore, we
presented a method that enables us to obtain the procedures to execute
arbitrary target quantum circuits by restricting the initial placement and
movements of the electrons. We also introduced the heuristics of Algorithm 1
to obtain as efficient procedures as possible. The previous studies tackling
the qubit mapping problem correspond to Algorithm 1 in this paper. In fact,
function initial_placement in Algorithm 1 refers to an approach proposed in
one of the previous studies [37].

If some two-qubit gates consisting of a quantum circuit are commutative, the
execution order of them can be changed. Leveraging this property, a method was
proposed to change the execution order of two-qubit gates so that the NN-cost
is as small as possible [26][51]. Since our native two-qubit gate,
$(SWAP)^{\alpha}$, is not commutative, this method cannot be applied to our
algorithm directly. However, the idea of transforming the quantum circuit to
reduce NN-cost is useful for us. Ferrari et al. proposed transforming VQE
ansatz, which consists of a CNOT cascade, into an equivalent quantum circuit
consisting of CNOT gates on linearly adjacent qubits [54]. This allows all
CNOT gates to be executed without inserting SWAP gates when the qubits are
placed linearly adjacent to each other. Then, the NN-cost is greatly reduced.
Similarly, synthesis methods have also been proposed, in which the required
quantum computation is achieved with as few quantum gates as possible
[55][56]. If the number of quantum gates can be reduced bu utilizing these
techniques, the length of the operation procedure can also be shortened.

To improve the fidelity of the calculated quantum state, taking into account
the error rate of physical qubits and their links when solving the qubit
mapping problem has been proposed [57][58][59]. To make the shuttling
operation procedure more efficient in our SQDA, the device error
characteristics of quantum gate operations and measurements should be
considered. Moreover, to reduce crosstalk, optimizing the scheduling of
quantum gate operations and the location of the gate execution on the array
has been proposed [60][61]. In this work, we have defined crosstalk avoidance
as a constraint and generate an operation procedure that satisfies the
constraint. This is similar to these previous studies in that crosstalk is
reduced by compiler software.

In trapped-ion and trapped-atom quantum computers, the qubits can be moved by
shuttling the ions and atoms that form the building blocks of the qubits, as
in silicon quantum computers. Therefore, they are moved to satisfy the NN-
constraint to execute a two-qubit gate. In trapped-ion quantum computers, two
ions must be stored in the same trap, which is achieved by shuttling the
target ions. There have been several studies on improving the efficiency of
shuttling procedures for 1-dimensional [62][63] and 2-dimensional
architectures [64]. Webber et al. proposed a 2D array structure to allow any
ion to move to any trap by shuttling and defined the direction properties of
ion passage on the array [64]. This allows for a two-qubit gate to be executed
on any pair of ions. Their aim was to establish ways of executing arbitrary
quantum circuits, which is similar to our aim. Restricting the direction of
ion passage in their study corresponds to restricting the transitions of $M$
in this paper. However, our SQDA has more complex restrictions compared to
trapped-ion arrays, such as the fact that electrons in the same row move
together. Therefore, we restrict the movement of electrons more strictly: for
example, electrons can basically only pass through the bus row and aisle
column. In trapped-atom quantum computers, to execute a two-qubit gate, the
target atoms are moved by an optical tweezer so that they are adjacent to each
other. Prior studies have attempted to optimize the movement of the target
atoms [65][66] by using a Satisfiability Modulo Theories (SMT) model that
incorporates physical constraints for the movement by the optical tweezer. The
model is then input to an SMT solver [67] and the optimal procedure is
obtained as a solution. By describing the constraints of our SQDA in the SMT
model, it may be possible to derive an optimal operation procedure. However,
since the SMT solver is not scalable, this method is difficult to apply to
large-scale quantum circuits.

In silicon quantum computers, there are many previous studies on the
implementation of shuttling [5][6][7][8][9][10][11][12][13][14], which is the
premise of this paper. However, as far as we know, there have been no studies
on the pathways for transferring electrons by shuttling, or on their
optimization. We show for the first time how to compile an arbitrary quantum
circuit and generate operation procedures for silicon quantum computers.

##  XI Conclusion

We proposed a method to generate an operation procedure to execute arbitrary
quantum circuits in our SQDA, which has complex constraints. We first defined
a state transition system $M$ as a formal model of the SQDA. Then, using this
model, we formally described the constraints and requirements that the
operation procedure should satisfy. Second, we discussed the problem that
occurs when searching for operation procedures for the target quantum circuit,
which is that there may be no solution in the entire search space or a
particular subspace. This results in a search space having to be exhaustively
explored, and the operation procedure cannot be obtained in a practical amount
of time. To solve this problem, we introduced six conditions that should be
satisfied in $M$ and demonstrated the concrete $M$ for our SQDA satisfying
those conditions. We also implemented the concrete $M$ and its search
algorithm as quantum compilers. Experiments with these compilers demonstrated
that operation procedures for our SQDA can be discovered in a practical amount
of time by searching $M$.

Future work will include implementing the improvements of $M$ described in
Section IX-A. The restriction of transitions in $M$ should be relaxed to
generate more efficient operation procedures. The core idea of electron
movements presented in this paper consists of bus row, aisle column and seat
dot, but there may be other ideas to extract more efficient operation
procedures. In particular, if we restrict the target quantum circuit to a
particular algorithm, we may be able to construct a more efficient $M$
specific to that algorithm. For example, for quantum circuits implementing the
Quantum Approximate Optimazation Algorithm (QAOA), there is a certain pattern
in the order of the two-qubit gates to be executed. By focusing on that
pattern, it may be possible to develop an $M$ that is more efficient for the
quantum circuit of QAOA, but which may not support other quantum circuits.
This approach should be effective over the next few years because only a
limited number of algorithms are of practical use in the Noisy Intermediate-
Scale Quantum (NISQ) era [68].

## Acknowledgment

This work was supported by JST Moonshot R&D Grant Number JPMJMS2065.

## References

  * [1] N. Lee, R. Tsuchiya, G. Shinkai, Y. Kanno, T. Mine, T. Takahama, R. Mizokuchi, T. Kodera, D. Hisamoto, and H. Mizuno, “Enhancing electrostatic coupling in silicon quantum dot array by dual gate oxide thickness for large-scale integration,” _Applied Physics Letters_ , vol. 116, no. 16, p. 162106, 04 2020. [Online]. Available: https://doi.org/10.1063/1.5141522
  * [2] N. Lee, R. Tsuchiya, Y. Kanno, T. Mine, Y. Sasago, G. Shinkai, R. Mizokuchi, J. Yoneda, T. Kodera, C. Yoshimura, S. Saito, D. Hisamoto, and H. Mizuno, “16 x 8 quantum dot array operation at cryogenic temperatures,” _Japanese Journal of Applied Physics_ , vol. 61, no. SC, p. SC1040, feb 2022\. [Online]. Available: https://dx.doi.org/10.35848/1347-4065/ac4c07
  * [3] H. Mizuno, “Quantum computing from hype to game changer,” in _2023 IEEE Symposium on VLSI Technology and Circuits (VLSI Technology and Circuits)_. IEEE, 2023, pp. 1–4.
  * [4] T. Sekiguchi, N. Sato, T. Utsugi, N. Lee, A. Miyamoto, T. Tomaru, S. Tanaka, C. Yoshimura, R. Ukai, and H. Mizuno, “A computing architecture using shuttling-qubit for a Si qubit array,” in _Silicon Quantum Electronics Workshop (SiQEW) 2023)_ , 2023.
  * [5] J. M. Boter, J. P. Dehollain, J. P. van Dijk, Y. Xu, T. Hensgens, R. Versluis, H. W. Naus, J. S. Clarke, M. Veldhorst, F. Sebastiano, and L. M. Vandersypen, “Spiderweb array: A sparse spin-qubit array,” _Phys. Rev. Appl._ , vol. 18, p. 024053, Aug 2022. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevApplied.18.024053
  * [6] A. R. Mills, D. M. Zajac, M. J. Gullans, F. J. Schupp, T. M. Hazard, and J. R. Petta, “Shuttling a single charge across a one-dimensional array of silicon quantum dots,” _Nature Communications_ , vol. 10, no. 1, p. 1063, Mar 2019\. [Online]. Available: https://doi.org/10.1038/s41467-019-08970-z
  * [7] V. Langrock, J. A. Krzywda, N. Focke, I. Seidler, L. R. Schreiber, and Ł. Cywiński, “Blueprint of a scalable spin qubit shuttle device for coherent mid-range qubit transfer in disordered si/sige/sio 2,” _PRX Quantum_ , vol. 4, no. 2, p. 020305, 2023.
  * [8] R. Li, L. Petit, D. P. Franke, J. P. Dehollain, J. Helsen, M. Steudtner, N. K. Thomas, Z. R. Yoscovits, K. J. Singh, S. Wehner _et al._ , “A crossbar network for silicon quantum dot qubits,” _Science advances_ , vol. 4, no. 7, p. eaar3960, 2018.
  * [9] B. Buonacorsi, B. Shaw, and J. Baugh, “Simulated coherent electron shuttling in silicon quantum dots,” _Phys. Rev. B_ , vol. 102, p. 125406, Sep 2020\. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevB.102.125406
  * [10] A. Zwerver, S. Amitonov, S. De Snoo, M. Mądzik, M. Rimbach-Russ, A. Sammak, G. Scappucci, and L. Vandersypen, “Shuttling an electron spin through a silicon quantum dot array,” _PRX Quantum_ , vol. 4, no. 3, p. 030303, 2023.
  * [11] T. Fujita, T. A. Baart, C. Reichl, W. Wegscheider, and L. M. K. Vandersypen, “Coherent shuttle of electron-spin states,” _npj Quantum Information_ , vol. 3, no. 1, p. 22, Jun 2017. [Online]. Available: https://doi.org/10.1038/s41534-017-0024-4
  * [12] T. Nakajima, M. R. Delbecq, T. Otsuka, S. Amaha, J. Yoneda, A. Noiri, K. Takeda, G. Allison, A. Ludwig, A. D. Wieck, X. Hu, F. Nori, and S. Tarucha, “Coherent transfer of electron spin correlations assisted by dephasing noise,” _Nature Communications_ , vol. 9, no. 1, p. 2133, May 2018\. [Online]. Available: https://doi.org/10.1038/s41467-018-04544-7
  * [13] J. Yoneda, W. Huang, M. Feng, C. H. Yang, K. W. Chan, T. Tanttu, W. Gilbert, R. C. C. Leon, F. E. Hudson, K. M. Itoh, A. Morello, S. D. Bartlett, A. Laucht, A. Saraiva, and A. S. Dzurak, “Coherent spin qubit transport in silicon,” _Nature Communications_ , vol. 12, no. 1, p. 4114, Jul 2021. [Online]. Available: https://doi.org/10.1038/s41467-021-24371-7
  * [14] A. Noiri, K. Takeda, T. Nakajima, T. Kobayashi, A. Sammak, G. Scappucci, and S. Tarucha, “A shuttling-based two-qubit logic gate for linking distant silicon quantum processors,” _Nature Communications_ , vol. 13, no. 1, p. 5740, Sep 2022. [Online]. Available: https://doi.org/10.1038/s41467-022-33453-z
  * [15] S. G. Philips, M. T. Mądzik, S. V. Amitonov, S. L. de Snoo, M. Russ, N. Kalhor, C. Volk, W. I. Lawrie, D. Brousse, L. Tryputen _et al._ , “Universal control of a six-qubit quantum processor in silicon,” _Nature_ , vol. 609, no. 7929, pp. 919–924, 2022.
  * [16] I. Heinz and G. Burkard, “High-fidelity cnot gate for spin qubits with asymmetric driving using virtual gates,” _Physical Review B_ , vol. 105, no. 12, p. L121402, 2022.
  * [17] ——, “Crosstalk analysis for single-qubit and two-qubit gates in spin qubit arrays,” _Physical Review B_ , vol. 104, no. 4, p. 045420, 2021.
  * [18] ——, “Crosstalk analysis for simultaneously driven two-qubit gates in spin qubit arrays,” _Physical Review B_ , vol. 105, no. 8, p. 085414, 2022.
  * [19] T.-K. Hsiao, C. J. van Diepen, U. Mukhopadhyay, C. Reichl, W. Wegscheider, and L. M. Vandersypen, “Efficient orthogonal control of tunnel couplings in a quantum dot array,” _Physical Review Applied_ , vol. 13, no. 5, p. 054018, 2020.
  * [20] R. E. Throckmorton and S. D. Sarma, “Crosstalk-and charge-noise-induced multiqubit decoherence in exchange-coupled quantum dot spin qubit arrays,” _Physical Review B_ , vol. 105, no. 24, p. 245413, 2022.
  * [21] M. A. Nielsen and I. L. Chuang, _Quantum computation and quantum information_. Cambridge university press, 2010.
  * [22] H. Fan, V. Roychowdhury, and T. Szkopek, “Optimal two-qubit quantum circuits using exchange interactions,” _Physical Review A_ , vol. 72, no. 5, p. 052323, 2005.
  * [23] F. Martins, F. K. Malinowski, P. D. Nissen, E. Barnes, S. Fallahi, G. C. Gardner, M. J. Manfra, C. M. Marcus, and F. Kuemmeth, “Noise suppression using symmetric exchange gates in spin qubits,” _Physical review letters_ , vol. 116, no. 11, p. 116801, 2016.
  * [24] M. Reed, B. Maune, R. Andrews, M. Borselli, K. Eng, M. Jura, A. Kiselev, T. Ladd, S. Merkel, I. Milosavljevic _et al._ , “Reduced sensitivity to charge noise in semiconductor spin qubits via symmetric operation,” _Physical review letters_ , vol. 116, no. 11, p. 110402, 2016.
  * [25] T. Utsugi, N. Lee, R. Tsuchiya, T. Mine, R. Mizokuchi, J. Yoneda, T. Kodera, S. Saito, D. Hisamoto, and H. Mizuno, “Single-electron pump in a quantum dot array for silicon quantum computers,” _Japanese Journal of Applied Physics_ , vol. 62, no. SC, p. SC1020, 2023.
  * [26] A. Matsuo and S. Yamashita, “Changing the gate order for optimal lnn conversion,” in _Reversible Computation_ , A. De Vos and R. Wille, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 89–101.
  * [27] G. Li, Y. Ding, and Y. Xie, “Tackling the qubit mapping problem for nisq-era quantum devices,” in _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_ , ser. ASPLOS ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 1001–1014. [Online]. Available: https://doi.org/10.1145/3297858.3304023
  * [28] A. Bhattacharjee, C. Bandyopadhyay, R. Wille, R. Drechsler, and H. Rahaman, “A novel approach for nearest neighbor realization of 2d quantum circuits,” _2018 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)_ , pp. 305–310, 2018. [Online]. Available: https://api.semanticscholar.org/CorpusID:51985889
  * [29] A. Lye, R. Wille, and R. Drechsler, “Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits,” in _The 20th Asia and South Pacific Design Automation Conference_ , 2015, pp. 178–183.
  * [30] A. Botea, A. Kishimoto, and R. Marinescu, “On the complexity of quantum circuit compilation,” in _Symposium on Combinatorial Search_ , 2018. [Online]. Available: https://api.semanticscholar.org/CorpusID:51881867
  * [31] D. Maslov, S. M. Falconer, and M. Mosca, “Quantum circuit placement,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 27, no. 4, pp. 752–763, 2008.
  * [32] M. Y. Siraichi, V. F. d. Santos, C. Collange, and F. M. Q. Pereira, “Qubit allocation,” in _Proceedings of the 2018 International Symposium on Code Generation and Optimization_ , ser. CGO 2018. New York, NY, USA: Association for Computing Machinery, 2018, p. 113–125. [Online]. Available: https://doi.org/10.1145/3168822
  * [33] B. Tan and J. Cong, “Optimality study of existing quantum computing layout synthesis tools,” _IEEE Transactions on Computers_ , vol. 70, no. 09, pp. 1363–1373, sep 2021.
  * [34] A. Shafaei, M. Saeedi, and M. Pedram, “Qubit placement to minimize communication overhead in 2d quantum architectures,” in _2014 19th Asia and South Pacific Design Automation Conference (ASP-DAC)_ , 2014, pp. 495–500.
  * [35] R. Wille, O. Keszocze, M. Walter, P. Rohrs, A. Chattopadhyay, and R. Drechsler, “Look-ahead schemes for nearest neighbor optimization of 1d and 2d quantum circuits,” in _2016 21st Asia and South Pacific Design Automation Conference (ASP-DAC)_ , 2016, pp. 292–297.
  * [36] D. Bhattacharjee and A. Chattopadhyay, “Depth-optimal quantum circuit placement for arbitrary topologies,” 2017.
  * [37] C.-C. Lin, S. Sur-Kolay, and N. K. Jha, “Paqcs: Physical design-aware fault-tolerant quantum circuit synthesis,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 23, no. 7, pp. 1221–1234, 2015\.
  * [38] A. Farghadan and N. Mohammadzadeh, “Quantum circuit physical design flow for 2d nearest-neighbor architectures: Quantum circuit design flow,” _International Journal of Circuit Theory and Applications_ , vol. 45, 03 2017\.
  * [39] S. Sivarajah, S. Dilkes, A. Cowtan, W. Simmons, A. Edgington, and R. Duncan, “t|ket⟩: a retargetable compiler for nisq devices,” _Quantum Science and Technology_ , vol. 6, no. 1, p. 014003, nov 2020. [Online]. Available: https://dx.doi.org/10.1088/2058-9565/ab8e92
  * [40] A. Zulehner, A. Paler, and R. Wille, “An efficient methodology for mapping quantum circuits to the ibm qx architectures,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 38, no. 7, pp. 1226–1236, 2018.
  * [41] A. Cross, “The ibm q experience and qiskit open-source quantum computing software,” in _APS March meeting abstracts_ , vol. 2018, 2018, pp. L58–003.
  * [42] P. Zhu, Z. Guan, and X. Cheng, “A dynamic look-ahead heuristic for the qubit mapping problem of nisq computers,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 39, no. 12, pp. 4721–4735, 2020.
  * [43] P. Zhu, S. Feng, and Z. Guan, “An iterated local search methodology for the qubit mapping problem,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 41, no. 8, pp. 2587–2597, 2021.
  * [44] R. Wille, M. Saeedi, and R. Drechsler, “Synthesis of reversible functions beyond gate count and quantum cost,” _arXiv preprint arXiv:1004.4609_ , 2010\.
  * [45] A. Chakrabarti, S. Sur-Kolay, and A. Chaudhury, “Linear nearest neighbor synthesis of reversible circuits by graph partitioning,” _arXiv preprint arXiv:1112.0564_ , 2011.
  * [46] M. Saeedi, R. Wille, and R. Drechsler, “Synthesis of quantum circuits for linear nearest neighbor architectures,” _Quantum Information Processing_ , vol. 10, pp. 355–377, 2011.
  * [47] Y. Hirata, M. Nakanishi, S. Yamashita, and Y. Nakashima, “An efficient conversion of quantum circuits to a linear nearest neighbor architecture,” _Quantum Info. Comput._ , vol. 11, no. 1, p. 142–166, jan 2011.
  * [48] A. Shafaei, M. Saeedi, and M. Pedram, “Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures,” in _Proceedings of the 50th annual design automation conference_ , 2013, pp. 1–6.
  * [49] R. Wille, A. Lye, and R. Drechsler, “Optimal swap gate insertion for nearest neighbor quantum circuits,” in _2014 19th Asia and South Pacific Design Automation Conference (ASP-DAC)_. IEEE, 2014, pp. 489–494.
  * [50] M. M. Rahman and G. W. Dueck, “Synthesis of linear nearest neighbor quantum circuits,” _arXiv preprint arXiv:1508.05430_ , 2015.
  * [51] W. HATTORI and S. YAMASHITA, “Mapping a quantum circuit to 2d nearest neighbor architecture by changing the gate order,” _IEICE Transactions on Information and Systems_ , vol. E102.D, no. 11, pp. 2127–2134, 2019.
  * [52] A. Matsuo, S. Yamashita, and D. J. Egger, “A sat approach to the initial mapping problem in swap gate insertion for commuting gates,” _IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences_ , p. 2022EAP1159, 2023.
  * [53] Y. Li, W. Liu, M. Li, and Y. Li, “Quantum circuit compilation for nearest-neighbor architecture based on reinforcement learning,” _Quantum Information Processing_ , vol. 22, no. 8, p. 295, 2023.
  * [54] D. Ferrari, I. Tavernelli, and M. Amoretti, “Deterministic algorithms for compiling quantum circuits with recurrent patterns,” _Quantum Information Processing_ , vol. 20, no. 6, p. 213, Jun 2021. [Online]. Available: https://doi.org/10.1007/s11128-021-03150-9
  * [55] D. Große, R. Wille, G. W. Dueck, and R. Drechsler, “Exact synthesis of elementary quantum gate circuits for reversible functions with don’t cares,” in _38th International Symposium on Multiple Valued Logic (ismvl 2008)_ , 2008, pp. 214–219.
  * [56] S. Ashhab, N. Yamamoto, F. Yoshihara, and K. Semba, “Numerical analysis of quantum circuits for state preparation and unitary operator synthesis,” _Phys. Rev. A_ , vol. 106, p. 022426, Aug 2022. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.106.022426
  * [57] P. Murali, J. M. Baker, A. Javadi-Abhari, F. T. Chong, and M. Martonosi, “Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers,” in _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_ , ser. ASPLOS ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 1015–1029. [Online]. Available: https://doi.org/10.1145/3297858.3304075
  * [58] S. S. Tannu and M. K. Qureshi, “Not all qubits are created equal: A case for variability-aware policies for nisq-era quantum computers,” in _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_ , ser. ASPLOS ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 987–999. [Online]. Available: https://doi.org/10.1145/3297858.3304007
  * [59] T. LeCompte, F. Qi, X. Yuan, N.-F. Tzeng, M. H. Najafi, and L. Peng, “Machine-learning-based qubit allocation for error reduction in quantum circuits,” _IEEE Transactions on Quantum Engineering_ , vol. 4, pp. 1–14, 2023.
  * [60] P. Murali, D. C. Mckay, M. Martonosi, and A. Javadi-Abhari, “Software mitigation of crosstalk on noisy intermediate-scale quantum computers,” in _Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems_ , ser. ASPLOS ’20. New York, NY, USA: Association for Computing Machinery, 2020, p. 1001–1016. [Online]. Available: https://doi.org/10.1145/3373376.3378477
  * [61] Y. Ding, P. Gokhale, S. Lin, R. Rines, T. Propson, and F. T. Chong, “Systematic crosstalk mitigation for superconducting qubits via frequency-aware compilation,” in _2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. Los Alamitos, CA, USA: IEEE Computer Society, oct 2020, pp. 201–214.
  * [62] A. A. Saki, R. O. Topaloglu, and S. Ghosh, “Muzzle the shuttle: efficient compilation for multi-trap trapped-ion quantum computers,” in _2022 Design, Automation & Test in Europe Conference & Exhibition (DATE)_. IEEE, 2022, pp. 322–327.
  * [63] J. Durandau, J. Wagner, F. Mailhot, C.-A. Brunet, F. Schmidt-Kaler, U. Poschinger, and Y. Bérubé-Lauzière, “Automated Generation of Shuttling Sequences for a Linear Segmented Ion Trap Quantum Computer,” _Quantum_ , vol. 7, p. 1175, Nov. 2023. [Online]. Available: https://doi.org/10.22331/q-2023-11-08-1175
  * [64] M. Webber, S. Herbert, S. Weidt, and W. K. Hensinger, “Efficient qubit routing for a globally connected trapped ion quantum computer,” _Advanced Quantum Technologies_ , vol. 3, no. 8, p. 2000027, 2020. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/qute.202000027
  * [65] S. Brandhofer, I. Polian, and H. P. Büchler, “Optimal mapping for near-term quantum architectures based on rydberg atoms,” in _2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD)_. IEEE Press, 2021, p. 1–7. [Online]. Available: https://doi.org/10.1109/ICCAD51958.2021.9643490
  * [66] B. Tan, D. Bluvstein, M. D. Lukin, and J. Cong, “Qubit mapping for reconfigurable atom arrays,” in _Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design_ , ser. ICCAD ’22. New York, NY, USA: Association for Computing Machinery, 2022. [Online]. Available: https://doi.org/10.1145/3508352.3549331
  * [67] L. De Moura and N. Bjørner, “Z3: An efficient smt solver,” in _Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems_ , ser. TACAS’08/ETAPS’08. Berlin, Heidelberg: Springer-Verlag, 2008, p. 337–340.
  * [68] J. Preskill, “Quantum Computing in the NISQ era and beyond,” _Quantum_ , vol. 2, p. 79, Aug. 2018. [Online]. Available: https://doi.org/10.22331/q-2018-08-06-79

## Appendix

###  XI-A Definitions of predicates

$\displaystyle
SameCol_{i}(b_{j},b_{k})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$
$\displaystyle v_{r_{j},c_{j}}=pos_{i}(b_{j})\land
v_{r_{k},c_{k}}=pos_{i}(b_{k})\land c_{j}=c_{k}$ (36) $\displaystyle
SameRow_{i}(b_{j},b_{k})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$
$\displaystyle v_{r_{j},c_{j}}=pos_{i}(b_{j})\land
v_{r_{k},c_{k}}=pos_{i}(b_{k})\land r_{j}=r_{k}$ (37) $\displaystyle
AdjHor_{i}(b_{j},b_{k})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$
$\displaystyle v_{r_{j},c_{j}}=pos_{i}(b_{j})\land
v_{r_{k},c_{k}}=pos_{i}(b_{k})\land r_{j}=r_{k}$
$\displaystyle\land|c_{j}-c_{k}|=1\land(v_{r_{j},c_{j}},v_{r_{k},c_{k}})\in E$
(38) $\displaystyle
AdjVer_{i}(b_{j},b_{k})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$
$\displaystyle v_{r_{j},c_{j}}=pos_{i}(b_{j})\land
v_{r_{k},c_{k}}=pos_{i}(b_{k})\land c_{j}=c_{k}$
$\displaystyle\land|r_{j}-r_{k}|=1\land(v_{r_{j},c_{j}},v_{r_{k},c_{k}})\in E$
$\displaystyle\land R(v_{r_{j},c_{j}})\land R(v_{r_{k},c_{k}})$ (39)

$\displaystyle
BC(v_{r_{k1},c_{k1}},v_{r_{k2},c_{k2}})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$
$\displaystyle\left(R(v_{r_{k1},c_{k1}})\land\lnot R(v_{r_{k2},c_{k2}})\land
v_{r_{k2},c_{k2}}\notin P_{i}\right)$ $\displaystyle\lor\left(\lnot
R(v_{r_{k1},c_{k1}})\land R(v_{r_{k2},c_{k2}})\land v_{r_{k2},c_{k2}}\notin
P_{i}\right)$ (40)

$\displaystyle
Reachable(s_{a},s_{b})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\exists
p=[t_{1},...,t_{i},...,t_{n}]\cdot s_{a}=s_{b}$
$\displaystyle\lor\left(t_{1}=(s_{a},l_{a+1},s_{a+1})\land
t_{n}=(s_{b-1},l_{b},s_{b})\right)$ (41)

###  XI-B Exception Case of Transition for Measurements

If the target electron to be measured is in column 15, it can be moved to
column 16 directly by shuttling to the right. The transition in such an
exception case is shown in Fig. 39.

Figure 39: Transitions to execute a measurement in the exception case

The transition to return to a state in $RS$ is the same as the one shown in
Fig. 30.