| Title |
A Parallelized Qubit Mapping Algorithm for Large-scale Quantum Circuits |
| Authors |
(Dongmin Kim) ; (Sengthai Heng) ; (Youngsun Han) |
| DOI |
https://doi.org/10.5573/IEIESPC.2021.11.1.40 |
| Keywords |
Qubit mapping problem; Parallel processing; SABRE algorithm |
| Abstract |
Quantum computers are superior to existing classical supercomputers in terms of run time for specific tasks, and various studies on quantum computers are in progress. Despite this, there is a significant gap in technology between available technologies and actual quantum computers on the noisy intermediate-scale quantum-scale. Currently, various quantum algorithms have been implemented and verified using quantum simulations. Therefore, the runtime performance of a quantum circuit can be verified in the same environment as a real quantum machine. A quantum compiler compiles quantum circuits. When a quantum circuit is compiled, logical qubits in a quantum circuit should be mapped to physical qubits, called qubit mapping. As qubit mapping is an NP-Complete problem, the compilation time increases exponentially according to the number of qubits. Therefore, various studies on effective qubit mapping techniques have been developed to accelerate the execution time. This paper proposes a new parallelized Qubit mapping algorithm. The proposed method consists of three-step processes: one circuit is divided into several circuits; the SABRE enhanced algorithm is executed on each circuit in parallel and then merged. The performance was evaluated using 10 benchmarks. The experimental results revealed an acceleration of up to 6.42x and an average speed up of 4.8x, with an average overhead of 1.03x in terms of the number of gates obtained. The proposed method outperformed the well-known modern qubit-mapping algorithm in terms of the execution time with exponential speedup improvement. |