Marcos Yukio Siraichi
email: yukio.siraichi@dcc.ufmg.br

Vinicius Fernandes
email: viniciussantos@dcc.ufmg.br

Dos Santos

Caroline Collange
email: caroline.collange@inria.fr

Fernando Magno
email: fernando@dcc.ufmg.br.

Quintão Pereira

Vinicius Fernandes

Vinícius Fernandes

Vinícius Fernandes

Santos

Qubit allocation as a combination of subgraph isomorphism and token swapping

Keywords: CCS Concepts:, Computer systems organization → Quantum computing, • Software and its engineering → Compilers, • Theory of computation → Parameterized complexity and exact algorithms Quantum computing, Qubit allocation, Graph isomorphism, Token swapping ACM Reference

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

The recent introduction of cloud access to quantum computers has made experimental quantum computing available to a wide community [START_REF] Devitt | Performing quantum computing experiments in the cloud[END_REF]]. For instance, the IBM Quantum Experience program 1 lets users build experiments based on either a visual circuit representation or a gate-level language based on the Quantum Assembler (QASM) syntax [START_REF] Cross | Open Quantum Assembly Language[END_REF]]. However, developing quantum programs is challenging: the level of abstraction offered by current programming languages is low; circuits need to obey machine-specific restrictions [START_REF] Häner | A Software Methodology for Compiling Quantum Programs[END_REF]; and today's quantum computers have tight resource constraints. As of today, IBM users have access to architectures with Qubits and Quantum Gates. Quantum programs are made of qubits and reversible quantum gates, which receive qubits as inputs, and produce qubits as outputs. The semantics of quantum programs can be expressed in terms of linear algebraic operations, and is commonly represented through the visual abstraction of quantum circuits. Figure 1 shows an example of quantum circuit. The circuit in Figure 1 has four pseudo qubits: a 0 , a 1 , b 0 , represented as horizontal lines. It uses four different types of gates to operate on these qubits: H , T , T † and CNOT. The gate CNOT ab is represented as a vertical line connecting a to b. We say that a qubit q encodes a superposition of the two classical states 0 and 1. Its state q consists of a two dimensional complex vector:

q = α |0⟩ + β |1⟩ = α 1 0 + β 0 1 = α β
Values |0⟩ and |1⟩ are the basis states of a 2D vector space, and α and β are complex numbers. A set of n qubits encodes a superposition of 2 n classical bit vectors of size n, whose state consists of a 2 n -dimension complex vector. In this terminology, quantum gates are understood as unitary matrix operations applied on vectors that describe quantum states. Example 2.1 illustrates this view.

Example 2.1. The Hadamard-Walsh gate H maps the basis state |0⟩ to (|0⟩ + |1⟩)/ √ 2, and |1⟩ to (|0⟩ -|1⟩)/ √ 2. Thus, it is equivalent to multiplying the quantum state by the matrix:

H = 1 √ 2 1 1 1 -1
Like the H and other single-qubit gates, the T gate is represented as a 2 × 2 matrix that multiplies a quantum state. Gate T † is its inverse, meaning that TT † is the identity matrix. The CNOT (short for Controlled Not) gate applies on two qubits. CNOT ab indicates that a controls b. Informally, it negates b, the second qubit, when a, the first qubit, is |1⟩. When a is |0⟩, the gate leaves b unchanged. Below, we show the matrix for the CNOT operation: CNOT = 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 A CNOT gate applies on pairs of qubits. Pairs of qubits are represented by 4-line vectors. These vectors come from the application of the tensor product ⊗ to the 2-line vectors that represent each individual qubit. Example 2.2 illustrates how pairs of qubits are combined.

Example 2.2. If |a⟩ and |b⟩ are the states of qubits a and b, then their combined state is given by the tensor product:

|a⟩ ⊗ |b⟩ = |ab⟩ = α a β a ⊗ α b β b = α a α b α a β b β a α b β a β b
The dimension of the combination is dim(|a⟩) × dim(|b⟩).

An informal summary of the semantics of a program such as the one seen on Figure 1 is the following: each individual gate, e.g., H , T † or T , represents a 2D-matrix; the application of such a gate into a qubit corresponds to matrix multiplication. Example 2.3 illustrates this view.

Example 2.3. The first column in Figure 1 (CNOT and H) corresponds to the matrix product:

(I ⊗ CNOT ⊗ H )(|a 0 a 1 b 0 b 1 ⟩)
The empty wire over the qubit a 0 represents the identity matrix I , i.e. the absence of any gate.

The single-qubit gates plus the CNOT gate form a universal set of gates that can implement arbitrary circuits [START_REF] Barenco | Elementary gates for quantum computation[END_REF]. Nevertheless, their exact semantics is immaterial to our exposition. Important to us is whether they are single-qubit or two-qubit gates. Even though sequences of single-qubit gates may sometimes be simplified away, thus reducing the total cost of the output program, we shall focus only on CNOT gates in this paper. Architectural Constraints. Actual quantum computers might not allow CNOTs to be performed between arbitrary pairs of qubits. In particular, quantum computers based on superconducting qubit technology are made of solid-state circuits that only allow interactions between physically connected qubits [START_REF] Michel H Devoret | Superconducting qubits: A short review[END_REF]]. Thus, technology restricts the possible shapes of the couplings graph, a structure whose definition we revisit below: Definition 2.4 (Coupling Graph [Gambetta et al. 2017]). Given a quantum architecture A with a set Q of qubits, its coupling graph is a directed graph G q = (Q, E q ), E q ⊆ Q ×Q. The edge q 1 → q 2 ∈ E q if, and only if, CNOT q 1 q 2 is valid in A.

Qubit Allocation

Problem 2.5 (Qubit Allocation). Input: a (directed) coupling graph G d q = (Q, E q ), a list Ψ = (P × P ) n , n ≥ 1 of n control relations between pseudo qubits p ∈ P, an integer k ≥ 0, a list of allowed quantum transformations Θ, and a function C : Θ → N that gives the cost to implement each transformation. Output: yes, if we can produce a version of Ψ that complies with G d q with transformations whose total cost does not exceed k.

In its simplest form [Siraichi et al. 2018, Def-2.4], qubit allocation is equivalent to the problem of finding an isomorphism between the coupling graph and the graph formed by the CNOT relations in the quantum circuit. However, no isomorphism might exist. When such is the case, the compiler must use transformations to fit a quantum circuit into the architecture. A quantum transformation consists of additional gates inserted in the circuit. Definition 2.6 shows the transformations Θ that we shall consider in this work. We consider only two operations: reversals and swaps, which Figure 2 illustrates. As Definition 2.5 states, transformations have a cost, which is ultimately determined by the gates necessary to implement them. In Section 4, we shall provide concrete examples of such costs. Example 2.7 shows one possible result for the allocation of the program shown in Figure 1. Definition 2.6. A transformation is a sequence of quantum operations that changes the mappings of pseudo qubits onto physical qubits. We recognize two transformations:

• Reversal: Emulation of a virtual CNOT between p a and p b controlled by p a using a CNOT from p b to p a (controlled by p b ) and 2 extra levels of Hadamard gates (Fig. 2-a). • Swap: exchanges two pseudo qubits p a and p b , at the expense of three CNOT and four Hadamard gates (Fig 2-c). Example 2.7. Given the coupling graph in Figure 3 (a), Figure 3 (c) shows a possible allocation of the program in Figure 1. Notice that when solving qubit allocation we can disregard singlequbit gates: only CNOT gates matter. These gates are represented as ordered pairs. Mapping f = {a 0 → q 0 , a 1 → q 4 , b 0 → q 2 , b 1 → q 1 } plus two reversals yields the circuit in Fig. 3 (c), which has the same semantics as the input quantum program in Fig. 3

(b).

Qubit Allocation and Register Allocation bear similarities; however, the latter is about allocating the -unlimited-virtual registers in the program to the -limited-registers in the architecture. In contrast, in quantum computing virtual qubits are also limited: we can only have as many as there are physical qubits in the architecture. The constraint is rather on the allowed interactions between qubits. It is impossible to copy the state of qubits due to the no-cloning theorem [START_REF] Wootters | A single quantum cannot be cloned[END_REF]; hence, we have to map and route them throughout the execution of the program.

Subgraph Isomorphism

Subgraph isomorphism is one of the key components of our solution to qubit allocation. For the sake of completeness, we define this problem below, and illustrate it in Example 2.9. . Input: undirected graphs G and H . Output: yes, if we can find a subgraph H ′ of H , plus a bijection f :

V (G) → V (H ′ ), where for every edge (u, v) ∈ E (G), ( f (u), f (v)) ∈ E(H ′ ).
Example 2.9. Figure 4 shows different solutions to an instance of subgraph isomorphism. Given the two undirected graphs in Figure 4 (a), G and H (left to right), Figure 4 (b) shows all possible isomorphic subgraphs. The bijections are:

• {a 0 → q 0 , a 1 → q 3 , b 0 → q 2 , b 1 → q 1 }; • {a 0 → q 0 , a 1 → q 4 , b 0 → q 2 , b 1 → q 1 }; • {a 0 → q 3 , a 1 → q 0 , b 0 → q 2 , b 1 → q 4 }; • {a 0 → q 3 , a 1 → q 1 , b 0 → q 2 , b 1 → q 4 }.
Notice that a 0 and b 1 are equivalent w.r.t. the rest of the graph; hence by switching a 0 and b 1 we double the number of bijections.

SIP is NP-complete [START_REF] Cook | The Complexity of Theorem-proving Procedures[END_REF]]. Different heuristics have been proposed to solve it [START_REF] Cordella | A (sub)graph isomorphism algorithm for matching large graphs[END_REF][START_REF] Han | Turboiso: Towards Ultrafast and Robust Subgraph Isomorphism Search in Large Graph Databases[END_REF][START_REF] Zhao | On Graph Query Optimization in Large Networks[END_REF]. As Section 3.1 will discuss, applying these heuristics would compromise the scalability of our algorithm. Therefore, we shall propose a parameterized algorithm to bound the number of instances of subgraph isomorphism to be solved, and shall rely on a greedy search to find solutions to individual instances of this problem. By bounding the search space we might not find a optimal solution to SIP. In other words, parameterization will let us exchange optimality for time.

q 2 q 0 q 1 q 3 q 4 (a 1 , b 0 ) (b 0 , b 1 ) (a 0 , b 1 ) (b 0 , b 1 ) (a 0 , b 1 ) (a 0 , b 0 ) (q 4 , q 2 ) rev (q 2 , q 1 ) (q 0 , q 1 ) rev (q 2 , q 1 ) (q 0 , q 1 ) (q 0 , q 2 ) (a) (b) (c)
q 2 q 0 q 1 q 3 q 4 b 1 b 0 a 0 a 1 • • • • • • • • • • • • • • • • • • • • (a) (b)

Token Swapping

Token Swapping is another central element to our solution to qubit allocation. This problem was introduced by [START_REF] Yamanaka | Swapping Labeled Tokens on Graphs[END_REF] in 2014, and proven to be NP-hard by [START_REF] Miltzow | Approximation and Hardness of Token Swapping[END_REF].

For completeness, we restate the definition of this problem below:

Problem 2.10 (Token Swapping -TWP). Input: a set of colors C, an integer k, an undirected graph G = (V , E), a bijective function f v : V → C representing a coloring of G, plus a bijective function f t : V → C that assigns colored tokens to vertices. Output: yes, if we can match the colors of vertices and tokens with up to k swap operations, where a swap exchanges tokens in two adjacent vertices.

Research around TWP is recent; hence, it has not been as deeply studied as SIP. Among current approaches to solve token swapping, we count two approximative algorithms [START_REF] Miltzow | Approximation and Hardness of Token Swapping[END_REF][START_REF] Yamanaka | Sequentially Swapping Colored Tokens on Graphs[END_REF], and an exponential method [START_REF] Surynek | Finding Optimal Solutions to Token Swapping by Conflict-based Search and Reduction to SAT[END_REF]]. Example 2.11 illustrates TWP. Example 2.11. Figure 5 (a) shows both f v = {q 0 → a, q 1 → b, q 2 → c, q 3 → e, q 4 → d } (bigger letters outside the circle), and f t = {q 0 → c, q 1 → d, q 2 → a, q 3 → e, q 4 → b} (smaller letters inside the circle). Thick edges in Figure 5 (b) represent swaps. The sequence of swaps (q 2 , q 4 ), (q 1 , q 2 ), (q 2 , q 4 ), (q 0 , q 2 ), takes us from f t to f v in 4 steps.

As we shall see in Section 3.2, token swapping lets us glue many different instances of the qubit allocation problem. We split the bigger problem using subgraph isomorphism, and then use token swapping to stitch solutions together. The beauty of this approach is that this splitting meets Bellman's Principle of Optimality [START_REF] Bellman | On a Routing Problem[END_REF]]. Hence, we can find an optimal solution to qubit allocation by uniting solutions of the smaller problems via dynamic programming.

q 1 q 4 q 3 q 2 • • • • • • • • • • • • • • • • • • • • (a) (b)

THE ALGORITHM

This section introduces Bounded Mapping Tree (BMT). BMT divides qubit allocation into two subproblems: Subgraph Isomorphism (Problem 2.8) and Token Swapping (Problem 2.10). BMT searches a solution space bounded by two parameters: the Maximum Number of Children and the Maximum Number of Partial Solutions. We shall clarify in Section 3.1 the meaning of these parameters. They let us control the size of the space of solutions that we search in order to solve qubit allocation. BMT consists of three different phases, which Figure 6 highlights: (i) qubit allocation is partitioned into multiple instances of subgraph isomorphism, and each instance is independently solved; (ii) all combinations of isomorphisms are evaluated via a dynamic programming model; (iii) a final program is produced out of the best combination of isomorphisms, via token swapping. The following sections discuss details of the three steps enumerated in Figure 6. Figure 7 summarizes the notation used in these sections.

Program Partitioning via Subgraph Isomorphisms

The first phase of BMT splits the list of control relations into multiple partitions, and maps the pseudo qubits in each of these subsequences into physical qubits. This phase relies on the notion of Maximal Isomorphic Sublist, which Definition 3.1 introduces, and Example 3.2 illustrates. Definition 3.1. [Maximal Isomorphic Sublist -MIS] Given a list of control relations Ψ, plus an (undirected) coupling graph G u q , we say that Ψ(i, j) is a Maximal Isomorphic Sublist if, and only if,

• [P] the set of Pseudo-Qubits in a quantum circuit.

• [Q] the set of Physical-Qubits present in the architecture. i.e. the vertices of the coupling graph.

• [f : P → Q ∪ {⊥}] the Mapping from pseudo-qubits to physical-qubits. The symbol ⊥ denotes pseudo qubits that are not mapped to any physical qubit.

• [F :

P (P → Q ∪ {⊥})] the Set of Mappings. • [G d q ]
the Directed Coupling Graph, whose vertices (Q) are physical qubits. An edge from q 1 to q 2 means that q 1 can control q 2 via a CNOT gate.

• [G u q ] the Undirected version of the Coupling Graph. • [Ψ : (P × P ) k ] a list of Control Relations. We let Ψ(i) denote the i th relation in this list, so that Ψ(i) = (p 1 , p 2 ) means that p 1 controls p 2 , i.e., via a CNOT gate. We let Ψ(i, j), 1 ≤ i < j ≤ k denote a sublist of Ψ from Ψ(i) to Ψ(j). Finally, we call Ψ i the i th partition of Ψ.

• [G Ψ ] the unique Graph determined by Ψ. The graph has a vertex v p for each pseudo-qubit p used in Ψ, and an edge

(v i , v j ) if (i, j) ∈ Ψ. • [H ≲ G] a Subgraph Isomorphism Relation indicating that H is isomorphic to some subgraph of G.
0 q 1 q 2 q 3 (r 1 , r 0 ) (r 2 , r 0 ) (r 2 , r 1 ) (r 3 , r 0 ) (r 3 , r 1 ) (r 3 , r 2 ) 1 2 3 4 5 6 Ψ G q G r 1 r 0 ✓ r 1 r 0 r 2 ✓ r 0 r 1 r 2 ✗
Fig. 8. From left to right, we have the coupling graph G d q , the list of control relations Ψ, partitioned into Maximal Isomorphic Sublists (solid boxes), and the graphs G Ψ derived from sublists of Ψ (dashed boxes). Next to each derived graph, we show if an isomorphism is possible (✓) or not (✗).

G Ψ(i, j ) ≲ G u q , and G Ψ(i, j+1) G u q or Ψ(j) is the last control relation. For simplicity, we shall refer to the set of Maximal Isomorphic Sublists of Ψ as S(Ψ) = {Ψ 1 , . . . , Ψ n }.

Example 3.2. Figure 8 shows a coupling graph G d q and a list of control relations Ψ. The derived graphs G Ψ(1,1) and G Ψ(1,2) for Ψ(1, 1) and Ψ(1, 2) can be embedded into the undirected version of the coupling graph, i.e., G u q . However, G Ψ(1,3) G u q . Thus, Ψ(1, 2) is a maximal isomorphic sublist.

The concept of maximal isomorphic sublist gives origin to the decision problem that we must solve in this phase of our algorithm. We state this problem below. Problem 3.3 (Partitioning of Control Relations -PCR). Input: an (undirected) coupling graph G u q , a list Ψ of n control relations and an integer k, k ≤ n. Output: a sequence S of k partitions Ψ(1, i 1 ), Ψ(i 1 + 1, i 2 ), . . . , Ψ(i k -1 + 1, i k ), such that for any Ψ(x, y) ∈ S, we have that G Ψ(x,y ) ≲ G u q .

Solving PCR. We solve PCR via an exhaustive recursive function S pcr , which generates every possible sublist of Ψ. Given a list Ψ(1, n) of n control relations, let us assume that the sublist Ψ(1, i) has already been split into k ′ partitions, k ′ < k. Thus, we need to split

Ψ(i + 1, n) into k -k ′ partitions.
We shall find the largest prefix of Ψ(i + 1, n) that gives us a maximal isomorphic sublist, turning it into another partition of Ψ.

To this end, we start with an empty mapping f ∅ = {}, i.e., the function that maps every pseudo qubit to an undefined physical qubit ⊥. We then update f successively for each instruction in Ψ(i + 1, n), until no longer possible. To implement S pcr , we notice that, given a mapping f , which accounts for the x -1 instructions in the sequence Ψ(i, i + x -1), plus the next instruction Ψ(i + x ), only three actions are possible. To describe these three actions, we consider that

Ψ(i + x ) = (p 1 , p 2 ).
A physical qubit that does not belong into the image of f is a free qubit. An edge in the coupling graph formed by two free qubits is a free edge:

• if f (p 1 ) = ⊥ and f (p 2 ) = ⊥, then, for every free edge (q 1 , q 2 ) ∈ E(G u q ), we create a new mapping f ′ = f ∪ {p 1 → q 1 , p 2 → q 2 }, and call S pcr recursively for every f ′ and Ψ(i +x +1, n).

• if f (p 1 ) = ⊥ and f (p 2 ) ⊥ (or f (p 1 ) ⊥ and f (p 2 ) = ⊥), then only one of the pseudo qubits needs to be mapped. Without loss of generality, let us assume that f (p 1 ) = ⊥ and f (p 2 ) ⊥. For every ( f (p 1 ), q 2 ) ∈ E(G u q ), such that q 2 is free, we create a new mapping f ′ = f ∪ {p 2 → q 2 }, and continue recursively for every f ′ and the remaining list.

• if f (p 1 ) ⊥, f (p 2 ) ⊥ and ( f (p 1 ), f (p 2 )) ∈ E (G u q )
, then no update is necessary. We continue recursively on f , Ψ(i + x + 1, n). If none of these three actions is possible, then Ψ(i, i +x -1) defines another partition as a maximal isomorphic sublist. In this case, we create a set of mappings F k ′ +1 containing all mappings that satisfy G Ψ(i,i+x -1) ≲ G u q , and invoke S pcr over the remaining list, this time with an empty mapping.

The cost of a maximal isomorphic sublist. Function S pcr creates a sequence of sets of mappings F 1 , F 2 , . . . , F m , m ≤ k. These sets range over the undirected version of the coupling graph; however, the final product of our qubit allocation must be assigned to the actual, i.e., directed, version. Any mapping onto G u q can be adjusted onto G d q , because we can use reversals, a quantum transformation introduced by Definition 2.6, to invert the semantics of an edge in the coupling graph. Yet, each reversal has a constant cost. Given a mapping f ∈ F k ranging over the sublist Ψ(i, j), we define its cost as the sum of the costs over each individual instruction Ψ(x ) ∈ Ψ(i, j). If Ψ(i) = (p 1 , p 2 ), then this individual cost is given by the necessity to apply an inversion to implement the edge ( f (p 1 ), f (p 2 )). Definition 3.4 formalizes this cost function: Definition 3.4 (Cost of Mapping). If f is a mapping from pseudo qubits to physical qubits, then its cost is given by a function C :

Ψ×F ×G d q → R. Given pseudo qubits p 1 , p 2 ∈ P, if ( f (p 1 ), f (p 2 )) ∈ G d q , then the cost is zero; otherwise, it is a constant C r ev .
Example 3.5. Given the coupling graph G u q and the list Ψ shown in Figure 8, we computed the set of mappings for the first two instructions. Figure 9 illustrate these generated mappings for each one of the instructions that compose the first partition, as well as the cost for each one of them. Considering C r ev = 4, below, we describe the steps we used for each instruction:

(1) Process (r 1 , r 0 ): both, r 1 and r 0 , are mapped to ⊥, and all the edges in the coupling graph are free. Thus, we map (r 1 , r 0 ) to any edge. There are six possible mappings. Cost: since q 0 has only outgoing edges, whenever r 1 is not mapped to q 0 , we have a cost of 4; (2) Process (r 2 , r 0 ): r 0 was mapped in the previous step; hence, we need to allocate r 2 . Each one of the six mappings of the previous step yields different possibilities for r 2 . For example, the mapping {r 1 → q 1 , r 0 → q 0 } gives us two possible locations for r 2 in the coupling graph: 9. Exhaustive mapping tree produced from the first instruction (r 1 , r 0 ) in our running example. The notation p • q indicates that pseudo qubit p is mapped onto physical qubit q. Mappings marked with ✗ are dead-ends, i.e., we cannot continue the exhaustive construction of new mappings from them. We show the cost of each mapping next to it. q 2 or q 3 . On the other hand, some mappings found in the previous step are dead-ends. For instance, {r 1 → q 0 , r 0 → q 1 } leaves no vertex for r 2 , because the only neighbour of q 1 in the coupling graph is exactly q 0 , which was already taken by r 0 . Cost: we sum the cost of the parent mapping with the cost of using the edge ( f (r 2 ), f (r 0 ));

(r 1 , r 0 ) (r 2 , r 0 ) r 1 • q 0 r 0 • q 1 ⇒ 0 ✗ r 1 • q 0 r 0 • q 2 ⇒ 0 ✗ r 1 • q 0 r 0 • q 3 ⇒ 0 ✗ r 1 • q 1 r 0 • q 0 ⇒ 4 r 1 • q 2 r 0 • q 0 ⇒ 4 r 1 • q 3 r 0 • q 0 ⇒ 4 r 1 • q 1 r 0 • q 0 r 2 • q 2 ⇒ 8 ✗ r 1 • q 1 r 0 • q 0 r 2 • q 3 ⇒ 8 ✗ r 1 • q 2 r 0 • q 0 r 2 • q 1 ⇒ 8 ✗ r 1 • q 2 r 0 • q 0 r 2 • q 3 ⇒ 8 ✗ r 1 • q 3 r 0 • q 0 r 2 • q 1 ⇒ 8 ✗ r 1 • q 3 r 0 • q 0 r 2 • q 2 ⇒ 8 ✗ Fig.
(3) Process (r 2 , r 1 ): adding this instruction to the sequence [(r 1 , r 0 ), (r 2 , r 0 )] makes it impossible to find a valid subgraph in G u q . Hence, Ψ(1, 2) is a maximal isomorphic subgraph, and to map (r 2 , r 1 ) we must start afresh.

Dealing with Combinatorial Explosion. Function S pcr is exponential, and becomes quickly unpractical as its input grows. To mitigate this problem, we bound the number of mappings via two parameters: (i) the maximum number of children mappings and (ii) the maximum size of the set of current mappings. The first parameter controls how many searches start from each mapping. The other limits the number of mappings that we can consider. Figure 10 illustrates these two forms of pruning. Pruning happens whenever we try to add a new instruction onto the current partition. We use the weight of each mapping for pruning, by using a roulette weighted selection. In other words, we select the mappings randomly, using their weights as a probability mass function.

In the end of this first phase, we have the input program sliced into up to

k partitions S = Ψ(1, i 1 ), Ψ(i 1 +1, i 2 ), . . . , Ψ(i k -1 +1, i k ), plus the corresponding sets of mappings F = F 1 , F 2 , . . . , F n . Each F j contains multiple ways to map Ψ(i j-1 + 1, i j ) onto G u q .
Each partition Ψ(x, y) gives origin to a derived graph G Ψ(x,y ) isomorphic to some subgraph of G u q . A byproduct of this phase is the cost of each mapping, which is given by the function C from Definition 3.4. Iterating the Quantum Program. Instructions in a quantum circuit do not have to be processed in the order defined by that circuit. Quantum gates over non-overlapping qubits may be executed in parallel; hence, we can change their order without changing the semantics of the program. Nevertheless, we still have to keep the gate sequence applied on each qubit. Therefore, to iterate over quantum programs, we use a directed acyclic graph (DAG) whose vertices represent gates. An edge (д i , д j ) indicates that д i should be executed before д j . A topological ordering of this graph determines the valid ways to iterate over the program. Whenever multiple orderings are possible, we select the next gate to be processed based on four criteria. To explain these predicates, suppose that (a, b) are pseudo-qubits linked by a candidate gate:

(1) a and b are mapped to adjacent physical-qubits;

(2) one of a or b is already mapped;

(3) none of a and b are mapped; (4) both a and b are mapped.

f f ′ 0 f ′ k • • • • • • • • • (a) (b) Instruction Number 21 22 23
Fig. 10. Tree of mappings for one partition. The i t h level represents the possible mappings once we add the i th instruction (on the left) to the mappings already in place. Since the number of leaves grows exponentially, we limit them with two parameters: M c : maximum number of children of each mapping, and M p : maximum number of mappings per partition. Complexity Analysis of the First Phase. We are generating exhaustively all the mappings that solve the subgraph isomorphism problem. To avoid the exponential complexity, we limit the generation process with two parameters: maximum number of children (M c ) and maximum number of partial solutions (M p ). Thus, for every instruction, we have to generate M c mappings for each of the M p partial solutions. Children mappings are created in O (|Q |). Therefore, the time complexity of the first phase is O (M c M p |Ψ||Q |). Since we keep up to M p mappings for each partition (which cannot be greater than |Ψ|), and each mapping takes O (|Q |) space, the space complexity is

f 1 1 f 1 2 . . . f 1 k1 F 1 f 2 1 f 2 2 . . . f 2 k2 F 2 • • • f n 1 f n 2 . . . f n kn F n F =
O (M p |Ψ||Q |)

Combining Mappings via Token Swapping

In Section 3.1 we have split the list of control relations into partitions, and created a set of mappings for each one of them. Now, we need to connect these partitions, adapting, via swaps, one mapping into another. Figure 11 illustrates this idea: for each partition we have a collection of candidate mappings F . We must find a path from some mapping f i ∈ F 1 to some mapping f n ∈ F n which minimizes the cost of implementing the program. Each path consists of n -1 hops. A hop is a way to transform

f i ∈ F i into f i+1 ∈ F i+1 .
This transformation is equivalent to Token Swapping. There exist |F i | × |F i+1 | possible paths between two successive sets of candidates F i and F i+1 . Thus, the number of paths between F 1 and F n is exponentially large. Hence, to find the optimal path illustrated in Figure 11, we must solve an NP-complete problem -token swapping-an exponential number of times! Fortunately, there are ways to approximate Token-Swapping [START_REF] Miltzow | Approximation and Hardness of Token Swapping[END_REF]], as we discuss in Section 3.2.1; and we can handle the combinatorial explosion of paths via dynamic programming, as we explain in Section 3.2.2.

3.2.1

Solving the Token Swapping Problem. Recently, [START_REF] Miltzow | Approximation and Hardness of Token Swapping[END_REF] presented a solution for the Token Swapping Problem that is proven to be 4-approximative. This algorithm is at least cubic on the size of the coupling graph, e.g., O (|Q | 3 ); however, we must still run it for at least min |F i | 2 × #Partitions -a task that becomes impractical even for small settings. Fortunately, Miltzow et al. also gave us the necessary equipment to avoid this effort. Thus, instead of finding approximations for every instance of the Token-Swapping Problem, we only estimate the cost of each one of these problems (without providing an actual solution to it). We use the function δ from Definition 3.6 to find such estimates. As noted in Miltzow et. al., the number of swaps -henceforth denoted by |∆( f pr ev , f )| -is less or equal to 2 × δ ( f f r eq , f ). Thus, we use this upper bound as the estimation of the number of swap operations. Example 3.7 illustrates this estimate.

Definition 3.6 (Cost of joining two successive mappings). Let d : Q × Q → N be a function that yields the minimum number of edges between two vertices in the coupling graph: f (a) and f pr ev (a). We define δ as follows:

δ ( f pr ev , f ) = p ∈P, f pr ev (p ) ⊥ d ( f pr ev (p), f (p))
Example 3.7. Figure 12 shows the sequence of swap operations that transform

f pr ev = {a → q 2 , b → q 0 , c → q 3 , d → q 1 } into f = {a → q 3 , b → q 0 , c → q 1 , d → q 2 }
, using the architecture from Figure 8. The δ function gives us an estimate, not the best solution for the Token-Swapping Problem. In this example, δ ( f pr ev , f ) = d (q 2 , q 3 ) + d (q 0 , q 0 ) + d (q 3 , q 1 ) + d (q 1 , q 2 ) = 6, yet the optimal swap sequence between f pr ev and f has 4 swaps.

q0 {b} q1 {d } q2 {a} q3 {c} q0 {b} q1 {d } q2 {a} q3 {c} q0 {a} q1 {d } q2 {b} q3 {c} q0 {c} q1 {d } q2 {b} q3 {a} q0 {d } q1 {c} q2 {b} q3 {a} q0 {b} q1 {c} q2 {d } q3 {a} f prev (1) (2)
(3) (4) f Fig. 12. Steps for transforming f pr ev into f , assuming the coupling graph seen in Figure 8. The pseudo qubit assigned to a physical qubit is shown in brackets. Gray edges indicate qubits that shall be swapped.

Ensuring that live qubits remain mapped. If a pseudo qubit p appears for the first time in a control relation Ψ(i), and for the last time in a control relation Ψ(j), we say that p is alive at Ψ(i, j). If a pseudo qubit is alive at Ψ(i, j), then it must be allocated to a physical qubit at every mapping f related to a partition containing instructions from Ψ(i, j). Otherwise, we would produce an incorrect quantum circuit, which might "overwrite" qubits still in use. However, this hazard would naturally happen if some partition Ψ(i ′ , j ′ ) ⊂ Ψ(i, j) does not contain any reference to p. Example 3.8. Pseudo qubit r 0 is alive at the second partition in Fig. 8; however, this partition only contains instruction Ψ(3) = (r 2 , r 1 ). A solution to PCR sets f (r 0 ) = ⊥ at partition 2. Yet, r 0 shall be necessary in the third partition; hence, it must be propagated from the first mapping to the third.

To prevent this kind of situation, we ensure that qubits are allocated at every partition where they are alive. To explain how we do it, lets us assume that p is alive at Ψ(i ′ , j ′ ), but is not used within that partition. Let f ′ be a mapping for Ψ(i ′ , j ′ ), where f ′ (p) = ⊥. We assume that f pr ev is the mapping for the previous partition, and that f pr ev (p) = q. We can safely assume that p is mapped by f pr ev by an inductive argument: p is mapped at the first partition where it is used, and we shall propagate it along other mappings, until the last partition that uses it. To ensure that p's image is defined at f ′ , we let f ′ (p) = q ′ , where q ′ is the unmapped qubit that is the closest to f pr ev (p). To see that q ′ exists, notice that there is always more pseudo qubits than physical qubits, and a pseudo qubit is never mapped onto two different physical qubits in the same partition.

Dynamic

Programming. The approximations discussed in Section 3.2.1 give us the means to calculate the cost of transforming one mapping into another, thus bridging two successive partitions of Ψ. Yet, we must find one such path between every pair of successive partitions, as Figure 11 illustrates. As we have already discussed, the number of paths is exponentially high, in terms of the number of partitions. However, the problem of finding an optimal path admits an exact solution in polynomial time, via a dynamic programming algorithm. To explain how this algorithm works, we first introduce the problem that it solves: Problem 3.9 (Construction of a Complete Seqence of Transformations). Input: a sequence of n sets of mappings of pseudo to physical qubits F 1 , F 2 , . . . , F n , the function C from Definition 3.4 and the function δ from Definition 3.6. output:

a sequence f 1 , f 2 , . . . , f n , f i ∈ F i , which minimizes δ ( f i-1 , f i ) + C ( f i ).
Problem 3.9 has optimal substructure. In other words, it can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to each sub-problem. Problems with such property admit exact solution via dynamic programming [START_REF] Bellman | On a Routing Problem[END_REF]]. Definition 3.10 describes the dynamic programming subproblem, and Equation 1 shows its recurrence relation. In Theorem 3.11 we state and prove the correctness of our solution. Finally, Example 3.13 illustrates how we solve Problem 3.9. Definition 3.10. (Subproblem) Our subproblem OPT (i, j) represents the optimal cost for allocating all control relations until the i-th partition, while using f i j (the j-th mapping that satisfies the subgraph isomorphism relation between the i-th partition and the coupling graph) as the last mapping. i.e. it is the minimum cost using the j-th mapping generated for the i-th partition.

OPT (i, j) =              C (Ψ i , f i j ) i = 1 min 0≤k < |F i -1 | δ ( f i-1 k , f i j ) + OPT (i -1, k ) + C (Ψ i , f i j ) i > 1 (1)
Theorem 3.11. The recurrence relation given by Equation 1 yields an optimal solution to Problem 3.9.

Proof 3.12. The proof is a case analysis on the two branches of function OPT:

(1) Base Case: i = 1 (there is only one partition). Since we have only one partition, and we are allocating it with f i j by definition, that is the optimal cost; (2) Inductive Case: i > 1. Suppose OPT (i, j) is not optimal. Since it is not optimal, there must exist another mapping f i-1 k ′ from the previous partition i -1 such that we profit more when transform-

ing f i-1 k ′ into f i j . Thus, δ ( f i-1 k ′ , f i j )+OPT (i-1, k ′ ) < OPT (i, j) = min k δ ( f i-1 k , f i j ) + OPT (i -1, k ) must be true, a contradiction. (r1, r0) (r2, r0) (r2, r1) (r3, r0) (r3, r1) (r3, r2) r1 • q1 r0 • q0 r2 • q2 Cost = 8 OPT = 8 r1 • q1 r0 • q0 r2 • q3 Cost = 8 OPT = 8 r1 • q2 r0 • q0 r2 • q1 Cost = 8 OPT = 8 r1 • q2 r0 • q0 r2 • q3 Cost = 8 OPT = 8 r1 • q3 r0 • q0 r2 • q1 Cost = 8 OPT = 8 r1 • q3 r0 • q0 r2 • q2 Cost = 8 OPT = 8 r1 • q0 r2 • q1 r1 • q0 r2 • q2 r1 • q0 r2 • q3 r1 • q1 r2 • q0 Cost = 0 OPT = 10 r1 • q1 r2 • q0 r1 • q2 r2 • q0 r1 • q3 r2 • q0 δ = 2 δ = 2 δ = 4 δ = 4 δ = 4 δ = 4 Ψ1 Ψ2
Fig. 13. Subproblem dependency for calculating OPT of the highlighted mapping. It shall be the minimum value of the sum of each dependency by its cost δ of transforming the previous one into the highlighted one.

Example 3.13. Figure 13 shows how we test all combinations of mappings for the first two program partitions. Calculating OPT (1, j) for any 1 ≤ j ≤ |F 1 | is trivial (base case). For the other case, given the recurrence relation, we have to get the minimum value given by the sum of the previous subproblems' optimal solution, plus the estimated number of swap operations for transforming one mapping into another. In this case, every subproblem has an optimal cost of 8; hence, we pick the solution with the smallest estimated transformation cost δ = 2. We repeat the process for every f ∈ F 2 .

Complexity Analysis of the Second Phase. In the worst case, we have |Ψ| partitions, each formed by one instruction. Each partition gives us up to M p mappings. For each mapping, we have to find the minimum cost between all the M p previous mappings, according to Equation 1

Code Generation

The dynamic programming algorithm discussed in Section 3.2.2 gives us a sequence of mappings f 1 , f 2 , . . . , f n , which shall guide us through the process of building a concrete program out of a virtual quantum circuit. Each mapping corresponds to a partition of Ψ. Let f 1 be the mapping for Ψ(i, j). Mapping f gives us the information necessary to allocate all the virtuals used between the first control instruction, e.g., Ψ(i) and the last, e.g., Ψ(j). After Ψ(j), a new partition, Ψ(j + i, k ), starts. Let us assume that the mapping that corresponds to this partition is f 2 . We need to create sequences of swaps linking f 1 and f 2 . We shall use the term ∆( f 1 , f 2 ) to denote this sequence. Figure 14 shows the product of this phase. From estimates (δ ) to concrete sequences (∆). In Section 3.2 we used a heuristic, the δ function, to over-estimate the quantity of swapping operations necessary to link consecutive mappings. To generate code, we replace this function with the 4-approximative algorithm used by [START_REF] Miltzow | Approximation and Hardness of Token Swapping[END_REF] to solve the Colored Token Swapping Problem. The δ function is an over-approximation of Miltzow et al.'s algorithm. Thus, the actual cost of the sequence of swaps ∆ that links two successive mappings might be lower than the cost found through δ . Dealing with partially defined mapping functions. Miltzow et al.'s approximation receives two mappings, f pr ev and f , and finds a sequence of swaps that transform f pr ev into f . In their original formulation, [START_REF] Miltzow | Approximation and Hardness of Token Swapping[END_REF] assume that f pr ev and f are permutations, i.e., functions with the same domain and image. However, in our case, these mappings do not necessarily enjoy this property, as the live ranges of virtual qubits are not always the same. In other words, we must account for any virtual qubit p such that f pr ev (p) = ⊥ and f (p) ⊥. We recall that we do not need to consider the possibility of f pr ev (p) ⊥ and f (p) = ⊥. This case will never happen, because, as discussed in Section 3.2.1, we ensure that live qubits remain always mapped. To make provision to partially defined mappings, we introduce a projection operator ▽:

f 1 ∆( f 1 , f 2 ) f 2 ∆( f 2 , f 3 ) • • • ∆( f n-1 , f n ) f n
( f pr ev ▽f )(p) =      q f (p) = q and f pr ev (p) ⊥ ⊥ f (p) = q and f pr ev (p) = ⊥
Instead of solving token swapping between f pr ev and f , we solve it between f pr ev and f pr ev ▽f . In other words, we solve the problem only for virtual qubits which are defined in both mappings. Lemma 3.14 shows that this approach is sound. Example 3.16 illustrates this phase with the input program used in the previous sections. Lemma 3.14. Let undef ( f ) = {p | f (p) = ⊥, p ∈ P }. Given the mapping f ′ = f pr ev ▽f , if the set undef ( f pr ev ) ⊇ undef ( f ), then ∆( f pr ev , f ′ ) is the minimum swap sequence we can get for ∆( f pr ev , f ).

Proof 3.15. Since undef ( f pr ev ) ⊇ undef ( f ), all pseudo-qubits mapped to a physical-qubit q, q ⊥, in f pr ev are defined in f . Thus, we have to allocate, at least, these pseudo-qubits. That is exactly what f ′ is: a mapping of the pseudo-qubits mapped in f pr ev to their respective physical-qubits mapped in f . Example 3.16. Figure 15 (a) shows the mappings selected for each partition of the program. Notice that the second mapping r 1 → q 1 , r 2 → q 0 , r 0 → q 2 is well-defined for r 0 , although this pseudo qubit is not used in the second partition, for the reasons that we have discussed in Example 3.8. From these mappings, we are able to calculate the ∆ function for each pair of consecutive partition. Figure 15 (b) shows the output generated in the end. All the instructions (Input Control Relations) are translated into physical-qubits, and swapping operations are used to bridge differences between consecutive mappings.

Complexity Analysis of the Third Phase. The algorithm given by [START_REF] Miltzow | Approximation and Hardness of Token Swapping[END_REF] is timewise expensive. That is because one of its steps is composed by the Hungarian Algorithm for minimum matching [W. 1955] (O (|Q | 3 )). Besides that, the algorithm's main loop will execute O (|Q |) breadth first searches (BFS) for each swap. Thus, the complexity of the approximative algorithm is

O (|Q | 3 + |∆||Q |(|Q | + E (G u q ))).
|∆| is bounded by the sum of the distance of misplaced qubits. Miltzow's algorithm runs once per partition (|Ψ| -1 times). Thus, the complexity of this phase is

O (|Ψ|(|Q | 3 + |∆||Q |(|Q | + E(G u q ))))
. The space complexity is the product of the number of mappings for each partition, O (|Ψ||Q |), and the space-complexity of the approximative algorithm

O (|Q | 2 ). (r 1 , r 0 ) (r 2 , r 0 ) (r 2 , r 1 ) (r 3 , r 0 ) (r 3 , r 1 ) (r 3 , r 2 ) r 1 • q 1 r 0 • q 0 r 2 • q 2 r 1 • q 1 r 2 • q 0 r 0 • q 2 r 3 • q 0 r 0 • q 2 r 1 • q 1 r 2 • q 3
(q 1 , q 0 ) (q 2 , q 0 ) swap(q 0 , q 2 ) (q 0 , q 1 ) swap(q 0 , q 3 ) (q 0 , q 2 ) (q 0 , q 1 ) (q 0 , q 3 ) (a) (b)

EVALUATION

In this section, we shall provide answers to the following research questions:

• [RQ1]: how do the parameters of our algorithm: maximum number of children and maximum number of partial solutions, affect the solution that it produces to qubit allocation? • [RQ2]: how does our algorithm compare with state-of-the-art approaches in terms of quality of solution? • [RQ3]: how efficient is our algorithm, in terms of space and time, compared with state-ofthe-art approaches? • [RQ4]: how does the target architecture influence the performance of BMT, compared to other qubit allocation algorithms? The algorithms used in this evaluation: We compare BMT against five algorithms: IBM's python sdk (QISKit); Siraichi et al. [2018] [2019] dedicated SU(4) compiler, which won the IBM QISKit challenge in 2018. Henceforth, we shall refer to these algorithms as ibm, wpm, jku2 , sbr and chw. We emphasize that none of these algorithms is guaranteed to find a global optimum, because they all resort to some simplification of the problem, even those that run an exhaustive search, such as jku. In our case, we segment the program greedily, and use an approximative algorithm to solve token swapping. BMT Configuration: We have selected the values for the two parameters in our algorithm empirically to obtain a good compromise between runtime and quality of solution. We shall consider two versions of BMT : bmtF and bmtS. The former is a faster version of BMT, which uses M c = 4 and M p = 320. The latter, the slower version, uses a more time consuming parametrization of BMT, featuring M c = 8 and M p = 1, 280. As we shall discuss in Section 4.1, bmtF produces circuits about 1% more costly than bmtS; however, it runs approximately 70% faster.

For the sake of fairness when performing runtime comparisons, we have implemented all the allocators in our C++ OpenQASM open source compiler Enfield. The compiler has an online interface, publicly available at http://cuda.dcc.ufmg.br/enfield/, where users can try all the different algorithms used in our empirical evaluation. Our implementation follows the original Python version of each algorithm. We certify that results remain unchanged by comparing outputs. Our implementation is always faster and more memory frugal than the original version of each algorithm, because we use C++ instead of Python. Runtime Environment. Most of the tests were executed on a dedicated server featuring an Intel(R) Xeon(TM) E5-2660 CPU @ 2.20GHz, with up to 32GB RAM, running Linux Debian Jessie 8.11. The experiments in Section 4.4 were executed in a commodity laptop, featuring an Intel i7 4700MQ @ 2.4GHz, with 8GB RAM, running Linux Debian Stretch 9.9. We chose a smaller machine for this last experiment to avoid paying the cost of the dedicated server. Benchmarks. We used the benchmarks evaluated by [START_REF] Zulehner | Efficient mapping of quantum circuits to the IBM QX architectures[END_REF]. These 158 programs were taken from the RevLib collection [START_REF] Wille | RevLib: An Online Resource for Reversible Functions and Reversible Circuits[END_REF], Quipper [START_REF] Alexander S Green | Quipper: a scalable quantum programming language[END_REF], and Scaf-fCC [START_REF] Javadi-Abhari | ScaffCC: a framework for compilation and analysis of quantum computing programs[END_REF]]. These suites are staple in papers on Qubit Allocation [START_REF] Lao | Mapping of Lattice Surgery-based Quantum Circuits on Surface Code Architectures[END_REF][START_REF] Li | Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices[END_REF][START_REF] Lin | PAQCS: Physical Design-Aware Fault-Tolerant Quantum Circuit Synthesis[END_REF][START_REF] Lin | Layout Synthesis for Topological Quantum Circuits With 1-D and 2-D Architectures[END_REF][START_REF] Pedram | Layout Optimization for Quantum Circuits with Linear Nearest Neighbor Architectures[END_REF][START_REF] Shafaei | Qubit placement to minimize communication overhead in 2D quantum architectures[END_REF][START_REF] Zulehner | Efficient mapping of quantum circuits to the IBM QX architectures[END_REF]. We have opted to use these benchmarks, instead of those recently used in the IBM Challenge because whereas the latter are randomly generated, our benchmarks are actual quantum circuits. We believe that the randomly produced patterns from IBM are not a good reflex of typical quantum circuits, because they show regularity that we cannot find in human-produced programs. Our collection, on the other hand, is more varied, because it was taken from three different sources, and even within a single source, programs were written by more than one person. Target architecture. The algorithms compared in this section work for any quantum architecture. In this paper we will use ibmqx20, "Tokyo" [IBM 2016]. To the best of our knowledge, Tokyo is the largest quantum computer publicly available as of February 2019. In Section 4.4, we shall experiment with the ibmqx3, "Albatross", which has 16 qubits, instead of 20. Allocation Quality. The quality of each solution will be evaluated along three dimensions:

• Weighted Cost: the combined cost of each gate used in the program. Following common methodology[IBM 2016], we let the cost of each CNOT be 10, and of each single-qubit gate be 1. As discussed by Zulehner and Wille [Zulehner and Wille 2019, Sec.5], the rationale behind this cost assignment is the fact that CNOT gates have an error rate one order of magnitude larger than single-qubit gates. Defining only these two costs is enough for all practical purposes, because composite gates may be rewritten as a sequence of single-qubit gates and CNOTs. • Gates: the total number of gates in the allocated program, without distinguishing CNOTs from single-qubit gates. This metric has been adopted in previous work [START_REF] Li | Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices[END_REF][START_REF] Pedram | Layout Optimization for Quantum Circuits with Linear Nearest Neighbor Architectures[END_REF][START_REF] Shafaei | Qubit placement to minimize communication overhead in 2D quantum architectures[END_REF][START_REF] Shrivastwa | Fast Qubit Placement in 2D Architecture Using Nearest Neighbor Realization[END_REF][START_REF] Zulehner | Efficient mapping of quantum circuits to the IBM QX architectures[END_REF]]. • Depth: the depth is closely related to the time a program takes to terminate. It is measured as the longest path that must be traversed to run a quantum circuit. This metric has also being used in previous work [START_REF] Amy | A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits[END_REF][START_REF] Maslov | Quantum Circuit Placement[END_REF][START_REF] Zulehner | Efficient mapping of quantum circuits to the IBM QX architectures[END_REF]]. Theoretically, given a quantum computer that executes operations simultaneously for disjoint sets of qubits, a program 2x deeper is likely to be 2x slower. The main benefit of running quantum programs faster is to minimize noise due to decoherence effects, which are exponential with respect to time. A 2x speedup would theoretically enable a quadratic improvement for decoherenceinduced error.

Allocation Efficiency. The efficiency of each solution will be evaluated along two dimensions:

• Memory Consumption: peak memory that each qubit allocation uses to process a quantum circuit, gauged by reading /proc/self/status. • Allocation Time: the time that each allocator needs to process a quantum circuit. Summary of Results: Figure 16 summarizes the comparison between our approach and the five algorithms we consider. Assuming that R foo and R bmt correspond respectively to a given algorithm and to bmtS, results are given by the ratio R f oo /R bmt . Each algorithm is represented by a major row. [orse] Count: the number of benchmarks where the algorithm was better (worse) than bmtS. We use a hyphen ("-") to mark cases where no benchmark exists. B.

[etter] (W.

[orse]) G. Mean: the geometric mean of the ratios of the benchmarks where the algorithm was better (worse) than bmtS. This column answers the following question: "what would be the G. Mean for this allocator, considering only the benchmarks where it performed better (worse) than bmtS?" Except for Better Count (B. Count), the higher the reported value, the better for bmtS.

Sub-rows (cost, depth, gates, mem and time) represent dimensions of quality and efficiency. In what follows, we shall analyze the five dimensions of efficiency that we have reported in Figure 16: cost, depth, gates, memory and time. The important message from Figure 16 is that bmtS outperforms all the other algorithms in terms of cost, depth and number of gates that it produces on average. Moreover, its closest competitor is bmtF -another contribution of this paper. Li et al.'s SABRE (sbr) yields the next best results; however, its cost is still 25% higher than bmtS.

RQ1: The Influence of Parameters

As we explained in Section 3.1, the search that BMT carries out on the universe of solutions is bounded by two parameters: M c , the maximum number of children; and M p , the maximum number of partial solution. To observe how these parameters impact the quality of BMT's solutions, and the runtime of this algorithm, we have performed an exhaustive batch of experiments with seven different values of M c and nine different values of M p , for a total of 54 combinations. The values that we chose for each parameter are: M c : 1, 2, 4, 8, 16, 32, and M p : 10, 20, 40, 80, 160, 320, 640, 1280, 2560. We run BMT three times for each combination of parameters, for each one of the 158 available benchmarks. Figure 17 summarizes this result. In this figure, we compare each combination of parameters against our BMT with these two parameters, e.g., M p and M c , set to 32 and 2,560, respectively. Larger values are possible, but operating with them becomes very time consuming, and we chose not to do it. We shall call this version of our algorithm BMT top . In other words, Figure 17 reports ratios in which each dimension of efficiency is compared against that same metric when M c = ∞ and M p = ∞. Each cell of Figure 17 contains two values: a ratio (taking BMT top as the baseline) and that ratio's standard deviation (Cost) Ratio of the cost of circuits produced by the different allocators using the cost of the circuit produced by bmtS as the baseline. The Y-axis shows the ratio of the weighted cost. The X-axis shows the benchmarks -each tick represents a different quantum circuit. Less is better. If we sum up the costs of all the 158 circuits, then we obtain the following absolute numbers, in ascending order: bmtS=24.5M, bmtF=25.3M, jku=29.6M, sbr=30.3M, chw=36.8M, ibm=40.3M and wpm=50.0M. Figure 16 reports averages.

) ptt -1.30-(1.13) -1.15-(1.08) -1.08-(1.05) -1.03-(1.03) -1.01-(1.02) -1.01-(1.04) -1.00-(1.01) -1.00-(1.01) -1.00-(1.01) cost -1.43-(1.09) -1.27-(1.07) -1.18-(1.05) -1.11-(1.04) -1.07-(1.02) -1.04-(1.02) -1.02-(1.02) -1.01-(1.01) -1.00-(1.01) depth -1.24-(1.06) -1.14-(1.04) -1.09-(1.03) -1.06-(1.03) -1.04-(1.02) -1.03-(1.02) -1.01-(1.02) -1.01-(1.02) -1.00-(1.01) gates -1.28-(1.06) -1.18-(1.04) -1.12-(1.03) -1.08-(1.03) -1.05-(1.02) -1.03-(1.02) -1.02-(1.01) -1.01-(1.01) -1.00-(1.
Analysis of results. As expected, the quality of the solution improves as we increase both M c and M p . That is to say, the higher the values of M c and M p , the lower the allocation cost produced by BMT. A bit smaller configuration, M c = 8 and M p = 1, 280, yield allocation costs within 2% of BMT t op . However, raising M p to 2,560 already gives results comparable to BMT top when M c = 4, but in 67% of BMT t op 's time. If we accept to produce circuits that are 3% more costly, then we can reduce the runtime of our algorithm even more: Setting M c = 4 and M p = 320 we remain within this bound, but run in 21% of the time taken by BMT top , on average.

RQ2: Quality of Allocation

Figure 18 compares the different allocators in terms of the circuits that they produce. Analyzing this figure in tandem with Figure 16, we can draw the following conclusions:

• Weighted Cost: bmtS yields the lowest cost. sbr, jku, chw, ibm, and wpm were 25%, 47%, 83%, 91%, and 125% worse than our algorithm, respectively. The faster version of BMT, e.g. bmtF, also outperforms the other algorithms. They were, respectively, 22%, 44%, 80%, 87% and 120% worse than bmtF. bmtF was only 2% worse than bmtS; • Depth: bmtS yields the smallest depth on average. sbr, jku, chw, ibm, and wpm were 35%, 44%, 92%, 76%, and 116% worse than our algorithm, respectively. The faster version of BMT, e.g. bmtF, also outperforms the other algorithms. They were, respectively, 32%, 41%, 88%, 73% and 113% worse than bmtF. bmtF was only 1.7% worse than bmtS; • Gates: bmtS yields the smallest number of gates. sbr, jku, chw, ibm, and wpm were 16%, 27%, 47%, 55%, and 75% worse than our algorithm, respectively. The faster version of BMT, e.g. bmtF, also outperforms the other algorithms. They were, respectively, 14%, 25%, 45%, 52% and 72% worse than bmtF. bmtF was only 1.8% worse than bmtS; Analysis of results. bmtS wins in cost, depth and gates, followed closely by bmtF. Both algorithms outperform sbr, jku, ibm, and wpm by a large margin. BMT's parameters allow users to, given enough time and space, find better and better solutions. The fact that our algorithm outperforms the others in terms of cost, depth and gates indicates that we generate circuits with smaller error The Y-axis shows the ratio of the weighted cost. The X-axis shows the benchmarks. Less is better. If we sum up the depth of all the 158 circuits, then we obtain the following absolute sum of longest paths in the circuit, in ascending order: bmtS=2.2M, bmtF=2.3M, jku=2.9M, sbr=3.2M, ibm=3.7M, chw=3.8M and wpm=4.7M. See Figure 16 for the averages. The Y-axis shows the ratio of the weighted cost. The X-axis shows the benchmarks. Less is better. If we sum up the gates used in all the 158 circuits, then we obtain the following absolute number of gates, in ascending order: bmtS=4.21M, bmtF=4.31M, jku=4.72M, sbr=4.75M, chw=5.38M, ibm=5.9M and wpm=6.79M. For the corresponding averages, see Figure 16.

rates (given by the weighted costs), but also faster circuits (given by the depth). These results show that BMT is able to yield good programs even with the maximum number of children, M c , limited to 8 (out of 96 possible children), and the maximum number of mappings, M p , restricted to 1,280 (out of an exponentially large universe).

Figures 18, 19 and 20 show results for individual benchmarks, and provide absolute numbers for our entire collection of 158 benchmarks. Notice that bmtS and bmtF still outperform the other approaches to qubit allocation in terms of absolute numbers. However, the relative order between these allocators change, given that some are more or less susceptible to worst cases due to the The X-axis shows benchmarks ordered in increasing order of the time spent by bmt (shaded area). If we sum up the time, in seconds, used during the allocation of all the 158 circuits, then we obtain the following absolute numbers, in ascending order: jku=157secs, chw=198secs, sbr=275secs, wpm=549secs, bmtF=883secs, ibm=1,405secs and bmtS=4,247secs. For the averages, see Figure 16. influence of outliers. There are a few cases in which all the other algorithms can beat bmtS. even though BMT has the potential to find optimal solutions to qubit allocation, when left unbounded, we parameterize it to keep runtime practical. Once we need to prune off mappings, we use a random roulette, weighted by the cost of each mapping. This is a heuristic, so, there might be problems that do not benefit from this approach. The hypothesis behind our pruning approach is that the smaller the number of partitions in the program, the lower its overall cost will be, because there will be less points where swaps will be necessary. However, there are quantum circuits in which this hypothesis is false. In these cases, even though we are glueing together a smaller number of partitions, more swaps might be necessary between them.

RQ3: Efficiency of the Algorithm

Figure 21 shows the time that each allocator takes to map pseudo-into physical-qubits. Figure 22, in turn, compares the allocators in terms of memory usage. From these figures, plus Figure 16, we draw the following conclusions:

• Allocation Time: bmtS is the slowest algorithm. sbr, jku, chw, ibm, and wpm took 11%, 4.4%, 2.8%, 46%, and 1.1% the time needed by our algorithm, respectively. The faster version of BMT, e.g. bmtF, was the third slowest one. All the other allocators, except bmtS and ibm that took, respectively, 244% and 59% more, were faster. sbr, jku, chw, and wpm took 41%, 15%, 9.8%, and 3.8% the time needed by it, respectively; • Memory Consumption: On average, there is not much variation memory-wise: sbr and jku consumed 5.4% and 2.0% more memory, respectively, and chw, ibm, wpm and bmtF consumed, on average, 6%, 8%, 3% and 3.6% less than bmtS. As expected, bmtF consumed a bit less memory than bmtS. sbr, jku, and wpm consumed 9.3%, 5.7%, and 0.6% more; and ibm and chw consumed 4.1% and 2.4% less. Analysis of results. BMT is slower than the other allocators. On average (arithmetic mean), bmtS takes 26 seconds per benchmark, with a standard deviation of 100 secs. The other algorithms stay under 10 secs per sample. The slowest part of BMT is phase dynamic programming search. The Y-axis shows the memory (bytes) in logarithmic scale. The X-axis shows benchmarks. Benchmarks are ordered in increasing order based on the memory used by bmtS (shaded area). If we sum up the memory, in bytes, used during the allocation of all the 158 circuits, then we obtain the following absolute numbers, in ascending order: ibm=13.8GB, chw=14.1GB, bmtF=14.1GB, wpm=15.3GB, bmtS=15.7GB, jku=18.6GB and sbr=18.7GB. For the averages, see Figure 16.

Dynamic programming accounts for, on average (geometric mean), 50% of the time. The first phase comes next, with 37% of the time. In spite of its higher computational complexity, jku runs faster than bmtF and bmtS.

Unsurprisingly, wpm is the fastest algorithm, on average. This implementation uses a best-effort heuristic that is linear on the size of quantum circuits and on the number of qubits. However, once we consider absolute runtimes, wpm suffers from outliers, and takes longer than other several other algorithms to finish. For instance, wpm is faster than sbr, on average, but it takes twice its total time to run. The reason behind this apparently paradox is that the geometric mean hides these outliers (10 out of 158). The absolute time of these 10 benchmarks accounts for 95% of the total runtime of wpm, and for 77% of sbr's.

The jku implementation uses an A* tree to guide the search for a good solution to qubit allocation. Thus, it needs to store intermediate results of this quest, to make backtracking possible. In other words, by storing these intermediate nodes, jku trades time for space. Figure 22 indicates that the memory usage of wpm, sbr, Q_ibm, and both BMTs grows linearly with the number of control relations; the same cannot be inferred for jku, which contains several outliers.

We close this section summarizing the data produced to answer research questions RQ2 and RQ3. Figure 23 subsumes these results. Interestingly, once we consider average runtime and costs, we find that all the algorithms, except for ibm fit into the optimal convex hull of time vs cost. In other words, following this path wpm → chw → jku → sbr → bmtF → bmtS we consistently improve allocation cost, at the expense of runtime.

RQ4: The Influence of the Target Architecture

The experiments reported in Sections 4.1, 4.2 and 4.3 were executed in a target architecture with 20 qubits. Figure 24 (a) shows its coupling graph. In this section, we investigate how the algorithms fare when given a different coupling graph. For this experiment, we chose Albatross3 , a retired architecture with 16 qubits, whose coupling graph Figure 24 (b) outlines. In addition of having less qubits than Tokyo, Albatross is asymmetric: connections between qubits are one-way. Figure 25 compares the performance of the seven algorithms considered in this paper, using Albatross' coupling graph. We run these experiments in a commodity laptop with 8GB of RAM, instead of the dedicated server (with 32GB of RAM) used in the three previous sections. Reason was cost: scheduling experiments in the server incurs into a monetary cost and follows a constrained time table. Furthermore, a simpler machine lets us show that our algorithms are practical.

We had to remove seven benchmarks from the experiments used to produce Figure 25, because jku could not handle them given the amount of available memory. The other six algorithms have been able to compile all the 158 benchmarks. If we include the missing seven benchmarks, then the cost of circuits produced by bmtS jumps from 37.6 million up to 58.3 million.

The jku and sbr allocators tend to produce circuits with lower cost than bmtS and bmtF, in Albatross. Adding back the seven excluded benchmarks does not change this scenario: sbr still outperforms the two instances of BMT. However, bmtS and bmtF produce circuits of shorter depth, on average, than the other algorithms, being amost 25% more efficient than sbr in this criterion. By construction, BMT is prone to produce circuits of short depth, because it tries to increase the size of each partition of the circuit. Less partitions do not necessarily, lead to lower costs, but tend to reduce circuit depth. The more connected the coupling graph, the better tends to be BMT's performance with regards to sbr. To support this statement, we have compared bmtS, bmtF, wpm and sbr using random graphs produced according to the Erdös-Rényi model [START_REF] Erdös | On Random Graphs I[END_REF]. We omit jku, because some experiments could not terminate due to lack of memory. Graph generation takes a parameter p, corresponding to the probability of adding an edge. We pick up graphs that have a certain diameter, given a fixed p. Figure 26 shows the result of this comparison, in terms of cost and depth for graphs with 16, 20 and 24 vertices (qubits) and diameters of 2 (p = 0.2), 4 (p = 0.1), 6 (p = 0.1) and 8 (p = 0.05) edges. These results are congruous with the fact that BMT's quality is better on Tokyo than on Albatross (which has a sparser coupling graph), and also support the hypothesis that BMT reduces depth as connectivity grows.

• for weighted cost (left), and depth (right) for all allocators. For each allocator, there are three groups (qubit number) of four bars (diameter). Each bar provides the result of using a given allocator on a different set of graphs.

• • • • • • • • • • • • • 0.6 0.9 1.2 1.5 1.8 2 4 6 8 9 Diameter Allocator • • bmtF bmtS wpm Qubits • • • 16 20 24 • • • • • • • • • • • • • • 0.
4.5 Discussion: Qubit Allocation as a Tool Towards Quantum Supremacy

An important question that concerns the material covered in this paper is: "is the time required to compile and execute a circuit allocated with BMT on a quantum computer significantly less than the time required to solve the same problem with a digital computer?" In other words, we are interested in knowing if there exists a particular problem size at which point the overhead incurred by bounded mapping trees becomes negligible. The answer to this question is positive, as we will argue in this section. However, the current prototypes of quantum computers that we have access today do not let us show this benefit with numbers. Even obtaining the runtime of a quantum circuit in the IBM Qiskit is not trivial today, due to the infrastructure to access the quantum computer. Yet, we can estimate the time to compile a circuit with BMT and run it on a quantum computer versus the time to simulate the circuit.

The current record of simulation of a quantum program on a digital machine stays at 60 Qubits [START_REF] Dang | Optimising Matrix Product State Simulations of ShorâĂŹs Algorithm[END_REF]] -four more than the previous record, from October of 2018 [START_REF] Pednault | Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits[END_REF]]. As mentioned by Dang et al., the simulation of a 50-qubits random state might require up to 18 petabytes of classical computer memory. In both works, Dang's and Pednault's, simulation at such scale was only possible by exploring particular characteristics of the algorithm to be simulated. The consensus today is that above 50 entangled qubits, simulation of general quantum programs in classical hardware becomes an intractable problem, with prohibitively high costs. To give the reader some perspective on these numbers, Markov et al. simulate approximate sampling of a 7 × 8 qubits architecture [START_REF] Markov | Quantum Supremacy Is Both Closer and Farther than It Appears[END_REF]. At a fidelity rate of 0.5%, their cost (estimated as cloud service fees) to simulate a circuit with 1+40+14 layers of depth would be around 35 thousand dollars. A deeper circuit, e.g., with 1+48+1 layers would add one million US dollars to this baseline cost.

Execution of the same circuit on a quantum computer is likely faster. Markov et al. provide the following estimates: "When sampling outputs on a quantum computer based on superconducting qubits, reported times are around 45ns per cycle with CNOT gates along the Z axis, 25ns per cycle with only single-qubit gates [START_REF] Kelly | State preservation by repetitive error detection in a superconducting quantum circuit[END_REF]]. Readout can be as fast as 140ns [START_REF] Sank | Fast Scalable State Measurement with Superconducting Qubits[END_REF], and qubits can be initialized to a known state in a few hundred nanoseconds [START_REF] Magnard | Fast and Unconditional All-Microwave Reset of a Superconducting Qubit[END_REF]."

Similarly, the time to run qubit allocation on a quantum circuit is much lower than the time to simulate it. We have compiled circuits with up to 100 qubits in commodity hardware. As an example, an 100-qubit Quantum Fourier Transform algorithm takes up to 150 and 500 seconds to be compiled by bmtF and bmtS, respectively. Thus, even though BMT runs in exponential time (when left unbounded), parameterization ensures that its execution time remains practical. Furthermore, due to material constraints like cooling to cryogenic temperature, we expect quantum computer time to remain much more expensive than classical computer time in the near future. So it is still a reasonable tradeoff to spend several seconds on commodity hardware to save milliseconds on a very expensive equipment. Finally, the benefit of reducing gate count or circuit depth -something that qubit allocation accomplishes-is not just a shorter execution time, but much more importantly, a lowered exposure to noise and decoherence, which leads to better accuracy of quantum programs.

RELATED WORK

Qubit allocation is a relatively recent issue. In 2004 Svore et al. mentioned the need to insert movement instructions, e.g., swaps, as a step in a general design flow to map a program representing a quantum computing algorithm into a technology-specific hardware. That early report did not provide an algorithm for solving qubit allocation, although the authors have addressed this challenge later [START_REF] Häner | A Software Methodology for Compiling Quantum Programs[END_REF][START_REF] Svore | A Layered Software Architecture for Quantum Computing Design Tools[END_REF]]. We believe that the first formal treatment of the problem, with definitions, complexity analyses and heuristics, was proposed by [START_REF] Maslov | Quantum Circuit Placement[END_REF] Earlier works would either solve qubit allocation manually, or present allocators only for specific quantum algorithms [START_REF] Blais | Quantum network optimization[END_REF][START_REF] Copsey | The Effect of Communication Costs in Solid-state Quantum Computing Architectures[END_REF][START_REF] Oskin | A practical architecture for reliable quantum computers[END_REF][START_REF] Saito | Actual computational time-cost of the Quantum Fourier Transform in a quantum computer using nuclear spins[END_REF]. Qubit allocation has several variations, all of which are NP-complete [START_REF] Yukio Siraichi | Qubit Allocation[END_REF]. Such diversity has led to an equally varied number of solutions. Our compiler, Enfield, implements the algorithms that we were aware of, and whose source code we could easily find, or whose authors were kind enough to help us. Some algorithms we decided not to implement, for the following reasons:

• Restricted design: some heuristics target specific quantum architectures. Architectures are determined by the shape of the coupling graphs; e.g.: 2D grids and lines [START_REF] Lin | PAQCS: Physical Design-Aware Fault-Tolerant Quantum Circuit Synthesis[END_REF][START_REF] Lin | Layout Synthesis for Topological Quantum Circuits With 1-D and 2-D Architectures[END_REF][START_REF] Pedram | Layout Optimization for Quantum Circuits with Linear Nearest Neighbor Architectures[END_REF][START_REF] Shafaei | Qubit placement to minimize communication overhead in 2D quantum architectures[END_REF][START_REF] Shrivastwa | Fast Qubit Placement in 2D Architecture Using Nearest Neighbor Realization[END_REF]]. • Runtime complexity: several heuristics suffer from a worst case exponential execution time. Contrary to our design, this runtime penalty is mandatory, i.e., it cannot be bounded via parameters [START_REF] Itoko | Quantum Circuit Compilers Using Gate Commutation Rules[END_REF][START_REF] Lao | Mapping of Lattice Surgery-based Quantum Circuits on Surface Code Architectures[END_REF][START_REF] Lin | Layout Synthesis for Topological Quantum Circuits With 1-D and 2-D Architectures[END_REF][START_REF] Maslov | Quantum Circuit Placement[END_REF][START_REF] Shafaei | Qubit placement to minimize communication overhead in 2D quantum architectures[END_REF][START_REF] Zulehner | Efficient mapping of quantum circuits to the IBM QX architectures[END_REF]]. • Swaps only: most of the solutions to qubit allocation rely on swaps as the transformation available to fit logical circuit into physical coupling graphs [START_REF] Lao | Mapping of Lattice Surgery-based Quantum Circuits on Surface Code Architectures[END_REF][START_REF] Li | Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices[END_REF][START_REF] Lin | PAQCS: Physical Design-Aware Fault-Tolerant Quantum Circuit Synthesis[END_REF][START_REF] Maslov | Quantum Circuit Placement[END_REF][START_REF] Pedram | Layout Optimization for Quantum Circuits with Linear Nearest Neighbor Architectures[END_REF][START_REF] Shafaei | Qubit placement to minimize communication overhead in 2D quantum architectures[END_REF]; hence, reversals are not considered. Token Swapping and Subgraph Isomorphism. Token swapping was formalized and proven NP-complete recently [START_REF] Yamanaka | Swapping Labeled Tokens on Graphs[END_REF]. Since then, this problem has been extensively studied [START_REF] Bonnet | Complexity of Token Swapping and its Variants[END_REF][START_REF] Kawahara | The Time Complexity of the Token Swapping Problem and Its Parallel Variants[END_REF][START_REF] Miltzow | Approximation and Hardness of Token Swapping[END_REF][START_REF] Yamanaka | Sequentially Swapping Colored Tokens on Graphs[END_REF][START_REF] Yamanaka | Swapping Labeled Tokens on Graphs[END_REF]. We know two concrete implementations of algorithms that solve token swapping exactly [START_REF] Miltzow | Approximation and Hardness of Token Swapping[END_REF][START_REF] Yukio Siraichi | Qubit Allocation[END_REF]]. These algorithms have exponential runtime. In this paper, to solve token swapping, we implement the 4-approximative algorithm from [START_REF] Miltzow | Approximation and Hardness of Token Swapping[END_REF], which runs in polynomial time. In contrast, subgraph isomorphism is an old problem. There are several heuristics and exact algorithms to solve it [START_REF] Cordella | A (sub)graph isomorphism algorithm for matching large graphs[END_REF][START_REF] Han | Turboiso: Towards Ultrafast and Robust Subgraph Isomorphism Search in Large Graph Databases[END_REF][START_REF] Zhao | On Graph Query Optimization in Large Networks[END_REF]. We use a best-effort approach. Thus, the search discussed in Section 3.1 might not find a solution, even though a solution might exist.

CONCLUSION

This paper has introduced a new model for Qubit Allocation, based on subgraph isomorphism and token swapping. We believe that these two problems provide a new principled approach to solve Qubit Allocation, in a way similar to what graph coloring has done to classic register allocation. And, just like there exist many solutions to register allocation based on graph coloring, several solutions to qubit allocation based on this combination of subgraph isomorphism and token swapping are possible. In this paper we have explored one among such possibilities. Our algorithm outperforms several state-of-the-art solutions to this problem along three different dimensions: weighted cost; depth; and number of gates, in a quantum architecture with 20 qubits. When we consider these metrics, our algorithm delivers better results than previous work, both in terms of averages and in terms of absolute numbers, at the expense of a longer runtime. The design and implementation of other solutions to Qubit Allocation, also based on the Isomorphism-Swapping combination, is an interesting research direction that we hope to explore in the future.

ACKNOWLEDGEMENT

This project was funded by grants from FAPEMIG (Grant APQ-03832-14 "Cooperation FAPs-INRIA-CNRS"), CNPq (Grant 406377/2018-9) and CAPES. We thank the referees for the time and expertise they have put into reviewing our work. Their suggestions have greatly improved our paper.

Fig. 1 .

 1 Fig. 1. Typical representation of a quantum program.

Fig. 2 .

 2 Fig. 2. (a) Reversal. (c) Swap.

Fig. 3 .

 3 Fig. 3. (a) the coupling graph; (b) the input quantum circuit; (c) the allocated quantum circuit (output) with two uses of the reversal transformation (highlighted).

Fig. 4 .

 4 Fig. 4. (a) two undirected graphs G and H (left to right); (b) all possible subgraphs of G isomorphic to H .

Fig. 5 .Fig. 6 .

 56 Fig. 5. (a) undirected graph of Figure 4 (a) with the labels of the vertices (f v ) outside the circle, the labels of the tokens (f t ) inside the circle. Grey boxes indicate vertices whose labels do not match tokens; (b) a sequence of swaps that solves the problem (highlighted edges).

Fig. 7 .

 7 Fig. 7. Summary of notation used in this paper.

  q

Fig. 11 .

 11 Fig. 11. Output from first phase F with some possible combinations represented by different paths. Each path in this figure represents one different solution. The path representing the optimal solution is highlighted.

  . The estimation of the swap cost takes O (|Q |), while the cost for ensuring live qubits remain mapped is O (|Q |(|Q | + E (G u q ))), since we execute, in the worst case, one BFS for each qubit. Hence, the time complexity of this phase is O ((M p ) 2 |Ψ||Q |(|Q | + E(G u q ))). The space complexity is O (M p |Ψ||Q |): each subproblem is O (|Q |), and we have O (M p |Ψ|) of them.

Fig. 14 .

 14 Fig.14. Mappings f and swapping sequences ∆ (highlighted) give us all the information that is necessary to transform a virtual quantum circuit into a physical quantum circuit.

Fig. 15 .

 15 Fig. 15. (a) from left to right, we have the whole input program segmented into partitions (dashed box), and their mappings; (b) the swap operations (grey boxes) necessary to transform one mapping into another.

Fig. 16 .

 16 Fig. 16. Summary of the comparison between bmtS and other algorithms. Allocator: algorithm that we compare with bmtS. Dim: dimensions of efficiency and quality. G. Mean: geometric mean of ratios, taking bmtS as baseline. G. Std. D.: the geometric standard deviation of the ratios. The closer to 1, the smaller the spread of the data. B.[etter] (W.[orse] Count: the number of benchmarks where the algorithm was better (worse) than bmtS. We use a hyphen ("-") to mark cases where no benchmark exists. B.[etter] (W.[orse]) G. Mean: the geometric mean of the ratios of the benchmarks where the algorithm was better (worse) than bmtS. This column answers the following question: "what would be the G. Mean for this allocator, considering only the benchmarks where it performed better (worse) than bmtS?" Except for Better Count (B. Count), the higher the reported value, the better for bmtS.

  76-(1.17) -1.55-(1.15) -1.41-(1.12) -1.29-(1.11) -1.28-(1.11) -1.29-(1.11) -1.28-(1.11) -1.28-(1.11) -1.28-(1.11) depth -1.43-(1.10) -1.3-(1.09) -1.22-(1.07) -1.15-(1.06) -1.15-(1.06) -1.15-(1.06) -1.15-(1.06) -1.15-(1.06) -1.15-(1.06) gates -1.49-(1.11) -1.35-(1.10) -1.27-(1.08) -1.2-(1.07) -1.19-(1.07) -1.19-(1.07) -1.18-(1.07) -1.19-(1.07) -1.19-(1.07) time -0.05-(1.09) -0.05-(1.09) -0.06-(1.10) -0.08-(1.12) -0.08-(1.12) -0.08-(1.12) -0.08-(1.11) -0.08-(1.14) -0.08-(1.12) mem -0.90-(1.10) -0.89-(1.10) -0.91-(1.10) -0.87-(1.09) -0.86-(1.09) -0.88-(1.10) -0.88-(1.10) -0.86-(1.09) -0.85-(1.09)ptt -1.82-(1.34) -1.53-(1.27) -1.34-(1.21) -1.22-(1.17) -1.21-(1.16) -1.21-(1.16) -1.21-(1.16) -1.21-(1.16) -1.21-(1.16) cost -1.49-(1.11) -1.31-(1.08) -1.21-(1.06) -1.13-(1.04) -1.08-(1.03) -1.06-(1.03) -1.06-(1.03) -1.06-(1.03) -1.05-(1.03) depth -1.27-(1.07) -1.17-(1.05) -1.11-(1.04) -1.07-(1.03) -1.04-(1.02) -1.03-(1.02) -1.03-(1.02) -1.03-(1.02) -1.03-(1.02) gates -1.32-(1.07) -1.21-(1.05) -1.14-(1.04) -1.09-(1.03) -1.06-(1.02) -1.05-(1.02) -1.04-(1.02) -1.04-(1.02) -1.04-(1.02) time -0.05-(1.09) -0.05-(1.09) -0.06-(1.10) -0.08-(1.12) -0.12-(1.15) -0.13-(1.16) -0.13-(1.14) -0.13-(1.15) -0.13-(1.15) mem -0.86-(1.09) -0.86-(1.09) -0.88-(1.10) -0.85-(1.09) -0.84-(1.09) -0.87-(1.10) -0.87-(1.09) -0.85-(1.09) -0.84-(1.08) ptt -1.38-(1.16) -1.19-(1.10) -1.10-(1.06) -1.05-(1.04) -1.02-(1.02) -1.01-(1.02) -1.01-(1.02) -1.01-(1.02) -1.01-(1.02) cost -1.44-(1.09) -1.27-(1.07) -1.18-(1.05) -1.11-(1.04) -1.06-(1.03) -1.03-(1.02) -1.02-(1.01) -1.01-(1.01) -1.00-(1.01) depth -1.24-(1.06) -1.15-(1.04) -1.10-(1.03) -1.06-(1.03) -1.04-(1.02) -1.02-(1.01) -1.01-(1.01) -1.01-(1.02) -1.00-(1.02) gates -1.29-(1.06) -1.18-(1.05) -1.12-(1.03) -1.08-(1.03) -1.05-(1.02) -1.03-(1.01) -1.02-(1.01) -1.01-(1.01) -1.00-(1.01) time -0.05-(1.09) -0.06-(1.09) -0.06-(1.10) -0.09-(1.13) -0.13-(1.15) -0.21-(1.18) -0.31-(1.20) -0.45-(1.16) -0.67-(1.25) mem -0.86-(1.09) -0.86-(1.09) -0.88-(1.09) -0.85-(1.09) -0.84-(1.09) -0.87-(1.10) -0.89-(1.09) -0.88-(1.09) -0.90-(1.08) ptt -1.32-(1.14) -1.16-(1.08) -1.08-(1.05) -1.03-(1.03) -1.01-(1.02) -1.00-(1.01) -1.00-(1.01) -1.00-(1.01) -1.00-(1.01) cost -1.43-(1.09) -1.27-(1.06) -1.18-(1.05) -1.11-(1.04) -1.06-(1.03) -1.04-(1.02) -1.02-(1.01) -1.01-(1.01) -1.00-(1.00) depth -1.23-(1.05) -1.15-(1.04) -1.09-(1.03) -1.06-(1.02) -1.04-(1.02) -1.02-(1.01) -1.01-(1.01) -1.01-(1.01) -1.00-(1.01) gates -1.28-(1.06) -1.18-(1.04) -1.12-(1.03) -1.08-(1.03) -1.05-(1.02) -1.03-(1.01) -1.02-(1.01) -1.01-(1.01) -1.00-(1.01) time -0.05-(1.09) -0.06-(1.10) -0.07-(1.10) -0.10-(1.16) -0.13-(1.15) -0.22-(1.19) -0.34-(1.20) -0.54-(1.18) -0.81-(1.15) mem -0.85-(1.09) -0.85-(1.09) -0.88-(1.10) -0.85-(1.09) -0.84-(1.09) -0.87-(1.10) -0.89-(1.09) -0.89-(1.08) -0.92-(1.07

Fig. 17 .

 17 Fig. 17. Exploration of the space of parameters. Rows group results by the maximum number of children (M c ), and columns group results by maximum number of partial solutions (M p ). Row ptt denotes the number of partitions in which we split the quantum circuit, given a certain set of parameters.

  Fig.18. (Cost) Ratio of the cost of circuits produced by the different allocators using the cost of the circuit produced by bmtS as the baseline. The Y-axis shows the ratio of the weighted cost. The X-axis shows the benchmarks -each tick represents a different quantum circuit. Less is better. If we sum up the costs of all the 158 circuits, then we obtain the following absolute numbers, in ascending order: bmtS=24.5M, bmtF=25.3M, jku=29.6M, sbr=30.3M, chw=36.8M, ibm=40.3M and wpm=50.0M. Figure16reports averages.

  Fig. 19. (Depth) Ratio of the depth of circuits produced by the different allocators, using bmtS as the baseline.The Y-axis shows the ratio of the weighted cost. The X-axis shows the benchmarks. Less is better. If we sum up the depth of all the 158 circuits, then we obtain the following absolute sum of longest paths in the circuit, in ascending order: bmtS=2.2M, bmtF=2.3M, jku=2.9M, sbr=3.2M, ibm=3.7M, chw=3.8M and wpm=4.7M. See Figure16for the averages.

  Fig. 20. (Gates) Ratio of the number of gates in the circuits produced by the different allocators by the cost of the circuit produced by bmtS. The Y-axis shows the ratio of the weighted cost. The X-axis shows the benchmarks. Less is better. If we sum up the gates used in all the 158 circuits, then we obtain the following absolute number of gates, in ascending order: bmtS=4.21M, bmtF=4.31M, jku=4.72M, sbr=4.75M, chw=5.38M, ibm=5.9M and wpm=6.79M. For the corresponding averages, see Figure16.

  Fig. 21. (Time) Time spent by different allocators. The Y-axis shows time (seconds) in logarithmic scale.The X-axis shows benchmarks ordered in increasing order of the time spent by bmt (shaded area). If we sum up the time, in seconds, used during the allocation of all the 158 circuits, then we obtain the following absolute numbers, in ascending order: jku=157secs, chw=198secs, sbr=275secs, wpm=549secs, bmtF=883secs, ibm=1,405secs and bmtS=4,247secs. For the averages, see Figure16.

  Fig. 22. (Memory) Memory used by different allocators.The Y-axis shows the memory (bytes) in logarithmic scale. The X-axis shows benchmarks. Benchmarks are ordered in increasing order based on the memory used by bmtS (shaded area). If we sum up the memory, in bytes, used during the allocation of all the 158 circuits, then we obtain the following absolute numbers, in ascending order: ibm=13.8GB, chw=14.1GB, bmtF=14.1GB, wpm=15.3GB, bmtS=15.7GB, jku=18.6GB and sbr=18.7GB. For the averages, see Figure16.

Fig. 23 .

 23 Fig. 23. Runtime vs Weighted Allocation Cost for all the algorithms compared in this evaluation. Allocation cost is measured as the sum of all the weighted costs of gates used to compose the quantum circuit after qubit allocation (result is given in millions).

Fig. 24 .

 24 Fig. 24. Coupling graphs for: (a) ibmqx20 "Tokyo", with 20 qubits. (b) ibmqx3 "Albatross", with 16 qubits.

  weighted partial mapper (WPM); Zulehner et al. [2018] A* search; Li et al. [2018] SWAP-based BidiREctional heuristic (SABRE); and Zulehner and Wille

  Fig. 25. Comparison between different qubit allocators in the Albatross architecture. We had to remove seven benchmarks from our collection of 158 circuits to perform this experiment, because jku requires more than 8GB of memory to compile them.

	Qubit Allocation as a Combination of Subgraph Isomorphism and Token Swapping				120:25
	Average time (wrt bmtS)	0 0.2 0.4 0.6 0.8 1	bmtS (1.00, 1.00) bmtF(1.01, 0.64) sbr(0.98, 0.10) jku(0.96, 0.03)	chw(1.21, 0.02) ibm(1.27, 0.26) wpm(1.56, 0.01)	Average number of gates (wrt bmtS)	0.9 1 1.1 1.2 1.3 1.4 1.5 1.6	bmtS (1.00, 1.00) bmtF(1.01, 1.01) sbr(1.24, 1.13) jku(1.04, 0.96) chw(1.43, 1.34) ibm(1.45, 1.49) wpm(1.69, 1.50)
		0.9	1	1.1	1.2	1.3	1.4	1.5	1.6		1	1.1	1.2	1.3	1.4	1.5	1.6	1.7
					Average cost (wrt bmtS)							Average depth (wrt bmtS)

  The first row shows the results w.r.t. sbr. The black points in the highlighted areas locate the Tokyo and Albatross architectures. The second row shows the absolute results (in millions)

	cost	Allocator • • bmtF	bmtS	wpm	Qubits •	16	•	20	•	24		depth
	1.75
	1.50
	1.25			Tokyo					Albatross				Tokyo							Albatross
	1.00
	75
	50.00 75.00 cost 83.3	2 68.4 bmtF	69.09	4 82.26	6 Diameter 51.87 68.16 Diameter 67.53 2 4 bmtS	47.8 sbr 6 8	8 48.72		91.72		9 87.58 wpm	76.05	9.15 depth 6.00 9.00	7.26 bmtF	8.1	9.08	7.19 Diameter bmtS	8.03	2	8.02 4	7.31 sbr 6	8	7.58	11.42	10.86 wpm	9.83
	25.00													3.00
	0.00													0.00
	Q16 Q20 Q24 Q16 Q20 Q24 Q16 Q20 Q24 Q16 Q20 Q24	Q16 Q20 Q24 Q16 Q20 Q24 Q16 Q20 Q24 Q16 Q20 Q24
	Fig. 26. Comparison of different qubit allocators in randomly produced graphs with 16, 20 and 24 qubits, and
	diameters of 2, 4, 6 and 8 nodes.

Proc. ACM Program. Lang., Vol. 3, No. OOPSLA, Article 120. Publication date: October 2019.

We shall call Zulehner et al.'s first algorithm JKU because it was designed and tested at Johannes Kepler Universität Linz. Proc. ACM Program. Lang., Vol.

3, No. OOPSLA, Article 120. Publication date: October 2019.

Choosing a smaller architecture is not possible, because several of our benchmarks use at least 16 qubits. Proc. ACM Program. Lang., Vol. 3, No. OOPSLA, Article 120. Publication date: October 2019.

Markov et al. explicitly denote layers of Hadamard gates with "1+" at the beginning of the circuit, and "+1" at the end. The other layers include other one-qubit gates and controlling CNOT gates. Proc. ACM Program. Lang., Vol. 3, No. OOPSLA, Article 120. Publication date: October 2019.