  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.
