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 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
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.
Fund: 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).
Zilu Chen(陈子禄), Zhijin Guan(管致锦), Shuxian Zhao(赵书娴), and Xueyun Cheng(程学云) Distributed quantum circuit partitioning and optimization based on combined spectral clustering and search tree strategies 2025 Chin. Phys. B 34 050305
[1] Feynman R P 2018 Feynman and Computation (cRc Press) pp. 133- 153 [2] Preskill J 2018 Quantum 2 79 [3] Qin D, Xu X and Li Y 2022 Chin. Phys. B 31 090306 [4] Jin Y X, Xu H Z, Wang Z A, Zhuang W F, Huang K X, Shi Y H, Ma W G, Li T M, Chen C T, Xu K, et al. 2024 Chin. Phys. B 33 050301 [5] Van Meter R and Devitt S J 2016 Computer 49 31 [6] Buhrman H and Röhrig H 2003 International Symposium on Mathematical Foundations of Computer Science (Springer) pp. 1-20 [7] Beals R, Brierley S, Gray O, Harrow AW, Kutin S, Linden N, Shepherd D and Stather M 2013 Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 469 20120686 [8] Cuomo D, Caleffi M and Cacciapuoti A S 2020 IET Quantum Communication 1 3 [9] Avron J, Casper O and Rozen I 2021 Phys. Rev. A 104 052404 [10] Fujii K, Yamamoto T, Koashi M and Imoto N 2012 arXiv:1202.6588 [quant-ph] [11] Cacciapuoti A S, Caleffi M, Tafuri F, Cataliotti F S, Gherardini S and Bianchi G 2019 IEEE Network 34 137 [12] Sundaram R G, Gupta H and Ramakrishnan C 2021 35th International Symposium on Distributed Computing (DISC 2021) (Schloss Dagstuhl- Leibniz-Zentrum für Informatik) [13] Sundaram R G, Gupta H and Ramakrishnan C 2022 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) (IEEE) pp. 415-425 [14] Davarzani Z, Zomorodi-Moghadam M, Houshmand M and Nouri- Baygi M 2020 Quantum Inf. Process. 19 1 [15] Nikahd E, Mohammadzadeh N, SedighiMand ZamaniMS 2021 Physica Scripta 96 035102 [16] Dadkhah D, Zomorodi M and Hosseini S E 2021 International Journal of Theoretical Physics 60 3271 [17] Ghodsollahee I, Davarzani Z, Zomorodi M, Pławiak P, Houshmand M and Houshmand M 2021 Quantum Inf. Process. 20 1 [18] Dadkhah D, Zomorodi M, Hosseini S E, Plawiak P and Zhou X 2022 IEEE Access 10 70329 [19] Davarzani Z, Zomorodi M and Houshmand M 2022 Scientific Reports 12 15421 [20] Luo T Y, Zheng Y Z, Fu X and Deng Y X 2024 Chin. Phys. B 33 120302 [21] Mao Y, Liu Y and Yang Y 2023 IEEE INFOCOM 2023-IEEE Conference on Computer Communications (IEEE) pp. 1-10 [22] Jozsa R 2004 IBM Journal of Research and Development 48 79 [23] Cheng X, Chen X, Cao K, Zhu P, Feng S and Guan Z 2023 Quantum Inf. Process. 22 187 [24] Bennett C H, Brassard G, Crépeau C, Jozsa R, Peres A and Wootters W K 1993 Phys. Rev. Lett. 70 1895 [25] Yimsiriwattana A and Lomonaco Jr S J 2004 arXiv:quant-ph/0402148 [26] Niu J, Zhang L, Liu Y, Qiu J, Huang W, Huang J, Jia H, Liu J, Tao Z, Wei W, et al. 2023 Nat. Electron. 235 241 [27] Houshmand M, Mohammadi Z, Zomorodi-Moghadam M and Houshmand M 2020 International Journal of Theoretical Physics 59 1315 [28] Daei O, Navi K and Zomorodi M 2021 International Journal of Theoretical Physics 60 3494 [29] Cambiucci W, Silveira R M and Ruggiero W V 2023 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) vol. 2 (IEEE) pp. 268-269 [30] Daei O, Navi K and Zomorodi-Moghadam M 2020 International Journal of Theoretical Physics 59 3804 [31] Yan J T 2023 IEEE Transactions on Quantum Engineering 4 1 [32] Andres-Martinez P and Heunen C 2019 Phys. Rev. A 100 032308
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
