Introduction

Quantum computing, owing to its inherent attributes of quantum superposition and quantum entanglement, has demonstrated significant potential in numerous domains, including rapid data searching and sorting1, quantum chemistry2, machine learning3,4 and cryptography5, etc. Taking the factorization of large numbers as an example6, the most powerful supercomputing, Frontier, may need hundreds of million years to decompose a 2048-bit large number, while a general quantum computer is supposed to accomplish the same task in a few seconds merely. The lowest resource (qubits) estimate for the 2048 bit integer factorization to date is 3 million ion-trap qubits7.

With the release of 127, 49, and 72 qubit quantum devices by IBM, Intel, and Google, respectively, the NISQ era, a new era of quantum technology development, has come, indicating a crucial advancement toward the future’s more potent and powerful quantum technologies8. Unfortunately, the existing limitations of quantum technology hinder its further progress. Specifically, the control qubit and target qubit of a two-qubit gate can only interact with adjacent specified qubit pairs.

Figure 1 shows the qubit topology of the quantum device, demonstrates various connecting ways between the coupled qubits9. As shown in the figure, all the qubits are placed on a planar geometry and bidirectional arrows are used to represent the connections between two qubits. Due to the limitations of the coupler, a physical qubit can only be connected to its neighboring physical qubit10. Usually, when designing quantum algorithms, the designers do not consider the limitations of the devices, allowing multiple-qubit gates to act on arbitrary qubits. However, a problem is ignored during this process. In the actual situation, quantum devices have their limitations regarding qubit interactions. It means that not all qubits can be connected, and different devices have unique topology diagrams for qubit connections.

Figure 1
figure 1

Qubit coupling diagram of IBM Q device. (a) IBM Q Santiago, (b) IBM Q Ourense, (c)Yorktown IBM QX2 v2.2.0, (d) IBM Q20 Tokyo, (e) IBM Q16 Melbourne.

Full size image

In the past few years, intrigued by the qubit mapping problem, more and more scholars have devoted themselves to further its study11,12. When tackling it, qubit mapping requires considering a series of qubit gate operations in a circuit and enabling all double-qubit gates to comply with the coupling restrictions of a quantum device by inserting SWAP gates. However, the insertion of SWAP gates leads to an increase in quantum circuit depth, noise, and quantum computation time, inevitably jeopardizing the fidelity of the algorithm13. As a result, an efficient algorithm for mapping qubits in logic circuits to qubits in physical chips is urgently needed, to minimize the impact of side effects, like noise, and maintain the fidelities of quantum computation.

To address the qubit mapping problem, researchers have proposed various methods, which can be broadly categorized into two types in general. The first class of methods formulates the qubit mapping problem as an equivalent mathematical problem. Wille et al.14 use inference engines such as Boolean satisfiability to obtain the minimum solution, while Bhattacharjee et al.15 propose an integer linear programming formulation to achieve the minimum logical depth of a quantum circuit. In the second class of methods, heuristic algorithms are mainly adopted for problem-solving. Among these layers, a heuristic approach is used to further screen out the optimal SWAP gate insertion choices between layers during the mapping process. Li et al.16 propose a bi-directional heuristic search algorithm based on SWAP using a new backward traversal technique to optimize the initial mapping globally and introduce a decay effect to achieve a trade-off between depth and gate number for the whole algorithm. Besides, regarding the problem of finding a qubit mapping as a subgraph isomorphism problem, Matsuo et al.17 suggest an SAT-based method for finding an excellent initial mapping for quantum circuits, which is combined with a heuristic clustering algorithm can effectively reduce the number of inserted SWAP gates. Eesa Nikahd et al.18 propose an automated method called Window-based Quantum Circuit Partition, which aims to minimize the communication cost between processing units in distributed quantum computing.

Currently, most practical qubit-mapping methods for NISQ devices are based on heuristic algorithms19. Therefore, this paper focuses on heuristic-based qubit 10 allocation methods. Although the available heuristic algorithms usually solve the qubit mapping problem in an acceptable time, some limitations still leave adverse effects20. For example, in the literature21, it is stated that there is more room to improve the generation of the initial qubit mapping. A single division by distance is inappropriate, as it may lead to missing the optimal mapping in many cases. In the literature13, a prospective approach is adopted to evaluate the cost of SWAP insertion. However, the window size of the prospective technique is fixed, which means that without considering the internal details of the quantum circuits, the optimal SWAP operations would be missed in many cases.

Given all that, this paper proposes the dynamic and look-ahead-based qubit mapping method for more efficiently solving the qubit mapping problem caused by the connectivity constraints between the physical qubits of NISQ devices. More specifically, the proposed method is a qubit initial mapping algorithm based on the idea of maximizing physical bit connectivity, which generates a set of qubit initial mappings according to the input quantum circuit information and the selected topology map. The algorithm not only optimizes the expression of physical bit connectivity by preferentially selecting the physical qubits adjacent to the mapped logical qubits but also takes into account the interactions between qubits as well as the order in which the quantum gates are executed, thus generating a better initial qubit mapping.

However, due to the limitation of quantum hardware, the coupling relationship between physical bits is often limited, and the generated initial mapping can only satisfy part of the coupling relationship. For this reason, we propose a heuristic search algorithm based on SWAP, which employs a multi-window look-ahead strategy and takes the Minimal Subsequent Positive Effect (MSPE) of the SWAP operation as a heuristic cost function. This heuristic algorithm dynamically searches for the optimal SWAP insertion strategy. Compared with the IBM qubit mapping strategy, the method in this paper reduces the number of SWAP gates inserted on the IBM Q16 Melbourne by up to 30.36% and reduces the number of SWAP gates by 12.94% on average. Compared to the SABRE algorithm, the method in this paper inserts up to 23.95% fewer SWAP gates on IBM Q20 Tokyo, with an average of 14.2% fewer SWAP gates.

Results

To better evaluate the effectiveness of the qubit mapping algorithm proposed in this paper, this algorithm is compared with the three methods integrated with the IBM Q Quantum Cloud platform, the SABRE16 algorithm, and the algorithms proposed in the literature21.The algorithms integrated with the IBM Q Quantum Cloud platform have been credited for its high credibility and reliability12, Sabre is a classical and representative algorithm, and21 is the basis of algorithm improvement in this paper. Therefore, they are selected as the baselines for the experiments in this paper.

Comparison with IBM solutions

Table 1 lists the experimental results compared with the BasicSwap qubit-mapping strategy, which is the default mapping algorithm used in IBM Q. The first three columns are the information related to the input circuit, i.e., the name of the circuit (Name), the number of qubits (n), and the number of gates (G). The 5th and 6th columns indicate the number of basic gates of the hardware-compatible circuits obtained using the algorithm proposed in this paper and BasicSwap, respectively, and the 7th column indicates the difference between the 5th and 6th columns in percentage.

Table 1 Compared with IBM Q’s BasicSwap qubit-mapping strategy.
Full size table

As shown in Table 1, the algorithm in this paper reduces the total number of basic gates in the mapped circuit. In the BasicSwap algorithm, the initial mapping of logical qubits is generated sequentially, e.g., logical qubit q0 is assigned to physical qubit Q0, logical qubit q1 is assigned to physical qubit Q1, and so on. However, in most cases, there are better choices than such an assignment without negatively affecting the subsequent SWAP-gate insertion. Instead, the better initial mapping strategy for quantum circuits based on the IQM method proposed in the previous section reduces the number of subsequent SWAP gate insertions, alleviating the potential risk. Overall, the method in this paper reduces the number of SWAP gates by 12.94% on average and up to 30.36%.

In addition, other algorithms are integrated into IBM Q, such as LookaheadSwap and StochasticSwap, which can insert SWAP gates into the quantum circuits to make them compatible with the coupling mapping. To further the study, the qubit mapping algorithm proposed in this paper is compared with LookaheadSwap and StochasticSwap, with the experimental results presented in Table 2. The table’s first column is the name of the benchmark circuit, and the second column is the number of SWAP gates added by the algorithm in this paper. The third to fifth and sixth to eighth columns denote the number of SWAP gates added by the LookaheadSwap and StochasticSwap methods, respectively, for optimization levels ranging from 1 to 3. A higher optimization level means that the circuit is optimized at the cost of a longer execution time.

Table 2 Comparison with IBM’s LookaheadSwap and StochasticSwap strategies.
Full size table

The LookaheadSwap method takes a forward-looking approach to evaluate the impact of SWAP-gate insertion. However, the limit in this forward-looking approach is adopting a fixed-size window, which is challenging to satisfy all quantum circuits in the actual situation to optimize qubit mapping. In this paper, the size of the forward-looking window is flexible, and hence, it can find a better SWAP-gate insertion strategy. As shown in Table 2, the number of SWAPs added by the algorithm in this paper is smaller than that of the LookaheadSwap method, proving its efficiency. The StochasticSwap method maps qubit by inserting randomly selected SWAPs. However, the nature of this method cannot guarantee that an optimal solution can be obtained every run. As a result, through the comparisons, the method proposed in this paper outperforms the StochasticSwap method in terms of algorithmic stability and efficiency.

Comparison with SABRE

In this section, experiments are carried out targeting the 20 qubit IBM Q20 Tokyo quantum processor, as shown in Fig. 1d, and compared with the SABRE algorithm proposed by Li et al.16. For a fair comparison, we utilized the publicly available SABRE code on the qiskit and compared it to our experiments, and the results of the experiments are shown in Tables 3 and 4.

Table 3 Experimental results of small-scale circuits.
Full size table
Table 4 Experimental results of medium-scale circuits.
Full size table

According to the number of quantum gate operations, quantum circuits can be classified into different scales, such as small-scale, medium-scale, and large-scale circuits. The experimental results are shown in Tables 3, 4 and 5. The first column in the table is the name of the benchmark circuit, the second column is the number of qubits in the circuit, and the third column indicates the number of gates in the circuit. The fourth column, g1, labeled “SABRE”, shows the number of CNOT gates added by the SABRE algorithm, and the fifth column, t1, indicates the time required to run the SABRE algorithm. The sixth column, g2, labeled “Ours”, denotes the number of auxiliary CNOT gates added by the qubit mapping algorithm proposed in this paper, and the seventh column, t2, represents the time required to run the algorithm in this paper. The last column labeled “Comp.” indicates the gate number difference between our and the SABER algorithms.

Table 5 Experimental results of n large-scale circuit.
Full size table

As shown in Table 3, for small-scale circuits, the circuit gate number optimization effect of this paper’s algorithm and the SABRE algorithm are almost the same. As shown in Table 4, the optimization effect of this paper’s algorithm is more significant when it comes to the medium-sized circuits, with the highest optimization rate reaching 23.95%. The SABRE algorithm finds an initial mapping by iterative bi-directional routing, using the reverse traversal techniques. Next, it adopts a heuristic search scheme to reduce the number of swaps inserted during compiling the quantum program. However, the SABRE algorithm has a different initial mapping each time it is executed. We ran the algorithm 5 times and selected the best result among them. This paper uses the IQM algorithm to generate a better initial mapping and the forward-looking algorithm to insert SWAP gates efficiently without needing multiple runs.

Meanwhile, as seen from Tables 3 and 4, the algorithms proposed in this paper do not have an advantage regarding compilation time as it is not the research goal. We aim to reduce the number of gates because the noise and distortion introduced by gate operations are crucial challenges in quantum computation. Various errors such as decoherence, qubit flipping, or phase shifting may occur during the execution of gate operations, which cumulatively may lead to erroneous computational results. Reducing the number of gate operations can directly lead to less impact of noise and distortion in quantum computing systems. Hence, to improve the correctness and stability of computation, the algorithms proposed in this paper focus on the number of SWAP gates and sacrifices the compilation time performance to a certain extent.

Comparison with QCM

After comparing with the QCM algorithm in the literature21, the experimental results are acquired and shown in Table 6. In this table, the first column is the name of the reference circuit, and the second column is the number of qubits in the circuit. The third column indicates the number of gates in the circuit, while the fourth column, labeled “QCM”, g1, indicates the number of CNOT gates added by the QCM algorithm. The fifth column, t1, represents the time required to run the QCM algorithm. The sixth column, g2, labeled “Ours”, denotes the number of auxiliary CNOT gates added by the qubit mapping algorithm proposed herein, and the seventh column, t2, is for the time required to run the algorithm herein. The eighth and ninth columns labeled “Comp.” represent the number of gates and the compilation time compared between the QCM algorithm and ours.

Table 6 Comparison with QCM algorithm.
Full size table

Discussion

In this work, we proposed several methods to tackle the qubit-mapping problems. As for the qubit mapping initialization problem, this paper uses the connectivity of physical qubits and the priority of qubits to generate a relatively optimal initial qubit mapping, which avoids subsequent SWAP-gate insertions as much as possible. In addition, the proposed method mentioned of inserting SWAP gates is proven to be effective for the qubit-mapping position-update problem. The method, based on the idea of multi-window look-ahead dynamically, inserts SWAP gates efficiently. The proposed algorithms can alleviate the coupling limitation of quantum devices and reduce the cost of mapping quantum circuits to NISQ devices. It has been shown that our work can alleviate the coupling limitation of quantum devices and has more flexible prospective depth, resulting in cost reductions for qubit mapping through the diminished insertion of SWAP gates.

However, there are other factors that can affect the execution of quantum computing, such as quantum gate execution error and quantum bit coherence time. These factors can be taken into consideration in future research. Additionally, arranging and optimizing quantum gates can reduce the number of quantum gates, which not only lowers the complexity of the computation but also enhances the fidelity of the operations. This is an important direction for optimization in quantum circuit design22. Our future research direction will be to adjust the algorithms proposed in this paper to account for these factors.

Methods

As for the problem that quantum hardware only allows double-qubit gates to act between a limited number of neighboring physical bits, a qubit-mapping algorithm is proposed in this research. As shown in Fig. 2, the algorithm is mainly divided into two parts: initialization of qubit mapping (IQM) and change of qubit mapping (CQM). IQM is a mapping strategy that generates the initial qubits, while CQM selects the best SWAP-gate insertion based on the initial mapping generated by IQM to change the qubit mapping.

Figure 2
figure 2

Qubit mapping algorithm flowchart.

Full size image

In the IQM phase, the quantum gates in the quantum procedure are first decomposed into basic quantum gates that can be directly applied to the NISQ device, and the qubit priority is determined based on the number of qubits acted on by the CNOT gate. Then, based on the topology of the selected quantum device, the connectivity of the physical qubits of the device is obtained. Finally, an initial qubit mapping is generated based on the obtained qubit priority and the connectivity of the physical bits.

In the CQM stage, the CNOT gates in the quantum program are first traversed to find gates that do not meet the coupling constraints according to the initial qubit mapping strategy that has been generated. Then, a multi-window look-ahead heuristic algorithm is taken to insert SWAP gates to update the qubit mapping, and the process is looped until the end of the CNOT gate traversal.

Initialization of qubit mapping (IQM)

To further improve the effectiveness of the initial mapping algorithm, we can introduce another metric called qubit interaction. The qubit interaction takes into account the execution order of quantum gates and the interaction relationships between qubits in the quantum circuit.

Qubit interaction

A physical quantum device can be represented by its coupling graph CG, which is an undirected graph (V, E) where each qubit in the device is a node in V, and there is an edge (qi, qj) 2 E between two nodes qi and qj if they can be operated by a two-qubit gate in the device.

Definition 1

Given a quantum circuit LC = (Q, C), where Q = {q0, q1,…, qn-1} be a set of logical qubits, and the quantum circuit C = {g0, g1, ..., gm-1} is a set of ordered gates. Assign a weight wi to each qubit gate gi, and the wi is

$${w}_{i}=m-i.$$
(1)

Definition 2

For each qubit pair \(({q}_{i}\text{,}{\text{q}}_{j})\), where \({q}_{i}\text{,}{ \, {\text{q}}}_{j}\) are qubits in LC, the weight \({\text{QPI}}({q}_{i}\text{,}{\text{q}}_{j})\) is

$${\text{QPI}}\left({q}_{i}\text{,}{\text{q}}_{j}\right)=\sum_{{g}_{i}}{w}_{i},{ g}_{i}=\left({q}_{i}\text{,}{\text{q}}_{j}\right)or\left({\text{q}}_{j}\text{,}{q}_{i}\right),$$
(2)

where wi is the weight of gi.

Definition 3

Let assign qi to Qj, and the qubit interaction is

$$ {\text{QBN}}\left( {Q_{i} } \right) = \mathop \sum \limits_{i,j = 0}^{{{\text{count}}}} {\text{QPI}}\left( {M\left( {Q_{i} } \right),M\left( {Q_{j} } \right)} \right),i \ne j,Q_{i} {,}Q_{j} \mathrel\backepsilon A,{\text{Dist}}\left[ {Q_{i} } \right]\left[ {Q_{j} } \right] = 1, $$
(3)

where M(Q) refers to the logical qubit corresponding to the physical qubit Q, A denotes the set of physical qubits that have been assigned, count denotes the number of physical qubits that have been assigned, and \({\text{Dist}}[{Q}_{i}][{Q}_{j}]=1\) denotes that Qi is adjacent to Qj.

The weight (wi) of the quantum gate (gi) indicate the sequence of quantum gates, where a higher number suggests that the quantum gate is placed earlier in the sequence. The \({\text{QPI}}({q}_{i}\text{,}{ \, {\text{q}}}_{j})\) refers to the total number of the weight of a pair of qubits interact in a circuit.

Example 1

Figure 3 displays the weights of the gates in the circuit and the QPI of each qubit pair. The QPI (q0, q2) has the highest weight indicates that the gates associated with these qubits are executed first and more frequently in the circuit.

Figure 3
figure 3

(a) The weight of each gate in the circuit, (b) the QPI of each qubit pair.

Full size image

Initial qubit mapping

Priority of logical qubits

The logical qubit priority is determined by the number of two-qubit gates applied on that qubit in the quantum program. If two qubits have the same priority value, a higher priority is given to the qubit that appears earlier in the circuit.

Physical connectivity strength (PCS)

In this paper, the definition of the PCS of a physical qubit is the sum of the number of its first-neighboring qubits and the sum of its second-neighboring qubits. A qubit’s second neighboring qubit refers to a first-neighboring qubit of one of its first-neighboring qubits but not itself or its first-neighboring qubit. The levels of neighboring qubits included in PCS relate to the scalability. For architectures with more qubits, it may be appropriate to include higher-level neighboring qubits in PCS, such as third-neighboring qubits and fourth-neighboring bits.

The PCS of a physical qubit is the number of its neighboring physical qubits. Therefore, when a physical qubit has a larger PCS, the logical qubit mapped to that physical qubit would have a more significant chance of connecting to other logical qubits, resulting in a low probability of moving. Conversely, when it comes to a physical qubit with a low PCS, fewer neighboring physical qubits are around it, indicating that more movements would be needed to satisfy the coupling constraints. These movements would require more SWAP-gate insertion, causing more possible errors. Therefore, the core idea of generating the initial mapping in this paper is to place the logical qubits with more interactions at the physical qubits with larger PCSs.

Algorithm 1 outlines the steps for constructing an initial mapping, where the input of the algorithm is the list of logical qubits sorted in descending order of QPI and the set PCS of all the physical bits, and the output of the algorithm is the quantum mapping M. More detailed, the algorithm is designed in the following way. First, the qubit with the highest QPI is assigned to the physical qubit with the highest PCS, the most connected physical qubit. Then, before the next logical qubit assignment, whether any of its logical neighbors have been placed should be checked. If none have been placed, the unassigned physical qubit with the highest PCS would be selected for allocation. Otherwise, among the unallocated physical neighbors of placed qubits, the physical qubit with the highest QBN value would be chosen. If multiple scenarios exist for the maximum QBN value, all mapping scenarios will be saved.

Algorithm 1
figure a

IQM.

Full size image

Example 2

The initial mapping construction process of the quantum circuit LC in Fig. 4a and the coupling diagram CG in Fig. 4b is shown in Fig. 4c,d. The logical qubit allocation sequence is shown in Fig. 4a, which is q2, q1, q0, q3. In this example, the PCS of a physical qubit is the sum of the number of its first-neighboring qubits. The complete hardware profile of ibm q ourense is shown in Fig. 3c.

Figure 4
figure 4

(a) Coupling graph of a 5-qubit quantum computer from IBM (ibm q ourense), (b) connectivity strength metrics of different qubits in ibm q ourense, (c) a original circuit with Priority of logical qubits and Qubit Pair Interaction, (d) qubit allocation and initial mapping.

Full size image

First, logical qubit ‘q2’ has a physical qubit candidate Q1, directly assigned to Q1. Then, Logical qubit ‘q1’ has 3 possible andidates (as it is a logical neighbor of ‘q2’), all have same QBN each and Q3 is picked randomly in the example. And Logical qubit ‘q0’ has 3 possible andidates, and Q4 has the highest QBN. Therefore, Q4 is chosen for ‘q0’. The other qubits ‘q3’ are placed to Q2 respectively in a similar fashion.

Change of qubit mapping (CQM)

After generating the initial bit mapping, some violated constraints in the quantum circuit must be resolved further. The essential problem is that the connections between physical qubits in a quantum device are finite. When mapping a double-qubit gate to a limited number of physical qubit pairs, SWAP-gate insertion is needed to change the qubit mapping to accommodate the coupling constraints of the physical device. Inserting SWAP gates at different positions has different impacts on subsequent quantum gates. Therefore, to better measure this impact, this paper proposes a heuristic algorithm based on multi-window look-ahead for calculating the impact of inserting SWAP gates on the operation of subsequent gates.

Specifically, regarding the Minimal Subsequent Positive Effect (MSPE) of the SWAP operation as a heuristic cost function, this algorithm calculates the effect of each insertion of a SWAP gate on the subsequent double-qubit gates, providing the best insertion operation for the local part. The MSPE is expressed as follows shown in the following:

$${\text{MSPE}}=\Delta \text{d}+{\sum }_{i}^{i+w}Dist\left({g}_{i}\right).$$
(4)

In this equation, Gi refers to the CNOT gate that does not match the mapping, and w is the window size, indicating the number of gates to be considered afterward, starting from the first gate. The window size grows until the optimal solution is obtained. Supposing the case that more than one optimal solution is obtained, the window size is increased by 1, and the MSPE value is recalculated until a minimum solution is obtained or the window reaches the tail of the circuit. \(\Delta \text{d}\) represents the impact of the SWAP gate on increasing the circuit depth. The quantum circuit in Fig. 5a is mapped like Fig. 5b, and then SWAP gates must be inserted. Calculated by Eq. (4), the \(\Delta \text{d}\) value is different for both insertion methods in Fig. 5c,d. However, the \(\Delta \text{d}\) of the circuit in Fig. 5c is zero, and the \(\Delta \text{d}\) of the circuit in Fig. 5d is one. Finally, the flow of the SWAP insertion is demonstrated in “Methods” section.

Figure 5
figure 5

Circuit \(\Delta \text{d}\) analysis chart when different SWAPs are used (a) Original Quantum Circuit, (b) Physical Qubit Coupling Graph Example, (c) Insert one SWAP operation between q1 and q2, (d) Insert one SWAP operation between q2 and q3.

Full size image

The flow of the CQM algorithm is demonstrated in Fig. 6. More detailed, in the first step, the input quantum circuits are converted into a DAG, and all double-qubit gates in the DAG are traversed layer by layer. Next, according to the current mapping, check whether the traversed double-qubit gates are consistent with the coupling diagram of the quantum device. If they are inconsistent, it is necessary to enumerate all the effective SWAP-gate insertions. Finally, the most effective SWAP-gate insertions are selected based on the multi-windowed forward-looking algorithm. The pseudo-code of CQM is shown in Algorithm 2.

Figure 6
figure 6

Flow chart of CQM algorithm.

Full size image
Algorithm 2
figure b

CQM.

Full size image

For the implementation details and source code, please refer to our GitHub repository: https://github.com/xxxxzbj/QM-DLA.