QRCC: Evaluating Large Quantum Circuits on Small Quantum Computers through Integrated Qubit Reuse and Circuit Cutting

Aditya Pawar, Yingheng Li, Zewei Mo, Yanan Guo, Xulong Tang, Youtao Zhang and 1 other

Today's quantum computers are small and noisy, so a circuit needing more qubits than a machine has must be chopped into pieces that each fit, run separately, and stitched back together with classical computation — but that stitching cost explodes exponentially with the number of cuts; this paper (University of Pittsburgh) shows that a second trick, reusing a qubit once it is done, actually creates opportunities to cut in fewer places, and it fuses qubit reuse with two kinds of circuit cutting into one solver-driven search that finds solutions with 29 percent fewer cuts.

The argument in one glance

Problem

A quantum circuit too big for the machine must be cut, but cutting is expensive

Today's quantum computers are in the noisy, intermediate-scale era: they have at most a few hundred physical qubits, those qubits are noisy, and some are so unreliable they must be left unused, so the largest circuit you can run with high fidelity is small. Many useful algorithms need far more qubits than that. One way to run a large circuit anyway is circuit cutting: chop the circuit into smaller subcircuits that each fit on the device, run each subcircuit, and reconstruct what the original circuit would have produced using classical post-processing on the results. It works, but there is a catch that dominates everything: the classical post-processing cost grows exponentially with the number of cuts. A circuit cut in a few places is fine; a circuit cut in many places becomes classically intractable to reconstruct. So the entire objective of circuit cutting is to fit the circuit onto the device using as few cuts as possible.
What people did

Use wire cutting, qubit reuse, or gate cutting, each on its own

Three techniques have been proposed to shrink a circuit to fit a small device: wire cutting (severing a wire between two parts of the circuit), qubit reuse (recycling a physical qubit once it is done for another logical qubit), and gate cutting (splitting a two-qubit gate into a sum of single-qubit ones). Each has been studied and applied on its own.
Why it fell short

Applied individually, they leave more cuts than necessary

Treating these techniques separately produces sub-optimal results, because they interact in ways a one-at-a-time approach cannot exploit. Wire cutting is optimized to minimize cuts by itself; qubit reuse is applied by itself; and gate cutting — which only works for a certain class of circuits and had not been well studied at the level of deciding where in a large circuit to cut — is often ignored entirely. Because the schemes are not co-optimized, they miss solutions that would need fewer cuts, and since post-processing cost is exponential in the cut count, every avoidable cut is disproportionately expensive. There was no framework that searched for the best combination of reuse and cutting together.
This paper's idea

Fuse qubit reuse with both kinds of cutting in one solver-driven search

QRCC integrates qubit reuse and circuit cutting — both wire cutting and gate cutting — into a single method for running large circuits on small machines. Its key observation is that the techniques help each other: cutting a wire lets a qubit finish its work early, which creates a fresh opportunity to reuse that qubit, and reusing qubits in turn eliminates cuts that would otherwise be needed. QRCC models the whole problem as an integer linear program and uses a solver to search the enlarged space for a solution that minimizes the number of cuts, adding gate cutting when only an expectation value is required. On average it finds solutions with 29 percent fewer cuts than the state of the art, and far more on the hardest circuits.

Why this problem is worth solving

The reason cutting is worth so much care is a hard exponential wall in the classical half of the computation.

Circuit cutting runs a large quantum circuit on a small device by partitioning it into subcircuits that each fit, executing them, and combining their measured results with classical computation to reconstruct what the whole circuit would have output. Wire cutting severs a connection between two parts of the circuit; to reconstruct across that severed wire, the post-processing must effectively sum over the possible quantum states that could have crossed it, and each additional cut multiplies the work, so the classical reconstruction cost grows exponentially with the number of cuts. This is the dominant cost of the whole approach: a circuit cut in a handful of places is reconstructable, but one cut in many places is not. Gate cutting is a related strategy that splits a two-qubit gate into a linear combination of single-qubit operations, again reconstructed classically, but because its post-processing cannot rebuild the full output distribution it applies only to circuits that compute an expectation value. In both cases, the number of cuts is the lever that controls tractability, which is why minimizing cuts is the singular goal, and why a method that finds fewer-cut solutions is directly a method for running larger circuits.

The complementary technique exploits a hardware capability that changes what “fitting” a circuit even means.

Qubit reuse lets a circuit that needs more logical qubits than the device has physical qubits still run, by recycling qubits over the course of the computation. The enabling hardware feature is mid-circuit measurement and reset: partway through a circuit, once a physical qubit has finished all the operations its current logical role requires, it can be measured, reset to a clean state, and redeployed to play a different logical qubit for the rest of the circuit. So a single physical qubit can serve as several logical qubits at different times, and a circuit whose logical width exceeds the machine’s physical width can be mapped on. Reuse depends on the circuit’s structure: a logical qubit can only be recycled after all its operations are done, so how early qubits finish determines how much reuse is possible. This is exactly where reuse and cutting meet, because cutting a wire ends a qubit’s obligations sooner and thus opens a reuse opportunity that did not exist before, which is the interaction QRCC is built to exploit.

What people did before, and where it broke

Wire cutting alone. Partition the circuit by severing wires, minimizing the number of wire cuts to keep classical post-processing tractable, as in the state-of-the-art CutQC. Where it broke. Optimizing wire cutting in isolation ignores that qubit reuse could remove cuts, so it settles for more cuts, and thus more exponential overhead, than a combined approach would need.
Qubit reuse alone. Use mid-circuit measurement and reset to recycle qubits so a wider logical circuit fits a narrower device. Where it broke. Applied on its own it does not coordinate with cutting decisions, missing that a well-placed wire cut would free a qubit earlier and enable reuse that eliminates other cuts.
Gate cutting under-explored. Recognize that splitting a two-qubit gate into single-qubit pieces is another way to cut, useful for expectation-value circuits. Where it broke. It had not been studied at the circuit level — deciding the best places to gate-cut a large circuit — and was largely left out of practical cutting frameworks, forgoing cut reductions it could provide.
Fall back to simulation or wait for bigger machines. Simulate the circuit classically, or run it only when a large enough quantum device is available. Where it broke. Classical simulation cost grows exponentially with qubit count and does not scale, and large quantum machines are scarce, noisy, and have limited public availability, so neither is a general answer.
The gap. No framework searched jointly over qubit reuse, wire cutting, and gate cutting, exploiting their interactions to minimize the total number of cuts. Because the cut count controls the exponential post-processing cost, co-optimizing these techniques rather than applying them one at a time is exactly what is needed, and it is what QRCC provides.

How QRCC works

Modeling reuse and cutting jointly, then solving for the fewest cuts

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

See qubit reuse and circuit cutting as one problem, because each unlocks the other. The waste in prior work comes from treating the techniques as independent tools, but they are structurally entangled: reuse recycles a qubit only after its operations end, and cutting a wire is one way to end a qubit’s operations early, so a cut can manufacture a reuse opportunity, and that reuse can in turn make other cuts unnecessary. QRCC’s foundational move is to stop optimizing them separately and instead search for the combination that, together, fits the circuit with the fewest cuts. Recycling a physical qubit once it has finished its role, so that a circuit needing more logical qubits than the device has can still run, is the same reuse mechanism the compiler-assisted qubit-reuse work covered elsewhere on this site is built on, exploiting mid-circuit measurement and reset to make a narrow device act wider — and QRCC’s contribution is to fold that reuse into the cutting decision rather than applying it afterward.

Bring gate cutting into the toolbox for the circuits that allow it. Wire cutting is general but is not the only way to sever a large circuit; a two-qubit gate can also be cut, decomposed into a linear sum of single-qubit gates whose results are recombined classically. This had been largely overlooked at the circuit level, yet for the important class of circuits that only need an expectation value — the setting of Hamiltonian simulation and many variational algorithms — gate cutting adds cutting locations that wire cutting cannot reach, giving the optimizer more ways to fit the circuit and thus fewer required cuts. Targeting the class of circuits whose useful answer is an expectation value, and specializing the method to exploit what that relaxation permits, is the same specialization the classical-bootstrap work for variational quantum algorithms covered elsewhere on this site relies on, taking advantage of the structure of expectation-value computations that full-distribution methods cannot. QRCC is the first framework to integrate wire and gate cutting, and to let both interact with reuse.

Turn the whole thing into a search a solver can optimize. Co-optimizing reuse, wire cutting, and gate cutting is a large combinatorial problem, so QRCC casts it as an integer linear program: the placement of cuts and reuses becomes a set of decision variables and constraints, and the objective — minimize the number of cuts — becomes the quantity the solver drives down. This formulation captures the interactions the individual heuristics miss, scales better than the prior state-of-the-art formulation, and is flexible enough to optimize under different goals by changing the objective. Reducing a hard combinatorial design choice to a solver formulation that searches for the option minimizing a costly resource, rather than hand-crafting a heuristic, is the same solver-aided strategy the solver-aided compiler work covered elsewhere on this site is built on, handing the intractable-by-hand decision to a general optimizer that can explore a far larger space of solutions.

Following a large circuit through QRCC

Fitting a circuit that needs more qubits than the device has

A trace, from the paper, of how integrating reuse with cutting finds a solution with fewer cuts than wire cutting alone, using the paper's running comparison against CutQC.

Step 1 of 5

The circuit is too wide for the device

A circuit needs more logical qubits than the small device provides, so it cannot run directly. Wire-cutting alone, as in CutQC, would split it into several subcircuits, but for a highly connected circuit it may need many cuts, or fail to find a fitting solution at all when the device is small.

For dense circuits like a quantum Fourier transform, with all-to-all two-qubit connections, the number of required wire cuts is large.

Why it works

Cutting and reuse reinforce each other, so joint search wins. Optimizing wire cutting and qubit reuse separately misses their interaction → but a cut ends a qubit’s work early to enable reuse, and reuse removes other needed cuts → so searching for the combination yields fewer total cuts than either technique alone.
Fewer cuts cut the exponential cost, not a linear one. Post-processing grows exponentially with the number of cuts, so each avoided cut is worth disproportionately much → but QRCC’s objective is exactly to minimize cuts → so a 29 percent average cut reduction translates into an outsized reduction in classical reconstruction cost.
Gate cutting adds options wire cutting cannot reach. For expectation-value circuits, wire cuts alone constrain where a circuit can be severed → but gate cutting splits two-qubit gates into single-qubit pieces at new locations → so the optimizer has more ways to fit the circuit and needs still fewer cuts.
An integer program captures interactions heuristics miss. Hand-tuned, one-at-a-time heuristics cannot see how reuse and cutting choices combine → but encoding the whole decision as an integer linear program lets a solver weigh them together → so QRCC finds co-optimized solutions and scales better than the prior formulation.
The gains are largest exactly where it matters most. Easy, sparsely-connected circuits are already cheap to cut → but dense, highly-connected circuits, where wire cutting needs many cuts or fails outright, are where reuse and gate cutting help most → so QRCC delivers its biggest reductions on the hardest cases, like the 32-to-6-cut quantum-Fourier-transform example.

What it costs (trade-offs and scope)

Gate cutting is limited to expectation-value circuits. The extra cut reductions from gate cutting apply only when the algorithm needs an expectation value, because gate-cutting post-processing cannot reconstruct a full output distribution. For circuits that need the full distribution, QRCC relies on wire cutting and reuse alone, and the additional gate-cut savings are unavailable.
The exponential wall is pushed back, not removed. QRCC minimizes cuts, but post-processing still grows exponentially in whatever cuts remain; a circuit that fundamentally requires many cuts is still expensive to reconstruct. The contribution is finding solutions with fewer cuts, not making cutting cheap in an absolute sense.
It inherits the costs and noise of hybrid execution. Running many subcircuits and reconstructing classically means more device executions and shots plus classical compute, and each subcircuit still runs on noisy hardware; the method improves fidelity per circuit by fitting better, but it does not escape the noise and sampling overheads intrinsic to the noisy-device era.
Solving the integer program has its own cost. Casting the joint problem as an integer linear program enables the search and scales better than prior formulations, but integer programming is itself hard in general; the framework caps quantities like the maximum number of cuts in experiments, and very large or dense circuits stress the solver.
Gains are benchmark- and connectivity-dependent. The 29 percent average and the dramatic best cases come on densely-connected circuits like the quantum Fourier transform; on circuits that are already easy to cut, such as an approximate transform with all-to-all connections removed, the improvement over wire cutting alone is negligible, so the benefit depends heavily on circuit structure.

The evaluation

Fitting a large circuit onto a small quantum device

Property	Wire cutting alone (CutQC)	Qubit reuse alone
Techniques used
Exploits reuse-cutting interaction
Gate cutting for expectation values	No	No
Search method		Heuristic
Number of cuts	Baseline	Not co-optimized

From the paper's evaluation against the state-of-the-art wire-cutting framework CutQC. QRCC reduces the number of cuts by 29 percent on average (with a variant at 24 percent), with far larger reductions on densely-connected circuits — for example from 32 cuts to 6 on an N-equals-30 quantum Fourier transform on a 27-qubit device — and further reductions when gate cutting is applicable, directly lowering the exponentially-scaling classical post-processing.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The contribution is a clean unification: qubit reuse, wire cutting, and gate cutting had each been used alone to fit large quantum circuits onto small devices, and QRCC is the first to co-optimize them, driven by the observation that cutting a wire frees a qubit early to enable reuse, and reuse in turn removes cuts. Because classical post-processing grows exponentially with the number of cuts, minimizing cuts is everything, and QRCC’s solver-based integer-programming search finds solutions with 29 percent fewer cuts on average than the state-of-the-art wire-cutting framework, up to dramatic reductions like 32 cuts to 6 on the hardest circuits, plus further savings from gate cutting on expectation-value circuits. Read that with its scope in mind. Gate cutting’s extra savings apply only to expectation-value circuits; the exponential post-processing wall is pushed back, not removed, since it still scales with the remaining cuts; the method inherits the noise and sampling overheads of running many subcircuits on noisy hardware; the integer program itself is costly and is bounded in the experiments; and the gains depend strongly on circuit connectivity, being negligible on already-easy circuits and largest on dense ones. Within those bounds, QRCC is a well-motivated step toward running larger quantum circuits on the small machines available today.

Background

Why running big circuits on small machines is the defining NISQ problem

It helps to see why so much ingenuity goes into stretching small quantum computers. The algorithms that make quantum computing exciting — for chemistry, optimization, and machine learning — generally need many high-quality qubits, and in principle a large, error-corrected quantum computer. But we are not there: current machines have at most a few hundred qubits, those qubits are noisy with short coherence times and crosstalk, and some are too unreliable to use at all, so the effective size is smaller still. Classical simulation is no escape, because its cost explodes exponentially with qubit count — a modest search algorithm once needed a supercomputer with thousands of nodes and hundreds of terabytes to simulate. So the central practical question of this era is how to run a computation that wants more qubits than any available machine has, and cutting a circuit into device-sized pieces with a classical stitch-up is one of the few general answers. That world, where the whole challenge is squeezing large quantum workloads onto scarce, imperfect hardware while the field waits for the machines to grow, is the same one the fault-tolerant million-qubit-scale distributed-computer work covered elsewhere on this site looks toward, imagining how a large quantum computer might eventually be assembled. QRCC is a tool for the meantime: making the small machines we have reach further.

If you remember only three things

1. Running a quantum circuit that needs more or better qubits than a small noisy device provides requires cutting it into device-sized subcircuits, running each, and reconstructing the result with classical post-processing whose cost grows exponentially with the number of cuts — so minimizing cuts is the whole objective; but the techniques for shrinking a circuit to fit (wire cutting, qubit reuse via mid-circuit measurement and reset, and the less-explored gate cutting) had each been applied in isolation, leaving more cuts, and thus more exponential overhead, than necessary.
2. QRCC integrates all three into one solver-driven search on the observation that they reinforce each other: cutting a wire lets a qubit finish its operations early, which opens a reuse opportunity, and reusing qubits removes cuts that would otherwise be needed to fit the device; it models the joint placement of cuts and reuses as an integer linear program and minimizes the number of cuts, adding gate cutting (splitting two-qubit gates into single-qubit pieces) for the class of circuits that only need an expectation value, where it opens cut locations wire cutting cannot reach.
3. Against the state-of-the-art wire-cutting framework CutQC, QRCC reduces the number of cuts by 29 percent on average, with far larger gains on densely-connected circuits (for example 32 cuts down to 6, an 81 percent reduction, on a hard quantum Fourier transform), plus additional reductions when gate cutting applies — directly shrinking the exponential classical post-processing; the trade-offs are that gate cutting is limited to expectation-value circuits, the exponential wall is pushed back rather than removed, the integer program itself is costly, and the benefit depends heavily on circuit connectivity.

Check yourself

Check your understanding

1. Why is minimizing the number of cuts the central goal of circuit cutting?
2. What is the key interaction between qubit reuse and circuit cutting that QRCC exploits?
3. What role does gate cutting play, and why is it limited?
4. How does QRCC search for a solution, and what did it achieve?

Sources

The paper is “QRCC: Evaluating Large Quantum Circuits on Small Quantum Computers through Integrated Qubit Reuse and Circuit Cutting” by Aditya Pawar, Yingheng Li, Zewei Mo, Yanan Guo, Xulong Tang, Youtao Zhang, and Jun Yang (University of Pittsburgh), published at ASPLOS 2024, DOI 10.1145/3622781.3674179.

This explainer is written from the full text of the authors’ arXiv version (arXiv:2312.10298). Everything above comes from the paper’s own sections: the introduction framing the noisy intermediate-scale era (devices with at most a few hundred noisy qubits, some frozen for unreliability, limited availability of large machines, and classical simulation cost growing exponentially with qubit count); the three mitigation techniques (wire cutting partitioning a circuit into subcircuits reconstructed by classical post-processing that grows exponentially with the number of cuts, qubit reuse via mid-circuit measurement and reset redeploying a finished physical qubit as another logical qubit, and gate cutting splitting a two-qubit gate into a linear sum of single-qubit gates for circuits computing expectation values); the observation that prior work applied these individually and sub-optimally and that gate cutting was under-explored at the circuit level; QRCC’s integrated approach and its key insight that wire cuts enlarge qubit-reuse opportunities which in turn eliminate cuts; the integer-linear-programming formulation that searches the enlarged space under different optimization goals with better scalability than the state-of-the-art CutQC; the end-to-end flow of modeling, solving, mapping to subcircuits, running, and reconstructing; the note that gate cutting applies only to expectation-value circuits because its post-processing cannot reconstruct a full distribution; and the evaluation reporting an average 29 percent reduction in the number of cuts (with a 24 percent variant) over CutQC, additional reductions from gate cutting, the largest gains on densely-connected circuits like the quantum Fourier transform (including a reduction from 32 cuts to 6, an 81 percent improvement, on an N-equals-30 circuit with a 27-qubit device) and negligible gains on already-easy circuits, together with the analysis that the number of cuts is the dominant factor in post-processing overhead.