arXiv:2407.05953 · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

Circuit Partitioning and Transmission Cost Optimization in Distributed Quantum Circuits

Xinyu Chen, Zilu Chen, Pengcheng Zhu, Xueyun Cheng, Zhijin Guan

Published Mar 4, 2025• 7 citations

Abstract

Given the limitations on the number of qubits in current noisy intermediate-scale quantum (NISQ) devices, the implementation of large-scale quantum algorithms on such devices is challenging, prompting research into distributed quantum computing. This article focuses on the issue of excessive communication complexity in distributed quantum computing based on the quantum circuit model. To reduce the number of quantum state transmissions, i.e., the transmission cost, in distributed quantum circuits, a circuit partitioning method based on the quadratic unconstrained binary optimization (QUBO) model is proposed, coupled with the lookahead method for transmission cost optimization. Initially, the problem of distributed quantum circuit partitioning is transformed into a graph minimum cut problem. The QUBO model, which can be accelerated by quantum annealing algorithms, is introduced to minimize the number of quantum gates between quantum processing units (QPUs) and the transmission cost. Subsequently, the dynamic lookahead strategy for the selection of transmission qubits is proposed to optimize the transmission cost in distributed quantum circuits. Finally, through numerical simulations, the impact of different circuit partitioning indicators on the transmission cost is explored, and the proposed method is evaluated on benchmark circuits. Experimental results demonstrate that the proposed circuit partitioning method has a shorter runtime compared with current circuit partitioning methods. Additionally, the transmission cost optimized by the proposed method is significantly lower than that of current transmission cost optimization methods, achieving noticeable improvements across different numbers of partitions.

DOI: 10.1109/tcad.2025.3547812

Related papers

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

Zilu Chen, Zhijin Guan, Shuxian 书娴 Zhao 赵 +1 more

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.

Chinese Physics BFeb 27, 20254 citations

Efficient Time-Aware Partitioning of Quantum Circuits for Distributed Quantum Computing

Raymond P. H. Wu, Chathu Ranaweera, Sutharshan Rajasegarar +3 more

To overcome the physical limitations of scaling monolithic quantum computers, distributed quantum computing (DQC) interconnects multiple smaller-scale quantum processing units (QPUs) to form a quantum network. However, this approach introduces a critical challenge, namely the high cost of quantum communication between remote QPUs incurred by quantum state teleportation and quantum gate teleportation. To minimize this communication overhead, DQC compilers must strategically partition quantum circuits by mapping logical qubits to distributed physical QPUs. Static graph partitioning methods are fundamentally ill-equipped for this task as they ignore execution dynamics and underlying network topology, while metaheuristics require substantial computational runtime. In this work, we propose a heuristic based on beam search to solve the circuit partitioning problem. Our time-aware algorithm incrementally constructs a low-cost sequence of qubit assignments across successive time steps to minimize overall communication overhead. The time and space complexities of the proposed algorithm scale quadratically with the number of qubits and linearly with circuit depth, offering a significant computational speedup over common metaheuristics. We demonstrate that our proposed algorithm consistently achieves significantly lower communication costs than static baselines across varying circuit sizes, depths, and network topologies, providing an efficient compilation tool for near-term distributed quantum hardware.

quant-pharXiv:2603.04126International Conference on Quantum Communications, Networking, and Computing (QCNC)Mar 5, 20261 citation

Resource-aware distributed quantum circuits partitioning strategy and transmission cost optimization

Pengcheng Zhu, Zongyuan 宗原 Dai 戴, Lihua Wei +2 more

Abstract To overcome the physical limitations of current quantum hardware in terms of available qubits and connectivity, distributed quantum computing (DQC) has emerged as a promising and scalable paradigm. However, in distributed settings, cross-node qubit interactions incur high communication overhead due to the use of costly quantum communication protocols. Efficient circuit partitioning and transmission cost optimization have thus become key challenges. This work addresses the often-overlooked issues of hardware heterogeneity and redundant transmission by proposing a resource-aware partitioning and transmission cost optimization method for distributed quantum circuits. First, we develop a partitioning framework constrained by qubit resources, which accommodates node capacity differences to enable flexible qubit allocation. Second, we model gate dependencies using a directed acyclic graph (DAG) representation and introduce formal criteria to detect “initial-state” and “final-state” redundancies. A measurement-reset strategy is then employed to replace part of the quantum communication, reducing inter-node data transmission. Experimental results on a variety of benchmark circuits and heterogeneous architectures demonstrate that our method significantly reduces transmission cost and improves overall resource utilization. These findings offer both theoretical insight and practical guidance for efficient distributed quantum computing.

Chinese Physics BOct 16, 20250 citations

Distributed quantum circuit partitioning and teleportation optimization based on a multi-dimensional evaluation strategy

Le 乐 Zhang 张, Zhijin Guan, Shuo 硕 Qin 秦 +3 more

Abstract Distributed quantum computing has emerged as a key approach to extending current quantum computing capabilities, with its performance largely determined by the cost of qubit transmissions across physical nodes. To minimize such cross-partition transmission costs, this paper proposes a distributed quantum circuit partitioning and teleportation optimization method based on a multidimensional evaluation strategy. First, a scoring function is designed using interaction strength and temporal fragmentation, guiding the partitioning process to balance structural compactness with temporal continuity. Building on this, we employ multiple starting points and parameter search strategies to progressively construct candidate partition schemes. Subsequently, a transmission-cost optimization method based on teleportation group partitioning is introduced to evaluate candidates more accurately, taking into account gate timing, interfering operations, and communication resource conflicts, thereby yielding a more realistic estimate of teleportation counts. Simulation results on several benchmark quantum circuits demonstrate that the proposed method consistently generates superior partitions under challenging conditions, such as high interaction density and significant gate interleaving. In some cases, teleportation counts are reduced by up to 64.7%, with an overall average improvement of 8%, verifying the adaptability and effectiveness of the method in optimizing communication across different interaction structures.

Chinese Physics BNov 6, 20250 citations

Optimized Quantum Circuit Partitioning Across Multiple Quantum Processors

Eneet Kaur, Shahrooz Pouryousef, Hassan Shapourian +4 more

This paper addresses the challenge of scaling quantum computing by employing distributed quantum algorithms across multiple processors. As quantum circuits grow in complexity, efficiently managing the entanglement resources required for communication between quantum processing units (QPUs) becomes increasingly critical. We propose novel methods to optimize entanglement consumption while accounting for network constraints. Our approach leverages graph partitioning techniques to optimize both qubit teleportation and gate teleportation, minimizing the number of Einstein-Podolsky-Rosen (EPR) pairs required to execute general quantum circuits. Additionally, we formulate an integer linear program (ILP) to further reduce entanglement requirements by mapping the logical resources of partitioned circuits to the physical constraints of the underlying quantum network. Finally, we analyze the entanglement cost for implementing the Quantum Fourier Transform (QFT) across multiple QPUs, employing an approach that exploits the circuit's structure to minimize total entanglement consumption. These contributions provide a pathway to scalable and resource-efficient distributed quantum computing.

IEEE Transactions on Quantum EngineeringJan 1, 20256 citations

Co-design threading model and circuit cutting for static and adaptive quantum circuits

Waldemir Cambiucci, Regina Melo Silveira, Wilson Vicente Ruggiero

Abstract As quantum computing rapidly evolves, scaling quantum algorithms to utilize multiple quantum processing units (QPUs) becomes crucial for overcoming the limitations of current noisy intermediate-scale quantum (NISQ) devices. This paper focuses on distributed quantum computing (DQC), specifically targeting the challenges associated with circuit cutting and circuit distribution in multi-QPU environments. By leveraging techniques such as hypergraph partitioning and threading models, this paper presents alternative strategies for dividing and managing both static and adaptive quantum circuits across multiple QPUs. A central research question is how the partitioning and distribution of quantum circuits can be optimized to minimize communication overhead and maximize computational performance in multi-QPU systems, for static and adaptive quantum circuits. To answer this question, a hypergraph partitioning method is proposed to effectively segment large static quantum circuits into manageable subcircuits, ensuring minimal inter-QPU gate operations and reduced time for the partitioning process. Additionally, a co-design threading model is presented, tailored for adaptive quantum circuits. This category of circuits can dynamically adjust their sequence of gates in runtime, based on intermediate measurements and classical control flows, creating unique challenges for circuit partition. Finally, to support the coordination between circuit partitions with static and adaptive circuits, we propose a quantum resource manager (QRM) architecture, bridging the gap between partitioning techniques and practical coordination for a scalable quantum computing system with multi-QPU architecture.

Quantum Information ProcessingMar 31, 20260 citations