# 2QAN: A quantum compiler for 2-local qubit Hamiltonian simulation algorithms

Lingling Lao, Dan E. Browne  Department of Physics and Astronomy, University
College London, London WC1E 6BT, United Kingdom

###### Abstract

Simulating quantum systems is one of the most important potential applications
of quantum computers. The high-level circuit defining the simulation needs to
be compiled into one that complies with hardware limitations such as qubit
architecture (connectivity) and instruction (gate) set. General-purpose
quantum compilers work at the gate level and have little knowledge of the
mathematical properties of quantum applications, missing further optimization
opportunities. Existing application-specific compilers only apply advanced
optimizations in the scheduling procedure and are restricted to the CNOT or CZ
gate set. In this work, we develop a compiler, named 2QAN, to optimize quantum
circuits for 2-local qubit Hamiltonian simulation problems, a framework which
includes the important quantum approximate optimization algorithm (QAOA). In
particular, we exploit the flexibility of permuting different operators in the
Hamiltonian (no matter whether they commute) and propose permutation-aware
techniques for qubit routing, gate optimization and scheduling to minimize
compilation overhead. 2QAN can target different qubit topologies and different
hardware gate sets. Compilation results on four applications (up to 50 qubits)
and three quantum computers (namely, Google Sycamore, IBMQ Montreal and
Rigetti Aspen) show that 2QAN outperforms state-of-the-art general-purpose
compilers and application-specific compilers. Specifically, 2QAN can reduce
the number of inserted SWAP gates by 11.5X, reduce overhead in hardware gate
count by 68.5X, and reduce overhead in circuit depth by 21X. Experimental
results on the Montreal device demonstrate that benchmarks compiled by 2QAN
achieve the highest fidelity.

##  I Introduction

Quantum simulation has broad applications in quantum many-body physics [1],
quantum chemistry [2], and quantum field theory [3] and has been demonstrated
in different quantum technologies [4, 5] (see [6] for a detailed review). The
problem of Hamiltonian simulation can grow exponentially with respect to the
system size, becoming intractable by classical computers for large systems.
Quantum computers can be used to efficiently solve this problem, as first
proposed by Richard Feynman [7]. The main challenge is to find an efficient
circuit that asymptotically approximates the time evolution of a Hamiltonian.
Different approaches have been proposed for efficient Hamiltonian simulation,
including product formulas [8, 9, 10], Taylor series [11], quantum walk [12],
and quantum signal processing [13]. The product formula has a straightforward
implementation and good performance in practice [14, 15]. Given a Hamiltonian
that is decomposed as a sum of Hermitian terms ($H=\sum_{j=1}^{L}h_{j}H_{j}$),
the product formula approximates the exponential of this Hamiltonian as a
product of exponentials of individual terms and each individual exponential
can be efficiently implemented by a quantum circuit. The approximation errors
are caused by the anti-commuting terms in the Hamiltonian. To achieve a
desired precision, the product is divided into many repetitions of small time
steps, the circuit therefore has a periodic structure.

This high-level circuit representation is typically hardware-agnostic and
needs to be decomposed into the instruction set supported by the underlying
quantum hardware. In noisy intermediate-scale quantum (NISQ) computers [16],
the universal instruction set is normally composed of arbitrary single-qubit
rotations and one or a few two-qubit gates (e.g., the SYC, CNOT, iSWAP gates
in quantum processors from Google, IBM, Rigetti respectively in Figure 1).
Furthermore, these quantum computers only allow two-qubit gates on restricted
qubit pairs, i.e., limited qubit connectivity. Compilation techniques are
required to map circuit qubits onto hardware qubits and insert SWAP gates to
move qubits to be neighbours, increasing circuit size in terms of gate count
and circuit depth. Two-qubit gates have much higher error rates than single-
qubit rotations and qubits have short coherence time [17]. Therefore, it is
critical to minimize compilation overhead for high-fidelity circuit
implementation.

(a) Google Sycamore (54 qubits) [17]

(b) IBM Montreal (27 qubits) [18]

(c) Rigetti Aspen (16 qubits) [19]

Figure 1: Device topologies and hardware two-qubit gates of different quantum
computers. Nodes represent qubits and edges represent the connectivity between
qubit pairs. All three devices allow arbitrary single-qubit rotations. Figure
2: Overview of the 2QAN compiler. The highlighted compilation passes exploit
the application-level semantics and cannot be replaced by general-purpose
compilation techniques. Other passes are implemented by existing tools.

Many approaches have been proposed for compiling quantum circuits onto NISQ
computers [20, 21, 22, 23, 24, 25, 26, 27]. These compilers operate at the
gate level and are designed for general circuits with little knowledge
regarding the mathematical properties of target applications. Exploiting the
synergy between applications and compilation techniques can provide more
optimizations on the implementation circuit, which will further improve
application performance. For the quantum simulation problems, one application-
specific property is the flexible ordering of different terms in the
Hamiltonian. That is, one could permute the exponentials of these terms
without losing computational accuracy. This is, however, difficult or even
impossible to be recognized at the gate level, especially when many of these
operators anti-commute with each other (changing the order of anti-commuting
gates violates program semantics). Several application-specific compilers have
also been developed [28, 29, 30, 31, 32, 33, 34, 35, 36], but their
optimization techniques are performed on one particular compilation pass and
are limited to the CNOT or CZ gate set.

In this work, we identify the flexibility in Hamiltonian operator permutation
and exploit it in the circuit compilation procedure. In particular, we propose
permutation-aware qubit routing, gate scheduling, and gate optimization
techniques to efficiently compile circuits for 2-local qubit Hamiltonian
simulation problems. The quantum approximate optimization algorithm (QAOA)
[37] also has Hamiltonians in this form. The developed compiler, named
2QAN111Pronounced ”toucan”. We propose the name 2QAN since this compiler
targets 2-local Qubit Hamiltonian simulation, is hardware Adapted and designed
for NISQ quantum devices., can target different qubit topologies and different
gate sets. Evaluation results on three quantum computers show that 2QAN can
significantly reduce gate count and circuit depth compared to state-of-the-art
quantum compilers. Furthermore, we also experimentally demonstrate the
advantages of 2QAN on the IBMQ Montreal device. The evaluation toolflow is
presented in Figure 2.

The main contributions of this work are:

  * •

We discover an optimization opportunity for compiling quantum simulation
problems on NISQ computers, that is, the order of different terms in a
Hamiltonian is flexible and a quantum compiler can permute their exponentials
(operators in the product formula) to minimize compilation overhead.

  * •

We exploit this flexibility and develop 2QAN, a quantum compiler for
efficiently compiling 2-local qubit Hamiltonian simulation problems on NISQ
computers. We first propose a permutation-aware qubit routing heuristic to
minimize the number of inserted SWAP gates. Then we implement a unitary
unifying pass that combines a SWAP gate with a circuit gate to further reduce
gate overhead. Moreover, we design a permutation-aware gate scheduling
technique to minimize circuit depth. The routing and scheduling algorithms
have quadratic time complexity in the number of gates and is scalable for
large systems.

  * •

We perform all the proposed permutation-aware compilation passes prior to the
gate decomposition pass as shown in Figure 2. That is, these optimization
algorithms are independent of the underlying hardware two-qubit gates,
allowing 2QAN to target different instruction sets.

  * •

We evaluate the proposed compiler by compiling the Heisenberg model, XY model,
Ising model, and the QAOA circuits onto three industrial quantum computers,
Google Sycamore [17], IBMQ Montreal [18], Rigetti Aspen [19]. Across all
benchmarks and quantum computers, the 2QAN compiler outperforms state-of-the-
art quantum compilers, including the general-purpose compilers
t$\ket{\textup{ket}}$ [26] and Qiskit [27], and the application-specific
compilers, Paulihedral [36] and the QAOA compiler [32, 33, 34]. For example,
2QAN can reduce the SWAP count, two-qubit gate overhead, and depth overhead by
on average 3.6x (9.1x), 4x (10.4x), and 2.1x (3.4x), respectively compared to
t$\ket{\textup{ket}}$ (Qiskit). Furthermore, experimental results of running
QAOA on the IBMQ Montreal device show that this substantial compilation
overhead reduction provides significant improvement in application
performance. 2QAN achieves the highest fidelity for all problem sizes and can
increase the QAOA layers while the other compilers cannot.

##  II Background

###  II-A Quantum simulation

Product formula: Consider a system Hamiltonian $H$ that is decomposed into a
sum of polynomially many Hermitian terms $H_{j}$,
$H=\sum_{j=1}^{L}h_{j}H_{j}$, its time evolution can be described by the
unitary $U=\textup{exp}(it\sum_{j=1}^{L}h_{j}H_{j})$. The goal is to find an
efficient circuit construction for this unitary. One of the leading approaches
is the product formula or the Trotter formula [8, 9, 10],

$V(t)=\prod_{j=1}^{L}\textup{exp}(ith_{j}H_{j})$ (1)

and each individual operator $V_{j}(t)=\textup{exp}(ith_{j}H_{j})$ can be
efficiently implemented by a quantum circuit. $V(t)=U$ if all the terms
commute (i.e., $H_{j}H_{k}=H_{k}H_{j}$). $(V(t/r))^{r}$ approximates $U$ for
large $r$ if some terms do not commute (which is typically the case in natural
physical systems). This algorithm is referred as the first-order
approximation. $V(t/r)$ is called one Trotterization step and the circuit has
$r$ such repetitions. Reducing $r$ will help save the simulation cost
substantially. For example, the second-order approximation

$V_{2}(t)=\prod_{j=1}^{L}\textup{exp}(ith_{j}H_{j}/2)\prod_{j=L}^{1}\textup{exp}(ith_{j}H_{j}/2)$
(2)

can reduce $r$ from $O((tL\Lambda)^{2}/\epsilon)$ (first-order) to
$O((tL\Lambda)^{1+\frac{1}{2}}/\epsilon^{\frac{1}{2}})$ [10]. $\Lambda$ is the
magnitude of the strongest term and $\epsilon$ is the desired error threshold.

Operator permutation: We note that the order of terms in the Hamiltonian can
be chosen from any of the $L!$ permutations. This flexibility allows one to
optimize the Hamiltonian simulation circuit for each Trotter step by
rearranging the $L$ individual operators ($V_{j}(t/r)$) in the product
formula. Optimizing each Trotter step will improve the overall circuit
construction since a large number ($r$) of such repetitions need to be
performed, which will be the focus of this work. Such rearrangement is not
trivial for general-purpose quantum compilers because some of the operators
anti-commute (e.g.,
$\textup{exp}(itX_{1}X_{2})\textup{exp}(itY_{2}Y_{3})\neq\textup{exp}(itY_{2}Y_{3})\textup{exp}(itX_{1}X_{2})$)
and reordering them at the gate level will cause logic violations in the
compilation.

2-local qubit Hamiltonian: In this work we consider 2-local qubit Hamiltonians
that originate in many physical systems,

$H=\sum_{(u,v)\in E}H_{uv}+\sum_{k\in V}H_{k}.$ (3)

$H_{uv}$ are two-qubit Hamiltonian terms and $H_{k}$ are single-qubit
Hamiltonians. The interaction graph of this Hamiltonian is represented by
$G(V,E)$, $V$ is the set of qubits and $E$ is the set of edges. The transverse
Ising model, XY model, and Heisenberg model all have Hamiltonians in this
form,

$H_{\textup{Ising}}=\sum_{(u,v)\in E}\gamma_{uv}Z_{u}Z_{v}+\sum_{k\in
V}\beta_{k}X_{k},$ (4) $H_{\textup{XY}}=\sum_{(u,v)\in
E}(\alpha_{uv}X_{u}X_{v}+\beta_{uv}Y_{u}Y_{v}),$ (5)
$H_{\textup{Heisenberg}}=\sum_{(u,v)\in
E}(\alpha_{uv}X_{u}X_{v}+\beta_{uv}Y_{u}Y_{v}+\gamma_{uv}Z_{u}Z_{v}),$ (6)

where $X,Y,Z$ are the Pauli operators. The computational complexity of
computing important properties such as their ground state energy depends on
the problem graph. Barahona [38] showed that computing the ground state energy
of a three-dimensional Ising lattice is NP-hard, whereas polynomial classical
algorithms are known for the two-dimensional Ising model in the absence of a
magnetic field [39]. Cubitt and Montanaro [40] proved the QMA-completeness of
the Heisenberg model and the XY model (QMA is the quantum analogue of NP
[41]).

(a) Problem circuit

(b) Generic compiler

(c) Application-specific compiler

Figure 3: Examples of compiling a 6-qubit 2-local Hamiltonian (Equation 3) to
a $2\times 3$ grid architecture. (a) The circuit construction of one Trotter
step, where the two(single)-qubit operators implement the evolution of
two(single)-qubit Hamiltonians. These two-qubit operators may not commute.
(b-c) Compilation procedure. Top figures show the compiled circuits and bottom
figures show the qubit mappings (nodes are qubits and edges represent their
connectivity). Gates between dashed lines can be performed in parallel. To
avoid confusion, SWAPs in this Figure are applied on the corresponding
hardware qubits, we draw them on the circuit qubits for better readability.
(b) Compilation procedure using a generic compiler that obeys the gate
dependencies in (a). In total, the compiled circuit has 12 two-qubit gates and
a depth of 7. (c) Compilation procedure by using 2QAN compiler that exploits
the flexible operator ordering in Hamiltonian simulation problems. In total,
the compiled circuit has 9 two-qubit gates and a depth of 5 (Each of inserted
SWAPs can be merged with a circuit unitary in gray area).

###  II-B Circuit compilation

NISQ computers have hardware limitations such as native gate set and qubit
connectivity, making quantum applications not directly executable. A hardware
gate set is typically composed of arbitrary single-qubit rotations and a few
two-qubit gates which vary across QC vendors. For example, IBM devices
currently have the CNOT as the native two-qubit gate [18], Rigetti implement
both CZ and iSWAP gates [19, 42], and Google support CZ, SYC,
$\sqrt{\textup{iSWAP}}$ gates [17, 43]. High-level quantum circuits need to be
decomposed into the given gate set by using analytical algorithms [44, 45] or
numerical approaches [46, 47]. Furthermore, two-qubit gates can only be
executed on the connected (nearest neighbouring, NN) qubits. Movement
operations such as SWAP gates need to be inserted for performing non-NN gates,
increasing the number of gates and circuit depth. NISQ computers have limited
qubit coherence time and high gate error rates. It is crucial to minimize
circuit sizes for reliable implementation of quantum applications. To this
purpose, quantum compilation techniques, including qubit mapping and routing,
gate decomposition and scheduling, have been developed to efficiently
transform high-level quantum circuits into hardware-compatible ones. For
general quantum circuits, the routing and scheduling algorithms assign
dependencies between gates to maintain the correctness of program semantics
[20, 21, 22, 23, 24, 25, 26, 27]. These dependencies are typically generated
based on the gate order in an input circuit. These general-purpose quantum
compilers work at the gate level and do not consider application-level
semantics. Any application-specific optimizations that can improve application
performance are desirable for NISQ computing.

Compilation for Hamiltonian simulation: As mentioned previously, when
constructing a circuit for each Trotter step, one is free to use any
permutation of the operators in the product formula (even they do not
commute). Such application-level property allows more optimizations for
Hamiltonian simulation problems but is not exploited by general-purpose
quantum compilers. Figure 3 shows an example of compiling a 6-qubit
Hamiltonian circuit to a $2\times 3$ grid architecture. A generic compiler
inserts 3 SWAP gates and outputs a 7-depth circuit with 12 two-qubit gates. In
contrast, a compiler that considers the flexibility in operator permutation
only uses 2 SWAPs. Moreover, these SWAP gates can be combined with other gates
in the circuit, further decreasing the gate count and circuit depth (the
compiled circuit only has 9 two-qubit gates and depth 5). In this work, we
design such an application-specific compiler for 2-local qubit Hamiltonian
simulation problems to improve application fidelity.

##  III Compilation techniques

In this section, we introduce the proposed compilation techniques for quantum
simulation. Figure 2 shows the overview of our 2QAN compiler.

###  III-A Qubit mapping

The goal of qubit mapping is to find an optimal qubit initial placement such
that the number of qubit moving operations required for implementing all two-
qubit gates is minimized. Similar to the approaches in [48, 49, 50], the qubit
mapping problem is formulated as a quadratic assignment problem (QAP). That
is, the problem of allocating each qubit in the circuit (facility) to one
qubit in the device (location) with the cost defined by a function of the
distance and interaction times (flow) between circuit qubits. Let $n$ be the
number of circuit qubits or physical qubits and denote by the set
$N=\\{1,2,\cdots,n\\}$. The objective function is

$\min_{\phi\in\mathit{S}_{n}}\sum_{i=1}^{n}\sum_{j=1}^{n}f_{ij}d_{\phi(i)\phi(j)}$
(7)

where $\mathit{S}_{n}$ is the set of all permutations $\phi$: $N\rightarrow
N$, $f_{ij}$ is the interaction times between circuit qubits $i$ and $j$,
$d_{\phi(i)\phi(j)}$ is the distance between hardware qubits $\phi(i)$ and
$\phi(j)$ and is calculated by using the Floyd-Warshall algorithm.

QAP is a NP-hard problem [51] and we use the Tabu search heuristic algorithm
[52, 53] to efficiently find good qubit mappings in this work. Other
heuristics such as simulated annealing [54] and greedy randomized adaptive
search procedure [55] can be also used for solving this problem. Prior works
observed that the QAP formulation of qubit mapping may not work well for
general quantum circuits [48, 49, 50]. This is because qubits need to interact
in a specific order (gate dependency) and the initial mapping benefits
diminish after insertion of SWAPs, e.g., some NN qubits may be moved further
apart but will interact later. This is not the case for 2-local Hamiltonian
simulation problems as any operator that is NN in a qubit map can be scheduled
directly regardless of their order in the circuit (see examples in Figure 3).

###  III-B Qubit routing

Generally, not all two-qubit gates are nearest neighbouring in an initial
qubit map. Movement operations such as SWAP gates need to be inserted to move
non-NN qubits, causing overheads in gate count and circuit depth. Efficient
qubit routing techniques are required to minimize compilation overhead for
reliable computation. Different from existing qubit routing algorithms that
respect the gate order in the input circuit [21, 24, 56, 57], the routing in
2QAN exploits the operator permutation flexibility in a Hamiltonian. The
pseudocode is in Algorithm 1 and an example is shown in Figure 3c.

Given an input circuit that implements one Trotter step of a Hamiltonian, our
routing algorithm starts by searching all the two-qubit gates that are NN in
an initial qubit layout found by the mapping algorithm (e.g., there are 7 NN
two-qubit gates in Figure 3c). These gates are directly mapped and SWAP gates
are needed to perform the remaining two-qubit gates (Lines 2-3). For these
non-NN gates, it compares their qubit distances in the hardware (the distance
matrix in Equation 7) and selects the shortest-distance one to route (Line 5).
If there are multiple shortest ones, select the first one in this set. Then
the routing algorithm finds all possible SWAP gates that act on one of the
qubits of the chosen gate $g$ (Line 6) It evaluates these SWAPs based on a
SWAP selection criteria (will be explained shortly) and selects the best one
as the first SWAP for gate $g$ (Line 7). The qubit map is updated and NN gates
are found for the new map and are removed from the un-routed gate set (Lines
8-10). This procedure (Lines 5-10) is repeated until all two-qubit gates are
performed. The time complexity of the routing algorithm is $O(m^{2}n)$, $m$ is
the number of two-qubit gates and $n$ is the number of qubits.

1:Un-routed circuit, initial map $\phi_{0}$, device topology

2:Routed circuit, a set of qubit maps $\\{\phi_{i}\\}$ and a set of NN gates
corresponding to each map $\\{G_{\phi_{i}}\\}$

3:Initialize the set of qubit maps $\Phi=\\{\phi_{0}\\}$

4:Initialize the set of NN gates for each map,
$G=\\{G_{\phi_{0}}\\},G_{\phi_{0}}\leftarrow$ all NN two-qubit gates for map
$\phi_{0}$

5:Initialize $G_{\textup{ur}}\leftarrow$ all un-routed (non-NN) two-qubit
gates

6:while $G_{\textup{ur}}\neq\varnothing$ do

7: Select the gate $g$ $\in G_{\textup{ur}}$ that has shortest distance in
$\phi_{i}$

8: $S_{g}\leftarrow$ Find all SWAP gates on qubits in $g$

9: Select the best SWAP from $S_{g}$ and add it to $G_{\phi_{i}}$

10: Update qubit map from $\phi_{i}$ to $\phi_{i+1}$

11: $G_{\phi_{i+1}}\leftarrow$Find NN gates in $G_{\textup{ur}}$ for map
$\phi_{i+1}$

12: Remove all gates in $G_{\phi_{i+1}}$ from $G_{\textup{ur}}$, add
$G_{\phi_{i+1}}$ to $G$, add $\phi_{i+1}$ to $\Phi$

13:end while

Algorithm 1 Permutation-aware routing

SWAP selection criteria: The best SWAP gate is evaluated based on three
criteria:

  1. 1.

Least SWAP count: It will lead to the minimal cost in Equation 7 (i.e., the
minimal number of SWAP gates) for remaining non-NN gates.

  2. 2.

Shortest circuit depth: It can be most interleaved with previously mapped
gates, introducing the least depth overhead.

  3. 3.

Best gate optimization: It can be merged with a circuit gate, i.e., if there
is a circuit gate applied on the same qubits as this SWAP, the compiler will
replace these two gates by a single unitary representing their product (more
details will be introduced in the next section).

For our compiler configuration, we will evaluate the best SWAP based on the
three criteria in the above priority order. Evaluating these criteria in a
different order may further improve the compiler but will not be explored
here. When there are multiple best options, a random one will be chosen. For
example, both SWAP (0,3) and SWAP (2,3) in map $\phi_{0}$ of Figure 3c can be
added for performing the two-qubit gate on pair (0,2) and they have the same
cost regarding the first two criteria. SWAP (2,3) is selected because it can
be combined with a circuit gate that operate on the same qubits. For
implementing the circuit gate on (4,5), both SWAP (1,5) and SWAP (1,4) are the
best, and the compiler randomly selects one.

###  III-C Unitary unifying

Figure 4: Unitary unifying example. The flexible operator permutation allows
the circuit gate on qubits (0,2) to be rescheduled and combined with the SWAP
gate. Figure 5: Examples of decomposing the SWAP, the unitary
$\textup{exp}(i\theta ZZ)$, and their product into CNOTs and single-qubit
rotations.

SWAP unitary unifying: For each added SWAP gate, the compiler searches over
all circuit gates. If there is a circuit gate operating on the same qubit pair
as this SWAP, the compiler reschedules the circuit gate to the SWAP gate cycle
and unifies them into a single unitary (see the example in Figure 4). Such
rescheduling is allowed because of the operator permutation flexibility in
Hamiltonian simulation. The unified unitary (referred as dressed SWAP) is the
product of the circuit gate unitary and the SWAP unitary. This unitary
unifying helps further reduce compilation overhead. Figure 5 shows the
decomposition of a SWAP gate, a circuit gate $\textup{exp}(i\theta ZZ)$, and
their unified unitary into CNOT gates and single-qubit rotations. The unified
unitary requires 3 CNOTs while the implementation of these two gates with
individual decomposition (in the left circuit in Figure 4) would require 5
CNOTs in total.

Circuit unitary unifying: Similarly, we merge all circuit gates that act on
the same qubit pair into one single unitary. For example, there are three two-
qubit Pauli terms on one qubit pair in the Heisenberg model (Equation 6). The
exponential of a two-qubit Pauli operator normally requires 2 CNOTs.
Implementing each of these three exponentials individually would use 6 CNOTs
in total [36] while the unified unitary only requires 3 CNOTs (Any two-qubit
gate can be implemented by at most 3 CNOTs [58, 59]). To reduce gate count, we
pro-process all 2-local Hamiltonian simulation circuits by using this circuit
unitary unifying prior to other compilation passes (not shown in Figure 2).

###  III-D Gate scheduling

Scheduling without dependency: When connectivity limitations are not
considered, the individual operators in one Trotter step (Equation 1) can be
performed in any order. Graph coloring algorithms [60] can be used to schedule
such circuits. In the graph construction, nodes represent operators (gates),
and two nodes are connected by an edge if they have common qubits and cannot
be scheduled in parallel. We use the default greedy algorithm in NetworkX
version 2.5 for our scheduling pass. The circuits without taking into account
topology constraints are scheduled by this method and are baseline circuits
used for calculating compilation overhead.

Scheduling with dependency: For connectivity-constrained quantum computers,
the routing pass in previous section will be applied. The router outputs a
list of qubit maps and a set of NN gates corresponding to each map, including
both circuit gates and (dressed) SWAP gates. The order of a (dressed) SWAP
gate and a circuit gate cannot be exchanged if the SWAP is inserted to make
the circuit gate NN. One can generate a gate dependency graph based on the
gate order after qubit routing and apply conventional scheduling algorithms
[21, 22] to minimize circuit depth (decoherence limit). This approach may
perform sufficiently well for some circuits such as the one in Figure 3c, but
more optimizations can be achieved for other circuits by considering the
operator permutation in Hamiltonian simulation. In this work, we apply such
application-specific optimizations and the pseudocode of the proposed gate
scheduling algorithm is presented in Algorithm 2 and an example is shown in
Figure 6.

1:The set of maps $\Phi=\\{\phi_{i}\\}$ and the set of NN gates corresponding
to each map $G=\\{G_{\phi_{i}}\\}$

2:Scheduled circuit

3:Use graph coloring algorithm to schedule gates in $G_{\phi_{0}}$

4:Initialize scheduling cycle $t=0$ and the set of scheduled gates in this
cycle $C_{t}=\varnothing$

5:Initialize qubit map for cycle $t$: $M_{t}\leftarrow$ last map in $\Phi$
(for an ALAP scheduling)

6:$G_{\textup{us}}\leftarrow$ All un-scheduled gates $\in G$

7:while $G_{\textup{us}}\neq\varnothing$ do

8: for each circuit gate $g\in G_{\textup{us}}$ do

9: Schedule $g$ in $C_{t}$ iff it is NN in $M_{t}$ and its qubits are free

10: end for

11: for each SWAP gate $\in G_{\textup{us}}$ do

12: Schedule it in $C_{t}$ iff it is NN in $M_{t}$, its qubits are free, and
there is no dependency violation

13: $M_{t+1}\leftarrow$ the map after applying this SWAP on $M_{t}$

14: end for

15: $t\leftarrow t+1$ and update $G_{\textup{us}}$

16:end while

17:Reverse the gate sequence in $\\{C_{0},\cdots,C_{t}\\}$ (ALAP)

Algorithm 2 Permutation-aware scheduling

(a) Generic scheduler

(b) Hybrid scheduler

Figure 6: ALAP scheduling examples. (a) A generic scheduler respects the gate
order provided by the routing pass. The scheduled circuit takes 4 cycles. (b)
The hybrid scheduler considers the flexibility of permuting circuit gates and
respects the dependency between a SWAP gate and its corresponding circuit
gates. The scheduled circuit takes 3 cycles.

Hybrid scheduling: Algorithm 2 is a hybrid of the above two scheduling
techniques. The flexible operator permutation property implies that circuit
gates can be scheduled in any qubit map where they are NN. The NN circuit
gates in the initial qubit map do not have dependencies and are first
scheduled using the graph coloring algorithm (Line 1). For other qubit maps,
dependencies between SWAP and circuit gates need to be respected. The
algorithm initializes the circuit cycle $t=0$. We implement an as-late-as-
possible (ALAP) schedule in this work so the algorithm assigns the last qubit
map to cycle 0 ($M_{0}$, Line 2). For cycle $t$, it first finds all circuit
gates that can be scheduled (Lines 6-8). A circuit gate can be scheduled at
$t$ only if its qubits are NN in map $M_{t}$ and these qubits are not
currently occupied by any other gates. For example, the gate on (1,3) in
Figure 6b is scheduled at cycle 0 while it needs to be scheduled at a
different cycle in Figure 6a because of the dependency constraint when using a
generic scheduler (which can schedule it until its predecessor gate on (1,5)
is performed). Afterwards, the scheduler finds all SWAP gates that can be
scheduled at this cycle (Lines 9-12). Except the qubit NN and availability
requirements, a SWAP gate can be scheduled at $t$ only if the circuit gates
that depends on it have been scheduled (e.g., red gates depend on the two
SWAPs in Figure 6b). Once a SWAP is inserted, the qubit map for next cycle
will be updated. The procedure in Lines 6-13 is repeated until all gates are
scheduled. Finally, the algorithm reverses the scheduled gate sequence (Line
15). The time complexity of this hybrid scheduling algorithm scales
quadratically with the number of gates.

##  IV Experimental setup

Benchmarks: We consider the Hamiltonians in a linear array with nearest
neighbouring (NN) and next nearest neighbouring (NNN) interactions for the
transverse Ising model, XY model, and Heisenberg model, they are noted as NNN
Ising, NNN XY, and NNN Heisenberg. The time evolution of a Hamiltonian is
implemented by using the product formula
$(\prod_{j=1}^{L}\textup{exp}(ih_{j}H_{j}t/r))^{r}$, $r$ is the number of
Trotter steps. The coefficients of $H_{j}$ are randomly sampled from
$(0,\pi)$. The number of two-qubit operators for NNN Ising, NNN XY, and NNN
Heisenberg models in each Trotter step is $2n-3$, $n$ is the number of qubits
ranging from 6 to 50 in our evaluation.

In addition, we also use QAOA [37] for solving the MAX-CUT problems on
3-regular graphs (QAOA-REG-3) as our benchmark. QAOA is a popular benchmark
for testing the performance of quantum computers and has been demonstrated in
different quantum processors [61, 62]. In particular, the connectivity differs
for each problem graph, which is well suited for evaluating compilation
techniques. QAOA has the same form as the Ising model, its problem Hamiltonian
is $C=\sum_{(u,v)\in E}Z_{u}Z_{v}$ and drive Hamiltonian is $B=\sum_{k\in
V}X_{k}$. The circuit implementation of one-layer QAOA is

$U(\gamma,\beta)=\prod_{(u,v)\in E}\textup{exp}(i\gamma Z_{u}Z_{v})\prod_{k\in
V}\textup{exp}(i\beta X_{k}),$ (8)

Different from Hamiltonian simulation, these parameters ($\gamma,\beta$)
differ in every layer. In our evaluation, we randomly sample 10 graph
instances for each problem size. The operator parameters for each instance are
chosen at their theoretically optimal values and are calculated by using tools
provided in ReCirq [63]. The number of two-qubit operators in one-layer QAOA-
REG-3 is $3n/2$, we consider qubit numbers $n$ from 4 to 22.

Quantum computers: We compile these benchmarks onto three quantum computers,
Google Sycamore [17], IBMQ Montreal [18], Rigetti Aspen [19]. As shown in
Figure 1, Sycamore has a grid architecture with SYC as hardware two-qubit
gate, Montreal has a dodecagon lattice with CNOT as native gate, Aspen has
connected octagons and iSWAP as native gate. All three devices support
arbitrary single-qubit rotations. Experiments on Montreal were performed on
29th October, 2021, the average CNOT error rate was 1.241%, average read-out
error rate was 1.832%, and average T1=87.75 $us$ and T2=72.65 $us$.

Quantum compilers: We first compare our 2QAN compiler with two state-of-the-
art general-purpose compilers, the t$\ket{\textup{ket}}$ compiler version
0.11.0 with the recommended ‘FullPass’ [26] and the Qiskit compiler version
0.26.2 with optimization level 3 [27]. We then compare 2QAN with two
application-specific compilers, the QAOA compiler (IC-QAOA) with default
settings [32, 33, 34] and the Paulihedral compiler for quantum simulation
[36]. For circuits with larger number of qubits, the default mapping in
t$\ket{\textup{ket}}$ may fail to find a qubit initial placement and we use
their ‘LinePlacement’ pass instead. t$\ket{\textup{ket}}$ and Qiskit have
advanced circuit optimizations for the CNOT or CZ gates. For devices that have
different hardware two-qubit gates, we disable the gate decomposition pass in
Qiskit and t$\ket{\textup{ket}}$. The 2QAN compiler always performs
permutation-aware passes prior to gate decomposition. The mapped circuits that
have application-level unitaries will need to be decomposed into hardware gate
sets. We apply the ‘SynthesiseIBM’ decomposition pass in t$\ket{\textup{ket}}$
to decompose the mapped circuits by 2QAN for the Montreal device. We use the
analytical method in Cirq [64] to decompose QAOA and Ising unitaries into SYC
gates. For other application unitaries and hardware gates, we use the
numerical approach developed in [47] for finding more efficient decomposition.
Both Qiskit and 2QAN involve randomization in the mapping procedure, we run
their mapping passes 5 times and choose the best results. We also pro-process
the input circuits for t$\ket{\textup{ket}}$ and Qiskit by applying the
circuit unitary unifying in Section III-C to reduce compilation overhead.

Metrics: Similar to prior works, we use the number of inserted SWAP gates
(smaller is better), the number of hardware two-qubit gates (smaller is
better), the depth of two-qubit gates (shorter is better), and the depth of
all gates (shorter is better) as metrics to compare the performance of
different compilers. We also calculate the increase in gate count and circuit
depth (i.e., compilation overhead, less is better) compared to the circuits
without considering connectivity constraints (i.e., the baseline
implementation). Furthermore, we experimentally evaluate the application
performance of QAOA benchmarks on the Montreal device. The performance is
measured by the normalized cost function $\left\langle
C\right\rangle/C_{\textup{min}}$ (larger is better) [62]. 1 means the perfect
result and 0 corresponds to the random guessing result.

Implementation: We implement 2QAN in Python 3.8. All compilation in our
evaluation was performed on a laptop with an Intel Core i7 processor (2.30GHz
and 32GB RAM).

##  V Compiler evaluation

(a) SWAP count for NNN Heisenberg model

(b) SYC count for NNN Heisenberg model

(c) SYC depth for NNN Heisenberg model

(d) SWAP count for NNN XY model

(e) SYC count for NNN XY model

(f) SYC depth for NNN XY model

(g) SWAP count for NNN Ising model

(h) SYC count for NNN Ising model

(i) SYC depth for NNN Ising model

(j) SWAP count for QAOA-REG-3

(k) SYC count for QAOA-REG-3

(l) SYC depth for QAOA-REG-3

Figure 7: Compilation results of the one-layer NNN Heisenberg model, NNN XY,
NNN Ising model, and QAOA-REG-3 on the Google Sycamore device. Each QAOA
problem size is averaged over 10 different instances (error bars show the
standard deviation) and operator parameters of QAOA circuits were chosen at
their theoretically optimal values. ‘2QAN dressed’ shows the number of SWAPs
that were merged with circuit gates by 2QAN, which helps to reduce hardware
gate count. ‘NoMap’ as our baseline, represents the compilation results when
assuming all-to-all qubit connectivity. The 2QAN compiler has least
compilation overhead (# SWAPs, # SYCs, and circuit depth) compared to
t$\ket{\textup{ket}}$[26], Qiskit [27].

(a) SWAP count for NNN Heisenberg model

(b) iSWAP count for NNN Heisenberg model

(c) iSWAP depth for NNN Heisenberg model

(d) SWAP count for NNN XY model

(e) iSWAP count for NNN XY model

(f) iSWAP depth for NNN XY model

(g) SWAP count for NNN Ising model

(h) iSWAP count for NNN Ising model

(i) iSWAP depth for NNN Ising model

(j) SWAP count for QAOA-REG-3

(k) iSWAP count for QAOA-REG-3

(l) iSWAP depth for QAOA-REG-3

Figure 8: Compilation results of the one-layer NNN Heisenberg model, NNN XY,
NNN Ising model, and QAOA-REG-3 on the Rigetti Aspen device. The 2QAN compiler
has least compilation overhead (# SWAPs, # iSWAPs, and circuit depth) compared
to t$\ket{\textup{ket}}$[26], Qiskit [27].

(a) SWAP count for NNN Heisenberg model

(b) CNOT count for NNN Heisenberg model

(c) CNOT depth for NNN Heisenberg model

(d) SWAP count for NNN XY model

(e) CNOT count for NNN XY model

(f) CNOT depth for NNN XY model

(g) SWAP count for NNN Ising model

(h) CNOT count for NNN Ising model

(i) CNOT depth for NNN Ising model

(j) SWAP count for QAOA-REG-3

(k) CNOT count for QAOA-REG-3

(l) CNOT depth for QAOA-REG-3

Figure 9: Compilation results of the one-layer NNN Heisenberg model, NNN XY,
NNN Ising model, and QAOA-REG-3 on the IBMQ Montreal device. The 2QAN compiler
has least compilation overhead (# SWAPs, # CNOTs, and circuit depth) compared
to t$\ket{\textup{ket}}$[26], Qiskit [27], and the QAOA compiler (IC-QAOA)
[32, 33, 34].

###  V-A Reducing overhead compared to generic compilers

In this section, we compare the compilation overhead of our 2QAN compiler with
t$\ket{\textup{ket}}$ and Qiskit. Figures 7, 8, 9 show the compilation results
on Google Sycamore, Rigetti Aspen, and IBM Montreal, respectively. Compared to
t$\ket{\textup{ket}}$ and Qiskit, 2QAN has least compilation overhead in terms
of the number of inserted SWAP gates, the number of hardware two-qubit gates,
and the circuit depth. We summarize the overhead reduction of 2QAN versus
t$\ket{\textup{ket}}$ and Qiskit in Tables I and II respectively. We define
the overhead reduction as the ratio of the overhead of t$\ket{\textup{ket}}$
or Qiskit and the overhead of 2QAN. We also compare the compilation results on
the CZ gate set for each qubit architecture in Appendix.

Across all benchmarks and quantum computers, 2QAN inserts on average 3.6x
fewer SWAPs than t$\ket{\textup{ket}}$ and 9.1x fewer SWAPs than Qiskit. This
SWAP count reduction will lead to a significant reduction of the hardware two-
qubit gate count. Moreover, a large percent of SWAPs are unified with circuit
gates by the unitary unifiying pass in 2QAN (gray bars in (a), (d), (g) of
Figures 7-9), further reducing the gate count. For example, when compiling to
the Sycamore device, 2QAN almost has no SYC overhead compared to the baseline
‘NoMap’ for the Heisenberg model. This is because most of the SWAPs can be
combined with circuit gates (Figure 7a) and such an unified gate can be
decomposed into similar number of SYCs as a circuit gate
$\textup{exp}(it(\alpha XX+\beta YY+\gamma ZZ))$. In contrast,
t$\ket{\textup{ket}}$ and Qiskit lead to on average 24.5% and 92.3% SYC
overhead. 2QAN reduces the two-qubit gate overhead by 4x and 10.4x compared to
t$\ket{\textup{ket}}$ and Qiskit on average over all evaluated benchmarks.
This gate count reduction helps reduce the circuit depth. The average depth
overhead reduction by using the 2QAN compiler is 2.1x relative to
t$\ket{\textup{ket}}$ and 3.4x relative to Qiskit.

| Sycamore | Aspen | Montreal
---|---|---|---
Benchmark | SWAPs | SYCs | SYC Depth | SWAPs | iSWAPs | iSWAP Depth | SWAPs | CNOTs | CNOT Depth
| avg | max | avg | max | avg | max | avg | max | avg | max | avg | max | avg | max | avg | max | avg | max
NNN Heisenberg | 1.7x | 3.9x | – | – | 1.2x | 2.7x | 1.1x | 1.8x | 3.2x | 5x | 1.5x | 3.2x | 2.2x | 4.6x | 6x | 12.8x | 2.4x | 5.2x
NNN XY | 1.7x | 3.4x | 6.2x | 21.1x | 1.2x | 2.1x | 1.1x | 1.7x | 1.9x | 3.8x | 1.3x | 2.5x | 2.8x | 4.5x | 5.3x | 8.3x | 2.7x | 3.9x
NNN Ising | 1.9x | 3.9x | 5.6x | 10.7x | 1.3x | 2.9x | 1.1x | 1.8x | 2x | 3.2x | 1.5x | 3.4x | 2.7x | 4.1x | 4.9x | 7.8x | 2.7x | 4x
QAOA-REG-3 | 1.8x | 2.5x | 3.2x | 4.4x | 3.9x | 9.5x | 1.8x | 2.4x | 3x | 4.5x | 2.2x | 3.8x | 2x | 2.4x | 3x | 4.3x | 3x | 4x

TABLE I: The average (avg) and maximum (max) compilation overhead reduction
when comparing 2QAN with t$\ket{\textup{ket}}$[26]. For the cases with blank
values ‘–’, the 2QAN compiler has negligible overhead.

| Sycamore | Aspen | Montreal
---|---|---|---
Benchmark | SWAPs | SYCs | SYC Depth | SWAPs | iSWAPs | iSWAP Depth | SWAPs | CNOTs | CNOT Depth
| avg | max | avg | max | avg | max | avg | max | avg | max | avg | max | avg | max | avg | max | avg | max
NNN Heisenberg | 6x | 9.7x | – | – | 1.8x | 2.6x | 3.3x | 4.3x | 9.3x | 13x | 2.7x | 3.4x | 5.1x | 10.1x | 14x | 27.8x | 3.8x | 7.6x
NNN XY | 6.5x | 11.1x | 24.1x | 68.5x | 2.1x | 3.5x | 3.2x | 4.1x | 5.4x | 8.4x | 2.5x | 3.4x | 5.6x | 8.3x | 10.7x | 16.1x | 4x | 6x
NNN Ising | 6.7x | 11.5x | 19x | 30.7x | 2.4x | 4.1x | 3.3x | 4.1x | 5.6x | 7.4x | 3x | 3.9x | 5.3x | 8.2x | 9.7x | 15x | 4x | 7.4x
QAOA-REG-3 | 4.7x | 6.4x | 8x | 10.6x | 6.9x | 21x | 3.1x | 4x | 5.2x | 6.9x | 3.5x | 5x | 3x | 3.9x | 4.4x | 5.1x | 3.7x | 4.8x

TABLE II: The average (avg) and maximum (max) compilation overhead reduction
when comparing 2QAN with Qiskit [27]. For the cases with blank values ‘–’, the
2QAN compiler almost has negligible overhead.

###  V-B Reducing overhead compared to specialized compilers

We further compare 2QAN with the QAOA compiler in [32, 33, 34] and the
Paulihedral compiler in [36]. We will only evaluate the compilations results
on IBM quantum computers because these two compilers are restricted to the
CNOT or CZ gate set. Compared to the QAOA compiler, 2QAN reduces SWAP count,
CNOT count overhead, and CNOT depth overhead by on average 2.6x, 4x, and 2.8x,
respectively (Figure 9j-9l). The Paulihedral compiler is not open-sourced yet
and we directly use the numbers from [36] as shown in Table III. The
Heisenberg models were compiled by assuming all-to-all connectivity and the
QAOA-REG-m were compiled to the IBMQ Manhattan device that has a dodecagon
lattice and CNOT as native two-qubit gate as the Montreal device. We generate
10 random graphs for each QAOA problem and present the average compilation
results of 2QAN in Table III. The CNOT count and circuit depth achieved by
Paulihedral are on average 1.59x and 1.64x as high as the circuits compiled by
2QAN. Therefore, by employing the permutation-aware optimizations in the
routing and unitary unifying passes, 2QAN outperforms both application-
specific compilers in terms of compilation overhead.

Benchmark | Paulihedral | 2QAN
---|---|---
CNOTs | Depth | CNOTs | Depth
Heisenberg-1D (30 qubits) | 87 | 13 | 87 | 13
Heisenberg-2D (30 qubits) | 216 | 43 | 147 | 25
Heisenberg-3D (30 qubits) | 305 | 65 | 177 | 31
QAOA-REG-4 (20 qubits) | 366 | 147 | 177(7) | 71(4)
QAOA-REG-8 (20 qubits) | 539 | 246 | 324(9) | 160(16)
QAOA-REG-12 (20 qubits) | 678 | 319 | 419(9) | 222(22)

TABLE III: Circuit size comparison with Paulihedral [36]. Numbers in brackets
show the standard deviation over 10 instances.

(a) Experimental results of 1-layer QAOA

(b) Experimental results of 2-layer QAOA

(c) Experimental results of 3-layer QAOA

Figure 10: Experimental results of running QAOA-REG-3 on the IBMQ Montreal
device. The y axis shows the application performance, which is measured by the
normalized cost function $\left\langle C\right\rangle/C_{\textup{min}}$
(larger is better). Each problem size is averaged over 10 different instances
(error bars show the standard deviation). For the same layer QAOA, 2QAN always
achieves better application performance compared to other compilers. By using
2QAN, the 4-qubit QAOA performance improves when the number of layers is
increased from 1 to 2.

###  V-C Improving application performance

To study how the compilation overhead reduction impacts application
performance, we experimentally implemented the QAOA benchmarks with different
numbers of layers on the IBMQ Montreal device. For the multiple-layer QAOA
circuits, the 2QAN compiler only performs compilation for the first layer and
obtains a circuit $c_{1}$. For odd number layers, it directly uses the
compiled circuit $c_{1}$. For even number layers, it simply reverses the two-
qubit gate order in $c_{1}$. In contrast, t$\ket{\textup{ket}}$ and Qiskit
compile a multiple-layer QAOA circuit as a whole. For all four compilers, the
compilation overhead of a $n$-layer QAOA circuit is approximately $n$ times of
the overhead of a single-layer circuit (see Figure 13 in Appendix). In NISQ
computers, the implementation of a quantum application that has fewer hardware
gates (reducing gate errors) and shorter circuit depth (reducing decoherence
errors) should have better performance (higher fidelity). This is
experimentally demonstrated in Figure 10, the circuits compiled by our 2QAN
compiler have the best application performance compared to the results from
using t$\ket{\textup{ket}}$, Qiskit, and IC-QAOA for all problem sizes and all
QAOA layers.

For example, as noise accumulates in QAOA circuits they will often converge to
the value 0 corresponding to a random guess. Here we see that the 3-layer QAOA
benchmarks compiled by t$\ket{\textup{ket}}$ or Qiskit or IC-QAOA already
approach zero for problems with 8 qubits. In comparison, 2QAN only comes close
to this value for much larger problems (around 20 qubits). Ideally (without
hardware noise), the application performance should improve with the number of
QAOA layers. However, in practice there is a trade off, with additional layers
also increasing the overall error probabilities, and hence decreasing
application performance. Figure 10 shows that the QAOA performance of all
problem sizes decreases when the number of layers increases for all compilers
except the 4-qubit QAOA compiled by 2QAN of which performance improves when
increasing the layer number from 1 to 2. This implies that efficient
compilation techniques can enhance device capacity and potentially pave the
way towards practical applications of quantum computing.

###  V-D Scalability and runtime

We use the Tabu search algorithm for solving the qubit placement problem. This
algorithm is fast for solving small problems, e.g, it takes around 1.6 seconds
for the 10-qubit Ising model and 12.2 seconds for the 20-qubit QAOA. However,
it becomes slow for larger problems and takes 330.2 (976.3) seconds for the
40(50)-qubit Heisenberg model. Qubit placement is not our main optimization
goal in this work. More efficient algorithms exist for solving QAP problems
[65] and other qubit mapping techniques [26, 27] could also be applied in
future work. The proposed routing and scheduling heuristics (Algorithm 1 and
Algorithm 2) scale quadratically with the number of gates in one Trotter step.
Moreover, we only perform the compilation for the first Trotter step and
simply use this circuit for odd-number steps and reverse the two-qubit gate
order for even-number steps. Such an implementation saves compilation time and
is similar to the second-order Trotterization in Equation 2. The runtime
evaluation and scalability analysis give us confidence that the 2QAN compiler
will scale up to near-term quantum applications with a considerable number of
qubits and gates.

##  VI Related work

The product formula is the most established approach to simulate the dynamics
of quantum systems. Approximation errors arise when there are anti-commuting
terms in the Hamiltonian. To achieve a desired precision, the time evolution
is divided into many small time steps. Assume a simulation circuit has $r$
Trotter steps and the operator count for implementing each step is $G$.
Minimizing the circuit size $Gr$ meanwhile maintaining computational accuracy
is crucial for a practical implementation. Besides the high-order
approximation approach [10], many randomization approaches have been proposed
to further reduce $Gr$ [66, 67, 68, 69, 70]. Afterwards, these high-level
circuits still need to be decomposed into native hardware gates. One popular
approach for optimizing low-level circuit for Hamiltonian simulation is to
first group Pauli terms into commuting sets and then apply simultaneous
diagonalization of Pauli exponentials in each set [71, 72] or gate
cancellation between consecutive Pauli exponentials [73, 74]. Other works
present circuit synthesis method based on the ZX-calculus [75, 76]. However,
these low-level circuit optimization approaches are restricted to CNOT or CZ-
based circuits and most of them do not consider the qubit connectivity
constraint, requiring further compilation.

Many compilation techniques have been proposed to map quantum circuits onto
NISQ computers with limited qubit connectivity and native gate sets. Some of
them optimize gate count to reduce high probability errors from two-qubit
gates or minimize circuit depth to mitigate the effect of decoherence [20, 21,
22, 23]. Others consider spatial and temporal noise variations and develop
noise-aware compilation algorithms to minimize error rates [24, 25, 56, 77].
Industrial quantum compilers such as t$\ket{\textup{ket}}$ [26] and Qiskit
[27] incorporate multiple techniques to achieve the best application
performance. These general-purpose compilers typically operate at the gate
level and can work for general quantum applications. Nevertheless, they have
little knowledge of the mathematical properties at the application level and
therefore lack fine-grained optimizations.

Application-specific compilation techniques will be advantageous for NISQ
computing. For example, optimized compilers have been developed for
variational quantum algorithms [28, 29, 30, 31, 32, 33, 34, 35] and quantum
simulation in product formula [36]. The optimization techniques in these
specialized compilers are restricted to CNOT or CZ gates and are not
applicable (or cause higher overhead) for quantum computers with other
hardware gates such as the SYC gate in Google Sycamore [17] and the iSWAP gate
in Rigetti Aspen [19]. Furthermore, most of them do not explore the flexible
operator permutation property in the product formula approach for quantum
simulation problems (no matter whether these operators commute or not). For
instance, the compilers in [29, 30, 31, 32, 33, 34] only check for commutable
gates in the circuit mapping procedure but many terms in the Hamiltonian may
not commute (e.g., the XY model and Heisenberg model) and changing the order
of anti-commuting gates will be prohibited. The compiler in [36] considers
this flexibility in the term scheduling procedure but lacks optimizations for
qubit routing and unitary unifying. To address these issues, we exploit the
operator permutation flexibility in different compiler passes and present
application-specific algorithms to minimize compilation overhead. Our 2QAN
compiler can target different architectures and provide efficient compilation
for different gate sets.

##  VII Conclusions

We have developed an application-specific compiler for 2-local qubit
Hamiltonian simulation problems. The designed 2QAN compiler exploits the
flexibility of permuting operators in a Hamiltonian and performs optimizations
on the qubit routing, gate synthesis, and gate scheduling passes. Evaluation
results showed that 2QAN can significantly reduce compilation overhead
compared to two general-purpose compilers and two application-specific
compilers across three quantum computers with different topologies and gate
sets. For some applications, 2QAN even has no gate overhead. Furthermore,
experimental results demonstrated that 2QAN can achieve the highest
application fidelity in practice on hardware. We believe application-specific
compilation techniques will help enhance the performance of quantum
applications on NISQ devices and allow them to explore their maximum
capacities.

Future work will perform more optimizations and investigate other research
directions. First, the objective of 2QAN is to minimize the number of SWAP
gates and circuit depth. NISQ computers have inhomogeneities and noise-aware
compilation techniques can be used to maximize application fidelity [24, 25,
56, 77]. Moreover, error mitigation techniques can be applied to further
reduce errors [78, 79, 80, 81]. In the experimental results reported here, we
only compiled the first Trotter step in Hamiltonian simulation and simply
applied a reverse scheduling for the two-qubit gates in the even-number steps.
Prior works prove that randomizing the operator order in each step can reduce
the simulation costs [66, 67]. Future work can adapt 2QAN to this
randomization and analyze how randomized compiling affects approximation
errors and the efficiency of quantum simulation algorithms. In addition, it is
worthwhile to investigate how to generalize these compilation techniques for
$k$-local Hamiltonians and other quantum simulation algorithms.

## Acknowledgements

We thank Prakash Murali for valuable feedback on the manuscript. We thank
Silas Dilkes for help with the t$\ket{\textup{ket}}$ compiler. We thank César
A. Rodríguez Rosario for help with the experimental setup on the IBMQ Montreal
device via Strangeworks QC platform. We acknowledge use of the IBM Q platform
for this work. We acknowledge funding from the EPSRC Prosperity Partnership in
Quantum Software for Modelling and Simulation (Grant No. EP/S005021/1).

## References

  * [1] Sadegh Raeisi, Nathan Wiebe, and Barry C Sanders.  Quantum-circuit design for efficient simulations of many-body quantum dynamics.  New Journal of Physics, 14(10):103017, 2012.
  * [2] David Poulin, Matthew B Hastings, Dave Wecker, Nathan Wiebe, Andrew C Doherty, and Matthias Troyer.  The Trotter step size required for accurate quantum simulation of quantum chemistry.  arXiv preprint arXiv:1406.4920, 2014.
  * [3] Stephen P Jordan, Keith SM Lee, and John Preskill.  Quantum algorithms for quantum field theories.  Science, 336(6085):1130–1133, 2012.
  * [4] Cornelius Hempel, Christine Maier, Jonathan Romero, Jarrod McClean, Thomas Monz, Heng Shen, Petar Jurcevic, Ben P. Lanyon, Peter Love, Ryan Babbush, Alán Aspuru-Guzik, Rainer Blatt, and Christian F. Roos.  Quantum chemistry calculations on a trapped-ion quantum simulator.  Phys. Rev. X, 8:031022, Jul 2018.
  * [5] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Andreas Bengtsson, Sergio Boixo, Michael Broughton, Bob B Buckley, David A Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Yu-An Chen, Ben Chiaro, Roberto Collins, Stephen J Cotton, William Courtney, Sean Demura, Alan Derk, Andrew Dunsworth, Daniel Eppens, Thomas Eckl, Catherine Erickson, Edward Farhi, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Jonathan A Gross, Steve Habegger, Matthew P Harrigan, Alan Ho, Sabrina Hong, Trent Huang, William Huggins, Lev B Ioffe, Sergei V Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V Klimov, Alexander N Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Erik Lucero, Michael Marthaler, Orion Martin, John M Martinis, Anika Marusczyk, Sam McArdle, Jarrod R McClean, Trevor McCourt, Matt McEwen, Anthony Megrant, Carlos Mejuto-Zaera, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Hartmut Neven, Michael Newman, Murphy Yuezhen Niu, Thomas E O’Brien, Eric Ostby, Bálint Pató, Andre Petukhov, Harald Putterman, Chris Quintana, Jan-Michael Reiner, Pedram Roushan, Nicholas C Rubin, Daniel Sank, Kevin J Satzinger, Vadim Smelyanskiy, Doug Strain, Kevin J Sung, Peter Schmitteckert, Marco Szalay, Norm M Tubman, Amit Vainsencher, Theodore White, Nicolas Vogt, Z Jamie Yao, Ping Yeh, Adam Zalcman, and Sebastian Zanker.  Observation of separated dynamics of charge and spin in the Fermi-Hubbard model.  arXiv preprint arXiv:2010.07965, October 2020.
  * [6] I. M. Georgescu, S. Ashhab, and Franco Nori.  Quantum simulation.  Rev. Mod. Phys., 86:153–185, Mar 2014.
  * [7] Richard P Feynman.  Simulating physics with computers.  International Journal of Theoretical Physics, 21(6/7), 1982.
  * [8] Hale F Trotter.  On the product of semi-groups of operators.  Proceedings of the American Mathematical Society, 10(4):545–551, 1959.
  * [9] Seth Lloyd.  Universal quantum simulators.  Science, pages 1073–1078, 1996.
  * [10] Masuo Suzuki.  General theory of fractal path integrals with applications to many-body theories and statistical physics.  Journal of Mathematical Physics, 32(2):400–407, 1991.
  * [11] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma.  Simulating hamiltonian dynamics with a truncated taylor series.  Phys. Rev. Lett., 114:090502, Mar 2015.
  * [12] Dominic W Berry and Andrew M Childs.  Black-box hamiltonian simulation and unitary implementation.  Quantum Information & Computation, 12(1-2):29–62, 2012.
  * [13] Guang Hao Low and Isaac L. Chuang.  Optimal hamiltonian simulation by quantum signal processing.  Phys. Rev. Lett., 118:010501, Jan 2017.
  * [14] Ryan Babbush, Jarrod McClean, Dave Wecker, Alán Aspuru-Guzik, and Nathan Wiebe.  Chemical basis of Trotter-Suzuki errors in quantum chemistry simulation.  Phys. Rev. A, 91:022311, Feb 2015.
  * [15] Andrew M Childs, Dmitri Maslov, Yunseong Nam, Neil J Ross, and Yuan Su.  Toward the first quantum simulation with quantum speedup.  Proceedings of the National Academy of Sciences, 115(38):9456–9461, 2018.
  * [16] John Preskill.  Quantum computing in the NISQ era and beyond.  Quantum, 2:79, 2018.
  * [17] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, 2019.
  * [18] IBM.  IBM Quantum Experience Devices.  https://quantum-computing.ibm.com/, 2020.
  * [19] Rigetti.  Rigetti computing.  https://www.rigetti.com/, 2020.
  * [20] Alwin Zulehner, Alexandru Paler, and Robert Wille.  An efficient methodology for mapping quantum circuits to the IBM QX architectures.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 38(7):1226–1236, 2018.
  * [21] Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah.  On the qubit routing problem.  arXiv preprint arXiv:1902.08091, 2019.
  * [22] Lingling Lao, Hans van Someren, Imran Ashraf, and Carmen G. Almudever.  Timing and resource-aware mapping of quantum circuits to superconducting processors.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pages 1–1, 2021.
  * [23] Andrew M Childs, Eddie Schoute, and Cem M Unsal.  Circuit transformations for quantum architectures.  arXiv preprint arXiv:1902.09102, 2019.
  * [24] Gushu Li, Yufei Ding, and Yuan 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, pages 1001–1014. ACM, 2019.
  * [25] Prakash Murali, Jonathan M Baker, Ali Javadi-Abhari, Frederic T Chong, and Margaret 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, pages 1015–1029, 2019.
  * [26] Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan.  t$|$ket$>$: a retargetable compiler for NISQ devices.  Quantum Science and Technology, 6(1):014003, 2020.
  * [27] Héctor Abraham, AduOffei, Rochisha Agarwal, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, Thomas Alexander, Eli Arbel, Abraham Asfaw, Carlos Azaustre, AzizNgoueya, Aman Bansal, Panagiotis Barkoutsos, George Barron, Luciano Bello, Yael Ben-Haim, Daniel Bevenius, Lev S. Bishop, Sorin Bolos, Samuel Bosch, Sergey Bravyi, David Bucher, Artemiy Burov, Fran Cabrera, Padraic Calpin, Lauren Capelluto, Jorge Carballo, Ginés Carrascal, Adrian Chen, Chun-Fu Chen, Edward Chen, Jielun (Chris) Chen, Richard Chen, Jerry M. Chow, Spencer Churchill, Christian Claus, Christian Clauss, Romilly Cocking, Abigail J. Cross, Andrew W. Cross, Simon Cross, Juan Cruz-Benito, Chris Culver, Antonio D. Córcoles-Gonzales, Sean Dague, Tareq El Dandachi, Marcus Daniels, Matthieu Dartiailh, DavideFrr, Abdón Rodríguez Davila, Anton Dekusar, Delton Ding, Jun Doi, Eric Drechsler, Drew, Eugene Dumitrescu, Karel Dumon, Ivan Duran, Kareem EL-Safty, Eric Eastman, Pieter Eendebak, Daniel Egger, Mark Everitt, Paco Martín Fernández, Axel Hernández Ferrera, Romain Fouilland, FranckChevallier, Albert Frisch, Andreas Fuhrer, MELVIN GEORGE, Julien Gacon, Borja Godoy Gago, Claudio Gambella, Jay M. Gambetta, Adhisha Gammanpila, Luis Garcia, Shelly Garion, Austin Gilliam, Aditya Giridharan, Juan Gomez-Mosquera, Salvador de la Puente González, Jesse Gorzinski, Ian Gould, Donny Greenberg, Dmitry Grinko, Wen Guan, John A. Gunnels, Mikael Haglund, Isabel Haide, Ikko Hamamura, Omar Costa Hamido, Vojtech Havlicek, Joe Hellmers, Łukasz Herok, Stefan Hillmich, Hiroshi Horii, Connor Howington, Shaohan Hu, Wei Hu, Rolf Huisman, Haruki Imai, Takashi Imamichi, Kazuaki Ishizaki, Raban Iten, Toshinari Itoko, JamesSeaward, Ali Javadi, Ali Javadi-Abhari, Jessica, Madhav Jivrajani, Kiran Johns, Jonathan-Shoemaker, Tal Kachmann, Naoki Kanazawa, Kang-Bae, Anton Karazeev, Paul Kassebaum, Spencer King, Knabberjoe, Yuri Kobayashi, Arseny Kovyrshin, Rajiv Krishnakumar, Vivek Krishnan, Kevin Krsulich, Gawel Kus, Ryan LaRose, Enrique Lacal, Raphaël Lambert, John Lapeyre, Joe Latone, Scott Lawrence, Christina Lee, Gushu Li, Dennis Liu, Peng Liu, Yunho Maeng, Aleksei Malyshev, Joshua Manela, Jakub Marecek, Manoel Marques, Dmitri Maslov, Dolph Mathews, Atsushi Matsuo, Douglas T. McClure, Cameron McGarry, David McKay, Dan McPherson, Srujan Meesala, Thomas Metcalfe, Martin Mevissen, Antonio Mezzacapo, Rohit Midha, Zlatko Minev, Abby Mitchell, Nikolaj Moll, Michael Duane Mooring, Renier Morales, Niall Moran, MrF, Prakash Murali, Jan Müggenburg, David Nadlinger, Ken Nakanishi, Giacomo Nannicini, Paul Nation, Edwin Navarro, Yehuda Naveh, Scott Wyman Neagle, Patrick Neuweiler, Pradeep Niroula, Hassi Norlen, Lee James O’Riordan, Oluwatobi Ogunbayo, Pauline Ollitrault, Steven Oud, Dan Padilha, Hanhee Paik, Yuchen Pang, Simone Perriello, Anna Phan, Francesco Piro, Marco Pistoia, Christophe Piveteau, Alejandro Pozas-iKerstjens, Viktor Prutyanov, Daniel Puzzuoli, Jesús Pérez, Quintiii, Rafey Iqbal Rahman, Arun Raja, Nipun Ramagiri, Anirudh Rao, Rudy Raymond, Rafael Martín-Cuevas Redondo, Max Reuter, Julia Rice, Diego M. Rodríguez, RohithKarur, Max Rossmannek, Mingi Ryu, Tharrmashastha SAPV, SamFerracin, Martin Sandberg, Ritvik Sapra, Hayk Sargsyan, Aniruddha Sarkar, Ninad Sathaye, Bruno Schmitt, Chris Schnabel, Zachary Schoenfeld, Travis L. Scholten, Eddie Schoute, Joachim Schwarm, Ismael Faro Sertage, Kanav Setia, Nathan Shammah, Yunong Shi, Adenilton Silva, Andrea Simonetto, Nick Singstock, Yukio Siraichi, Iskandar Sitdikov, Seyon Sivarajah, Magnus Berg Sletfjerding, John A. Smolin, Mathias Soeken, Igor Olegovich Sokolov, SooluThomas, Starfish, Dominik Steenken, Matt Stypulkoski, Shaojun Sun, Kevin J. Sung, Hitomi Takahashi, Ivano Tavernelli, Charles Taylor, Pete Taylour, Soolu Thomas, Mathieu Tillet, Maddy Tod, Miroslav Tomasik, Enrique de la Torre, Kenso Trabing, Matthew Treinish, TrishaPe, Wes Turner, Yotam Vaknin, Carmen Recio Valcarce, Francois Varchon, Almudena Carrera Vazquez, Victor Villar, Desiree Vogt-Lee, Christophe Vuillot, James Weaver, Rafal Wieczorek, Jonathan A. Wildstrom, Erick Winston, Jack J. Woehr, Stefan Woerner, Ryan Woo, Christopher J. Wood, Ryan Wood, Stephen Wood, Steve Wood, James Wootton, Daniyar Yeralin, David Yonge-Mallo, Richard Young, Jessie Yu, Christopher Zachow, Laura Zdanski, Helena Zhang, Christa Zoufal, and Zoufalc.  Qiskit: An open-source framework for quantum computing, 2019.
  * [28] Pierre-Luc Dallaire-Demers and Frank K. Wilhelm.  Quantum gates and architecture for the quantum simulation of the Fermi-Hubbard model.  Phys. Rev. A, 94:062304, Dec 2016.
  * [29] Davide Venturelli, Minh Do, Eleanor Rieffel, and Jeremy Frank.  Compiling quantum circuits to realistic hardware architectures using temporal planners.  Quantum Science and Technology, 3(2):025004, 2018.
  * [30] Yunong Shi, Nelson Leung, Pranav Gokhale, Zane Rossi, David I Schuster, Henry Hoffmann, and Frederic T Chong.  Optimized compilation of aggregated instructions for realistic quantum computers.  In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1031–1044, 2019.
  * [31] Pranav Gokhale, Yongshan Ding, Thomas Propson, Christopher Winkler, Nelson Leung, Yunong Shi, David I Schuster, Henry Hoffmann, and Frederic T Chong.  Partial compilation of variational algorithms for noisy intermediate-scale quantum machines.  In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, pages 266–278, 2019.
  * [32] Mahabubul Alam, Abdullah Ash-Saki, and Swaroop Ghosh.  Circuit compilation methodologies for quantum approximate optimization algorithm.  In 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 215–228. IEEE, 2020.
  * [33] Mahabubul Alam, Abdullah Ash-Saki, and Swaroop Ghosh.  An efficient circuit compilation flow for quantum approximate optimization algorithm.  In 2020 57th ACM/IEEE Design Automation Conference (DAC), pages 1–6. IEEE, 2020.
  * [34] Mahabubul Alam, Abdullah Ash-Saki, Junde Li, Anupam Chattopadhyay, and Swaroop Ghosh.  Noise resilient compilation policies for quantum approximate optimization algorithm.  In Proceedings of the 39th International Conference on Computer-Aided Design, pages 1–7, 2020.
  * [35] Gushu Li, Yunong Shi, and Ali Javadi-Abhari.  Software-hardware co-optimization for computational chemistry on superconducting quantum processors.  arXiv preprint arXiv:2105.07127, 2021.
  * [36] Gushu Li, Anbang Wu, Yunong Shi, Ali Javadi-Abhari, Yufei Ding, and Yuan Xie.  Paulihedral: A generalized block-wise compiler optimization framework for quantum simulation kernels.  arXiv preprint arXiv:2109.03371, 2021.
  * [37] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  A quantum approximate optimization algorithm.  arXiv:1411.4028, 2014.
  * [38] Francisco Barahona.  On the computational complexity of ising spin glass models.  Journal of Physics A: Mathematical and General, 15(10):3241, 1982\.
  * [39] Lars Onsager.  Crystal statistics. i. a two-dimensional model with an order-disorder transition.  Phys. Rev., 65:117–149, Feb 1944.
  * [40] Toby Cubitt and Ashley Montanaro.  Complexity classification of local hamiltonian problems.  SIAM Journal on Computing, 45(2):268–316, 2016.
  * [41] Alexei Yu Kitaev, Alexander Shen, Mikhail N Vyalyi, and Mikhail N Vyalyi.  Classical and quantum computation.  Number 47. American Mathematical Soc., 2002.
  * [42] Deanna M Abrams, Nicolas Didier, Blake R Johnson, Marcus P da Silva, and Colm A Ryan.  Implementation of the XY interaction family with calibration of a single pulse.  arXiv preprint arXiv:1912.04424, 2019.
  * [43] B. Foxen, C. Neill, A. Dunsworth, P. Roushan, B. Chiaro, A. Megrant, J. Kelly, Zijun Chen, K. Satzinger, R. Barends, F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, S. Boixo, D. Buell, B. Burkett, Yu Chen, R. Collins, E. Farhi, A. Fowler, C. Gidney, M. Giustina, R. Graff, M. Harrigan, T. Huang, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, P. Klimov, A. Korotkov, F. Kostritsa, D. Landhuis, E. Lucero, J. McClean, M. McEwen, X. Mi, M. Mohseni, J. Y. Mutus, O. Naaman, M. Neeley, M. Niu, A. Petukhov, C. Quintana, N. Rubin, D. Sank, V. Smelyanskiy, A. Vainsencher, T. C. White, Z. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis.  Demonstrating a Continuous Set of Two-Qubit Gates for Near-Term Quantum Algorithms.  Phys. Rev. Lett., 125:120504, Sep 2020.
  * [44] B. Kraus and J. I. Cirac.  Optimal creation of entanglement using a two-qubit gate.  Phys. Rev. A, 63:062309, May 2001.
  * [45] Navin Khaneja, Roger Brockett, and Steffen J. Glaser.  Time optimal control in spin systems.  Phys. Rev. A, 63:032308, Feb 2001.
  * [46] Marc Grau Davis, Ethan Smith, Ana Tudor, Koushik Sen, Irfan Siddiqi, and Costin Iancu.  Heuristics for quantum compiling with a continuous gate set.  arXiv preprint arXiv:1912.02727, 2019.
  * [47] Lingling Lao, Prakash Murali, Margaret Martonosi, and Dan Browne.  Designing calibration and expressivity-efficient instruction sets for quantum computing.  In ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA), pages 846–859, 2021.
  * [48] Mohammad Javad Dousti, Alireza Shafaei, and Massoud Pedram.  Squash: a scalable quantum mapper considering ancilla sharing.  In Proceedings of the 24th edition of the great lakes symposium on VLSI, pages 117–122, 2014.
  * [49] Tayebeh Bahreini and Naser Mohammadzadeh.  An minlp model for scheduling and placement of quantum circuits with a heuristic solution approach.  ACM Journal on Emerging Technologies in Computing Systems (JETC), 12(3):1–20, 2015.
  * [50] Lingling Lao, Bas van Wee, Imran Ashraf, J van Someren, Nader Khammassi, Koen Bertels, and Carmen G Almudever.  Mapping of lattice surgery-based quantum circuits on surface code architectures.  Quantum Science and Technology, 4(1):015005, 2018.
  * [51] Sartaj Sahni and Teofilo Gonzalez.  P-complete approximation problems.  J. ACM, 23(3):555–565, July 1976.
  * [52] Fred Glover.  Tabu search—part I.  ORSA Journal on computing, 1(3):190–206, 1989.
  * [53] Fred Glover.  Tabu search—part II.  ORSA Journal on computing, 2(1):4–32, 1990.
  * [54] Rainer E Burkard and Franz Rendl.  A thermodynamically motivated simulation procedure for combinatorial optimization problems.  European Journal of Operational Research, 17(2):169–174, 1984.
  * [55] Yong Li, Panos M Pardalos, and Mauricio GC Resende.  A greedy randomized adaptive search procedure for the quadratic assignment problem.  Quadratic assignment and related problems, 16:237–261, 1993.
  * [56] Swamit S Tannu and Moinuddin 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, pages 987–999. ACM, 2019.
  * [57] Yongshan Ding, Xin-Chuan Wu, Adam Holmes, Ash Wiseth, Diana Franklin, Margaret Martonosi, and Frederic T Chong.  SQUARE: strategic quantum ancilla reuse for modular quantum programs via cost-effective uncomputation.  In 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA), pages 570–583. IEEE, 2020.
  * [58] Farrokh Vatan and Colin Williams.  Optimal quantum circuits for general two-qubit gates.  Phys. Rev. A, 69:032315, Mar 2004.
  * [59] G. Vidal and C. M. Dawson.  Universal quantum circuit for two-qubit transformations with three controlled-NOT gates.  Phys. Rev. A, 69:010301, Jan 2004.
  * [60] Tommy R Jensen and Bjarne Toft.  Graph coloring problems, volume 39.  John Wiley & Sons, 2011.
  * [61] Nathan Lacroix, Christoph Hellings, Christian Kraglund Andersen, Agustin Di Paolo, Ants Remm, Stefania Lazar, Sebastian Krinner, Graham J. Norris, Mihai Gabureac, Johannes Heinsoo, Alexandre Blais, Christopher Eichler, and Andreas Wallraff.  Improving the performance of deep quantum optimization algorithms with continuous gate sets.  PRX Quantum, 1(2):110304, 2020.
  * [62] Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B Buckley, David A Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Sean Demura, Andrew Dunsworth, Daniel Eppens, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Alan Ho, Sabrina Hong, Trent Huang, L B Ioffe, Sergei V Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V Klimov, Alexander N Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Martin Leib, Orion Martin, John M Martinis, Jarrod R McClean, Matt McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Charles Neill, Florian Neukart, Murphy Yuezhen Niu, Thomas E O’Brien, Bryan O’Gorman, Eric Ostby, Andre Petukhov, Harald Putterman, Chris Quintana, Pedram Roushan, Nicholas C Rubin, Daniel Sank, Andrea Skolik, Vadim Smelyanskiy, Doug Strain, Michael Streif, Marco Szalay, Amit Vainsencher, Theodore White, Z Jamie Yao, Ping Yeh, Adam Zalcman, Leo Zhou, Hartmut Neven, Dave Bacon, Erik Lucero, Edward Farhi, and Ryan Babbush.  Quantum approximate optimization of non-planar graph problems on a planar superconducting processor.  Nature physics, 17(3):332–336, February 2021.
  * [63] Quantum AI team and collaborators.  ReCirq, October 2020.
  * [64] Cirq Developers.  Cirq, May 2021.  See full list of authors on Github: https://github.com/quantumlib/Cirq/graphs/contributors.
  * [65] Rainer E Burkard, Eranda Cela, Panos M Pardalos, and Leonidas S Pitsoulis.  The quadratic assignment problem.  In Handbook of combinatorial optimization, pages 1713–1809. Springer, 1998.
  * [66] Andrew M Childs, Aaron Ostrander, and Yuan Su.  Faster quantum simulation by randomization.  Quantum, 3:182, 2019.
  * [67] Earl Campbell.  Random compiler for fast hamiltonian simulation.  Phys. Rev. Lett., 123:070503, Aug 2019.
  * [68] Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng, and Joel A Tropp.  Quantum simulation via randomized product formulas: Low gate complexity with accuracy guarantees.  arXiv preprint arXiv:2008.11751, 2020.
  * [69] Yingkai Ouyang, David R White, and Earl T Campbell.  Compilation by stochastic Hamiltonian sparsification.  Quantum, 4:235, 2020.
  * [70] Paul K Faehrmann, Mark Steudtner, Richard Kueng, Maria Kieferova, and Jens Eisert.  Randomizing multi-product formulas for improved Hamiltonian simulation.  arXiv preprint arXiv:2101.07808, 2021.
  * [71] Ewout van den Berg and Kristan Temme.  Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters.  Quantum, 4:322, 2020.
  * [72] Alexander Cowtan, Will Simmons, and Ross Duncan.  A generic compilation strategy for the unitary coupled cluster ansatz.  arXiv preprint arXiv:2007.10515, 2020.
  * [73] Matthew B Hastings, Dave Wecker, Bela Bauer, and Matthias Troyer.  Improving quantum algorithms for quantum chemistry.  arXiv preprint arXiv:1403.1539, 2014.
  * [74] Kaiwen Gui, Teague Tomesh, Pranav Gokhale, Yunong Shi, Frederic T Chong, Margaret Martonosi, and Martin Suchara.  Term grouping and travelling salesperson for digital quantum simulation.  arXiv preprint arXiv:2001.05983, 2020.
  * [75] Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons, and Seyon Sivarajah.  Phase gadget synthesis for shallow circuits.  arXiv preprint arXiv:1906.01734, 2019.
  * [76] Arianne Meijer-van de Griend and Ross Duncan.  Architecture-aware synthesis of phase polynomials for NISQ devices.  arXiv preprint arXiv:2004.06052, 2020.
  * [77] Prakash Murali, David C McKay, Margaret Martonosi, and Ali 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, pages 1001–1016, 2020.
  * [78] Kristan Temme, Sergey Bravyi, and Jay M. Gambetta.  Error mitigation for short-depth quantum circuits.  Phys. Rev. Lett., 119:180509, Nov 2017.
  * [79] Ying Li and Simon C. Benjamin.  Efficient variational quantum simulator incorporating active error minimization.  Phys. Rev. X, 7:021050, Jun 2017.
  * [80] Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C. Mckay, and Jay M. Gambetta.  Mitigating measurement errors in multiqubit experiments.  Phys. Rev. A, 103:042605, Apr 2021.
  * [81] Swamit S Tannu and Moinuddin K Qureshi.  Mitigating measurement errors in quantum computers by exploiting state-dependent bias.  In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, pages 279–290, 2019.

In this appendix, we present additional results of comparing 2QAN’s
compilation performance on the IBM Montreal, Google Sycamore, and Rigetti
Aspen devices. In addition to the hardware two-qubit gates (SYC and iSWAP) in
Figure 1, Sycamore and Aspen also implement CZ gates as native gates. In this
comparison, we use the recommended optimization passes for the CNOT/CZ gates
in Qiskit, t$\ket{\textup{ket}}$, and the QAOA compiler. That is, we use
Qiskit with optimization level 3, t$\ket{\textup{ket}}$ with the ‘FullPass’
(FullPeepholeOptimise, followed by the default qubit mapping pass,
SynthesiseIBM), the QAOA compiler with. Similarly to results in Section V,
2QAN exploits the term permutation flexibility in Hamiltonian simulation and
has the least compilation overhead (the number of inserted SWAPs, the CNOT
gate count, and the circuit depth) compared to all three compilers across all
benchmarks and quantum computers.

Figure 11 and Table IV show the compilation results on the Sycamore
architecture with CZ as the hardware two-qubit gate. 2QAN almost has no CZ
overhead compared to ‘NoMap’ for the Heisenberg model. This is because most of
the SWAPs can be combined with circuit gates (Figure 11a) and such an unified
gate can be decomposed into the same number (3) of CZs as a circuit gate
$\textup{exp}(it(\alpha XX+\beta YY+\gamma ZZ))$. In contrast,
t$\ket{\textup{ket}}$ and Qiskit lead to on average 55.6% and 107% CZ
overhead, respectively. Similarly, 2QAN almost has no overhead for the XY
model and only has on average 8.7% CZ overhead for the Ising model (the
circuit unitary $\textup{exp}(i\theta ZZ)$ requires 2 CZs). The maximum depth
reduction over four benchmarks is 10.3x relative to t$\ket{\textup{ket}}$ and
13.7x compared to Qiskit.

Figure 12 and Table V show the results of compilation on the Aspen
architecture. 2QAN inserts the same number of SWAPs as t$\ket{\textup{ket}}$
for all three models. More than 60% of these SWAPs can be combined with
circuit gates, which will help reduce hardware gate count. For example, 2QAN
reduces CZ overhead of the Heisenberg model by on average 2.8x (up to 3.0x)
compared to t$\ket{\textup{ket}}$ and 7.2x (up to 9.3x) with respect to
Qiskit. The average depth reduction over three benchmarks is 1.6x and 2.9x
compared to t$\ket{\textup{ket}}$ and Qiskit, respectively.

Figure 13 shows the compilation results of 3-layer QAOA on the Montreal
device. Since QAOA has periodic circuit structures, the 3-layer QAOA circuits
have approximately 3x compilation overhead compared to 1-layer QAOA circuits
in Figure 9.

(a) SWAP count for NNN Heisenberg model

(b) CZ count for NNN Heisenberg model

(c) CZ depth for NNN Heisenberg model

(d) SWAP count for NNN XY model

(e) CZ count for NNN XY model

(f) CZ depth for NNN XY model

(g) SWAP count for NNN Ising model

(h) CZ count for NNN Ising model

(i) CZ depth for NNN Ising model

(j) SWAP count for QAOA-REG-3

(k) CZ count for QAOA-REG-3

(l) CZ depth for QAOA-REG-3

Figure 11: Compilation results of the one-layer NNN Heisenberg model, NNN
Ising model, and QAOA on the Google Sycamore architecture with CZ as hardware
gate. The 2QAN compiler has least compilation overhead compared to Qiskit and
t$\ket{\textup{ket}}$.

(a) SWAP count for NNN Heisenberg model

(b) CZ count for NNN Heisenberg model

(c) CZ depth for NNN Heisenberg model

(d) SWAP count for NNN XY model

(e) CZ count for NNN XY model

(f) CZ depth for NNN XY model

(g) SWAP count for NNN Ising model

(h) CZ count for NNN Ising model

(i) CZ depth for NNN Ising model

(j) SWAP count for QAOA-REG-3

(k) CZ count for QAOA-REG-3

(l) CZ depth for QAOA-REG-3

Figure 12: Compilation results of the one-layer NNN Heisenberg model, NNN
Ising model, and QAOA on the Rigetti Aspen architecture with CZ as hardware
gate. The 2QAN compiler has least compilation overhead compared to Qiskit and
t$\ket{\textup{ket}}$.

|  t$\ket{\textup{ket}}$ | Qiskit
---|---|---
SWAPs | CZs | Depth | SWAPs | CZs | Depth
avg | max | avg | max | avg | max | avg | max | avg | max | avg | max
NNN Heisenberg | 3.3x | 5x | – | – | 2.2x | 4.1x | 5.1x | 9x | – | – | 2.1x | 3x
NNN XY | 2.8x | 4.9x | 7.5x | 14.6x | 2.2x | 4.4x | 5.7x | 9.2x | 15.4x | 27.5x | 2.3x | 3.8x
NNN Ising | 2.6x | 5x | 8.7x | 15.6x | 1.3x | 2.9x | 5.2x | 8.9x | 16.4x | 29.6x | 2.4x | 4.1x
QAOA-REG-3 | 1.8x | 2.4x | 3.4x | 4.8x | 4.3x | 10.3x | 3.6x | 5.3x | 6.7x | 9x | 5.5x | 13.7x

TABLE IV: The average (avg) and maximum (max) compilation overhead reduction
when comparing 2QAN with t$\ket{\textup{ket}}$ and Qiskit on the Sycamore
architecture with CZ as hardware gate. For the cases with blank values ‘–’,
2QAN has negligible CZ overhead.

|  t$\ket{\textup{ket}}$ | Qiskit
---|---|---
SWAPs | CZs | Depth | SWAPs | CZs | Depth
avg | max | avg | max | avg | max | avg | max | avg | max | avg | max
NNN Heisenberg | 1x | 1x | 2.8x | 3x | 1.2x | 1.4x | 2.7x | 3.5x | 7.2x | 9.3x | 2.4x | 3x
NNN XY | 0.99x | 1x | 1.7x | 1.8x | 1.1x | 1.4x | 2.8x | 3.4x | 4.8x | 6.2x | 2.5x | 3.6x
NNN Ising | 1x | 1x | 1.7x | 1.8x | 1.2x | 1.4x | 2.7x | 3.5x | 4.9x | 6.2x | 2.8x | 3.7x
QAOA-REG-3 | 2.1x | 2.8x | 3.1x | 6.5x | 2.4x | 3.6x | 3.3x | 4.6x | 4.6x | 5x | 3.4x | 4.6x

TABLE V: The average (avg) and maximum (max) compilation overhead reduction
when comparing 2QAN with t$\ket{\textup{ket}}$ and Qiskit on the Aspen
architecture with CZ as hardware gate.

(a) SWAP count for 3-layer QAOA-REG-3

(b) CNOT count for 3-layer QAOA-REG-3

(c) CNOT depth for 3-layer QAOA-REG-3

Figure 13: Compilation results of 3-layer QAOA-REG-3 on the IBMQ Montreal
device. Each QAOA problem size is averaged over 10 different instances (error
bars show the standard deviation) and operator parameters of QAOA circuits
were chosen at their theoretically optimal values. ‘2QAN dressed’ shows the
number of SWAPs that were merged with circuit gates by 2QAN, which helps to
reduce hardware gate count. ‘NoMap’ represents the compilation results when
assuming all-to-all qubit connectivity. The overhead of 3-layer QAOA circuits
is approximately 3 times of the overhead of 1-layer QAOA circuits. The 2QAN
compiler has least compilation overhead compared to Qiskit,
t$\ket{\textup{ket}}$, and the QAOA compiler (IC-QAOA).