Title: Optimal wire cutting with and without classical communication
Abstract:
Circuit cutting is the process of partitioning large quantum circuits, which require more quantum memory than physically available, into smaller subcircuits. The original circuit can be simulated only running the individual subcircuits at the cost of a sampling overhead.
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 (space-like) and wire cuts (time-like). We argue that all existing circuit cutting techniques can be understood in the framework of quasiprobabilistic simulations of gates. Furthermore, we characterize the optimal overhead costs for wire cutting where the subcircuits can exchange classical information or not, introducing a new protocol based on quantum state teleportation. We show that the minimum cost of wire cutting with classical communication features a submultiplicative behavior in the number of cuts.