2.1 Qubit Mapping Problem

Running a quantum circuit using simulation is not the same as running in a real quantum machine. Qubits used in quantum simulations are called logical qubits, while those used in actual quantum machines are called physical qubits. These two qubits run the quantum circuit under different conditions, and the condition considered in this study is the Qubit connectivity.

Qubit connectivity contains information on how different qubits are connected and can be expressed in a graph called a coupling map. In the case of logical qubits, because they are all connected to each other, the coupling map is not considered when executing the quantum circuit on a quantum simulator. By contrast, because not all physical qubits are connected to each other, the quantum circuit is executed in consideration of the coupling map. Fig. 1 shows the coupling map of a real quantum machine, IBM Q Tokyo. In the coupling map of IBM Q Tokyo, the circles indicate physical qubits, and straight arrows indicate that physical qubits are connected to each other. For example, qubits 6 and 7 are connected to each other, but qubits 6 and 12 are not. Hence, there are limitations in operating the quantum circuit because the physical qubits of the actual quantum machine are only connected to specific qubits.

Fig. 1. Coupling map of a 20-qubit IBM Tokyo quantum machine.

A quantum circuit consists of several qubits and quantum gates. Quantum gates can be divided into single-qubit gates and multi-qubit gates. When executing a quantum circuit composed of these quantum gates in an actual quantum machine, it is necessary to check whether multi-qubit gates can be executed without additional work. That is, if the physical qubits to which the multi-qubit gates are applied are not connected to each other, these multi-qubit gates cannot be executed directly on an actual quantum machine. To solve this problem, it is necessary to connect the physical qubits that are separated. On the other hand, because the location of the physical qubit cannot be changed, the logical qubit must first be mapped to the physical qubit on the coupling map. Some of the logical qubits are separated from each other and some are connected according to the coupling map. To connect the separated physical qubits, it is necessary to connect the logical qubits mapped to the corresponding physical qubits. To this end, many SWAP gates that change the positions of the logical qubits are added to the original quantum circuit. Accordingly, the number of gates in the quantum circuit increases, which increases the execution time of qubit mapping. That is, to alleviate this problem, it is necessary to minimize the total number of gates using only a minimum number of SWAP gates.

Fig. 2 shows two different quantum circuits in which arbitrary quantum circuits can be produced through qubit mapping: (a) is a coupling map composed of four qubits, and (b) is a quantum circuit composed of four qubits and six quantum gates. If qubit mapping is performed considering the coupling map of (a) provided in (b), a quantum circuit is constructed, as shown in (c). The CNOT gate, which is indicated by the red dotted line in circuit (b), is applied to the first and third qubits. In the coupling graph of (a), the first and third qubits are not connected to each other. Thus, they cannot be executed directly on the quantum machine. The CNOT gate represented by the blue dotted line is a CNOT gate that can be affected by the SWAP gates added for the CNOT, which are represented by the red dotted line to be executed. When Qubit mapping is performed, two possible results can be observed: (c) and (d). In (c), two swap gates were added, and in (d), only one swap was added. Therefore, for a NISQ-scale quantum circuit, depending on the qubit mapping algorithm, the number of swap gates added, and the execution time of qubit mapping may be affected.

Fig. 2. Example of two different quantum circuits after qubit mapping: (a) Example of the coupling map of a quantum machine; (b) Example of a quantum circuit; (c), (d) Mapped quantum circuit by qubit mapping.

2.2 Qubit-mapping Algorithms

Recent studies related to Qubit mapping have been conducted to implement NISQ-scale quantum circuits in real quantum machines. Cowtan et al. ^[20] performed Qubit mapping using the t|ket> quantum compiler in the architecture of IBM QX5, a real quantum machine with 16 qubits, and IBM Tokyo with 20 qubits. Cowtan et al. ^[20] aimed to minimize the depth of the added quantum gate and quantum circuit. For performance verification, from a significantly small-scale quantum circuit with five quantum gates to a NISQ-scale quantum circuit as a benchmark, the benchmarks were run together in the compiler systems of Qiskit, Project Q, and Qulic to compare the performance. In the performance comparison, however, it is difficult to accurately compare the performance with t|ket> because the number and depth of quantum gates and depth of Qiskit and Qulic for approximately 3000 or more quantum circuits in the IBM Q Tokyo machine used by Cowtan et al. ^[20] were not measured. In addition, the execution time required for qubit mapping in the three compilers was not analyzed.

A previous study ^[21] used a heuristic algorithm using the gate commutation rule and the gate transformation rule to reduce the number of additional gates. In particular, the number of additional gates required for qubit mapping was minimized using the Bridge gate and the SWAP gate. On the other hand, the quantum circuit was used as a benchmark for performance verification contained up to 38577 quantum gates, which is not sufficiently large. Comparison analysis of the circuit execution time was not performed sufficiently. Zulehner et al. ^[22] performed qubit mapping that minimizes the number of gates added to the IBM QX architecture and reported superior performance compared to the default qubit-mapping algorithm provided by Qiskit at the time the thesis was written. Cowtan et al. ^[20] developed and verified the superiority of the SABRE algorithm by comparing its performance with that by Zulehner et al. ^[22] in terms of the number of additional quantum gates, total number of gates, and quantum qubit mapping execution time. On the other hand, the benchmarks used for performance verification included a maximum of 34881 quantum gates, which is significantly smaller than the number of quantum gates on the NISQ-scale to be addressed in this study. Zhang et al. ^[23] performed qubit mapping to minimize the circuit depth using a depth-aware SWAP insertion scheme. The reported performance of the method ^[23] was verified by comparing it with the SABRE algorithm and the method reported by Zulehner et al. ^[22].

Compared to the two methods, the method reported by Zhang et al. ^[23] showed superior performance in terms of additional gates and depth. On the other hand, the benchmarks used by Zhang et al. ^[23] are also not NISQ-scale quantum circuits, and a detailed analysis of the execution time was not performed except for the statement that the expected execution time can be equated with the depth. Niu et al. ^[24] reported the performance of reducing the number of additional gates by 28\% on average compared to SABRE on the ibmq\_almaden machine and 14\% on the ibmq\_tokyo machine by proposing a hardware-aware mapping transition algorithm. On the other hand, because Niu et al. ^[24] also benchmarked the quantum circuit used in SABRE, the execution time of the NISQ-scale quantum circuit was not compared and analyzed. Therefore, the present study used the NISQ-scale quantum circuit as a benchmark to analyze the execution time, which was insufficient in previous papers, and reduce it compared to the existing methodology. The circuit consists of three sub-processes using the SABRE algorithm, and the execution time of SABRE was compared with the proposed method for performance verification.

3.1 Proposed Method

First, the quantum circuit was split into several quantum subcircuits. By doing this, each quantum subcircuit could be computed in parallel. Circuit splitting processes on quantum circuit objects of the Qiskit library. In this version, every quantum circuit that contains more than 300 gates must be split. There is a trade-off between the number of gates per quantum subcircuit and the number of core processes used. This trade-off is mentioned in section 4.2.

Second, one quantum circuit was divided into quantum subcircuits with the same number of quantum gates, and the SABRE algorithm was applied to the quantum subcircuits to perform qubit mapping. At this time, because SABRE mapping is performed on a relatively small quantum sub-circuit compared to the original circuit, the size of a Directed Acyclic Graph (DAG) ^[19] of each quantum sub-circuit is also relatively small. The size of the DAG has a significant impact on the execution time of the qubit mapping because the DAG is checked multiple times during qubit mapping. In addition, because SABRE mapping is applied to each quantum subcircuit in parallel, the execution time of qubit mapping is faster than that of one-by-one. After SABRE mapping, the position of the last logical qubit of each quantum subcircuit is different from the initial position because the SWAP gates are added to each quantum subcircuit. The quantum gate is not applied to the correct qubit if all quantum subcircuits are combined under these conditions. Thus, the measurement result will be incorrect. To address the position changes, the logical qubit position must be moved back to the initial position. To achieve this, when performing SABRE mapping for each quantum subcircuit, the initial logical qubit position is arranged from the first qubit to the last qubit in order. When SABRE mapping is finished, the position of the changed logical qubit is rearranged from the first qubit to the last qubit sequentially. Different permutations are added to each circuit to rearrange the physical qubits. The permutation describes the current position of the logical qubit that allows the addition of reversed swap gates to move the qubit back to the initial position. The permutation pattern is extracted by identifying which qubits are swapped when the SABRE mapping operates. This pattern is different for each quantum subcircuit, and the positions of the last logical qubits of all quantum subcircuits are rearranged sequentially through permutation. In addition, this reversed swap process is also executed in parallel to accelerate the execution time.

Finally, each quantum subcircuit on which SABRE mapping and permutation have been performed must be combined into one quantum circuit again. Since all quantum subcircuits have physical qubits arranged in order by permutation at the end of the circuit, they can be converted quickly into a single quantum circuit with a simple '+' operation without additional work. The final quantum circuit has a different configuration from the circuit mapped by the SABRE algorithm; however, the result after the measurement is the same. Therefore, the accuracy of the quantum circuit mapped through the proposed method is reliable.

3.2 Example of Proposed Method

Fig. 4 is an arbitrary quantum circuit with four qubits and a total of 19 quantum gates. Assume that a given quantum circuit is operated in a quantum machine with a coupling map, as shown in Fig. 2(a). First, as shown in Fig. 5, a quantum circuit is divided into three quantum subcircuits with six quantum gates through the circuit split process. Subsequently, the red dotted line of each quantum subcircuit cannot be executed directly. Hence, it becomes a quantum gate that requires an additional swap, and the blue dotted line becomes a quantum gate that can be changed owing to the additional swap.

Fig. 6 presents three quantum subcircuits to which SABRE mapping is applied. Each swap gate is applied at a different location. Hence, the location of the final physical qubit is different from the first location. Therefore, before combining them as one quantum circuit, each permutation is applied in Fig. 7. The square brackets in permutation are the pattern of permutation, and each quantum subcircuit has a different pattern. Consequently, the position of the final qubit becomes the same as the position of the first qubit, which avoids applying a quantum gate to the wrong qubit when merging. Fig. 8 shows that it has become one quantum circuit again after the Circuit Merge process.

Fig. 4. Example of a quantum circuit with four qubits and 19 quantum gates.

Fig. 5. Quantum subcircuits after Circuit Split process of proposed method.

Fig. 6. 3 quantum subcircuits after the SABRE mapping process of the proposed method.

Fig. 7. 3 quantum subcircuits after adding Permutation at the end of the SABRE applied quantum circuits.

Fig. 8. Qubit-mapped quantum circuit after the Circuit Merge process of the proposed method.

4.1 Speedup

Fig. 9 shows that the execution time of the proposed method is improved compared to the SABRE execution time. All experiments in this study were executed on a server with an AMD EPYC 7R32 CPU up to 3.4GHz (32 physical cores, two threads per core) and 128GB memory. The operating system was Ubuntu 20.04.2 LTS. The Python and Qiskit versions were 3.8.10 and 0.30.1, respectively. A Python multiprocessing module was used to perform the SABRE algorithm in parallel, and the number of processes depends on the number of CPU cores. Ten NISQ-scale quantum circuits were used as benchmarks, and the number of CPU cores was doubled from two to use up to 32 cores.

The Qiskit simulator was used to verify the accuracy of the experimental results and confirm that the results of the original quantum circuit, the circuit to which SABER was applied, and the circuit to which the proposed method was applied were all the same.

Because the proposed method executes SABRE mapping in parallel, the execution time speedup is improved approximately twofold when the number of cores is doubled. The proposed method in most quantum circuits outperformed SABRE. In the case of $pm\_4096$ with full name $plus63mod4096\_163$, using 32 cores, it was possible to obtain a speedup improvement of 6.4x compared to SABRE. On average, the proposed method obtained 1.5x, 2.5x, 3.5x, 4.5x, and 4.8x faster for 2, 4, 8, 16, and 32 cores, respectively, compared to SABRE.

The proposed method ran the SABER algorithm in parallel while increasing the number of CPU cores from 2 to 32. In some benchmarks, the execution time of the proposed method did not increase linearly when the number of cores was doubled. The proposed algorithm consisted of three parts. The circuit split and circuit merge process take time because only the part that performs qubit mapping was in parallel. Therefore, the execution time of the proposed method did not improve the performance completely linearly according to the number of cores.

4.2 Overhead Estimation

Table 1 lists the total number of quantum gates and the circuit depth generated by the SABRE and proposed method. The comparison normalized the results of SABRE and presented the results for the number of SWAP gates added using the proposed method, total number of gates, and depth. Because the proposed method included the permutations, there was a possibility that the number of swap gates to be added would be larger than that of the SABRE algorithm. On average, 1.25x swap gates were added compared to SABRE. On the other hand, in terms of the total gates, compared to SABRE, the maximum value was 1.05x, and the average was 1.03x, indicating a relatively small number compared to the added swap gates.

The depth of a quantum circuit is the total number of layers in which quantum gates can be executed simultaneously ^[25]. That is, quantum gates included in one layer can be executed in parallel; hence, the depth can significantly affect the overall execution time of the circuit. The depth of the proposed method increased up to 1.06x with an average of 1.03x compared to SABRE.

This study analyzed the methods to improve the execution time performance of the proposed method for future studies. The SABRE algorithm was executed in parallel by dividing one quantum circuit into multiple small-scale quantum subcircuits, doubling from at least two CPU cores to 32 for each quantum subcircuit. The results are presented in Fig. 9. Some specific benchmarks, such as $misex1\_241$, i.e., the number of cores, were doubled, but the speedup improvement was decreased. This is because the quantum subcircuits are assigned randomly to each core without considering the computational load of each quantum subcircuit when executing this method. That is, the load-balancing issue was not considered. Therefore, the consistent speedup improvement of the method according to the number of cores will need to be determined by adding a load-balancing algorithm optimized to the proposed method in future research.

Fig. 9. Speedup execution time of the proposed method compared to SABRE.

Table 1. Number of additional gates and depth of the Proposed method compared to SABRE.