# Optimal Layout Synthesis for Quantum Circuits
as Classical Planning (full version)††thanks: This is the full technical
report for I. Shaik and J. van de Pol, Optimal Layout Synthesis for Quantum
Circuits as Classical Planning. In: Proc. IEEE/ACM IC on Computer-Aided
Design, (ICCAD’23), San Francisco, California, USA, 2023.

Irfansha Shaik  Department of Computer Science
Aarhus University
Aarhus, Denmark
<EMAIL_ADDRESS>Jaco van de Pol  Department of Computer Science
Aarhus University
Aarhus, Denmark
<EMAIL_ADDRESS>
###### Abstract

In Layout Synthesis, the logical qubits of a quantum circuit are mapped to the
physical qubits of a given quantum hardware platform, taking into account the
connectivity of physical qubits. This involves inserting SWAP gates before an
operation is applied on distant qubits. Optimal Layout Synthesis is crucial
for practical Quantum Computing on current error-prone hardware: Minimizing
the number of SWAP gates directly mitigates the error rates when running
quantum circuits.

In recent years, several approaches have been proposed for minimizing the
required SWAP insertions. The proposed exact approaches can only scale to a
small number of qubits. Proving that a number of swap insertions is optimal is
much harder than producing near optimal mappings.

In this paper, we provide two encodings for Optimal Layout Synthesis as a
classical planning problem. We use optimal classical planners to synthesize
the optimal layout for a standard set of benchmarks. Our results show the
scalability of our approach compared to previous leading approaches. We can
optimally map circuits with 9 qubits onto a 14 qubit platform, which could not
be handled before by exact methods.

###### Index Terms:

Layout Synthesis, Transpiling, Quantum Circuits, Classical Planning, SAT
Planning, Optimal Planning

##  I Introduction

Quantum algorithms can speed up certain computational problems. For example,
Shor’s Algorithm [1] provides an exponential speed-up for factorization, and
Grover’s algorithm [2] provides a quadratic speed-up for database search. In
recent years, quantum computing is envisaged as a way to solve hard problems
[3], out of reach for classical computers. Formulating new algorithms to solve
more problems faster on quantum computers, and enabling compilation of those
algorithms on actual quantum hardware is of great interest.

In this paper, we focus on the latter part, especially mapping a quantum
circuit to an arbitrary quantum architecture. Following [4], we distinguish
logical synthesis and layout synthesis for quantum circuits. _Logical
synthesis_ constructs an (efficient) quantum circuit of quantum gates on a
number of logical qubits. Following [5, 6, 7], arbitrary quantum circuits can
be represented by a few simple gates. We assume that the resulting quantum
circuit consists of any standard unary gates and binary Controlled-NOT (CNOT)
gates. A CNOT gate acts on two qubits. If the control qubit is true, then the
target qubit is flipped. After logical synthesis, the gates and the order of
their application to the logical qubits is fixed.

We focus on _Layout synthesis_ , mapping the logical qubits onto the qubits of
some physical hardware platform. High level algorithms assume that every pair
of (logical) qubits is connected. However, in actual hardware platforms, often
only a subset of (physical) qubit connections are realized. So one needs to
compile the logical circuit to a physical hardware platform, such that every
CNOT gate is applied only on neighboring qubits. It is not always possible to
find a fixed mapping from logical qubits to physical qubits, such that every
CNOT is applied on neighbors. In such cases, SWAP gates can be inserted, to
swap the values of two connected qubits. A SWAP gate can be built from 3 CNOT
gates. The goal of layout synthesis is to insert a minimal number of SWAP
gates into the circuit, to move logical qubits to physical qubits, satisfying
all neighbor constraints on subsequent CNOT gates.

##### State-of-the-Art and Related Work

Layout Synthesis has many names, for example, Transpilation, Compilation,
Routing problem etc. An extensive overview and comparison of existing
approaches is provided in [4], discussing both exact and heuristic approaches.
Several heuristic approaches exist, for instance based on Dynamic Programming
[8], A* search [9], and Temporal Planning [10, 11, 12, 13]. Concrete tools
include Qiskit’s SABRE [14] and Hardware-Aware (HA) [15]. While the state-of-
the-art heuristic approaches are fast and scalable, it has been observed that
the solutions are non-optimal [16]. In fact, [4] observed large optimality
gaps, up to 1.5-12x and 5-45x on average on major quantum computing platforms.

For practical quantum computing on current NISQ machinery (noisy, intermediate
scale quantum computers), the primary goal is to reduce the error rate. Since
with each new gate the error rate increases, it is essential to minimize the
number of additional SWAP gates in the Layout Synthesis. Therefore, in this
paper we will focus on exact approaches.

Recently, several exact approaches have been proposed for optimal Layout
Synthesis. An exact approach based on Dynamic Programming was proposed in
[17], but it scales only to small circuits. Layout Synthesis was formulated as
an SMT encoding in [16], where propositional constraints are given for
satisfying connectivity and integer costs are assigned to additional swap
gates. The authors report improved optimal plans compared to heuristic
approaches. They use an exponential number of variables to represent all
permutations for the initial mapping. In a followup work [18], optimal
subarchitectures are considered to reduce the number of permutations by
mapping to a subset of physical qubits. In [19], the tool OLSQ is presented,
based on an improved SMT encoding of permutations using a polynomial number of
variables in the number of qubits. Those authors also allow optimizing error
rates when individual error rates are given for qubits and gates. In [20], it
is proposed to solve Layout Synthesis as a MAXSAT problem.

In theory, both SMT and MAXSAT approaches can prove lower bounds on the number
of SWAP gates, thus guaranteeing optimality. However, optimal Layout Synthesis
is an NP-complete problem [21]. In practice, most tools make some
approximations. For instance, they limit the number of added swap gates, or
they switch to heuristic search after some time limit. For example, the tool
satmap by [20] only produces near optimal solutions, due to a restriction on
the number of swaps. Even with these restrictions, all three approaches report
improved optimality compared to heuristic approaches. However, the improved
(near) optimality comes at the cost of time and memory. We aim at improving
the performance, while preserving the optimality of the exact approaches.

##### Contribution

In this paper, we provide the first encoding of Optimal Layout Synthesis as a
classical planning problem. The possible actions in this planning problem are:
1) to map a logical qubit to an initial physical qubit; 2) to apply a CNOT
gate to the proper qubits; or 3) to insert an additional SWAP gate. In the
latter case, we allow swapping logical qubits, as well as swapping a logical
qubit with an extra ancillary qubit, since this can lead to even shorter
plans. The conditions on the actions ensure that the solution satisfies all
constraints. The shortest plan corresponds to a layout with the minimal number
of SWAP gates. This enables the use of optimal planning tools to find the
optimal layout.

In fact, we provide two encodings. The first one is based on _global levels_
to resolve dependencies. Viewing these levels as discrete time stamps, this
encoding is close to the temporal planning approach [10, 11, 12, 13], but we
use the simpler fragment of classical planning, and moreover our encoding is
exact, while their approach minimizes makespan, but not necessarily the number
of SWAP gates. Our second, more efficient but still exact encoding, avoids the
explicit representation of time steps and is based on the relative order
induced by _local dependencies_ between CNOT gates.

We implement both encodings in the open source translator Q-Synth
(https://github.com/irfansha/Q-Synth/), written in Python. It takes two
inputs: a quantum circuit with unary and binary CNOT gates in the standard
OPENQASM 2.0 format [6], and a directed graph, modeling the connectivity graph
of a hardware architecture platform. We use Qiskit libraries [22] for parsing,
printing and extracting layers from a given circuit. Initially, we ignore
unary gates and compute the dependencies between the CNOT gates. The output of
the translator is a planning problem represented in PDDL (Planning Domain
Definition Language) [23]. This enables to use off-the-shelf classical
planners for computing optimal plans for these PDDL instances. The optimal
plan is translated back to an OPENQASM circuit by re-inserting the unary
gates.

We experimented with the planner Fast Downward [24] (with multiple backends
[25, 26]) and with Madagascar [27], which is based on an encoding into SAT
(propositional satisfiability). Other planners, like those based on QBF
(Quantified Boolean Logic) [28] could be used as well. We report the
performance of our two approaches on some standard benchmarks and compare them
to a number of existing exact (QMAP [29, 18] and OLSQ [19]) and heuristic
approaches (QISKIT’s SABRE [14]). As reported before, the heuristic approach
SABRE is very fast, but often uses more SWAP gates than necessary. In all
solved cases, we computed the correct minimal number of required SWAP gates.

We demonstrate that the performance of our approach is better than previous
exact approaches. Moreover, our Local encoding performs much better than our
Global encoding. The existing tool QMAP performed better than OLSQ in our
experiments on a 5 qubit platform. On the other hand, OLSQ performed better
than QMAP on a 14 qubit platform. Our Local approach is up to two orders of
magnitude faster than OLSQ and solves 8 unique instances that OLSQ could not
solve in 3 hours. Our approach finds optimal mappings of 9-qubit circuits onto
a 14-qubit platform, where previous exact tools, OLSQ and QMAP, could only map
5-qubit and 4 qubits circuits respectively on the same platform.

##  II Preliminaries

###  II-A Layout Synthesis for Quantum Circuits

Layout Synthesis is mapping a logical circuit to some physical quantum
computer architecture. Higher level algorithms make some assumptions, for
example one-to-one connectivity is assumed among all qubits. However, physical
architectures can have many restrictions, for example limited connectivity
between qubits where binary gates can be applied. Particular qubits could also
have different error rates and time durations. One takes into account such
considerations when mapping to some architecture. In case no mapping exists
such that the logical circuit can be mapped, SWAP gates can be added between
neighbors to move the logical qubits to connected qubits. Note that using
ancillary qubits can reduce the number of required SWAP gates. In this work,
we focus on minimizing the number of SWAP gates and consider the use of
planning for error rate optimization as future work.

We illustrate layout synthesis on an adder circuit, a standard example from
[19]. The traditional circuit representation of the circuit is shown in Fig.
1. It contains 10 binary CNOT gates and 13 unary gates. Fig. 2 shows the adder
circuit in OPENQASM format (with gate numbers as comments).

Figure 1: Adder circuit before mapping to IBM-QX2.

        OPENQASM 2.0;
        include "qelib1.inc";
        qreg q[4];
        x q[0];//g1
        x q[1];//g2
        h q[3];//g3
        cx q[2], q[3]; //g4
        t q[0];//g5
        t q[1];//g6
        t q[2];//g7
        tdg q[3];  //g8
        cx q[0], q[1]; //g9
        cx q[2], q[3]; //g10
        cx q[3], q[0]; //g11
        cx q[1], q[2]; //g12
        cx q[0], q[1]; //g13
        cx q[2], q[3]; //g14
        tdg q[0];  //g15
        tdg q[1];  //g16
        tdg q[2];  //g17
        t q[3];//g18
        cx q[0], q[1]; //g19
        cx q[2], q[3]; //g20
        s q[3];//g21
        cx q[3], q[0]; //g22
        h q[3];//g23

Figure 2: Adder circuit in OPENQASM format and in DAG format, showing the gate
dependencies. Figure 3: Coupling map for IBM-QX2 (Tenerife) Figure 4: Coupling
map for IBM Melbourne Figure 5: Adder circuit after mapping to IBM-QX2, with 1
optimal swap insertion. Measurement gates indicate the final location of the
logical qubits.

Figure 2 also provides a DAG representation with dependencies between gates,
as computed by Qiskit [22]. The green nodes (inputs) are logical qubits,
whereas the red nodes represent the (binary) CNOT gates, and the other nodes
are unary gates. We use the gate numbers to represent the dependencies between
gates in the DAG. There are 11 layers in total, if we do not count the top
qubit layer (the inputs are not part of the circuit). All gates in the same
layer act on independent qubits, so they can be executed independently. We use
this fact in Section III-A to handle dependencies between CNOT gates.

Figure 3 illustrates the IBM platform IBM-QX2 with 5 physical qubits. In
general, the connections between qubits are directed, and our approach can
handle directed coupling graphs. However, other exact tools can only handle
symmetric connections, so for a fair comparison we only consider bidirectional
platforms in this paper.

To map the adder circuit onto any platform, one needs 4 physical qubits
connected as a square since it has CNOT gates on the qubit pairs
$(q0,q1),(q1,q2),(q2,q3),(q3,q0)$. However, IBM-QX2 has no 4 qubits that are
connected in the form of a square, thus SWAP gates are needed. We observe from
our results in Table I that 1 SWAP insertion is sufficient. The circuit in
Figure 5 shows the mapped circuit with 1 additional SWAP gate. First, the
logical qubits ${q0,q1,q2,q3}$ of the circuit are mapped to physical qubits
${q0,q1,q2,q3}$. For the mapped circuit, the order of gates g11 and g12 is
reversed, and a SWAP gate on qubits q2 and q3 is added in between. Since g11
and g12 are in the same layer, they are independent, and this change preserves
the correctness. All gates after g11 and g12 must be mapped to the swapped
physical qubits: Essentially, from this point on, q2 and q3 are interchanged.

The Melbourne platform (Fig. 4) contains a subset of 4 qubits that form a
square. Consequently, the adder circuit does not require any additional SWAP
gates when mapped on Melbourne. We can indeed find a mapping without any SWAP
gates as shown in Table II.

###  II-B Classical Planning

One of the main applications of Automated Planning [30] is scheduling. In
Section III, we will model Layout Synthesis as a planning problem. Classical
Planning is finding a valid sequence of deterministic actions from a single
initial state to some goal state, where the initial state and the effect of
all actions are completely known. The _Planning Domain Definition Language_
(PDDL) [23] is a standard domain-specific language for classical planning
problems used in International Planning Competitions (IPC). As shown in
Listing 1: The domain file specifies types, predicates and actions. For
predicates one can optionally specify types, as we will later see in the
Section III. PDDL is an action-centered language; the actions essentially
specify how the world changes by preconditions and effects. Action conditions
and effects are represented similar to First-Order-Logic, using parameters to
achieve compact descriptions. An example for an action is map_initial with
parameters ?l and ?p in Section III-A. The problem file specifies objects,
initial state and goal conditionas shown in Listing 2 Initial and Goal states
are represented using a set of (negated) propositions.

Given a planning problem in PDDL format, one can use off-the-shelf planners
such as Fast Downward, Madagascar, etc. A planning problem description can
also assign costs to actions. In Planning competitions, planners are
categorized based on how they handle these costs. Optimal Planners return only
plans with optimal cost; Satisfying Planners, on the other hand, return some
plan quickly, regardless of the cost. Nevertheless, given enough time, some
satisfying planners such as Fast Downward Stone Soup (FDSS) [24] can optimize
the cost to a large extent. Note that if cost is not specified, each action is
considered to have cost 1.

Listing 1: Domain file structure

⬇

(define (domain Quantum)

(:requirements :typing)

(:types …)

(:predicates …)

(:action …)…)

Listing 2: Problem file structure

⬇

(define (problem example)

(:domain Quantum)

(:objects …)

(:init …)

(:goal (and …)))

##  III Layout Synthesis as Classical Planning

In this section, we describe two encodings of layout synthesis as a classical
planning problem, represented in PDDL.111Our Quantum Circuit Layout domain
received the Outstanding Domain Submission Award at the International Planning
Competition IPC 2023. Both encodings include the following actions:

  * •

apply_cnot, to apply the CNOT gate of two logical qubits on two physical
qubits.

  * •

swap, to insert a SWAP gate. We allow swapping two mapped logical qubits, as
well as swapping a mapped logical qubit with an ancillary qubit.

Both encodings include the following predicates, to model the state after a
partial plan:

  * •

mapped(?l,?p), to keep track on which physical qubit a logical qubit is
currently mapped.

  * •

rcnot(...), keeping track which CNOT gates are still required (all CNOT gates
are still required in the initial state, none should be required in the goal
state).

The planning problem defines the following constraints on valid plans:

  * •

Initial Mapping: The initial mapping from logical to physical qubits must be
injective.

  * •

Valid Gate Dependencies: Gates must be applied to the correct qubits in proper
order.

  * •

Valid CNOT and SWAP gates: All CNOT and SWAP gates are only applied on
neighboring physical qubits.

As a consequence, since all CNOT gates must be applied anyway, the shortest
valid plan will correspond to the correct layout, with the minimal number of
SWAP gates inserted.

Since the hardware platform only constrains 2-qubit gate connectivity, layout
synthesis can focus on the CNOT gates and their dependencies only. The unary
gates can be reinserted later. Ignoring the unary gates, every CNOT gate has
at most two direct dependencies. We illustrate this again on the DAG of the
adder-circuit of Fig. 2. There, $g4$ depends on the input gates $g2$ and $g3$;
gate $g10$ only depends on $g4$; and gate $g11$ depends on the CNOT gates $g9$
and $g10$. In general, a CNOT gate could also depend on one input qubit and
one CNOT gate, but this does not happen in the example of Fig. 2.

We parse the circuit and extract the CNOT gates with their dependencies. After
finding a solution, we reconstruct the circuit including single qubit gates.
We first encode $n$ logical qubits as objects $\\{l_{0},\dots,l_{n-1}\\}$ of
type lqubit, and $m$ physical qubits using objects as
$\\{p_{0},\dots,p_{m-1}\\}$ of type pqubit. In our experiments, we do not
specify costs, so each additional SWAP gate increases the cost by 1.
Alternatively, one could specify an explicit cost for SWAP gates; for example
a cost of 3, representing 3 underlying CNOT gates.

The first encoding (Section III-A) is based on _global levels_ , corresponding
to the layers with CNOT gates in the dependency graph. This encoding uses two
extra actions: map_initial, mapping a logical qubit to a physical qubit in the
first time slice, and action move_depth, to advance to the next time slice.
The second, more efficient encoding (Section III-B), avoids the explicit
representation of time steps and is based on the relative order of _local
dependencies_ between CNOT gates (and logical input qubits).

###  III-A Global Level Based Model

####  III-A1 Domain Specification

In this section, we specify the predicates and actions required for the domain
specification. Note that a domain file specifies the predicates and the
actions of the problem domain. The predicates describe the state of the world,
whereas the actions describe the change from one state to another.

##### Valid Initial Mapping

For modelling the first constraint i.e., mapping logical qubits to physical
qubits, we define three predicates and one action. The predicate mapped
specifies that the logical qubit ?l is mapped to the physical qubit ?p. The
two auxiliary predicates mapped_pq/mapped_lq describe if a physical/logical
qubit is already mapped, since one needs an injective mapping. The parameter
?p (?l) in these predicates is of type pqubit (lqubit). To obtain
propositional instances, one substitutes all objects with corresponding types
in the predicates. This process is called grounding. It translates the PDDL
description to a (potentially very large) propositional problem.

We use the map_initial action to map a logical qubit ?l to a physical qubit
?p. One can apply the action only if ?l and ?p are both not mapped. Once the
action is applied, ?l is mapped to ?p.

Listing 3: predicates and action for initial mapping

⬇

(:types lqubit pqubit)

(:predicates (mapped ?l - lqubit ?p - pqubit)

(mapped_lq ?l - lqubit)

(mapped_pq ?p - pqubit))

(:action map_initial

:parameters (?l - lqubit ?p - pqubit)

:precondition (and

(not(mapped_lq ?l)) (not(mapped_pq ?p)))

:effect (and (mapped ?l ?p)

(mapped_lq ?l) (mapped_pq ?p)))

##### Valid Gate Dependencies

To enforce gate dependencies in this model, we use the layers as generated by
Qiskit.222This may introduce spurious dependencies, when independent gates end
up in different layers. This sub-optimality is solved in our Local model. As
long as gates are executed layer by layer, their dependencies will be
respected. When modelling layout synthesis as planning, we only consider the
layers with CNOT gates. To represent layers in our first planning model, we
introduce objects of type depth, representing discrete depths, i.e., one
object for each layer that contains a CNOT gate. In the DAG of the adder
example in Figure 2, only the layers at depths $d2,d3,d4,d5,d6,d8,d{10}$
contain CNOT gates.

To ensure the circuit is executed layer by layer, we maintain a predicate
current_depth to specify the current layer, and use a static predicate
next_depth to relate the current and the next layer. We use the action
move_depth to move from one layer to another layer in a plan. Every valid plan
has exactly $k$ move_depth actions, where $k$ is the number of layers in the
DAG with at least one CNOT gate.

Using layers provides two advantages over placing each instruction in its own
layer, following the OPENQASM input order: (1) There are fewer dependencies,
potentially reducing the number of swaps; (2) There are fewer move_depth
actions in the plan, which typically decreases the solving time.

Listing 4: predicates and action for valid gate dependencies

⬇

(:types depth)

(:predicates (current_depth ?d - depth)

(next_depth ?d1 ?d2 - depth))

(:action move_depth

:parameters (?d1 ?d2 - depth)

:precondition (and (current_depth ?d1)

(next_depth ?d1 ?d2))

:effect (and (not(current_depth ?d1))

(current_depth ?d2)))

##### Valid CNOT and SWAP gates

For the final constraint, we need to specify when CNOT and SWAP gates can be
applied. To model that a CNOT gate must be applied on specific qubits at a
certain depth, we use predicate rcnot (required-cnot) in Listing 5. Predicate
(rcnot ?l1 ?l2 ?d) indicates that a CNOT gate must still be applied between
two logical qubits ?l1, ?l2 at the layer ?d. Here ?l1, ?l2, ?d are parameters
that can be substituted with objects of the corresponding types to generate
(grounded) propositions.

To apply a CNOT gate, the corresponding logical qubits must be mapped to some
physical qubits; these physical qubits must be connected; and the current
depth must match a required CNOT gate. The action apply_cnot ensures that all
the above conditions are satisfied. The effect of this action removes one
required CNOT operation (rcnot).

Finally, we model the action swap to allow swapping of logical qubits when
required. We allow two types of swaps:

  * •

Swapping two mapped logical qubits.

  * •

Swapping a mapped logical qubit with an ancillary qubit.

Note that we call both actions swap, although their parameters and conditions
are different. In the first case, similar to a CNOT gate, both logical qubits
must be mapped to connected physical qubits. The effect will update the
mapping from logical to physical qubits. In the second case, a logical qubit
?l1 must be mapped to a physical qubit ?p1, which should be connected to a
free (not mapped) physical qubit ?p2. Once swapped, ?l1 is now mapped to ?p2,
and ?p1 becomes free again (not mapped). If the coupling graph is _not_
bidirectional, we need a symmetric version of the ancillary swap as well (see
Appendix -B for full details).

Listing 5: predicates and actions for valid CNOT and SWAP gates

⬇

(:predicates

(rcnot ?l1 ?l2 - lqubit ?d - depth)

(connected ?p1 ?p2 - pqubit))

(:action apply_cnot

:parameters (?l1 ?l2 - lqubit

?p1 ?p2 - pqubit ?d - depth)

:precondition (and (connected ?p1 ?p2)

(mapped ?l1 ?p1) (mapped ?l2 ?p2)

(rcnot ?l1 ?l2 ?d) (current_depth ?d))

:effect (and (not(rcnot ?l1 ?l2 ?d))))

(:action swap ;; with another mapped qubit

:parameters (?l1 ?l2 - lqubit

?p1 ?p2 - pqubit)

:precondition (and (connected ?p1 ?p2)

(mapped ?l1 ?p1) (mapped ?l2 ?p2) )

:effect (and

(not(mapped ?l1 ?p1)) (mapped ?l1 ?p2)

(not(mapped ?l2 ?p2)) (mapped ?l2 ?p1)))

(:action swap ;; with an ancillary qubit

:parameters (?l1 - lqubit ?p1 ?p2 - pqubit)

:precondition (and (connected ?p1 ?p2)

(mapped ?l1 ?p1) (not(mapped_pq ?p2)) )

:effect (and

(not(mapped ?l1 ?p1)) (mapped ?l1 ?p2)

(not(mapped_pq ?p1)) (mapped_pq ?p2)))

####  III-A2 Problem Specification

In the problem file, we need to specify the initial and goal states of the
planning problem. For the adder example, the initial depth is the first layer
with a CNOT, d2. We specify the coupling map of the architecture using
connected predicates. For CNOT mapping, we specify all the required CNOT gates
at specific depths. Finally, the next_depth predicate specifies a total
ordering of the layers. Note that the initial state specification is complete,
i.e., all propositions not specified are negated. In case of the goal
specification, one only needs to specify the propositions that must be
achieved. Propositions that are not specified are open, resulting in more than
one goal state. In our model, we specify that all logical qubits are mapped
and all required CNOT gates are performed (i.e., each rcnot is negated).
Listings 6 and 7 present snippets of initial and goal specification of our
adder example.

Listing 6: Adder initial state snippets

⬇

(:init

(current_depth d2)

(connected p1 p0) (connected p1 p2) …

(next_depth d2 d3) (next_depth d3 d4) …

(rcnot l2 l3 d2) (rcnot l0 l1 d3) … )

Listing 7: Adder goal state snippets

⬇

(:goal

(and

(mapped_lq l0) … (mapped_lq l3)

(not (rcnot l2 l3 d2)) … ))

###  III-B Local Dependency Based Model

In the Global model, using explicit actions for moving to the next depth
results in almost doubling the plan length in the worst case. At least, the
plan length increases by the number of layers in the circuit with CNOT gates.
It is well known that increased plan length can result in increased solving
time. Additionally, we need initial mapping actions for mapping logical qubits
to physical qubits. This further increases the plan length. These initial
mapping steps also create a large search space, which is not a priori pruned
by the needs of the logical circuit. Moreover, since the layers introduce
spurious dependencies, the resulting number of SWAPs could be suboptimal.

To overcome these problems, we make three improvements to our Global encoding.
First, we drop the layers and handle local dependencies directly when applying
CNOT gates. Second, we integrate the initial mapping into the corresponding
CNOT gates. Third, as a final optimization, we partially ground the gates in
the apply_cnot actions to reduce the number of parameters. We now describe
these improvements in detail.

####  III-B1 Avoiding Layers (Local/Initial)

In all our actions and predicates, we drop the depth parameters, and we drop
the action next_depth. Instead, we will specify gate dependencies locally.
Recall that during planning we only consider the binary CNOT gates, and we
completely ignore the unary gates. Then a CNOT gate $C_{1}$ depends on at most
two preceding CNOT gates $C_{2}$ and $C_{3}$. A gate could also directly
depend on a logical input qubit. As long as $C_{2}$ and $C_{3}$ are executed
before $C_{1}$, we preserve the correctness.

To model local dependencies (cf. Listing 8), we introduce a static predicate
(cnot ?l1 ?l2 ?g1 ?g2 ?g3), which indicates that the logical circuit contains
a gate ?g1 on logical qubits ?l1 and ?l2, that depends on previous gates ?g2
and ?g3. To avoid exceptions for gates that directly depend on the input
qubits, we view lqubit as a subtype of gate. We introduce predicate done to
keep track of the CNOT gates that have already been applied. Using done, we
don’t require mapped_lq anymore, and we rename mapped_pq to occupied. The
predicates mapped and connected are similar as before.

Listing 8: Local/Initial Domain: types and predicates

⬇

(:types

pqubit gate - object

lqubit - gate)

(:predicates

(cnot ?l1 ?l2 - lqubit ?g0 ?g1 ?g2 - gate)

(done ?g - gate)

(mapped ?l - lqubit ?p - pqubit)

(occupied ?p - pqubit)

(connected ?p1 ?p2 - pqubit))

The actions map_initial and apply_cnot are adapted as in Listing 9. Note that
an lqubit becomes done when it is mapped, while a CNOT gate becomes done when
it is applied. Also note that in the latter case, we require that the
dependent CNOT gates (or logical input qubits) are already done. The swap-
actions are similar to the global encoding in Listing 5.

Listing 9: Local/Initial Domain: actions map_initial and apply_cnot

⬇

(:action map_initial

:parameters (?l - lqubit ?p - pqubit)

:precondition

(and (not(done ?l)) (not(occupied ?p)))

:effect (and (done ?l)

(mapped ?l ?p) (occupied ?p)))

(:action apply_cnot

:parameters (?l1 ?l2 - lqubit

?p1 ?p2 - pqubit

?g0 ?g1 ?g2 - gate)

:precondition (and

(cnot ?l1 ?l2 ?g0 ?g1 ?g2)

(connected ?p1 ?p2)

(mapped ?l1 ?p1) (mapped ?l2 ?p2)

(done ?g1) (done ?g2) (not(done ?g0)))

:effect (and (done ?g0)))

####  III-B2 Integrating the Initial Mapping (Lifted/Compact)

Recall that not all CNOT gates have two CNOT dependencies; for example gate
$g4$ in Figure 2 depends directly on two logical (input) qubits l2 and l3. To
avoid explicit initial mapping actions, we integrate the mapping of these
input qubits directly into the CNOT actions.

In this lifted compact model, we drop the map_initial action entirely.
Instead, we split the apply_cnot action in four cases, depending on whether
this gate depends on previous gates or on logical input qubits. In the latter
case, we immediately map the logical qubits to any unmapped, connected
physical qubits. In Listing 10 we show two cases, where gate ?g0 depends on
two gates, or on two inputs, respectively. Note that in the latter case we can
drop the test for (done ?l1) and (done ?l2), since in this model a logical
qubit can only be the input to a single CNOT gate (ignoring intermediate unary
gates). The full model also includes mixed cases for apply_cnot_gate_input and
apply_cnot_input_gate.

Listing 10: Lifted/Compact Domain: apply_cnot actions

⬇

(:action apply_cnot_gate_gate

:parameters (?l1 ?l2 - lqubit

?p1 ?p2 - pqubit

?g0 ?g1 ?g2 - gate)

:precondition (and

(cnot ?l1 ?l2 ?g0 ?g1 ?g2)

(connected ?p1 ?p2)

(mapped ?l1 ?p1) (mapped ?l2 ?p2)

(done ?g1) (done ?g2) (not (done ?g0)))

:effect (and (done ?g0)))

(:action apply_cnot_input_input

:parameters (?l1 ?l2 - lqubit

?p1 ?p2 - pqubit ?g0 - gate)

:precondition (and

(cnot ?l1 ?l2 ?g0 ?l1 ?l2)

(connected ?p1 ?p2)

(not (occupied ?p1)) (not (occupied ?p2))

(not (done ?g0))

)

:effect (and (done ?g0)

(mapped ?l1 ?p1) (occupied ?p1)

(mapped ?l2 ?p2) (occupied ?p2)))

####  III-B3 Grounding the Gate Names (Local/Compact)

In both local models, the cnot-predicate and the apply_cnot action depend on
many parameters. This could slow down the planning tools, since they have to
instantiate these actions for all possible object combinations. Note that for
each gate, the dependencies and the logical qubits they are applied to are
known at compile time. Therefore, as a final optimization step, in our
Local/Compact model we specialize the apply_cnot actions in the domain
specification for each gate.

The domain file now depends on the logical circuit instance, since it refers
to its gates and qubits. This requires the introduction of constants with the
new type gateid (one for each CNOT gate), as well as constants for the logical
qubits. The mapped physical qubits are not known at compile time, but will be
determined by the planner tool.

For example, the CNOT gate $g11$ in the adder circuit in Fig. 2 is represented
by the constant g11, and it is handled by the action apply_cnot_g11. It is
applied to the logical qubits l3 and l0. This gate depends on two CNOT gates
g9 and g10, so the precondition also requires that the dependent CNOT gates g9
and g10 are already done. The complete action specification for this gate
becomes:

Listing 11: A partially grounded CNOT action for the adder circuit

⬇

(:types gateid lqubit pqubit)

(:constants g4 g9 g10 g11 … g22 - gateid

l0 l1 l2 l3 - lqubit)

(:action apply_cnot_g11

:parameters (?p1 ?p2 - pqubit)

:precondition (and (not (done g11))

(done g9) (done g10)

(mapped l3 ?p1) (mapped l0 ?p2)

(connected ?p1 ?p2))

:effect (and (done g11)))

The CNOT gate $g4$ depends on two inputs, so the corresponding action
apply_cnot_g4 will integrate two initial mappings as follows:

Listing 12: CNOT gate with integrated initial mapping

⬇

(:action apply_cnot_g4

:parameters (?p1 ?p2 - pqubit)

:precondition (and (not (done g4))

(not(occupied ?p1)) (not(occupied ?p2))

(connected ?p1 ?p2))

:effect (and (done g4)

(mapped l2 ?p1) (occupied ?p1)

(mapped l3 ?p2) (occupied ?p2)))

A similar integration is also applied to CNOT gates which depend only on one
other CNOT gate. We provide the full specification for the Adder example in
Appendix -A.

The Local Compact encoding avoids spurious dependencies due to using fixed
levels. It also results in shorter plans, since we avoid the next_depth and
map_initial actions. Searching for shorter plans should be more efficient. We
also expect that the efficiency is further improved since the actions have
fewer parameters (due to grounding) and logical qubits will only be mapped to
connected physical qubits, as required by the initial CNOT gates. The
following section compares the performance of the “Global”, the (lifted)
“Local Initial” and the (grounded) “Local Compact” encodings experimentally.

##  IV Experimental Evaluation

###  IV-A Experiment Design

We have implemented the translation of quantum circuits into PDDL instances in
our tool Q-Synth (Quantum Synthesizer).333Q-Synth is available open source at
https://github.com/irfansha/Q-Synth/. For an experimental evaluation, we
consider a standard set of 16 benchmark circuits from [19], and we map them
onto IBM platforms Tenerife (5 qubits) and Melbourne (14 qubits). The first
experiment maps onto platform Tenerife (also called IBM-X2). We consider those
6 out of 16 circuits that use at most the 5 physical qubits available in
Tenerife. For this experiment, we give a 300 seconds time limit and a 16-GB
memory limit. The second experiment maps onto platform Melbourne. We try all
13 out of 16 circuits that use at most 14 qubits. We give a 3-hour time limit
and a 48-GB memory limit for all 13 instances. In both cases, we measure and
report the CPU time taken by the whole tool chain (including parsing,
encoding, searching for an optimal plan, and extracting and validating the
mapped circuits).

Q-Synth requires a planning tool to solve the generated PDDL instances. We
consider the Fast Downward planner (FD) with two planner configurations, the
Big Joint Optimal Landmarks Planner (BJOLP) [25] and Merge-and-Shrink (MS)
[26], and the SAT based planner Madagascar (M) [27]. For both experiments, we
apply FD+BJOLP on the Global models (column G-bj) and Lifted Initial models
(column LI-bj). On the Local Compact models, we report results from all three
planners FD with BJOLP (L-bj), FD with MS (L-ms), and Madagascar (L-M). Note
that Madagascar is a satisfying planner. We increment the plan length by 1
until we find a plan. This ensures optimality of the plans generated by
Madagascar.

We compare our results with three existing tools. First with Qiskit’s
heuristic approach SABRE [14]. We use the first 100 seeds for SABRE Layout and
take the minimum number of swaps produced by any seed. In every instance, this
approach with 100 runs takes approximately 2 minutes.

Then we compare with two leading exact approaches QMAP [29, 18] and OLSQ [19].
Although there are heuristic versions of both tools, we only consider the
exact versions of them. We use the latest version OLSQ 0.0.4.1 installed using
pip. Note that OLSQ only uses bidirectional coupling graphs, so for sake of
uniformity we change the coupling maps of Tenerife and Melbourne for all
experiments. For QMAP, we use the latest version mqt.qmap 2.1.3. By default,
it uses subset optimization (QMAP-S) as in [29]. However, QMAP-S was shown to
be suboptimal for certain architectures [18]. Essentially, QMAP-S maps a given
circuit with $k$ logical qubits to a subset of $k$ physical qubits. Instead,
QMAP-SA uses optimal subarchitectures that also allow ancillary qubits. We
compare Q-Synth with the exact approaches QMAP (without subarchitectures) and
QMAP-SA (with optimal subarchitectures) as described in [18]. We also
experiment with QMAP-S on the Melbourne platform, but for a fair comparison,
in this case we also disable ancillary swaps in Q-Synth, run with planner
FD+BJOLP (L-bj-na).

###  IV-B Validation

Validating if our mapped circuits are optimal and correct is non-trivial. We
use the following four measures to ensure correctness and optimality.

  * •

When a circuit is mapped, we try to recover the original circuit by reversing
the swaps and using the reverse initial mapping. The resultant circuit must be
exactly the same as the original circuit, which we compare using Qiskit.

  * •

We check if all the 2-qubit gates are applied on the connected qubits. One
could alternatively use the checkmap function from QISKIT.

  * •

We compare the equivalence of the mapped circuit with the original circuit
with at least 1 million simulations in Qiskit.

  * •

Finally, for optimality we cross compare with the results obtained from other
exact tools.

Note that with SAT based planners, one could extract certificates when
refuting an instance. This provides provable lower bounds on the number of
swaps.

###  IV-C Results

In Table I (platform Tenerife), Q-Synth with both models and all planner
configurations, and both existing tools QMAP and OLSQ, solve all the
instances. Overall, for the benchmarks on this small platform, Q-Synth
performs similar to QMAP, whereas OLSQ is considerably slower, especially on
the larger instances. All exact approaches compute the minimum number of swaps
required for mod5mils_65 as 2. On the other hand, SABRE returns 3 swap
insertions, which is non-optimal.

Table II presents the results on platform Melbourne with 14 qubits. Our
Q-Synth with Local Initial models performs much better than with Global
models. Further, Q-Synth with Local Compact models performs much better than
with Local Initial models, especially on 9 qubit instances. Q-Synth solves
most instances with planner FD with MS (L-ms) or BJOLP (L-bj): 11 out of 13
within the time and memory limits; with Madagascar it solves 8 out of 13
instances (L-M); surprisingly L-M times out on one 5-qubit instance. Even our
Global encoding with FD+BJOLP (G-bj) solves 6 out of 13 instances, which is
more than previous exact methods. Other planning tools on our Global models
did not perform that well (timings are not reported here). Of the previous
exact approaches, OLSQ solves only 3 out of 13 instances in total, while QMAP-
SA solves 2 out of 13. Q-Synth is 2 orders of magnitude faster than OLSQ on
the or instance. On the other hand, QMAP (without subarchitectures) runs out
of memory for all instances. In case of solving without ancillary qubits,
QMAP-S solves 7 instances, including one 7-qubit instance. Q-Synth with Local
models without ancillary swaps (L-bj-na) still solves the same 11 instances
optimally (although this combination is suboptimal in general). It runs up to
ten times faster than L-bj (with ancillary swaps). So considering ancillary
swaps can increase the solving time considerably.

We don’t know the minimal number of SWAP gates required for the largest
benchmarks, since none of the exact tools could solve them. On the other hand,
with SABRE we could compute an upper bound on this number. One might also find
such plans by using QMAP and OLSQ in satisfying mode, or running the planning
tools on our encoding in satisfying mode, but this has not been the focus of
the research reported here. Note that for 5 instances, SABRE gives non-optimal
swap insertions (this phenomenon was also observed in [4]). For example, for
4gt13_92, SABRE gives 3 additional swaps, which can be implemented by 9
additional CNOT gates. Within 2 minutes, our approach L-ms computed the
minimum number of swaps needed, which then also provides a guaranteed lower
bound. This demonstrates the feasibility of classical planning for exact
optimal layout synthesis of quantum circuits of moderate size.

TABLE I: Platform Tenerife or IBM-QX2 (5 qubits), q: Number of logical qubits,
c: Number of CNOT gates, +s: Number of swaps added,
*: non-optimal count. We specify the time taken by all exact tools in seconds. |  |  |  | Our tool Q-Synth (exact) | Previous Exact Tools | SABRE
---|---|---|---|---|---|---
Circuit | Q | C | +S | G-bj | LI-bj | L-ms | L-bj | L-M | QMAP | QMAP-SA | OLSQ | +S
or | 3 | 6 | 0 | 4.9 | 4.3 | 4.1 | 4.0 | 3.9 | 4.0 | 3.9 | 6.7 | 0
adder | 4 | 10 | 1 | 4.4 | 4.2 | 4.4 | 4.0 | 4.7 | 3.9* | 4.1* | 40.3 | 1
qaoa5 | 5 | 8 | 0 | 3.9 | 4.1 | 4.6 | 4.2 | 4.0 | 4.0 | 3.9 | 12.6 | 0
4mod5-v1_22 | 5 | 11 | 1 | 4.7 | 4.1 | 4.7 | 4.1 | 4.1 | 4.0 | 3.9 | 24.2 | 1
mod5mils_65 | 5 | 16 | 2 | 4.2 | 4.0 | 5.3 | 4.3 | 5.4 | 4.0 | 4.0 | 107 | 3
4gt13_92 | 5 | 30 | 0 | 4.3 | 4.2 | 6.4 | 4.1 | 5.0 | 4.1 | 4.4 | 136 | 0
TABLE II: Platform Melbourne (14 qubits), q: Number of logical qubits, c:
Number of CNOT gates, +s: Number of swaps added,
TO/MO: Time/Memory Out, *: suboptimal count. We specify the time taken by all exact tools in seconds. |  |  |  | Our tool Q-Synth (exact) | Previous Exact Tools | Without ancillary qubits | SABRE
---|---|---|---|---|---|---|---
Circuit | Q | C | +S | G-bj | LI-bj | L-ms | L-bj | L-M | QMAP | QMAP-SA | OLSQ | L-bj-na | QMAP-S | +S
or | 3 | 6 | 2 | 4.9 | 4.1 | 7.6 | 4.1 | 4.3 | MO | 5.5 | 517 | 4.2 | 2.8 | 2
adder | 4 | 10 | 0 | 5.5 | 4.5 | 15.1 | 4.2 | 4.6 | MO | 6.5 | 30.5 | 4.3 | 2.4 | 0
qaoa5 | 5 | 8 | 0 | 5.0 | 4.5 | 23.7 | 4.4 | 4.1 | MO | TO | 39.5 | 4.2 | 2.6 | 0
4mod5-v1_22 | 5 | 11 | 3 | 115 | 29.2 | 25.6 | 5.1 | 7.4 | MO | TO | TO | 4.7 | 10.1 | 4
mod5mils_65 | 5 | 16 | 6 | 1825 | 57.8 | 33.7 | 7.0 | 16.3 | MO | TO | TO | 4.6 | 18.6 | 6
4gt13_92 | 5 | 30 | 10 | TO | 280 | 85.8 | 121 | TO | MO | TO | TO | 11.5 | 183* | 13
tof_4 | 7 | 22 | 1 | 5831 | 2716 | 125 | 4.7 | 12.3 | MO | TO | TO | 5.1 | 6734 | 1
barenco_tof_4 | 7 | 34 | 5 | TO | 10643 | 184 | 29.9 | 27.7 | MO | TO | TO | 8.4 | TO | 6
tof_5 | 9 | 30 | 1 | TO | TO | 386 | 5.0 | 449 | MO | MO | TO | 4.7 | TO | 1
mod_mult_55 | 9 | 40 | 7 | TO | TO | 2316 | 7710 | TO | MO | MO | TO | 761 | TO | 8
barenco_tof_5 | 9 | 50 | 6 | TO | TO | 634 | 187 | TO | MO | MO | TO | 23.2 | TO | 7
vbe_adder_3 | 10 | 50 | - | TO | TO | TO | TO | TO | MO | MO | TO | TO | TO | 8
rc_adder_6 | 14 | 71 | - | TO | TO | TO | TO | TO | MO | MO | TO | TO | MO | 12
Total number of instances solved: | 6 | 8 | 11 | 11 | 8 | 0 | 2 | 3 | 11 | 7 | 13

##  V Comparison with Related Work

### Comparison to QMAP and OLSQ

Our tool Q-Synth with the Local model outperforms QMAP significantly: Q-Synth
solves 9 instances uniquely. The difference is clear when the number of qubits
is more than 4: all the instances timed out for QMAP after 3 hours. Note that
Q-Synth solves all three 9-qubit instances (two even within 4 minutes). QMAP
uses an exponential number of variables in the number of qubits to represent
the permutations. We conjecture that is the reason for poor performance on the
14 qubit platform. Even with sub-architecture optimization, scaling to 14
qubit platform seems difficult, and we expect the same challenge for even
larger platforms. A similar bottleneck for QMAP is reported in [20] with
platform Tokyo (20 qubits). The number of SWAPs in QMAP depends on the order
of the input circuit, which can result in suboptimal solutions. For example,
QMAP and QMAP-SA give 2 additional swaps for the adder instance, instead of 1
optimal swap (∗ in Table I).

Even our Global encoding outperforms QMAP and solves three 5-qubit instances
and one 7-qubit instance. Avoiding the layers in Local Initial already
improves the performance up to an order of magnitude. Integrating the initial
maps with CNOT actions improves the performance even further. This shows the
strength of planning based approaches, and the effect of modelling the problem
(Global vs Local) on performance.

OLSQ (run in exact mode for optimal solutions) scales poorly with the number
of qubits and CNOT gates compared to Q-Synth. Between OLSQ and QMAP-SA, QMAP-
SA performs better on a 5-qubit platform whereas OLSQ performs better on a
14-qubit platform. These results are consistent with the exponential
dependency of QMAP on the target platform. Note that other approaches could
also benefit from the optimal subarchitectures computed by QMAP-SA. Further,
when optimizing for the number of swaps, the solutions from OLSQ are not
necessarily optimal. OLSQ optimizes swap count for each depth iteratively and
stops at the first depth where a mapping is found. This can be suboptimal
since larger depth mapped circuits are not explored. In our experiments, the
swap counts generated by OLSQ were optimal.

Both tools and also satmap by [20] provide heuristic approaches that produce
near optimal solutions and scale much better. In this paper, we focus only on
exact approaches where the solutions are truly optimal in the count of swap
insertions. Proving that there exists no mapping with less SWAP gates is much
harder. For larger circuits, one could apply satisfying planners to our
models, to find near-optimal solutions.

##### Without Ancillary Qubits

QMAP-S performs significantly better than QMAP-SA, consistent with the
theoretical considerations in [18]. For example, consider the instance qaoa5,
QMAP-S tries to map onto a 5-qubit subset of the physical qubits, while QMAP-
SA tries to map onto a 7-qubit subset, i.e., it allows 2 additional ancillary
qubits. Further, QMAP-S imposes a restriction on the number of swaps in front
of each gate. In case of qaoa5, the swap limit is 3, which significantly
reduces the solving time. However, it is not clear to us if this technique
preserves the optimality. Note that, for the same instance, the swap limit
with QMAP-SA is 7. We observed that QMAP-S returns 11 additional swaps for the
instance 4gt13_92 (∗ in Table II), instead of 10 swaps as reported by Q-Synth.
OLSQ in heuristic mode (OLSQ-TB) also gives 10 additional swaps for the same
instance, confirming an upper bound of 10 swaps. Our approach without
ancillary swaps still reports the correct minimal swap insertions in all
instances. However, [18] provides an example where ancillary swaps are
essential to obtain an optimal solution.

### Comparison to Temporal Planning

The authors of [10] proposed to use temporal planners for Layout Synthesis on
QAOA problems. In Section 4 [10], classical planning is mentioned as a
potential alternative for temporal planning. However, they use time steps for
gates to avoid dependencies, similar to our Global level-based encoding, but
without grouping the CNOT gates in layers. This can almost double the plan
lengths, and it blurs the look-ahead information due to lack of dependencies.
In their paper, poor preliminary results were reported with the SAT based
planner Madagascar (M/Mp) with parallel plans, which is consistent with our
observations. Another key issue with their use of temporal planning is the
lack of optimality: one can only obtain plans optimal in makespan. This issue
is similar to parallel plans in classical planning: the number of swaps added
need not be optimal and can be worse in practice.

In [13], layout synthesis for the QAOA algorithm for graph coloring is split
into two stages: Qubit Initialization (QI) and Routing. Classical planning is
considered for QI, where it is only used for initializing logical qubits on
physical qubits. The addition of SWAP gates and generating actual plans is
still handled by temporal planners. Compared to random initial allocation,
using the classical planner FastDownward, improved the makespan in many
instances.

##  VI Conclusion

From our experiments, we conclude that classical planning provides a strong
alternative to temporal planning or SMT solving for solving the optimal
circuit-layout synthesis problem. Moreover, the model using Local dependencies
is superior to the one using Global levels.

###  -A PDDL specification for Adder Circuit – Local Compact

We provide the detailed domain file and problem file for the adder example in
Fig 1. We map it to the Tenerife platform by using the Local Compact encoding.
These files can be generated using our tool
Q-Synth444https://github.com/irfansha/Q-Synth/releases/tag/Q-Synth-v1.0-ICCAD23,
using the following command, where -a1 switches on the use of ancillary bits,
and -b1 makes the coupling map bidirectional.

q-synth.py -m local -p tenerife -a1 -b1 Benchmarks/adder.qasm

Listing 13: Adder circuit – Local Compact; domain file

⬇

(define (domain Quantum)

(:requirements :strips :typing

:negative-preconditions)

(:types lqubit pqubit gateid - object)

(:constants g4 g9 g10 g11 g12 g13

g14 g19 g20 g22 - gateid

l0 l1 l2 l3 - lqubit)

(:predicates

(occupied ?p - pqubit)

(mapped ?l - lqubit ?p - pqubit)

(connected ?p1 ?p2 - pqubit)

(done ?g - gateid))

(:action swap

:parameters (?l1 ?l2 - lqubit

?p1 ?p2 - pqubit)

:precondition (and (connected ?p1 ?p2)

(mapped ?l1 ?p1) (mapped ?l2 ?p2))

:effect (and

(not (mapped ?l1 ?p1)) (mapped ?l1 ?p2)

(not (mapped ?l2 ?p2)) (mapped ?l2 ?p1)))

(:action swap-ancillary1

:parameters (?l1 - lqubit

?p1 ?p2 - pqubit)

:precondition (and (connected ?p1 ?p2)

(mapped ?l1 ?p1) (not (occupied ?p2)))

:effect (and

(not (mapped ?l1 ?p1)) (mapped ?l1 ?p2)

(not (occupied ?p1)) (occupied ?p2)))

(:action swap-ancillary2

:parameters (?l2 - lqubit ?p1 ?p2 - pqubit)

:precondition (and (connected ?p1 ?p2)

(mapped ?l2 ?p2) (not (occupied ?p1)))

:effect (and

(not (mapped ?l2 ?p2)) (mapped ?l2 ?p1)

(not (occupied ?p2)) (occupied ?p1)))

(:action apply_cnot_g4

:parameters (?p1 ?p2 - pqubit)

:precondition (and

(not (done g4)) (connected ?p1 ?p2)

(not(occupied ?p1)) (not(occupied ?p2)))

:effect (and (done g4)

(mapped l2 ?p1) (occupied ?p1)

(mapped l3 ?p2) (occupied ?p2)))

(:action apply_cnot_g9

:parameters (?p1 ?p2 - pqubit)

:precondition (and

(not (done g9)) (connected ?p1 ?p2)

(not (occupied ?p1)) (not(occupied ?p2)))

:effect (and (done g9)

(mapped l0 ?p1) (occupied ?p1)

(mapped l1 ?p2) (occupied ?p2)))

(:action apply_cnot_g10

:parameters (?p1 ?p2 - pqubit)

:precondition (and

(not (done g10)) (connected ?p1 ?p2)

(done g4) (mapped l2 ?p1)

(done g4) (mapped l3 ?p2))

:effect (and (done g10)))

(:action apply_cnot_g11

:parameters (?p1 ?p2 - pqubit)

:precondition (and

(not (done g11)) (connected ?p1 ?p2)

(done g9) (mapped l1 ?p1)

(done g10) (mapped l2 ?p2))

:effect (and (done g11)))

(:action apply_cnot_g12

:parameters (?p1 ?p2 - pqubit)

:precondition (and

(not (done g12)) (connected ?p1 ?p2)

(done g10) (mapped l3 ?p1)

(done g9) (mapped l0 ?p2))

:effect (and (done g12)))

(:action apply_cnot_g13

:parameters (?p1 ?p2 - pqubit)

:precondition (and

(not (done g13)) (connected ?p1 ?p2)

(done g12) (mapped l0 ?p1)

(done g11) (mapped l1 ?p2))

:effect (and (done g13)))

(:action apply_cnot_g14

:parameters (?p1 ?p2 - pqubit)

:precondition (and

(not (done g14)) (connected ?p1 ?p2)

(done g11) (mapped l2 ?p1)

(done g12) (mapped l3 ?p2))

:effect (and (done g14)))

(:action apply_cnot_g19

:parameters (?p1 ?p2 - pqubit)

:precondition (and

(not (done g19)) (connected ?p1 ?p2)

(done g13) (mapped l0 ?p1)

(done g13) (mapped l1 ?p2))

:effect (and (done g19)))

(:action apply_cnot_g20

:parameters (?p1 ?p2 - pqubit)

:precondition (and

(not (done g20)) (connected ?p1 ?p2)

(done g14) (mapped l2 ?p1)

(done g14) (mapped l3 ?p2))

:effect (and (done g20)))

(:action apply_cnot_g22

:parameters (?p1 ?p2 - pqubit)

:precondition (and

(not (done g22)) (connected ?p1 ?p2)

(done g20) (mapped l3 ?p1)

(done g19) (mapped l0 ?p2))

:effect (and (done g22))))

Listing 14: Adder circuit – Local Compact; problem file

⬇

(define (problem circuit)

(:domain Quantum)

(:objects p0 p1 p2 p3 p4 - pqubit)

(:init

(connected p1 p0)

(connected p0 p1)

(connected p2 p0)

(connected p0 p2)

(connected p2 p1)

(connected p1 p2)

(connected p3 p2)

(connected p2 p3)

(connected p3 p4)

(connected p4 p3)

(connected p4 p2)

(connected p2 p4)

)

(:goal (and

(done g4)

(done g9)

(done g10)

(done g11)

(done g12)

(done g13)

(done g14)

(done g19)

(done g20)

(done g22))))

An optimal plan, generated by FastDownward with BJOLP looks as follows:

      (apply_cnot_g9 p0 p1)
      (apply_cnot_g4 p2 p3)
      (apply_cnot_g10 p2 p3)
      (apply_cnot_g11 p1 p2)
      (swap l2 l3 p2 p3)
      (apply_cnot_g12 p2 p0)
      (apply_cnot_g13 p0 p1)
      (apply_cnot_g19 p0 p1)
      (apply_cnot_g14 p3 p2)
      (apply_cnot_g20 p3 p2)
      (apply_cnot_g22 p2 p0)

The optimal plan needs 1 swap (cf Fig. 5). The Global encoding can be obtained
in a similar manner by specifying -m global and the lifted Local Initial
encoding by using -m lifted_initial.

###  -B Complete SWAP Actions for Global and Local Initial

Listing 15: Complete SWAP actions for Global and Local Initial models

⬇

(:action swap

:parameters (?l1 ?l2 - lbit ?p1 ?p2 - pbit)

:precondition (and

(connected ?p1 ?p2)

(mapped ?l1 ?p1) (mapped ?l2 ?p2))

:effect (and

(mapped ?l1 ?p2) (not (mapped ?l1 ?p1))

(mapped ?l2 ?p1) (not (mapped ?l2 ?p2))))

(:action swap-ancillary1

:parameters (?l1 - lbit ?p1 ?p2 - pbit)

:precondition (and

(connected ?p1 ?p2)

(mapped ?l1 ?p1)

(not (occupied ?p2)))

:effect (and

(not(mapped ?l1 ?p1)) (not(occupied ?p1))

(mapped ?l1 ?p2) (occupied ?p2)))

(:action swap-ancillary2

:parameters (?l2 - lbit ?p1 ?p2 - pbit)

:precondition (and

(connected ?p1 ?p2)

(mapped ?l2 ?p2)

(not (occupied ?p1)))

:effect (and

(not(mapped ?l2 ?p2)) (not(occupied ?p2))

(mapped ?l2 ?p1) (occupied ?p1)))

## Acknowledgement

We thank L. Burgholzer for his generous help with the various versions of the
QMAP software.

Please cite this paper as:

    @inproceedings{ShaikvdP2023,
      author       = {Irfansha Shaik and
                      Jaco van de Pol},
      title        = {Optimal Layout Synthesis
                      for Quantum Circuits
                      as Classical Planning},
      booktitle    = {{ICCAD’23}},
      address      = {San Diego, CA, USA}},
      organization = {{IEEE/ACM}},
      year         = {2023}
    }

## References

  * [1] P. W. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring,” in _35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994_. IEEE Computer Society, 1994, pp. 124–134. [Online]. Available: https://doi.org/10.1109/SFCS.1994.365700
  * [2] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in _Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996_ , G. L. Miller, Ed. ACM, 1996, pp. 212–219. [Online]. Available: https://doi.org/10.1145/237814.237866
  * [3] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell _et al._ , “Quantum supremacy using a programmable superconducting processor,” _Nature_ , vol. 574, no. 7779, pp. 505–510, 2019.
  * [4] B. Tan and J. Cong, “Optimality study of existing quantum computing layout synthesis tools,” _IEEE Trans. Computers_ , vol. 70, no. 9, pp. 1363–1373, 2021. [Online]. Available: https://doi.org/10.1109/TC.2020.3009140
  * [5] M. Amy, D. Maslov, M. Mosca, and M. Roetteler, “A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits,” _IEEE Trans. Comput. Aided Des. Integr. Circuits Syst._ , vol. 32, no. 6, pp. 818–830, 2013\. [Online]. Available: https://doi.org/10.1109/TCAD.2013.2244643
  * [6] A. W. Cross, L. S. Bishop, J. A. Smolin, and J. M. Gambetta, “Open quantum assembly language,” 2017.
  * [7] D. M. Miller, R. Wille, and Z. Sasanian, “Elementary quantum gate realizations for multiple-control toffoli gates,” in _2011 41st IEEE International Symposium on Multiple-Valued Logic_ , 2011, pp. 288–293.
  * [8] M. Y. Siraichi, V. F. dos Santos, C. Collange, and F. M. Q. Pereira, “Qubit allocation,” in _Proceedings of the 2018 International Symposium on Code Generation and Optimization, CGO 2018, Vösendorf / Vienna, Austria, February 24-28, 2018_ , J. Knoop, M. Schordan, T. Johnson, and M. F. P. O’Boyle, Eds. ACM, 2018, pp. 113–125. [Online]. Available: https://doi.org/10.1145/3168822
  * [9] A. Zulehner, A. Paler, and R. Wille, “An efficient methodology for mapping quantum circuits to the IBM QX architectures,” _IEEE Trans. Comput. Aided Des. Integr. Circuits Syst._ , vol. 38, no. 7, pp. 1226–1236, 2019\. [Online]. Available: https://doi.org/10.1109/TCAD.2018.2846658
  * [10] D. Venturelli, M. Do, E. G. Rieffel, and J. Frank, “Temporal planning for compilation of quantum approximate optimization circuits,” in _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017_ , C. Sierra, Ed. ijcai.org, 2017, pp. 4440–4446. [Online]. Available: https://doi.org/10.24963/ijcai.2017/620
  * [11] K. E. C. Booth, M. Do, J. C. Beck, E. G. Rieffel, D. Venturelli, and J. Frank, “Comparing and integrating constraint programming and temporal planning for quantum circuit compilation,” in _Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling, ICAPS 2018, Delft, The Netherlands, June 24-29, 2018_. AAAI Press, 2018, pp. 366–374. [Online]. Available: https://aaai.org/ocs/index.php/ICAPS/ICAPS18/paper/view/17787
  * [12] D. Venturelli, M. Do, B. O’Gorman, J. Frank, E. Rieffel, K. Booth, T. Nguyen, P. Narayan, and S. Nanda, “Quantum circuit compilation: An emerging application for automated reasoning,” in _Proceedings of the 12th International Scheduling and Planning Applications Workshop (SPARK 2019)_ , 2019, pp. 95–103.
  * [13] M. Do, Z. Wang, B. O’Gorman, D. Venturelli, E. G. Rieffel, and J. Frank, “Planning for compilation of a quantum algorithm for graph coloring,” in _ECAI 2020 - 24th European Conference on Artificial Intelligence, 29 August-8 September 2020, Santiago de Compostela, Spain, August 29 - September 8, 2020 - Including 10th Conference on Prestigious Applications of Artificial Intelligence (PAIS 2020)_ , ser. Frontiers in Artificial Intelligence and Applications, vol. 325. IOS Press, 2020, pp. 2338–2345. [Online]. Available: https://doi.org/10.3233/FAIA200363
  * [14] G. Li, Y. Ding, and Y. Xie, “Tackling the qubit mapping problem for NISQ-era quantum devices,” in _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2019, Providence, RI, USA, April 13-17, 2019_ , I. Bahar, M. Herlihy, E. Witchel, and A. R. Lebeck, Eds. ACM, 2019, pp. 1001–1014. [Online]. Available: https://doi.org/10.1145/3297858.3304023
  * [15] S. Niu, A. Suau, G. Staffelbach, and A. Todri-Sanial, “A hardware-aware heuristic for the qubit mapping problem in the NISQ era,” _IEEE Transactions on Quantum Engineering_ , vol. 1, pp. 1–14, 2020.
  * [16] R. Wille, L. Burgholzer, and A. Zulehner, “Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations,” in _Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019, Las Vegas, NV, USA, June 02-06, 2019_. ACM, 2019, p. 142. [Online]. Available: https://doi.org/10.1145/3316781.3317859
  * [17] T. Itoko, R. Raymond, T. Imamichi, A. Matsuo, and A. W. Cross, “Quantum circuit compilers using gate commutation rules,” in _Proceedings of the 24th Asia and South Pacific Design Automation Conference, ASPDAC 2019, Tokyo, Japan, January 21-24, 2019_. ACM, 2019, pp. 191–196. [Online]. Available: https://doi.org/10.1145/3287624.3287701
  * [18] T. Peham, L. Burgholzer, and R. Wille, “On optimal subarchitectures for quantum circuit mapping,” _ACM Transactions on Quantum Computing_ , vol. 4, no. 4, jul 2023. [Online]. Available: https://doi.org/10.1145/3593594
  * [19] B. Tan and J. Cong, “Optimal layout synthesis for quantum computing,” in _IEEE/ACM International Conference On Computer Aided Design, ICCAD 2020, San Diego, CA, USA, November 2-5, 2020_. IEEE, 2020, pp. 137:1–137:9. [Online]. Available: https://doi.org/10.1145/3400302.3415620
  * [20] A. Molavi, A. Xu, M. Diges, L. Pick, S. S. Tannu, and A. Albarghouthi, “Qubit mapping and routing via MaxSAT,” in _55th IEEE/ACM International Symposium on Microarchitecture, MICRO 2022, Chicago, IL, USA, October 1-5, 2022_. IEEE, 2022, pp. 1078–1091. [Online]. Available: https://doi.org/10.1109/MICRO56248.2022.00077
  * [21] A. Botea, A. Kishimoto, and R. Marinescu, “On the complexity of quantum circuit compilation,” in _Proceedings of the Eleventh International Symposium on Combinatorial Search, SOCS 2018, Stockholm, Sweden - 14-15 July 2018_ , V. Bulitko and S. Storandt, Eds. AAAI Press, 2018, pp. 138–142. [Online]. Available: https://aaai.org/ocs/index.php/SOCS/SOCS18/paper/view/17959
  * [22] Qiskit contributors, “Qiskit: An open-source framework for quantum computing,” 2023.
  * [23] D. V. McDermott, “The 1998 AI planning systems competition,” _AI Mag._ , vol. 21, no. 2, pp. 35–55, 2000. [Online]. Available: https://doi.org/10.1609/aimag.v21i2.1506
  * [24] M. Helmert, G. Röger, and E. Karpas, “Fast downward stone soup: A baseline for building planner portfolios,” in _ICAPS 2011 Workshop on Planning and Learning_ , vol. 2835, 2011.
  * [25] C. Domshlak, M. Helmert, E. Karpas, E. Keyder, S. Richter, G. Röger, J. Seipp, and M. Westphal, “BJOLP: The big joint optimal landmarks planner,” 2011.
  * [26] S. Sievers, “Fast Downward merge-and-shrink,” _IPC-9 planner abstracts_ , pp. 85–90, 2018.
  * [27] J. Rintanen, “Madagascar: Scalable planning with SAT,” in _8th International Planning Competition_ , 2014. [Online]. Available: https://research.ics.aalto.fi/software/sat/madagascar/
  * [28] I. Shaik and J. van de Pol, “Classical planning as QBF without grounding,” in _ICAPS_. AAAI Press, 2022, pp. 329–337.
  * [29] L. Burgholzer, S. Schneider, and R. Wille, “Limiting the search space in optimal quantum circuit mapping,” in _27th Asia and South Pacific Design Automation Conference, ASP-DAC 2022, Taipei, Taiwan, January 17-20, 2022_. IEEE, 2022, pp. 466–471. [Online]. Available: https://doi.org/10.1109/ASP-DAC52403.2022.9712555
  * [30] M. Ghallab, D. Nau, and P. Traverso, _Automated Planning: theory and practice_. Elsevier, 2004.