Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits

• Published in: ACM transactions on quantum computing (Print) 2024-09, Vol.5 (3), p.1-26, Article 20
• Main Authors: Cheng, Chin-Yi, Yang, Chien-Yi, Kuo, Yi-Hsiang, Wang, Ren-Chu, Cheng, Hao-Chung, Huang, Chung-Yang (Ric)
• Format: Article
• Language: English
• Subjects: Computer systems organization; Hardware; Physical synthesis; Quantum computing
• ISSN: 2643-6809; 2643-6817
• DOI: 10.1145/3680291

Qubit mapping is a critical aspect of implementing quantum circuits on real hardware devices. Currently, the existing algorithms for qubit mapping encounter difficulties when dealing with larger circuit sizes involving hundreds of qubits. In this article, we introduce an innovative qubit mapping algorithm, Duostra, tailored to address the challenge of implementing large-scale quantum circuits on real hardware devices with limited connectivity. Duostra operates by efficiently determining optimal paths for double-qubit gates and inserting SWAP gates accordingly to implement the double-qubit operations on real devices. Together with two heuristic scheduling algorithms, Limitedly Exhaustive Search and Shortest-Path Estimation, it yields results of good quality within a reasonable runtime, thereby striving toward achieving quantum advantage. Experimental results showcase our algorithm’s superiority, especially for large circuits beyond the NISQ era. For example, on large circuits with more than 50 qubits, we can reduce the mapping cost on an average 21.75% over the virtual best results among QMAP, t \(|ket\rangle\) , Qiskit, and SABRE. Besides, for mid-size circuits such as the SABRE-large benchmark, we improve the mapping costs by 4.5%, 5.2%, 16.3%, 20.7%, and 25.7%, when compared to QMAP, TOQM, t \(|ket\rangle\) , Qiskit, and SABRE, respectively.