Cutting circuits with multiple two-qubit unitaries

Lukas Schmitt, Christophe Piveteau, David SutterQuantum 2025 · DOI

TL;DR

This paper tackles the challenge of simulating large quantum circuits on smaller quantum computers by developing a precise method for "cutting" circuits. They provide a closed-form formula for the optimal sampling overhead when cutting arbitrary two-qubit gates, proving that cutting multiple gates together is more efficient than cutting them individually, and that classical communication doesn't offer an advantage.

What Problem Does This Paper Address?

Quantum computers are powerful, but scaling them up to tackle complex problems is a major hurdle. Limited qubit counts and connectivity on current hardware mean that large quantum circuits, necessary for demonstrating quantum advantage, often cannot be run directly. "Circuit cutting" or "knitting" offers a solution by breaking down a large circuit into smaller, manageable subcircuits that can be executed on smaller devices. The challenge lies in the "sampling overhead" introduced by this process, which can scale exponentially with the number of cuts. This paper aims to precisely quantify this overhead for arbitrary two-qubit gates and explore whether combining cuts or using classical communication can improve efficiency.

Methods

The core of this work revolves around "quasiprobability simulation," a technique that replaces non-local gates (those spanning across the cut) with probabilistic mixtures of local operations. The efficiency of this method is characterized by a "γ-factor," which quantifies the sampling overhead. The authors derive a closed-form formula for this γ-factor for arbitrary two-qubit gates, utilizing their KAK decomposition. They then extend this analysis to parallel cuts (multiple gates in the same time slice) and "black box" cuts (gates separated by unknown operations). A key technique is the use of ancillary qubits and a "negativity trick" to implement the quasiprobability simulation without requiring classical communication between subcircuits.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • No Advantage from Classical Communication: For cutting two-qubit gates, allowing subcircuits to communicate classically doesn't reduce the sampling overhead compared to purely local operations. This is a significant finding, simplifying the practical implementation of circuit cutting.
  • Joint Cutting is Cheaper: Cutting multiple two-qubit gates simultaneously (in parallel or in a black box setting) is strictly more efficient than cutting each gate individually. This submultiplicative behavior of the γ-factor is a crucial insight for optimizing circuit cutting strategies.
  • Universal Formula for Two-Qubit Gates: The paper provides a general formula for the γ-factor of any two-qubit gate, based on its KAK decomposition. This allows for precise calculation of the sampling overhead for a wide range of two-qubit operations.
  • Black Box Cuts are Efficient: The overhead for cutting gates separated by arbitrary, unknown operations (black box cuts) is shown to be the same as for parallel cuts, without requiring classical communication. This is a powerful result for practical applications where the structure of the entire circuit might not be fully known or controllable.

Key Results

  • The optimal sampling overhead for cutting a single arbitrary two-qubit unitary $U$ is given by $\gamma(U) = 1 + 2 \sum_{i \neq j} |u_i||u_j|$, where $u_i$ are KAK coefficients.
  • For $n$ parallel copies of a two-qubit gate $U$, the overhead is $\gamma(U^{\otimes n}) = 2(1 + \Delta_U)^n - 1$, where $\Delta_U = \sum_{i \neq j} |u_i||u_j|$. This demonstrates strict submultiplicativity: $\gamma(U^{\otimes n}) < (\gamma(U))^n$ for $\gamma(U) > 1$.
  • The sampling overhead for cutting $N$ two-qubit gates in a black box setting is $1 + 2 \sum_{k \neq k'} |w_k||w_{k'}|$, where $w_k$ are products of KAK coefficients. This is the same as the parallel cut overhead.
  • The paper provides concrete examples for CNOT, SWAP, and CRx gates, showing their γ-factors and confirming the submultiplicative behavior.

Limitations and Future Work

The paper focuses on two-qubit unitaries. Characterizing the optimal sampling overhead for more general, larger unitaries remains an open question. The authors also suggest exploring the optimal overhead for non-unitary channels, where a strict separation between LO and LOCC might exist. Additionally, while the black box cut construction is efficient, it relies on ancillary qubits, and for complex interleaved operations, finding the optimal LO decomposition might be challenging. The paper also notes that their results for black box cuts do not apply to the black box setting where the interleaved operations are arbitrary but unknown.

Summary updated

BibTeX
@article{schmitt2025cutting,
  author = {Lukas Schmitt and Christophe Piveteau and David Sutter},
  title = {{Cutting circuits with multiple two-qubit unitaries}},
  journal = {Quantum},
  year = {2025},
  doi = {10.22331/q-2025-02-18-1634},
}
Figure