arXiv:2412.17704

ShotQC: Reducing Sampling Overhead in Quantum Circuit Cutting

Po-Hung Chen, Bo‐Hung Chen, Dah-Wei Chiou, Jie-Hong Roland Jiang

Published Dec 23, 2024• 0 citations

Abstract

The recently developed quantum circuit cutting technique greatly extends the capabilities of current noisy intermediate-scale quantum (NISQ) hardware. However, it introduces substantial overhead in both classical postprocessing and quantum resources, as the postprocessing complexity and sampling cost scale exponentially with the number of circuit cuts. In this work, we propose an enhanced circuit cutting framework, ShotQC, which effectively reduces the sampling overhead through two key optimizations: shot distribution and cut parameterization. The former employs an adaptive Monte Carlo strategy to dynamically allocate more quantum shots to subcircuit configurations that contribute more to the variance in the final outcome. The latter exploits additional degrees of freedom in postprocessing to further suppress variance. Integrating these optimizations, ShotQC significantly reduces the sampling overhead without increasing classical postprocessing complexity, as demonstrated across a range of benchmark circuits.

DOI: 10.48550/arxiv.2412.17704

Related papers

Circuit cutting with classical side information

Christophe Piveteau, Lukas Schmitt, David Sutter

Circuit cutting is a technique for simulating large quantum circuits by partitioning them into smaller subcircuits, which can be executed on smaller quantum devices. The results from these subcircuits are then combined in classical postprocessing to accurately reconstruct the expectation value of the original circuit. Circuit cutting introduces a sampling overhead that grows exponentially with the number of gates and qubit wires that are cut. Many recently developed quasiprobabilistic circuit cutting techniques leverage classical side information, obtained from intermediate measurements within the subcircuits, to enhance the postprocessing step. In this work, we provide a formalization of general circuit cutting techniques utilizing side information through quantum instruments. With this framework, we analyze the advantage that classical side information provides in reducing the sampling overhead of circuit cutting. Surprisingly, we find that in certain scenarios, side information does not yield any reduction in sampling overhead, whereas in others it is essential for circuit cutting to be feasible at all. Furthermore, we present a lower bound for the optimal sampling overhead with side information that can be evaluated efficiently via semidefinite programming and improves on all previously known lower bounds.

arXiv:2503.22384Physical Review ResearchJun 25, 20251 citation

Approximate Quantum Circuit Cutting

Daniel Chen, Betis Baheri, Vipin Chaudhary +3 more

Current and imminent quantum hardware lacks reliability and applicability due to noise and limited qubit counts. Quantum circuit cutting -- a technique dividing large quantum circuits into smaller subcircuits with sizes appropriate for the limited quantum resource at hand -- is used to mitigate these problems. However, classical postprocessing involved in circuit cutting generally grows exponentially with the number of cuts and quantum counts. This article introduces the notion of approximate circuit reconstruction. Using a sampling-based method like Markov Chain Monte Carlo (MCMC), we probabilistically select bit strings of high probability upon reconstruction. This avoids excessive calculations when reconstructing the full probability distribution. Our results show that such a sampling-based postprocessing method holds great potential for fast and reliable circuit reconstruction in the NISQ era and beyond.

arXiv:2212.01270Dec 2, 20221 citation

Approximate Quantum Circuit Reconstruction

Daniel Chen, Betis Baheri, Vipin Chaudhary +3 more

Current and imminent quantum hardware lacks reliability and applicability due to noise and limited qubit counts. Quantum circuit cutting — a technique dividing large quantum circuits into smaller subcircuits with sizes appropriate for the limited quantum resource at hand — is used to mitigate these problems. However, classical postprocessing involved in circuit cutting generally grows exponentially with the number of cuts and quantum counts. This article introduces the notion of approximate circuit reconstruction. Using a sampling-based method like Markov Chain Monte Carlo (MCMC), we probabilistically select bit strings of high probability upon reconstruction. This avoids excessive calculations when reconstructing the full probability distribution. Our results show that such a sampling-based postprocessing method holds great potential for fast and reliable circuit reconstruction in the NISQ era and beyond.

IEEE International Conference on Quantum Computing and Engineering (QCE)Sep 1, 202216 citations

Cut&Shoot: Cutting & Distributing Quantum Circuits Across Multiple NISQ Computers

Giuseppe Bisicchia, Alessandro Bocci, José Manuel García-Alonso +2 more

Currently, quantum researchers are facing the limitations of NISQ (Noisy Intermediate-Scale Quantum) computers, such as limited qubit counts and high sensitivity to external interference. In response to these challenges, two techniques have recently been proposed, among others, to enhance the execution of quantum circuits: circuit cutting and shot-wise distribution. Circuit cutting partitions large quantum circuits into smaller fragments that can be executed on today's NISQ devices. Shot-wise distribution leverages multiple heterogeneous quantum computers by distributing the shots of a single quantum circuit execution across various NISQ devices, improving resiliency and reducing overall execution time, in a flexible and customisable way. In this work, we investigate the synergic effect of a seamless composition of these two techniques into a unified pipeline of our own design, termed Cut&Shoot. This pipeline fragments a single quantum circuit into multiple independent sub-circuits, distributes the shots of each fragment across various quantum computers, and finally merges the results to reconstruct the output for the original circuit. Noisy simulation experiments seem to indicate that circuit cutting effectively reduces error rates, without the need to increase the number of shots performed. Shot-wise distribution, instead, while offering several qualitative advantages, does not significantly affect error rates, with negligible time overhead.

IEEE International Conference on Quantum Computing and Engineering (QCE)Sep 15, 20243 citations

Fast reconstruction algorithm based on HMC sampling

Hang Lian, Jinchen Xu, Yu Zhu +3 more

In Noisy Intermediate-Scale Quantum (NISQ) era, the scarcity of qubit resources has prevented many quantum algorithms from being implemented on quantum devices. Circuit cutting technology has greatly alleviated this problem, which allows us to run larger quantum circuits on real quantum machines with currently limited qubit resources at the cost of additional classical overhead. However, the classical overhead of circuit cutting grows exponentially with the number of cuts and qubits, and the excessive postprocessing overhead makes it difficult to apply circuit cutting to large scale circuits. In this paper, we propose a fast reconstruction algorithm based on Hamiltonian Monte Carlo (HMC) sampling, which samples the high probability solutions by Hamiltonian dynamics from state space with dimension growing exponentially with qubit. Our algorithm avoids excessive computation when reconstructing the original circuit probability distribution, and greatly reduces the circuit cutting post-processing overhead. The improvement is crucial for expanding of circuit cutting to a larger scale on NISQ devices.

Scientific ReportsOct 18, 20233 citations

Noise-aware selection of circuit cutting strategies under hardware noise non-uniformity

Debarthi Pal, Ritajit Majumdar, Padmanabha Venkatagiri Seshadri +2 more

Noise in contemporary quantum hardware is highly non-uniform across qubits and couplers, giving rise to localized low-noise "islands" within otherwise noisy device topologies. As quantum workloads scale, executions are increasingly forced to traverse high-noise regions, degrading algorithmic fidelity. Circuit cutting provides a route to circumvent such regions by decomposing large circuits into smaller subcircuits, but its practicality is limited by exponential sampling overhead and the lack of systematic guidance on how cut strategies should align with heterogeneous hardware noise. In this work, we present a hardware-noise-aware circuit cutting framework that explicitly exploits the spatial non-uniformity of noise in quantum devices. Rather than proposing a new cut-finding algorithm, we formalize the problem of device-constraint selection under realistic hardware noise and show that this choice critically determines both execution overhead and effective noise. Using a unified gate- and wire-cutting formulation, we demonstrate that small, hardware-informed relaxations in the device constraint yield exponential reductions in execution overhead while preserving alignment with low-noise hardware regions. Across representative workloads, our method achieves an average reduction in the number of circuit executions ranging from 5-54x for 20-qubit circuits, and enables tractable circuit cutting for 50-qubit circuits and application-level benchmarks where conventional strategies incur prohibitive overhead. These results establish noise-aware device-constraint selection as a necessary ingredient for making circuit cutting resource-efficient and practically deployable on contemporary quantum hardware.

quant-pharXiv:2604.24422Apr 28, 20260 citations