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.
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.
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.
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.
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.
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.
Distributed quantum computing (DQC) is a new paradigm aimed at scaling up quantum computing via the interconnection of smaller quantum processing units (QPUs). Shared entanglement allows teleportation of both states and gates between QPUs. This leads to an attractive horizontal scaling of quantum processing power that comes at the expense of the additional time and noise introduced by entanglement sharing protocols. Consequently, protocols for partitioning quantum circuits should aim to minimise the amount of entanglement-based communication required between distributed QPUs. Existing protocols tend to focus primarily on optimising entanglement costs for gate teleportation or state teleportation to cover operations between QPUs, rather than both at the same time. The most general form of the problem should treat gate and state teleportation on the same footing, allowing minimal cost circuit partitions through a combination of the two. This work introduces a graph-based formulation that allows joint optimisation of gate and state teleportation cost. The formulation permits lowe-bit cost for a variety of circuit types. Using a genetic algorithm, improved performance over state-of-the-art methods is obtained in terms of both average e-bit cost and time scaling.
A promising avenue for scaling quantum computing is to connect quantum processing units (QPUs) by generating entanglement between them. This requires circuit partitioning: partially rewriting quantum circuits to run on a distributed quantum system using quantum teleportation protocols, while preserving the unitary operation implemented by the circuit. The key metric to minimize when partitioning is the e-bit count, defined as the number of maximally entangled qubit pairs that must be generated between QPUs. We focus on partitioning the quantum Fourier transform (QFT) circuit, which is widely used as a subroutine in quantum algorithms such as quantum phase estimation and arithmetic circuits. Specifically, we present an optimal gate-packing-based partitioning scheme under bounded communication ancilla constraints, as well as a novel detached-gate-based partitioning scheme that achieves optimal e-bit consumption when ancilla availability is unrestricted. We compare these schemes against prior analytical partitioning approaches for the QFT and evaluate them against partitions produced by general-purpose circuit partitioning algorithms. We further validate our approach by implementing the bounded-ancilla circuits on quantum hardware.