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.
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.
Quantum computing holds immense promises for solving complex problems by leveraging quantum mechanics in a computational paradigm. However, challenges around the computational limitations of current noisy intermediate-scale quantum computers make it difficult to widely apply quantum advantages. These machines, with a limited number of qubits and high error rates, struggle to execute large quantum circuits, with higher dimensions of depth, size or width. To address those challenges, distributing circuits among processing agents or cutting circuits in small segments to be run in sequence are considered viable approaches to enhance scalability and computational power. The main goal for this paper is to present a hypergraphic representation approach for quantum circuit cutting, applicable to spatial and temporal scenario, using hypergraphic theory and heuristics. For each approach, the target is to reduce communication costs in the spatial scenario, and the initialization cost in the temporal scenario. To accomplish this, we apply heuristics for hypergraphic partitioning, considering the high level representation of the quantum circuit with different combinations of quantum gates. We compared results against different heuristics, such as Stoer-Wagner, Fiduccia-Mattheyses, and Kernighan-Lin, creating graphics based in a new circuit dimension called, coupling ratio for the circuit. The observed results from this method indicate the hypergraphic partitioning process as a critical step as part of a new reference architecture for quantum computers, in distributed quantum computing environments.
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.
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.
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.
Near-term hardware is constrained by high error rates, small qubit counts, and relatively low output fidelity, making the execution of large, high performance quantum circuits difficult. Circuit partitioning (or circuit cutting) has emerged as a promising approach to circumvent these limitations by decomposing circuits into smaller subcircuits at two-qubit interaction points. However, it remains unclear which classes of circuits benefit the most from partitioning and under what hardware conditions it is most effective. In this work, we evaluate the suitability of quantum circuits for partitioning from three perspectives: improving fidelity, enabling distributed execution, and scaling to larger circuit sizes. Specifically, we compare uncut circuit execution against two circuit partitioning approaches: Qiskit's automatic cut finding technique and a custom performance optimized circuit cutting method. We also measure these across GHZ, QFT, brickwork, and random quantum circuits ranging from 4 to 14 qubits, using mean absolute error of expectation values and overall output fidelity. Our results show that partitioning benefits larger, highly interconnected circuits, with our custom method reducing error by up to 55\% and improve fidelity for GHZ circuits, but degrading performance for brickwork circuits at larger scales.
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.