Compiling Quantum Circuits to Realistic Hardware
Architectures using Temporal Planners
Davide Venturelli1,2 , Minh Do3,4 , Eleanor Rieffel1 , Jeremy Frank4

arXiv:1705.08927v2 [quant-ph] 21 Dec 2017

1

NASA Ames Research Center, Quantum Artificial Intelligence Laboratory
USRA Research Institute for Advanced Computer Science (RIACS)
3
Stinger Ghaffarian Technologies (SGT Inc.)
4
NASA Ames Research Center, Planning and Scheduling Group
2

E-mail: davide.venturelli@nasa.gov

2
Abstract. To run quantum algorithms on emerging gate-model quantum hardware,
quantum circuits must be compiled to take into account constraints on the hardware. For
near-term hardware, with only limited means to mitigate decoherence, it is critical to
minimize the duration of the circuit. We investigate the application of temporal planners to
the problem of compiling quantum circuits to newly emerging quantum hardware. While
our approach is general, we focus on compiling to superconducting hardware architectures
with nearest neighbor constraints. Our initial experiments focus on compiling Quantum
Alternating Operator Ansatz
(QAOA) circuits whose high number of commuting gates allow great flexibility in the
order in which the gates can be applied. That freedom makes it more challenging to find
optimal compilations but also means there is a greater potential win from more optimized
compilation than for less flexible circuits. We map this quantum circuit compilation
problem to a temporal planning problem, and generated a test suite of compilation problems
for QAOA circuits of various sizes to a realistic hardware architecture. We report
compilation results from several state-of-the-art temporal planners on this test set. This
early empirical evaluation demonstrates that temporal planning is a viable approach to
quantum circuit compilation.

1. Introduction
We explore the use of temporal planners to optimize compilation of quantum circuits to
newly emerging quantum hardware. Currently only special purpose quantum hardware is
commercially available: quantum annealers that run only one type of quantum optimization
algorithm. The emerging gate-model processors, currently in prototype phase, are universal
in that, once scaled up, they can run any quantum algorithm. This facilitates expanding the
empirical exploration of quantum algorithms beyond optimization, as well as enabling the
exploration of a broader array of quantum approaches to optimization.
Quantum algorithms are usually specified as idealized quantum circuits that do not
take into account hardware constraints. This approach makes sense since the actual
physical constraints vary from architecture to architecture. With the advent of gate-model
processors, researchers have begun to explore approached to compiling idealized quantum
circuits to realistic hardware. For example, emerging superconducting quantum processors
have planar architectures with nearest-neighbor restrictions on the locations (qubits) to
which the gates can be applied. Such processors include the 5-qubit processor IBM
recently made publicly available the cloud [IBM, 2017a], recently updated to 20 qubits,
and processors being fabricated by other groups, such as Intel/TU Delft [Versluis et al.,
2016], UC Berkeley [Ramasesh et al., 2017], Rigetti Computing [Sete et al., 2016] [Reagor
et al., 2017], and Google [Boxio, 2016]. All cited groups have announced plans to build

3
gate-model quantum processors with 40 or more qubits in the near term. Idealized circuits
generally do not respect nearest neighbor constraints; idealized quantum circuits generaly
contain many gates between pairs of qubits that are not nearest neighbors and therefor
cannot be implemented directly on the processors. - see Figure 2 for more details. For this
reason, compiling idealized quantum circuits to superconducting hardware requires adding
supplementary gates that move qubit states to locations where the desired gate can act on
them.
Quantum computational hardware suffers from decoherence, which degrades the
performance of quantum algorithms over time. Especially for near-term hardware, with
only limited means to mitigate decoherence, it is critical to minimize the duration of
(execution of) the circuit that carries out the quantum computation, so as to minimize
the decoherence experienced by the computation. Other, more sophisticated, compilation
cost functions, such as figure-of-merits taking into account fidelity of operations [Bishop
et al., 2017] [Moll et al., 2017], could be used in the future within the temporal planning
approach to compilation we explore here. Optimizing the duration of compiled circuits is
a challenging problem due to the parallel execution of gates with different durations. For
quantum circuits with flexibility in when the gates can be applied, or when some gates
commute with each other (so can be applied in a different order while still achieving
the same computation) the search space for feasible compilations is larger than for less
flexible circuits. That freedom makes it more challenging to find optimal compilations but
also means there is a greater potential win from more optimized compilation than for less
flexible circuits.
While there has been active development of software libraries that server as a software
toolchain to compile an algorithm (specified in some standardized language) into idealized
quantum circuits (see Ref. [Chong et al., 2017] for a review, and [Wecker and Svore,
2014] [Smith et al., 2016a] [Steiger et al., 2016a] [Devitt, 2016] [Barends et al., 2016]
for the most relevant works), few approaches have been explored for compiling idealized
quantum circuits to realistic quantum hardware [Beals et al., 2013] [Brierley, 2015]
[Bremner et al., 2016], leaving the problem open for innovation. Recent studies explore
exact schemes [Wille et al., 2014], approximate tailored methods [Kole et al., 2017] or
formulations suited for off-the-shelf Mixed Integer Linear Programming (MILP) solvers
such as Gurobi [Bhattacharjee and Chattopadhyay, 2017]. The benchmarks in prior work
have mostly revolved around circuits composed by elementary gates relevant for faulttolerant quantum computing schemes, with attention shifting recently in the quantum
computing community towards algorithms to be run on near-term hardware. These
algorithms have circuits that often contain a large number of mutually commuting gates,

4
but not necessarily natively available in the hardware. Recently a tailored scheduling
heuristic approach has been published by [Guerreschi and Park, 2016] to schedule quantum
circuits with many commuting gates (but only for gates of unity duration and/or on a
linear architecture.) Prior work had not used a temporal planning approach, which can
be applied quite generally, enabling us to address, for the first time, gates with variable
durations, generic architectures with inhomogeneous spatial features, and efficiencies that
can be gained when large numbers of gates commute. An similar issue arising when
compiling classical programs is the register allocation problem, in which program variables
are assigned to machine registers to improve execution time; this problem reduces to graph
coloring [Fu et al., 2005].
In this paper, we apply temporal planning techniques to the problem of compiling
quantum circuits to realistic gate-model quantum hardware. Temporal planning is a
subdomain of Automated Planning and Scheduling, a branch of Artificial Intelligence
(AI) which is concerned with the identification of strategic decisions, among a large finite
set of possibilities, to achieve a specific goal that includes temporal constraints or time
optimization objectives.
As we will explain in Section 4, we use domain-independent AI planners to find
a parallel sequence of conflict-free instructions that, when executed, achieve the same
result as the machine-independet quantum circuit. Additional instructions specific to a
gate-model architecture are inserted. The temporal planners aim to provide a machinedependent plan that minimizes makespan, while respecting all machine-dependent
constraints (e.g. available gates to perform swap operations, physical layout of the gates,
duration of gates, exclusions on simultaneous operations.) While our approach is general,
we focus our initial experiments on circuits that have few ordering constraints and thus
allow highly parallel plans. We report on experiments using a diverse set of temporal
planners to compile circuits of various sizes to an architecture inpired by those currently
being built. This early empirical evaluation demonstrates that temporal planning is a viable
approach to quantum circuit compilation.
In Sec. 2, we describe the problem of compiling idealized quantum circuits to specific
hardware architectures in detail. Sec. 3 describes QAOA circuits, the class of circuits with
many commuting gates that we target for our initial invstigation. Section 4 explains our
mapping of the quantum circuit compilation problem to temporal planning problem. Sec. 5
presents our results applying state-of-the-art temporal planners to this circuit compilation
problem. In Sec. 6, we outline future research directions stemming from this study. The aim
is to write the paper to communicate clearly to both the quantum computing community
and the temporal planning and artificial intelligence communities, so it will necessarily

5
contain some material that is review for one or the other group.
2. Architecture-specific quantum circuit compilation problem
Quantum circuits for general quantum algorithms are often described on an idealized
architecture in which any 2-qubit gate can act on any pair of qubits. Physical constraints
impose restrictions on which pairs of qubits support gate interactions in an actual physical
architecture. In this work, we concentrate on superconducting qubit architectures, using an
abstract model that takes into account gate durations and the nearest neighbor topology
of the quantum processors which will be used as the basis for the temporal planning
formulation of the compilation problem.
In general, the model will specify different types of abstract quantum gates,
each taking different durations, with a duration depending on the specific physical
implementation in terms of primitive gates. Gate-model quantum architectures operate as
digital computers with a clock, and times could be expressed in terms of clock cycles.
Elementary or primitive gates are the gates that have been directly implemlented in
the hardware and carefully calibrated, so are generally the fastest possible operations.
However, from a sequence of primitive gates, composite gates can be synthesized, making
it possible to describe a chip in terms of the relevant gates for the algorithm, as long as we
take into account the number of clock cycles that are required to perform the wanted gate.
In the model, qubits in a quantum processor can be thought of as nodes in a graph, and
the relevant 2-qubit quantum gates are associated to edges. In many architectures more than
one 2-qubit gate may be implementable between a given pair of qubits, so this structure is
a multigraph (multiple edges allowed between two nodes). In general the gates are nonsymmetric so the multi-graph could be directed (i.e. distinguishing the roles of two qubits),
as for instance is the case if we include the primitive (calibrated) gates in the IBM Quantum
Experience chip [IBM, 2017b].
Gates that operate on distinct sets of qubits may be able operate concurrently, though
there can be additional restrictions on which operations can be done in parallel, such as requiring the sets in operation to be non-adjacent, due to cross-talk and frequency-crowding,
as in Google’s proposed architecture [Boxio, 2016]).
The swap gate and its synthesis: In this study, we make extensive use of a particular type
of a 2-qubit gate, the swap gate, which exchanges the state of two qubits, though other
gate choices are possible. In order for the computation specified by the idealized circuit
to be completed, quantum information must be moved to locations where the desired gates

=

X−π/2

X−π/2

iSWAP

=

iSWAP

=

iSWAP

6

X−π/2

Figure 1. A known decomposition of the swap gate using as primitive gates three CNOTs or replacing recursively the C-NOTs with their synthesis in terms of iSWAPs and
X-rotations.

can be carried out, and a sequence of swap gates can be used to move the contents of two
distant qubits to a location where a desired gate can be executed. For this reason, the swap
gate is a useful gate for compilation in sparsely-connected architectures.
This origin of the “duration” abstraction for gates is exemplified in Figure 1(left) for
the swap gate, which can be efficiently decomposed in three control-NOT (CNOT) gates
[Schuch and Siewert, 2003]. The swap gate should last at least three times as long as the
CNOT gate [Vatan and Williams, 2004]. Figure 1(right) shows a possible synthesis of the
same swap in terms of only iSWAP gates, which are the primitives available everywhere
across the chip described in [Sete et al., 2016] .
Beside the timings dictated by logical gate synthesis, different choices of synchronization and time-scales of executions are possible, leading to different possible durations.
For instance, in [Caldwell et al., 2017] the controlled-Z gate (CZ) could last 175 or 270
nanoseconds depending on which choices are made at calibration. Across the chip, calibration might result in different gate times depending on the location in the chip even if the
underlying circuitry is the same, as shown in [IBM, 2017b], where the CNOT gate duration
could vary up to a factor of 2.
For the purposes of this study, we consider a simplified model in which swap gates
are available between any two adjacent qubits on the chip and all swap gates have the same
duration, but our temporal planning approach can handle the more general cases.
2.1. Formal problem statement
An idealized quantum circuit consists of a set of nodes (qubits), which can be thought of
as memory locations, and a specification of start times for operations (gates), each acting on a single node or set of nodes. The idealized quantum circuit also includes implicit
or explicit specification of which operations commute (the order in which they are exe-

7
cuted can be switched without affecting the computation) either individually or as blocks.
A hardware architecture specification can be viewed as a weighted, labeled multigraph
on a set of nodes, corresponding to physical quantum memory locations (qubits) in the
hardware, where each edge represents an operation (quantum gate) that can be physically
implemented on the pair of qubits in the physical hardware, possibly as a composite gate,
with the labels indicating the type of quantum gate and the weight giving its duration. The
output of the compilation process is a circuit that can be used to perform a quantum computation. It does not perform the computation itself, and therefore the compilation step can
be carried out on a conventional (non-quantum) computer. In this work, we are concerned
with the efficiency and effectiveness of the compilation. A separate issue, which we do not
consider here, is the performance of the quantum algorithms we are compiling.
Ideal to hardware-specific quantum circuit compilation problem: The problem input
is an idealized quantum circuit and a hardware multigraph. The output is a time-resolved
hardware-specific circuit that implements the quantum computation described by idealized
quantum circuit. The objective is to minimize the makespan (the circuit duration) of the
resulting schedule.
2.2. Compilation examples
Fig. 2 shows a hypothetical chip design that we will use for our experiments on circuit
compilation. It is inspired by the architecture proposed by Rigetti Computing Inc. [Sete
et al., 2016]. Qubits are labeled with ni and the colored edges indicate the types of 2-qubit
gates available (considering just those relevant for the algorithm), in this case swap gates
and two other types of 2-qubit gate (further described in Section 4). Given an idealized
circuit consisting only of the non-swap gates, used to define general quantum algorithms,
the circuit compilation problem is to find a new architecture-specific circuit by adding swap
gates when required, and reordering commuting operations when desired. The objective is
to minimize the overall duration to execute all gates in the new circuit. To illustrate the
challenges of finding effective compilation, we present some concrete examples, with reference to the 8-qubit section in the top left of Fig. 2.
Example 1: Suppose that at the beginning of the compilation, each qubit location ni
is associated to the qubit state qi . Let us also assume that the idealized circuit requires
the application of a red gate to the states q2 and q4 , initially located on qubits n2 and n4 .
One way to achieve this task would be to swap the state in n4 with n1 , while at the same

8

n2

n3
0000

n1

n4

n5

n6

n7

n8

Figure 2. Left: A schematic for the hypothetical chip design, based on an architecture
proposed by Rigetti Computing used in our numerical experiments. Available relevant
2-qubit gates are represented by colored arcs in a weighted multigraph. Each color is
associated to a specified, distinct gate-type and duration: SWAP gates (black) and two other
types of 2-qubits gates (red and blue). The 1-qubit gates are present at each qubit (black
dot). Right: Dashed boxes indicate the three different chip sizes used in our empirical
evaluation (see Sec. 5). For visual clarity, only the label locations and the SWAP-gates for
the smaller chip size, corresponding to the top-left sector of the largest chip, are shown.

time swapping n2 with n3 . Another swap, between n1 and n2 , positions q4 in n2 where a
red-gate connects it to q2 (which is now in n3 ).
The sequence of gates to achieve the stated goal are:
{SWAPn4 ,n1 , SWAPn2 ,n3 } →
≡

RED (q2 , q4 )

SWAP n1 ,n2

→

RED n2 ,n3

(1)

The first line refers to the sequence of gate applications, while the second corresponds to
the algorithm objective specification (a task defined over the qubit states). The sequence in
Eq. (1) takes 2τswap + τred clock cycles where τ? represents the duration of the ?-gate.
Example 2:
Consider an idealized circuit that requires BLUE(q1 , q2 ) ∧ RED(q4 , q2 ), in no particular
order. If τblue > 3 × τswap , the compiler might want to execute BLUEn1 ,n2 while the qubit
state q4 is swapped all the way clockwise in five SWAPs from n4 to n3 where REDn2 ,n3 can
be executed. However, if τblue < 3×τswap , it is preferable to wait until the end of BLUEn1 ,n2

9
and then start to executthe instruction sequence in Eq. (1).

3. Compiling QAOA for the MaxCut problem
While our approach can be used to compile arbitrary quantum circuits to a wide range of
architectures, in this paper we concentrate on one particular case: the class of Quantum
Alternating Operator Ansatz (QAOA) circuits [Farhi et al., 2014a, Hadfield et al., 2017]
for MaxCut (defined in the later part of this section) to the above-mentioned architecture
inspired to Rigetti Computing Inc. [Sete et al., 2016]. We choose to work with QAOA
circuits because they have many gates that commute with each other (i.e., no ordering
enforced). Such flexibility in the ordering of the gates means that the compilation search
space is larger than for other less flexible circuits. This makes finding the optimal
compilation more challenging, but also means there is potential for greater compilation
optimization, compared to other less flexible classes of circuits.
QAOA circuits have been the focus of recent research [Farhi et al., 2014a] [Farhi et al.,
2014b] [Farhi and Harrow, 2016] [Wecker et al., 2016] [Yang et al., 2016] [Guerreschi
and Smelyanski, 2017] [Jiang et al., 2017] [Wang et al., 2017] [Hadfield et al., 2017]
in the quantum computing community since their introduction by Farhi et al. in [Farhi
et al., 2014a]. The acronym was reworked from “quantum approximate optimization
algorithm” to “quantum alternating operator ansatz” in [Hadfield et al., 2017] since QAOA
circuits have been applied to exact optimization and sampling as well as to approximate
optimization and there are other quantum approaches to approximate optimization.
Recently Google Inc. proposed an alternative quantum approximate optimization
approach
in fixed nearest-neighbor architectures explicitly to avoid the compilation step that is
the subject of our work [Farhi et al., 2017]. Their numerical results on MaxCut instances
show a small hit in performance. Furthermore, unlike the QAOA circuits we consider
here, in which the number of parameters is independent of the number of qubits, their
alternative approach has many more parameters, which increase with the number of qubits,
and these parameters must be optimized separately for each architecture. While their
approach makes good use of near-term hardware with numbers of qubits for which the
parameter optimization is tractable, ultimately one wants a scalable algorithm that can be
compiled to arbitrary architectures. Thus, while interesting, especially in the very nearterm, rather than obviating the need, their work serves to underscore the need for efficient
approaches to optimize compilation.

10

q5

q1

PS1

MX

PS2

q6
q3

q4

q7

Figure 3. Example of a 6-vertex MaxCut problem on a randomly generated graph (qstates
q2 and q8 are not appearing in this instance). The association of quantum states to every
node allows the definition of the compilation objectives in terms of gates, as exemplified
on the right panel for QAOA p = 2. Colored edges refer to Figure 6.

We chose MaxCut as the target problem of reference, as it is becoming one of the
de facto benchmark standards for quantum optimization of all types and it is considered a
primary target for experimentation in the architecture of [Sete et al., 2016].
MaxCut Problem: Given a graph G(V, E) with n = |V | vertices and m = |E| edges.
The objective is to partition the graph vertices into two sets such that the number of edges
connecting vertices in different sets is maximized.
A quadratic boolean objective function for MaxCut is:
1 X
(1 − si sj ),
(2)
U=
2 (i,j)∈E
where si are binary variables, one for each vertex vi , with values +1 or -1 indicating to
which partition the vertex vi is assigned.
Idealized QAOA circuits alternate between a phase separation step (PS), based on the
objective function, and a mixing step. The phase-separation step for QAOA for MaxCut is
simpler than for other optimization problems, consisting of a set of identical 2-qubit gates
that must be applied between certain pairs of qubits depending on the graph of the MaxCut
instance under consideration. Specifically, the idealized QAOA circuit for MaxCut requires
a 2-qubit gate for each quadratic term in the objective function of Eq. (2), as well as 1-qubit
gates for each vertex for the mixing step [Farhi et al., 2014a].

11
In Fig. 3 a 6-vertex graph is shown, providing an illustrative instance that will be used
to describe the compilation procedure. We will refer to these as p-s gates, and the main
goal of the compilation is to carry them out.
The p-s gates all commute with each other, implying that they can be carried out in
any order without changing the computation.
In the mixing phase, a set of 1-qubit operations are applied, one to each qubit‡
All p-s gates that involve a specific qubit q must be carried out before the mixing
operator on q can be applied. These two steps are repeated p times. We consider p = 1 and
p = 2 in our experiments (detailed in Section 5).
For every vertex i ∈ V , QAOA for MaxCut requires a quantum state qi to be assigned
on a qubit on the chip, and for every edge (i, j) ∈ E, the PS step of QAOA requires
executing a gate corresponding to P - S(qi , qj ). We ignore the final mixing step since it is
trivial to compile by just applying the 1-qubit mixing gate to each qubit as the last operation.
We chose the architecture proposed by Rigetti Compuing in [Sete et al., 2016] (see
Fig. 2) for our initial exploration because it offers a particularly interesting compilation,
and therefore planning, problem, due to the existence of two different kinds of nearest
neighbor relation in the proposed hardware. After the synthesis of the QAOA MaxCut
gates, these two different relations become two different durations of two-qubit gates,
which corresponds to the red and blue edges as described above.
In our problem specification, while there are two flavors of p-s gates (red, blue),
corresponding to two different durations of execution, the compilation goals (see figure 3)
do not care on which of these two types of gates carries out the required steps. For the
purpose of this proof-of-concept work, these durations we assign to the gates are not
derived from actual designs of ongoing experiments, but are realistic and serve to illustrate
possible future designs.
The constraints on the compilation problem can be understood, with reference to
Fig. 2, as:
•

SWAP

gates are located at every edge with τswap = 2.

• there are two kind of non-swap gates: P - S gates are 2-qubit gates and
1-qubit gates.
•

MIX

gates are

gates are located at every edge of the grid, but their duration τp−s can be 3 or 4
depending on their location (respectively blue or red edges in Fig.2).
P-S

‡ This is another simple feature of MaxCut, and it is due to the fact that all possible 2N si variable
assignments (see Eq. 2) are defining a valid cut. If this wasn’t the case, then the mixing phase would also
likely require the application of 2-qubit gates, further complicating the scheduling problem.

12
•

MIX

gates are located at every vertex with τmix =1.

• In an initialization stage, which is not considered as part of the compilation problem,
a quantum state is assigned to each qubit.
4. Compilation of a Quantum Circuit as Temporal Planning Problem
Planning is the problem of finding a conflict-free set of actions and their respective
execution times that connects the initial-state I and the desired goal state G. We now
introduce some key concepts that provide the background for approaching the problem of
compiling quantum circuits as a temporal planning problem.
Classical planning problems are expressed in terms of binary state variables and
actions. Examples of state variables for our problem are “The quantum state Ψ is assigned
to qubit number X” and “The quantum state Φ has been transformed by the application of
gate G present on qubits X and Y ,” which may be True or False. Actions consist of two
lists, a set of preconditions and a set of effects.
The effects of an action consists of a subset of state variables with the values they take
on if the action is carried out. For example, the action “State Ψ is now moved from qubit
X to qubit Y ” has one precondition, “State Ψ is assigned to X = True” and has two effects
“State Ψ is assigned to X = False” and “State Ψ is assigned to Y = True.”
A specific planning problem specifies an initial state, with values specified for all state
variables, and a goal, specified values for one or more state variables. As for preconditions,
goals are conventionally positive, so the goal value for the goal variables is True. Generally,
the goal specifies values for only a small subset of the state variables. A plan is a sequence
of actions.
A valid plan, or a solution to the planning problem, is a sequence of actions A1 , ..., AL
such that the state at time step ti−1 meets the preconditions for action Ai , the effects of
action Ai are reflected in the state at time step ti , and the state at the end has all of the
goal variables set to True. For an introduction on Automated Planning and Scheduling, see
[Ghallab et al., 2004].
Planners: A planner is software implementing a collection of algorithms; it takes as input
a specification of domain and a problem description and returns a valid plan if one exists.
Many different approaches have been implemented to find a viable plan, among them: (i)
heuristically search over the possible valid plan trajectories or over the library of partial
plans or (ii) compile the planning problem into another combinatorial substrate (e.g., SAT,
MILP, CSP) and feed the problem to off-the-shelf solvers.

13

Planning Domain Description Language (PDDL): PDDL is a modeling language that was
originally created to standardize the input for planners competing in the International Planning Competition (IPC). Over time, it has become the de facto standard for modeling languages used by many domain-independent planners. We use PDDL 2.1, which allows the
modeling of temporal planning formulation in which every action a has duration da , starting time sa , and end time ea = sa + da . Action conditions cond(a) are required to be
satisfied either (i) instantaneously at sa or ea or (ii) required to be true starting at sa and
remain true until ea . Action effects eff (a) may instantaneously occur at either sa or ea .
Actions can execute when their temporally-constrained conditions are satisfied, and when
executed, will cause state-change effects. The most common objective function in temporal planning is to minimize the plan makespan, i.e. the shortest total plan execution time.
This objective matches well with the objective of our targeted quantum circuit compilation
problem. To enable reuse of key problem features present in an ensemble of similar instances, the PDDL model of a planning problem is separated into two major parts: (i) the
domain description that captures the common objects and behaviors shared by all problem
instances of this planning domain and (ii) the problem instance description that captures
the problem-specific objects, initial state, and goal setting for each particular problem.
PDDL is a flexible language that offers multiple alternatives for modeling a planning problem. These modeling choices greatly affect the performance of existing PDDL
planners. For instance, many planners pre-process the original domain description before
building plans; this process is time-consuming, and may produce large ‘ground’ models depending on how action templates were written. Also, not all planners can handle all PDDL
language features effectively (or even at all). For this project, we have iterated through different modeling choices with the objective of constructing a PDDL model that: (i) contains
a small number of objects and predicates for compact model size; (ii) uses action templates
with few parameters to reduce preprocessing effort; while (iii) ensuring that the model can
be handled by a wide range of existing PDDL temporal planners.
Modeling Quantum Gate Compilation in PDDL 2.1: To apply a temporal planner to the
circuit compilation problem, we must represent the allowed gates as actions and the desired
circuit as a set of goal variables. We describe how to do so for the QAOA circuit compilation problem exemplified in Fig. 3, ensuring that for a plan to be valid, the required P - S or
MIX gates are scheduled for each step of the algorithm. At the high-level, in this domain,
we need to model: (i) how actions representing P - S, SWAP, and MIX gates affect qubits and

14
(:constants q1 q2 q3 q4 q5 q6 q7 q8 - qstate)
(:durative-action swap 1 2
:parameters (?q1 - qstate ?q2 - qstate)
:duration (= ?duration 2)
:condition (and (at start (located at 1 ?q1))
(at start (located at 2 ?q2)))
:effect (and (at start (not (located at 1 ?q1)))
(at start (not (located at 2 ?q2)))
(at end (located at 1 ?q2))
(at end (located at 2 ?q1))))

(:durative-action mix q5 at 1
:parameters ( )
:duration (= ?duration 1)
:condition (and (at start (located at 1 q5))
(at start (GOAL PS1 q1 q5))
(at start (GOAL PS1 q5 q6))
(over all (not (mixed q5))))
:effect (and (at start (not (located at 1 q5)))
(at end (located at 1 q5))
(at end (mixed q5))))

(:durative-action P-S 2ndPhaseSeparation at 6-7
:parameters (?q1 - qstate ?q2 - qstate)
:duration (= ?duration 3)
(:durative-action P-S 1stPhaseSeparation at 6-7
:condition (and (at start (located at 6 ?q1))
:parameters (?q1 - qstate ?q2 - qstate)
:duration (= ?duration 3)
(at start (located at 7 ?q2))
:condition (and (at start (located at 6 ?q1))
(at start (not (GOAL PS2 ?q1 ?q2)))
(at start (located at 7 ?q2))
(at start (GOAL PS1 ?q1 ?q2))
(at start (not (GOAL PS1 ?q1 ?q2)))
(at start (mixed ?q1))
:effect (and (at start (not (located at 6 ?q1)))
(at start (mixed ?q2)))
(at start (not (located at 7 ?q2)))
:effect (and (at start (not (located at 6 ?q1)))
(at end (located at 6 ?q1))
(at start (not (located at 7 ?q2)))
(at end (located at 7 ?q2))
(at end (located at 6 ?q1))
(at end (GOAL PS1 ?q1 ?q2))
(at end (located at 7 ?q2))
(at end (GOAL PS1 ?q2 ?q1)))))
(at end (GOAL PS2 ?q1 ?q2))
(at end (GOAL PS2 ?q2 ?q1)))))
Figure 4. PDDL model of actions representing some exemple of SWAP, MIX, and P - S
gates. The first line indicates that this compilation problem involves 8 qubit states. For
each action, the duration indicates how long the action takes. The first action, a swap at
qubits 1 and 2, has as parameters the two qstates to swap. The condition checks that these
states are indeed located at the qubits on which the swap will occur. The effect makes sure
the states have been swapped. The second action mixes qstate q5 at qubit 1, with conditions
that state q5 is indeed at qubit 1, and both the phase separation gates involving qstate q5
(see Fig. 3) have been carried out. The effects include setting mixed q5 to TRUE The
third and fourth actions are phase separation actions in a p = 2 circuit corresponding to the
first and second levels of the algorithm.

15
qubit states (qstate); (ii) the actual qubits and qstates involved in a particular compilation
problem, with their initial locations and final goal requirements, (iii) the underlying graph
structure (gates connecting different pairs of qubits). We follow the conventional practice
of modeling (i) in the domain description while (ii) is captured in the problem description.
One common practice is to model (iii) within the problem file. However, given that we
target a rather sparse underlying qubit-connecting graph structure (see Fig. 2), we decide to
capture it within the domain file to ease the burden of the “grounding” and pre-processing
step for existing planners, which can be very time-consuming. Specifically:
Objects: We need to model three types of object: qubits, qstates, and the location of the P - S
and SWAP gates (i.e., edges in the multigraph of Fig. 2 connecting different qubits). Since
qstates are associated (by means of the predicate located at, see Fig. 4 for concrete example) to specific qubits, they have been modeled explicitly as planning objects, while the
qubits and the gate locations (i.e., edges) are modeled implicitly. It is clear from the action
definitions in Fig. 4 that qubit locations are embedded explicitly within the action declaration. This approach avoids declaring qubits as part of the action parameters, significantly
reducing the number of ground actions to be generated. For 2-qubit actions, the potential
number of ground actions reduces from N 4 to N 2 × |E|, with N the number of qubits
in the chip (up to 40) and E the set of connections between qubits. While it’s true that
many modern planners will be able to filter out invalid ground actions during the grounding/preprocessing step, our empirical evaluation shows that capturing the graph structure
explicitly in the domain file speeds up the preprocessing time of all tested planners, sometime as significantly as 40x.
Actions: Temporal planning actions are created to model: (i) 2-qubit SWAP gates, (ii)
2-qubit P - S gates, and (iii) 1-qubit MIX gates. For reference, Fig. 4 shows the PDDL
description of a SWAP gate between qubits 1 and 2, the MIX gate of state q5 on qubit 1,
and the P - S gates between qubits 6 and 7 at the first and second phase separation. § In the
action’s condition list, we specify that gates are accomplished on the two qstates only if they
are located on the corresponding qubits. Note that some planners (e.g., CPT, POPF) can not
handle action preconditions that are specified negatively (e.g., (overall(not(mixedq5))) of
action mix q5 at 1 in Figure 4). For those planners, we’ve also created another PDDL
version of our domain where dummy predicates such as not mixed is introduced to
represent the opposite value of those that need to be negatively satisfied in some action’s
§ The full set of PDDL model for all our tested problems is available at: https://ti.arc.nasa.gov/
m/groups/asr/planning-and-scheduling/VentCirComp17_data.zip

16
precondition list. To prevent a qstate q currently belonging to qubit X from being addressed
by multiple gates at the same time (i.e. “mutex” relations in planning terminology), we
assign value FALSE to the predicate (located at X q) at the starting time of all actions
involving q.
The most complex constraint to model is the conditions to mix a qstate q given the
requirement that all P - S gates involving q in the previous phase separation step have been
executed. We explored several other choices to model this requirement such as: (i) use a
metric variable P Scount(q) to model how many P - S gates involving q have been achieved
at a given moment; or (ii) use ADL quantification and conditional effect constructs supported in PDDL. Ultimately, we decided to explicitly model all P - S gates that need to be
achieved as conditions of the MIX(q) action. This is due to the fact that alternative options
require using more expressive features of PDDL2.1 which are not supported by many effective temporal planners.k
Objective: For a level p QAOA circuit, the goal is to have all of the (GOAL P Si ?q1 ?q2)
predicates, for any q1 and q2 connected in the graph, for 1 ≤ i ≤ p set to TRUE and all
mixedi qj set to true for 1 ≤ j ≤ N and 1 ≤ i ≤ p − 1 (since the final mixing step can be
added by hand at the end). Since we only consider p = 1 and p = 2, so only have a mixing
step in the p = 2 case, we have simplified the notation to simply mixed qj. Further, we use
the standard temporal planning objective of minimizing the plan makespan. Minimizing
the makespane coincides with minimizing the circuit depth, which is the main objective of
the compilation problem.
Alternative models: Given that non-temporal planners can perform much better than
temporal planners on problems of the same size, we also created the non-temporal
version of the domain by discretizing action durations into consecutive “time-steps”
ti , introducing additional predicates next(ti , ti+1 ) enforcing a link between consecutive
time-steps. However, initial evaluation of this approach with the M/Mp SAT-based
planner [Rintanen, 2012] (which optimize parallel planning steps) indicated that the
performance of non-temporal planners on this discretized (larger) model is much worse
than the performance of existing temporal planners on the original model.
k Only one of six planners in the Temporal track of the latest IPC (2014) supports numeric variables and also
only one of six supports quantified conditions. Preliminary tests with our PDDL model using metric variables
to track satisfied goals involving qstate q using several planners shows that they perform much worse than on
non-metric version, comparatively. This is to be expected as currently, state-of-the-art PDDL planners still
do not handle metric quantities as well as logical variables.

17
Another option is to totally ignore the temporal aspect and encode it as a “classical”
planning problem where actions are instantaneous. A post-processing step is then
introduced to inject back the temporal constraints and schedule actions in the found
classical plans. While we do not believe this approach would produce good quality plans,
it’s another promising option to scale up to larger problems in this domain.
5. Empirical Evaluation
We modeled the QAOA circuit compilation problem as described in the previous sections
and tested them using various off-the-shelf PDDL 2.1 Level 4 temporal planners. The results were collected on a RedHat Linux 2.4Ghz machine with 8GB RAM.
Problem generation: We consider three problem sizes based on grids with N = 8, 21 and
40 qubits (dashed boxes in Fig. 2). The utilized chip layouts are representative of devices
to come in the next 2 years¶
For each grid size, we generated two problem classes: (i) p = 1 (only one PS-mixing
step) and (ii) p = 2 (two PS-mixing steps). To generate the graphs G for which a MaxCut
needs to be found, for each grid size, we randomly generate 100 Erdös-Rényi graphs G
[Erdös and Rényi, 1960]. Half (50 problems) are generated by choosing N of N (N − 1)/2
edges over respectively 7, 18, 36 qstates randomly located on the circuit of size 8, 21, and
40 qubits (referred to herafter as ‘Utilization’ u=90%). The other half are generated by
choosing N edges over 8, 21, and 40 qstates, respectively (referred to herafter as ‘Utilization’ u=100%). In total, we report tests on 600 random planning problems with size in the
range [1024-232000] for the number of grounded actions and [192-8080] for the number
of predicates.
Planner setup: Since larger N and p lead to more complex setting with more predicates,
ground actions, requiring planners to find longer plans, the allocated cutoff time for
different setting are as follow: (i) 10 minutes per instance for N = 8, (ii) 30 minutes per
instance for P = 1, N = 21; (iii) 60 minutes per instance for other cases. The timelimits
are comparable to what used in the previous International Planning Competitions. We
select planners that performed well in the temporal planning track of previous IPCs, while
at the same time representing a diverse set of planning technologies:
¶ A gate-model 8-qubit chip with the grid we used is currently available from Rigetti, however the gate set
is currently uncalibrated or calibrated with different durations depending on the edges, so our benchmarks do
not model actual hardware.

18
• LPG: which is based on local search with restarts over action graphs [Gerevini et al.,
2003]. Specifically, LPG incrementally builds a multi-level graph structure. Each
layer represented by a single action and each graph edge represents a supporting
connection between one action’s effect with a condition of another action appearing
in a later layer. The graph leaf nodes represent action conditions that have not been
supported (i.e., “connected”) by other action effects. At the beginning of the search
process, LPG starts with a two-layer graph consisting of two newly created actions:
(i) Ainit : which occupies the first layer of the graph, has an empty condition list,
and has an effect list represents state variables that are true in the initial states; (ii)
Agoal : which occupies the last layer, has an empty effect list, and has a condition list
represents all goals. At each search step, LPG generates the local search neighborhood
by considering all decisions of either: (i) establishing a new edge connecting an
existing action’s effect with an open condition of another action appears in a later
layer (without conflicting with negative effects of other actions), (ii) removing an
edge from the existing graph; (iii) adding another action to the graph; (iv) removing
an action from the graph. Each resulting candidate partial (i.e., incomplete) plan in the
local search neighborhood is evaluated by a heuristic function balancing between how
close that candidate is from being a complete plan (i.e., fewer unsatisfied conditions)
and how good the quality of the likely complete plan starting from that candidate
partial plan based on the user’s defined objective function (e.g., minimizing the
plan makespan). LPG then selects the best candidate partial plan from the search
neighborhood and starts a new search episode. This process is repeated until a
complete plan is found. When LPG is run in the “anytime” mode, it does not stop
when the first complete plan is found, but will restart its planning process with the
found plan(s) used as the baseline quality comparison on the subsequent trials.
• Temporal FastDownward (TFD): a heuristic forward state-space (FSS) search planner
with post-processing to reduce makespan [Eyerich et al., 2009]. In the FSS framework,
the planner starts from the initial state I with an empty plan P and tries to extends P
until the state resulted from applying P satisfies all goals+ . In each search step, FSS
planners will generate new search nodes by taking a state SP = Apply(P, I), reached
from applying P to the initial state I, and considers all actions A applicable in SP (i.e.,
all conditions of A are satisfied by SP ). All newly generated states S 0 = Apply(A, SP )
are put in the search queue, ordered by the heuristically evaluated “quality” of S 0 . The
heuristic value evaluating a given state S generally depends on two factors: (i) the
+

This is in contrast to the backward state-space (BSS) planners, which build the plan “backward” starting
from the goals until it reaches the initial state.

19
quality of the partial plan leading from I to S, and (ii) the estimation on the quality of
the remaining plan leading from S to the goals. In TFD, the second part is estimated
through analyzing a set of special structure called the domain-transition graphs (DTG)
and causal-graph (CG) that are statically built for each planning problem∗ . After
a valid plan P is found, TFD also tries to improve the final plan makespan by
rescheduling actions in P , pushing them to start as early as possible without violating
the various logical and temporal constraints between different actions in P such as
causal supports and potential conflicts caused by actions’ negative effects. This postprocessing step is done greedily and takes little time compared to the planning process.
• SGPlan: partition the planning problem into subproblems that can be solved
separately, while resolving the inconsistencies between partial plans using extended
saddle-point condition [Wah and Chen, 2004] [Chen and Wah, 2006]. Specifically,
SGPlan uses a sub-goal partitioning strategy in which a high-level planning problem
is divided into smaller planning problems, each one targets a smaller subset of goals.
Furthermore, if a “landmark” (i.e., a given state or condition that needs to be visited
by all plans when solving a given problem) is found for a subset of the goals, that
landmark can be used to further partition a sub-planning problem into a subset of
secondary sub-problems. Thus, the original planning problem can be partitioned into a
hierarchy of multi-level interconnected smaller sub-problems, each with its own initial
state and set of goals. Each sub-problem can be solved by any off-the-shelf planner. In
particular, SGPlan uses a slightly modified Metric-FF, a forward state-space planner,
and an earlier version of LPG to solve sub-planning problems.
• CPT: uses the Partial Order Causal Link (POCL) framework, which once dominated
planning research. POCL planners search through the space of partial plans; each one
consists of a list of actions and the causal-link between them. A causal-link indicates
that an action’s effect is used to support another action’s condition. CPT [Vidal and
Geffner, 2006] utilizes techniques from constraint-programming to create (1) effective
branching scheme to select what action to consider next during each search step; (2) a
makespan-bound automatically extracted from the planning problem to set the horizon
for the solution search.
At the moment, CPT is one of the most effective temporal planners that can minimize
plan makespan.
∗ A directed edge in the DTG connects two values v and v 0 of a given state variable s in which there exist
an action a that can make the “transition” from v to v 0 by deleting v and add v 0 when executed. There is an
edge in CG connecting two DTGs associated with two state variables s and s0 if there is an action a that has
a condition depends on s and an effect causing change of the value of s0 .

20

Utilization u
LPG
TFD
SGPlan
POPF
CPT

P1
P2
N8
N21
N40
N8
N21
0.9 1.0 0.9 1.0 0.9 1.0 0.9 1.0 0.9 1.0
50 50 50 50 10 14 50 50 50 50
50 50 50 50
50 50 50 50
50 50 50 50 50 50 50 50
50 50 48 50
8
19 50 50
4
6
50 50
-

Table 1. Summary of the solving capability of selected planners. Numbers indicate how
many random problems out of 50 have been solved.

• POPF: is a forward-chaining planner that combines forward-state-space search
framework with ideas from the POCL planning framework. In POCL planning, a
new action is a threat to a causal link if it removes the condition the action introduces
in support of another action. During the forward search, when applying an action to a
state, POPF [Coles et al., 2010] seeks to introduce only the ordering constraints needed
to resolve threats, rather than insisting the new action occurs after all of those already
in the plan. POPF mostly uses the relaxed-plan heuristic similar to other forward statespace planners, but has a dedicated Simple Temporal Network (STN) implementation
to handle the temporal constraints incurred from temporal actions interleaving in the
explored partial plans. Besides temporal constraints, POPF can also handle linear
continuous numeric effects on resources. It does so by offloading those constraints to
a dedicated MILP solver.
We ran SGPlan (Ver 5.22), TFD (Ver IPC2014), POPF, and CPT (latest versions at
time of writing) with their default parameters. Unlike other planners, which support a single mode, LPG (Ver TD 1.0) has three standard modes, which we all ran to collect empirical
results: (i) -speed that uses heuristic geared toward finding a valid plan quickly, (ii) -quality
that uses heuristic balancing plan quality and search steps, and (iii) -n 10 (k = 10) that will
try to find within the time limit up to 10 plans of gradually better quality by using the
makespan of previously found plan as upper-bound when searching for a new plan. Since
LPG (k = 10) option always dominates both LPG-quality and LPG-speed by solving more
problems with better overall quality for all setting, we will exclude results for LPG-quality
and LPG-speed from our evaluation discussion. For the rest of this section, LPG result is
represented by LPG (k = 10).

21

Utilization u
LPG
TFD
SGPlan
POPF

p=1, N8
0.9
1.0
0.88 0.89
0.87 0.87
0.67 0.68
0.81 0.81

p=1, N21
0.9
1.0
0.91 0.87
0.95 0.90
0.64 0.67
0.90 0.94

p=2, N8
0.9 1.0
0.50 0.52
0.99 0.99
0.75 0.79
0.87 0.91

Table 2. Plan quality comparison between different planners using IPC formula (higher
value indicates better plan quality). Highlighted results represent the best performance
in the problem class. CPT results for N=8 p=1 are proven optimal so they are implicitly
assigned 1.0.

Evaluation Result Summary: Table 1 shows the overall performance on the ability to
find a plan of different planners. SGPlan stops after finding one valid plan while TFD,
LPG, and POPF are “anytime” planners that exhaust the allocated time limit and try to find
gradually improving quality plans. While CPT can find multiple plans, it does not return
any until it can prove that the plan found is optimal. Since no planner was able to find a
single solution for N = 40 and p = 2 within the 60 minute cutoff, we omit the result for
this case from Table 1. Overall, LPG was able to solve the highest number of problems,
followed by TFD, SGPlan, and POPF. Being an optimal-guarantee planner, CPT can only
solve the smallest problem set (N = 8, p = 1) and can not find any solution for the other
sets. SGPlan can find a solution very quickly, compared to the time it takes other three
other anytime planners to find the first solution. It is the only planner that can scale up and
solve all 100 problem in the N = 40 for p = 1 (finding plans with 150-220 actions). Unfortunately, SGPlan stopped with an internal error for N = 21 and p = 2. TFD generally spent
a lot of time on preprocessing for p = 1, N = 21 (around 15 minutes) and p = 2, N = 21
(around 30 minutes) but when it is finished with the pre-processing phase] it can find a
solution quickly and also can improve the solution quality quickly. TFD spent all of the
60 minutes time limit on pre-processing for N = 40 problems. LPG can generally find
the first solution more quickly than POPF and much faster than TFD (but still much more
slowly than SGPlan) but does not improve the solution quality as quickly as TFD or POPF.
Plan quality comparison: to compare the plan quality across planners, we use the formula
] The two most time-consuming parts in TFD’s pre-processing routine are “processing axioms” and
“invariant analysis”. While “processing axioms” are always consistently time-consuming, “invariant
analysis” is heuristically done and sometime can be quick while some other times can be very time
consuming.

22
■

45

35
30
25
20

makespan (CPT□ TFD■ LPG■ POPF■ SGPlan■)

15
10
10

■

■
■
■ ■
■ ■ ■
■ ■■■
■ ■
■ ■ ■■
■ ■
■■ ■
■■■ ■■■
■ ■
■■ ■■■
■■ ■ ■■
■ ■■■■
■■■■■■
■■■ ■ ■■
■■■■ ■
■■■
■■
■■■
□
■■
■■
■ ■■□
□□□■
□□□
■■■
■■
■■□□□
■□
■□□
□
■□
■□□□
■■□□ □
■□ □
□□□
□□ □ □

40

15

20

25

■

□
□

100

80

60

40

20
20

100

80

60

40

20
20

■

■
■

■

■
■

■

■ ■
■

■
■
■
■
■ ■
■ ■
■ ■ ■
■■
■■■
■
■
■ ■■ ■ ■■
■ ■ ■ ■■ ■
■ ■■ ■ ■ ■■
■■ ■ ■■■■ ■■
□ ■ ■■■■■
■■ ■■
□■ □□
■■ ■■■□
■■
■
■■
□□■□
■ □
■ □□□
□□
■ □ □
■□
■□□ □
□
■ □□ □ □
□ □
□□

□

30

35

40

45

15

20

25

■

■

■

■■■
■
■■■
■
■■
□□□
■
□
■□□
□

30

■
■

■
■

■

■

□

□

35

□

■
■
■

□

40

45

15

■

■

■
■■
■
■
■ ■ ■ ■
■
■■ ■ ■
■
■ ■■■ ■■■
■
■ ■■■ ■■■■■■■ ■■■
■
■■ ■ ■ ■
■ ■■■
■
■ ■■ ■■■■ ■
■
■
■
■
■
■
■■■■■
■■■ ■■■■ ■■■ ■ ■
■■
■■■■ ■
■■
■■■ ■
■■■
■■■ ■
■
■
■■

60

80

makespan TFD

100

120

■

■■■
■■■■ ■
■■ ■■■ ■
■ ■■
■■■■■■■■■
■■
■■■ ■■
■■■
■■
■■■■■
■
■■ ■
■
■■
■■■
■■
■■ ■ ■
■
■■■■■■
■■
■■■
■
■■ ■
■
■■
■■■■■
■■■■ ■
■■■
■■■■
■■■
■■
■■■
■■■
■
■
■
■■■
■
■
■
■
■
■
■
■
■■ ■■
■
■

■

■ ■
■
■
60

80

makespan TFD

40

60

■
■

100

100

120

■

■
■ ■
■
■ ■■■ ■■
■
■■ ■ ■
■
■■■ ■■■■
■
■■
■
■
■
■■ ■
■
■■■■ ■■ ■■ ■■ ■■
■■■
■ ■■■ ■
■■■
■ ■■ ■■■
■■
■■■ ■
■■
■
■
■
■
■■■ ■■■ ■
■ ■■
■■
■
■ ■ ■■
■■■■■ ■■
■■■ ■ ■
■
■
■ ■ ■■ ■ ■
■
■
■■
■

40

■■

■

■■
■■
■■■ ■
■

60

makespan LPG

25

30

35

40

15

45

■

■

■

■

80

■
■
■
100

60

80

makespan POPF

100

120

60

40

30

35

40

■

■

■

45

■

60

80

100

makespan SGPlan
■

■
■ ■ ■
■
■■■
■■
■
■
■
■
■
■ ■■■■ ■ ■
■■■ ■■ ■
■
■
■■
■■■■■■
■ ■■ ■
■■
■
■
■■■
■■■■■■■
■
■
■■■
■■ ■
■■
■■■
■■■■
■
■■■ ■■■
■
■■■
■ ■
■■
■■■■ ■
■■■ ■
■ ■■■
■
■■
■
■■■
■
■
■ ■
■
■■
■■■■■
■
■
■■■■■■
■ ■■
■
■■■■■■
40

25

■

□
■

■■
■
■■
■ ■■
■ ■ ■■■■ ■
■
■■■■■ ■■ ■
■ ■
■■ ■■■ ■■
■
■■■ ■■ ■■
■
■ ■
■■ ■ ■
■ ■■■
■
■ ■■■■ ■ ■■ ■
■
■
■
■
■
■
■
■■ ■■■■
■■
■■
■■
■■ ■
■■
■■■■■■
■■■■■■■ ■■
■■■■■■■■■■■
■
■

■ ■ ■
■■
■ ■
■ ■■■ ■■
■■ ■
■
■
■
■■■■
■
■■ ■■■ ■■
■ ■■■■ ■■■■
■ ■■■■ ■
■■ ■ ■■■
■ ■■■
■■■ ■■■
■ ■■■ ■
■■
■■■■■■
■
■■■■■
■■
■■■■
■■■■■■■
■
■
■
■■■
■ ■■
■
■
■
■■■ ■
40

20

■

makespan SGPlan

■
■

■

■

■

80

makespan LPG

■

■

■

40

■

■
■

■

40

20

■
■
■
■■■
■■
■■
■
■ ■ ■ ■
■
■■
■ ■
■ ■■■■■■ ■■■ ■
■■■ ■■■ ■■ ■■■
■■■ ■■■■■
■ ■
■ ■■■ ■■■ ■■■
□■
■ ■■■ ■■■□
■ ■
□□
□□ ■□ □
□
■ ■■■ ■□
■
■■
■
□ □
■■
■
■□■ ■
■□ □□□□
■
□
□■□ □■
□□ □
■■
■□ □ □
□
□
■□□□
■□
□
□
□

■

□

■

■
■
■
■ ■

■
■
■
■
■■
■
□

makespan POPF

■

■■■ ■
■ ■■■
■■
■■■
■■
■
■■■ ■■
■ ■■■■■■ ■ ■
■■ ■■■■■
■
■■■■■
■■■
■■
■■
■■■■
■■■■■■
■■■
■■
■■■
■ ■■
■■
■■
■■■■
■
■
■
■■
■■■■■■
■■■■■
■■■■■
■■■■
■

■

■

■
■
■■
■ ■
■
■■■
■■
■ ■■
■■ ■
■■
■ ■ ■
■ ■■■■■ ■
■ ■ ■■■
■■■ ■
■ ■ ■■■
■■ ■■■■■
■■■
■ ■■■■■
■ ■■
■■■ ■■■
■■ ■■■■
■
■■■□
■ ■ □
□
□
■□
■■□
■□■□□
■ ■
□
■■■□
■■
■ □
■□□ □
□□
□□
□□
■■
■■
■■
□ □□ □
■□
■□
□ □
□□□

makespan LPG

makespan TFD

120

■

■

■
■

120

■

■■

■ ■

■■
■
■
■ ■■ ■ ■ ■
■
■■■ ■■■■ ■■■
■
■
■ ■
■■ ■■
■ ■■■■ ■■
■ ■ ■■■■■■
■■■■■
■■■■■■■
■ ■ ■■
■■■
■■■■
■
■■
■
■■■■■■■■
■■
■■
■■
■■■
■■
■ ■
■
■
■
■
■
■
■ ■■ ■■■■■■■■
■■■■
■ ■■ ■
■
■■■ ■■
■■ ■ ■
■
■
■
80

makespan POPF

100

40

60

80

100

makespan SGPlan

Figure 5. Instance-by-instance makespan comparison of the used planners on the problem
set for u=1.0 (results for u=0.9 are qualitatively similar). Scatterplots indicate on the xaxis a specific planner, compared on the y axis against another planner (color code in the
legend). The dashed line indicate equal makespan. The first row of plots shows N =8, p=1;
the second row N =8, p=2; the third row N =21, p=1.

employed by the IPCs to grade planners in the temporal planning track since IPC6 [Helmert
et al., 2008]: for each planning instance i, if the best-known makespan is produced by a
plan Pi , then for a given planner X that returns a plan PXi for i, the score of PXi is calculated
as: makespan(Pi ) divided by makespan(PXi ). A comparative value closer to 1.0 indicates
that planner X produces better quality plan for instance i. We use this formula and average
the score for our three tested planners over the instance ensembles that are completely

23
solved by the time cutoff. Table 2 shows the performance of different planners with regard
to plan quality. For N = 8 and p = 1, for which we know the optimal plans given that
CPT was able to solve all 100 problems, LPG found the best quality plans but TFD is only
slightly worse and POPF is not far behind.
The comparison results for N = 21 and p = 1 is similar in the sense that the three
anytime planners LPG, TFD, and POPF perform very similarly but in this case TFD and
POPF are slightly better than LPG. For N = 8 and p = 2, TFD nearly always produce the
best quality plan with POPF slightly behind while LPG perform significantly worse. The
mixing and the requirement to synchronize the two phase-separation seems to confuse the
local search heuristic in LPG. SGPlan, which unlike TFD, LPG, POPF only find a single
solution, produce lower quality plans, as expected. However, for the p = 2 case, SGPlan
produces overall better quality plans compared to LPG, even though LPG returns multiple
plans for each instance.
Fig. 5 shows in further detail the head-to-head makespan comparison between
different pairs of planners, specifically pairwise comparisons between TFD, SGPLan, LPG,
and POPF: TFD always dominates SGPlan, TFD dominates LPG majority of the times
(except for N = 8, p = 1 where the performances are comparable), and SGPlan dominates
LPG on bigger problems, but is slightly worse on smaller problems. POPF performance in
general is very similar with the one of TDF, especially for N = 8.
For a more detailed analysis with data reported for each specific instance, see [NASA,
2017].
Planning time comparison: Both TFD, LPG, and POPF use “anytime” search algorithms
and use all of their allocated time to try finding better gradually better quality plans. In contrast, SGPlan return a single solution and thus generally take a very short amount of time
with the median solving time for SGPlan in p=1|N8 , p=1|N21 , P =1|N40 and P =2|N8 are
0.02, 1, 25, and 0.05 seconds††. CPT, in general, set a very tight upper-bound on makespan
before trying to find a plan within the bound and prove that the solution is optimal. For the
smallest problem set when it can solve all 100 instances, it took a very short time between
1 to 2 seconds to find and prove optimality. However, for any other bigger set, its tight
upper bounds proven to be ineffective in finding a single solution.
Other planners: We have also conducted tests on: VHPOP, HSP*, and YASPH. While
LPG, SGPlan, TFD, and POPF were selected for their ability to solve large planning prob†† For comparison purpose, LPG-quality, which also try to returns a single solution of good quality, produces
the median solving time for P =1|N8 and P =2|N8 are 0.9 and 70 seconds respectively.

24
lems, we hoped that HSP* and VHPOP would return optimal plans to complement CPT in
providing a baseline for plan quality estimation. Unfortunately, HSP* and VHPOP failed
to find a single plan even for our smallest problems for various reason: VHPOP ran out
of memory quickly, while HSP* couldn’t find any plan for a cutoff time of 2 hours. We
have preliminary acceptable results with YAHSP up to N=40 but they will be discussed in
a future work.
Discussion: Our preliminary empirical evaluation shows that the test planners provide a
range of tradeoffs between scalability and plan quality. At one end, SGPlan can scale up to
large problem sizes and solve them in a short amount of time, providing reasonably good
quality plans (compared to the best known solutions). At the other end, TFD utilizes all
of the allocated time to find the best quality solutions but in general is the slowest by far
to obtain a valid solution. LPG and POPF balance between the two: they can either find
one solution quickly like SGPlan or can utilize the whole time prior to cutoff to find better
quality solutions.
Since planning is exponentially hard with regard to the problem size (i.e., number
of state variables and actions), being able to partition it into sub-problems of smaller
sizes definitely helps SGPlan to be find a valid solution quickly. However, there are
several reasons that TFD, LPG, and POPF can find overall better quality solutions: (i)
their anytime algorithms allow them to gradually find better quality plans, using the
previously found plans as baseline for pruning unpromising search directions; (ii) SGP’s
partitioning algorithm is based on logical relationship between state variables and actions
and ignores all temporal aspects. Thus, combining plans for sub-problems using logical
global constraints can lead to plans of lower quality for time-sensitive objective function
such as minimizing the plan makespan.
Fig. 6 shows a visualization of plans in a ‘Gantt chart’ format, putting the planners in
comparison for a single N =8 instance from Fig. 3. To illustrate the representation, we can
look at the shown p=2 case: consider the, qstate q1 initially located at n1 . The first gate it
is involved in is the phase separation gate shown in green between qstates q1 and q4. The
second gate is a phase separation gate between qubits 1 and 2 which contain qstates q1 and
q3 respectively, because states q2 and q3 were swapped in the previous step. State q1 is
then swapped with the state in qubit 2, prior to being involved in another phase separation
gate, between the contents of qubits 2 and 3, this time with state q5 that was swapped into
qubit 3 during time steps 3 − 4. It is then mixed while still located at qubit 2. Continuing to
read through the chart in this way, we see that qstate q1 undergoes the following sequence

25
n1
n2
n3
n4
n5
n6
n7
n8
n1
n2
n3
n4
n5
n6
n7
n8
n1
n2
n3
n4
n5
n6
n7
n8
n1
n2
n3
n4
n5
n6
n7
n8

POPF
■
■

■
■

■

■

■
■

■

■

■
■

n1
n2
n3
n4
n5
n6
n7
n8

■

■

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
SGPlan

■
■

■

■
■

■

■

■

LPG
■
■
■

■
■

■

■

■
■

■
■

■

■

■
■
■

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

■
■

■

■
■

■

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
TFD
■
■

■
■
■
■

■

■
■

■

■

n1
n2
n3
n4
n5
n6
n7
n8

■

■

■

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
TFD p=2
■
■

■
■

■
■

+

■
■

1
■

3
■
■

5

■
4

■
■

CPT
■
■

■
■
■
■

■

■

■

■

■

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

■

7

■

■
■

■

■

■
■

+
■
+
■

+
■
+
■

■
■

+
+
■
■
■
■
+
+
+
■
■
■
■
■ 6 ■
■
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

Figure 6. The Gantt charts show compilations, labeled for each planner of the QAOA for
the MaxCut instance depicted in Fig. 3 on the N=8 processor in Fig. 2. Schedules have time
on the x-axis and qubit locations on the y-axis. Each row indicates what gate operates on
each qubit at a given time during the plan (Colored blocks represents p-s gates, of duration
3 or 4 depending on their location, with synchronized pair colors associated to edges in
Fig. 3 and white blocks are swap gates). The last schedule shows a compilation of p = 2
performed by TFD. Black blocks with numbers are mix gates acting on the corresponding
state. Gates marked with a + indicate superfluous gates that were inserted in the plan by
TFD, that could be detected and eliminated in post-processing.

26
of actions:
P - S 3 (q1 , q4 )

→ P - S3 (q1 , q3 ) → P - S4 (q1 , q5 ) →

→

→ P - S4 (q1 , q5 ) →

WAIT(4)

→ P - S3 (q1 , q3) →

WAIT(3)

MIX (q1 )

WAIT (2)

→ P - S3 (q1 , q4 )

where we denote the duration of the P - S gates in subscript and we introduced an WAIT gate
to indicate inaction times. The second mixing phase is trivially scheduled at the end of the
last tasks for each qstate.
In the shown case, TFD has found an optimal solution (same makespan as CPT).
Based on an “eye-test” and manual analysis, the best plans returned are usually of
good quality but not without defects. Note also that the plan found by TFD for p=2 is also
worse than the one that would be trivially obtained by replicating the optimal makespan
p=1 solution twice (the second time in reverse). The displayed output also contains some
unnecessary gates. Examples are the repeated swaps at time 11 and 30, and the mixing
of the un-utilized logical states q2 and q8 at times 1,5. These spurious gates/actions do
not affect the makespan, and they can be identified and eliminated by known plan postprocessing techniques [Do and Kambhampati, 2003]. We also believe a tighter PDDL
model will help eliminate extra gates.
6. Conclusion and Future Work
In this paper we presented a novel approach to the problem of compiling idealized quantum
circuits to specific quantum hardware, focusing our experiments on QAOA circuits. Our
presentation and tests have been focused on the pedagogical and practically relevant
example of MaxCut, but the approach is sufficiently general to be applied to QAOA circuits
for any discrete optimization problem, and to arbitrary quantum circuits more generally.
Because QAOA has so many commuting gates, we expect to obtain a bigger win for this
sort of algorithm than typical quantum algorithms. For most circuits, however, the problem
of determining which swaps to make when to ensure that the qstates are next each other
in order to carry out the desired gate sequence is highly non-trivial. Many swaps can be
done in parallel, and ideally would place qstates in such a way that multiple gates can be
carried out before having to swap again, or more generally in a way so as to minimize the
run time of the circuit. For these reasons, we expect the temporal planning approach to
enable significant gains over a brute force for circuits generally.
A handful of well-established temporal planners were able to compile the QAOA
circuits with reasonable efficiency, demonstrating the viability of this approach. We plan

27
to expand the portfolio of plannes we have tested, keeping up with latest AI planning
technology; the data used in our tests, as well as the PDDL models, will be made available
online at [NASA, 2017].
One thing that will be expanded in our analysis is the assessment of the quality
of the best plans found compared to optimal solutions. At the moment, there is no
published work on finding optimal solution for this problem and, as outlined in the
previous section, our current effort to get existing optimal-makespan planners to find
solutions has been successful only for N = 8, p = 1. Another important direction is to
support circuit optimization beyond the makespan objective: for instance there is currently
tremendous interest in the definition of figure-of-merits that could quantify the power of
near-term quantum devices to execute experiment of interests (i.e. quantum supremacy
experiments) [Bishop et al., 2017].
This work paves the way for future work on the use of AI planning methods for
quantum circuit compilation and design. In future work, we plan to further tune the
performance of the planners, including choosing an initial assignment of qstates to qubits
favorable for compilation, instead of using a random assignment. In order to scale reliably
to QAOA circuits with more levels and therefore larger plan sizes, we will develop
decomposition approaches in which p ¿ 1 could be divided into multiple p = 1 problems to
be solved independently and matched in a postprocessing phase. Initial results show that
the advantage of not decomposing the problem amounts to approximately 10% of reduction
of the makespan on average, and more than half of the test instances can be scheduled
optimally by focusing on the p = 1 problem.
We will also compare with other approaches to this compilation problem such as
sorting networks [Beals et al., 2013] [Brierley, 2015] [Bremner et al., 2016], constraint
programming (CP), or tailored scheduling heuristics [Guerreschi and Park, 2016] and
develop more advanced hybrid compilation methods building on the various strengths
of the temporal planning approaches and of other approaches. Once mature we will
integrate compilation with other software supporting experimentation with various nearterm processors. A virtue of the planning approach is that the temporal planning framework
is very flexible with respect to features of the hardware, including irregular graph structures
and diverse gate durations.
In the future, we can include in the PDDL modeling additional features that are
characteristics of quantum computer architectures, such as the crosstalk effects of 2-qubit
gates, realistic durations from optimal 2-qubit gate synthesis that could allow P - S and
SWAP gates to be performed as a single gate, or the ability to quantum teleport quantum
states across the chip [Copsey et al., 2003], and features of broad classes of quantum

28
algorithms including measurement and feedback, error correction, and fault tolerant gate
implementations. As hardware graphs, primitive gate sets, and gate durations for processors
build by experimental groups become available, we will apply this temporal planning
approach with these hardware parameters as input. Conversely, results from future work
comparing results of compilation to different potential architectures may suggest hardware
designs that take into account the ability to support efficient compiled circuits.
We will also consider other families of quantum circuits, including QAOA circuits
applied to problems beyond MaxCut [Hadfield et al., 2017], and to more typical quantum
circuits, with fewer pairwise commuting gates, but for which it remains difficult to fine
an optimal sequence of swap and goal gates. This temporal planning approach to quantum
circuit compilation should be of great interest to the community developing low-level quantum compilers for generic architectures [Steiger et al., 2016b] [Häner et al., 2016] and to
designers of machine-instructions languages for quantum computing [Smith et al., 2016b]
[Cross et al., 2017].

7. Acknowledgements
The authors acknowledge useful discussions with Will Zeng, Robert Smith, and Bryan
O’Gorman. The authors appreciate support from the NASA Advanced Exploration Systems program and NASA Ames Research Center (Sponsor Award No. NNX12AK33A and
contract No. NNA16BD14C). The views and conclusions contained herein are those of the
authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the U.S. Government. The U.S. Government is
authorized to reproduce and distribute reprints for Governmental purpose notwithstanding
any copyright annotation thereon.
[Barends et al., 2016] Barends, R., Shabani, A., Lamata, L., Kelly, J., Mezzacapo, A., Heras, U. L., Babbush,
R., Fowler, A. G., Campbell, B., Chen, Y., et al. (2016). Digitized adiabatic quantum computing with a
superconducting circuit. Nature, 534(7606):222–226.
[Beals et al., 2013] Beals, R., Brierley, S., Gray, O., Harrow, A. W., Kutin, S., Linden, N., Shepherd, D.,
and Stather, M. (2013). Efficient distributed quantum computing. Proceedings of the Royal Society A.,
469(2153):767 – 790.
[Bhattacharjee and Chattopadhyay, 2017] Bhattacharjee, D. and Chattopadhyay, A. (2017). Depth-optimal
quantum circuit placement for arbitrary topologies. arXiv preprint arXiv:1703.08540.
[Bishop et al., 2017] Bishop, L., Bravyi, S., Cross, A., Gambetta, J., and Smolin, J. (2017). Quantum
volume. https://ibm.biz/BdiaQe.

29
[Boxio, 2016] Boxio, S. (2016). Characterizing quantum supremacy in near-term devices. In arXiv preprint
arXiv:1608.0026.
[Bremner et al., 2016] Bremner, M. J., Montanaro, A., and Shepherd, D. J. (2016). Achieving quantum
supremacy with sparse and noisy commuting quantum computations. arXiv preprint arXiv:1610.01808.
[Brierley, 2015] Brierley, S. (2015). Efficient implementation of quantum circuits with limited qubit
interactions. arXiv preprint arXiv:1507.04263.
[Caldwell et al., 2017] Caldwell, S., Didier, N., Ryan, C., Sete, E., Hudson, A., Karalekas, P., Manenti, R.,
Reagor, M., da Silva, M., Sinclair, R., et al. (2017). Parametrically-activated entangling gates using
transmon qubits. arXiv preprint arXiv:1706.06562.
[Chen and Wah, 2006] Chen, Y. and Wah, B. (2006). Temporal planning using subgoal partitioning and
resolution in sg-plan. Journal of Artificial Intelligence Research, 26:323 – 369.
[Chong et al., 2017] Chong, F. T., Franklin, D., and Martonosi, M. (2017). Programming languages and
compiler design for realistic quantum hardware. Nature, 549(7671):180–187.
[Coles et al., 2010] Coles, A. J., Coles, A. I., Fox, M., and Long, D. (2010). Forward-chaining partialorder planning. In Proceedings of the Twentieth International Conference on Automated Planning and
Scheduling (ICAPS-10).
[Copsey et al., 2003] Copsey, D., Oskin, M., Impens, F., Metodiev, T., Cross, A., Chong, F. T., Chuang, I. L.,
and Kubiatowicz, J. (2003). Toward a scalable, silicon-based quantum computing architecture. IEEE
Journal of selected topics in quantum electronics, 9(6):1552–1569.
[Cross et al., 2017] Cross, A. W., Bishop, L. S., Smolin, J. A., and Gambetta, J. M. (2017). Open quantum
assembly language. arXiv preprint arXiv:1707.03429.
[Devitt, 2016] Devitt, S. J. (2016). Performing quantum computing experiments in the cloud. Physical
Review A, 94(3):222–226.
[Do and Kambhampati, 2003] Do, M. B. and Kambhampati, S. (2003). Improving the temporal flexibility
of position constrained metric temporal plans. In Proceedings of the 13th International Conference on
Artificial Intelligence Planning and Scheduling (ICAPS).
[Erdös and Rényi, 1960] Erdös, P. and Rényi, A. (1960). On the evolution of random graphs. Publications
of the Mathematical Institute of the Hungarian Academy of Sciences, 5:569–573.
[Eyerich et al., 2009] Eyerich, P., Mattmüller, R., and Röger, G. (2009). Using the context-enhanced additive
heuristic for temporal and numeric planning. In Proceedings of the 19th International Conference on
Automated Planning and Scheduling, pages 318 – 325.
[Farhi et al., 2014a] Farhi, E., Goldstone, J., and Gutmann., S. (2014a). A quantum approximate
optimization algorithm. In arXiv preprint arXiv:1411.4028.
[Farhi et al., 2014b] Farhi, E., Goldstone, J., and Gutmann., S. (2014b). A Quantum Approximate
Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem. In arXiv preprint
axXiv:1412.6062.
[Farhi et al., 2017] Farhi, E., Goldstone, J., Gutmann, S., and Neven, H. (2017). Quantum algorithms for
fixed qubit architectures. arXiv preprint arXiv:1703.06199.
[Farhi and Harrow, 2016] Farhi, E. and Harrow, A. W. (2016). Quantum supremacy through the quantum
approximate optimization algorithm. In arXiv preprint arXiv:1602.07674.
[Fu et al., 2005] Fu, C., Wilken, K., and Goodwin, D. (2005). A faster optimal register allocator. The
Journal of Instruction-Level Parallelism, 7:1 – 31.
[Gerevini et al., 2003] Gerevini, A., Saetti, L., and Serina, I. (2003). Planning through stochastic local search
and temporal action graphs. Journal of Artificial Intelligence Research, 20:239 – 290.

30
[Ghallab et al., 2004] Ghallab, M., Nau, D., and Traverso, P. (2004). Automated Planning: theory and
practice. Elsevier.
[Guerreschi and Smelyanski, 2017] Guerreschi, G. and Smelyanski, M. (2017). Practical optimization for
hybrid quantum-classical algorithms. In arXiv preprint arXiv:1701.01450.
[Guerreschi and Park, 2016] Guerreschi, G. G. and Park, J. (2016). Gate scheduling for quantum algorithms.
arXiv preprint arXiv:1612.08208.
[Hadfield et al., 2017] Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., and Biswas, R.
(2017). From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator
Ansatz. ArXiv e-prints.
[Häner et al., 2016] Häner, T., Steiger, D. S., Svore, K., and Troyer, M. (2016). A software methodology for
compiling quantum programs. arXiv preprint arXiv:1604.01401.
[Helmert et al., 2008] Helmert, M., Do, M., and Refanidis, I. (2008). The 2008 international
planning competition: Deterministic track. http://icaps-conference.org/ipc2008/
deterministic/. 2008-02-19.
[IBM, 2017a] IBM (2017a). The ibm quantum experience. http://www.research.ibm.com/
quantum/. 2017-02-19.
[IBM, 2017b] IBM (2017b). Ibm quantum experience ibmqx3 backend specifications. https:
//github.com/QISKit/ibmqx-backend-information/tree/master/backends/
ibmqx3.
[Jiang et al., 2017] Jiang, Z., Rieffel, E., and Wang, Z. (2017). A qaoa-inspired circuit for grover’s
unstructured search using a transverse field. In arXiv preprint arXiv:1702.0257.
[Kole et al., 2017] Kole, A., Datta, K., and Sengupta, I. (2017). A new heuristic for n-dimensional nearest
neighbor realization of a quantum circuit. IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems.
[Moll et al., 2017] Moll, N., Barkoutsos, P., Bishop, L. S., Chow, J. M., Cross, A., Egger, D. J., Filipp, S.,
Fuhrer, A., Gambetta, J. M., Ganzhorn, M., Kandala, A., Mezzacapo, A., Müller, P., Riess, W., Salis, G.,
Smolin, J., Tavernelli, I., and Temme, K. (2017). Quantum optimization using variational algorithms
on near-term quantum devices. ArXiv e-prints.
[NASA, 2017] NASA (2017). Repository with complementary materials for the reproduction of the
tests of the paper (pddl files and instances). https://ti.arc.nasa.gov/m/groups/asr/
planning-and-scheduling/VentirComp17_data.zip.
[Ramasesh et al., 2017] Ramasesh, V., O’Brien, K., Dove, A., Kreikebaum, J. M., Colless, J., and Siddiqi, I.
(2017). Design and characterization of a multi-qubit circuit for quantum simulations. In March Meeting
2017. American Physical Society.
[Reagor et al., 2017] Reagor, M., Osborn, C., Tezak, N., Staley, A., Prawiroatmodjo, G., Scheer, M.,
Alidoust, N., Sete, E., Didier, N., da Silva, M., et al. (2017). Demonstration of universal parametric
entangling gates on a multi-qubit lattice. arXiv preprint arXiv:1706.06570.
[Rintanen, 2012] Rintanen, J. (2012). Planning as satisfiability: Heuristics. Artificial Intelligence, 193:45 –
86.
[Schuch and Siewert, 2003] Schuch, N. and Siewert, J. (2003). Natural two-qubit gate for quantum
computation using the xy interaction. Physical Review A, 67(3):032301.
[Sete et al., 2016] Sete, E. A., Zeng, W. J., and Rigetti, C. T. (2016). A functional architecture for scalable
quantum computing. In , IEEE International Conference on Rebooting Computing (ICRC).
[Smith et al., 2016a] Smith, R. S., Curtis, M. J., and Zeng, W. J. (2016a). A practical quantum instruction

31
set architecture. In arXiv preprint arXiv:1608.03355.
[Smith et al., 2016b] Smith, R. S., Curtis, M. J., and Zeng, W. J. (2016b). A practical quantum instruction
set architecture. arXiv preprint arXiv:1608.03355.
[Steiger et al., 2016a] Steiger, D. S., Häner, T., and Troyer, M. (2016a). Projectq: An open source software
framework for quantum computing. In arXiv preprint arXiv:1612.08091.
[Steiger et al., 2016b] Steiger, D. S., Häner, T., and Troyer, M. (2016b). Projectq: An open source software
framework for quantum computing. arXiv preprint arXiv:1612.08091.
[Vatan and Williams, 2004] Vatan, F. and Williams, C. (2004). Optimal quantum circuits for general twoqubit gates. Phys. Rev. A, 69:032315.
[Versluis et al., 2016] Versluis, R., Poletto, S., Khammassi, N., Haider, N., Michalak, D., Bruno, A., Bertels,
K., and DiCarlo, L. (2016). Scalable quantum circuit and control for a superconducting surface code.
arXiv preprint arXiv:1612.08208.
[Vidal and Geffner, 2006] Vidal, V. and Geffner, H. (2006). Branching and pruning: An optimal temporal
pocl planner based on constraint programming. Artificial Intelligence Journal, 170(3):298335.
[Wah and Chen, 2004] Wah, B. and Chen, Y. (2004). Subgoal partitioning and global search for solving
temporal planning problems in mixed space. International Journal on Artificial Intelligence Tools,
13(4):767 – 790.
[Wang et al., 2017] Wang, Z., Hadfield, S., Jiang, Z., and Rieffel, E. G. (2017). The Quantum
Approximation Optimization Algorithm for MaxCut: A Fermionic View. arXiv:1706.02998.
[Wecker et al., 2016] Wecker, D., Hastings, M. B., and Troyer, M. (2016). Training a quantum optimizer. In
arXiv preprint arXiv:1605.05370.
[Wecker and Svore, 2014] Wecker, D. and Svore, K. M. (2014). Liqui|>: A software design architecture
and domain-specific language for quantum computing. In arXiv preprint arXiv:1402.4467.
[Wille et al., 2014] Wille, R., Lye, A., and Drechsler, R. (2014). Exact reordering of circuit lines for nearest
neighbor quantum architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits
and Systems, 33(12):1818–1831.
[Yang et al., 2016] Yang, Z. C., Rahmani, A., Shabani, A., Neven, H., and Chamon, C. (2016).
Optimizing variational quantum algorithms using pontryagin’s minimum principle. In arXiv preprint
arXiv:1607.06473.

