1.   Introduction

Quantum computing has attracted more and more interest in the last decades, since it provides the possibility to efficiently solve important problems such as integer factorization^[1], unstructured search^[2], and solving linear equations^[3]. However, the (great) improvements in computer science driven by quantum technology are still in the early stage, since large-scale quantum computers have not yet been built. IBM has developed the first 5-qubit backend called IBM QX2, followed by the 16-qubit backend IBM QX3. The revised versions of them are called IBM QX4 and IBM QX5, respectively. Google announced the realization of quantum supremacy, with the 53-qubit quantum processor Sycamore^[4]. IBM Q Experience ¹ provides the public with free quantum computing resources on the cloud and Qiskit ², an open source quantum computing software framework.

Users of early quantum computers mainly rely on quantum circuits to implement quantum algorithms. There is a gap between the design and the implementation of a quantum algorithm^[5]. In the design stage, we usually do not consider any hardware connectivity constraints. But in order to implement an algorithm on a quantum physical device, physical constraints have to be taken into account. For example, IBM physical devices only support 1-qubit gates and the 2-qubit CX gate between two adjacent qubits. Hence, it is necessary to transform the circuits for quantum algorithms to satisfy both logical and physical constraints. It is called qubit mapping, which maps a logical circuit to a physical device by inserting additional gates. A major challenge for quantum information processing is quantum decoherence. Quantum gates are applied in a coherent period but the qubits stay in the coherent state for a very short time. The longest coherence time of a superconducting quantum chip is still within 10 $\mu$s–100 $\mu$s^[6]. Thus, the main goal of qubit mapping is to reduce the number of additional gates and the depth of output circuits in an efficient way.

In the current work, we use In-Memory Subgraph Matching (IMSM)^[7] to generate partial isomorphic subgraphs of logical circuits and physical ones as a set of partial initial mappings. By exploiting an appropriate subgraph isomorphism and the connectivity of the logical circuits and the physical ones, we get a dense (clustered nodes) initial mapping, which avoids some nodes from being mapped to remote positions. Note that both subgraph isomorphism and the adjustment of qubit mapping are NP-complete^[8]. Thus, to be practically efficient, we propose to use tabu search^[9] to generate logical circuits that will be executed on the physical device. The advantage of tabu search is to jump out of local optimum and ensure the diversity of the transformed results. We insert SWAP gates, associated with the gates on the shortest path to the candidate set, which greatly reduces the search space and improves the search speed. We design three evaluation functions that consider not only the current gates but also the constraints of the gates already processed. Our experiments have been conducted by using the architectures of IBM Q Tokyo and Sycamore as the target physical devices. The experimental results show that the evaluation function based on calculating the number of additional gates inserts the smallest number of gates. We test several combinations of state-of-the-art initial mapping and adjustment algorithms aiming to insert fewer additional gates after qubit mapping. Generally speaking, Tabu Search Based Adjustment (TSA) outperforms the Zulehner-Paler-Wille (ZPW) algorithm^[10], SWAP-Based BidiREctional heuristic search algorithm (SABRE)^[11] and Filtered Depth-Limited Search (FiDLS)^[12] in different aspects. When compared with the Dynamic Look-Ahead Heuristic technique (DLH)^[13], which uses the maximum consecutive positive effect of an SWAP operation (MCPE) and the optimized version (MCPE_OP) as the heuristic cost function, the additional gates inserted by TSA in the DLH benchmarks have been reduced by 27.32% and 12.42%, respectively.

The main contributions of this article are summarized as follows.

$1)$ We extend IMSM, which only generates a set of partial initial mappings, by completing the mapping based on the connectivity between qubits.

$2)$ We propose a heuristic circuit adjustment algorithm based on tabu search, TSA, which can adjust large-scale circuits much more efficiently than existing precise search and heuristic algorithms.

$3)$ We propose three look-ahead evaluation functions for the circuit adjustment; one employs configuration checking with aspiration (CCA)^[14], and the other two use the number of additional gates and the depth of the generated circuit as evaluation criteria, taking into account both the current gates and some gates yet to be processed.

$4)$ We compare several state-of-the-art initial mapping and adjustment algorithms, and the results show that the initial mapping generated by our method requires inserting fewer SWAP gates, and TSA has better scalability than them for adjusting the mapping for large-scale circuits.

The rest of this article is organized as follows. In Section 2, we discuss the related work. In Section 3, we recall some background in quantum computing and quantum information. In Section 4, we introduce the problem of qubit mapping and provide our detailed solution. Section 5 reports the experimental results. We conclude in the last section and discuss future work.

2.   Related Work

Paler^[15] has shown that initial mappings have an important impact on qubit mapping. Just by placing qubits in different positions from the default trivial placement in the circuit instances on actual noisy intermediate-scale quantum (NISQ) devices, the cost can be reduced by up to 10%. One important goal of circuit adjustment algorithms is to minimize the number of additional gates. There are currently five main methods to attack the qubit mapping problem.

● Unitary Matrix Decomposition Algorithm. It is used to rearrange a quantum circuit from the beginning while retaining the input circuit^{[16, 17]}. It can be applied to a broad class of circuits consisting of generic gate sets, but the results are not so efficient as a compiler designed specifically for this task.

● Converting into Existing Problems. This approach converts the qubit mapping problem into some existing problems, such as AI planning^{[18, 19]}, integer linear programming^[20], and satisfiability modulo theories (SMT)^[21], and then uses existing tools to find the optimum in an acceptable amount of time for the problem. Furthermore, as the time cost is usually high, it can only process small-scale quantum circuits.

● Exact Methods. Siraichi et al. proposed an exact method^[8]. It iterates over all possible mappings; thus it is only suitable for simple quantum circuits and cannot be extended to complex ones.

● Graph Theory. Shafaei et al. used the minimum linear permutation solution in graph theory to model the problem of reducing the interaction distance^[22]. A two-step method was used to reduce the qubit mapping to a graph problem to minimize the number of additional gates^{[23, 24]}.

● Heuristic Search. Existing solutions mainly aim at inserting as few SWAP gates as possible^{[8, 10-13, 25, 26]}, using the fidelity of the generated circuit as the objective function^[27] or minimizing the overall circuit latency^[28]. At present, there are a number of methods^{[10, 11, 13, 22]} that exploit the look-ahead idea. In particular, Zhu et al. proposed to dynamically adjust the number of look-ahead gates^[13]. SABRE^[11] depends on a random initial mapping. SAHS^[26] is an annealing algorithm to find an initial mapping, but it is unstable. FiDLS^[12] tends to search through all possible combinations of SWAP gates to minimize the number of executable 2-qubit gates. But the cost of a thorough search is very high, especially when dealing with medium-scale and large-scale circuits. DLH^[13] can deal with some large-scale benchmarks. We will give a quantitative comparison with this method in Section 5. A variation-aware qubit movement strategy^[27] was proposed, which takes advantage of the change in error rate and a change-aware qubit mapping strategy by trying to select the route with the lowest probability of failure. Lao et al. showed that the fidelity of a circuit is related to the delay and the number of gates^[28]. Now some heuristic methods are also applied to other platforms such as Surface-17^{[28, 29]} and Sycamore^[12].

3.   Preliminaries

In this section, we introduce some notions and notations of quantum computing. Let $\mathbb{C}$ denote the set of all complex numbers.

Classical information is stored in bits, while quantum information is stored in qubits. Besides two basic states $\left| {\bf{0}} \right\rangle$ and $\left| {\bf{1}} \right\rangle$, a qubit can be in any linear superposition state like $\left| {{\phi}} \right\rangle =a\left| {\bf{0}} \right\rangle +b\left| {\bf{1}} \right\rangle$, where $a,b\in \mathbb{C}$ satisfy the condition $|a|^{2}+|b|^{2}=1$. The intuition is that $\left| {{\phi}} \right\rangle$ is in the state $\left| {\bf{0}} \right\rangle$ with probability $|a|^{2}$ and in the state $\left| {\bf{1}} \right\rangle$ with probability $|b|^{2}$. We use the letter $Q$ (resp. $q$) to denote a physical (resp. logical) qubit.

A quantum gate acts on a qubit to change the state of the qubit. For example, the Hadamard (H) gate is applied on a qubit, and the CX gate is applied on two qubits. Their symbols and matrix forms are shown in Fig.1. The H gate turns state $\left| {\bf{0}} \right\rangle$ (resp. $\left| {\bf{1}} \right\rangle$) into $(\left| {\bf{0}} \right\rangle +\left| {\bf{1}} \right\rangle )/{\sqrt{2}}$ (resp. $(\left| {\bf{0}} \right\rangle -\left| {\bf{1}} \right\rangle )/{\sqrt{2}}$). The CX gate is a generalization of the classical XOR gate, since the action of the gate may be summarized as $\left| {{\boldsymbol{A}},{\boldsymbol{B}}} \right\rangle \rightarrow |{\boldsymbol{A}}, {\boldsymbol{B}} \oplus {\boldsymbol{A}}\rangle$, where $\oplus$ is addition modulo two, which is exactly what the XOR gate does. That is, the control qubit and the target qubit are XORed and stored in the target qubit. Here $\left| {{\boldsymbol{A}},{\boldsymbol{B}}} \right\rangle$ is a shorthand of the product state $\left| {\boldsymbol{A}} \right\rangle \left| {\boldsymbol{B}} \right\rangle =\left| {\boldsymbol{A}} \right\rangle \otimes \left| {\boldsymbol{B}} \right\rangle$. We use an SWAP gate to exchange the states between two adjacent qubits, and multiple operations simulate moving non-adjacent qubits to adjacent positions. An SWAP gate can be implemented by three CX gates, or by inserting four H gates to change the direction of the middle CX gate, as illustrated in Fig.2.

Figure  1.  Symbols of two quantum gates and their matrices.

下载: 全尺寸图片 幻灯片

Figure  2.  Implementing an SWAP gate by CX gates and H gates.

下载: 全尺寸图片 幻灯片

In a quantum circuit, each line represents a wire. The wire does not necessarily correspond to a physical wire but may correspond to the passage of time or a physical particle that moves from one location to another through space. The interested reader can find more details of these gates from the standard textbook^[30]. The execution order of a quantum logical circuit is from left to right. The width of a circuit refers to the number of qubits in the circuit. The depth of a circuit refers to the number of layers executable in parallel. For example, the depth of the circuit in Fig.3(a) is 6, and the width is 5. We refer to a circuit with the number of 2-qubit gates no more than 100 as a small-scale circuit, a circuit with the number of 2-qubit gates more than 1000 as a large-scale circuit, and the rest are medium-scale circuits. It is unnecessary to consider quantum gates acting on single qubits since 1-qubit gates are local^[22], which do not need to move the involved qubits for gate applications.

Figure  3.  (a) Original quantum circuit. (b) Logical interaction graph of (a).

下载: 全尺寸图片 幻灯片

In the current work, we mainly consider the physical circuits of the IBM Q series, called coupling graphs. Let ${\cal{CG}}=(V_{{\cal{C}}}, E_{{\cal{C}}})$ denote the coupling graph of a physical device, where $V_{{\cal{C}}}$ is the set of physical qubits and $E_{{\cal{C}}}$ is the set of edges representing the connectivity between qubits related by CX gates. Figs.4(a)–4(e) are the coupling graphs of the 5-qubit IBM QX2, IBM QX4, 16-qubit IBM QX3, IBM QX5, and the 20-qubit IBM Q Tokyo, respectively. The control of one qubit to a neighbor is unilateral, but for IBM Q Tokyo the control between two adjacent qubits is bilateral. The direction in each edge indicates the control direction of each 2-qubit gate, and 2-qubit gates can only be performed between two adjacent qubits.

Figure  4.  Coupling graphs of IBM Q series. (a) IBM QX2. (b) IBM QX4. (c) IBM QX3. (d) IBM QX5. (e) IBM Q Tokyo.

下载: 全尺寸图片 幻灯片

Given an interaction graph ${\cal{IG}}$, a coupling graph ${\cal{CG}}$, an initial mapping $\tau$, and a CX gate ${\boldsymbol{g}}= \langle q_{{\rm{c}}},q_{{\rm{t}}} \rangle$ where $q_{{\rm{c}}}$ is the control qubit and $q_{{\rm{t}}}$ is the target qubit, if the gate ${\boldsymbol{g}}$ is executable on coupling graph ${\cal{CG}}$, then $\langle\tau[q_{{\rm{c}}}],\tau[q_{{\rm{t}}}] \rangle$ should be a directed edge on ${\cal{CG}}$.

Example 1. Consider the logical interaction graph ${\cal{IG}}$ and a coupling graph ${\cal{CG}}$ shown in Fig.3(b) and the blue part of Fig.4(e). Let the initial mapping be as follows,

Then the 2-qubit gate ${\boldsymbol{g}}_{0}=\langle q_{2},q_{1}\rangle$ is not executable, since the edge $\langle \tau[q_{2}],\tau[q_{1}] \rangle$ $= \langle Q_{6},Q_{0} \rangle$ does not exist in ${\cal{CG}}$. However, the gate ${\boldsymbol{g}}_{1}=\langle q_{3},q_{4} \rangle$ is executable, since the edge $\langle \tau[q_{3}],\tau[q_{4}] \rangle = \langle Q_{5},Q_{11} \rangle$ exists in ${\cal{CG}}$.

4.   Qubit Mapping

Assume that the input circuit has only 1-qubit gates and CX gates^{[31, 32]}. We expect to find a qubit mapping algorithm that, when given an input circuit, can produce an output circuit with a small number of additional gates in an acceptable amount of time. Roughly speaking, we propose a method of qubit mapping with the following three steps.

$1)$ Preprocessing. This step includes extracting the interaction graph from the input circuit and calculating the shortest paths of the coupling graph.

$2)$ Isomorphism and Completion. First, the subgraph isomorphism algorithm is used to find a set of partial initial mappings^[7]. Then we perform a mapping completion to process the remaining nodes that do not satisfy all isomorphism requirements, according to the connectivity between the unmapped nodes and the mapped ones.

$3)$ Adjustment. After the second step, some logically adjacent nodes may be mapped to physically non-adjacent nodes, therefore, the quantum circuit is not executable on the coupling graph. We use a tabu search based adjustment algorithm to generate circuits that can be physically executed.

4.1   Preprocessing

In the preprocessing step, we adjust the input circuit described by an openQASM program^[33] to extract the interaction graph from the input circuit and calculate the shortest paths of the coupling graph.

Quantum gates acting on different qubits can be executed in parallel. The notation ${\cal{L}}({\cal{C}})=\{{\cal{L}}_{0},$ ${\cal{L}}_{1}, \ldots, {\cal{L}}_{n}\}$ denotes the layered form of circuit ${\cal{C}}$, where ${\cal{L}}_{i} \ (0 \leqslant i \leqslant n)$ stands for a set of quantum gates that can be executed in parallel. The quantum gate sets separated by the dotted lines in Fig.3(a) are the following: ${\cal{L}}_{0}=\{{\boldsymbol{g}}_{0},{\boldsymbol{g}}_{1}\},{\cal{L}}_{1}=\{{\boldsymbol{g}}_{2}\}, {\cal{L}}_{2}=\{{\boldsymbol{g}}_{3},{\boldsymbol{g}}_{4}\},$${\cal{L}}_{3}=\{{\boldsymbol{g}}_{5},{\boldsymbol{g}}_{6}\},{\cal{L}}_{4}=\{{\boldsymbol{g}}_{7}\},{\cal{L}}_{5}=\{{\boldsymbol{g}}_{8}\}$.

At the same time of layering, we generate an interaction graph ${\cal{IG}}=(V_{ {\cal{I}}}, E_{{\cal{I}}})$, which is an undirected graph with $V_{{\cal{I}}}$ being the set of vertices, and $E_{{\cal{I}}}$ the set of undirected edges that denotes the connectivity between qubits related by CX gates. Given a coupling graph and assuming that the distance of each edge is 1, we use the Floyd-Warshall algorithm^[34] to calculate the shortest distance matrix, with ${{D}}[Q_{{\rm{c}}}][Q_{{\rm{t}}}]$ denoting the shortest distance from $Q_{{\rm{c}}}$ to $Q_{{\rm{t}}}$.

Consider a CX gate ${\boldsymbol{g}}= \langle q_{{\rm{c}}},q_{{\rm{t}}} \rangle$. If $q_{{\rm{c}}}$ and $q_{{\rm{t}}}$ are mapped to $Q_{{\rm{c}}}$ and $Q_{{\rm{t}}}$, respectively, then the cost of executing ${\boldsymbol{g}}$ under the shortest path is denoted by $cost_{\boldsymbol{g}}=7 \times({{D}}[Q_{{\rm{c}}}][Q_{{\rm{t}}}]-1)$ on devices with unilateral control. For IBM Q Tokyo, the cost is $cost_{\boldsymbol{g}}=3 \times({{D}}[Q_{{\rm{c}}}][Q_{{\rm{t}}}]-1)$.

Example 2. Consider the QX5 coupling graph (cf. Fig.4(d)). Given a CX gate ${\boldsymbol{g}} = \langle q_{1}, q_{2} \rangle$, with $q_{1}$ mapped to $Q_{6}$ and $q_{2}$ mapped to $Q_{13}$, the shortest distance between them is ${{D}}[Q_6][Q_{13}]=3$. There are three shortest paths of moving from $Q_{6}$ to an adjacent position of $Q_{13}$: $\pi_{0}={Q_{6}\rightarrow Q_{5} \rightarrow Q_{4} \rightarrow Q_{13}},$ $\pi_{1}={Q_{6}\rightarrow Q_{5} \rightarrow Q_{12} \rightarrow Q_{13}},$ $\pi_{2}=Q_{6}\rightarrow Q_{11} \rightarrow Q_{12} \rightarrow Q_{13}.$ Their costs are given by $cost_{\pi_{0}}=18,\ cost_{\pi_{1}}=14,$ and $cost_{\pi_{2}}=14,$ respectively. Here $cost_{\pi_i}$ for $0\leqslant i\leqslant 2$ stands for the cost of swapping the qubits $Q_{6}$ to $Q_{13}$ along the path $\pi_i$.

4.2   Isomorphism and Completion

Generally speaking, in a coupling graph, it is almost impossible to find a subgraph that exactly matches the interaction graph. We regard the mapping with the largest number of mapped nodes as a good partial mapping. IMSM compares various compositions of several state-of-the-art subgraph isomorphism algorithms. Since IMSM cannot process disconnected graphs, we manually create connected graphs by linking isolated nodes to the ones with the largest degree in the interaction graph. Note that this does not change the architecture of the original circuit.

The input of Algorithm 1 is a coupling graph ${\cal{CG}}$, an interaction graph ${\cal{IG}}$, and a partial mappings set $T$. Line 2 selects the largest number $l$ of mapped nodes, and the partial mappings with $l$ mapped nodes are used by the candidate set. Lines 3–22 complete the partial mappings. The function $len(\tau)$ returns the size of $\tau$. In line 5, we initialize an empty queue $V$, which stores unmapped logical qubits, traverse the mapping $\tau$, and add the unmapped qubits to $V$. We then loop until $V$ is empty, and all logical qubits are mapped to physical qubits. Line 7 takes out the first element in $V$ to $q$. Line 8 gets the adjacency matrix of ${\cal{CG}}$. Line 9 initializes a list $U$, sorted by descending degree of connectivity to $q$. Lines 10–20 traverse $U$ and select the node $U[0]$ that has been mapped to the physical node $Q$ in the coupling graph and has the largest number of logical connections to $q$ in $U$. Line 13 deletes the node $U[0]$ from $U$. Lines 15–17 select the node $k$ adjacent to $Q$ in the adjacency matrix and map $q$ to that node. Finally, we generate a dense mapping.

Example 3. Consider the interaction graph shown in Fig.3(a) and the coupling graph in Fig.4(e). Suppose we have a partial mapping set $T=\{\tau_{0},$ $\tau_{1}, \ldots, \tau_{n}\}$. We take one of the partial mappings as an example.

where $q_{1}\rightarrow -1$ means that $q_{1}$ is not mapped to any physical qubit, therefore we need the mapping completion algorithm. The maximum number of mapped nodes is 4. We demonstrate how $\tau_{0}$ is completed. We add all unmapped nodes to the queue $V$; in this example, we have $V=\{q_{1}\}$. Then we loop until $V$ is empty. We pop the first element $q_1$ of $V$, get the adjacency matrix of the target graph, and the candidate nodes list $U=\{q_{3},q_{2},q_{4},q_{0}\}$. Next, we traverse $U$ and take out the first element $q_{3}$ in $U$, and calculate the physical node $Q_{5}$ as $\tau_0[q_{3}]=Q_{5}$. Finally, we map $q_1$ to the node connected to $q_3$ but not yet mapped. In this example, it can be directly mapped to $Q_{0}$. In the end, we obtain the mapping $\tau_{0}=\{q_{0}\rightarrow Q_{10}, q_{1}\rightarrow Q_{0}, q_{2}\rightarrow Q_{6}, q_{3}\rightarrow Q_{5},q_{4}\rightarrow Q_{11}\}.$

4.3   Adjustment

4.3.1   Tabu Search

Tabu search uses a tabu list to avoid searching repeated spaces and deadlock and amnesty rules to jump out of the local optimum to ensure the diversity of transformed results. Our circuit adjustment mainly relies on the tabu search algorithm, aiming to adjust those large-scale circuits that the existing algorithms are difficult to process and generate a circuit closer to the optimal solution.

The calculation of the candidate set is shown in Algorithm 2. The input $M_{{\rm{p}}}$ is a mapping from physical qubits to logical ones, where $j = M_{{\rm{p}}}[i]$ means that the $i$-th physical qubit is mapped to the $j$-th logical qubit. The set $M_{{\rm{l}}}$ denotes the mapping of logical qubits to physical ones, where $j = M_{{\rm{l}}} [i]$ means that the $i$-th logical qubit is mapped to the $j$-th physical qubit. The set ${\cal{L}}$ includes all the gates in the current layer, and the output is a candidate mapping set of the current mapping. The set $E$ and the matrix ${\boldsymbol{D}}$ contain the shortest paths and distances of all nodes in the coupled graph, respectively. Lines 3–7 delete the gate ${\boldsymbol{g}}$ that can be executed in ${\cal{L}}$ under the current mapping and gather the control qubit $q_{{\rm{c}}}$ and target qubit $q_{{\rm{t}}}$ of gate ${\boldsymbol{g}}$ that cannot be executed into the set $B$. Lines 8–24 traverse gates ${\boldsymbol{g}}$ in ${\cal{L}}$, and calculate the shortest paths between the nodes of ${\boldsymbol{g}}$. If the endpoints $e.s$ and $e.t$ of edge $e$ intersect with $B$ on the shortest path, then $e$ is an element of the candidate set. Lines 14–20 update the mapping after the swap. Lines 21–24 generate a new candidate solution. Line 22 stores the swapped edges that will be used in the output circuit, and line 23 calculates the swap scores using an evaluation function.

Example 4. Let us consider the mapping

with ${\cal{L}}_{0}=\{{\boldsymbol{g}}_{0},{\boldsymbol{g}}_{1}\}$, $cost_{{\boldsymbol{g}}_{1}}=0$, and $cost_{{\boldsymbol{g}}_{0}}=3$. The gate ${\boldsymbol{g}}_{1}$ can be executed directly in the $\tau_{0}$ mapping, therefore we delete it from ${\cal{L}}_{0}$, but ${\boldsymbol{g}}_{0}$ cannot be executed in the mapping $\tau_{0}$. The nodes that cannot be executed join the set $B=\{q_{2}, q_{1}\}$. The set of shortest paths is

We traverse the shortest paths and calculate the candidate set. The current candidate set is $\{(Q_{6},Q_{1}),$ $(Q_{1},Q_{0}),$ $(Q_{6},Q_{5}),$ $(Q_{5},Q_{0}) \}$.

TSA takes a layered circuit and an initial mapping as input and outputs a circuit that can be executed in the specified coupling graph, as shown in Algorithm 3. The adjusted circuit mapping of each layer is used as the initial mapping of the next layer. Line 1 regards the initial mapping $\tau_{{\rm{ini}}}$ as the best mapping $\tau_{{\rm{best}}}$. Lines 3–12 cyclically check whether all the gates in the current layer can be executed under the mapping $\tau_{{\rm{best}}}$. If all the gates are executable or the number of iterations reaches the given bound, the search is completed. Otherwise, the search continues. Line 4 gets the current mapping candidate, and line 7 finds the best mapping in the candidate set. Note that if the edge swapped by a candidate appears in the tabu list, the candidate will be removed from the candidate set. Then from the remaining candidates, we choose a mapping with the lowest cost. Line 9 takes the amnesty rules. If the best candidate is not found, the amnesty rules will select the mapping with the lowest cost in the candidate set as the best mapping. Lines 10–12 update the best mapping $\tau_{{\rm{best}}}$ and insert the swapped edge performed by the best mapping to the tabu list $tb$. The motivation is to execute the generated circuit in parallel as much as possible and to avoid swapping the edges in the tabu list. Then it will check whether the termination condition of the algorithm is satisfied. The condition determines whether the number of iterations reaches the given bound, or the current mapping ensures all the gates in the current layer can be executed.

4.3.2   Evaluation Functions with Look Ahead

We propose three evaluation functions: one introduces CCA; one uses the number of additional gates in the generated circuit as an evaluation criterion as given in (1); and the last one uses the depth of the generated circuit as an evaluation criterion as given in (2). They give rise to three variants of TSA called TSA_cca, TSA_num, and TSA_dep, respectively.

CCA has mainly been used for Boolean Satisfiability (SAT) problems. We apply the idea of CCA to adjust circuits. Let $submake$ represent the number of qubits for which two qubits are closer after an SWAP gate, and $subbreak$ represent the number of qubits for which two qubits are farther apart after an SWAP gate. We introduce $subscore=$ $submake\ \, -$ $subbreak$ into the evaluation function and adjust the weight with the Smooth Weight based Threshold (SWT) scheme^[14].

The output of the $i$-th layer, with $i$ smaller than the depth of the circuit $d$, is used as the input of the $(i+1)$-th layer. Note that any SWAP gate in the $i$-th layer will affect the mapping of the $(i+1)$-th layer. If we only consider the gate of the current layer when selecting the SWAP gate, only the requirements of the $i$ layer will be satisfied, not necessarily those of the next layer. Therefore, we take the gates from the $i$-th to the $(i+l_{{\rm{a}}})$-th layer, with $i+l_{{\rm{a}}} \leqslant d$, into consideration, where $l_{{\rm{a}}}$ is the number of look-ahead layers. It is necessary to give a higher priority to executing the gates in the $i$-th layer, therefore we introduce an attenuation factor $\delta$ to control the influence of the gates in the look-ahead layers.

Here $cost_{{\rm{num}}}(Q_{{\rm{c}}}, Q_{{\rm{t}}})$ (resp. $cost_{{\rm{dep}}}(Q_{{\rm{c}}}, Q_{{\rm{t}}})$) denotes the distance (resp. depth) of all the gates in layer ${\cal{L}}_j$ ($i\leqslant j \leqslant i+l_{{\rm{a}}}$), after swapping the state of $Q_{{\rm{c}}}$ with that of $Q_{{\rm{t}}}$. The function $Depth({\cal{L}})$ returns the depth of ${\cal{L}}$ and the notation $q_{{\rm{c}}}$ (resp. $q_{{\rm{t}}}$) stands for the control (resp. target) qubit of gate ${\boldsymbol{g}}$.

Example 5. Let us continue the previous example. We select the one with the lowest evaluation score from the candidate set. Assuming $\delta=0.5$ and $l_{{\rm{a}}}=2$, for ${\cal{L}}_{1}=\{{\boldsymbol{g}}_{2},{\boldsymbol{g}}_{0}\}$, the candidate set is $\{(Q_{6},Q_{1}),$ $(Q_{1},Q_{0}), (Q_{6},Q_{5}), (Q_{5},Q_{0}) \},$ and the costs are given as follows:

The algorithm chooses the first SWAP with the smallest score, and the mapping becomes $\tau_{0}=\{q_{0} \rightarrow$ $Q_{10}, q_{1}\rightarrow Q_{0}, q_{2}\rightarrow Q_{1},q_{3}\rightarrow Q_{5},q_{4}\rightarrow Q_{11}\}$.

The current mapping ensures that ${\boldsymbol{g}}_{0}$ is executable. Thus we can continue to the next layer.

4.3.3   Complexity

Given an interaction graph ${\cal{IG}}=(V_{{\cal{I}}},E_{{\cal{I}}})$ and a coupling graph ${\cal{CG}}=(V_{{\cal{C}}},E_{{\cal{C}}})$, we assume that the depth of the circuit is $d$ and there are $G$ 2-qubit gates in one layer. The candidate set consists of the edges connected to the control or target qubits, thus the size of the SWAP candidate set is $8\times G$. The worst-case time complexity is $O(d\times G\times(8\times G)^{(|E_{{\cal{C}}}|-1)})$, and the space complexity is $O(G)$.

5.   Experiments

We compare TSA with several state-of-the-art algorithms for qubit mapping, namely ZPW^[10], SABRE^[11], FiDLS^[12], and DLH^[13]. Notice that other algorithms such as SAHS^[26] and ${\rm{t}} \mid {\rm{ket}}\rangle$^[25] are not listed because Li et al.^[12] have pointed out that FiDLS is superior to SAHS and the latter outperforms ${\rm{t}} \mid {\rm{ket}}\rangle$^[26]. The implementation in Python is available online ³. All the experiments are conducted on a Ubuntu machine with a 2.2 GHz CPU and 64 GB memory. We take the logarithm $\log_{10}$ of both the $x$-axis and $y$-axis such that the experimental results are easy to observe. The time limit for each benchmark is one hour. Among the 159 benchmarks, we have considered, 158 of them are taken from some functions of RevLib^[35], and one is added by our own. This dataset has also been adopted in several related work. We believe that it is representative and our comparative experiments are carried out on it. With the 159 benchmarks, we compare TSA with ZPW, SABRE, and FiDLS on IBM Q Tokyo, and with FiDLS on Sycamore. Since the code of DLH is not available online, we only make comparison with this algorithm on the number of inserted additional gates but not the running time. Note that SABRE uses a random initial mapping, thus for every benchmark we execute it five times, each with a different initial mapping, and report the best result out of the five trials. TSA uses unsorted candidates, and thus we execute it five times and take the best result. Other algorithms are deterministic, therefore they only run once. Fig.5 illustrates the entire process of our experiments. Below we go through it in more detail.

Figure  5.  Sketch of the experiments.

下载: 全尺寸图片 幻灯片

Firstly, we test TSA with fixed and variable look-ahead parameter $l_{{\rm{a}}}$. In Fig.6, different colors represent the logarithms of the number of additional gates. The lower the points in the figure, the fewer additional gates inserted. As for the look-ahead parameter $l_{{\rm{a}}}$, the optimal parameter for each circuit may be different. We have done thousands of experiments and found that when $l_{{\rm{a}}}=2$, the number of additional gates is relatively small for all benchmarks. It means that a 2-layer look-ahead already gives a good performance for TSA.

Figure  6.  Impact of the look-ahead parameter $l_{{\rm{a}}}$ on search results.

下载: 全尺寸图片 幻灯片

In Fig.7, we compare ${\rm{TSA}}_{{\rm{cca}}}$, ${\rm{TSA}}_{{\rm{dep}}}$ and ${\rm{TSA}}_{{\rm{num}}}$ using the 159 benchmarks mentioned above. Compared with ${\rm{TSA}}_{{\rm{cca}}}$ (resp. ${\rm{TSA}}_{{\rm{num}}}$), the depth of the generated circuits by ${\rm{TSA}}_{{\rm{dep}}}$ is reduced by 2.37% (resp. 3.42%) on average. Compared with ${\rm{TSA}}_{{\rm{cca}}}$ (resp. ${\rm{TSA}}_{{\rm{dep}}}$), the number of additional gates by ${\rm{TSA}}_{{\rm{num}}}$ is reduced by 2.69% (resp. 9.56%) on average. Therefore, it is preferable to use either ${\rm{TSA}}_{{\rm{dep}}}$ or ${\rm{TSA}}_{{\rm{num}}}$, depending on the optimization objective to be either the depth or the number of additional gates of the resulting circuits.

Figure  7.  Comparison of the number of additional gates inserted by ${\rm{TSA}}_{{\rm{dep}}}$, ${\rm{TSA}}_{{\rm{cca}}}$, and ${\rm{TSA}}_{{\rm{num}}}$.

下载: 全尺寸图片 幻灯片

Secondly, we use the benchmarks^[13] to compare ${\rm{TSA}}_{{\rm{num}}}$ with DLH. Note that two heuristic cost functions MCPE and MCPE_OP are used in DLH. Since there is no code available online for DLH, we only compare the number of additional gates inserted with the circuits^[13], as shown in Table 1. Compared with MCPE and MCPE_OP, ${\rm{TSA}}_{{\rm{num}}}$ reduces the total number of additional gates by 27.32% and 12.42%, respectively.

Table  1.  Comparison of MCPE, MCPE_OP and ${\rm{TSA}}_{{\rm{num}}}$

Benchmark	$n$	$G$	$G_0$ (MCPE)	$G_1$ (MCPE_OP)	$G_2$ (${\rm{TSA}}_{{\rm{num}}}$)	$\Delta_0(\%)$	$\Delta_1 (\%)$
4mod5-v1_22	5	21	0	0	0	0.00	0.00
mod5mils_65	5	35	0	0	0	0.00	0.00
alu-v0_27	5	36	3	3	6	–100.00	–100.00
decod24-v2_43	4	52	0	0	0	0.00	0.00
4gt13_92	5	66	21	21	0	100.00	100.00
ising_model_10	16	786	0	0	0	0.00	0.00
ising_model_13	16	786	0	0	0	0.00	0.00
ising_model_16	16	786	0	0	0	0.00	0.00
qft_10	10	200	39	39	57	–46.15	–46.15
qft_16	16	512	225	192	189	16.00	1.56
rd84_142	15	343	153	108	99	35.29	8.33
adr4_197	13	3439	1566	1224	1029	34.29	15.93
radd_250	13	3213	1353	1047	852	37.03	18.62
z4_268	11	3073	1071	855	915	14.57	–7.02
sym6_145	14	3888	1017	1017	681	33.04	33.04
misex1_241	15	4813	2118	1098	1032	51.27	6.01
rd73_252	10	5321	2352	2193	1629	30.74	25.72
cycle10_2_110	12	6050	2226	1968	1890	15.09	3.96
square_root_7	15	7630	2061	1788	1509	26.78	15.60
sqn_258	10	4459	3708	3057	3093	16.59	–1.18
rd84_253	12	13658	6411	5697	4605	28.17	19.17
co14_215	15	17936	5634	5062	6813	–20.93	–34.59
sym9_193	10	34881	15420	13746	12315	20.14	10.41
urf5_158	9	164416	69852	58947	56253	19.47	4.57
hwb9_119	10	207775	93219	89355	78753	15.52	11.87
urf4_187	11	512064	220329	168366	141768	35.66	15.80
Sum	–	1307223	428778	355782	311598	27.32	12.42
Note: $n$ is the number of qubits, $G$ is the number of gates in the input circuit, $G_0$–$G_2$ are the numbers of additional gates inserted by MCPE, MCPE_OP and TSAnum, respectively, and $\Delta_i=(G_i-G_2)/G_i$.

下载: 导出CSV 

| 显示表格

Thirdly, we compare the combinations of several algorithms for inserting fewer additional gates. In order to visualize the differences between ZPW, FiDLS, SABRE, and TSA, we have plotted a series of figures available online as supplementary materials ⁴. We use the initial mapping and adjustment algorithms from ZPW^[10], SABRE^[11], FiDLS^[12], and TSA.

In Table 2, we compare the performance of the four initial mapping algorithms of ZPW, SABRE, FiDLS, and TSA under the specific adjustment algorithms. For example, in the first row, the adjustment algorithm is fixed to be that of ZPW; there are 115 circuits that all of the four initial mapping algorithms can successfully transform and we compare the number of additional gates. As we can see, the initial mapping algorithm of TSA performs the best when used in conjunction with the five adjustment algorithms. It leads to a reduction of 41%, 30%, and 37% of additional gates compared with the initial mapping algorithms of ZPW, SABRE, and FiDLS.

Table  2.  Comparison of the Initial Mapping Algorithms of ZPW, SABRE, FiDLS, and TSA

Algorithm	$N$	$G$	$G_0$	$G_1$	$G_2$	$G_3$	$\Delta_0 (\%)$	$\Delta_1 (\%)$	$\Delta_2 (\%)$
ZPW	115	63666	29640	24951	27651	17412	41.26	30.22	37.03
SABRE	108	77790	28671	26079	26412	16068	43.96	38.39	39.16
FiDLS	120	209433	29484	28434	30195	25950	11.99	8.74	14.06
${\rm{TSA}}_{{\rm{num}}}$	120	163485	54969	52512	62817	45948	12.50	26.85	18.59
${\rm{TSA}}_{{\rm{cca}}}$	120	163485	57777	53922	61668	46305	19.86	14.13	24.91
Note: $N$ is the number of circuits that all the four initial mapping algorithms can successfully transform, $G$ is the number of gates in the input circuits, $G_0$–$G_3$ are the numbers of additional gates inserted by ZPW, SABRE, FiDLS, and TSA, respectively, and $\Delta_i=(G_i-G_3)/G_i$.

下载: 导出CSV 

| 显示表格

We then compare the five adjustment algorithms from ZPW, SABRE, FiDLS, ${\rm{TSA}}_{{\rm{num}}}$, and ${\rm{TSA}}_{{\rm{cca}}}$ under specific initial mapping algorithms in Table 3. FiDLS gives rise to the fewest additional gates. For example, in the second row, SABRE is used as the adjustment algorithm, 16632 (resp. 12072) gates are inserted under the initial mapping of SABRE (resp. TSA). The SABRE adjustment algorithm combined with the initial mapping provided by TSA has fewer gates inserted than the SABRE initial mapping algorithm in these benchmarks. This shows that the initial mapping of TSA is better than that of SABRE. FiDLS uses a deep search on the circuits, calculates the full permutation of all edges, and then selects the best among all the permutations according to an evaluation function. FiDLS takes large-scale search space and long search time for large-scale circuits. Overall, TSA performs well on large-scale circuits, trading off additional gates and runtime.

Table  3.  Comparison of the Adjustment Algorithms of ZPW, SABRE, FiDLS, ${\rm{TSA}}_{{\rm{num}}}$, and ${\rm{TSA}}_{{\rm{cca}}}$

Algorithm	$N$	$G$	$G_0$	$G_1$	$G_2$	$G_3$	$G_4$	$\Delta_0 (\%)$	$\Delta_1 (\%)$	$\Delta_2 (\%)$	$\Delta_4 (\%)$
ZPW	94	29443	14472	11244	4938	10173	10389	29.71	9.53	–106.01	2.08
SABRE	105	49987	19053	16632	6204	12072	11904	36.61	27.41	–94.58	–1.41
FiDLS	109	105428	45813	31011	16668	37800	37851	17.49	–21.89	–126.78	0.13
TSA	124	150464	49620	30447	19068	40461	40629	18.46	–32.89	–112.19	0.41
Note: $N$ is the number of circuits that all the five adjustment algorithms can successfully transform, $G$ is the number of gates in the input circuits, $G_0$–$G_4$ are the numbers of additional gates inserted by ZPW, SABRE, FiDLS, TSA$_{\rm{num}}$, and TSA$_{\rm{cca}}$, respectively, and $\Delta_i=(G_i-G_3)/G_i$.

下载: 导出CSV 

| 显示表格

Fourthly, we compare the overall performance of ${\rm{TSA}}_{{\rm{num}}}$ and ${\rm{TSA}}_{{\rm{cca}}}$ with SABRE and FiDLS on IBM Q Tokyo. We test 159 circuits, including 66 small-scale circuits, 49 medium-scale circuits, and 44 large-scale ones. Note that in Table 4 and Fig.8 we do not display the data for ZPW. Instead, we make comparison with SABRE because it is already shown that SABRE is much more scalable than ZPW^[11]. In Fig.8, the number of additional gates introduced by the blue bars is the largest, followed by the red ones. We can see that the yellow bars are the shortest when the $x$-axis is greater than 3, indicating that FiDLS has inserted the fewest gates in the large-scale circuits. The green bars are for ${\rm{TSA}}_{{\rm{num}}}$. The number of additional gates it introduces is slightly larger than that of FiDLS. It can also be seen from Table 4 that ${\rm{TSA}}_{{\rm{num}}}$ takes much less time than FiDLS in general. SABRE successfully transforms 144 circuits, including all the small-scale and medium-scale circuits, and 29 large-scale ones, which takes 12436 seconds. FiDLS successfully transforms 159 circuits, which takes 63841 seconds. ${\rm{TSA}}_{{\rm{num}}}$ and ${\rm{TSA}}_{{\rm{cca}}}$ are much faster, as they successfully transform all the 159 circuits, taking 2465 seconds and 2523 seconds, respectively. Compared with SABRE, the number of additional SWAP gates generated by ${\rm{TSA}}_{{\rm{num}}}$ is reduced by 51% on average, among the 115 small-scale and medium-scale circuits that both of them can successfully transform.

Table  4.  Comparison of Runtime and Number of Circuits Successfully Transformed by SABRE, FiDLS, ${\rm{TSA}}_{{\rm{num}}}$, and ${\rm{TSA}}_{{\rm{cca}}}$

Scale	$N$	$G$	SABRE				FiDLS				${\rm{TSA}}_{{\rm{num}}}$				${\rm{TSA}}_{{\rm{cca}}}$
			$N_0$	$G_0$	$t_0$ (s)		$N_1$	$G_1$	$t_1$ (s)		$N_2$	$G_2$	$t_2$ (s)		$N_3$	$G_3$	$t_3$ (s)
Small	66	5997	66	2301	2		66	1329	7		66	894	16		66	897	21
Medium	49	21618	49	10218	22		49	5328	90		49	5199	57		49	5280	62
Large	44	3289162	29	162522	12412		44	532485	63744		44	1013196	2392		44	1037427	2440
Sum	159	3312734	144	175041	12436		159	539142	63841		159	1015521	2465		159	1043604	2523
Note: $N$ is the number of test circuits, $G$ is the number of gates in the input circuits, $N_0$–$N_3$ are the numbers of circuits successfully transformed by SABRE, FiDLS, TSA$_{\rm{num}}$, and TSA$_{\rm{cca}}$ respectively, $t_0$–$t_3$ are the runtime of SABRE, FiDLS, TSA$_{\rm{num}}$, and TSA$_{\rm cca}$, respectively, and $G_0$–$G_3$ are the numbers of additional gates inserted by SABRE, FiDLS, TSA$_{\rm{num}}$, and TSA$_{\rm cca}$, respectively.

下载: 导出CSV 

| 显示表格

Figure  8.  Comparison of SABRE, ${\rm{TSA}}_{{\rm{cca}}}$, ${\rm{TSA}}_{{\rm{num}}}$ and FiDLS on IBM Q Tokyo.

下载: 全尺寸图片 幻灯片

In small-scale (resp.middle-scale) circuits, ${\rm{TSA}}_{{\rm{num}}}$ generates an average of 33% (resp. 2%) fewer additional SWAP gates compared with FiDLS. Specifically, FiDLS inserts 1329 (resp. 5328) additional gates, while the number is 894 (resp. 5199) for ${\rm{TSA}}_{{\rm{num}}}$. When dealing with large-scale circuits, although ${\rm{TSA}}_{{\rm{num}}}$ inserts more additional gates, it can convert large-scale circuits more than 25 times faster than FiDLS, as we can see in the fourth row and the $t_{2}$-column of Table 4.

Finally, we set the 53-qubit quantum processor Sycamore as our target device and compare TSA with FiDLS still on the 159 benchmarks. In each row of Table 5, the same initial mapping algorithm is used, and in each column, the same adjustment algorithm is used. Generally speaking, TSA leads to a reduction of 2%-3% for the number of inserted additional gates. In the experiment, we find that the degrees of the Sycamore nodes are small and the maximum is 4. If the degrees of nodes in the interaction graph are generally greater than the maximum degree of Sycamore, it is not very suitable to use subgraph isomorphism to generate the set of partial initial mappings. The algorithm tempts to first match the node with the largest degree. If the node with the maximum degree does not satisfy the isomorphism condition, the initial mapping generated by the subgraph isomorphism algorithm is not friendly. However, the adjustment of TSA is still very effective because the time cost is drastically lowered, going from 31896 seconds for FiDLS to 1795 seconds for ${\rm{TSA}}_{{\rm{num}}}$, that is, the latter is more than 17 times faster than the former.

Table  5.  Comparing the Initial Mapping and Adjustment Algorithms of FiDLS and TSA on Sycamore

Algorithm	FiDLS			${\rm{TSA}}_{{\rm{num}}}$			${\rm{TSA}}_{{\rm{cca}}}$		$\Delta_1 (\%)$	$\Delta_2 (\%)$
	$G_0$	$t_0$ (s)		$G_1$	$t_1$ (s)		$G_2$	$t_2$ (s)
FiDLS	2311560	31896		2245314	233		2257371	3392	2.86	2.56
TSA	2305125	31211		2234937	1795		2252271	3390	3.04	2.29
Note: The number of test circuits, $N$, is 159, the number of gates in the input circuits, $G$, is 3312734, $G_0$–$G_2$ are the numbers of additional gates inserted by FiDLS, TSA$_{\rm{num}}$ and TSA$_{\rm{cca}}$, respectively, $t_0$–$t_2$ are the runtime of FiDLS, TSA$_{\rm{num}}$, and TSA$_{\rm{cca}}$, respectively, and $\Delta_i=(G_0-G_i)/G_0$.

下载: 导出CSV 

| 显示表格

6.   Conclusions

We proposed a scalable algorithm called Tabu Search-Based Adjustment (TSA) for qubit mapping. We first used a subgraph isomorphism algorithm and a mapping completion algorithm based on the connectivity between qubits to generate a high-quality initial mapping. Then we employed a look-ahead heuristic search to adjust the mapping, which takes into account the influence of the gates yet to be processed to reduce the number of additional gates. We compared the performance of the initial mapping and adjustment algorithms of TSA with state-of-the-art algorithms ZPW, SABRE, and FiDLS, using the architectures of IBM Q Tokyo and Sycamore as the target devices. Our experimental results show that the initial mapping of TSA gives rise to fewer SWAP gates inserted and the adjustment algorithm can be obtained in an acceptable amount of time. Most small-scale and medium-scale circuits can be transformed in a few seconds. For large-scale circuits, the results can be obtained within a few minutes. In the future, we will investigate how to reduce the number of additional gates inserted and increase the speed. We will also apply the proposed method to more noisy intermediato-scale quantum (NISQ) devices.