Distributed Quantum Circuit Partitioning and Optimization Based on Combined Spectral Clustering and Search Tree Strategies

Abstract In the current Noisy Intermediate-Scale Quantum (NISQ) era, a single Quantum Processing Unit (QPU) is insufficient to implement large-scale quantum algorithms, which 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 the 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 the spectral clustering-based partitioning exhibits robust stability and efficiency in runtime in quantum circuits of different scales. In experiments involving the Quantum Fourier Transform (QFT) algorithm and Revlib quantum circuits, the transmission cost achieved by the global gate search tree strategy is significantly optimized.