Abstract Effective circuit partitioning is critical for Noisy Intermediate-Scale Quantum (NISQ) devices, which are hampered by high error rates and limited qubit connectivity. Standard partitioning heuristics often neglect gate-specific error impacts, leading to suboptimal divisions with significant communication overhead and reduced fidelity. This paper introduces Fidelipart , a novel framework that transforms quantum circuits into a fidelity-aware hypergraph. In this model, gate error rates and structural dependencies inform the weights of nodes (gates) and hyperedges (representing multi-qubit interactions and qubit timelines), guiding an Mt-KaHyPar partitioner to minimize cuts through error-prone operations. We evaluated Fidelipart against BQSKit’s QuickPartitioner on 6-qubit/22-gate (‘Circuit S’), 10-qubit/55-gate (‘Circuit M’), and 24-qubit/88-gate (‘Circuit L’) benchmarks under a linear topology with a consistent local contiguous re-mapping strategy. Results demonstrate Fidelipart ’s superior performance. It achieved SWAP gate reductions ranging from 77.3% (Circuit L) to 100% (Circuit S) and up to a 52.2% decrease in cut qubits (Circuit L). These physical improvements directly translated to estimated fidelity gains ranging from 27.3% (Circuit S) to over 254.8% (Circuit M). While Fidelipart showed a modest runtime increase of 8-13% and variable effects on maximum partition depth, its substantial enhancement of circuit fidelity highlights the significant benefits of integrating detailed error-awareness into the partitioning process for more reliable NISQ computations.
Abstract Effective circuit partitioning is critical for Noisy Intermediate-Scale Quantum (NISQ) devices, which are hampered by high error rates and limited qubit connectivity. Standard partitioning heuristics often neglect gate-specific error impacts, leading to suboptimal divisions with significant communication overhead and reduced fidelity. This paper introduces Fidelipart , a novel framework that transforms quantum circuits into a fidelity-aware hypergraph. In this model, gate error rates and structural dependencies inform the weights of nodes (gates) and hyperedges (representing multi-qubit interactions and qubit timelines), guiding an Mt-KaHyPar partitioner to minimize cuts through error-prone operations. We evaluated Fidelipart against BQSKit’s QuickPartitioner on 6-qubit/22-gate (‘Circuit S’), 10-qubit/55-gate (‘Circuit M’), and 24-qubit/88-gate (‘Circuit L’) benchmarks under a linear topology with a consistent local contiguous re-mapping strategy. Results demonstrate Fidelipart ’s superior performance. It achieved SWAP gate reductions ranging from 77.3% (Circuit L) to 100% (Circuit S) and up to a 52.2% decrease in cut qubits (Circuit L). These physical improvements directly translated to estimated fidelity gains ranging from 27.3% (Circuit S) to over 254.8% (Circuit M). While Fidelipart showed a modest runtime increase of 8-13% and variable effects on maximum partition depth, its substantial enhancement of circuit fidelity highlights the significant benefits of integrating detailed error-awareness into the partitioning process for more reliable NISQ computations.
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.
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 is gaining momentum in revolutionizing the way we approach complex problem-solving. However, the practical implementation of quantum algorithms remains a significant challenge due to the error-prone and hardware limits of near-term quantum devices. For instance, physical qubit connections are limited, which necessitates the use of quantum SWAP gates to dynamically transform the logical topology during execution. In addition, to optimize fidelity, it is essential to ensure that 1) the allocated hardware has a low error rate and 2) the number of SWAP gates injected into the circuit is minimized. To address these challenges, we propose a suite of algorithms: the Fidelity-aware Graph Extraction Algorithm (FGEA) is used to identify the hardware region with the lowest probability of error, the Frequency-based Mapping Algorithm (FMA) allocates logical-physical qubits that reduce the potential distance of topological transformation, and the Heuristic Routing Algorithm (HRA) searches for an optimal swapping injection strategy. We evaluate the proposed algorithms on the IBM-provided Noisy Intermediate-Scale Quantum (NISQ) computer, using a dataset consisting of 17 different quantum circuits of various sizes. The circuits are executed on the IBM Toronto Falcon processor. The three proposed algorithms outperform the existing SABRE algorithm in reducing the number of SWAP gates required. Therefore, our proposed algorithms hold significant promise in enhancing the fidelity and reducing the number of SWAP gates required in implementing Quantum algorithms.
Current quantum computers do not yet have the required qubit resources to meet the demands of most practical quantum algorithms. To circumvent this constraint, the practice of dividing these algorithms into parts through quantum circuit cutting has been explored. Many of these works either show exponential scaling or are far from optimal solutions. In this paper, MosaiQC is presented as a novel framework to improve upon existing circuit cutting frameworks. A hybrid warmstart with refinement optimization is used to find cutting solutions, allowing the combination of both wire and gate cuts. Additionally, MosaiQC enables hardware partitions of mixed sizes. Furthermore, the refinement stage incorporates a fast approximate quadratic assignment solver to better place hardware partitions, demonstrating a mean local fidelity improvement of 19.56%±6.17% over the baseline algorithm. In runtime and sampling overhead costs, improvements of 2.88× and an average of 16.84% cut reduction (resulting in an average 5.83⋅1011× overhead reduction) are observed. MosaiQC demonstrates a superior trade-off for run speed and solution quality, while adding fundamental features excluded by most competitors. With this, MosaiQC demonstrates that scalable heuristic optimization can substantially reduce the computational overhead of circuit-cut placement for increasingly large quantum circuits.
The advancement of quantum computing into the utility scale requires compilation frameworks that can effectively manage the discrepancy between high-level algorithmic intent and the low-level physical constraints of contemporary hardware. Quantum circuit partitioning is a pivotal stage in this compilation pipeline, particularly when leveraging high-performance synthesis tools that are computationally bounded by the number of qubits. Existing partitioning approaches, such as ScanPartitioner [19] and QuickPartitioner [21], while effective, do not leverage structural patterns in circuits, limiting their ability to make globally informed local partitioning decisions. To address this gap, we propose a novel structural-aware quantum circuit partitioning method using a reinforcement learning (RL) framework that harnesses global circuit knowledge to guide local partitioning decisions, enabling more optimization opportunities at the sub-circuit level. Experimental results on benchmark circuits transpiled to satisfy IBM quantum hardware constraints show that our approach reduces the native two-qubit gate count compared to existing quantum circuit partitioners (ScanPartitioner and QuickPartitioner) with an average two-qubit gate reduction of 18.55% over baselines. This research establishes a scalable and robust methodology for partitioning quantum circuits, bridging the gap between exact and approximate synthesis in the Noisy Intermediate-Scale Quantum (NISQ) era and beyond.
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.