Technical Papers Archive

QPAR: A Plug-In Parallel Framework for Qubit Routing


Authors: Jiaqi Liu, Runzhe Zhang, and Mingfei Zhang (Shanghai Jiao Tong University); Zhuo Song (Shanghai Jiao Tong University, Alibaba Cloud); and Quan Chen, Jingwen Leng, Minyi Guo, Pu Pang, and Anbang Wu (Shanghai Jiao Tong University)

Abstract: Qubit routing, a key stage of quantum compiler, inserts additional operations (e.g., SWAP gates) to ensure quantum circuit instructions are executable on physical hardware. The effectiveness of routing in terms of minimizing additional operations is critical, as they introduce extra overhead and noise. However, existing routing methods often suffer from high computational overhead, limiting their scalability for large-scale circuit compilation. To overcome this limitation, we present QPAR, a plug-in parallel framework to boost the scalability of routing algorithms. The key insight of QPAR is that, while qubit routing is a sequential process, we can first relax the sequential dependencies to enable parallelism and then rebuild them to ensure correctness. QPAR further establishes optimizations to combat potential loss of routing effectiveness caused by parallelization. Experimental results demonstrate that QPAR can accelerate routing algorithms by up to 126.6x, with negligible, even negative, cost increases on a 128-logical-core server.


Presentation: file

Back to Technical Papers Archive Listing