Source-linked AI summary
CutQC: Using Small Quantum Computers for Large Quantum Circuit Evaluations
Wei Tang, Teague Tomesh, Martin Suchara, Jeffrey Larson, Margaret Martonosi
TL;DR
NISQ devices are constrained by noise and qubit counts, while classical simulation becomes impractical for larger circuits. CutQC cuts large circuits into smaller subcircuits, executes them on quantum devices, and reconstructs outputs through classical postprocessing. CutQC evaluates circuits up to 100 qubits and improves χ2 loss by 21% to 47% versus direct execution on large quantum computers.
Problem
NISQ noise and limited qubit counts constrain reliable quantum-circuit execution, while classical simulation is generally impractical for larger circuits.
Method
CutQC automatically cuts large circuits into smaller subcircuits for execution on smaller quantum devices, then reconstructs or samples the original output using scalable classical postprocessing.
Results
CutQC evaluates quantum circuits up to 100 qubits while improving χ2 loss by 21% to 47% across benchmarks versus direct executions on large quantum computers.
Takeaways & Limitations
The hybrid approach extends quantum-circuit evaluation beyond the reach of current quantum or classical methods alone while simultaneously improving output fidelity.
Takeaways & Limitations
Some benchmarks cannot be mapped within 10 cuts and 5 subcircuits, and several workloads have size or even-qubit restrictions.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
NISQ devices are constrained by noise, limited qubit counts, and poor scalability, while classical simulation becomes intractable for larger circuits. CutQC combines circuit cutting, small quantum devices, and classical postprocessing to extend circuit size, fidelity, and runtime performance.
- Motivation: NISQ devices face noise and scaling challenges that make reliable execution increasingly difficult as qubit counts grow.Reported noise sources include limited coherence time, frequency selection, crosstalk, and limited control bandwidth.
- Motivation: Larger devices can produce worse fidelity; the 53-qubit Rochester device failed to produce meaningful results for a 26-qubit BV circuit.A 10-qubit BV circuit on the 20-qubit Johannesburg device achieved below 1% fidelity.
- Motivation: Classical simulation provides noiseless ground truth but is not generally tractable, with 45-qubit simulations requiring tens of hours on thousands of nodes and hundreds of terabytes of memory.
- CutQC: CutQC automatically cuts large circuits into smaller subcircuits for execution on smaller quantum devices, then reconstructs or samples the original output through scalable classical postprocessing.
- Results: CutQC evaluates circuits up to 100 qubits on existing NISQ devices, beyond the reach of current quantum or classical methods alone.
- Results: CutQC improves χ2 loss by 21% to 47% across benchmarks and achieves 60X to 8600X runtime speedup over classical simulations.
2 BACKGROUND
Quantum circuits can be evaluated through classical simulation, direct quantum execution, or hybrid methods. Classical simulation supplies noiseless ground truth but scales exponentially, while quantum execution uses compiled, repeated measurements on hardware.
- Evaluation modes: Quantum programs are represented as sequences of single- and multiqubit gate operations and can be evaluated classically, quantum mechanically, or in hybrid mode.
- Classical simulation: State vector simulation sequentially multiplies unitary matrices with a state vector to produce error-free complex-amplitude outputs.An N-qubit operation is represented by a 2^N × 2^N unitary matrix.
- Circuit cutting: Figure 3 cuts a qubit wire by replacing it with four measurement-initialization circuit pairs whose subcircuits can be evaluated independently.The procedure yields three distinct upstream measurement circuits and four downstream initialization circuits because I- and Z-basis measurements share a physical implementation.
- Classical simulation: State vector simulation scales exponentially and is used as ground truth for benchmarking small quantum circuits and computing the χ2 noise metric.
- Quantum execution: NISQ hardware execution compiles circuits for device connectivity, native gates, noise, and crosstalk, then records measured classical bit strings across thousands of shots.
3 CIRCUIT CUTTING
CutQC cuts quantum circuits across qubit wires, executes the resulting smaller subcircuits with quantum devices, and reconstructs the original output through classical postprocessing. The approach is exact in theory, but practical reconstruction requires sufficient sampling and scalable handling of the exponentially growing postprocessing space.
- Circuit partitioning: CutQC uses vertical, timewise cuts on qubit wires to partition a large circuit into smaller subcircuits executable on devices with fewer qubits.A five-qubit circuit can be split into two three-qubit subcircuits by cutting one wire.
- Circuit partitioning: Pauli-basis decomposition enables a cut by measuring boundary qubits in Pauli bases and initializing corresponding qubits in eigenstates.The resulting subcircuits provide the terms needed for output reconstruction.
- Output reconstruction: For one cut, three upstream and four downstream subcircuit variations produce four Kronecker-product pairs that are summed in classical postprocessing.The five-qubit example evaluates these variations on a three-qubit device instead of a five-qubit device.
- Output reconstruction: The reconstructed output strictly equals the uncut circuit output mathematically, although insufficient subcircuit shots can produce nonconverged probabilities and negative reconstructed values.Real-device experiments used at most 8,192 shots per subcircuit and observed no negative results.
- Scaling challenges: With K cut edges, the cutting scheme evaluates all measurement-initialization combinations, yielding 4^K Kronecker products and making cut selection important for limiting overhead.A dynamic definition algorithm addresses classical postprocessing for locating solution states or sampling large output distributions.
4 FRAMEWORK OVERVIEW
CutQC automatically partitions arbitrary quantum circuits into device-sized subcircuits and reconstructs the original output with classical postprocessing. Its MIP formulation minimizes reconstruction overhead, while supporting full-state reconstruction or dynamic sampling when full probability storage becomes prohibitive.
- Framework pipeline: CutQC uses mixed-integer programming to find efficient cuts, evaluates the resulting subcircuits on small quantum devices, and reconstructs the original circuit outputs.The framework uses Gurobi for cut search and a parallel C reconstructor based on Kronecker products.
- Circuit model: The MIP search assigns multiqubit-gate vertices to subcircuits and models cuts on graph edges connecting those vertices.Single-qubit gates are ignored during cut finding; the formulation supports gates involving up to two qubits and can be generalized to multiqubit gates.
- Subcircuit constraints: Each subcircuit’s device demand combines original input qubits with initialization and measurement qubits induced by cuts, and must not exceed the device size D.The search also accepts a maximum number of subcircuits n_C.
- Optimization objective: The optimization objective minimizes floating-point multiplications required to reconstruct the circuit, capturing most computation for full 2^n-probability outputs.The formulation breaks equivalent subcircuit-labeling symmetries to improve solver efficiency.
- Postprocessing modes: Full-definition queries reconstruct every output probability, whereas dynamic-definition queries reduce postprocessing overhead by avoiding reconstruction of the entire 2^n-state distribution.Dynamic definition is motivated by the prohibitive memory required to store full probability outputs for larger circuits.
5 METHODOLOGY
The methodology benchmarks CutQC’s postprocessing and classical-simulation runtimes, evaluates circuits beyond available device sizes, and compares real-device fidelity against direct execution. Experiments span several representative gate-based circuit families and use χ² loss to measure distribution error.
- Runtime evaluation: The runtime study uses up to 16 compute nodes and scales Kronecker-product postprocessing time after at least 10 minutes per node when needed.End-to-end wall time is reported when postprocessing takes less than 10 minutes.
- Experimental scope: Experiments benchmark full-definition queries through 35 qubits and dynamic-definition queries through 100 qubits.The larger-scale dynamic experiments use uniform subcircuit-output distributions because accurate backends are unavailable at that scale.
- Runtime assumptions: Experiments constrain cut search to at most 5 subcircuits and 10 cuts, while assuming quantum-device runtime is negligible because superconducting gate times are nanoseconds.CutQC can execute subcircuits on multiple small quantum computers in parallel.
- Fidelity evaluation: Real-system fidelity compares CutQC using IBM’s 5-qubit Bogota device with direct execution on IBM’s 20-qubit Johannesburg device.The comparison uses χ² loss, where smaller values indicate better agreement with ground-truth distributions.
- Benchmarks: The benchmark suite includes Supremacy, AQFT, Grover, Bernstein–Vazirani, Adder, and hardware-efficient ansatz circuits.These circuits cover dense-output, algorithmic, arithmetic, and near-term variational workloads; valid sizes vary by benchmark implementation.
6 EXPERIMENT RESULTS
Experiments show that CutQC can evaluate circuits larger than available quantum devices while reducing postprocessing and improving output fidelity. Results span full-definition, dynamic-definition, and real-system evaluations.
- Full Definition Query: 60X to 8600X average runtime speedup over classical simulation is achieved for benchmark circuits using 10- to 25-qubit quantum computers.FD-query experiments use 16 compute nodes for postprocessing.
- Full Definition Query: CutQC’s postprocessing overhead depends on benchmark connectivity, circuit size, and quantum-computer size, with larger devices eventually showing diminishing runtime returns.Dense circuits and circuits that greatly exceed available quantum resources require more classical postprocessing; in some cases, that overhead exceeds classical-simulation benefits.
- Dynamic Definition Query: For dense-output Supremacy circuits, recursive zoom-in improves high-probability bins and builds a closer approximation to the ground-truth distribution.More recursions increase the definition of selected regions without storing the full distribution.
- Dynamic Definition Query: Recursion 4 locates the |1111⟩ solution state for a 4-qubit BV circuit executed on 3-qubit quantum computers.Dynamic definition recursively refines merged bins, while each recursion stores vectors of length 2^1 instead of 2^4.
- Dynamic Definition Query: CutQC evaluates benchmark circuits up to 24 qubits with decreasing χ2 across recursions, while its cumulative runtime is negligible relative to classical simulation.The evaluation uses up to 10 recursions and a maximum system memory setting of 10 qubits.
- Real QC Runs: 21% to 47% average χ2 reduction is achieved for different benchmarks, with nearly 60% reduction in the best cases.AQFT is omitted from the reduction summary because it experiences a negative reduction.
- Discussion: CutQC processes 2^35 bins for circuits up to 100 qubits with perfect postprocessing fidelity, while overall fidelity remains limited by NISQ noise.The paper states that improving NISQ devices should improve overall fidelity without increasing CutQC runtime.
- Discussion: 16-node postprocessing provides a 14X speedup over 1 node, indicating that CutQC can scale across CPU-based supercomputing platforms.The study expects stronger scaling when more cuts require additional Kronecker products.
7 RELATED WORK
Related work improves purely quantum execution, trades classical and quantum resources with higher overheads, or provides limited classical simulation coverage. CutQC is presented as a more flexible end-to-end alternative.
- Quantum Compilation: Quantum compilation techniques improve NISQ execution through calibration-aware mapping, operation scheduling, and repeated executions for error mitigation.These approaches focus on improving a purely quantum computing strategy.
- Hybrid Approaches: Prior hybrid approaches use simple qubit partitioning, exponentially higher postprocessing, or manually separated toy circuits.The paper contrasts CutQC as automatically selecting cut positions for arbitrary circuit structures.
- Classical Simulation: Previous classical-simulation methods either require massive computing resources or simulate very few output states with low fidelity.These limitations motivate hybrid evaluation approaches.
8 CONCLUSION
The conclusion presents CutQC as a hybrid strategy for executing quantum algorithms beyond current quantum or classical limits. It also positions automatic cutting and reconstruction as relevant as quantum hardware scales.
- Conclusion: CutQC leverages quantum and classical platforms together to execute quantum algorithms of up to 100 qubits while improving output fidelity.The reported results are described as beyond the reach of current quantum or classical methods alone.
- Conclusion: Automatic circuit cutting and efficient reconstruction provide a practical strategy for hybrid quantum/classical advantage as NISQ and fault-tolerant systems develop.The conclusion states that these techniques remain relevant across future hardware regimes.
A.1 Abstract
The artifact supplies source code for the end-to-end CutQC toolflow and benchmarking code for selected runtime and fidelity experiments. Its HPC parallel implementation is not included.
- Artifact: The artifact includes source code for the end-to-end CutQC toolflow and benchmarking code for several runtime and fidelity experiments.The supplied passage describes the artifact contents.
- Artifact: The HPC parallel version is not provided because different HPC platforms require different setups.This is an artifact-availability boundary rather than a runtime result.
A.2 Artifact Checklist •
The artifact checklist identifies the algorithms, compilation environment, hardware, runtime state, metrics, outputs, and experiments used for CutQC.
- A.2 Artifact Checklist •: The artifact uses mixed integer programming, dynamic definition, quantum mechanics, Intel icc, IBM superconducting quantum computers, and CutQC experiments measuring runtime and fidelity.Runtime is sensitive to CPU usage, and χ2 is defined by Equation 16.
A.3.1 How to Access.
The artifact requires specified software and IBMQ access, supports configurable experiments, and may reproduce lower speedups because its distributed implementation is unavailable. Fidelity results can also vary across replacement devices.
- A.3.1 How to Access.: Runtime results depend on the specified classical hardware, although relative speedup should be similar across hardware.
- A.3.1 How to Access.: Fidelity experiments require an active IBMQ account, while the artifact uses Python 3.7, Intel icc, Qiskit 0.23, and Gurobi 9.0+.
- A.3.1 How to Access.: The provided scripts run runtime and fidelity benchmarks, with runtime affected by IBMQ queue time and expected runtime of about 20 minutes.The runtime benchmark uses a 15-qubit QC, and the fidelity benchmark prints χ2.
- A.3.1 How to Access.: Users can adjust QC size, circuit size and type, parallel threads, memory, and IBM devices, but the artifact omits multi-node parallelism, potentially reducing speedup.The paper's 20-qubit Johannesburg device has retired; Boeblingen is recommended, while fidelity may vary on smaller available devices.