Quantum algorithms offer an exponential speedup over classical algorithms for a range of computational problems. The fundamental mechanisms underlying quantum computation required the development and construction of quantum computers. These devices are referred to as NISQ (Noisy Intermediate-Scale Quantum) devices. Not only are NISQ devices extremely limited in their qubit count but they also suffer from noise during computation and this problem only gets worse as the size of the circuit increases which limits the practical use of quantum computers for modern day applications. This paper will focus on utilizing quantum circuit partitioning to overcome the inherent issues of NISQ devices. Partitioning a quantum circuit into smaller subcircuits has allowed for the execution of quantum circuits that are too large to fit on one quantum device. There have been many previous approaches to quantum circuit partitioning and each of these approaches differ in how they work with some focusing on hardware-aware partitioning, optimal graph-based partitioning, multi-processor architectures and many more. These approaches achieve success in their objective but they often fail to scale well which impacts cost and noise. The ultimate goal of this paper is to mitigate these issues by minimizing 3 important metrics; noise, time and cost. To achieve this we use dynamic partitioning for practical circuit cutting and we take advantage of the benefits of hybrid execution where classical computation will be used alongside quantum hardware. This approach has proved to be beneficial with respect to noise with classical execution enabling a 42.30% reduction in noise and a 40% reduction in the number of qubits required in cases where a mixture of classical and quantum computation were required.
Quantum algorithms offer an exponential speedup over classical algorithms for a range of computational problems. The fundamental mechanisms underlying quantum computation required the development and construction of quantum computers. These devices are referred to as NISQ (Noisy Intermediate-Scale Quantum) devices. Not only are NISQ devices extremely limited in their qubit count but they also suffer from noise during computation and this problem only gets worse as the size of the circuit increases which limits the practical use of quantum computers for modern day applications. This paper will focus on utilizing quantum circuit partitioning to overcome the inherent issues of NISQ devices. Partitioning a quantum circuit into smaller subcircuits has allowed for the execution of quantum circuits that are too large to fit on one quantum device. There have been many previous approaches to quantum circuit partitioning and each of these approaches differ in how they work with some focusing on hardware-aware partitioning, optimal graph-based partitioning, multi-processor architectures and many more. These approaches achieve success in their objective but they often fail to scale well which impacts cost and noise. The ultimate goal of this paper is to mitigate these issues by minimizing 3 important metrics; noise, time and cost. To achieve this we use dynamic partitioning for practical circuit cutting and we take advantage of the benefits of hybrid execution where classical computation will be used alongside quantum hardware. This approach has proved to be beneficial with respect to noise with classical execution enabling a 42.30% reduction in noise and a 40% reduction in the number of qubits required in cases where a mixture of classical and quantum computation were required.
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 (QC) is a new paradigm offering the potential of exponential speedups over classical computing for certain computational problems. Each additional qubit doubles the size of the computational state space available to a QC algorithm. This exponential scaling underlies QC’s power, but today’s Noisy Intermediate-Scale Quantum (NISQ) devices face significant engineering challenges in scalability. The set of quantum circuits that can be reliably run on NISQ devices is limited by their noisy operations and low qubit counts. This paper introduces CutQC, a scalable hybrid computing approach that combines classical computers and quantum computers to enable evaluation of quantum circuits that cannot be run on classical or quantum computers alone. CutQC cuts large quantum circuits into smaller subcircuits, allowing them to be executed on smaller quantum devices. Classical postprocessing can then reconstruct the output of the original circuit. This approach offers significant runtime speedup compared with the only viable current alternative—purely classical simulations—and demonstrates evaluation of quantum circuits that are larger than the limit of QC or classical simulation. Furthermore, in real-system runs, CutQC achieves much higher quantum circuit evaluation fidelity using small prototype quantum computers than the state-of-the-art large NISQ devices achieve. Overall, this hybrid approach allows users to leverage classical and quantum computing resources to evaluate quantum programs far beyond the reach of either one alone.
Noisy intermediate-scale quantum (NISQ) devices with limited qubit count and connectivity limit the scale of quantum circuits that can be executed. Circuit cutting methods simulate larger quantum computers by decomposing large circuits into small subcircuits that can be executed on NISQ hardware. Existing circuit cutting methods only consider the qubit count of the target hardware for finding the locations of cuts on the circuits. This can result in deeper subcircuits after mapping on the hardware. Fidelity decays exponentially with circuit depth and diminishes the quality of execution. We propose a circuit-cutting framework that reduces variance in the depth of subcircuits after mapping to the hardware. Our method formulates the initial circuit cutting as a multi-objective optimization problem based on an evolutionary search method with the number of cuts and the maximum depth of individual routed subcircuits as fitness objectives. This method is implemented as an extension to the existing Qiskit Circuit Cutting Addon, which allows for integration in existing flows. Our approach achieves reductions in routed subcircuit depth of up to 9.9% across benchmark circuits compared with baseline methods.
Abstract Hybrid quantum-classical algorithms are a leading approach for applying noisy intermediate-scale quantum (NISQ) devices to practical problems. A key challenge in this paradigm is determining how to partition large computational problems into smaller sub-tasks that can be executed on size-limited quantum hardware. Current methods often rely on static, predetermined partitioning strategies that primarily consider the problem's structure, often failing to adapt to the quantum processor's dynamic noise characteristics. In this work, we introduce and analyze a dynamic scheduling framework, named Dy-Part, designed to address this challenge. Dy-Part automates the partitioning decision by using a heuristic cost model that balances two competing factors: the expected infidelity of the quantum computation, which increases with circuit size, and the classical post-processing overhead, which increases as the problem is broken into more pieces. To find the optimal partition size that minimizes this cost, our framework employs an efficient ternary search, whose output guides a fast, greedy graph partitioning heuristic. We demonstrate and validate this approach using the Variational Quantum Eigensolver (VQE) to solve the Max-Cut problem. Our results, averaged over 30 random graph instances, show that while a static strategy is effective in low-noise regimes, Dy-Part provides a more robust solution as noise increases. For instance, on 12-node graphs with a high gate error rate ((ϵgate>10−2)), Dy-Part's dynamic strategy yields a mean approximation ratio more than double that of the static baseline. These results show that a dynamic, noise-aware scheduling approach can provide a robust method for configuring hybrid workflows, offering a practical pathway to maximizing the performance of near-term quantum computers.
Executing large quantum circuits is not feasible using the currently available NISQ (noisy intermediate-scale quantum) devices. The high costs of using real quantum devices make it further challenging to research and develop quantum algorithms. As a result, performing classical simulations is usually the preferred method for researching and validating large-scale quantum algorithms. However, these simulations require a huge amount of resources, as each additional qubit exponentially increases the computational space required. Distributed Quantum Computing (DQC) is a promising alternative to reduce the resources required for simulating large quantum algorithms at the cost of increased runtime. This study presents a comparative analysis of two simulation methods: circuit-splitting and full-circuit execution using distributed memory, each having a different type of overhead. The first method, using CutQC, cuts the circuit into smaller subcircuits and allows us to simulate a large quantum circuit on smaller machines. The second method, using Qiskit-Aer-GPU, distributes the computational space across a distributed memory system to simulate the entire quantum circuit. Results indicate that full-circuit executions are faster than circuit-splitting for simulations performed on a single node. However, circuit-splitting simulations show promising results in specific scenarios as the number of qubits is scaled.
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.