Overcoming the Sampling Bottleneck in Quantum Circuit Cutting

23 concepts14 papers1 proposal

Today's Noisy Intermediate-Scale Quantum (NISQ) devices are severely limited by their qubit counts and gate fidelities. To run large, practical quantum algorithms on this limited hardware, researchers use a technique called circuit cutting (or circuit knitting). The core idea is simple: take a large quantum circuit, cut its long-range wires or non-local gates, and execute the resulting smaller subcircuits on separate, smaller quantum devices.

However, this hardware-bypassing strategy comes with a steep catch: an exponential sampling overhead. To reconstruct the exact output of the original uncut circuit, the subcircuits must be executed across a vast number of different measurement and preparation configurations. The total number of classical samples (or "shots") required scales exponentially with the number of cuts, creating a severe classical post-processing bottleneck that can quickly render the approach computationally prohibitive.

To make circuit cutting practical, a growing body of research focuses on understanding why this overhead occurs and developing mathematical and algorithmic strategies to suppress it.


Why Circuit Cutting Costs Exponentially More Shots

To understand why circuit cutting incurs an exponential sampling tax, we have to look at how a cut is represented mathematically. When we cut a quantum wire or a two-qubit gate, we are breaking a quantum channel. Because we cannot directly transmit quantum states between disconnected hardware fragments, we must mimic the channel classically.

We do this using a quasiprobability decomposition. The identity channel (a wire) or a unitary gate is expanded into a linear combination of simpler, localized operations:

$$\mathcal{M} = \sum_{i} c_i \mathcal{E}_i$$

Because quantum operations involve entanglement and interference, some of the coefficients $c_i$ in this expansion must be negative. When we sample from this decomposition to reconstruct an expectation value, we cannot sample using negative probabilities. Instead, we normalize the coefficients into a true probability distribution, which forces us to track a "sign" or weight for each shot.

The variance of this estimator scales with the robustness $\gamma = \sum_i |c_i|$. For a single cut, the number of required samples scales by $\gamma^2$. Crucially, when we make $k$ independent cuts, the operations tensor together, causing the total robustness to compound multiplicatively:

$$\text{Total Shots} \propto \gamma^{2k}$$

As highlighted by Ufrecht et al. in Optimal joint cutting of two-qubit rotation gates, this statistical tax demands a massive increase in circuit executions to maintain accuracy. Whether applying cutting to distributed quantum neural networks (Pira et al. in An Invitation to Distributed Quantum Neural Networks), financial sentiment analysis (Stein et al. in Applying QNLP to Sentiment Analysis in Finance), or distributed optimization frameworks (Huang et al. in A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm), this exponential scaling remains the primary barrier to scalability.

To combat this, researchers have developed four primary strategies.


Strategy 1: Joint Cutting and Structural Optimization

The most direct way to lower the exponential overhead is to reduce the base of the exponent, $\gamma$. If we treat every cut independently, the overhead is strictly multiplicative. However, if we cut multiple gates together, we can exploit their shared algebraic structure to find a more efficient joint quasiprobability decomposition.

Ufrecht et al. demonstrated this by introducing a virtual gate-teleportation protocol for the joint cutting of two-qubit rotation gates. By optimizing the decomposition globally across multiple gates, the authors significantly reduced the sampling overhead compared to cutting gates individually.

In Cutting circuits with multiple two-qubit unitaries, Sutter derived a closed-form formula for the optimal sampling overhead of arbitrary two-qubit gates, proving mathematically that joint cutting always meets or outperforms individual cutting.

Other structural approaches leverage alternative mathematical frameworks to optimize the cuts. For instance, Periyasamy et al. utilized the graphical language of ZX calculus in Cutting multi-control quantum gates with ZX calculus to decompose complex multi-controlled gates. This method achieves a sampling overhead that remains constant relative to the number of control qubits, while simultaneously slashing the physical CNOT gate count to improve noise resilience.


Strategy 2: Leveraging Classical Communication

Traditional "incoherent" circuit cutting assumes that subcircuits are executed completely in isolation, with their data aggregated entirely during classical post-processing. However, if we allow classical communication between subcircuits during the execution of the broader workload, we can alter the fundamental bounds of the sampling overhead.

In Circuit Knitting With Classical Communication, Sutter demonstrated that allowing subcircuits to pass classical measurement outcomes to downstream fragments can significantly reduce simulation overhead. By conditioning later operations on earlier results, classical communication effectively prunes the space of required quasiprobability configurations.

Sutter expanded on this in Optimal Wire Cutting With Classical Communication, providing a rigorous characterization of the optimal sampling overhead bounds. The work proves that while independent wire cuts without communication suffer from a strict multiplicative cost increase, introducing classical communication breaks this bottleneck, unlocking substantial efficiency gains for multi-cut scenarios.


Strategy 3: Pruning the Reconstruction Space

Another highly effective approach is to avoid calculating the full, exact reconstruction tensor product altogether. Not all basis elements or subcircuit configurations contribute equally to the final expectation value.

Neglecting Uninformative Elements

In Efficient Quantum Circuit Cutting by Neglecting Basis Elements, Chen et al. identified that certain basis elements carry zero or negligible information across a circuit cut. By dynamically identifying and neglecting these elements, the authors achieved up to a 33% speedup in classical reconstruction time without sacrificing accuracy.

Similarly, Chen et al. developed an online detection method in Online Detection of Golden Circuit Cutting Points to pinpoint "golden cutting points" that naturally minimize redundant classical computations during measurement reconstruction.

State-Dependent Optimization

Instead of optimizing a circuit cut for arbitrary inputs, we can tailor the decomposition to the specific quantum states flowing through the wire. In State Dependent Optimization with Quantum Circuit Cutting, Li et al. introduced a framework that optimizes subcircuits based on their specific input and measurement states. This targeted pruning achieved up to a 73% reduction in the average gate count per term, significantly mitigating noise and post-processing overhead.

Approximate Reconstruction via MCMC

When exact classical reconstruction is entirely out of reach due to a high number of cuts, we can turn to statistical approximation. Chen et al. proposed this shift in Approximate Quantum Circuit Reconstruction. Instead of computing the vast, exponential combination of all potential outcomes, the authors leveraged Markov Chain Monte Carlo (MCMC) techniques to intelligently sample the most significant measurement outcomes. This approach bypasses the exact reconstruction bottleneck, making the execution of highly partitioned circuits feasible on NISQ hardware.


Strategy 4: Minimizing the Number of Cuts

Because the sampling overhead scales exponentially with the number of cuts ($k$), the most powerful mathematical lever available is simply reducing $k$ itself.

Co-designing with Qubit Reuse

One way to avoid making a cut is to reuse the qubits we already have. In QRCC: Evaluating Large Quantum Circuits on Small Quantum Computers through Integrated Qubit Reuse and Circuit Cutting, Pawar et al. introduced a framework that integrates circuit cutting with mid-circuit measurement and qubit reset (qubit reuse). By measuring a qubit, logging its classical state, and resetting it to handle a different part of the computation, the QRCC framework drastically reduces the number of physical wire cuts required, yielding lower post-processing overhead and higher overall fidelity.

Naive Circuit Cutting:
Circuit ─── [Cut] ─── Subcircuit 1 (Run separately)
        └─── [Cut] ─── Subcircuit 2 (Run separately) -> Compounding Exponential Overhead

Integrated QRCC:
Circuit ─── [Mid-Circuit Measure & Reset] ─── Qubit Reused -> Fewer Cuts Needed!

Parallelizing via Commuting Groups

When cuts are unavoidable, we can maximize the information extracted from every physical shot. In Efficient Circuit Wire Cutting Based on Commuting Groups, Li et al. developed a method that groups required subcircuit measurements into commuting sets. By measuring multiple properties simultaneously, this technique drastically reduces the total number of independent subcircuits and measurement shots needed to reconstruct the final answer, providing a scalable path forward for hardware with limited qubit counts.

Key Foundational Work

An Invitation to Distributed Quantum Neural Networks (2022) — contributed 3 concept elements to this direction.
Optimal joint cutting of two-qubit rotation gates (2023) — contributed 3 concept elements to this direction.
Online Detection of Golden Circuit Cutting Points (2023) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_exponential_sampling_overhead_13f91a8c,
  title = {exponential sampling overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/exponential-sampling-overhead/rdr_13f91a8c5e4f446187b7887e743646b4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_exponential_sampling_overhead_13f91a8c_v1,
  title = {exponential sampling overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/exponential-sampling-overhead/rdr_13f91a8c5e4f446187b7887e743646b4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake