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.
Comments
v2: 24 pages, 20 figures. Added the detached-gate-based distributed QFT construction and related results. v1: 22 pages, 20 figures
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.
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.
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.
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.
Executing quantum algorithms over distributed quantum systems requires quantum circuits to be divided into sub-circuits which communicate via entanglement-based teleportation. Naively mapping circuits to qubits over multiple quantum processing units (QPUs) results in large communication overhead, increasing both execution time and noise. This can be minimised by optimising the assignment of qubits to QPUs and the methods used for covering non-local operations. Formulations that are general enough to capture the spectrum of teleportation possibilities lead to complex problem instances which can be difficult to solve effectively. This highlights a need to exploit the wide range of heuristic techniques used in the graph partitioning literature. This paper formalises and extends existing constructions for graphical quantum circuit partitioning and designs a new objective function that captures further possibilities for non-local operations via nested state teleportation . We adapt the well-known Fiduccia-Mattheyses heuristic to the constraints and problem objective and explore multilevel techniques that coarsen hypergraphs and partition at multiple levels of granularity. We find that this reduces runtime and improves solution quality of standard partitioning. We place these techniques within a larger framework, through which we can extract full distributed quantum circuits including teleportation instructions. We compare the entanglement requirements and runtimes with state-of-the-art methods, finding that we achieve the lowest entanglement costs in most cases. Averaging over a wide range of circuits, we reduce the entanglement requirements by 35% compared with the next best-performing method. We also find that our techniques can scale to much larger circuit sizes than competing methods, provided the number of partitions is not too large.
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.
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.