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.
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.
As quantum computing evolves, distributing circuits across multiple Quantum Processing Units (QPUs) is crucial to scaling algorithms and overcoming the limitations of current Noisy Intermediate-Scale Quantum (NISQ) devices. We introduce HyPAQ, a hypergraph partitioning framework for efficient circuit cutting and distribution in multi-QPU environments. HyPAQ reduces inter-QPU communication and improves performance by optimizing partitioning for both static and adaptive circuits, leveraging segmentation and a codesign threading model, respectively. For static circuits, HyPAQ employs weighted hypergraph partitioning heuristics, dividing circuits into smaller subcircuits that balance computational load while minimizing communication costs. This approach extends to reduced hypergraph representations, enabling more efficient cuts in larger circuits and outperforming traditional bipartite methods. In adaptive circuits, where operations depend on intermediate measurements, HyPAQ introduces an assisted segmentation model capable of addressing runtime dynamics absent in static cases, ensuring scalable execution even in measurement-driven scenarios. Designed to integrate with a full-stack architecture, HyPAQ coordinates partitioning, execution, and resource allocation across multi-QPU systems. Experimental results demonstrate significant reductions in communication overhead and improved scalability, making HyPAQ a practical and adaptable solution for distributed quantum computing.
Quantum computing promises to revolutionize problem-solving through quantum mechanics, but current NISQ devices face limitations in qubit count and error rates, hindering the execution of large-scale quantum circuits. To address these challenges and improve scalability, two main circuit cutting strategies have emerged: the gate-cut approach, which distributes circuit segments across multiple QPUs (spatial), and the qubit wire cut approach, which divides circuits for sequential execution (temporal). This paper presents a hypergraph-based circuit cutting methodology suitable for both spatial and temporal scenarios. By modeling quantum circuits as high-level hypergraphs, we apply partitioning heuristics such as Stoer-Wagner, Fiduccia-Mattheyses, and Kernighan-Lin to optimize the partitioning process. Our approach aims to reduce communication overhead in spatial cuts and minimize qubit initialization costs in temporal ones. To assess effectiveness, we propose a new evaluation metric called the coupling ratio, which quantifies the trade-offs between communication and initialization. Comparative analyses show that hypergraph partitioning improves the efficiency of distributed quantum architectures. Notably, the Fiduccia-Mattheyses heuristic offers superior performance and adaptability for real-time circuit cutting on multi-QPU systems. Overall, this work positions hypergraph partitioning as a foundational technique for scalable quantum computing in distributed environments.
There is a consensus that the distribution of quantum circuits among processing agents is a viable approach to achieve greater scalability with current hardware technologies of noisy intermediate-scale devices.Thus, new quantum computer architectures with multiple processing units should consider additional circuit partitioning steps, with the generation of subcircuits with lower communication costs between partitions.This article presents a modular multi-QPU quantum computer architecture, as well as results with hypergraph partitioning of circuits, as a permanent layer in future distributed quantum system architectures.
When dealing with NISQ computers (Noise Intermediate Scale Quantum), it is widely accepted that distributing circuits among processing agents is an effective way to increase scalability with small machines. This approach can improve overall computational power, but it requires using qubits for communication between partitions, dedicated for the teleportation protocol over time. The main challenge is to minimize this communication cost by using efficient circuit partitioning strategies. There are many different partitioning approaches in the literature, but a consensus is needed on the best method for distribution scenarios. Here, we explore the partitioning process of quantum circuits using a hypergraphic representation for the circuit, to run this task. First, explore and compare different approaches of hypergraphic partitioning. Then, we created a variation of the Fiduccia-Mattheyses heuristic to minimize the communication qubits between partitions. Thanks to our tunning and an applied approach, we reduced the cost of partitioning circuits of 10% to 50% with respect to the different algorithms from state of art. Our method involves three steps: logical segmentation and grouping of gates; translation of the circuit into a hypergraphic representation; and use of the Fiduccia-Mattheyses heuristic variation for hypergraphic partitioning. This research explores quantum circuits partitioning for different scenarios as multi-QPU and distributed machine over classical communication, consolidating important results for quantum development in distributed scenarios, for a set of benchmark algorithms.
Distributing quantum workloads over many Quantum Processing Units (QPUs) is a crucial step in scaling up quantum computers toward practical quantum advantage due to the limitations in size of a single QPU. In the absence of high-fidelity quantum interconnects, circuit knitting could provide a path to computing certain properties of large quantum systems on many QPUs of limited size in a distributed fashion using only classical communication. Circuit knitting partitions large quantum circuits into manageable sub-circuits, however, reconstructing observables in a straightforward manner comes at an exponential cost in sampling and classical post-processing. To mitigate the overhead this technique incurs, we introduce an Adaptive Circuit Knitting (ACK) method that finds efficient partitions of quantum circuits by discovering regions of minimal entanglement between subsystems. We simulate 1D and 2D disordered mixed-field Ising models up to 60 qubits and show that the ACK approach can reduce circuit knitting sampling overheads by up to four orders of magnitude for observables of interest. We highlight our parallel GPU-accelerated implementation and discuss the need for efficient classical simulators to enable distributed quantum algorithm development. Our techniques could enable efficient distribution of quantum simulation for both near-term and fault-tolerant architectures.
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.