中国物理B ›› 2025, Vol. 34 ›› Issue (5): 50305-050305.doi: 10.1088/1674-1056/adbada

• • 上一篇    下一篇

Distributed quantum circuit partitioning and optimization based on combined spectral clustering and search tree strategies

Zilu Chen(陈子禄)1, Zhijin Guan(管致锦)1,2,†, Shuxian Zhao(赵书娴)3, and Xueyun Cheng(程学云)1,‡   

  1. 1 School of Artificial Intelligence and Computer Science, Nantong University, Nantong 226019, China;
    2 College of Engineering the Internet of Things, Taihu University, Wuxi 214063, China;
    3 Jiangsu Huihuan Environmental Protection Technology Co., Ltd., Nantong 226010, China
  • 收稿日期:2024-12-24 修回日期:2025-02-24 接受日期:2025-02-27 出版日期:2025-05-15 发布日期:2025-04-18
  • 通讯作者: Zhijin Guan, Xueyun Cheng E-mail:guan.zj@ntu.edu.cn;chen.xy@ntu.edu.cn
  • 基金资助:
    Project supported by the National Natural Science Foundation of China (Grant No. 62072259), in part by the Natural Science Foundation of Jiangsu Province (Grant No. BK20221411), the PhD Start-up Fund of Nantong University (Grant No. 23B03), and the Postgraduate Research & Practice Innovation Program of School of Information Science and Technology, Nantong University (Grant No. NTUSISTPR24_05).

Distributed quantum circuit partitioning and optimization based on combined spectral clustering and search tree strategies

Zilu Chen(陈子禄)1, Zhijin Guan(管致锦)1,2,†, Shuxian Zhao(赵书娴)3, and Xueyun Cheng(程学云)1,‡   

  1. 1 School of Artificial Intelligence and Computer Science, Nantong University, Nantong 226019, China;
    2 College of Engineering the Internet of Things, Taihu University, Wuxi 214063, China;
    3 Jiangsu Huihuan Environmental Protection Technology Co., Ltd., Nantong 226010, China
  • Received:2024-12-24 Revised:2025-02-24 Accepted:2025-02-27 Online:2025-05-15 Published:2025-04-18
  • Contact: Zhijin Guan, Xueyun Cheng E-mail:guan.zj@ntu.edu.cn;chen.xy@ntu.edu.cn
  • Supported by:
    Project supported by the National Natural Science Foundation of China (Grant No. 62072259), in part by the Natural Science Foundation of Jiangsu Province (Grant No. BK20221411), the PhD Start-up Fund of Nantong University (Grant No. 23B03), and the Postgraduate Research & Practice Innovation Program of School of Information Science and Technology, Nantong University (Grant No. NTUSISTPR24_05).

RichHTML

0

PDF (PC)

38

赞

摘要： In the current noisy intermediate-scale quantum (NISQ) era, a single quantum processing unit (QPU) is insufficient to implement large-scale quantum algorithms; this has driven extensive research into distributed quantum computing (DQC). DQC involves the cooperative operation of multiple QPUs but is concurrently challenged by excessive communication complexity. To address this issue, this paper proposes a quantum circuit partitioning method based on spectral clustering. The approach transforms quantum circuits into weighted graphs and, through computation of the Laplacian matrix and clustering techniques, identifies candidate partition schemes that minimize the total weight of the cut. Additionally, a global gate search tree strategy is introduced to meticulously explore opportunities for merged transfer of global gates, thereby minimizing the transmission cost of distributed quantum circuits and selecting the optimal partition scheme from the candidates. Finally, the proposed method is evaluated through various comparative experiments. The experimental results demonstrate that spectral clustering-based partitioning exhibits robust stability and efficiency in runtime in quantum circuits of different scales. In experiments involving the quantum Fourier transform algorithm and Revlib quantum circuits, the transmission cost achieved by the global gate search tree strategy is significantly optimized.

关键词: NISQ era, distributed quantum computing, quantum circuit partitioning, transmission cost

Abstract: In the current noisy intermediate-scale quantum (NISQ) era, a single quantum processing unit (QPU) is insufficient to implement large-scale quantum algorithms; this has driven extensive research into distributed quantum computing (DQC). DQC involves the cooperative operation of multiple QPUs but is concurrently challenged by excessive communication complexity. To address this issue, this paper proposes a quantum circuit partitioning method based on spectral clustering. The approach transforms quantum circuits into weighted graphs and, through computation of the Laplacian matrix and clustering techniques, identifies candidate partition schemes that minimize the total weight of the cut. Additionally, a global gate search tree strategy is introduced to meticulously explore opportunities for merged transfer of global gates, thereby minimizing the transmission cost of distributed quantum circuits and selecting the optimal partition scheme from the candidates. Finally, the proposed method is evaluated through various comparative experiments. The experimental results demonstrate that spectral clustering-based partitioning exhibits robust stability and efficiency in runtime in quantum circuits of different scales. In experiments involving the quantum Fourier transform algorithm and Revlib quantum circuits, the transmission cost achieved by the global gate search tree strategy is significantly optimized.

Key words: NISQ era, distributed quantum computing, quantum circuit partitioning, transmission cost

中图分类号:  (Quantum information)

  • 03.67.-a
03.67.Lx (Quantum computation architectures and implementations) 03.67.Ac (Quantum algorithms, protocols, and simulations)