Optimal Wire Cutting With Classical Communication

Lukas Brenner, Christophe Piveteau, David SutterIEEE Trans. Information Theory 2025 · DOI

TL;DR

This paper tackles the problem of "circuit knitting," a technique for running large quantum circuits on smaller quantum computers by breaking them into sub-circuits. The authors provide a rigorous characterization of the optimal "sampling overhead" for wire cuts, both with and without classical communication between sub-circuits, showing significant improvements over existing methods.

What Problem Does This Paper Address?

Quantum computers are currently limited by the number of qubits available. To run larger, more complex quantum circuits, researchers employ "circuit knitting," which involves partitioning a large circuit into smaller sub-circuits that can be executed on available hardware. The results from these sub-circuits are then combined classically to reconstruct the outcome of the original circuit. A key challenge in circuit knitting is the "sampling overhead" – the increased number of times each sub-circuit must be run to obtain accurate results. This overhead scales exponentially with the number of "cuts" (ways the circuit is divided). This paper focuses specifically on "wire cuts," where a qubit's path is broken between sub-circuits, and aims to find the most efficient way to perform these cuts, especially when the sub-circuits can communicate classically.

Methods

The paper leverages the framework of "quasiprobability simulation" to analyze circuit knitting. This technique allows for the simulation of operations that are not directly implementable on a quantum computer by introducing a controlled form of "negative probability." The core of the paper involves finding "quasiprobability decompositions" (QPDs) of the identity channel (representing a wire cut) that minimize a quantity called the "gamma-factor" (γ), which directly corresponds to the sampling overhead.

The authors distinguish between two scenarios for wire cuts:

  1. Parallel wire cuts: Multiple wires are cut simultaneously within the same time slice.
  2. Arbitrary wire cuts: Wires can be cut at any position in the circuit.

For each scenario, they analyze the optimal sampling overhead with and without classical communication between the sub-circuits. They introduce novel techniques and proofs to establish the optimality of their proposed QPDs.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Classical communication offers a significant advantage for wire cutting: While gate cutting doesn't always benefit from classical communication, wire cutting shows a provable improvement, especially for multiple cuts.
  • Submultiplicativity is key: When classical communication is allowed, the cost of cutting multiple wires is less than the sum of the costs of cutting each wire individually. This "submultiplicative" behavior is crucial for achieving optimal overhead.
  • Wire cutting can be framed as gate cutting: The paper shows that wire cutting problems can be elegantly translated into the framework of quasiprobabilistic gate cutting, allowing for a unified analysis.
  • Optimal overheads are characterized: The paper provides explicit formulas for the optimal sampling overhead for both parallel and arbitrary wire cuts, with and without classical communication.

Key Results

The paper establishes the following optimal sampling overheads for cutting n wires:

  • Without classical communication:
    • Parallel wire cuts: $4^n$
    • Arbitrary wire cuts: $4^n$
    • This implies that for wire cuts without classical communication, there's no advantage in jointly cutting multiple wires; the cost is simply $n$ times the cost of a single wire cut.
  • With classical communication:
    • Parallel wire cuts: $2^{n+1} - 1$
    • Arbitrary wire cuts: $2^{n+1} - 1$
    • This shows a dramatic improvement, especially for larger $n$. For $n=1$, the overhead drops from $16$ to $3$. The submultiplicative property means the overhead for $n$ cuts is significantly less than $n$ times the overhead for a single cut.

Limitations and Future Work

  • Ancilla qubits: The proposed optimal protocol for arbitrary wire cuts with classical communication requires $n$ ancilla qubits. While the authors discuss how to reuse these qubits to maintain a constant number of ancillas, it's noted that this is a practical consideration.
  • Open question: It remains an open question whether the optimal sampling overhead for wire cutting can be achieved without the need for additional ancilla qubits.
  • Emulation of one-way communication: The paper highlights that for certain types of wire cuts (e.g., single wire cuts), the classical communication can be one-way, potentially allowing for emulation on a single quantum computer by sequential execution. This is a promising avenue for practical implementation.

Summary updated

BibTeX
@article{brenner2025optimal,
  author = {Lukas Brenner and Christophe Piveteau and David Sutter},
  title = {{Optimal Wire Cutting With Classical Communication}},
  journal = {IEEE Trans. Information Theory},
  year = {2025},
  doi = {10.1109/tit.2025.3601047},
}
Figure