Optimal wire cutting with classical communication

Abstract

Circuit knitting is the process of partitioning large quantum circuits into smaller subcircuits such that the result of the original circuits can be deduced by only running the subcircuits. Such techniques will be crucial for near-term and early fault-tolerant quantum computers, as the limited number of qubits is likely to be a major bottleneck for demonstrating quantum advantage. One typically distinguishes between gate cuts and wire cuts when partitioning a circuit. The cost for any circuit knitting approach scales exponentially in the number of cuts. One possibility to realize a cut is via the quasiprobability simulation technique. In fact, we argue that all existing rigorous circuit knitting techniques can be understood in this framework. Furthermore, we characterize the optimal overhead for wire cuts where the subcircuits can exchange classical information or not. We show that the optimal cost for cutting $n$ wires without and with classical communication between the subcircuits scales as $O(16^n)$ and $O(4^n)$, respectively.

arXiv comment17 pages, 5 figures

References in corpus (17)

• Error mitigation for short-depth quantum circuits
• Extending the computational reach of a noisy superconducting quantum processor
• Practical Quantum Error Mitigation for Near-Future Applications
• Everything You Always Wanted to Know About LOCC (But Were Afraid to Ask)
• Application of a resource theory for magic states to fault-tolerant quantum computing
• The Future of Quantum Computing with Superconducting Qubits
• Simulating Large Quantum Circuits on a Small Quantum Computer
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Doubling the size of quantum simulators by entanglement forging
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Quantifying magic for multi-qubit operations
• Robustness of Magic and Symmetries of the Stabiliser Polytope
• Circuit knitting with classical communication
• Constructing a virtual two-qubit gate by sampling single-qubit operations
• Fast quantum circuit cutting with randomized measurements
• Quasiprobability decompositions with reduced sampling overhead
• Overhead for simulating a non-local channel with local channels by quasiprobability sampling

Cited by in corpus (2)

• Mitigating errors in state preparation and measurement with noncomputational states
• Circuit Folding: Scalable and Graph-Based Circuit Cutting via Modular Structure Exploitation