# On the Qubit Routing Problem

Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will

Simmons, Seyon Sivarajah

► To cite this version:

Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, et al.. On the Qubit Routing Problem. 14 th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), Jun 2019, Maryland, United States. 10.4230/LIPIcs.TQC.2019.5 . hal-05015883

HAL Id: hal-05015883

https://hal.science/hal-05015883v1

Submitted on 1 Apr 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques 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.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the Qubit Routing Problem

## Alexander Cowtan

Cambridge Quantum Computing Ltd, 9a Bridge Street, Cambridge, CB2 1UB, United Kingdom

## Silas Dilkes

Cambridge Quantum Computing Ltd, 9a Bridge Street, Cambridge, CB2 1UB, United Kingdom

## Ross Duncan

Cambridge Quantum Computing Ltd, 9a Bridge Street, Cambridge, CB2 1UB, United Kingdom
University of Strathclyde, 26 Richmond Street, Glasgow, G1 1XH, United Kingdom
ross.duncan@cambridgequantum.com

## Alexandre Krajenbrink

Cambridge Quantum Computing Ltd, 9a Bridge Street, Cambridge, CB2 1UB, United Kingdom
Laboratoire de Physique de l'École Normale Supérieure, PSL University, CNRS, Sorbonne Universités, 24 rue Lhomond, 75231 Paris Cedex 05, France

## Will Simmons

Cambridge Quantum Computing Ltd, 9a Bridge Street, Cambridge, CB2 1UB, United Kingdom

## Seyon Sivarajah

Cambridge Quantum Computing Ltd, 9a Bridge Street, Cambridge, CB2 1UB, United Kingdom

## Abstract

We introduce a new architecture-agnostic methodology for mapping abstract quantum circuits to realistic quantum computing devices with restricted qubit connectivity, as implemented by Cambridge Quantum Computing's t|ket〉 compiler. We present empirical results showing the effectiveness of this method in terms of reducing two-qubit gate depth and two-qubit gate count, compared to other implementations.

**2012 ACM Subject Classification** Theory of computation → Quantum computation theory; Computer systems organization → Quantum computing; Hardware → Quantum computation; Software and its engineering → Compilers; Software and its engineering → Retargetable compilers

**Keywords and phrases** Quantum Computing, Qubit routing, Compilation

**Digital Object Identifier** 10.4230/LIPIcs.TQC.2019.5

**Related Version** A full version of the paper is available at https://arxiv.org/abs/1902.08091.

**Acknowledgements** We thank Steven Herbert for many helpful conversations and encouragement.

# 1 Introduction

There is a significant gap between the theoretical literature on quantum algorithms and the way that quantum computers are implemented. The simple and popular *quantum circuit model* presents the quantum computer as a finite number of qubits upon which quantum gates act; see Fig. 1 for an example. Typically gates act on one or two-qubits at a time, and the circuit model allows multi-qubit gates to act on any qubits without restriction. However, in realistic hardware the qubits are typically laid out in a fixed two or three dimensional topology where gates may only be applied between neighbouring qubits. In order for a circuit to be executed on such hardware, it must be modified to ensure that whenever two-qubits are required to interact, they are adjacent in memory. This is a serious departure from the von Neumann architecture of classical computers, where operations may involve data at distant locations in memory without penalty.

<figure><img src="image_2.png" /></figure>

© Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah;

licensed under Creative Commons License CC-BY

14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019).

Editors: Wim van Dam and Laura Mančinska; Article No. 5; pp. 5:1–5:32

<figure><img src="image_3.png" /></figure>

Leibniz International Proceedings in Informatics
LIPICS Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
## 5:2 On the Qubit Routing Problem

We refer to the task of modifying a circuit to conform to the memory layout of a specific quantum computer as the *qubit routing problem*. When non-adjacent qubits are required to interact we can insert additional SWAP gates to exchange a qubit with a neighbour, moving it closer to its desired partner. In general many – or even all – of the qubits may need to be swapped, making this problem non-trivial. Since quantum algorithms are usually designed without reference to the connectivity constraints of any particular hardware, a solution to the routing problem is required before a quantum circuit can be executed. Therefore qubit routing forms a necessary stage of any compiler for quantum software. Current quantum computers – the so-called NISQ<fnref n="1" /> devices – impose additional constraints. Their short coherence times and relatively low fidelity gates require that the circuit depth and the total number of gates are both as low as possible. As routing generally introduces extra gates into a circuit, increasing its size and depth, it is crucial that the circuit does not grow too much, or its performance will be compromised.

The general case of the routing problem, also called the qubit allocation problem, is known to be infeasible. The sub-problem of assigning logical qubits to physical ones is equivalent to sub-graph isomorphism [14], while determining the optimal swaps between assignments is equivalent to token-swapping [19] which is at least NP-hard [3] and possibly PSPACE-complete [10]. Siraichi et al. [14] propose an exact dynamic programming method (with complexity exponential in the number of qubits) and a heuristic method which approximates it well, at least on the small (5 qubit) circuits considered. Zulehner et al. [20] propose an algorithm based on depth partitioning and A* search which is specialised to the architectures of IBM devices [1]. Other approaches take advantage of the restricted topology typically found in quantum memories such as linear nearest neighbour [7] or hypercubic [4] which rely on classical sorting networks; see Appendix A for a discussion of this approach. Lower bound results for routing are presented by Herbert [5].

In this paper we describe the solution to the routing problem implemented in $t|ket⟩$, a platform-independent compiler developed by Cambridge Quantum Computing Ltd<fnref n="2" />. The heuristic method in $t|ket⟩$ matches or beats the results of other circuit mapping systems in terms of depth and total gate count of the compiled circuit, and has much reduced run time allowing larger circuits to be routed.

Aside from qubit routing, $t|ket⟩$ also provides translation from general circuits to any particular hardware-supported gate set, a variety of advanced circuit optimisation routines, and support for most of the major quantum software frameworks. These will be described in future papers. Compilation through $t|ket⟩$ guarantees hardware compatibility and minimises the depth and gate count of the final circuit across a range of hardware and software platforms.

In Section 2 we formalise the problem and present an example instance. In Section 3 we describe the method used by $t|ket⟩$ to solve the problem. In Section 4 we describe some of the architectures on which we tested the algorithm and in Section 5 we present empirical results of $t|ket⟩$'s performance, both in terms of scaling and in comparison to other compiler software. Full tables of results are provided in the Appendix.

## 2 The Routing Problem

We represent a quantum computer as a graph where nodes are physical qubits and edges are the allowed two-qubit interactions<fnref n="3" />. Since the circuit model assumes we can realise a two-qubit gate between any pair of qubits, it is equivalent to the complete graph (Fig. 2a).

<footnote n="1">¹ “Noisy intermediate-scale quantum” devices; see [13] for a survey.</footnote>

<footnote n="2">² $t|ket⟩$ is available as a python module from https://pypi.org/project/pytket/.</footnote>

<footnote n="3">³ We don't consider architectures with multi-qubit interactions involving more than two-qubits.</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 1 Example of a quantum circuit containing one and two-qubit gates acting on four qubits, $q1$, $q2$, $q3$ and $q4$. This circuit has five timesteps, each with gates acting on disjoint sets of qubits.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 2 Nodes in the graph represent physical qubits and edges are the allowed interactions. (a) The circuit model assumes all-to-all communication between qubits, i.e. a complete graph and (b) a physically realistic one-dimensional nearest neighbour cyclic graph, the ring.</figcaption></figure>

Realistic qubit architectures are connectivity limited: for instance, in most superconducting platforms the qubit interaction graph must be planar; ion traps present more flexibility, but are still not fully connected. For now we will use the ring graph (Fig. 2b) as a simple example. Given such a restricted graph, our goal is to emulate the complete graph with minimal additional cost.

From this point of view, the routing problem can be stated as follows. Given (i) an arbitrary quantum circuit and (ii) a connected graph specifying the allowed qubit interactions, we must produce a new quantum circuit which is equivalent to the input circuit, but uses only those interactions permitted by the specification graph. Provided the device has at least as many qubits as the input circuit then a solution always exists; our objective is to minimise the size of the output circuit.

## 2.1 Example: Routing on a Ring

Let's consider the problem of routing the circuit shown in Fig. 1 on the ring graph of Fig. 2(b). The first step is to divide the circuit into *timesteps*, also called *slices*. Loosely speaking, a timestep consists of a subcircuit where the gates act on disjoint sets of qubits and could in principle all be performed simultaneously (see Section 3.1 for a precise definition). The single qubit gates have no bearing on the routing problem so can be ignored, and thus a timestep can be reduced to a set of qubit pairs that are required to interact via some two-qubit gate.

Next, the logical qubits of the circuit must be mapped to the nodes of the graph. For our example a reasonable initial mapping is $q1 \to 1$, $q3 \to 2$, $q2 \to 3$, $q4 \to 4$ as shown in Fig. 3. This has the advantage that the qubits which interact in the first timestep are adjacent in the graph, and the same for the second timestep.
5:4 On the Qubit Routing Problem

<figure><img src="image_6.png" /><figcaption>■ **Figure 3** An initial mapping of logical qubits to nodes. Highlighted nodes are labelled with the mapped qubit.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>■ **Figure 4** (a) Qubit mapping to nodes if $q1$ and $q3$ swap positions. (b) Qubit mapping to nodes if $q2$ and $q3$ swap positions.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>■ **Figure 5** Quantum circuit in Fig. 1 mapped to architecture graph of Fig. 2b.</figcaption></figure>

However at the third timestep our luck has run out: the CNOT gate between $q1$ and $q2$ is not possible in the current configuration. We must add SWAP gates to exchange logical qubits to enable the desired two-qubit interactions. In the example there are two candidates: swapping nodes 1 and 3, or swapping nodes 2 and 3, yielding the configurations shown in Fig. 4. Looking ahead to the final slice – slice 4 has no two-qubit gates so can be ignored – we see that $q3$ and $q4$ will need to interact. In configuration (a) these qubits are distance 3 apart, and hence two additional swaps will be needed to bring them together. In configuration (b) however they are already adjacent. As we want to minimise the number of additional elements to our circuit we choose to swap nodes 2 and 3 to yield the final circuit shown in Fig. 5.

While this was a tiny example we can see in microcosm all the key elements of the problem: the need to find a mapping of qubits to nodes; the notion of distance between qubits at the next timestep; and the need to compute the permutation of the nodes to enable the next timestep. It should be clear even from this small example that as the size of the circuit increases the number of candidate swaps increases dramatically. Further, if we have
to swap several pairs of qubits at the same time, improving the situation for one pair may worsen the situation for another pair. There is a clear arbitrage to apply to bring all the pairs together as soon as possible.

In the worst case $O(n^2)$ swaps suffice to get from any $n$-node configuration to any other [19], although for sufficiently regular graphs much better is possible [4]. A recent lower bound result states that the minimum number of swaps is $O(\log n)$ in the worst case [5], which is achieved by the cyclic butterfly network [4].

Our goal is to optimise the circuit globally so finding optimal mappings between timesteps is not sufficient. It is necessary to evaluate candidate mappings across multiple timesteps; this is the core of the t|ket routing algorithm.

## 2.2 SWAP Synthesis and Routing

In the preceding section we described the routing problem in terms of inserting SWAP gates into the circuit. However not all device technologies offer SWAP as a primitive operation. Superconducting devices, for example, typically offer a single two-qubit interaction from which all other gates, including the SWAP, must be constructed. As a further complication, these interactions may be asymmetric. For example, in some IBM devices [1], the two-qubit interaction is a CNOT where one qubit is always the control and the other always the target. The graph representing the machine is therefore directed, as shown in Fig. 6, where the direction indicates the orientation of the gate.

<figure><img src="image_9.png" /><figcaption>Figure 6 Architecture with one-way connectivity constraint.</figcaption></figure>

This complication is easily removed by the usual trick of inserting Hadamard gates, as in Fig. 7. Hence the swap gate can be implemented by three (unidirectional) CNOTS and four Hadamards, as in Fig. 8.

<figure><img src="image_10.png" /><figcaption>Figure 7 Inverting a CNOT gate for a directed graph.</figcaption></figure>

Consider running our routed quantum circuit on the directed architecture of Fig. 6. As this graph constrains the direction of interactions, the quantum circuit we produced is no longer valid. We account for this using the inversion in Fig. 7, producing the circuit shown in Fig. 9. Many simplifications are possible on the resulting circuit, but care must be taken to ensure that the simplified circuit is still conformant to the architecture digraph.
5:6 On the Qubit Routing Problem

<figure><img src="image_11.png" /><figcaption>Figure 8 Representation of a SWAP gate in terms of three consecutive CNOT and its inverted representation for a directed graph.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 9 Quantum circuit in Fig. 1 routed for architecture graph in Fig. 6.</figcaption></figure>

3 The t|ket〉 Routing Procedure

The routing algorithm implemented in t|ket〉 guarantees compilation of any quantum circuit to
any architecture, represented as simple connected graph. It is therefore completely hardware
agnostic. The algorithm proceeds in four stages: decomposing the input circuit into timesteps;
determining an initial placement; routing across timesteps; and a final clean-up phase.

**3.1 Slicing the Circuit Into Timesteps**

Before routing we partition the quantum circuit into timesteps. The circuit structure provides a natural partial ordering of the gates; thus a greedy algorithm starting from inputs can divide the input circuit into “vertical” partitions of gates which can be executed simultaneously. We simply traverse the circuit adding the qubits involved in a two-qubit gate to the current timestep. Since only multi-qubit interactions (such as CNOT or CZ gates) constrain the problem, single-qubit gates can be ignored<fnref n="4" />. If a gate requires a qubit already used in the previous timestep, a new timestep is created. This procedure is repeated until all gates are assigned to a timestep. A timestep thus consists of a set of disjoint pairs of (logical) qubits which represent gates scheduled for simultaneous execution.

Applying this method to the example from Fig. 1 would yield the following timesteps.

$$
1 \mapsto \{(q1, q3), (q2, q4)\}
$$

$$
2 \mapsto \{(q2, q3)\}
$$

$$
3 \mapsto \{(q1, q2), (q3, q4)\}
$$

$$
4 \mapsto \{(q1, q2)\}
$$

Note, that this is not the same as the illustrative slicing shown in Fig. 1!

The *density* of a timestep is a measure of the number of simultaneous gates executed.
For an *n*-qubit architecture with single and two-qubit gates, the *density* is

$$
d = \frac{\text{\#two-qubit gates}}{\lfloor \frac{n}{2} \rfloor}.
$$

<footnote n="4">⁴ More accurately: while the single-qubit gates can be ignored for the purposes of routing, they must be retained for circuit generation; for clarity we ignore them for now.</footnote>
Note that $d = 1$ where every qubit is involved in a two-qubit gate in this timestep; a timestep is sparse when its density is close to zero. In principle, the density could be constrained to make routing easier. In practice this seems to make little difference, and we use this quantity only for the analysis in Section 5.1.

## 3.2 Initial Mapping

For the routing algorithm to proceed we require an initial mapping of logical qubits (referred to as qubits) and physical qubits (referred to as nodes). In $t|ket$ a simple but surprisingly effective procedure is used.

We iterate over the timesteps to construct a graph whose vertices are qubits. At timestep $n$ we add the edge $(q, q')$ to the graph if $(i)$ this pair is present in the timestep and $(ii)$ both qubits $q$ and $q'$ have degree less than 2 in the current graph. Each connected component of the resulting graph is necessarily either a line or a ring; the rings are broken by removing an arbitrarily chosen edge.

Disconnected qubits in this graph correspond either to qubits which never interact at all, or to those whose first interaction is with a qubit whose first two interactions are with others. These disconnected qubits are not included in the initial placement at all; they are added later in the routing procedure.

We then select a subgraph of the architecture with high average degree and low diameter to start from. If the architecture is Hamiltonian connected – all the common architectures are<fnref n="5" /> – then it is possible to map the qubit graph to the architecture as one long line starting from a high degree vertex within this subgraph, and greedily choosing the highest degree available neighbour. This ensures that most of the gates in the first two timesteps can be applied without any swaps; the only exceptions are those gates corresponding to the edges removed when breaking rings.

If the initial mapping cannot be completed as one long line, then the line is split and mapped as several line segments.

## 3.3 Routing

The routing algorithm iteratively constructs a new circuit which conforms to the desired architecture, taking the sliced circuit and the current mapping of qubits to nodes as input.

The algorithm compares the current timestep of the input circuit to the current qubit mapping. If a gate in the current timestep requires a qubit which has not yet been mapped, it is allocated to the nearest available node to its partner. All gates which can be performed in the current mapping – all single-qubit gates and those two-qubit gates whose operands are adjacent – are immediately removed from the timestep and added to the output circuit. If this exhausts the current timestep, we advance to the next; otherwise SWAPs must be added.

We define a distance vector $d(s, m)$ which approximates the number of SWAPs needed to make timestep $s$ executable in the mapping $m$; these vectors are ordered pointwise. Let $s_0$ denote the current timestep, $s_1$ for its successor, and so on, and write $\sigma \bullet m$ to indicate the action of swap $\sigma$ upon the mapping $m$. We compute a sequence of sets of candidate SWAPs as follows:

$$ 
\begin{aligned}
\Sigma_0 &= \text{swaps}(s_0) \\
\Sigma_{t+1} &= \arg \min_{\sigma \in \Sigma_t} d(s_t, \sigma \bullet m)
\end{aligned}
$$

<footnote n="5">⁵ See Section. 4 and Refs. [18, 8].</footnote>
5:8 On the Qubit Routing Problem

where swaps(s₀) denotes all the pertinent swaps available at the initial timestep. The sequence terminates either when |Σₜ| = 1 or after a predefined cutoff. The selected SWAP is added to the circuit and the mapping is updated accordingly. We now return to the start and continue until the entire input circuit has been consumed.

The pointwise ordering of the distance vectors employed by t|ket⟩ is strict in the sense that d(s, m) > d(s, σ ∙ m) implies that for all pairs of qubits (q, q') in s, the longest of the shortest paths between any two paired qubits in σ ∙ m is not longer than the longest of the shortest paths in m. In other words, the diameter of the subgraph composed of all pairs of qubits (q, q') in s should decrease strictly under the action of swap σ on the mapping m. In consequence, in some highly symmetric configurations, the algorithm sometimes gets stuck, failing to find any candidate swap. We employ two strategies to overcome this. The first is to attempt the process again with pairs of disjoint swaps instead of individual ones. If this also fails then we resort to brute force: a pair of maximally distant qubits in the current timestep are brought together using a sequence of swaps along their shortest connecting path. This guarantees at least one gate may be performed, and disrupts the symmetry of the configuration, hopefully allowing the algorithm to escape from the bad configuration.

Remark

In practice there is no need to slice the circuit in advance, and in fact better results are achieved
by computing the timesteps dynamically during routing. The “next slice” is recomputed
immediately after each update of the mapping, avoiding any unnecessary sequentialisation.

3.4 SWAP Synthesis and Clean-Up

If the target hardware does not support SWAP as a primitive operation, after the circuit has been routed the SWAPs in the routed circuit must be replaced with hardware appropriate gates, as per Section 2.2. While we assume that the input circuit was already well-optimised before routing, it is usually possible to remove some of the additional gates which are inserted during this process in a final clean-up pass.

The essential criterion here is that any changes to the circuit must respect the existing routing. This can be guaranteed by using any set of rewrite rules between one- and two-qubit circuits. The routing procedure will not insert SWAPs immediately before a two-qubit gate on the same two qubits, but it may do so afterwards, so the possibility to, for example, cancel consecutive CNOT gates exists. However such cancellation rules are the only “true” two-qubit rewrites which can be applied. In addition, t|ket⟩ uses a small set of rewrites for fusing single-qubit gates, and commuting single qubit gates past two-qubit gates. The particular rewrite rules vary according to supported gates of the hardware.

4 Graph Representation of Quantum Computers

We represent the architecture of a given quantum computer as a simple connected graph,
directed or undirected. We now list some specific architecture graphs used in this work.

1. *The ring*, Fig. 2(b). A one-dimensional cyclic graph where each node is connected to its two nearest neighbors.

2. *The cyclic butterfly*, Fig. 10(a). A non-planar graph with $n = r \times 2^r$ nodes. Each node is denoted by a pair $(w, i)$ where $w$ is $r$-bit sequence corresponding to one of the $2^r$ rows and $i$ represents the column. Two nodes $(w, i)$ and $(v, j)$ are connected if $j \equiv i + 1 \pmod r$.
and if $w = v$ or $w$ and $v$ have only one bit difference at position $i$, hence the connectivity is equal to 4 for any node, see Ref. [4].

3. *The square grid*, Fig. 10(b). A two-dimensional graph with a square shape where nodes are connected to their four neighbors except at the edges where there can be only two or three neighbors.

4. *The IBM Q 20 Tokyo*, Fig. 10(c). The graph supporting the 20-qubit processor produced by IBM is a two-dimensional graph with 20 nodes, it is rectangular with some extra connectivity, see Ref. [1].

5. *The Rigetti 19Q-Acorn*, Fig. 10(d). The graph supporting the quantum processor produced by Rigetti is a two-dimensional graph with 20 nodes, see Ref. [15].

In Appendix A Table 3 we present the basic properties of these graphs such as their degree and diameter, and the depth overhead of classical sorting algorithms on these graphs.

<figure><img src="image_13.png" /><figcaption>**Figure 10** (a) a cyclic butterfly graph with $n = 3 \times 2^3$ nodes (the first column is represented twice to improve the readability of the connectivity), (b) a 2-dimensional square grid with $n = 3^2$ nodes, (c) the IBM Q 20 Tokyo chip (Ref. [1]), and (d) the Rigetti 19Q-Acorn chip (Ref. [15]). The edges represent the allowed interactions between qubits.</figcaption></figure>
5:10 On the Qubit Routing Problem

5 Results

The current generation of quantum computers, the NISQ devices [13], are characterised by small numbers of qubits and shallow circuit depths. In this setting constant factors are more important than asymptotic analysis, so we present two sets of empirical results on the performance of t|ket〉's routing algorithm. In the first set of results we evaluate the scaling behaviour on synthetic inputs of increasing size. In the second we compare the performance of t|ket〉 against competing compiler implementations on a set of realistic circuits. Note that while the t|ket〉 algorithm is very efficient, we report on the quality of the results rather than the time or memory requirements.

5.1 Scaling

The routing algorithm described in Section 3 can handle circuits of arbitrary depth, and architectures corresponding to any connected graph. We now evaluate how increasing the circuit depth, as well as the size and connectivity of the architecture graph influence the depth of the routed circuit.

As described above, routing adds SWAP gates to the circuit, increasing both its total gate count and the depth of the circuit. Since the total gate count depends on the particular gate set supported by the architecture, we will consider only the increase in circuit depth here. Therefore a reasonable figure of merit is the depth ratio:

$$
R = \frac{\text{number of output timesteps}}{\text{number of input timesteps}},
$$

where timesteps are computed as described in Section 3.1. We define the mean depth overhead as

$$
N = \text{number of output timesteps} - \text{number of input timesteps.}
$$

For a fair comparison to classical sorting algorithms, we consider that a SWAP gate counts
as only one additional gate rather than, for example, three when decomposed into CNOT
gates, and hence will induce at most one additional timestep.

5.1.1 Scaling With Depth

To assess the performance of t|ket⟩ with respect to increasingly deep circuits we perform the
following protocol for each of the selected architectures.

- We randomly generate 1000 circuits of density $d = 1$ and $t$ initial timesteps for $t \in [2, 10]$. Note that requiring $d = 1$ implies there are no single-qubit gates in the circuit.

- Use $t|\text{ket}\rangle$ to route the circuit on the chosen architecture.

- Compute $R$ for the routed circuit.

We tested using the following five architectures:

- a ring of size $r = 64$;

- a square grid of size $r^2 = 64$;

- a cyclic butterfly of size $r2^r = 64$;

- the IBM Q 20 Tokyo ($n = 20$);

- the Rigetti 19Q-Acorn<fnref n="6" /> ($n = 20$).

<footnote n="6">⁶ The Rigetti Acorn has only 20 qubits, but due a manufacturing defect which only 19 are usable. This is not relevant to our tests [12].</footnote>
<figure><img src="image_14.png" /><figcaption>Figure 11 Multiple timesteps measurement and architecture comparison. The mean and standard deviation of the ratio *R* are represented. The left plot overlaps results for the ring, square grid and cyclic butterfly for 64 nodes. The right plot overlaps results for IBM and Rigetti architectures with 20 nodes. Results generated with random initial (dense) circuits with density equal to unity.</figcaption></figure>

The number of nodes for the ring, square grid and cyclic butterfly architectures is chosen for fair comparison and similarly for the IBM and the Rigetti cases. To eliminate sampling bias, a single set of 64-qubit circuits was generated for all the *n* = 64 architectures, and similarly for the *n* = 20 architectures.

Figure. 11 represents the mean and standard deviation of the ratio *R* for the graphs. The ratio *R* is approximately constant and the effect of circuit depth is dominated by the influence of the architecture's connectivity. This ratio seems to converge for circuits of depth greater than 5 and we report in Table 2 the values of *R* obtained for the largest number of input timesteps. While the ratios obtained seem rather large, it is worth remembering that *d* = 1 circuits are the worst case for routing.

5.1.2 Scaling With Architecture Size

To evaluate the scaling with respect to the size of the architecture we consider single-timestep
random quantum circuits of varying density, which are routed on architectures of increasing
size. Initial qubit mapping is disabled for these tests so that only the routing procedure is
evaluated. While this is an important part of the algorithm, in this case we are interested in
the scaling, to which the initial mapping only provides an initial offset.

- For each architecture of size *n* generate 10*n* random circuits of depth one, for each *d* ∈ {0.5, 0.67, 1.0}.

- Generate a random initial mapping of qubits on the architecture.

- Route the timestep using t|ket⟩, using the given mapping.

- Compute *N* for the routed circuit.

The following architectures were evaluated:

- Rings of size *r* ∈ [10, 200]

- Square grids of size *r*², *r* ∈ [3, 13]

- Cyclic butterflies of size *r*2*, *r* ∈ [2, 6].

The results are shown in Fig. 12 and the best fit parameters are given in Table 1. The
prior results for the ring and square grid are determined with a regression in log-log space
## 5:12 On the Qubit Routing Problem

<table><caption>Table 1 Scaling of the depth overhead with architecture size for single-timestep random circuits.</caption><thead><tr><th>Graph</th><th>d = 0.5</th><th>d = 0.67</th><th>d = 1.0</th></tr></thead><tbody><tr><td>Ring</td><td>0.2451 × n</td><td>0.2451 × n</td><td>0.2451 × n</td></tr><tr><td>Square</td><td>0.5501 × n<sup>0.55</sup></td><td>0.8050 × n<sup>0.56</sup></td><td>0.8991 × n<sup>0.58</sup></td></tr><tr><td>Cyclic Butterfly</td><td>0.3496 × log(n)<sup>1.85</sup></td><td>0.3002 × log(n)<sup>2.05</sup></td><td>0.1510 × log(n)<sup>2.72</sup></td></tr></tbody></table>

<table><caption>Table 2 Summary of our scaling results for dense circuits (d = 1).</caption><thead><tr><th>Graph</th><th>Depth overhead N for single-timestep circuits</th><th>Ratio output - input timesteps R</th></tr></thead><tbody><tr><td>Ring</td><td>0.2451 × n<sup>1.00</sup></td><td>16.42 ± 0.25 (n = 64)</td></tr><tr><td>Square grid</td><td>0.8991 × n<sup>0.58</sup></td><td>11.09 ± 0.56 (n = 64)</td></tr><tr><td>Cyclic butterfly</td><td>0.1510 × log(n)<sup>2.72</sup></td><td>7.14 ± 0.61 (n = 64)</td></tr><tr><td>Rigetti 19Q-Acorn</td><td>0</td><td>7.00 ± 0.47</td></tr><tr><td>IBM Q 20 Tokyo</td><td>0</td><td>6.08 ± 0.47</td></tr></tbody></table>

and the cyclic butterfly in log - log(log) space (represented in the insets for d = 1). In each case we see that the overhead appears to grow with the diameter of the graph, although with an exponent that varies (slightly) with the density.

## 5.2 Realistic Benchmarks

Random circuits have an essentially uniform structure, which circuits arising from quantum algorithms typically lack. In certain cases this can make random circuits easier to route – although in the preceding section we have largely avoided this by using circuits of high density. To give $t|ket\rangle$ a more realistic test we have also evaluated its performance on a standard set of 156 circuits which perform various algorithms. These range in size from 6 to 16 qubits, and 7 to more than half a million gates.

We ran $t|ket\rangle$ on each circuit of the benchmark set, with the 16-qubit ibmqx5 Rueschlikon, which is a 2 × 8 rectangular grid, as the target architecture. We then repeated the same test set using the 20-qubit IBM Tokyo as the target architecture. Since both these architectures have CNOT as their only two-qubit operation, and since it has lower fidelity than the single-qubit operations, we selected figures of merit based on minimising the CNOT count and depth of the output circuit. In this test we do perform SWAP synthesis, to get a more realistic evaluation of the output for these devices. Let $C_{CX}(c)$ be the total number of CNOT gates in circuit c, and let $D_{CX}(c)$ be the depth of the circuit counting only the CNOT gates. The two measures of interest are

$$R_D = \frac{D_{CX}(\text{out})}{D_{CX}(\text{in})}$$

$$R_C = \frac{C_{CX}(\text{out})}{C_{CX}(\text{in})}$$

where in and out are the input and output circuits respectively. The results are shown in Fig. 13. We can see that $t|ket\rangle$ achieves approximately linear overhead across the entire test
<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>

■ **Figure 12** Variation of depth overhead with architecture size for single timestep random circuits. Plots from left to right: the ring, square and cyclic butterfly architectures. The mean and standard deviation of the depth overhead versus number of nodes (or qubits) is represented. The inset plots represent the log-log linear fit for the ring and the square (resp. log-loglog fit for the butterfly) for the data set of density $d = 1$.
5:14 On the Qubit Routing Problem

<figure><img src="image_18.png" /><figcaption>Figure 13 Performance of $t|ket⟩$ on realistic test examples. (left) Mean ratio of output to input CX depth as a function of circuit depth (averaged in bins) (right) Mean ratio of output to input CX count (averaged in bins).</figcaption></figure>

set. The mean $R_D$ of 2.64 and $R_C$ of 2.61 for ibmqx5, and a mean $R_D$ of 1.73 and $R_C$ of 1.69 for IBM Tokyo.

We also compared the performance of $t|ket⟩$ to a selection of other freely available quantum compiler systems: IBM's QISKit [9], Project Q [16], and Rigetti Computing's Quilc [15]<fnref n="7" />. None of the other compilers was able to complete the test set in the time allotted, despite being given at least an hour of compute time per example on a powerful computer<fnref n="8" />. For comparison, $t|ket⟩$ completed the entire benchmark set in 15 mins on the same hardware. In addition, Project Q does not support routing for the IBM Tokyo architecture due to its unusual graph structure; therefore it was only tested on the ibmqx5 architecture. Therefore comparison of all four compilers is only available for circuits of fewer than 2000 total gates. The comparative results are shown in Fig. 14. We can see that $t|ket⟩$, Qiskit and Quilc exhibit approximately linear overhead, while Project Q appears somewhat worse than linear. A line of best fit calculated using the least squares method is shown for each compiler in Fig. 14. Quilc and $t|ket⟩$ exhibit very similar performance; the others show significantly higher overhead.

Finally, we compared the results to the published data of Zulehner et al. [20] who use the same benchmark set, but use total gate count and depth as the metric. Since Quilc does not generate the same gate set as the others, it was excluded from this comparison. The algorithm of Zulehner et al. [20] achieves comparable performance to $t|ket⟩$. The results are presented in Appendix B.

The test set we used for this work was published by IBM as part of the QISKit Developer Challenge<fnref n="9" />, a public competition to design a better routing algorithm. The competition was won by Zulehner et al. [20]. The test circuits are available from http://iic.jku.at/eda/research/ibm_qx_mapping/.

<footnote n="7">⁷ Since Quilc emits CZ as its preferred two-qubit gate we computed its figures using $D_{CZ}$ and $C_{CZ}$ instead.</footnote>

<footnote n="8">⁸ See Appendix B for more details.</footnote>

<footnote n="9">⁹ https://qx-awards.mybluemix.net/#qiskitDeveloperChallengeAward</footnote>
<figure><img src="image_19.png" /><figcaption>Figure 14 Comparison of performance between different compilers. Top row: routing on the ibmqx5 architecture. Bottom row: routing on the IBM Tokyo architecture. Left column: input CX count against output CX count. Right column: input CX depth against output CX depth. The benchmark is done against the test set available on http://iic.jku.at/eda/research/ibm_qx_mapping/ and the results are averaged in bins when the initial count or depth is equal.</figcaption></figure>

## 6 Conclusion

As better NISQ machines with the potential to effectively run quantum algorithms become available, the need for software solutions that allow users to easily run quantum circuits on them becomes more apparent. The $t|ket⟩$ routing module is one such solution and provides hardware compatibility with minimal extra gate overhead. It is flexible, general and scalable. In this work we have outlined how the routing procedure works and the figures of merit we use to assess routing performance for different graphs.

Finally, we consider possible extensions of this work. Firstly, we note that reinforcement learning offers an alternative approach to the qubit routing problem [6]. Eventually we foresee implementing several approaches to routing in $t|ket⟩$ to best adapt to differing algorithms and architectures.

Secondly, when considering the routing problem, we made the implicit assumption that all gates were equal. In real devices, notably superconducting devices, each gate has its own fidelity and run time and this has to be taken into account. Splitting a quantum circuit into timesteps becomes more complex as we introduce the different run times and we also have
5:16 On the Qubit Routing Problem

to ensure that the overhead in the error rate encountered by qubits is as small as possible. Additionally, in real life experiments, it has been observed in [17] and [11] that even the properties of the qubits can fluctuate intra-days. This calls for a general protocol that could accommodate this constraint. Addressing these different constraints transforms the problem from a routing one to a scheduling one, which we plan to address with t|ket⟩. Implementing these constraints and measuring t|ket⟩ performance on this matter will be the object of future work.

References

1 IBM Q. URL: https://www.research.ibm.com/ibm-q/.

2 Robert Beals, Stephen Brierley, Oliver Gray, Aram W. Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, and Mark Stather. Efficient Distributed Quantum Computing. *Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science*, 469(2153), 2013. doi:10.1098/rspa.2012.0686.

3 Édouard Bonnet, Tillmann Miltzow, and Paweł Rzążewski. Complexity of Token Swapping and Its Variants. *Algorithmica*, 80(9):2656–2682, September 2018. doi:10.1007/s00453-017-0387-0.

4 Stephen Brierley. Efficient implementation of Quantum circuits with limited qubit interactions. *Quantum Information and Computation*, 17(13-14):1096–1104, 2015. arXiv:1507.04263.

5 Steven Herbert. On the depth overhead incurred when running quantum algorithms on near-term quantum computers with limited qubit connectivity. arXiv preprint, 2018. arXiv: 1805.12570.

6 Steven Herbert and Akash Sengupta. Using Reinforcement Learning to find Efficient Qubit Routing Policies for Deployment in Near-term Quantum Computers. arXiv preprint, 2018. arXiv:1812.11619.

7 Yuichi Hirata, Masaki Nakanishi, Shigeru Yamashita, and Yasuhiko Nakashima. An efficient conversion of quantum circuits to a linear nearest neighbor architecture. *Quantum Information and Computation*, 11:142–166, January 2011.

8 Shien-Ching Hwang and Gen-Huey Chen. Cycles in butterfly graphs. *Networks: An International Journal*, 35(2):161–171, 2000.

9 IBM Research. Qiskit. URL: https://qiskit.org.

10 Mark R. Jerrum. The complexity of finding minimum-length generator sequences. *Theoretical Computer Science*, 36:265–289, 1985. doi:10.1016/0304-3975(85)90047-7.

11 P. V. Klimov, J. Kelly, Z. Chen, M. Neeley, A. Megrant, B. Burkett, R. Barends, K. Arya, B. Chiaro, Yu Chen, A. Dunsworth, A. Fowler, B. Foxen, C. Gidney, M. Giustina, R. Graff, T. Huang, E. Jeffrey, Erik Lucero, J. Y. Mutus, O. Naaman, C. Neill, C. Quintana, P. Roushan, Daniel Sank, A. Vainsencher, J. Wenner, T. C. White, S. Boixo, R. Babbush, V. N. Smelyanskiy, H. Neven, and John M. Martinis. Fluctuations of Energy-Relaxation Times in Superconducting Qubits. *Phys. Rev. Lett.*, 121:090502, August 2018. doi:10.1103/PhysRevLett.121.090502.

12 J. S. Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom, S. Caldwell, N. Didier, E. Schuyler Fried, S. Hong, P. Karalekas, C. B. Osborn, A. Papageorge, E. C. Peterson, G. Prawiroatmodjo, N. Rubin, Colm A. Ryan, D. Scarabelli, M. Scheer, E. A. Sete, P. Sivarajah, Robert S. Smith, A. Staley, N. Tezak, W. J. Zeng, A. Hudson, Blake R. Johnson, M. Reagor, M. P. da Silva, and C. Rigetti. Unsupervised Machine Learning on a Hybrid Quantum Computer. arXiv.org, 2017. arXiv:1712.05771.

13 John Preskill. Quantum Computing in the NISQ era and beyond. *Quantum*, 2:79, August 2018. doi:10.22331/q-2018-08-06-79.

14 Marcos Yukio Siraichi, Vinícius Fernandes dos Santos, Sylvain Collange, and Fernando Magno Quintão Pereira. Qubit allocation. In *Proceedings of the 2018 International Symposium on Code Generation and Optimization*, pages 113–125. ACM, 2018.
15 Robert S. Smith, Michael J. Curtis, and William Zeng. A Practical Quantum Instruction Set Architecture. Technical report, Rigetti Computing, 2016. arXiv:1608.03355.

16 Damian Steiger and Thomas Häner. Project Q: Powerful open source software for quantum computing. URL: https://projectq.ch [cited 28 January 2019].

17 Swamit S. Tannu and Moinuddin K. Qureshi. A Case for Variability-Aware Policies for NISQ-Era Quantum Computers. arXiv.org, 2018. arXiv:1805.10224.

18 Stephen A Wong. Hamilton cycles and paths in butterfly graphs. *Networks*, 26(3):145–150, 1995.

19 Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno. Swapping Labeled Tokens on Graphs. In Alfredo Ferro, Fabrizio Luccio, and Peter Widmayer, editors, *Fun with Algorithms*, pages 364–375. Springer International Publishing, 2014. doi:10.1007/978-3-319-07890-8_31.

20 Alwin Zulehner, Alexandru Paler, and Robert Wille. An Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures. arXiv.org, 2017. arXiv:1712.04722.

21 Alwin Zulehner and Robert Wille. Compiling SU(4) Quantum Circuits to IBM QX Architectures. arXiv.org, 2018. arXiv:1808.05661.
A Dynamical Routing Versus Sorting Networks

The routing problem described in this work can be solved using classical sorting algorithms. One of these is the cyclic odd-even sort for the ring of Fig. 2b). Starting from an architecture with *n* nodes, one compares sequentially all even and odd labeled edges. After exactly *n* − 1 timesteps, the input will be sorted regardless of input.

<figure><img src="image_20.png" /><figcaption>Figure 15 An example of sorting network on 8 inputs : odd-even sort over a ring.</figcaption></figure>

For the ring, square and cyclic butterfly graphs presented in Section 4, we summarize in Table 3 some details on the degree and diameter these graphs and the depth overhead of classical sorting algorithms (precisely the quantity *N* introduced in Section 5).

The downside of classical sorting algorithms is that they are unadapative: they compute
the same sequence of comparisons regardless of input. As circuits are usually sparse, see
Section 3.1, this leaves many unecessary comparisons, and would treat quantum circuits
as sequences of hard timesteps. Indeed, routing solutions derived from classical sorting
algorithms tend to pack a quantum circuit into multiple timesteps and then insert SWAP
gates in between timesteps. Solving the routing problem sequentially timestep by timestep
produces a concatenation of locally optimal solutions which can be very far from the globally
optimal one. A good solution should be dynamic, consider a SWAP gate's influence on
multiple timesteps, and optimize the global problem rather than the local one. See Ref. [21]
for an additional discussion on this matter. Additional details on sorting networks in quantum
computing are available in Ref. [2, 4].

<table><caption>Table 3 Comparison of different networks with *n* nodes.</caption>
  <thead>
    <tr>
      <th>Graph</th>
      <th>Degree</th>
      <th>Diameter</th>
      <th>N</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>Ring</td>
      <td>2</td>
      <td>n&#773;<sup>1</sup>&frasl;<sub>2</sub></td>
      <td>n&#773;<sup>1</sup> &minus; 1</td>
    </tr>
    <tr>
      <td>Square grid</td>
      <td>4</td>
      <td>2&radic;n &minus; 1</td>
      <td>3&radic;n</td>
    </tr>
    <tr>
      <td>Cyclic butterfly (n = r &times; 2<sup>r</sup>)</td>
      <td>4</td>
      <td>(3 log<sub>2</sub>(n)) / 2</td>
      <td>6 log<sub>2</sub>(n)</td>
    </tr>
  </tbody>
</table>
## B Detailed Benchmark Results

The table rows are the names of the benchmark QASM circuits, which are available from www.github.com/iic-jku/ibm_qx_mapping. Benchmark data for Zulehner et al. is collected from results presented in their paper [20] – note they do not present data for the complete set of examples. An example Jupyter workbook which demonstrates the benchmarking procedure is found at https://github.com/CQCL/pytket/blob/master/examples/tket_benchmarking.ipynb.

All computations were run on a Google Cloud virtual machine with the following specification: machine type n1-standard-2 (2 vCPUs, 7.5GB Memory), Intel Broadwell, 16GB RAM and Standard Persistent Disk. Each example was run until completion, the computation aborted, or until 60 minutes of real time had passed, whichever came first. Note that Quilc aborts in much less than 60 minutes.

In the tables, *g* indicates the gate count of the circuit; in Table 4 this means all gates; in Table 5 and 6 this means CX count only. The circuit depth is labelled *d*; in Table 4 this means total depth; in Table 5 and 6 this means CX depth only. The bold values are the best performance on the each row. The “t|ket〉 comparison” column shows the ratio between t|ket〉's performance and the best other compiler; values less than 1 indicate that t|ket〉 performs better.

### NOTE

The example circuit “ground_state_estimation” gives anomalously low values after routing. This is due to an error in the circuit, which allows the post-routing clean-up pass of t|ket〉 to eliminate almost the entire circuit.

### B.1 All Gates Comparison on ibmqx5

<table><caption>Table 4 All gates comparison on ibmqx5.</caption><thead><tr><th rowspan="2">Name</th><th rowspan="2">g<sub>in</sub></th><th rowspan="2">d<sub>in</sub></th><th colspan="2">Qiskit 0.7.0</th><th colspan="2">Zulehner et al.</th><th colspan="2">CQC's t|ket〉</th><th colspan="2">t|ket〉 comparison</th></tr><tr><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>r<sub>gate</sub></th><th>r<sub>depth</sub></th></tr></thead><tbody><tr><td>xor5_254</td><td>7</td><td>5</td><td>45</td><td>24</td><td>*</td><td>*</td><td><b>25</b></td><td><b>14</b></td><td>0.56</td><td>0.58</td></tr><tr><td>graycode6_47</td><td>5</td><td>5</td><td><b>13</b></td><td><b>7</b></td><td>*</td><td>*</td><td>15</td><td>9</td><td>1.15</td><td>1.29</td></tr><tr><td>ex1_226</td><td>7</td><td>5</td><td>56</td><td>32</td><td>*</td><td>*</td><td><b>25</b></td><td><b>14</b></td><td>0.45</td><td>0.44</td></tr><tr><td>4gt11_84</td><td>18</td><td>11</td><td>59</td><td>34</td><td>*</td><td>*</td><td><b>48</b></td><td><b>32</b></td><td>0.81</td><td>0.94</td></tr><tr><td>4mod5-v0_20</td><td>20</td><td>12</td><td>64</td><td>35</td><td>*</td><td>*</td><td><b>50</b></td><td><b>31</b></td><td>0.78</td><td>0.89</td></tr><tr><td>ex-1_166</td><td>19</td><td>12</td><td><b>53</b></td><td>36</td><td>*</td><td>*</td><td><b>53</b></td><td><b>34</b></td><td>1.00</td><td>0.94</td></tr><tr><td>4mod5-v1_22</td><td>21</td><td>12</td><td>75</td><td>46</td><td>*</td><td>*</td><td><b>64</b></td><td><b>40</b></td><td>0.85</td><td>0.87</td></tr><tr><td>mod5d1_63</td><td>22</td><td>13</td><td>94</td><td>53</td><td>*</td><td>*</td><td><b>65</b></td><td><b>39</b></td><td>0.69</td><td>0.74</td></tr><tr><td>ham3_102</td><td>20</td><td>13</td><td>62</td><td>39</td><td>*</td><td>*</td><td><b>47</b></td><td><b>32</b></td><td>0.76</td><td>0.82</td></tr><tr><td>4gt11_83</td><td>23</td><td>16</td><td>100</td><td>57</td><td>*</td><td>*</td><td><b>75</b></td><td><b>46</b></td><td>0.75</td><td>0.81</td></tr><tr><td>4gt11_82</td><td>27</td><td>20</td><td>109</td><td>61</td><td>*</td><td>*</td><td><b>86</b></td><td><b>55</b></td><td>0.79</td><td>0.90</td></tr><tr><td>rd32-v0_66</td><td>34</td><td>20</td><td>116</td><td>73</td><td>*</td><td>*</td><td><b>70</b></td><td><b>46</b></td><td>0.60</td><td>0.63</td></tr><tr><td>alu-v0_27</td><td>36</td><td>21</td><td>163</td><td>86</td><td>*</td><td>*</td><td><b>96</b></td><td><b>61</b></td><td>0.59</td><td>0.71</td></tr><tr><td>4mod5-v1_24</td><td>36</td><td>21</td><td>142</td><td>80</td><td>*</td><td>*</td><td><b>97</b></td><td><b>62</b></td><td>0.68</td><td>0.78</td></tr><tr><td>4mod5-v0_19</td><td>35</td><td>21</td><td>143</td><td>88</td><td>*</td><td>*</td><td><b>103</b></td><td><b>66</b></td><td>0.72</td><td>0.75</td></tr><tr><td>mod5mils_65</td><td>35</td><td>21</td><td>137</td><td>84</td><td>*</td><td>*</td><td><b>93</b></td><td><b>59</b></td><td>0.68</td><td>0.70</td></tr></tbody></table>
5:20 On the Qubit Routing Problem

<table><thead><tr><th rowspan="2">Name</th><th rowspan="2">g<sub>in</sub></th><th rowspan="2">d<sub>in</sub></th><th colspan="2">Qiskit 0.7.0</th><th colspan="2">Zulehner et al.</th><th colspan="2">CQC's t|ket⟩</th><th colspan="2">t|ket⟩ comparison</th></tr><tr><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>r<sub>gate</sub></th><th>r<sub>depth</sub></th></tr></thead><tbody><tr><td>rd32-v1_68</td><td>36</td><td>21</td><td>130</td><td>76</td><td>*</td><td>*</td><td><b>70</b></td><td><b>46</b></td><td>0.54</td><td>0.61</td></tr><tr><td>alu-v1_28</td><td>37</td><td>22</td><td>142</td><td>84</td><td>*</td><td>*</td><td><b>99</b></td><td><b>66</b></td><td>0.70</td><td>0.79</td></tr><tr><td>alu-v2_33</td><td>37</td><td>22</td><td>138</td><td>80</td><td>*</td><td>*</td><td><b>91</b></td><td><b>57</b></td><td>0.66</td><td>0.71</td></tr><tr><td>alu-v4_37</td><td>37</td><td>22</td><td>130</td><td>75</td><td>*</td><td>*</td><td><b>103</b></td><td><b>64</b></td><td>0.79</td><td>0.85</td></tr><tr><td>alu-v3_35</td><td>37</td><td>22</td><td>143</td><td>79</td><td>*</td><td>*</td><td><b>103</b></td><td><b>64</b></td><td>0.72</td><td>0.81</td></tr><tr><td>3_17_13</td><td>36</td><td>22</td><td>127</td><td>88</td><td>*</td><td>*</td><td><b>89</b></td><td><b>62</b></td><td>0.70</td><td>0.70</td></tr><tr><td>alu-v1_29</td><td>37</td><td>22</td><td>135</td><td>78</td><td>*</td><td>*</td><td><b>101</b></td><td><b>66</b></td><td>0.75</td><td>0.85</td></tr><tr><td>millor_11</td><td>50</td><td>29</td><td>158</td><td>107</td><td>*</td><td>*</td><td><b>139</b></td><td><b>92</b></td><td>0.88</td><td>0.86</td></tr><tr><td>alu-v3_34</td><td>52</td><td>30</td><td>212</td><td>126</td><td>*</td><td>*</td><td><b>146</b></td><td><b>99</b></td><td>0.69</td><td>0.79</td></tr><tr><td>decod24-v2_43</td><td>52</td><td>30</td><td>206</td><td>123</td><td>*</td><td>*</td><td><b>136</b></td><td><b>89</b></td><td>0.66</td><td>0.72</td></tr><tr><td>decod24-v0_38</td><td>51</td><td>30</td><td>173</td><td>108</td><td>*</td><td>*</td><td><b>127</b></td><td><b>84</b></td><td>0.73</td><td>0.78</td></tr><tr><td>mod5d2_64</td><td>53</td><td>32</td><td>185</td><td>110</td><td>*</td><td>*</td><td><b>158</b></td><td><b>105</b></td><td>0.85</td><td>0.95</td></tr><tr><td>4gt13_92</td><td>66</td><td>38</td><td>263</td><td>158</td><td>*</td><td>*</td><td><b>187</b></td><td><b>119</b></td><td>0.71</td><td>0.75</td></tr><tr><td>4gt13-v1_93</td><td>68</td><td>39</td><td>281</td><td>164</td><td>*</td><td>*</td><td><b>168</b></td><td><b>105</b></td><td>0.60</td><td>0.64</td></tr><tr><td>4mod5-v0_18</td><td>69</td><td>40</td><td>272</td><td>160</td><td>*</td><td>*</td><td><b>181</b></td><td><b>122</b></td><td>0.67</td><td>0.76</td></tr><tr><td>decod24-bdd_294</td><td>73</td><td>40</td><td>262</td><td>147</td><td>*</td><td>*</td><td><b>205</b></td><td><b>129</b></td><td>0.78</td><td>0.88</td></tr><tr><td>one-two-three-v2_100</td><td>69</td><td>40</td><td>256</td><td>151</td><td>*</td><td>*</td><td><b>194</b></td><td><b>129</b></td><td>0.76</td><td>0.85</td></tr><tr><td>one-two-three-v3_101</td><td>70</td><td>40</td><td>268</td><td>165</td><td>*</td><td>*</td><td><b>199</b></td><td><b>129</b></td><td>0.74</td><td>0.78</td></tr><tr><td>4mod5-v1_23</td><td>69</td><td>41</td><td>283</td><td>154</td><td>*</td><td>*</td><td><b>196</b></td><td><b>136</b></td><td>0.69</td><td>0.88</td></tr><tr><td>4mod5-bdd_287</td><td>70</td><td>41</td><td>283</td><td>152</td><td>*</td><td>*</td><td><b>212</b></td><td><b>133</b></td><td>0.75</td><td>0.88</td></tr><tr><td>rd32_270</td><td>84</td><td>47</td><td>289</td><td>167</td><td>*</td><td>*</td><td><b>220</b></td><td><b>148</b></td><td>0.76</td><td>0.89</td></tr><tr><td>4gt5_75</td><td>83</td><td>47</td><td>315</td><td>175</td><td>*</td><td>*</td><td><b>227</b></td><td><b>143</b></td><td>0.72</td><td>0.82</td></tr><tr><td>alu-bdd_288</td><td>84</td><td>48</td><td>319</td><td>170</td><td>*</td><td>*</td><td><b>253</b></td><td><b>160</b></td><td>0.79</td><td>0.94</td></tr><tr><td>alu-v0_26</td><td>84</td><td>49</td><td>331</td><td>188</td><td>*</td><td>*</td><td><b>230</b></td><td><b>145</b></td><td>0.69</td><td>0.77</td></tr><tr><td>decod24-v1_41</td><td>85</td><td>50</td><td>355</td><td>198</td><td>*</td><td>*</td><td><b>221</b></td><td><b>139</b></td><td>0.62</td><td>0.70</td></tr><tr><td>rd53_138</td><td>132</td><td>56</td><td>642</td><td>269</td><td>*</td><td>*</td><td><b>416</b></td><td><b>217</b></td><td>0.65</td><td>0.81</td></tr><tr><td>4gt5_76</td><td>91</td><td>56</td><td>360</td><td>195</td><td>*</td><td>*</td><td><b>266</b></td><td><b>168</b></td><td>0.74</td><td>0.86</td></tr><tr><td>4gt13_91</td><td>103</td><td>61</td><td>410</td><td>229</td><td>*</td><td>*</td><td><b>269</b></td><td><b>181</b></td><td>0.66</td><td>0.79</td></tr><tr><td>cnt3-5_179</td><td>175</td><td>61</td><td>684</td><td>275</td><td>*</td><td>*</td><td><b>569</b></td><td><b>221</b></td><td>0.83</td><td>0.80</td></tr><tr><td>qft_10</td><td>200</td><td>63</td><td>692</td><td>214</td><td>447</td><td>170</td><td><b>345</b></td><td><b>154</b></td><td>0.77</td><td>0.91</td></tr><tr><td>4gt13_90</td><td>107</td><td>65</td><td>427</td><td>250</td><td>*</td><td>*</td><td><b>284</b></td><td><b>190</b></td><td>0.67</td><td>0.76</td></tr><tr><td>alu-v4_36</td><td>115</td><td>66</td><td>410</td><td>232</td><td>*</td><td>*</td><td><b>286</b></td><td><b>184</b></td><td>0.70</td><td>0.79</td></tr><tr><td>mini_alu_305</td><td>173</td><td>69</td><td>829</td><td>317</td><td><b>474</b></td><td><b>225</b></td><td>524</td><td>243</td><td>1.11</td><td>1.08</td></tr><tr><td>ising_model_10</td><td>480</td><td>70</td><td><b>235</b></td><td><b>41</b></td><td>251</td><td>47</td><td>255</td><td><b>41</b></td><td>1.09</td><td>1.00</td></tr><tr><td>ising_model_16</td><td>786</td><td>71</td><td><b>391</b></td><td><b>41</b></td><td>426</td><td>48</td><td>426</td><td><b>41</b></td><td>1.09</td><td>1.00</td></tr><tr><td>ising_model_13</td><td>633</td><td>71</td><td><b>313</b></td><td><b>41</b></td><td>329</td><td>47</td><td>398</td><td>110</td><td>1.27</td><td>2.68</td></tr><tr><td>4gt5_77</td><td>131</td><td>74</td><td>451</td><td>266</td><td>*</td><td>*</td><td><b>356</b></td><td><b>226</b></td><td>0.79</td><td>0.85</td></tr><tr><td>sys6-v0_111</td><td>215</td><td>75</td><td>975</td><td>365</td><td><b>613</b></td><td><b>250</b></td><td>675</td><td>264</td><td>1.10</td><td>1.06</td></tr><tr><td>one-two-three-v1_99</td><td>132</td><td>76</td><td>501</td><td>299</td><td>*</td><td>*</td><td><b>354</b></td><td><b>233</b></td><td>0.71</td><td>0.78</td></tr><tr><td>one-two-three-v0_98</td><td>146</td><td>82</td><td>578</td><td>343</td><td>*</td><td>*</td><td><b>376</b></td><td><b>250</b></td><td>0.65</td><td>0.73</td></tr><tr><td>decod24-v3_45</td><td>150</td><td>84</td><td>551</td><td>318</td><td>*</td><td>*</td><td><b>383</b></td><td><b>247</b></td><td>0.70</td><td>0.78</td></tr><tr><td>4gt10-v1_81</td><td>148</td><td>84</td><td>555</td><td>310</td><td>*</td><td>*</td><td><b>377</b></td><td><b>248</b></td><td>0.68</td><td>0.80</td></tr></tbody></table>
<table><thead><tr><th rowspan="2">Name</th><th rowspan="2">g<sub>in</sub></th><th rowspan="2">d<sub>in</sub></th><th colspan="2">Qiskit 0.7.0</th><th colspan="2">Zulehner et al.</th><th colspan="2">CQC's t|ket⟩</th><th colspan="2">t|ket⟩ comparison</th></tr><tr><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>r<sub>gate</sub></th><th>r<sub>depth</sub></th></tr></thead><tbody><tr><td>aj-e11_165</td><td>151</td><td>86</td><td>541</td><td>309</td><td>*</td><td>*</td><td><b>402</b></td><td><b>260</b></td><td>0.74</td><td>0.84</td></tr><tr><td>4mod7-v0_94</td><td>162</td><td>92</td><td>641</td><td>374</td><td>*</td><td>*</td><td><b>442</b></td><td><b>291</b></td><td>0.69</td><td>0.78</td></tr><tr><td>alu-v2_32</td><td>163</td><td>92</td><td>587</td><td>340</td><td>*</td><td>*</td><td><b>458</b></td><td><b>292</b></td><td>0.78</td><td>0.86</td></tr><tr><td>rd73_140</td><td>230</td><td>92</td><td>1008</td><td>416</td><td><b>656</b></td><td><b>301</b></td><td>675</td><td>329</td><td>1.03</td><td>1.09</td></tr><tr><td>4mod7-v1_96</td><td>164</td><td>94</td><td>617</td><td>351</td><td>*</td><td>*</td><td><b>443</b></td><td><b>284</b></td><td>0.72</td><td>0.81</td></tr><tr><td>4gt4-v0_80</td><td>179</td><td>101</td><td>704</td><td>373</td><td>*</td><td>*</td><td><b>458</b></td><td><b>293</b></td><td>0.65</td><td>0.79</td></tr><tr><td>mod10_176</td><td>178</td><td>101</td><td>685</td><td>384</td><td>*</td><td>*</td><td><b>459</b></td><td><b>293</b></td><td>0.67</td><td>0.76</td></tr><tr><td>0410184_169</td><td>211</td><td>104</td><td>846</td><td>399</td><td>758</td><td><b>336</b></td><td><b>739</b></td><td>347</td><td>0.97</td><td>1.03</td></tr><tr><td>qft_16</td><td>512</td><td>105</td><td>2131</td><td>532</td><td>1341</td><td><b>404</b></td><td><b>1233</b></td><td>446</td><td>0.92</td><td>1.10</td></tr><tr><td>4gt12-v0_88</td><td>194</td><td>108</td><td>793</td><td>432</td><td>*</td><td>*</td><td><b>499</b></td><td><b>320</b></td><td>0.63</td><td>0.74</td></tr><tr><td>rd84_142</td><td>343</td><td>110</td><td>1660</td><td>548</td><td><b>971</b></td><td><b>353</b></td><td>1166</td><td>506</td><td>1.20</td><td>1.43</td></tr><tr><td>rd53_311</td><td>275</td><td>124</td><td>1358</td><td>560</td><td><b>942</b></td><td>469</td><td>959</td><td><b>452</b></td><td>1.02</td><td>0.96</td></tr><tr><td>4_49_16</td><td>217</td><td>125</td><td>783</td><td>459</td><td>*</td><td>*</td><td><b>610</b></td><td><b>398</b></td><td>0.78</td><td>0.87</td></tr><tr><td>sym9_146</td><td>328</td><td>127</td><td>1584</td><td>640</td><td><b>955</b></td><td><b>425</b></td><td>999</td><td>451</td><td>1.05</td><td>1.06</td></tr><tr><td>4gt12-v1_89</td><td>228</td><td>130</td><td>855</td><td>473</td><td>*</td><td>*</td><td><b>592</b></td><td><b>381</b></td><td>0.69</td><td>0.81</td></tr><tr><td>4gt12-v0_87</td><td>247</td><td>131</td><td>919</td><td>484</td><td>*</td><td>*</td><td><b>650</b></td><td><b>396</b></td><td>0.71</td><td>0.82</td></tr><tr><td>4gt4-v0_79</td><td>231</td><td>132</td><td>893</td><td>495</td><td>*</td><td>*</td><td><b>622</b></td><td><b>399</b></td><td>0.70</td><td>0.81</td></tr><tr><td>hwb4_49</td><td>233</td><td>134</td><td>929</td><td>540</td><td>*</td><td>*</td><td><b>621</b></td><td><b>405</b></td><td>0.67</td><td>0.75</td></tr><tr><td>sym6_316</td><td>270</td><td>135</td><td>1381</td><td>625</td><td><b>852</b></td><td><b>456</b></td><td>890</td><td>471</td><td>1.04</td><td>1.03</td></tr><tr><td>4gt12-v0_86</td><td>251</td><td>135</td><td>992</td><td>512</td><td>*</td><td>*</td><td><b>668</b></td><td><b>410</b></td><td>0.67</td><td>0.80</td></tr><tr><td>4gt4-v0_72</td><td>258</td><td>137</td><td>903</td><td>485</td><td>*</td><td>*</td><td><b>658</b></td><td><b>401</b></td><td>0.73</td><td>0.83</td></tr><tr><td>4gt4-v0_78</td><td>235</td><td>137</td><td>935</td><td>492</td><td>*</td><td>*</td><td><b>641</b></td><td><b>411</b></td><td>0.69</td><td>0.84</td></tr><tr><td>mod10_171</td><td>244</td><td>139</td><td>859</td><td>496</td><td>*</td><td>*</td><td><b>640</b></td><td><b>417</b></td><td>0.75</td><td>0.84</td></tr><tr><td>4gt4-v1_74</td><td>273</td><td>154</td><td>1008</td><td>570</td><td>*</td><td>*</td><td><b>732</b></td><td><b>469</b></td><td>0.73</td><td>0.82</td></tr><tr><td>rd53_135</td><td>296</td><td>159</td><td>1132</td><td>604</td><td>*</td><td>*</td><td><b>854</b></td><td><b>536</b></td><td>0.75</td><td>0.89</td></tr><tr><td>mini-alu_167</td><td>288</td><td>162</td><td>953</td><td>557</td><td>*</td><td>*</td><td><b>748</b></td><td><b>480</b></td><td>0.78</td><td>0.86</td></tr><tr><td>one-two-three-v0_97</td><td>290</td><td>163</td><td>1060</td><td>610</td><td>*</td><td>*</td><td><b>737</b></td><td><b>487</b></td><td>0.70</td><td>0.80</td></tr><tr><td>ham7_104</td><td>320</td><td>185</td><td>1327</td><td>697</td><td>*</td><td>*</td><td><b>896</b></td><td><b>550</b></td><td>0.68</td><td>0.79</td></tr><tr><td>decod24-enable_126</td><td>338</td><td>190</td><td>1280</td><td>730</td><td>*</td><td>*</td><td><b>894</b></td><td><b>586</b></td><td>0.70</td><td>0.80</td></tr><tr><td>mod8-10_178</td><td>342</td><td>193</td><td>1341</td><td>722</td><td>*</td><td>*</td><td><b>879</b></td><td><b>561</b></td><td>0.66</td><td>0.78</td></tr><tr><td>cnt3-5_180</td><td>485</td><td>209</td><td>1833</td><td>822</td><td><b>1376</b></td><td><b>669</b></td><td>1560</td><td>819</td><td>1.13</td><td>1.22</td></tr><tr><td>ex3_229</td><td>403</td><td>226</td><td>1566</td><td>859</td><td>*</td><td>*</td><td><b>1057</b></td><td><b>663</b></td><td>0.67</td><td>0.77</td></tr><tr><td>4gt4-v0_73</td><td>395</td><td>227</td><td>1413</td><td>799</td><td>*</td><td>*</td><td><b>1037</b></td><td><b>671</b></td><td>0.73</td><td>0.84</td></tr><tr><td>mod8-10_177</td><td>440</td><td>251</td><td>1494</td><td>884</td><td>*</td><td>*</td><td><b>1169</b></td><td><b>750</b></td><td>0.78</td><td>0.85</td></tr><tr><td>C17_204</td><td>467</td><td>253</td><td>1789</td><td>950</td><td>*</td><td>*</td><td><b>1318</b></td><td><b>812</b></td><td>0.74</td><td>0.85</td></tr><tr><td>alu-v2_31</td><td>451</td><td>255</td><td>1499</td><td>874</td><td>*</td><td>*</td><td><b>1171</b></td><td><b>762</b></td><td>0.78</td><td>0.87</td></tr><tr><td>rd53_131</td><td>469</td><td>261</td><td>1875</td><td>1016</td><td>*</td><td>*</td><td><b>1238</b></td><td><b>776</b></td><td>0.66</td><td>0.76</td></tr><tr><td>alu-v2_30</td><td>504</td><td>285</td><td>1746</td><td>982</td><td>*</td><td>*</td><td><b>1335</b></td><td><b>850</b></td><td>0.76</td><td>0.87</td></tr><tr><td>mod5adder_127</td><td>555</td><td>302</td><td>2094</td><td>1135</td><td>*</td><td>*</td><td><b>1407</b></td><td><b>903</b></td><td>0.67</td><td>0.80</td></tr><tr><td>rd53_133</td><td>580</td><td>327</td><td>2149</td><td>1172</td><td>*</td><td>*</td><td><b>1623</b></td><td><b>986</b></td><td>0.76</td><td>0.84</td></tr><tr><td>cm82a_208</td><td>650</td><td>337</td><td>2624</td><td>1303</td><td>*</td><td>*</td><td><b>1777</b></td><td><b>1036</b></td><td>0.68</td><td>0.80</td></tr><tr><td>majority_239</td><td>612</td><td>344</td><td>2437</td><td>1267</td><td>*</td><td>*</td><td><b>1648</b></td><td><b>1022</b></td><td>0.68</td><td>0.81</td></tr><tr><td>ex2_227</td><td>631</td><td>355</td><td>2568</td><td>1340</td><td>*</td><td>*</td><td><b>1722</b></td><td><b>1092</b></td><td>0.67</td><td>0.81</td></tr><tr><td>sf_276</td><td>778</td><td>435</td><td>2895</td><td>1615</td><td>*</td><td>*</td><td><b>2012</b></td><td><b>1312</b></td><td>0.69</td><td>0.81</td></tr></tbody></table>
5:22 On the Qubit Routing Problem

<table><thead><tr><th rowspan="2">Name</th><th rowspan="2">g<sub>in</sub></th><th rowspan="2">d<sub>in</sub></th><th colspan="2">Qiskit 0.7.0</th><th colspan="2">Zulehner et al.</th><th colspan="2">CQC's t|ket⟩</th><th colspan="2">t|ket⟩ comparison</th></tr><tr><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>r<sub>gate</sub></th><th>r<sub>depth</sub></th></tr></thead><tbody><tr><td>sf_274</td><td>781</td><td>436</td><td>2875</td><td>1577</td><td>*</td><td>*</td><td><b>1989</b></td><td><b>1293</b></td><td>0.69</td><td>0.82</td></tr><tr><td>con1_216</td><td>954</td><td>508</td><td>3836</td><td>1966</td><td>*</td><td>*</td><td><b>2815</b></td><td><b>1689</b></td><td>0.73</td><td>0.86</td></tr><tr><td>wim_266</td><td>986</td><td>514</td><td>3777</td><td>1921</td><td>2985</td><td>1711</td><td><b>2861</b></td><td><b>1707</b></td><td>0.96</td><td>1.00</td></tr><tr><td>rd53_130</td><td>1043</td><td>569</td><td>3783</td><td>2049</td><td>*</td><td>*</td><td><b>2872</b></td><td><b>1756</b></td><td>0.76</td><td>0.86</td></tr><tr><td>f2_232</td><td>1206</td><td>668</td><td>4737</td><td>2459</td><td>*</td><td>*</td><td><b>3529</b></td><td><b>2208</b></td><td>0.74</td><td>0.90</td></tr><tr><td>cm152a_212</td><td>1221</td><td>684</td><td>4791</td><td>2499</td><td>3738</td><td><b>2155</b></td><td><b>3580</b></td><td>2195</td><td>0.96</td><td>1.02</td></tr><tr><td>rd53_251</td><td>1291</td><td>712</td><td>4868</td><td>2668</td><td>*</td><td>*</td><td><b>3665</b></td><td><b>2279</b></td><td>0.75</td><td>0.85</td></tr><tr><td>hwb5_53</td><td>1336</td><td>758</td><td>4917</td><td>2766</td><td>*</td><td>*</td><td><b>3577</b></td><td><b>2287</b></td><td>0.73</td><td>0.83</td></tr><tr><td>cm42a_207</td><td>1776</td><td>940</td><td>6862</td><td>3507</td><td>5431</td><td><b>3013</b></td><td><b>5066</b></td><td>3043</td><td>0.93</td><td>1.01</td></tr><tr><td>pm1_249</td><td>1776</td><td>940</td><td>7274</td><td>3744</td><td>5431</td><td><b>3013</b></td><td><b>5066</b></td><td>3043</td><td>0.93</td><td>1.01</td></tr><tr><td>dc1_220</td><td>1914</td><td>1038</td><td>7632</td><td>3973</td><td>5946</td><td>3378</td><td><b>5433</b></td><td><b>3180</b></td><td>0.91</td><td>0.94</td></tr><tr><td>squar5_261</td><td>1993</td><td>1049</td><td>8019</td><td>4006</td><td>6267</td><td><b>3448</b></td><td><b>6110</b></td><td>3532</td><td>0.97</td><td>1.02</td></tr><tr><td>z4_268</td><td>3073</td><td>1644</td><td>12567</td><td>6352</td><td>9717</td><td><b>5335</b></td><td><b>9379</b></td><td>5532</td><td>0.97</td><td>1.04</td></tr><tr><td>sqrt8_260</td><td>3009</td><td>1659</td><td>12852</td><td>6615</td><td>9744</td><td>5501</td><td><b>8869</b></td><td><b>5355</b></td><td>0.91</td><td>0.97</td></tr><tr><td>radd_250</td><td>3213</td><td>1781</td><td>13098</td><td>6880</td><td>10441</td><td><b>5872</b></td><td><b>9831</b></td><td>5892</td><td>0.94</td><td>1.00</td></tr><tr><td>adr4_197</td><td>3439</td><td>1839</td><td>13966</td><td>7050</td><td>11301</td><td>6205</td><td><b>10074</b></td><td><b>5910</b></td><td>0.89</td><td>0.95</td></tr><tr><td>sym6_145</td><td>3888</td><td>2187</td><td>14078</td><td>7794</td><td>*</td><td>*</td><td><b>10961</b></td><td><b>6858</b></td><td>0.78</td><td>0.88</td></tr><tr><td>misex1_241</td><td>4813</td><td>2676</td><td>-</td><td>-</td><td>15185</td><td><b>8729</b></td><td><b>14411</b></td><td>8834</td><td>0.95</td><td>1.01</td></tr><tr><td>rd73_252</td><td>5321</td><td>2867</td><td>-</td><td>-</td><td>*</td><td>*</td><td><b>15666</b></td><td><b>9288</b></td><td></td><td></td></tr><tr><td>cycle10_2_110</td><td>6050</td><td>3386</td><td>-</td><td>-</td><td>19857</td><td><b>11141</b></td><td><b>18361</b></td><td>11314</td><td>0.92</td><td>1.02</td></tr><tr><td>hwb6_56</td><td>6723</td><td>3736</td><td>-</td><td>-</td><td>*</td><td>*</td><td><b>18688</b></td><td><b>11650</b></td><td></td><td></td></tr><tr><td>square_root_7</td><td>7630</td><td>3847</td><td>-</td><td>-</td><td>25212</td><td><b>13205</b></td><td><b>23258</b></td><td>13305</td><td>0.92</td><td>1.01</td></tr><tr><td>ham15_107</td><td>8763</td><td>4819</td><td>-</td><td>-</td><td>28310</td><td><b>15891</b></td><td><b>26551</b></td><td>15951</td><td>0.94</td><td>1.00</td></tr><tr><td>dc2_222</td><td>9462</td><td>5242</td><td>-</td><td>-</td><td>30680</td><td><b>17269</b></td><td><b>29784</b></td><td>18303</td><td>0.97</td><td>1.06</td></tr><tr><td>sqrtn_258</td><td>10223</td><td>5458</td><td>-</td><td>-</td><td>32095</td><td>17801</td><td><b>29740</b></td><td><b>17456</b></td><td>0.93</td><td>0.98</td></tr><tr><td>inc_237</td><td>10619</td><td>5863</td><td>-</td><td>-</td><td>34375</td><td><b>19176</b></td><td><b>32096</b></td><td>19523</td><td>0.93</td><td>1.02</td></tr><tr><td>cm85a_209</td><td>11414</td><td>6374</td><td>-</td><td>-</td><td>37746</td><td>21189</td><td><b>34467</b></td><td><b>21014</b></td><td>0.91</td><td>0.99</td></tr><tr><td>rd84_253</td><td>13658</td><td>7261</td><td>-</td><td>-</td><td>45497</td><td>24473</td><td><b>41770</b></td><td><b>24147</b></td><td>0.92</td><td>0.99</td></tr><tr><td>col4_215</td><td>17936</td><td>8570</td><td>-</td><td>-</td><td>63826</td><td><b>30366</b></td><td><b>57906</b></td><td>30807</td><td>0.91</td><td>1.01</td></tr><tr><td>root_255</td><td>17159</td><td>8835</td><td>-</td><td>-</td><td>57874</td><td><b>30068</b></td><td><b>52900</b></td><td>30448</td><td>0.91</td><td>1.01</td></tr><tr><td>mlp4_245</td><td>18852</td><td>10328</td><td>-</td><td>-</td><td>*</td><td>*</td><td><b>59020</b></td><td><b>35251</b></td><td></td><td></td></tr><tr><td>urf2_277</td><td>20112</td><td>11390</td><td>-</td><td>-</td><td>*</td><td>*</td><td><b>64763</b></td><td><b>37903</b></td><td></td><td></td></tr><tr><td>sym9_148</td><td>21504</td><td>12087</td><td>-</td><td>-</td><td>66637</td><td>38849</td><td><b>61342</b></td><td><b>37448</b></td><td>0.92</td><td>0.96</td></tr><tr><td>life_238</td><td>22445</td><td>12511</td><td>-</td><td>-</td><td>74632</td><td>41767</td><td><b>67852</b></td><td><b>40987</b></td><td>0.91</td><td>0.98</td></tr><tr><td>hwb7_59</td><td>24379</td><td>13437</td><td>-</td><td>-</td><td>*</td><td>*</td><td><b>68463</b></td><td><b>41787</b></td><td></td><td></td></tr><tr><td>max46_240</td><td>27126</td><td>14257</td><td>-</td><td>-</td><td>84914</td><td><b>46270</b></td><td><b>80329</b></td><td>46590</td><td>0.95</td><td>1.01</td></tr><tr><td>clip_206</td><td>33827</td><td>17879</td><td>-</td><td>-</td><td>114336</td><td><b>60882</b></td><td><b>104857</b></td><td>61053</td><td>0.92</td><td>1.00</td></tr><tr><td>9symml_195</td><td>34881</td><td>19235</td><td>-</td><td>-</td><td>116508</td><td>64279</td><td><b>106669</b></td><td><b>63651</b></td><td>0.92</td><td>0.99</td></tr><tr><td>sym9_193</td><td>34881</td><td>19235</td><td>-</td><td>-</td><td>116508</td><td>64279</td><td><b>106669</b></td><td><b>63651</b></td><td>0.92</td><td>0.99</td></tr><tr><td>sao2_257</td><td>38577</td><td>19563</td><td>-</td><td>-</td><td>131002</td><td><b>66975</b></td><td><b>120587</b></td><td>68114</td><td>0.92</td><td>1.02</td></tr><tr><td>dist_223</td><td>38046</td><td>19694</td><td>-</td><td>-</td><td>125867</td><td><b>66318</b></td><td><b>117367</b></td><td>67731</td><td>0.93</td><td>1.02</td></tr><tr><td>urf5_280</td><td>49829</td><td>27822</td><td>-</td><td>-</td><td>*</td><td>*</td><td><b>155513</b></td><td><b>92045</b></td><td></td><td></td></tr><tr><td>urf1_278</td><td>54766</td><td>30955</td><td>-</td><td>-</td><td>*</td><td>*</td><td><b>178380</b></td><td><b>104583</b></td><td></td><td></td></tr><tr><td>sym10_262</td><td>64283</td><td>35572</td><td>-</td><td>-</td><td>215569</td><td>118753</td><td><b>197690</b></td><td><b>118233</b></td><td>0.92</td><td>1.00</td></tr><tr><td>hwb8_113</td><td>69380</td><td>38717</td><td>-</td><td>-</td><td>*</td><td>*</td><td><b>201013</b></td><td><b>122660</b></td><td></td><td></td></tr><tr><td>urf2_152</td><td>80480</td><td>44100</td><td>-</td><td>-</td><td>*</td><td>*</td><td><b>221274</b></td><td><b>139339</b></td><td></td><td></td></tr></tbody></table>
<table><thead><tr><th rowspan="2">Name</th><th colspan="2">Qiskit 0.7.0</th><th colspan="2">Zulehner et al.</th><th colspan="2">CQC's t|ket⟩</th><th colspan="2">t|ket⟩ comparison</th></tr><tr><th>g<sub>in</sub></th><th>d<sub>in</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>r<sub>gate</sub></th><th>r<sub>depth</sub></th></tr></thead><tbody><tr><td>urf3_279</td><td>125362</td><td>70702</td><td>—</td><td>—</td><td>440509</td><td>239702</td><td>406738</td><td>237181</td><td>0.92</td><td>0.99</td></tr><tr><td>plus63mod4096_163128744</td><td>72246</td><td>—</td><td>—</td><td>—</td><td>439981</td><td>243861</td><td>402395</td><td>243814</td><td>0.91</td><td>1.00</td></tr><tr><td>urf5_158</td><td>164416</td><td>89145</td><td>—</td><td>—</td><td>—</td><td>*</td><td>*</td><td>465129</td><td>284825</td><td></td><td></td></tr><tr><td>urf6_160</td><td>171840</td><td>93645</td><td>—</td><td>—</td><td>580295</td><td>313011</td><td>541013</td><td>313653</td><td>0.93</td><td>1.00</td></tr><tr><td>urf1_149</td><td>184864</td><td>99585</td><td>—</td><td>—</td><td>—</td><td>*</td><td>*</td><td>525310</td><td>321185</td><td></td><td></td></tr><tr><td>plus63mod8192_164187112</td><td>105142</td><td>—</td><td>—</td><td>—</td><td>640204</td><td>354076</td><td>585116</td><td>355168</td><td>0.91</td><td>1.00</td></tr><tr><td>hwb9_119</td><td>207775</td><td>116199</td><td>—</td><td>—</td><td>655220</td><td>375105</td><td>608175</td><td>369246</td><td>0.93</td><td>0.98</td></tr><tr><td>urf3_155</td><td>423488</td><td>229365</td><td>—</td><td>—</td><td>—</td><td>*</td><td>*</td><td>1211536</td><td>735676</td><td></td><td></td></tr><tr><td>ground_state _esti-390180</td><td>245614</td><td>—</td><td>—</td><td>—</td><td>520010</td><td>376695</td><td>12243</td><td>6804</td><td>0.02</td><td>0.02</td></tr><tr><td>mation_10</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>urf4_187</td><td>512064</td><td>264330</td><td>—</td><td>—</td><td>1650845</td><td>878249</td><td>1487289</td><td>867091</td><td>0.90</td><td>0.99</td></tr></tbody></table>

g: the number of quantum gates (elementary operations), d: depth of the quantum circuits, — are time-outs and * are data not provided by the Zulehner et al.

<figure><img src="image_21.png" /><figcaption>Figure 16 Routing comparison on ibmqx5, gate count and depth of the routed circuits when counting all gates. The upper charts are a zoomed in version of the initial segment of the lower charts. The results are averaged in bins when the initial count or depth is equal.</figcaption></figure>
## B.2 CX Only Comparison on ibmqx5

<figure><img src="image_22.png" /><figcaption>Figure 17 Routing comparison on ibmqx5, CX count and CX depth when counting only CX gates. The charts are a zoomed in version of the initial segment of upper charts of Fig. 14.</figcaption></figure>

<table><caption>Table 5 CX gates only comparison on ibmqx5.</caption><thead><tr><th rowspan="2">Name</th><th rowspan="2">g<sub>in</sub></th><th rowspan="2">d<sub>in</sub></th><th colspan="2">Qiskit</th><th colspan="2">Project Q</th><th colspan="2">Quilc 1.1.1</th><th colspan="2">CQC's t|ket⟩</th><th colspan="2">t|ket⟩</th></tr><tr><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>r<sub>gate</sub></th><th>r<sub>depth</sub></th></tr></thead><tbody><tr><td>xor5_254</td><td>5</td><td>5</td><td>17</td><td>14</td><td>58</td><td>31</td><td>17</td><td>12</td><td><b>8</b></td><td><b>8</b></td><td>0.47</td><td>0.67</td></tr><tr><td>graycode6_47</td><td>5</td><td>5</td><td><b>5</b></td><td><b>5</b></td><td><b>5</b></td><td><b>5</b></td><td><b>5</b></td><td><b>5</b></td><td><b>5</b></td><td><b>5</b></td><td>1.00</td><td>1.00</td></tr><tr><td>ex1_226</td><td>5</td><td>5</td><td>20</td><td>16</td><td>58</td><td>31</td><td>17</td><td>12</td><td><b>8</b></td><td><b>8</b></td><td>0.47</td><td>0.67</td></tr><tr><td>4gt11_84</td><td>9</td><td>8</td><td>22</td><td>18</td><td>58</td><td>33</td><td>25</td><td>18</td><td><b>18</b></td><td><b>17</b></td><td>0.82</td><td>0.94</td></tr><tr><td>4mod5-v0_20</td><td>10</td><td>9</td><td>22</td><td>19</td><td>43</td><td>28</td><td>20</td><td><b>17</b></td><td><b>19</b></td><td>18</td><td>0.95</td><td>1.06</td></tr><tr><td>ex-1_166</td><td>9</td><td>9</td><td>19</td><td>19</td><td><b>18</b></td><td><b>18</b></td><td>27</td><td>21</td><td><b>18</b></td><td><b>18</b></td><td>1.00</td><td>1.00</td></tr><tr><td>4mod5-v1_22</td><td>11</td><td>10</td><td>29</td><td>27</td><td>60</td><td>41</td><td>29</td><td><b>21</b></td><td><b>23</b></td><td>22</td><td>0.79</td><td>1.05</td></tr><tr><td>mod5d1_63</td><td>13</td><td>11</td><td>37</td><td>29</td><td>48</td><td>36</td><td>40</td><td>28</td><td><b>25</b></td><td><b>22</b></td><td>0.68</td><td>0.79</td></tr><tr><td>ham3_102</td><td>11</td><td>11</td><td>24</td><td>22</td><td>20</td><td>20</td><td>24</td><td>20</td><td><b>18</b></td><td><b>18</b></td><td>0.90</td><td>0.90</td></tr><tr><td>4gt11_83</td><td>14</td><td>14</td><td>36</td><td>30</td><td>71</td><td>38</td><td>34</td><td>28</td><td><b>29</b></td><td><b>26</b></td><td>0.85</td><td>0.93</td></tr><tr><td>4gt11_82</td><td>18</td><td>18</td><td>42</td><td><b>33</b></td><td>91</td><td>50</td><td>43</td><td>34</td><td><b>36</b></td><td><b>33</b></td><td>0.86</td><td>1.00</td></tr><tr><td>rd32-v0_66</td><td>16</td><td>16</td><td>43</td><td>40</td><td>36</td><td>31</td><td>39</td><td>32</td><td><b>24</b></td><td><b>24</b></td><td>0.67</td><td>0.77</td></tr><tr><td>alu-v0_27</td><td>17</td><td>15</td><td>60</td><td>46</td><td>71</td><td>50</td><td>52</td><td>39</td><td><b>38</b></td><td><b>36</b></td><td>0.73</td><td>0.92</td></tr><tr><td>4mod5-v1_24</td><td>16</td><td>15</td><td>53</td><td>44</td><td>78</td><td>51</td><td>46</td><td>38</td><td><b>34</b></td><td><b>33</b></td><td>0.74</td><td>0.87</td></tr><tr><td>4mod5-v0_19</td><td>16</td><td>16</td><td>53</td><td>49</td><td>106</td><td>72</td><td>44</td><td>37</td><td><b>37</b></td><td><b>36</b></td><td>0.84</td><td>0.97</td></tr><tr><td>mod5mils_65</td><td>16</td><td>16</td><td>52</td><td>47</td><td>43</td><td>41</td><td>46</td><td>36</td><td><b>34</b></td><td><b>33</b></td><td>0.79</td><td>0.92</td></tr><tr><td>rd32-v1_68</td><td>16</td><td>16</td><td>47</td><td>40</td><td>36</td><td>31</td><td>36</td><td>29</td><td><b>24</b></td><td><b>24</b></td><td>0.67</td><td>0.83</td></tr><tr><td>alu-v1_28</td><td>18</td><td>16</td><td>52</td><td>44</td><td>42</td><td><b>36</b></td><td>50</td><td>40</td><td><b>39</b></td><td>37</td><td>0.93</td><td>1.03</td></tr><tr><td>alu-v2_33</td><td>17</td><td>15</td><td>53</td><td>45</td><td>72</td><td>51</td><td>52</td><td>39</td><td><b>35</b></td><td><b>33</b></td><td>0.67</td><td>0.85</td></tr><tr><td>alu-v4_37</td><td>18</td><td>16</td><td>51</td><td>43</td><td>49</td><td>43</td><td>53</td><td>40</td><td><b>39</b></td><td><b>37</b></td><td>0.80</td><td>0.93</td></tr><tr><td>alu-v3_35</td><td>18</td><td>16</td><td>55</td><td>45</td><td>49</td><td>43</td><td>54</td><td>40</td><td><b>39</b></td><td><b>37</b></td><td>0.80</td><td>0.93</td></tr><tr><td>3_17_13</td><td>17</td><td>17</td><td>47</td><td>47</td><td>41</td><td>41</td><td>50</td><td>39</td><td><b>35</b></td><td><b>35</b></td><td>0.85</td><td>0.90</td></tr><tr><td>alu-v1_29</td><td>17</td><td>15</td><td>51</td><td>42</td><td>71</td><td>50</td><td>51</td><td>38</td><td><b>38</b></td><td><b>36</b></td><td>0.75</td><td>0.95</td></tr><tr><td>miller_11</td><td>23</td><td>23</td><td>57</td><td>57</td><td>52</td><td>52</td><td>77</td><td>59</td><td><b>50</b></td><td><b>50</b></td><td>0.96</td><td>0.96</td></tr><tr><td>alu-v3_34</td><td>24</td><td>23</td><td>81</td><td>71</td><td>156</td><td>96</td><td>73</td><td>62</td><td><b>57</b></td><td><b>56</b></td><td>0.78</td><td>0.90</td></tr></tbody></table>
<table><thead><tr><th rowspan="2">Name</th><th rowspan="2">g<sub>in</sub></th><th rowspan="2">d<sub>in</sub></th><th colspan="2">Qiskit</th><th colspan="2">Project Q</th><th colspan="2">Quilc 1.1.1</th><th colspan="2">CQC's t|ket</th><th colspan="2">t|ket</th></tr><tr><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>r<sub>gate</sub></th><th>r<sub>depth</sub></th></tr></thead><tbody><tr><td>decod24-v2_43</td><td>22</td><td>22</td><td>73</td><td>65</td><td>81</td><td>67</td><td>63</td><td>53</td><td><b>49</b></td><td><b>49</b></td><td>0.78</td><td>0.92</td></tr><tr><td>decod24-v0_38</td><td>23</td><td>23</td><td>62</td><td>56</td><td>88</td><td>65</td><td>66</td><td>52</td><td><b>48</b></td><td><b>48</b></td><td>0.77</td><td>0.92</td></tr><tr><td>mod5d2_64</td><td>25</td><td>25</td><td>70</td><td>61</td><td>179</td><td>104</td><td>63</td><td><b>55</b></td><td><b>61</b></td><td>60</td><td>0.97</td><td>1.09</td></tr><tr><td>4gt13_92</td><td>30</td><td>26</td><td>98</td><td>85</td><td>177</td><td>110</td><td>86</td><td>69</td><td><b>66</b></td><td><b>64</b></td><td>0.77</td><td>0.93</td></tr><tr><td>4gt13-v1_93</td><td>30</td><td>27</td><td>104</td><td>89</td><td>185</td><td>109</td><td>79</td><td>61</td><td><b>60</b></td><td><b>57</b></td><td>0.76</td><td>0.93</td></tr><tr><td>4mod5-v0_18</td><td>31</td><td>31</td><td>103</td><td>90</td><td>158</td><td>109</td><td>91</td><td>70</td><td><b>70</b></td><td><b>68</b></td><td>0.77</td><td>0.97</td></tr><tr><td>decod24-bdd_294</td><td>32</td><td>31</td><td>97</td><td>79</td><td>170</td><td>105</td><td>98</td><td>77</td><td><b>77</b></td><td><b>71</b></td><td>0.79</td><td>0.92</td></tr><tr><td>one-two-three-v2_100</td><td>32</td><td>29</td><td>96</td><td>83</td><td>191</td><td>116</td><td><b>69</b></td><td><b>62</b></td><td>71</td><td>71</td><td>1.03</td><td>1.15</td></tr><tr><td>one-two-three-v3_101</td><td>32</td><td>29</td><td>102</td><td>91</td><td>182</td><td>116</td><td>78</td><td><b>68</b></td><td><b>72</b></td><td>69</td><td>0.92</td><td>1.01</td></tr><tr><td>4mod5-v1_23</td><td>32</td><td>30</td><td>106</td><td>86</td><td>178</td><td>106</td><td>102</td><td>79</td><td><b>74</b></td><td><b>73</b></td><td>0.73</td><td>0.92</td></tr><tr><td>4mod5-bdd_287</td><td>31</td><td>31</td><td>106</td><td>83</td><td>170</td><td>115</td><td>100</td><td>76</td><td><b>82</b></td><td><b>75</b></td><td>0.82</td><td>0.99</td></tr><tr><td>rd32_270</td><td>36</td><td>35</td><td>109</td><td>92</td><td>210</td><td>124</td><td>101</td><td><b>82</b></td><td><b>84</b></td><td><b>82</b></td><td>0.83</td><td>1.00</td></tr><tr><td>4gt5_75</td><td>38</td><td>33</td><td>121</td><td>98</td><td>223</td><td>135</td><td>116</td><td>83</td><td><b>83</b></td><td><b>77</b></td><td>0.72</td><td>0.93</td></tr><tr><td>alu-bdd_288</td><td>38</td><td>35</td><td>122</td><td>96</td><td>206</td><td>140</td><td>124</td><td>90</td><td><b>95</b></td><td><b>88</b></td><td>0.78</td><td>0.98</td></tr><tr><td>alu-v0_26</td><td>38</td><td>35</td><td>125</td><td>103</td><td>224</td><td>135</td><td>115</td><td>80</td><td><b>83</b></td><td><b>78</b></td><td>0.72</td><td>0.97</td></tr><tr><td>decod24-v1_41</td><td>38</td><td>35</td><td>133</td><td>106</td><td>225</td><td>150</td><td>118</td><td>93</td><td><b>83</b></td><td><b>76</b></td><td>0.70</td><td>0.82</td></tr><tr><td>rd53_138</td><td>60</td><td>42</td><td>242</td><td>146</td><td>460</td><td>193</td><td>170</td><td><b>104</b></td><td><b>156</b></td><td>118</td><td>0.92</td><td>1.13</td></tr><tr><td>4gt5_76</td><td>46</td><td>42</td><td>135</td><td>107</td><td>257</td><td>172</td><td>112</td><td><b>79</b></td><td><b>97</b></td><td>92</td><td>0.87</td><td>1.16</td></tr><tr><td>4gt13_91</td><td>49</td><td>46</td><td>154</td><td>126</td><td>309</td><td>178</td><td>131</td><td><b>100</b></td><td><b>106</b></td><td>101</td><td>0.81</td><td>1.01</td></tr><tr><td>cnt3-5_179</td><td>85</td><td>43</td><td>260</td><td>153</td><td>450</td><td>215</td><td><b>216</b></td><td><b>121</b></td><td>219</td><td><b>121</b></td><td>1.01</td><td>1.00</td></tr><tr><td>qft_10</td><td>90</td><td>34</td><td>273</td><td>123</td><td>432</td><td>167</td><td><b>129</b></td><td><b>45</b></td><td>147</td><td>85</td><td>1.14</td><td>1.89</td></tr><tr><td>4gt13_90</td><td>53</td><td>50</td><td>158</td><td>135</td><td>372</td><td>210</td><td>144</td><td><b>106</b></td><td><b>113</b></td><td>108</td><td>0.78</td><td>1.02</td></tr><tr><td>alu-v4_36</td><td>51</td><td>47</td><td>154</td><td>125</td><td>303</td><td>190</td><td>136</td><td>110</td><td><b>106</b></td><td><b>101</b></td><td>0.78</td><td>0.92</td></tr><tr><td>mini_alu_305</td><td>77</td><td>53</td><td>320</td><td>176</td><td>410</td><td>201</td><td>-</td><td>-</td><td><b>196</b></td><td><b>134</b></td><td>0.61</td><td>0.76</td></tr><tr><td>ising_model_10</td><td>90</td><td>20</td><td><b>90</b></td><td><b>20</b></td><td><b>90</b></td><td><b>20</b></td><td><b>90</b></td><td><b>20</b></td><td><b>90</b></td><td><b>20</b></td><td>1.00</td><td>1.00</td></tr><tr><td>ising_model_16</td><td>150</td><td>20</td><td><b>150</b></td><td><b>20</b></td><td><b>150</b></td><td><b>20</b></td><td><b>150</b></td><td><b>20</b></td><td><b>150</b></td><td><b>20</b></td><td>1.00</td><td>1.00</td></tr><tr><td>ising_model_13</td><td>120</td><td>20</td><td><b>120</b></td><td><b>20</b></td><td><b>120</b></td><td><b>20</b></td><td><b>120</b></td><td><b>20</b></td><td>144</td><td>58</td><td>1.20</td><td>2.90</td></tr><tr><td>4gt5_77</td><td>58</td><td>51</td><td>165</td><td>143</td><td>371</td><td>239</td><td>158</td><td><b>121</b></td><td><b>136</b></td><td>125</td><td>0.86</td><td>1.03</td></tr><tr><td>sys6-v0_111</td><td>98</td><td>55</td><td>369</td><td>204</td><td>691</td><td>274</td><td>279</td><td><b>137</b></td><td><b>254</b></td><td>147</td><td>0.91</td><td>1.07</td></tr><tr><td>one-two-three-v1_99</td><td>59</td><td>56</td><td>187</td><td>163</td><td>314</td><td>205</td><td>174</td><td>135</td><td><b>131</b></td><td><b>128</b></td><td>0.75</td><td>0.95</td></tr><tr><td>one-two-three-v0_98</td><td>65</td><td>59</td><td>207</td><td>182</td><td>324</td><td>229</td><td>192</td><td>145</td><td><b>146</b></td><td><b>140</b></td><td>0.76</td><td>0.97</td></tr><tr><td>decod24-v3_45</td><td>64</td><td>57</td><td>208</td><td>178</td><td>422</td><td>264</td><td>177</td><td>146</td><td><b>139</b></td><td><b>133</b></td><td>0.79</td><td>0.91</td></tr><tr><td>4gt10-v1_81</td><td>66</td><td>60</td><td>215</td><td>174</td><td>426</td><td>250</td><td>179</td><td><b>138</b></td><td><b>144</b></td><td><b>138</b></td><td>0.80</td><td>1.00</td></tr><tr><td>aj-e11_165</td><td>69</td><td>63</td><td>205</td><td>168</td><td>354</td><td>252</td><td>190</td><td><b>141</b></td><td><b>153</b></td><td>144</td><td>0.81</td><td>1.02</td></tr><tr><td>4mod7-v0_94</td><td>72</td><td>66</td><td>239</td><td>205</td><td>372</td><td>228</td><td>217</td><td>160</td><td><b>162</b></td><td><b>157</b></td><td>0.75</td><td>0.98</td></tr><tr><td>alu-v2_32</td><td>72</td><td>64</td><td>225</td><td>191</td><td>416</td><td>269</td><td>211</td><td><b>157</b></td><td><b>165</b></td><td><b>157</b></td><td>0.78</td><td>1.00</td></tr><tr><td>rd73_140</td><td>104</td><td>68</td><td>384</td><td>228</td><td>640</td><td>302</td><td>304</td><td><b>170</b></td><td><b>257</b></td><td>182</td><td>0.85</td><td>1.07</td></tr><tr><td>4mod7-v1_96</td><td>72</td><td>65</td><td>234</td><td>192</td><td>458</td><td>299</td><td>205</td><td>162</td><td><b>160</b></td><td><b>155</b></td><td>0.78</td><td>0.96</td></tr><tr><td>4gt4-v0_80</td><td>79</td><td>71</td><td>268</td><td>207</td><td>572</td><td>300</td><td>218</td><td><b>162</b></td><td><b>178</b></td><td>166</td><td>0.82</td><td>1.02</td></tr><tr><td>mod10_176</td><td>78</td><td>70</td><td>257</td><td>211</td><td>541</td><td>309</td><td>238</td><td>175</td><td><b>174</b></td><td><b>163</b></td><td>0.73</td><td>0.93</td></tr><tr><td>0410184_169</td><td>104</td><td>70</td><td>323</td><td>221</td><td>828</td><td>387</td><td>293</td><td><b>171</b></td><td><b>284</b></td><td>190</td><td>0.97</td><td>1.11</td></tr><tr><td>qft_16</td><td>240</td><td>58</td><td>835</td><td>298</td><td>900</td><td>265</td><td><b>369</b></td><td><b>111</b></td><td>504</td><td>244</td><td>1.37</td><td>2.20</td></tr></tbody></table>
5:26 On the Qubit Routing Problem

<table><thead><tr><th rowspan="2">Name</th><th rowspan="2">g<sub>in</sub></th><th rowspan="2">d<sub>in</sub></th><th colspan="2">Qiskit</th><th colspan="2">Project Q</th><th colspan="2">Quilc 1.1.1</th><th colspan="2">CQC's t|ket⟩</th><th colspan="2">t|ket⟩</th></tr><tr><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>r<sub>gate</sub></th><th>r<sub>depth</sub></th></tr></thead><tbody><tr><td>4gt12-v0_88</td><td>86</td><td>77</td><td>291</td><td>232</td><td>599</td><td>335</td><td>231</td><td>182</td><td><b>188</b></td><td><b>180</b></td><td>0.81</td><td>0.99</td></tr><tr><td>rd84_142</td><td>154</td><td>81</td><td>629</td><td>303</td><td>869</td><td>370</td><td><b>410</b></td><td><b>228</b></td><td>442</td><td>277</td><td>1.08</td><td>1.21</td></tr><tr><td>rd53_311</td><td>124</td><td>92</td><td>519</td><td>314</td><td>871</td><td>443</td><td>390</td><td><b>246</b></td><td><b>370</b></td><td>252</td><td>0.95</td><td>1.02</td></tr><tr><td>4_49_16</td><td>99</td><td>91</td><td>300</td><td>256</td><td>536</td><td>353</td><td>262</td><td><b>208</b></td><td><b>226</b></td><td>217</td><td>0.86</td><td>1.04</td></tr><tr><td>sym9_146</td><td>148</td><td>91</td><td>604</td><td>355</td><td>780</td><td>385</td><td>410</td><td><b>229</b></td><td><b>382</b></td><td>251</td><td>0.93</td><td>1.10</td></tr><tr><td>4gt12-v1_89</td><td>100</td><td>88</td><td>325</td><td>257</td><td>756</td><td>428</td><td>277</td><td><b>210</b></td><td><b>229</b></td><td>214</td><td>0.83</td><td>1.02</td></tr><tr><td>4gt12-v0_87</td><td>112</td><td>94</td><td>345</td><td>266</td><td>772</td><td>440</td><td>298</td><td><b>248</b></td><td><b>221</b></td><td>0.83</td><td>0.98</td></tr><tr><td>4gt4-v0_79</td><td>105</td><td>94</td><td>341</td><td>278</td><td>708</td><td>439</td><td>274</td><td><b>236</b></td><td><b>222</b></td><td>0.86</td><td>1.00</td></tr><tr><td>hwb4_49</td><td>107</td><td>99</td><td>348</td><td>294</td><td>553</td><td>348</td><td>302</td><td><b>231</b></td><td><b>220</b></td><td>0.76</td><td>0.96</td></tr><tr><td>sym6_316</td><td>123</td><td>98</td><td>522</td><td>343</td><td>738</td><td>396</td><td>392</td><td><b>254</b></td><td><b>337</b></td><td>259</td><td>0.86</td><td>1.02</td></tr><tr><td>4gt12-v0_86</td><td>116</td><td>98</td><td>371</td><td>284</td><td>820</td><td>460</td><td>283</td><td><b>227</b></td><td><b>258</b></td><td>231</td><td>0.91</td><td>1.02</td></tr><tr><td>4gt4-v0_72</td><td>113</td><td>95</td><td>340</td><td>265</td><td>858</td><td>466</td><td>295</td><td><b>220</b></td><td><b>251</b></td><td>224</td><td>0.85</td><td>1.02</td></tr><tr><td>4gt4-v0_78</td><td>109</td><td>99</td><td>353</td><td>271</td><td>713</td><td>447</td><td>328</td><td><b>243</b></td><td><b>229</b></td><td>0.74</td><td>0.97</td></tr><tr><td>mod10_171</td><td>108</td><td>97</td><td>323</td><td>272</td><td>753</td><td>425</td><td>301</td><td><b>226</b></td><td><b>240</b></td><td>229</td><td>0.80</td><td>1.01</td></tr><tr><td>4gt4-v1_74</td><td>119</td><td>108</td><td>375</td><td>312</td><td>937</td><td>522</td><td>367</td><td><b>278</b></td><td><b>258</b></td><td>0.76</td><td>0.97</td></tr><tr><td>rd53_135</td><td>134</td><td>114</td><td>434</td><td>338</td><td>918</td><td>507</td><td>424</td><td><b>290</b></td><td><b>323</b></td><td>297</td><td>0.76</td><td>1.02</td></tr><tr><td>mini-alu_167</td><td>126</td><td>111</td><td>357</td><td>311</td><td>925</td><td>536</td><td>338</td><td><b>262</b></td><td><b>282</b></td><td>264</td><td>0.83</td><td>1.01</td></tr><tr><td>one-two-three-v0_97</td><td>128</td><td>116</td><td>397</td><td>335</td><td>812</td><td>474</td><td>380</td><td><b>287</b></td><td><b>270</b></td><td>0.76</td><td>0.96</td></tr><tr><td>ham7_104</td><td>149</td><td>134</td><td>506</td><td>393</td><td>954</td><td>562</td><td>397</td><td><b>343</b></td><td><b>312</b></td><td>0.86</td><td>0.99</td></tr><tr><td>decod24-enable_126</td><td>149</td><td>134</td><td>472</td><td>397</td><td>908</td><td>553</td><td>428</td><td><b>341</b></td><td><b>322</b></td><td>0.80</td><td>1.00</td></tr><tr><td>mod8-10_178</td><td>152</td><td>135</td><td>510</td><td>400</td><td>1030</td><td>605</td><td>449</td><td><b>338</b></td><td><b>315</b></td><td>0.75</td><td>0.95</td></tr><tr><td>cnt3-5_180</td><td>215</td><td>148</td><td>683</td><td>451</td><td>1327</td><td>691</td><td><b>585</b></td><td><b>390</b></td><td>601</td><td>461</td><td>1.03</td><td>1.18</td></tr><tr><td>ex3_229</td><td>175</td><td>157</td><td>588</td><td>470</td><td>1269</td><td>718</td><td>539</td><td><b>403</b></td><td><b>371</b></td><td>0.75</td><td>0.95</td></tr><tr><td>4gt4-v0_73</td><td>179</td><td>160</td><td>535</td><td>445</td><td>1180</td><td>690</td><td>470</td><td><b>370</b></td><td><b>401</b></td><td>376</td><td>0.85</td><td>1.02</td></tr><tr><td>mod8-10_177</td><td>196</td><td>178</td><td>573</td><td>498</td><td>1354</td><td>775</td><td>563</td><td><b>448</b></td><td><b>418</b></td><td>0.80</td><td>0.99</td></tr><tr><td>C17_204</td><td>205</td><td>173</td><td>673</td><td>523</td><td>1892</td><td>891</td><td>614</td><td><b>447</b></td><td><b>502</b></td><td>454</td><td>0.82</td><td>1.02</td></tr><tr><td>alu-v2_31</td><td>198</td><td>172</td><td>564</td><td>476</td><td>1350</td><td>816</td><td>547</td><td><b>406</b></td><td><b>438</b></td><td>413</td><td>0.80</td><td>1.02</td></tr><tr><td>rd53_131</td><td>200</td><td>175</td><td>701</td><td>554</td><td>1230</td><td>749</td><td>624</td><td><b>421</b></td><td><b>474</b></td><td>432</td><td>0.76</td><td>1.03</td></tr><tr><td>alu-v2_30</td><td>223</td><td>199</td><td>664</td><td>546</td><td>1595</td><td>878</td><td>682</td><td><b>502</b></td><td><b>472</b></td><td>0.76</td><td>0.96</td></tr><tr><td>mod5adder_127</td><td>239</td><td>208</td><td>793</td><td>633</td><td>1705</td><td>1022</td><td>702</td><td><b>533</b></td><td><b>499</b></td><td>0.76</td><td>0.95</td></tr><tr><td>rd53_133</td><td>256</td><td>221</td><td>805</td><td>640</td><td>1703</td><td>977</td><td>739</td><td><b>543</b></td><td><b>615</b></td><td>554</td><td>0.83</td><td>1.02</td></tr><tr><td>cm82a_208</td><td>283</td><td>234</td><td>1003</td><td>724</td><td>2092</td><td>1081</td><td>848</td><td><b>665</b></td><td><b>576</b></td><td>0.78</td><td>0.99</td></tr><tr><td>majority_239</td><td>267</td><td>232</td><td>932</td><td>704</td><td>1985</td><td>1102</td><td>805</td><td><b>624</b></td><td><b>568</b></td><td>0.78</td><td>0.98</td></tr><tr><td>ex2_227</td><td>275</td><td>241</td><td>965</td><td>737</td><td>1907</td><td>1107</td><td>789</td><td><b>584</b></td><td><b>656</b></td><td>603</td><td>0.83</td><td>1.03</td></tr><tr><td>sf_276</td><td>336</td><td>301</td><td>1104</td><td>902</td><td>2083</td><td>1290</td><td>935</td><td><b>743</b></td><td><b>762</b></td><td><b>727</b></td><td>0.81</td><td>0.98</td></tr><tr><td>sf_274</td><td>336</td><td>300</td><td>1095</td><td>878</td><td>2145</td><td>1287</td><td>922</td><td><b>686</b></td><td><b>757</b></td><td>725</td><td>0.82</td><td>1.06</td></tr><tr><td>con1_216</td><td>415</td><td>346</td><td>1454</td><td>1078</td><td>3593</td><td>1872</td><td>1288</td><td><b>891</b></td><td><b>1075</b></td><td>940</td><td>0.83</td><td>1.05</td></tr><tr><td>wim_266</td><td>427</td><td>352</td><td>1432</td><td>1058</td><td>3482</td><td>1823</td><td>1209</td><td><b>870</b></td><td><b>1089</b></td><td>951</td><td>0.90</td><td>1.09</td></tr><tr><td>rd53_130</td><td>448</td><td>383</td><td>1430</td><td>1132</td><td>3563</td><td>1905</td><td>1300</td><td><b>930</b></td><td><b>1099</b></td><td>976</td><td>0.85</td><td>1.05</td></tr><tr><td>f2_232</td><td>525</td><td>449</td><td>1796</td><td>1364</td><td>4409</td><td>2187</td><td>1563</td><td><b>1154</b></td><td><b>1309</b></td><td>1205</td><td>0.84</td><td>1.04</td></tr><tr><td>cm152a_212</td><td>532</td><td>461</td><td>1813</td><td>1374</td><td>5455</td><td>2557</td><td>1510</td><td><b>1078</b></td><td><b>1364</b></td><td>1221</td><td>0.90</td><td>1.13</td></tr><tr><td>rd53_251</td><td>564</td><td>492</td><td>1851</td><td>1474</td><td>5391</td><td>2555</td><td>1629</td><td><b>1221</b></td><td><b>1405</b></td><td>1268</td><td>0.86</td><td>1.04</td></tr><tr><td>hwb5_53</td><td>598</td><td>535</td><td>1850</td><td>1525</td><td>6201</td><td>2717</td><td>1713</td><td><b>1320</b></td><td><b>1360</b></td><td><b>1276</b></td><td>0.79</td><td>0.97</td></tr><tr><td>cm42a_207</td><td>771</td><td>634</td><td>2607</td><td>1926</td><td>8818</td><td>3910</td><td>2284</td><td><b>1600</b></td><td><b>1920</b></td><td>1691</td><td>0.84</td><td>1.06</td></tr></tbody></table>
<table><thead><tr><th rowspan="2">Name</th><th rowspan="2">g<sub>in</sub></th><th rowspan="2">d<sub>in</sub></th><th colspan="2">Qiskit</th><th colspan="2">Project Q</th><th colspan="2">Quilc 1.1.1</th><th colspan="2">CQC's t|ket</th><th colspan="2">t|ket</th></tr><tr><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>r<sub>gate</sub></th><th>r<sub>depth</sub></th></tr></thead><tbody><tr><td>pm1_249</td><td>771</td><td>634</td><td>2713</td><td>2043</td><td>8818</td><td>3910</td><td>2220</td><td>1555</td><td>1920</td><td>1691</td><td>0.86</td><td>1.09</td></tr><tr><td>dc1_220</td><td>833</td><td>705</td><td>2895</td><td>2194</td><td>11741</td><td>4784</td><td>2351</td><td>1690</td><td>2077</td><td>1770</td><td>0.88</td><td>1.05</td></tr><tr><td>squar5_261</td><td>869</td><td>720</td><td>3015</td><td>2189</td><td>10135</td><td>4466</td><td>2676</td><td>1845</td><td>2358</td><td>1954</td><td>0.88</td><td>1.06</td></tr><tr><td>z4_268</td><td>1343</td><td>1112</td><td>4744</td><td>3473</td><td>22664</td><td>8032</td><td>4104</td><td>2870</td><td>3583</td><td>3059</td><td>0.87</td><td>1.07</td></tr><tr><td>sqrt8_260</td><td>1314</td><td>1121</td><td>4853</td><td>3633</td><td>22130</td><td>8209</td><td>4107</td><td>2937</td><td>3416</td><td>2985</td><td>0.83</td><td>1.02</td></tr><tr><td>radd_250</td><td>1405</td><td>1210</td><td>4952</td><td>3782</td><td>23920</td><td>8909</td><td>4290</td><td>3027</td><td>3768</td><td>3281</td><td>0.88</td><td>1.08</td></tr><tr><td>adr4_197</td><td>1498</td><td>1249</td><td>5284</td><td>3883</td><td>22303</td><td>8649</td><td>4538</td><td>3142</td><td>3871</td><td>3279</td><td>0.85</td><td>1.04</td></tr><tr><td>sym6_145</td><td>1701</td><td>1499</td><td>5356</td><td>4324</td><td>40194</td><td>11879</td><td>4910</td><td>3675</td><td>4170</td><td>3820</td><td>0.85</td><td>1.04</td></tr><tr><td>misex1_241</td><td>2100</td><td>1797</td><td>-</td><td>-</td><td>20756</td><td>10450</td><td>5798</td><td>4367</td><td>5578</td><td>4941</td><td>0.96</td><td>1.13</td></tr><tr><td>rd73_252</td><td>2319</td><td>1963</td><td>-</td><td>-</td><td>45433</td><td>15172</td><td>-</td><td>-</td><td>6007</td><td>5173</td><td>0.13</td><td>0.34</td></tr><tr><td>cycle10_2_110</td><td>2648</td><td>2276</td><td>-</td><td>-</td><td>50777</td><td>17976</td><td>-</td><td>-</td><td>7084</td><td>6316</td><td>0.14</td><td>0.35</td></tr><tr><td>hwb6_56</td><td>2952</td><td>2559</td><td>-</td><td>-</td><td>72955</td><td>21358</td><td>-</td><td>-</td><td>7125</td><td>6496</td><td>0.10</td><td>0.30</td></tr><tr><td>square_root_7</td><td>3089</td><td>2520</td><td>-</td><td>-</td><td>37275</td><td>16316</td><td>-</td><td>-</td><td>8928</td><td>7401</td><td>0.24</td><td>0.45</td></tr><tr><td>ham15_107</td><td>3858</td><td>3273</td><td>-</td><td>-</td><td>46860</td><td>21421</td><td>-</td><td>-</td><td>10206</td><td>8884</td><td>0.22</td><td>0.41</td></tr><tr><td>dc2_222</td><td>4131</td><td>3518</td><td>-</td><td>-</td><td>45200</td><td>21119</td><td>-</td><td>-</td><td>11545</td><td>10210</td><td>0.26</td><td>0.48</td></tr><tr><td>sqn_258</td><td>4459</td><td>3719</td><td>-</td><td>-</td><td>93394</td><td>29983</td><td>-</td><td>-</td><td>11425</td><td>9743</td><td>0.12</td><td>0.32</td></tr><tr><td>inc_237</td><td>4636</td><td>3928</td><td>-</td><td>-</td><td>39432</td><td>21180</td><td>-</td><td>-</td><td>12381</td><td>10872</td><td>0.31</td><td>0.51</td></tr><tr><td>cm85a_209</td><td>4986</td><td>4256</td><td>-</td><td>-</td><td>71744</td><td>29352</td><td>-</td><td>-</td><td>13297</td><td>11722</td><td>0.19</td><td>0.40</td></tr><tr><td>rd84_253</td><td>5960</td><td>4917</td><td>-</td><td>-</td><td>118473</td><td>40259</td><td>-</td><td>-</td><td>16027</td><td>13432</td><td>0.14</td><td>0.33</td></tr><tr><td>co14_215</td><td>7840</td><td>5759</td><td>-</td><td>-</td><td>84431</td><td>36897</td><td>-</td><td>-</td><td>22357</td><td>17144</td><td>0.26</td><td>0.46</td></tr><tr><td>root_255</td><td>7493</td><td>5965</td><td>-</td><td>-</td><td>128324</td><td>47123</td><td>-</td><td>-</td><td>20332</td><td>16951</td><td>0.16</td><td>0.36</td></tr><tr><td>mlp4_245</td><td>8232</td><td>6930</td><td>-</td><td>-</td><td>50107</td><td>31076</td><td>-</td><td>-</td><td>22759</td><td>19640</td><td>0.45</td><td>0.63</td></tr><tr><td>urf2_277</td><td>10066</td><td>8312</td><td>-</td><td>-</td><td>243218</td><td>71917</td><td>-</td><td>-</td><td>25127</td><td>21186</td><td>0.10</td><td>0.29</td></tr><tr><td>sym9_148</td><td>9408</td><td>8062</td><td>-</td><td>-</td><td>241725</td><td>73636</td><td>-</td><td>-</td><td>23489</td><td>20883</td><td>0.10</td><td>0.28</td></tr><tr><td>life_238</td><td>9800</td><td>8356</td><td>-</td><td>-</td><td>221220</td><td>72011</td><td>-</td><td>-</td><td>26064</td><td>22788</td><td>0.12</td><td>0.32</td></tr><tr><td>hwb7_59</td><td>10681</td><td>9112</td><td>-</td><td>-</td><td>264057</td><td>78857</td><td>-</td><td>-</td><td>26033</td><td>23163</td><td>0.10</td><td>0.29</td></tr><tr><td>max46_240</td><td>11844</td><td>9657</td><td>-</td><td>-</td><td>269243</td><td>84007</td><td>-</td><td>-</td><td>30709</td><td>25891</td><td>0.11</td><td>0.31</td></tr><tr><td>clip_206</td><td>14772</td><td>12028</td><td>-</td><td>-</td><td>213901</td><td>85381</td><td>-</td><td>-</td><td>40504</td><td>34045</td><td>0.19</td><td>0.40</td></tr><tr><td>9symml_195</td><td>15232</td><td>12849</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>40897</td><td>35349</td><td></td><td></td></tr><tr><td>sym9_193</td><td>15232</td><td>12849</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>40897</td><td>35349</td><td></td><td></td></tr><tr><td>sao2_257</td><td>16864</td><td>13209</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>46536</td><td>37963</td><td></td><td></td></tr><tr><td>dist_223</td><td>16624</td><td>13274</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>45230</td><td>37762</td><td></td><td></td></tr><tr><td>urf5_280</td><td>23764</td><td>19888</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>60233</td><td>51479</td><td></td><td></td></tr><tr><td>urf1_278</td><td>26692</td><td>22307</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>69370</td><td>58597</td><td></td><td></td></tr><tr><td>sym10_262</td><td>28084</td><td>23736</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>76180</td><td>65905</td><td></td><td></td></tr><tr><td>hwb8_113</td><td>30372</td><td>26041</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>77247</td><td>68560</td><td></td><td></td></tr><tr><td>urf2_152</td><td>35210</td><td>32247</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>84345</td><td>77320</td><td></td><td></td></tr><tr><td>urf3_279</td><td>60380</td><td>50568</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>158115</td><td>132770</td><td></td><td></td></tr><tr><td>plus63mod4096_16356329</td><td>48265</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>155209</td><td>135715</td><td></td><td></td></tr><tr><td>urf5_158</td><td>71932</td><td>64750</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>177757</td><td>158774</td><td></td><td></td></tr><tr><td>urf6_160</td><td>75180</td><td>67637</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>209231</td><td>174548</td><td></td><td></td></tr><tr><td>urf1_149</td><td>80878</td><td>72933</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>200949</td><td>179071</td><td></td><td></td></tr><tr><td>plus63mod8192_16481865</td><td>70222</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>226354</td><td>198162</td><td></td><td></td></tr><tr><td>hwb9_119</td><td>90955</td><td>77968</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>233049</td><td>205682</td><td></td><td></td></tr><tr><td>urf3_155</td><td>185276</td><td>167215</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>463538</td><td>409727</td><td></td><td></td></tr></tbody></table>
5:28 On the Qubit Routing Problem

<table><thead><tr><th rowspan="2">Name</th><th rowspan="2">g<sub>in</sub></th><th rowspan="2">d<sub>in</sub></th><th colspan="2">Qiskit</th><th colspan="2">Project Q</th><th colspan="2">Quilc 1.1.1</th><th colspan="2">CQC's t|ket⟩</th><th colspan="2">t|ket⟩</th></tr><tr><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>r<sub>gate</sub></th><th>r<sub>depth</sub></th></tr></thead><tbody><tr><td>ground_state _es-154209 151095</td><td></td><td></td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>5039</td><td>3897</td><td></td><td></td></tr><tr><td>timation_10</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>urf4_187</td><td>224028</td><td>185975</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>568938</td><td>481368</td><td></td><td></td></tr></tbody></table>

g: the number of quantum gates (elementary operations),

d: depth of the quantum circuits and – are time-outs

B.3 CX Only Comparison on IBM Tokyo

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /><figcaption>Figure 18 Routing comparison on IBM Tokyo, CX count and CX depth when counting only CX gates. The charts are a zoomed in version of the initial segment of lower charts of Fig. 14.</figcaption></figure>

<table><caption>Table 6 CX gates only comparison on IBM Tokyo.</caption><thead><tr><th rowspan="2">Name</th><th rowspan="2">g<sub>in</sub></th><th rowspan="2">d<sub>in</sub></th><th colspan="2">Qiskit</th><th colspan="2">Quilc 1.1.1</th><th colspan="2">CQC's t|ket⟩</th><th colspan="2">t|ket⟩</th></tr><tr><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>r<sub>gate</sub></th><th>r<sub>depth</sub></th></tr></thead><tbody><tr><td>xor5_254</td><td>5</td><td>5</td><td>14</td><td>11</td><td>7</td><td>7</td><td>5</td><td>5</td><td>0.71</td><td>0.71</td></tr><tr><td>graycode6_47</td><td>5</td><td>5</td><td>17</td><td>11</td><td>5</td><td>5</td><td>5</td><td>5</td><td>1.00</td><td>1.00</td></tr><tr><td>ex1_226</td><td>5</td><td>5</td><td>18</td><td>12</td><td>7</td><td>7</td><td>5</td><td>5</td><td>0.71</td><td>0.71</td></tr><tr><td>4gt11_84</td><td>9</td><td>8</td><td>27</td><td>24</td><td>15</td><td>14</td><td>9</td><td>8</td><td>0.60</td><td>0.57</td></tr><tr><td>4mod5-v0_20</td><td>10</td><td>9</td><td>25</td><td>19</td><td>16</td><td>15</td><td>19</td><td>18</td><td>1.19</td><td>1.20</td></tr><tr><td>ex-1_166</td><td>9</td><td>9</td><td>28</td><td>25</td><td>18</td><td>15</td><td>9</td><td>9</td><td>0.50</td><td>0.60</td></tr><tr><td>4mod5-v1_22</td><td>11</td><td>10</td><td>26</td><td>25</td><td>20</td><td>18</td><td>23</td><td>22</td><td>1.15</td><td>1.22</td></tr><tr><td>mod5d1_63</td><td>13</td><td>11</td><td>43</td><td>31</td><td>28</td><td>23</td><td>13</td><td>11</td><td>0.46</td><td>0.48</td></tr><tr><td>ham3_102</td><td>11</td><td>11</td><td>25</td><td>25</td><td>18</td><td>15</td><td>9</td><td>9</td><td>0.50</td><td>0.60</td></tr><tr><td>4gt11_83</td><td>14</td><td>14</td><td>41</td><td>32</td><td>20</td><td>20</td><td>17</td><td>16</td><td>0.85</td><td>0.80</td></tr><tr><td>4gt11_82</td><td>18</td><td>18</td><td>49</td><td>34</td><td>30</td><td>27</td><td>24</td><td>23</td><td>0.80</td><td>0.85</td></tr><tr><td>rd32-v0_66</td><td>16</td><td>16</td><td>57</td><td>43</td><td>21</td><td>20</td><td>12</td><td>12</td><td>0.57</td><td>0.60</td></tr><tr><td>alu-v0_27</td><td>17</td><td>15</td><td>63</td><td>48</td><td>53</td><td>34</td><td>20</td><td>19</td><td>0.38</td><td>0.56</td></tr><tr><td>4mod5-v1_24</td><td>16</td><td>15</td><td>66</td><td>49</td><td>28</td><td>27</td><td>16</td><td>15</td><td>0.57</td><td>0.56</td></tr><tr><td>4mod5-v0_19</td><td>16</td><td>16</td><td>67</td><td>51</td><td>25</td><td>25</td><td>25</td><td>25</td><td>1.00</td><td>1.00</td></tr></tbody></table>
<table><thead><tr><th rowspan="2">Name</th><th rowspan="2">g<sub>in</sub></th><th rowspan="2">d<sub>in</sub></th><th colspan="2">Qiskit 0.7.0</th><th colspan="2">Quilc 1.1.1<br>Pyquil 2.1.1</th><th colspan="2">CQC's t|ket⟩</th><th colspan="2">t|ket⟩<br>comparison</th></tr><tr><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>r<sub>gate</sub></th><th>r<sub>depth</sub></th></tr></thead><tbody><tr><td>mod5mils_65</td><td>16</td><td>16</td><td>71</td><td>48</td><td>28</td><td>28</td><td><b>25</b></td><td><b>25</b></td><td>0.89</td><td>0.89</td></tr><tr><td>rd32-v1_68</td><td>16</td><td>16</td><td>53</td><td>45</td><td>24</td><td>17</td><td><b>12</b></td><td><b>12</b></td><td>0.50</td><td>0.71</td></tr><tr><td>alu-v1_28</td><td>18</td><td>16</td><td>60</td><td>35</td><td>40</td><td>26</td><td><b>21</b></td><td><b>20</b></td><td>0.53</td><td>0.77</td></tr><tr><td>alu-v2_33</td><td>17</td><td>15</td><td>59</td><td>44</td><td>29</td><td>28</td><td><b>20</b></td><td><b>19</b></td><td>0.69</td><td>0.68</td></tr><tr><td>alu-v4_37</td><td>18</td><td>16</td><td>67</td><td>45</td><td>52</td><td>33</td><td><b>21</b></td><td><b>20</b></td><td>0.40</td><td>0.61</td></tr><tr><td>alu-v3_35</td><td>18</td><td>16</td><td>57</td><td>43</td><td>52</td><td>33</td><td><b>21</b></td><td><b>20</b></td><td>0.40</td><td>0.61</td></tr><tr><td>3_17_13</td><td>17</td><td>17</td><td>46</td><td>38</td><td>26</td><td>25</td><td><b>17</b></td><td><b>17</b></td><td>0.65</td><td>0.68</td></tr><tr><td>alu-v1_29</td><td>17</td><td>15</td><td>57</td><td>43</td><td>53</td><td>34</td><td><b>20</b></td><td><b>19</b></td><td>0.38</td><td>0.56</td></tr><tr><td>miller_11</td><td>23</td><td>23</td><td>65</td><td>53</td><td>32</td><td>29</td><td><b>23</b></td><td><b>23</b></td><td>0.72</td><td>0.79</td></tr><tr><td>alu-v3_34</td><td>24</td><td>23</td><td>109</td><td>74</td><td>37</td><td>36</td><td><b>27</b></td><td><b>27</b></td><td>0.73</td><td>0.75</td></tr><tr><td>decod24-v2_43</td><td>22</td><td>22</td><td>57</td><td>55</td><td>28</td><td>28</td><td><b>22</b></td><td><b>22</b></td><td>0.79</td><td>0.79</td></tr><tr><td>decod24-v0_38</td><td>23</td><td>23</td><td>79</td><td>57</td><td>27</td><td>25</td><td><b>21</b></td><td><b>21</b></td><td>0.78</td><td>0.84</td></tr><tr><td>mod5d2_64</td><td>25</td><td>25</td><td>94</td><td>77</td><td><b>38</b></td><td><b>38</b></td><td>40</td><td>40</td><td>1.05</td><td>1.05</td></tr><tr><td>4gt13_92</td><td>30</td><td>26</td><td>84</td><td>65</td><td><b>39</b></td><td><b>35</b></td><td>42</td><td>38</td><td>1.08</td><td>1.09</td></tr><tr><td>4gt13-v1_93</td><td>30</td><td>27</td><td>106</td><td>70</td><td><b>37</b></td><td><b>34</b></td><td>39</td><td>36</td><td>1.05</td><td>1.06</td></tr><tr><td>4mod5-v0_18</td><td>31</td><td>31</td><td>91</td><td>71</td><td>58</td><td>46</td><td><b>43</b></td><td><b>40</b></td><td>0.74</td><td>0.87</td></tr><tr><td>decod24-bdd_294</td><td>32</td><td>31</td><td>102</td><td>85</td><td><b>44</b></td><td><b>37</b></td><td>53</td><td>52</td><td>1.20</td><td>1.41</td></tr><tr><td>one-two-three-<br>v2_100</td><td>32</td><td>29</td><td>86</td><td>75</td><td><b>46</b></td><td><b>41</b></td><td>53</td><td>52</td><td>1.15</td><td>1.27</td></tr><tr><td>one-two-three-<br>v3_101</td><td>32</td><td>29</td><td>108</td><td>91</td><td>53</td><td>50</td><td><b>42</b></td><td><b>39</b></td><td>0.79</td><td>0.78</td></tr><tr><td>4mod5-v1_23</td><td>32</td><td>30</td><td>113</td><td>82</td><td>50</td><td>49</td><td><b>47</b></td><td><b>42</b></td><td>0.94</td><td>0.86</td></tr><tr><td>4mod5-bdd_287</td><td>31</td><td>31</td><td>103</td><td>84</td><td>46</td><td><b>39</b></td><td><b>43</b></td><td>43</td><td>0.93</td><td>1.10</td></tr><tr><td>rd32_270</td><td>36</td><td>35</td><td>117</td><td>98</td><td><b>45</b></td><td><b>38</b></td><td>54</td><td>53</td><td>1.20</td><td>1.39</td></tr><tr><td>4gt5_75</td><td>38</td><td>33</td><td>99</td><td>74</td><td><b>56</b></td><td><b>53</b></td><td><b>56</b></td><td>54</td><td>1.00</td><td>1.02</td></tr><tr><td>alu-bdd_288</td><td>38</td><td>35</td><td>140</td><td>110</td><td><b>65</b></td><td><b>45</b></td><td>74</td><td>72</td><td>1.14</td><td>1.60</td></tr><tr><td>alu-v0_26</td><td>38</td><td>35</td><td>115</td><td>85</td><td><b>56</b></td><td><b>48</b></td><td>57</td><td>56</td><td>1.02</td><td>1.17</td></tr><tr><td>decod24-v1_41</td><td>38</td><td>35</td><td>127</td><td>100</td><td><b>56</b></td><td><b>50</b></td><td>62</td><td>62</td><td>1.11</td><td>1.24</td></tr><tr><td>rd53_138</td><td>60</td><td>42</td><td>202</td><td>130</td><td><b>111</b></td><td><b>87</b></td><td><b>111</b></td><td>91</td><td>1.00</td><td>1.05</td></tr><tr><td>4gt5_76</td><td>46</td><td>42</td><td>115</td><td>84</td><td><b>67</b></td><td><b>55</b></td><td>68</td><td>66</td><td>1.01</td><td>1.20</td></tr><tr><td>4gt13_91</td><td>49</td><td>46</td><td>147</td><td>113</td><td><b>62</b></td><td><b>59</b></td><td>70</td><td>65</td><td>1.13</td><td>1.10</td></tr><tr><td>cnt3-5_179</td><td>85</td><td>43</td><td>327</td><td>150</td><td>182</td><td><b>90</b></td><td><b>179</b></td><td>109</td><td>0.98</td><td>1.21</td></tr><tr><td>qft_10</td><td>90</td><td>34</td><td>342</td><td>140</td><td>75</td><td><b>45</b></td><td><b>73</b></td><td>50</td><td>0.97</td><td>1.11</td></tr><tr><td>4gt13_90</td><td>53</td><td>50</td><td>158</td><td>120</td><td><b>67</b></td><td><b>64</b></td><td>77</td><td>72</td><td>1.15</td><td>1.12</td></tr><tr><td>alu-v4_36</td><td>51</td><td>47</td><td>158</td><td>112</td><td><b>67</b></td><td><b>62</b></td><td><b>67</b></td><td>63</td><td>1.00</td><td>1.02</td></tr><tr><td>mini_alu_305</td><td>77</td><td>53</td><td>265</td><td>137</td><td><b>125</b></td><td><b>93</b></td><td>158</td><td>129</td><td>1.26</td><td>1.39</td></tr><tr><td>ising_model_10</td><td>90</td><td>20</td><td>222</td><td>78</td><td>111</td><td><b>41</b></td><td><b>105</b></td><td>50</td><td>0.95</td><td>1.22</td></tr><tr><td>ising_model_16</td><td>150</td><td>20</td><td>540</td><td>160</td><td><b>172</b></td><td><b>31</b></td><td>234</td><td>110</td><td>1.36</td><td>3.55</td></tr><tr><td>ising_model_13</td><td>120</td><td>20</td><td>381</td><td>121</td><td>171</td><td>68</td><td><b>150</b></td><td><b>61</b></td><td>0.88</td><td>0.90</td></tr><tr><td>4gt5_77</td><td>58</td><td>51</td><td>156</td><td>121</td><td><b>73</b></td><td><b>67</b></td><td>91</td><td>82</td><td>1.25</td><td>1.22</td></tr><tr><td>sys6-v0_111</td><td>98</td><td>55</td><td>302</td><td>144</td><td><b>170</b></td><td><b>117</b></td><td>176</td><td>137</td><td>1.04</td><td>1.17</td></tr><tr><td>one-two-three-v1_99</td><td>59</td><td>56</td><td>211</td><td>166</td><td>95</td><td><b>77</b></td><td><b>84</b></td><td>81</td><td>0.88</td><td>1.05</td></tr><tr><td>one-two-three-v0_98</td><td>65</td><td>59</td><td>202</td><td>156</td><td>94</td><td>86</td><td><b>92</b></td><td><b>84</b></td><td>0.98</td><td>0.98</td></tr><tr><td>decod24-v3_45</td><td>64</td><td>57</td><td>189</td><td>130</td><td>103</td><td>94</td><td><b>92</b></td><td><b>90</b></td><td>0.89</td><td>0.96</td></tr><tr><td>4gt10-v1_81</td><td>66</td><td>60</td><td>234</td><td>177</td><td><b>100</b></td><td><b>92</b></td><td>105</td><td>99</td><td>1.05</td><td>1.08</td></tr><tr><td>aj-e11_165</td><td>69</td><td>63</td><td>199</td><td>161</td><td>93</td><td>89</td><td><b>88</b></td><td><b>87</b></td><td>0.95</td><td>0.98</td></tr></tbody></table>
5:30 On the Qubit Routing Problem

<table><thead><tr><th rowspan="2">Name</th><th rowspan="2">g<sub>in</sub></th><th rowspan="2">d<sub>in</sub></th><th colspan="2">Qiskit 0.7.0</th><th colspan="2">Quilc 1.1.1<br>Pyquil 2.1.1</th><th colspan="2">CQC's t|ket⟩</th><th colspan="2">t|ket⟩<br>comparison</th></tr><tr><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>r<sub>gate</sub></th><th>r<sub>depth</sub></th></tr></thead><tbody><tr><td>4mod7-v0_94</td><td>72</td><td>66</td><td>200</td><td>144</td><td><b>97</b></td><td><b>87</b></td><td>111</td><td>110</td><td>1.14</td><td>1.26</td></tr><tr><td>alu-v2_32</td><td>72</td><td>64</td><td>250</td><td>178</td><td><b>92</b></td><td><b>84</b></td><td>109</td><td>106</td><td>1.18</td><td>1.26</td></tr><tr><td>rd73_140</td><td>104</td><td>68</td><td>341</td><td>186</td><td><b>179</b></td><td><b>122</b></td><td>182</td><td>148</td><td>1.02</td><td>1.21</td></tr><tr><td>4mod7-v1_96</td><td>72</td><td>65</td><td>230</td><td>181</td><td>100</td><td>89</td><td><b>91</b></td><td><b>85</b></td><td>0.91</td><td>0.96</td></tr><tr><td>4gt4-v0_80</td><td>79</td><td>71</td><td>196</td><td>145</td><td><b>112</b></td><td><b>90</b></td><td>115</td><td>106</td><td>1.03</td><td>1.18</td></tr><tr><td>mod10_176</td><td>78</td><td>70</td><td>285</td><td>197</td><td>120</td><td><b>104</b></td><td><b>118</b></td><td>114</td><td>0.98</td><td>1.10</td></tr><tr><td>0410184_169</td><td>104</td><td>70</td><td>362</td><td>209</td><td>257</td><td>135</td><td><b>184</b></td><td><b>122</b></td><td>0.72</td><td>0.90</td></tr><tr><td>qft_16</td><td>240</td><td>58</td><td>934</td><td>311</td><td><b>243</b></td><td><b>90</b></td><td>303</td><td>153</td><td>1.25</td><td>1.70</td></tr><tr><td>4gt12-v0_88</td><td>86</td><td>77</td><td>267</td><td>195</td><td><b>137</b></td><td><b>106</b></td><td>140</td><td>133</td><td>1.02</td><td>1.25</td></tr><tr><td>rd84_142</td><td>154</td><td>81</td><td>539</td><td>240</td><td><b>280</b></td><td><b>172</b></td><td>286</td><td>176</td><td>1.02</td><td>1.02</td></tr><tr><td>rd53_311</td><td>124</td><td>92</td><td>422</td><td>256</td><td>-</td><td>-</td><td><b>253</b></td><td><b>191</b></td><td>0.60</td><td>0.75</td></tr><tr><td>4_49_16</td><td>99</td><td>91</td><td>253</td><td>190</td><td><b>140</b></td><td><b>129</b></td><td>166</td><td>162</td><td>1.19</td><td>1.26</td></tr><tr><td>sym9_146</td><td>148</td><td>91</td><td>497</td><td>272</td><td><b>259</b></td><td><b>177</b></td><td><b>259</b></td><td>200</td><td>1.00</td><td>1.13</td></tr><tr><td>4gt12-v1_89</td><td>100</td><td>88</td><td>323</td><td>228</td><td>153</td><td>139</td><td><b>151</b></td><td><b>138</b></td><td>0.99</td><td>0.99</td></tr><tr><td>4gt12-v0_87</td><td>112</td><td>94</td><td>384</td><td>267</td><td>166</td><td>152</td><td><b>136</b></td><td><b>123</b></td><td>0.82</td><td>0.81</td></tr><tr><td>4gt4-v0_79</td><td>105</td><td>94</td><td>262</td><td>190</td><td><b>116</b></td><td><b>105</b></td><td>133</td><td>128</td><td>1.15</td><td>1.22</td></tr><tr><td>hwb4_49</td><td>107</td><td>99</td><td>306</td><td>228</td><td><b>142</b></td><td><b>133</b></td><td>150</td><td>141</td><td>1.06</td><td>1.06</td></tr><tr><td>sym6_316</td><td>123</td><td>98</td><td>422</td><td>269</td><td><b>229</b></td><td><b>165</b></td><td>232</td><td>192</td><td>1.01</td><td>1.16</td></tr><tr><td>4gt12-v0_86</td><td>116</td><td>98</td><td>356</td><td>238</td><td>170</td><td>156</td><td><b>143</b></td><td><b>130</b></td><td>0.84</td><td>0.83</td></tr><tr><td>4gt4-v0_72</td><td>113</td><td>95</td><td>379</td><td>252</td><td>170</td><td>139</td><td><b>131</b></td><td><b>120</b></td><td>0.77</td><td>0.86</td></tr><tr><td>4gt4-v0_78</td><td>109</td><td>99</td><td>247</td><td>195</td><td><b>135</b></td><td><b>120</b></td><td>140</td><td>135</td><td>1.04</td><td>1.12</td></tr><tr><td>mod10_171</td><td>108</td><td>97</td><td>305</td><td>215</td><td><b>133</b></td><td><b>114</b></td><td>165</td><td>161</td><td>1.24</td><td>1.41</td></tr><tr><td>4gt4-v1_74</td><td>119</td><td>108</td><td>365</td><td>274</td><td><b>168</b></td><td><b>138</b></td><td>182</td><td>175</td><td>1.08</td><td>1.27</td></tr><tr><td>rd53_135</td><td>134</td><td>114</td><td>442</td><td>305</td><td>241</td><td>186</td><td><b>194</b></td><td><b>179</b></td><td>0.80</td><td>0.96</td></tr><tr><td>mini-alu_167</td><td>126</td><td>111</td><td>369</td><td>282</td><td><b>167</b></td><td><b>153</b></td><td>174</td><td>157</td><td>1.04</td><td>1.03</td></tr><tr><td>one-two-three-v0_97</td><td>128</td><td>116</td><td>367</td><td>263</td><td><b>188</b></td><td><b>175</b></td><td>189</td><td>184</td><td>1.01</td><td>1.05</td></tr><tr><td>ham7_104</td><td>149</td><td>134</td><td>309</td><td>236</td><td><b>209</b></td><td><b>169</b></td><td>236</td><td>221</td><td>1.13</td><td>1.31</td></tr><tr><td>decod24-enable_126</td><td>149</td><td>134</td><td>363</td><td>280</td><td><b>215</b></td><td><b>194</b></td><td>227</td><td>219</td><td>1.06</td><td>1.13</td></tr><tr><td>mod8-10_178</td><td>152</td><td>135</td><td>331</td><td>263</td><td><b>188</b></td><td><b>167</b></td><td>224</td><td>209</td><td>1.19</td><td>1.25</td></tr><tr><td>cnt3-5_180</td><td>215</td><td>148</td><td>822</td><td>439</td><td><b>377</b></td><td><b>234</b></td><td>379</td><td>285</td><td>1.01</td><td>1.22</td></tr><tr><td>ex3_229</td><td>175</td><td>157</td><td>460</td><td>354</td><td>319</td><td>231</td><td><b>214</b></td><td><b>197</b></td><td>0.67</td><td>0.85</td></tr><tr><td>4gt4-v0_73</td><td>179</td><td>160</td><td>451</td><td>356</td><td>259</td><td>227</td><td><b>242</b></td><td><b>222</b></td><td>0.93</td><td>0.98</td></tr><tr><td>mod8-10_177</td><td>196</td><td>178</td><td>609</td><td>423</td><td><b>248</b></td><td><b>218</b></td><td>277</td><td>261</td><td>1.12</td><td>1.20</td></tr><tr><td>C17_204</td><td>205</td><td>173</td><td>664</td><td>474</td><td>384</td><td>295</td><td><b>268</b></td><td><b>236</b></td><td>0.70</td><td>0.80</td></tr><tr><td>alu-v2_31</td><td>198</td><td>172</td><td>553</td><td>426</td><td>402</td><td><b>287</b></td><td><b>306</b></td><td>289</td><td>0.76</td><td>1.01</td></tr><tr><td>rd53_131</td><td>200</td><td>175</td><td>604</td><td>437</td><td>300</td><td><b>227</b></td><td><b>267</b></td><td>243</td><td>0.89</td><td>1.07</td></tr><tr><td>alu-v2_30</td><td>223</td><td>199</td><td>482</td><td>373</td><td><b>293</b></td><td><b>269</b></td><td>358</td><td>338</td><td>1.22</td><td>1.26</td></tr><tr><td>mod5adder_127</td><td>239</td><td>208</td><td>650</td><td>476</td><td>356</td><td>292</td><td><b>311</b></td><td><b>288</b></td><td>0.87</td><td>0.99</td></tr><tr><td>rd53_133</td><td>256</td><td>221</td><td>703</td><td>499</td><td>359</td><td><b>308</b></td><td><b>348</b></td><td>328</td><td>0.97</td><td>1.06</td></tr><tr><td>cm82a_208</td><td>283</td><td>234</td><td>914</td><td>607</td><td><b>393</b></td><td><b>317</b></td><td>451</td><td>391</td><td>1.15</td><td>1.23</td></tr><tr><td>majority_239</td><td>267</td><td>232</td><td>720</td><td>528</td><td>402</td><td>328</td><td><b>348</b></td><td><b>311</b></td><td>0.87</td><td>0.95</td></tr><tr><td>ex2_227</td><td>275</td><td>241</td><td>886</td><td>648</td><td>443</td><td><b>371</b></td><td><b>416</b></td><td>391</td><td>0.94</td><td>1.05</td></tr><tr><td>sf_276</td><td>336</td><td>301</td><td>989</td><td>731</td><td><b>372</b></td><td><b>340</b></td><td>489</td><td>453</td><td>1.31</td><td>1.33</td></tr><tr><td>sf_274</td><td>336</td><td>300</td><td>863</td><td>643</td><td>457</td><td>391</td><td><b>357</b></td><td><b>328</b></td><td>0.78</td><td>0.84</td></tr><tr><td>con1_216</td><td>415</td><td>346</td><td>1389</td><td>916</td><td><b>659</b></td><td><b>486</b></td><td>736</td><td>626</td><td>1.12</td><td>1.29</td></tr><tr><td>wim_266</td><td>427</td><td>352</td><td>1145</td><td>793</td><td><b>763</b></td><td><b>501</b></td><td>772</td><td>688</td><td>1.01</td><td>1.37</td></tr></tbody></table>
<table><thead><tr><th rowspan="2">Name</th><th rowspan="2">g<sub>in</sub></th><th rowspan="2">d<sub>in</sub></th><th colspan="2">Qiskit 0.7.0</th><th colspan="2">Quilc 1.1.1 Pyquil 2.1.1</th><th colspan="2">CQC's t|ket⟩</th><th colspan="2">t|ket⟩ comparison</th></tr><tr><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>r<sub>gate</sub></th><th>r<sub>depth</sub></th></tr></thead><tbody><tr><td>rd53_130</td><td>448</td><td>383</td><td>1242</td><td>899</td><td>695</td><td><b>547</b></td><td><b>646</b></td><td>608</td><td>0.93</td><td>1.11</td></tr><tr><td>f2_232</td><td>525</td><td>449</td><td>1443</td><td>1069</td><td><b>722</b></td><td><b>621</b></td><td>854</td><td>772</td><td>1.18</td><td>1.24</td></tr><tr><td>cm152a_212</td><td>532</td><td>461</td><td>1491</td><td>1051</td><td>805</td><td><b>633</b></td><td><b>793</b></td><td>717</td><td>0.99</td><td>1.13</td></tr><tr><td>rd53_251</td><td>564</td><td>492</td><td>1487</td><td>1058</td><td>960</td><td><b>659</b></td><td><b>805</b></td><td>715</td><td>0.84</td><td>1.08</td></tr><tr><td>hwb5_53</td><td>598</td><td>535</td><td>1568</td><td>1179</td><td>941</td><td>765</td><td><b>808</b></td><td><b>757</b></td><td>0.86</td><td>0.99</td></tr><tr><td>cm42a_207</td><td>771</td><td>634</td><td>2333</td><td>1593</td><td>1411</td><td>996</td><td><b>1102</b></td><td><b>968</b></td><td>0.78</td><td>0.97</td></tr><tr><td>pm1_249</td><td>771</td><td>634</td><td>2303</td><td>1574</td><td>1411</td><td>996</td><td><b>1102</b></td><td><b>968</b></td><td>0.78</td><td>0.97</td></tr><tr><td>dc1_220</td><td>833</td><td>705</td><td>2450</td><td>1715</td><td>1532</td><td><b>1049</b></td><td><b>1436</b></td><td>1261</td><td>0.94</td><td>1.20</td></tr><tr><td>squar5_261</td><td>869</td><td>720</td><td>2902</td><td>1948</td><td><b>1463</b></td><td><b>1063</b></td><td>1631</td><td>1372</td><td>1.11</td><td>1.29</td></tr><tr><td>z4_268</td><td>1343</td><td>1112</td><td>4185</td><td>2828</td><td>2282</td><td><b>1632</b></td><td><b>2235</b></td><td>1914</td><td>0.98</td><td>1.17</td></tr><tr><td>sqrt8_260</td><td>1314</td><td>1121</td><td>4079</td><td>2846</td><td>2406</td><td><b>1665</b></td><td><b>2235</b></td><td>1964</td><td>0.93</td><td>1.18</td></tr><tr><td>radd_250</td><td>1405</td><td>1210</td><td>4346</td><td>3050</td><td>-</td><td>-</td><td><b>2697</b></td><td><b>2361</b></td><td>0.62</td><td>0.77</td></tr><tr><td>adr4_197</td><td>1498</td><td>1249</td><td>4584</td><td>3110</td><td><b>2333</b></td><td><b>1720</b></td><td>2737</td><td>2368</td><td>1.17</td><td>1.38</td></tr><tr><td>sym6_145</td><td>1701</td><td>1499</td><td>4872</td><td>3517</td><td>2554</td><td><b>2042</b></td><td><b>2301</b></td><td>2145</td><td>0.90</td><td>1.05</td></tr><tr><td>misex1_241</td><td>2100</td><td>1797</td><td>-</td><td>-</td><td><b>3249</b></td><td><b>2435</b></td><td>4291</td><td>3760</td><td>1.32</td><td>1.54</td></tr><tr><td>rd73_252</td><td>2319</td><td>1963</td><td>-</td><td>-</td><td>3854</td><td><b>2798</b></td><td><b>3748</b></td><td>3276</td><td>0.97</td><td>1.17</td></tr><tr><td>cycle10_2_110</td><td>2648</td><td>2276</td><td>-</td><td>-</td><td>4511</td><td><b>3463</b></td><td><b>4342</b></td><td>3802</td><td>0.96</td><td>1.10</td></tr><tr><td>hwb6_56</td><td>2952</td><td>2559</td><td>-</td><td>-</td><td>4405</td><td><b>3575</b></td><td><b>4205</b></td><td>3904</td><td>0.95</td><td>1.09</td></tr><tr><td>square_root_7</td><td>3089</td><td>2520</td><td>-</td><td>-</td><td><b>4967</b></td><td><b>3427</b></td><td>5790</td><td>4833</td><td>1.17</td><td>1.41</td></tr><tr><td>ham15_107</td><td>3858</td><td>3273</td><td>-</td><td>-</td><td>6649</td><td><b>4828</b></td><td><b>6485</b></td><td>5605</td><td>0.98</td><td>1.16</td></tr><tr><td>dc2_222</td><td>4131</td><td>3518</td><td>-</td><td>-</td><td>-</td><td>-</td><td><b>7694</b></td><td><b>6708</b></td><td></td><td></td></tr><tr><td>sqn_258</td><td>4459</td><td>3719</td><td>-</td><td>-</td><td>-</td><td>-</td><td><b>6863</b></td><td><b>5984</b></td><td></td><td></td></tr><tr><td>inc_237</td><td>4636</td><td>3928</td><td>-</td><td>-</td><td>-</td><td>-</td><td><b>8274</b></td><td><b>7176</b></td><td></td><td></td></tr><tr><td>cm85a_209</td><td>4986</td><td>4256</td><td>-</td><td>-</td><td>-</td><td>-</td><td><b>8166</b></td><td><b>7093</b></td><td></td><td></td></tr><tr><td>rd84_253</td><td>5960</td><td>4917</td><td>-</td><td>-</td><td>-</td><td>-</td><td><b>9506</b></td><td><b>8154</b></td><td></td><td></td></tr><tr><td>co14_215</td><td>7840</td><td>5759</td><td>-</td><td>-</td><td>-</td><td>-</td><td>14415</td><td>11195</td><td></td><td></td></tr><tr><td>root_255</td><td>7493</td><td>5965</td><td>-</td><td>-</td><td>-</td><td>-</td><td>11971</td><td>9940</td><td></td><td></td></tr><tr><td>mlp4_245</td><td>8232</td><td>6930</td><td>-</td><td>-</td><td>-</td><td>-</td><td>15156</td><td>13061</td><td></td><td></td></tr><tr><td>urf2_277</td><td>10066</td><td>8312</td><td>-</td><td>-</td><td>-</td><td>-</td><td>17367</td><td>15384</td><td></td><td></td></tr><tr><td>sym9_148</td><td>9408</td><td>8062</td><td>-</td><td>-</td><td>-</td><td>-</td><td>13893</td><td>12321</td><td></td><td></td></tr><tr><td>life_238</td><td>9800</td><td>8356</td><td>-</td><td>-</td><td>-</td><td>-</td><td>15944</td><td>13926</td><td></td><td></td></tr><tr><td>hwb7_59</td><td>10681</td><td>9112</td><td>-</td><td>-</td><td>-</td><td>-</td><td>17655</td><td>15828</td><td></td><td></td></tr><tr><td>max46_240</td><td>11844</td><td>9657</td><td>-</td><td>-</td><td>-</td><td>-</td><td>19519</td><td>16979</td><td></td><td></td></tr><tr><td>clip_206</td><td>14772</td><td>12028</td><td>-</td><td>-</td><td>-</td><td>-</td><td>25499</td><td>21345</td><td></td><td></td></tr><tr><td>9symml_195</td><td>15232</td><td>12849</td><td>-</td><td>-</td><td>-</td><td>-</td><td>24532</td><td>21295</td><td></td><td></td></tr><tr><td>sym9_193</td><td>15232</td><td>12849</td><td>-</td><td>-</td><td>-</td><td>-</td><td>24532</td><td>21295</td><td></td><td></td></tr><tr><td>sao2_257</td><td>16864</td><td>13209</td><td>-</td><td>-</td><td>-</td><td>-</td><td>28799</td><td>23847</td><td></td><td></td></tr><tr><td>dist_223</td><td>16624</td><td>13274</td><td>-</td><td>-</td><td>-</td><td>-</td><td>27953</td><td>23342</td><td></td><td></td></tr><tr><td>urf5_280</td><td>23764</td><td>19888</td><td>-</td><td>-</td><td>-</td><td>-</td><td>41610</td><td>36329</td><td></td><td></td></tr><tr><td>urf1_278</td><td>26692</td><td>22307</td><td>-</td><td>-</td><td>-</td><td>-</td><td>46023</td><td>40020</td><td></td><td></td></tr><tr><td>sym10_262</td><td>28084</td><td>23736</td><td>-</td><td>-</td><td>-</td><td>-</td><td>44383</td><td>38132</td><td></td><td></td></tr><tr><td>hwb8_113</td><td>30372</td><td>26041</td><td>-</td><td>-</td><td>-</td><td>-</td><td>50008</td><td>44245</td><td></td><td></td></tr><tr><td>urf2_152</td><td>35210</td><td>32247</td><td>-</td><td>-</td><td>-</td><td>-</td><td>58307</td><td>53905</td><td></td><td></td></tr><tr><td>urf3_279</td><td>60380</td><td>50568</td><td>-</td><td>-</td><td>-</td><td>-</td><td>105870</td><td>91838</td><td></td><td></td></tr><tr><td>plus63mod4096_163</td><td>56329</td><td>48265</td><td>-</td><td>-</td><td>-</td><td>-</td><td>95107</td><td>82375</td><td></td><td></td></tr><tr><td>urf5_158</td><td>71932</td><td>64750</td><td>-</td><td>-</td><td>-</td><td>-</td><td>122288</td><td>110318</td><td></td><td></td></tr></tbody></table>
5:32 On the Qubit Routing Problem

<table><thead><tr><th rowspan="2">Name</th><th rowspan="2">g<sub>in</sub></th><th rowspan="2">d<sub>in</sub></th><th colspan="2">Qiskit</th><th colspan="2">Quilc 1.1.1</th><th rowspan="2">CQC's t|ket⟩</th><th rowspan="2">t|ket⟩<br>comparison</th></tr><tr><th>g<sub>out</sub></th><th>d<sub>out</sub></th><th>g<sub>out</sub></th><th>d<sub>out</sub></th></tr></thead><tbody><tr><td>urf6_160</td><td>75180</td><td>67637</td><td>–</td><td>–</td><td>–</td><td>–</td><td>141416 120999</td><td>r<sub>gate</sub> r<sub>depth</sub></td></tr><tr><td>urf1_149</td><td>80878</td><td>72933</td><td>–</td><td>–</td><td>–</td><td>–</td><td>137791 123873</td><td></td></tr><tr><td>plus63mod8192_164</td><td>81865</td><td>70222</td><td>–</td><td>–</td><td>–</td><td>–</td><td>145872 125957</td><td></td></tr><tr><td>hwb9_119</td><td>90955</td><td>77968</td><td>–</td><td>–</td><td>–</td><td>–</td><td>149106 131678</td><td></td></tr><tr><td>urf3_155</td><td>185276</td><td>167215</td><td>–</td><td>–</td><td>–</td><td>–</td><td>317732 285000</td><td></td></tr><tr><td>ground_state _esti-154209</td><td>151095</td><td></td><td>–</td><td>–</td><td>–</td><td>–</td><td>1015 776</td><td></td></tr><tr><td>mation_10</td><td></td><td></td><td>–</td><td>–</td><td>–</td><td>–</td><td></td><td></td></tr><tr><td>urf4_187</td><td>224028</td><td>185975</td><td>–</td><td>–</td><td>–</td><td>–</td><td>385355 330368</td><td></td></tr></tbody></table>

g: the number of quantum gates (elementary operations),

d: depth of the quantum circuits and – are time-outs.