# String Abstractions for Qubit Mapping

Blake Gerard  The University of Oklahoma<EMAIL_ADDRESS>and  Martin Kong
The University of Oklahoma<EMAIL_ADDRESS>
(2021)

###### Abstract.

One of the key compilation steps in Quantum Computing (QC) is to determine an
initial logical to physical mapping of the qubits used in a quantum circuit.
The impact of the starting qubit layout can vastly affect later scheduling and
placement decisions of QASM operations, yielding higher values on critical
performance metrics (gate count and circuit depth) as a result of quantum
compilers introducing SWAP operations to meet the underlying physical
neighboring and connectivity constraints of the quantum device.

In this paper we introduce a novel qubit mapping approach, string-based qubit
mapping. The key insight is to prioritize the mapping of logical qubits that
appear in longest repeating non-overlapping substrings of qubit pairs
accessed. This mapping method is complemented by allocating qubits according
to their global frequency usage. We evaluate and compare our new mapping
scheme against two quantum compilers (QISKIT and TKET) and two device
topologies, the IBM Manhattan (65 qubits) and the IBM Kolkata (27 qubits). Our
results demonstrate that combining both mapping mechanisms often achieve
better results than either one individually, allowing us to best QISKIT and
TKET baselines, yielding between 13% and 17% average improvement in several
group sizes, up to 32% circuit depth reduction and 63% gate volume
improvement.

quantum computing, qubit placement, circuit depth optimization, sub-string
detection

††journalyear: 2021††copyright: rightsretained††conference: ; ;

##  1\. Introduction

The field of Quantum Computing (QC) is rapidly growing. Several technologies
and applications are being sought and designed to demonstrate Quantum
Supremacy (Arute et al., 2019). At the same time, various quantum computers
have been constructed and made accessible to the public as cloud services
(IBM, 2021). Numerous real quantum devices such as Google Sycamore and
Rigetti’s Aspen-9 (Rigetti, 2021) have been proposed to tackle problems beyond
the computational power of today’s supercomputers. This effort has been
complemented by multiple applications being expressed using frameworks such as
OpenFermion (McClean et al., 2017), while various quantum compilers (QISKIT
(IBM, 2018), Rigetti’s Pyquil (Rigetti, [n. d.]), Google’s Cirq (Developers,
2021), Cambridge’s TKET (Sivarajah et al., 2020)) support the task of
translating and mapping quantum programs onto real hardware.

Ultimately, programs are lowered to a form of quantum assembly such as
OpenQASM (Cross et al., 2017) and used as input to the rest of the quantum
compilation process (or “transpilation” in QISKIT terminology). Compiling
quantum programs involves several steps, including determining the initial
qubit layout, introducing special operations to move the state of a qubit
(Quantum Bit) between non-physically adjacent qubits (also known as layout
synthesis or routing), gate scheduling, and further lowering the program to
technology dependent, native operations available in the physical device, e.g.
pulse compilation (Alexander et al., 2020) (Tan and Cong, 2020a).

In this paper we focus on the problem of determining the initial qubit layout,
that is, the task of assigning each logical qubit to a physical qubit on an
specific target device. In particular, a quantum computer has a fixed number
of physical qubits, $Q$, which are physically connected by the underlying
technology. Thus, the quantum device is often represented as a coupling graph
$G=(Q,E)$. The existence of an edge in the graph denotes that the qubits
connected by it can be used as operands to a two-qubit quantum gate operation.
In this scenario we say that the qubits are “physically adjacent”. However,
when this is not the case, and owing to the “no cloning theorem” (Bužek and
Hillery, 1996), the compiler is required to introduce special quantum
operations, SWAPs, to exchange the state between two non-physically adjacent
qubits.

Given the number of physical qubits of a device, $Q$, the number of possible
layouts is $Q!$. Given this, the problem of determining a logical-to-physical
qubit mapping consists on computing a permutation of the original logical
qubit sequence $q_{0},q_{1},\ldots,q_{n-1}$ so that quality and performance
metrics (e.g. circuit depth, gate volume, total error and even execution time)
are optimized.

We propose a new qubit mapping class, String-Based Qubit Allocation (SBQA).
The key insight is to prioritize qubit allocation over sub-string sequences,
and within these, further favor qubits that are heavily used. Strings are
extracted from a linearized sub-trace of the quantum program consisting of
only indices used in two-qubit gates. Once the high-impact qubits are
processed within a sub-string, repeated occurrences are removed from the sub-
trace before locating the next repeated sub-string to target. This approach is
then complemented with a simple qubit allocation using global histograms. Our
results show that our qubit mapping strategies often achieve 13%-15% average
improvement on several groups of quantum circuits (arranged by size), peaking
at 32% circuit depth improvement and 63% in gate volume.

To summarize, the contributions of our work are: i) We propose two new qubit
mapping techniques, Sub-String (SS) and Global Frequencies (GF), which are
designed to be used both in combination or in stand-alone fashion. In
particular, SS is, to the best of our knowledge, the first qubit mapping
technique driven by string patterns. ii) We conduct a comprehensive evaluation
of our techniques, comparing to layout methods available in state-of-the-art
quantum compilers (QISKIT and TKET). Furthermore, we demonstrate that a two-
phase qubit mapping strategy offers benefits above any of the individual
techniques we propose. iii) To address the urgency for more scalable
techniques, we strongly motivate the need for novel qubit mapping strategies
by identifying limitations of current qubit/gate mappers. We thus depart from
graph- and solver-based approaches. Moreover, we demonstrate that techniques
availabe today are better tuned for small circuits and small quantum devices.
iv) We introduce a new standalone tool that can be used by the community to
explore new qubit mapping strategies.

The rest of this paper is organized as follows. Section 2 further motivates
our research problem. Section 3 covers the main background and related
concepts needed. Section 4 provides an overview and working example applying
our technique. Section 5 introduces our string-based qubit mapping methods.
Section 6 presents a comprehensive evaluation and comparison of our method
against baseline compilers, initial layout and routing methods. Section 7
recaps and summarizes the most recent and relevant related work to the problem
of qubit mapping. Finally, Section 8 presents the conclusions and future
directions of our work.

##  2\. Motivation

Numerous techniques proposed in prior work have simultaneously addressed the
qubit mapping and routing problem. However, we make the distinction between
finding a good initial logical-to-physical qubit mapping (which can change
during the compilation of the program) and the process of introducing SWAP
operations to amend physical connectivity constraints not met naturally in the
program. We thus defer the routing problem to already available passes in
today’s quantum compilers.

To the best of our knowledge, all quantum compilation passes operate over the
dependence graph extracted from the quantum assembly representation. TKET’s
Graph Placement (Cowtan et al., 2019) attempts to map logical qubits in a
greedy fashion by building graphs from independent pairs of qubits accessed
through various time steps (a logical partition of gates that can be executed
in parallel). Once the graph is built, it finds an isomorphic sub-graph in the
coupling graph representing the physical device. In particular, this method
ensures that only two timesteps are free of SWAP operations. The algorithm
also breaks long lines that fail to map into smaller ones until they are
successfully assigned. In a similar spirit, MUQUT (Bhattacharjee et al., 2019)
attempts to map qubits by extracting sub-graphs of fixed cardinality from the
program’s dependence graph and proceeding to map them to isomorphic sub-graph
of the coupling graph. Seed nodes used for extracting the logical sub-graph
are randomly selected. Maslov, Falconer and Mosca (Maslov et al., 2008)
proposed one of the earliest qubit placement heuristics based on recursive
graph partitioning. Techniques like Dense Layout (IBM, 2018) in QISKIT map
qubits by searching for the “most connected subset of (logical) qubits”.
Zulehner, Paler and Wille (Zulehner et al., 2018) partition the input program
dependence graph into network layers, and apply A* search techniques to find
local optimal mappings; Mappings between adjacent layers are then repaired in
a later pass. Siraichi et al. (Siraichi et al., 2018) select the initial
mapping by determining heavily used logical qubits, and mapping them to
physical ones that most closely match their out-degree. A second class of
approaches, which incur an even higher computational complexity, resort to
Integer Linear Programming and Satisfiability Modulo Theory (SMT) solvers to
find optimal solutions; The qubit (and gates) mapping problem is formulated to
assign individual gates onto the graph defining the connectivity of a quantum
device (Murali et al., 2019; Tan and Cong, 2020a; Wille et al., 2019; Murali
et al., 2020), making it even harder to decouple a strong inital mapping from
gate scheduling and mapping.

#### A simple example

To further motivate the need for better qubit mapping techniques, consider the
rd84_253 quantum circuit from the IBM-QX circuit set (Institute for Integrated
Circuits, 2019). This circuit consists of 13,659 quantum gates, of which 5,960
are two-qubit gates. Previous studies have shown that two-qubit gates,
significantly impact several quality metrics of quantum programs (Tan and
Cong, 2020a, b) owing to the topological constraints that must be met for a
two-qubit gate to be executed. More precisely, a two-qubit gate can only be
executed on two qubits that are physically linked in the coupling graph that
defines the quantum device.

We have designed two complementary qubit mapping techniques, one based on Sub-
String (SS) detection of two-qubit quantum operations, and a Global Frequency
(GF) approach. Furthermore, when applied back-to-back, the combined mapping
strategy, Global Sub-string Frequency (GSF), often delivers stronger results
than any one individual technique. To demonstrate this, we present in Table 1
excerpts of our results: the variation in circuit depth (number of quantum
operations in the critical path), variation in gate volume (number of gates)
and variation in SWAP operations (state exchange between two any qubits).
Results are normalized to the baseline compiler QISKIT using the SABRE initial
layout method and TKET with Noise-Aware Placement. For circuit depth and gate
volume, any value above 1.00 represents an improvement, while for the SWAP
Ops, positive values indicate improvement. Each of our three mapping methods
are compiled with a base configuration (suffix b) and with an optimized one
(suffix o) – Flags used shown in Section 6. As we can see, our methods achieve
up to $1.19\times$ circuit depth improvement with QISKIT and up to
$1.20\times$ with TKET. At the same time, with GSFo on TKET, we produce up to
$1.25\times$ improvement on the gate volume metric, out matching all other
mappings. Lastly, our mapping methods also improves the number of needed SWAP
operations, obtaining a 29% reduction with GSFo. As a point of reference the
best improvement in gate volume reported in (Li et al., 2019) was 30% on a
circuit with 3,888 QOPS (quantum operations) while for rd84_253 the
improvement on gate volume was 5%. Lastly, the same study was limited to
circuits with up to 34,881 gates.

Table 1. rd84_253 compilation metrics collected on IBM Manhattan (65 qubit): Circuit Depth, Gate Volume and Inserted SWAP Operations. | Compiler | Mapping Method
---|---|---
Metric | Config. |  SSb |  SSo |  GFb |  GFo |  GSFb |  GSFo
Circuit | QISKIT | 1.19 | 1.01 | 1.19 | 1.03 | 1.17 | 1.05
Depth | TKET | 1.02 | 1.07 | 0.96 | 1.12 | 1.09 | 1.2
Gate | QISKIT | 0.67 | 1.01 | 0.7 | 1.04 | 0.65 | 1.07
Volume | TKET | 0.097 | 1.1 | 0.96 | 1.14 | 1.03 | 1.25
SWAPS | QISKIT | -0.47 | 0.01 | -0.4 | 0.04 | -0.51 | 0.06
Ops | TKET | 0.19 | 0.16 | 0.17 | 0.17 | 0.28 | 0.29

##  3\. Background

#### Qubits

Qubits are the basic unit of information in quantum computing. Each qubit
represents a linear combination $c_{1}|0\rangle+c_{2}|1\rangle$ of two basis
states $|0\rangle$ and $|1\rangle$, with $c_{1}$ and $c_{2}$ being complex
numbers. A set of logically contiguous qubits conforms a quantum register.

#### Quantum Gates

Are unitary matrix operations applied to individual qubits. Current quantum
gate typically operate on a single qubit and on two qubits at the time. For
example, the CX (Controlled-NOT) gate takes two operands, the control qubit
and the target qubit, while the X gate takes a single qubit. Each quantum
architecture defines a gate basis, a set of gates to which all programs must
be reduced to. For example, IBM quantum computers use gates CX, ID, RZ, SX and
X as their gate basis.

#### Quantum Assembly and Circuit Diagrams

Quantum programs can be represented in a device agnostic fashion using quantum
assembly formats such as OpenQASM (Cross et al., 2017). Listing
LABEL:lst:graycode show the implementation of the graycode6_47 circuit using
OpenQASM. The same program can also be visualized as a circuit diagram, as
shown in Figure LABEL:fig:graycode-circuit. Circuit diagrams depict logical
qubits as horizontal lanes, with the time-dimension advancing from left to
right. Single-qubit gates are directly placed on a single lane, while two-
qubit gates connect the qubit lanes used as operands.

⬇

OPENQASM 2.0;

qreg q[16];

creg c[16];

cx q[1],q[0];

cx q[2],q[1];

cx q[3],q[2];

cx q[4],q[3];

cx q[5],q[4];

⬇

\hfill

\begin{minipage}{0.4\linewidth}

\includegraphics[width=\linewidth]{figures/graycode-circuit-converted}

\captionof{figure}{\label{fig:graycode-circuit}Graycode6\_47 circuit diagram.}

\end{minipage}

\end{minipage}

\paragraph{Coupling Graph}

Current quantum computers present stringent architectural constraints

that require qubits used as arguments to two-qubit gates (e.g. the \texttt{cx}

gate) to be qubits that are physically connected. Thus, quantum devices are

conceptually modeled in {\em coupling graphs}. A {\em physical} qubit

in modeled in the graph as a node, while edges linking two nodes establish

the physical connection. Figure \ref{fig:coupling-maps} show the topology

of the quantum devices used in our evaluation, the 27-qubit

IBM Kolkata and the 65-qubit IBM Manhattan \cite{ibm-services}.

\begin{figure}[h]

\includegraphics[width=0.45\linewidth]{figures/ibmq-kolkata-converted}

\includegraphics[width=0.45\linewidth]{figures/ibmq-manhattan-converted}

\caption{\label{fig:coupling-maps}Example coupling maps: 27-qubit device IBM
Kolkata (left) and 65-qubit IBM Manhattan (right)}

\end{figure}

##  4\. Overview

In this section we give a brief overview of the major steps followed for
computing a more effective initial logical-to-physical qubit mapping. The
input to our mapping method is a QASM file containing the quantum operations
(QOPS), such as the one shown in Fig. LABEL:lst:graycode. Next, we extract a
sub-trace containing not only the CX (CNOT) gates, but all two-qubit gate
operations. Take for instance circuit max46_240 from the IBM-QX quantum
circuit set (Institute for Integrated Circuits, 2019), which consists of
27,126 QOPS, of which 11,844 are CX gates. The remaining gates are distributed
as 5,076 TDG gates, 6,768 T gates, 3,384 H gates and 54 X gates. Next, for
each 2-qubit gate of the form $OPCODE~{}q_{1},~{}q_{2}$ we compute a
linearized identifier $id_{lin}=q_{1}~{}.~{}DEV_{width}+q_{2}$, where
$DEV_{width}$ is the number of physical qubits available in target quantum
device. Thus, all symbols conforming our strings will be defined in the
alphabet $\\{u~{}.~{}DEV_{width}+v:0\leq u,v<DEV_{width}\\}$.

Once the program has been converted into a linearized string representation,
we compute a few statistics to drive the qubit mapping process. For example,
this program references 76 distinct characters of our alphabet from the
potential 729 ($27^{2}$). These are all the logical qubit-to-qubit connections
used the circuit. In total, the 76 logical links are used 11,844 times; The
average logical connection is used 155.8 times, with a standard deviation of
174.6. However, not all qubits are used in the same fashion nor at the same
frequency. Consider Table 2, where for each logical qubit used in circuit
max46_240 we show in the third row, the number of times that the said qubit is
used as the first operand (the control qubit) in a 2-qubit gate. The second
row states the number of distinct logical connections used in the program for
each logical qubit, while the fourth and last row limit the total number of
references to only the two and three most frequently qubits paired with a
given qubit $q_{i}$. From here on, we will often refer to all pairs $\langle
q_{i},q_{j}\rangle$ of a given qubit $q_{i}$ as the logical pair, edge, link
or connections of $q_{i}$.

Table 2.  Edge histogram of circuit max46_240. Qubit | 0 | 1 | 2 | 3 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---
No. Distinct | 2 | 6 | 8 | 8 | 9 | 9 | 9 | 9
Used Total | 420 | 1222 | 1128 | 972 | 1010 | 1636 | 2060 | 1876
Top 2 | 420 | 1074 | 732 | 460 | 382 | 752 | 1304 | 1188
Top 3 | 420 | 1142 | 912 | 580 | 558 | 972 | 1644 | 1360

Next, we proceed to determine if there exists a substring pattern in the
linearized string that repeats and which does not overlap with following
occurrences. For example, from the linearized string representation of
max46_240 a substring of length 364 meeting these conditions is found 2 times
at locations 4,536 and 11,200. This means that there are two sequences of 364
2-qubit gate operations which can be optimized (hopefully) by the quantum
compiler only once. The repeated sequence found, from a graph-based mapping
approach, could eventually be found as a path (or line in TKET terminology) in
the data dependence graph, but interspersed with single-qubit gates, making
the search for gate sequences of this length much harder to find.

The actual logical to physical mapping of qubits then proceeds. We compute the
information listed in Table 2 but restricted to the logical qubits used within
the subsequence. Mapping within the gate subsequence will be constrained to
only the qubits whose frequency of usage is above the mean value of the
subsequence. For example, when limiting this information to only the qubit
pairs referenced in the substring, the mean value becomes 849.2; A quick
inspection reveals that 5 logical qubits have more logical links than the
mean, namely $q_{1},q_{2},q_{7},q_{8}$ and $q_{9}$. Qubits that satisfy this
condition belong to the High-Impact Qubits (HIQ) set. Furthermore, the steps
that follow will limit the mapping of logical qubits that belong to the HIQ
set. This is done to avoid mapping qubits that will ultimately have a low
impact on later compilation metrics, such as the gate volume, circuit depth
and swap count. Mapping takes place by choosing a leading logical qubit and a
leading physical qubit to which to map it. By extension, logical qubits used
as the target node to a logical link will be mapped to the qubits physically
adjacent to the lead physical qubit. Mapping proceeds by sorting and aligning
the neighboring qubits in both cases. In our example, logical qubit $q_{8}$
and physical qubit $q_{25}$ would be chosen as the lead qubits, while logical
qubits $q_{1}$, $q_{7}$ and $q_{9}$ would be mapped to physical qubits
$q_{22}$, $q_{24}$ and $q_{26}$. We note here that logical qubit $q_{9}$ was
also in the HIQ set, and was a close second choice of a lead qubit. However,
selecting $q_{8}$ will preclude choosing $q_{9}$ later.

Our algorithm will attempt to continue mapping qubits from the HIQ set if the
chosen lead logical qubit has at least one non-mapped neighbor. If no further
mappings take place within the current string subsequence, the current
sequence is removed from the linearized string representation prior to
repeating the steps starting with the local histogram computation. If no
repeating subsequence is found, the string-based qubit allocation strategy
terminates, and we proceed to use only the global pair frequencies (See Table
2). Finally, if no qubit pair can be mapped, the process alternates to map
most referenced logical qubits to physical qubits with the best fidelity and
lowest read error.

##  5\. Mapping

###  5.1. Detecting Sub-Strings

As first step, we extract a linearized trace from all the pairs of qubit
indices appearing in 2-qubit gates (e.g. $\langle 1,2\rangle$ from CX 1,2),
and encoding the pair as a $q_{1}~{}.~{}Q_{device}+q_{2}$, where $Q_{device}$
is the number of physical qubits in the quantum device, $q_{1}$ is the first
component of the pair, and $q_{2}$ the second one. The linearization allows us
distinguish pairs $\langle i,j\rangle$ from $\langle j,i\rangle$. We do note,
however, that all 2-qubit gate operations, regardless of their type, will be
encoded in this fashion.

Next, we proceed to determine whether there exists a subsequence of QASM
operations that repeats within the linearized two-qubit stream. If a repeating
subsequence does exist, we are interested in the longest, non-overlapping one.
In summary, we aim to find the longest repeating non-overlapping substring.
Then, the most relevant qubits within each substring will be mapped first.

Eq. 1 is used to compute the length of matching substrings from a given string
$S$, and storing the prefix lengths in a table $T$. Table $T$ is built from
the bottom-up, computing first prefixes of length 1, then prefixes of length 2
and so on. It is easy to see that if $S_{i}\neq S_{j}$ then the matching
prefix length is zero; Otherwise the new prefix length effectively increases
by one. Eq. 1 can be easily implemented in an iterative fashion; However, care
must be taken to minimize the memory footprint of $T$ in order to avoid
incurring in a $O(n^{2})$ space complexity, which for QASM-based circuits soon
consisting of millions of QOPS can result in significant memory requirements.
To illustrate this point, a program with 100K QASM operations, and encoding
each qubit index pair as a 4-byte integer would require $32.25GB$ while one
with 500K quantum operations would require $931GB$. Thus, when computing this
table, we resort to keep only the two most recent rows, keeping the maximum
length of $T_{i,j}$, and storing the $i$ index at each update to the maximum
length.

(1) $\displaystyle T_{i,j}=\begin{cases}T_{i-1,j-1}+1:&S_{i}=S_{j}\wedge
j>i\wedge T_{i-1,j-1}<j-i\\\ 0&otherwise\end{cases}$

###  5.2. Global Frequencies

Next, We compute for each qubit pair $\langle q_{i},q_{j}\rangle$ the number
of times that such pair is used in two-qubit quantum gates. We denote this
value as $refs(\langle q_{i},q_{j}\rangle)$. Then, for each qubit $q_{i}$ we
compute its total usage frequency as:

$\displaystyle freq(q_{i})=\sum_{q_{j}}refs(\langle q_{i},q_{j}\rangle)$

In several instances, and to prioritize the mapping of qubits. we will also
sort all neighboring qubits $q_{j}$, for a given $q_{i}$, by their $refs$
value.

###  5.3. Mapping Qubits from Sub-Strings

Algorithm 1 Map Qubits by Sub-String (SS) Method

0: $Q_{phys}$: Physical Qubit Set; $Q_{log}$: Logical Qubit Set; $P$ : QASM
Program

0: $M_{l2p}$: Logical-to-physical qubit layout map.

1: /* Initialize pending list */

2: $Q_{pending}$ $\leftarrow$ Extract two-qubit indices from $P$;

3: $Q_{avail}$ $\leftarrow$ $Q_{phys}$;

4: $edges$ $\leftarrow$ Extract_qubit_pairs_from_program ($P$);

5: $P_{str}$ $\leftarrow$ linearize_qubit_pairs ($edges$);

6: while (not done) do

7: /* Build a histogram of edges (pairs of qubits) */

8: $H$ $\leftarrow$ build_qubit_edge_frequency ($edges$);

9: /* Select High-Impact Qubits (hiq) from H */

10: $L_{hiq}$ $\leftarrow$ build_high_impact_qubit_list ($H$);

11: $str$ $\leftarrow$ find_lrnos ($P_{str}$);

12: if length($str$) $<2$ then

13: done $\leftarrow$ True;

14: end if

15: $ehist$ $\leftarrow$ substring_histogram (str);

16: while ($q_{phys}$ $\leftarrow$ get_next_physical_qubit ($Q_{avail}$)) do

17: if ($q_{phys}$ is invalid) then

18: break;

19: end if

20: $L_{phys}$ $\leftarrow$ $\\{q_{phys}\\}\cup(adj(q_{phys})\cap Q_{avail});$

21: $L_{log}$ $\leftarrow$ select_logical_qubits ($Q_{pending}$, $L_{hiq}$,
$ehist$);

22: if size($L_{log}$) ¡ 2 then

23: break;

24: end if

25: $M_{l2p}$ $\leftarrow$map_qubits ($L_{log}$, $L_{phys}$);

26: $Q_{pending}$ $\leftarrow$ $Q_{pending}$ \- $L_{log}$;

27: $Q_{avail}$ $\leftarrow$ $Q_{avail}$ \- $L_{phys}$;

28: sort $Q_{avail}$ by number of available neighbors;

29: end while

30: if no qubits were mapped in previous loop then

31: $P_{str}$ $\leftarrow$ remove_substring_occurrences ($P_{str}$, $str$);

32: sort $Q_{avail}$ by number of available neighbors;

33: $edges$ $\leftarrow$$edges$ \- $\\{\langle
q_{i},q_{j}\rangle:q_{i}~{}or~{}q_{j}\not\in Q_{pending}\\}$;

34: end if

35: end while

36: return $M_{l2p}$;

Algorithm 1 presents the steps taken to map a subset of logical qubits used in
the input program to a set of physical available qubits. The overall algorithm
proceeds by finding longest repeating non-overlapping sub-strings (LRNOS) in
the quantum program, and proceeding to map as many high-impact qubits (HIQ) as
possible from it. We define a HIQ as a qubit with a higher $freq$ than the
mean, but restricted to the current LRNOS. To differentiate HIQ from other
qubits, we compute the average number of times that a logical qubit $q_{i}$
appears as the first operand of a two-qubit gate operation (e.g.
$CX~{}q_{i},~{}q_{j}$), as defined in Sec.5.2. This number is then used as a
minimum threshold to properly identify any $HIQ$. In addition, we also require
logical qubits to be in the $Q_{pending}$ set.

Qubit mapping proceeds at two levels, rounds and steps. Rounds allocate qubits
for a given LRNOS, and are controlled in the outermost while-loop of Alg. 1;
Steps perform finer-grain actions in the innermost while-loop, by first
selecting a leading physical qubit ($q_{phys}$) to be used as the control
qubit to a number of 2-qubit gate operations, followed by selecting the still
available physical qubits adjacent to the leading one ($adj(q_{phys})$). A
similar selection is done for the logical qubits; The lead logical qubit is
selected from the $L_{hiq}$, after which the $k=len(adj(q_{phys}))$ most often
qubits $q_{j}$ such that $\langle q_{i},q_{j}\rangle$ are chosen and added to
$L_{log}$. Once logical and physical qubits have been chosen, we map each
corresponding leading qubits and their adjacent ones, assigning more heavily
used logical qubits to the physical qubits with the lowest error. The steps
loop exits when either a leading physical qubit cannot be found, or when the
set of logical qubits, $L_{log}$, consists of only one qubit (the leading
one). The latter scenario occurs when non-HIQ qubits remain in the current
LRNOS. After exiting the steps loop, a few actions are taken to prepare for
the next LRNOS: sub-string occurrences of the current LRNOS are removed from
$P_{str}$, the set/list of available physical qubits ($Q_{avail}$) is sorted
by the number of available neighbors, while the list of linearized qubit pairs
($edges$) is updated by removing all edges that have been partially allocated
either because the source or target qubit are not pending anymore.

###  5.4. Mapping Remaining 2-qubit gate Qubits

Algorithm 2 Map Qubit by Global Frequency (GF)

0: $Q_{phys}$: Physical Qubit Set; $Q_{log}$: Logical Qubit Set; $P$ : QASM
Program

0: $M_{l2p}$: Logical-to-physical qubit layout map.

1: /* Initialize pending list */

2: $Q_{pending}$ $\leftarrow$ Extract two-qubit indices from $P$;

3: $Q_{pending}$ $\leftarrow$ $Q_{pending}$ \- physical($M_{l2p}$)

4: sort $Q_{avail}$ by number of available physical neighbors;

5: $edges$ $\leftarrow$ Extract_qubit_pairs_from_program ($P$);

6: while ($Q_{pending}$ $\neq\varnothing$) do

7: $edges$ $\leftarrow$ $edges$ $\cap\\{\langle
q_{i},q_{j}\rangle:q_{i},q_{j}\in Q_{pending}\\}$ ;

8: $ehist$ $\leftarrow$ build_histogram ($edges$);

9: if $ehist$ is empty then

10: break;

11: end if

12: $q_{phys}$ $\leftarrow$ get_next_physical_qubit ($Q_{avail}$);

13: $L_{phys}$ $\leftarrow$ $\\{q_{phys}\\}\cup(adj(q_{phys})\cap Q_{avail});$

14: $L_{log}$ $\leftarrow$ select_logical_qubits ($Q_{pending}$, $ehist$);

15: if size($L_{log}$) ¡ 2 then

16: break;

17: end if

18: $M_{l2p}$ $\leftarrow$map_qubits ($L_{log}$, $L_{phys}$);

19: $Q_{pending}$ $\leftarrow$ $Q_{pending}$ \- $L_{log}$;

20: $Q_{avail}$ $\leftarrow$ $Q_{avail}$ \- $L_{phys}$;

21: end while

22: return $M_{l2p}$;

Table 3.  Average of normalized depth variation by circuit size – QISKIT compiler. | IBM Manhattan (65 qubit) | IBM Kolkata (27 qubit)
---|---|---
C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | C10 | C11 | C12 | C13
Group [Size Range] : |  SSb |  SSo |  GFb |  GFo |  GSFb |  GSFo |  SSb |  SSo |  GFb |  GFo |  GSFb |  GSFo
(Instances): |  |  |  |  |  |  |  |  |  |  |  |
G1 [ 1: 1K] (105) | 1.01 | 1.06 | 1.07 | 1.01 | 0.99 | 1.02 | 1.03 | 1.03 | 1.07 | 1.08 | 0.95 | 1.08
G2 [ 1K: 5K] (15) | 1.11 | 1.03 | 1.10 | 1.02 | 1.12 | 1.03 | 1.11 | 1.02 | 1.11 | 1.00 | 1.12 | 1.02
G3 [ 5K: 10K] (6) | 1.13 | 0.98 | 1.15 | 0.98 | 1.14 | 0.98 | 1.15 | 0.99 | 1.13 | 0.99 | 1.14 | 1.00
G4 [10K: 20K] (7) | 1.13 | 1.00 | 1.13 | 1.02 | 1.12 | 1.02 | 1.13 | 1.01 | 1.12 | 1.02 | 1.12 | 1.01
G5 [20K: 30K] (5) | 1.13 | 0.95 | 1.12 | 0.97 | 1.13 | 0.97 | 1.14 | 1.00 | 1.16 | 1.01 | 1.17 | 1.00
G6 [30K: 40K] (5) | 1.13 | 1.00 | 1.11 | 0.99 | 1.13 | 1.00 | 1.13 | 0.99 | 1.12 | 1.00 | 1.13 | 1.02
G7 [40K: 100K] (5) | 1.13 | 0.98 | 1.13 | 0.98 | 1.14 | 1.00 | 1.12 | 0.97 | 1.14 | 1.01 | 1.11 | 0.99
G8 [100K: 250K] (7) | 1.10 | 1.00 | 1.11 | 0.98 | 1.10 | 1.00 | 1.11 | 0.99 | 1.11 | 1.00 | 1.12 | 1.00
G9 [250K: 1M] (2) | 1.09 | 0.98 | 1.09 | 0.98 | 1.09 | 0.98 | 1.16 | 1.05 | 1.14 | 1.05 | 1.16 | 1.05
Table 4.  Average of normalized depth variation by circuit size – TKET compiler. | IBM Manhattan (65 qubit) | IBM Kolkata (27 qubit)
---|---|---
C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | C10 | C11 | C12 | C13
Group [Size Range] |  SSb |  SSo |  GFb |  GFo |  GSFb |  GSFo |  SSb |  SSo |  GFb |  GFo |  GSFb |  GSFo
(Instances): |  |  |  |  |  |  |  |  |  |  |  |
G1 [ 1: 1K] (105) | 0.66 | 0.78 | 0.71 | 0.88 | 0.64 | 0.75 | 0.68 | 0.80 | 0.70 | 0.89 | 0.63 | 0.72
G2 [ 1K: 5K] (15) | 0.89 | 0.97 | 0.89 | 1.02 | 0.88 | 0.96 | 0.79 | 0.89 | 0.81 | 0.90 | 0.80 | 0.89
G3 [ 5K: 10K] (6) | 0.85 | 0.97 | 0.87 | 0.98 | 0.84 | 1.03 | 0.89 | 0.97 | 0.86 | 1.03 | 0.88 | 1.05
G4 [ 10K: 20K] (7) | 0.93 | 1.03 | 0.91 | 1.05 | 0.97 | 1.10 | 0.94 | 1.04 | 0.90 | 1.03 | 0.96 | 1.05
G5 [ 20K: 30K] (5) | 0.99 | 1.10 | 1.01 | 1.12 | 0.97 | 1.06 | 0.97 | 1.06 | 0.97 | 1.07 | 0.98 | 1.08
G6 [ 30K: 40K] (5) | 0.93 | 1.04 | 0.94 | 1.09 | 0.93 | 1.08 | 0.92 | 1.00 | 0.94 | 1.05 | 0.94 | 1.02
G7 [ 40K: 100K] (5) | 0.92 | 1.02 | 0.92 | 1.03 | 0.92 | 1.02 | 0.86 | 0.96 | 0.88 | 0.98 | 0.85 | 0.96
G8 [100K: 250K] (7) | 0.92 | 1.05 | 0.93 | 1.04 | 0.93 | 1.04 | 0.93 | 1.04 | 0.92 | 1.03 | 0.94 | 1.05
G9 [250K: 1M] (2) | 0.92 | 1.01 | 0.98 | 1.09 | 0.92 | 1.01 | 0.86 | 0.97 | 0.87 | 0.96 | 0.86 | 0.97

Next, we present a second algorithm, inspired in MUQUT’s (Bhattacharjee et
al., 2019) k-vertex topology graph extraction, and which complements the sub-
string based qubit allocation method introduced in the previous section.
Algorithm 2 is a more direct version of Algorithm 1. It only attempts to map
qubits by considering the histogram (global frequency) of logical qubits used
in 2-qubit gates. Consequently, the assignment of qubits is performed in a
single loop, choosing first a leading physical qubit (and indirectly, its
adjacent physical ones), followed by selecting the leading logical qubit
together with its neighbors. The actual mapping proceeds in the same fashion
as in the first algorithm. The loop stops whenever we find that the updated
global histogram $ehist$ has no pending edges (NOTE: qubits can still be
pending, but they will no form a pair $\langle q_{i},q_{j}\rangle$ where both
qubits are in the $Q_{pending}$). At the end of each iteration, both the
logical pending qubit set ($Q_{pending}$) and the physical available qubit set
($Q_{avail}$) are accordingly updated.

Table 5. Experimental Testbed

.  Compilers Base Flags / Passes Opt Flags / Passes TKET identity placement +
Same as base + v0.13.0 routing + FullPeepholeOptimize + IBM rebase +
NoiseAwarePlacement validity predicate (Only for Original QASM) QISKIT
layout_method= layout_method=’sabre’ + ’trivial’ + routing_method=’sabre’ +
opt-level=2 scheduling_method=None + v0.23.6 translation_method= ’translator’
+ opt-level=2

###  5.5. Mapping Remaining 1-qubit gate Qubits

If after mapping qubits with Algorithm 1 – 2 no unmapped pair $\langle
q_{i},q_{j}\rangle$ can be found, we then proceed to map qubits based solely
on their single-qubit gate error and read error rates, which are obtained from
the physical parameter files associated to each quantum device.

##  6\. Evaluation

We implemented the qubit mapping methods described in Sec.5 as a single
standalone tool which takes quantum circuits in OpenQASM and emits a remapped
program also in OpenQASM. The compilers used, together with their version and
options are listed in Table 5. Devices used are the IBM Manhattan (65-qubit,
72 edges) and Kolkata (27-qubit, 28 edges) (IBM, 2021). Physical parameter
files were retrieved on August 22, 2021.

#### Evaluated Circuits:

We use the IBM-QX QASM benchmark set (Institute for Integrated Circuits,
2019), which has been extensively used in prior works (Zulehner et al., 2018;
Li et al., 2019; Sivarajah et al., 2020; Tan and Cong, 2020a). All circuits in
this collection utilize up to 16 qubits. The suite consist of 158 quantum
circuits, of which we use all but the ground-state-estimation circuit owing to
compilers removing all but a handful of operations from a program with $390K$
quantum operations. The average circuit size (in number of quantum gates) of
the remaining 157 circuits is $18,714.5$ operations, with a standard deviation
of $62,863$. However, 105 of the circuits present 1000 or fewer operations. We
thus organize our results in 9 groups. The specific ranges of circuit sizes
can be found on the leftmost column of Table 3–7. The new mappings were
collected in a 32-core AMD Thread-Ripper server, with 128 GB DRAM, and
operating with Ubuntu 18. The total time to generate all 157 layouts, for the
Manhattan topology, with our SS, GF and GSF mappings was 79.2sec, 79.4sec and
159.3sec, respectively.

Table 6.  Average of normalized gates variation by circuit size: QISKIT compiler. | IBM Manhattan (65 qubit) | IBM Kolkata (27 qubit)
---|---|---
C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | C10 | C11 | C12 | C13
Group [Size Range] |  SSb |  SSo |  GFb |  GFo |  GSFb |  GSFo |  SSb |  SSo |  GFb |  GFo |  GSFb |  GSFo
(Instances): |  |  |  |  |  |  |  |  |  |  |  |
G1 [ 1: 1K] (105) | 0.55 | 1.04 | 0.63 | 0.98 | 0.53 | 0.98 | 0.57 | 1.01 | 0.63 | 1.00 | 0.49 | 1.00
G2 [ 1K: 5K] (15) | 0.63 | 1.04 | 0.63 | 1.04 | 0.64 | 1.05 | 0.64 | 1.00 | 0.64 | 0.99 | 0.64 | 1.00
G3 [ 5K: 10K] (6) | 0.63 | 0.98 | 0.65 | 0.97 | 0.64 | 0.97 | 0.65 | 0.98 | 0.62 | 0.99 | 0.64 | 1.00
G4 [ 10K: 20K] (7) | 0.64 | 1.00 | 0.64 | 1.00 | 0.63 | 1.02 | 0.64 | 1.01 | 0.63 | 1.02 | 0.64 | 1.01
G5 [ 20K: 30K] (5) | 0.64 | 0.90 | 0.62 | 0.94 | 0.64 | 0.93 | 0.64 | 0.99 | 0.66 | 1.01 | 0.68 | 1.01
G6 [ 30K: 40K] (5) | 0.64 | 1.00 | 0.63 | 1.01 | 0.64 | 1.00 | 0.63 | 1.00 | 0.63 | 1.00 | 0.63 | 1.04
G7 [ 40K: 100K] (5) | 0.64 | 0.98 | 0.64 | 0.98 | 0.66 | 0.99 | 0.62 | 0.92 | 0.65 | 1.01 | 0.62 | 0.97
G8 [100K: 250K] (7) | 0.65 | 1.01 | 0.66 | 1.00 | 0.65 | 1.01 | 0.64 | 0.98 | 0.64 | 0.99 | 0.66 | 1.01
G9 [250K: 1M] (2) | 0.60 | 0.92 | 0.60 | 0.91 | 0.60 | 0.92 | 0.65 | 1.02 | 0.63 | 0.98 | 0.65 | 1.02
Table 7.  Average of normalized gates variation by circuit size – TKET compiler. | IBM Manhattan (65 qubit) | IBM Kolkata (27 qubit)
---|---|---
C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | C10 | C11 | C12 | C13
Group [Size Range] |  SSb |  SSo |  GFb |  GFo |  GSFb |  GSFo |  SSb |  SSo |  GFb |  GFo |  GSFb |  GSFo
(Instances): |  |  |  |  |  |  |  |  |  |  |  |
G0 [ 1: 1K] (105) | 0.52 | 0.64 | 0.59 | 0.87 | 0.48 | 0.64 | 0.52 | 0.69 | 0.56 | 0.81 | 0.44 | 0.57
G1 [ 1K: 5K] (15) | 0.78 | 0.91 | 0.79 | 0.97 | 0.78 | 0.91 | 0.71 | 0.82 | 0.71 | 0.83 | 0.71 | 0.82
G2 [ 5K: 10K] (6) | 0.78 | 0.96 | 0.79 | 0.96 | 0.76 | 1.02 | 0.80 | 0.99 | 0.79 | 1.03 | 0.80 | 1.10
G3 [ 10K: 20K] (7) | 0.89 | 1.04 | 0.88 | 1.06 | 0.91 | 1.11 | 0.88 | 1.04 | 0.86 | 1.03 | 0.91 | 1.05
G4 [ 20K: 30K] (5) | 0.94 | 1.11 | 0.96 | 1.12 | 0.94 | 1.08 | 0.92 | 1.06 | 0.91 | 1.07 | 0.93 | 1.07
G5 [ 30K: 40K] (5) | 0.88 | 1.07 | 0.89 | 1.10 | 0.88 | 1.09 | 0.88 | 1.01 | 0.89 | 1.05 | 0.89 | 1.03
G6 [ 40K: 100K] (5) | 0.85 | 1.01 | 0.85 | 1.02 | 0.87 | 1.00 | 0.81 | 0.93 | 0.80 | 0.95 | 0.78 | 0.94
G7 [100K: 250K] (7) | 0.88 | 1.06 | 0.88 | 1.06 | 0.88 | 1.05 | 0.87 | 1.04 | 0.85 | 1.02 | 0.88 | 1.05
G8 [250K: 1M] (2) | 0.86 | 1.02 | 0.93 | 1.11 | 0.86 | 1.02 | 0.80 | 0.95 | 0.79 | 0.93 | 0.80 | 0.95

###  6.1. General Trends

We focus our analysis on the circuit depth (number of gates in the program’s
critical path) and on the gate volume metric (number of gates in the program).
However, as in some cases the impact on these metrics can be small relative to
the original circuit size, we take the approach of previous works (Li et al.,
2019; Tan and Cong, 2020a; Sivarajah et al., 2020) and consider only the
metric variation, i.e., the difference between the metric obtained after
compilation and the original metric value (circuit depth or gate volume).

We show the summary of our results on Tables 3 – 7. The first column in all
four tables indicates the group number (range of circuit sizes prior to
compilation) and the number of circuit instances meeting the criterion. The
next 12 columns list the average of our normalized results, i.e. the ratio of
the metric obtained with the baseline configuration by the metric value
obtained when using our mapping (or a combination of them). Column names
denote the combination of our 3 mappings (SS, GF, GSF) in tandem with two
different compiler configurations, $b$ for base and $o$ for optimized. As
previously discussed, GSF is the back-to-back application of our two mapping
strategies, Sub-String (SS) followed by Global Frequencies (GF). Columns C2–C7
correspond to results collected on IBM Manhattan while columns C8–C13
correspond to IBM Kolkata.

#### Impact on Circuit Depth

From Table 3 and Table 4 we observe that our qubit mappings are especially
beneficial when used in conjunction with the QISKIT compiler, while benefits
when utilizing TKET are more noticeable for groups G3–G9, the larger circuit
classes. We recall that average values above 1.00 represent an improvement on
the metrics. We can also observe an interesting phenomenon between groups G1
and G2 on Table 3, which is an inversion in trends; On group G1 configurations
SSo, GFo and GSFo outperform SSb, GFb and GSFb. Then, starting with group G2,
the base configurations always outperform the optimized ones. This
demonstrates that, QISKIT is currently better tuned for smaller circuits. In
contrast, the same effect is not detected in Table 4, where the optimized
configurations always outperform the base ones. Nonetheless, while a similar
inversion does not manifest with TKET, first signs of improvements appear on
group G3, and become more consistent on groups G4 – G9. This suggests that
TKET’s qubit placement method is better tuned for circuits with up to 10K
gates.

Next, we note that our results with QISKIT are somewhat better on the Kolkata
topology, where we achieve an average circuit depth improvement of up to
$1.17\times$ on G5 and $1.16\times$ on G9 with GSFo. These are good examples
of when SS and GF can work in tandem to obtain better overall results. In
comparison, results on Manhattan exhibit less variation among groups, and
averaging $1.13\times$ improvement in several groups. Notable improvements
with TKET on Manhattan can be seen on group G4, where GSFo ($1.10\times$)
clearly outmatches SSo ($1.03\times$) and GFo ($1.05\times$). Finally, we note
a modest decline on the effectiveness of our techniques for groups G7–G9 on
Manhattan, and a more pronounced one on Kolkata for the same groups.

(a) Circuit depth: QISKIT, Manhattan, group G2.

(b) Circuit depth: TKET, Manhattan, group G2.

(c) Circuit depth: QISKIT, Kolkata, group G5.

(d) Circuit depth: TKET, Kolkata, group G5.

Figure 1. Normalized circuit depth variation in IBM-QX, groups 2 and 5.

(a) Gate volume: TKET, Manhattan, group G2.

(b) Gate volume: TKET, Kolkata, group G5.

Figure 2. Normalized gate volume variation in IBM-QX, groups 2 and 5, only
TKET compiler.

#### Impact on Gate Volume

Tables 6–7 summarize our results on the gate count variation using both
compilers and topologies. The first observation we make is related to the
effect of the compiler configurations used base and optimized; Our methods
were particularly impactful on the circuit depth when using the QISKIT
compiler. Sadly, this appears to come with a penalty that manifests on the
gate volume, where the base configurations are consistently outperformed by
the optimized ones. The phenomenon can be interpreted as additional gates
being introduced out of the critical path, but often enough to yield a 30%–40%
gap between the base and optimized configurations. This trend is not observed
when using the TKET compiler, where improvements on both the circuit depth and
gate volume correlate. Overall, we also remark that improvements in the gate
volume when using QISKIT only allow to match the baseline, whereas with TKET
improvements are of the same order as on the circuit depth. For instance, on
Manhattan’s group G4, the aggregate improvement when using GSFo (i.e. SSo \+
GFo) is of the order of $1.11\times$, besting the $1.04\times$ of SSo and
$.106\times$ of GFo. In a similar fashion, TKET on Kolkata’s group G3 achieves
an average $1.10\times$ improvement in the gate volume, exceeding the
$0.99\times$ of SSo and $1.03\times$ of GFo.

Figure 3. Impact of new qubit mappings on SWAP insertion with TKET: Manhattan
(top) and Kolkata (bottom) devices.

###  6.2. Zooming into individual groups

We now turn our attention to understand the impact of our qubit mapping
methods within each circuit size group. Due to the large number of groups and
configurations, we focus on two groups, G2 and G5. Figure 1 displays the
normalized circuit depth for the 4 corresponding configurations of topologies
and compilers. We can see the individual behavior of the 15 circuits
comprising group G2. Our mappings used with the QISKIT compiler clearly
provide better benefits than when using TKET on Manhattan’s group G2 (Figure
1(a)). More specifically, we can notice that GSFb constantly achieves the best
improvement, with only one exception, SSb at x-tick 10. We also observe that
GSFb outperforms GSFo in all but two situations (x-tick 2 and 3). Results for
the same topology and group, but this time using TKET are not as good (Figure
1(b)); The best improvements are obtained by the GFo mapping in 4 cases, while
the vast majority of data points fall below the improvement level. We believe
this is owed to TKET being more highly tuned for smaller circuits, i.e. groups
G1 – G3. Very similar trends can be observed for group 5 on Kolkata, with
QISKIT achieving close to $1.2\times$ improvement on the circuit depth in
several instances (Figure 1(c)), and producing benefits for 3 of the 5
circuits with TKET (Figure 1(d)). Next, we shift our focus to analyze the
impact of our mapping techniques on the gate volume. These results can be seen
in Fig.2. In general, we see that the optimized circuits practically always
obtain better gate volumes for both topologies and both selected groups (G2
and G5). Interestingly, we also note that TKET’s gate volume results are
generally worse on smaller circuits than with larger ones. This observation
aligns well with results on the circuit depth metric previously discussed.
Lastly, the 1.63% reported improvement (Sec. 1) in gate volume was obtained in
group G3, Kolkata device, with TKET.

###  6.3. Impact on SWAP operations

To conclude our evaluation, we present in Fig.3 plots showing the impact of
our mapping strategies over quantum circuits consisting from 500 QOPS to 100K
QOPS. This range spans parts of group G1 and all of groups G2 – G7. Data
points are sorted by their original circuit size, i.e. the number of QOPS
prior to compilation. Data clearly demonstrates that our qubit mapping
approach significantly reduces the number of SWAPs when used with TKET,
nearing 50% SWAP reduction in a few occasions, and consistently reaching 30%
to 40% reduction for large enough circuits. Especially noticeable is the trend
change after the first 10 circuits, where our results experience a marked
improvement on Kolkata, and especially on Manhattan, as the circuit size
increases. In addition, the fact that all our mapping variants improve
collectively further strengthens the premise that TKET is currently better
suited for small circuits and for topologies with lower qubit counts. In
contrast, improvements with QISKIT are more modest, reaching up to 15%
improvement on Manhattan and 16% reduction on Kolkata (NOTE: Plot omitted due
to space limitations). We also note that the optimized configurations (the
ones with suffix o) consistently achieve better results than their base
counterparts.

##  7\. Related Work

The problem of qubit allocation has gained strong interest in the last few
years, largely on account of its impact on on several quality metrics that
affect the performance and behavior of a quantum program (Murali et al.,
2019). However, this problem has been typically studied in conjunction with
the layout synthesis task (also known as layout routing), which repairs a
quantum program by moving qubit states onto physically adjacent qubits to meet
topological constraints (Maslov et al., 2008). Furthermore, this problem has
been proven to be NP-complete (Tan and Cong, 2020a; Siraichi et al., 2018). As
a result, exhaustive enumeration and search techniques such as JKU’s (Zulehner
et al., 2018), while efficient on small circuits and small devices, will
ultimately not scale with programs expected to have millions of quantum gates.
Heuristics such as SABRE (Li et al., 2019) and WPM (Siraichi et al., 2018),
which perform multiple passes on the input program, offer better scalability
prospects. In addition to SABRE, WPM, JKU, TKET line placement (Sivarajah et
al., 2020), BMT (Siraichi et al., 2019), Google’s Cirq (Developers, 2021)
greedy routing and IBM’s Dense Layout and Stochastic Swap (IBM, 2018), also
perform qubit placement by traversing the DAG quantum graph, and performing
local decisions on network layers or qubit paths. As an alternative, several
works have also attempted to tackle this problem using Integer Linear
Programming and Boolean Satisfiability Solvers (Murali et al., 2019; Tan and
Cong, 2020a; Wille et al., 2019; Murali et al., 2020; Bhattacharjee et al.,
2019). These approaches have been successful in finding high-quality solutions
to improve program success rates with noise-aware mappings. However, they
still attempt to map individual gate instances, often in combination with gate
scheduling. Consequently, they are more apt for small circuits and small
devices. In contrast, the methods proposed in this work, in a spirit similar
to (Gerard and Kong, 2021), focus exclusively on the logical-to-physical
assignment of qubits, deferring the SWAP insertion job to later passes.

##  8\. Conclusion and Future Directions

We have presented two qubit mapping techniques, which can be used
independently and together. We assume a decoupled strategy for qubit mapping,
where pairs of offending qubits not physically connected will be repaired by a
later compiler pass. More, our approach, based on detecting repetitive string
patterns, often combined with global frequency detection, offers strong
benefits with the QISKIT and TKET compilers, showing improvement on quality
metrics such as circuit depth, gate volume and SWAP count. As future work, we
plan to further exploit string-oriented quantum optimizations to find patterns
that allow for the decomposition of large quantum programs, and leveraging
repetitive patterns to better exploit locality.

## References

  * (1)
  * Alexander et al. (2020) Thomas Alexander, Naoki Kanazawa, Daniel J Egger, Lauren Capelluto, Christopher J Wood, Ali Javadi-Abhari, and David C McKay. 2020\.  Qiskit pulse: programming quantum computers through the cloud with pulses.  _Quantum Science and Technology_ 5, 4 (2020), 044006\.
  * Arute et al. (2019) Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. 2019\.  Quantum supremacy using a programmable superconducting processor.  _Nature_ 574, 7779 (2019), 505–510.
  * Bhattacharjee et al. (2019) Debjyoti Bhattacharjee, Abdullah Ash Saki, Mahabubul Alam, Anupam Chattopadhyay, and Swaroop Ghosh. 2019.  MUQUT: Multi-Constraint Quantum Circuit Mapping on Noisy Intermediate-Scale Quantum Computers.  (2019).  arXiv:quant-ph/1911.08559
  * Bužek and Hillery (1996) Vladimir Bužek and Mark Hillery. 1996.  Quantum copying: Beyond the no-cloning theorem.  _Physical Review A_ 54, 3 (1996), 1844.
  * Cowtan et al. (2019) Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. 2019.  On the Qubit Routing Problem. In _14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)_ _(Leibniz International Proceedings in Informatics (LIPIcs))_ , Wim van Dam and Laura Mancinska (Eds.), Vol. 135. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 5:1–5:32.  https://doi.org/10.4230/LIPIcs.TQC.2019.5
  * Cross et al. (2017) Andrew W Cross, Lev S Bishop, John A Smolin, and Jay M Gambetta. 2017.  Open quantum assembly language.  _arXiv preprint arXiv:1707.03429_ (2017).
  * Developers (2021) Cirq Developers. 2021\.  Cirq.  (Aug. 2021).  https://doi.org/10.5281/zenodo.5182845 See full list of authors on Github: https://github .com/quantumlib/Cirq/graphs/contributors.
  * Gerard and Kong (2021) Blake Gerard and Martin Kong. 2021.  Exploring Affine Abstractions for Qubit Mapping. In _2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS)_ _(QCS ’21)_.
  * IBM (2018) IBM. 2018.  Qiskit.  (2018).  https://qiskit.org
  * IBM (2021) IBM. 2021.  IBM Quantum Services.  (2021).  https://quantum-computing.ibm.com/services
  * Institute for Integrated Circuits (2019) Johannes Kepler University Linz Institute for Integrated Circuits. 2019.  IIC JKU - IBMQX QASM Circuits.  (2019).  https://github.com/iic-jku/ibm_qx_mapping/tree/master/examples Online; accessed on April 2021.
  * Li et al. (2019) Gushu Li, Yufei Ding, and Yuan Xie. 2019.  Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices. In _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_ _(ASPLOS ’19)_. ACM, New York, NY, USA, 1001–1014.  https://doi.org/10.1145/3297858.3304023
  * Maslov et al. (2008) Dmitri Maslov, Sean M. Falconer, and Michele Mosca. 2008\.  Quantum Circuit Placement.  _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ 27, 4 (2008), 752–763.  https://doi.org/10.1109/TCAD.2008.917562
  * McClean et al. (2017) Jarrod R McClean, Ian D Kivlichan, Damian S Steiger, Yudong Cao, E Schuyler Fried, Craig Gidney, Thomas Häner, Vojtĕch Havlíček, Zhang Jiang, Matthew Neeley, et al. 2017\.  OpenFermion: The Electronic Structure Package for Quantum Computers.  _arXiv preprint arXiv:1710.07629_ (2017).
  * Murali et al. (2019) Prakash Murali, Jonathan M. Baker, Ali Javadi-Abhari, Frederic T. Chong, and Margaret Martonosi. 2019.  Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers. In _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_ _(ASPLOS ’19)_. ACM, New York, NY, USA, 1015–1029.  https://doi.org/10.1145/3297858.3304075
  * Murali et al. (2020) Prakash Murali, David C McKay, Margaret Martonosi, and Ali Javadi-Abhari. 2020.  Software mitigation of crosstalk on noisy intermediate-scale quantum computers. In _Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems_ _(ASPLOS’20)_. 1001–1016.
  * Rigetti ([n. d.]) Rigetti. [n. d.].  Pyquil.  ([n. d.]).  https://github.com/rigetti/pyquil
  * Rigetti (2021) Rigetti. 2021\.  Rigetti Systems: Aspen-9 Quantum Processor.  (2021).  https://qcs.rigetti.com/qpus/
  * Siraichi et al. (2019) Marcos Yukio Siraichi, Vinícius Fernandes dos Santos, Caroline Collange, and Fernando Magno Quintão Pereira. 2019.  Qubit Allocation As a Combination of Subgraph Isomorphism and Token Swapping.  _Proc. ACM Program. Lang._ 3, OOPSLA, Article 120 (Oct. 2019), 29 pages.  https://doi.org/10.1145/3360546
  * Siraichi et al. (2018) Marcos Yukio Siraichi, Vinícius Fernandes dos Santos, Sylvain Collange, and Fernando Magno Quintao Pereira. 2018.  Qubit Allocation. In _Proceedings of the 2018 International Symposium on Code Generation and Optimization_ _(CGO 2018)_. ACM, New York, NY, USA, 113–125.  https://doi.org/10.1145/3168822
  * Sivarajah et al. (2020) Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. 2020\.  tket: a retargetable compiler for NISQ devices.  _Quantum Science and Technology_ 6, 1 (Nov 2020), 014003.  https://doi.org/10.1088/2058-9565/ab8e92
  * Tan and Cong (2020a) Bochen Tan and Jason Cong. 2020a.  Optimal Layout Synthesis for Quantum Computing. In _Proceedings of the 39th International Conference on Computer-Aided Design_ _(ICCAD ’20)_. Association for Computing Machinery, New York, NY, USA, Article 137, 9 pages.  https://doi.org/10.1145/3400302.3415620
  * Tan and Cong (2020b) Bochen Tan and Jason Cong. 2020b.  Optimality Study of Existing Quantum Computing Layout Synthesis Tools.  _IEEE Trans. Comput._ (2020), 1–12.  https://doi.org/10.1109/TC.2020.3009140
  * Wille et al. (2019) Robert Wille, Lukas Burgholzer, and Alwin Zulehner. 2019\.  Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations. In _2019 56th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 1–6.
  * Zulehner et al. (2018) Alwin Zulehner, Alexandru Paler, and Robert Wille. 2018\.  Efficient mapping of quantum circuits to the IBM QX architectures. In _2018 Design, Automation Test in Europe Conference Exhibition (DATE)_. 1135–1138.  https://doi.org/10.23919/DATE.2018.8342181