PaperlayerView exact revision on arXiv

Source-linked AI summary

Circuit knitting with classical communication

Christophe Piveteau, David Sutter

arXiv:2205.00016v3quant-ph

TL;DR

Limited qubit availability motivates circuit knitting, but quasiprobability simulation incurs sampling overhead. This paper analyzes whether classical communication helps and introduces joint gate-teleportation-based simulations, reducing the overhead for repeated nonlocal CNOTs from O(9^n) to O(4^n) with LOCC.

  • Problem

    The paper asks whether classical communication between local quantum computers can reduce the sampling overhead of quasiprobabilistically knitting circuits across limited-qubit devices.

  • Method

    The authors characterize γ-factors for local-operation settings and use classical communication with gate teleportation to jointly simulate repeated nonlocal gates.

  • Results

    For n nonlocal CNOT gates, LOCC reduces the overhead from O(9^n) to O(4^n), with analogous improvements for Clifford gates and restricted controlled-rotation regimes.

  • Takeaways & Limitations

    Classical communication can considerably reduce circuit-knitting overhead for nonlocal computations, although the benefit depends on the gate family and communication setting.

  • Takeaways & Limitations

    The technique requires additional quantum memory for stored Bell pairs, and its non-Clifford generalization remains incompletely understood.

Abstract

from arXiv · show

The scarcity of qubits is a major obstacle to the practical usage of quantum computers in the near future. To circumvent this problem, various circuit knitting techniques have been developed to partition large quantum circuits into subcircuits that fit on smaller devices, at the cost of a simulation overhead. In this work, we study a particular method of circuit knitting based on quasiprobability simulation of nonlocal gates with operations that act locally on the subcircuits. We investigate whether classical communication between these local quantum computers can help. We provide a positive answer by showing that for circuits containing $n$ nonlocal CNOT gates connecting two circuit parts, the simulation overhead can be reduced from $O(9^n)$ to $O(4^n)$ if one allows for classical information exchange. Similar improvements can be obtained for general Clifford gates and, at least in a restricted form, for other gates such as controlled rotation gates.

1 Introduction

The paper studies whether classical communication can reduce quasiprobability-simulation overhead in circuit knitting, where large circuits are partitioned across smaller devices. It develops analytic characterizations and a multi-gate technique showing substantial reductions for Clifford gates, while identifying scope limits for applications and non-Clifford generalizations.

  • Motivation: Circuit knitting partitions a large circuit into subcircuits on smaller devices, replacing nonlocal gates with locally executable operations and estimating measurement expectations by sampling.The approach addresses limited qubit availability but introduces sampling overhead and may require additional memory or communication resources.
  • Research question: The paper asks whether classical communication between the two local computers can reduce the sampling overhead, comparing LO, one-way communication, and LOCC settings.The LOCC setting permits two-way classical communication, while LO and one-way communication provide progressively more restricted protocols.
  • Single-gate analysis: For many two-qubit gates, including Clifford and selected controlled-rotation gates, a single gate gains no advantage from classical communication, and the paper derives closed-form γ-factor expressions.The exact characterization improves on prior upper bounds for the gates covered by the theorems and corollaries.
  • Multiple instances: The multi-gate technique uses bidirectional classical communication and gate teleportation to jointly simulate repeated nonlocal gates, rather than optimizing each gate independently.For repeated CNOTs, jointly generating Bell pairs exploits submultiplicativity of the γ-factor, at the cost of additional quantum memory.
  • Quantitative results: O(9^n) becomes O(4^n) for n nonlocal CNOT gates with LOCC, while the corresponding one-way-communication setting reaches O(8^n); SWAP overhead falls from O(49^n) to O(16^n).The LOCC CNOT result uses γ_LOCC(CNOT)=3 and a jointly simulated n-gate protocol.
  • Scope and open questions: The framework is most suitable for circuits with few nonlocal gates and classically intractable local computations, while non-Clifford extensions remain incomplete and controlled-rotation improvements are established only for π/3 < θ < 5π/3.Some gates still have unknown optimal overheads or unknown communication benefits, and practical use requires managing the memory trade-off from storing Bell pairs.

2 Circuit knitting using quasiprobability simulation

Quasiprobability circuit knitting replaces nonlocal gates with probabilistically sampled local operations, producing an unbiased estimate with sampling overhead. The γ-factor formalizes the minimum overhead and is invariant under local unitaries while potentially becoming strictly submultiplicative across gates.

  • Circuit-knitting procedure: A quasiprobability decomposition replaces a nonlocal gate with local operations sampled according to coefficient magnitudes and reweighted by coefficient signs.The resulting Monte Carlo estimator preserves the desired expectation value, while its required shot count increases with the decomposition overhead.
  • Circuit-knitting procedure: For n nonlocal gates, each gate is independently replaced during circuit shots, so the total sampling overhead scales exponentially with n.The exponential scaling limits the method to circuits with a reasonable number of nonlocal gates.
  • Overhead characterization: The γ-factor is the smallest achievable sampling overhead among quasiprobability decompositions over LO, one-way classical communication, or LOCC protocols.Optimal QPDs are precisely those attaining this minimum.
  • Overhead characterization: The γ-factor is invariant under local unitaries and can be strictly submultiplicative under tensor products, reducing overhead for jointly treated operations.Submultiplicativity is identified as central to reducing sampling overhead.

3 Local quasiprobability decompositions for states

For state preparation, LOCC sampling overhead is connected to robustness of entanglement. This connection shows that classical communication does not change the optimal overhead, while jointly preparing multiple Bell pairs can be cheaper than preparing them sequentially.

  • State-preparation overhead: The γ-factor for a bipartite state characterizes the optimal sampling overhead required to prepare it using quasiprobabilistic circuit knitting.The relevant reference state is a fixed product state, and the overhead is considered over local-operation and communication settings.
  • Entanglement connection: Classical communication does not change the sampling overhead for the task of preparing a bipartite state.The state-preparation result identifies the LOCC overhead through an entanglement measure.
  • Entanglement connection: For any density operator, γ_LOCC(ρ_AB) = 1 + 2E(ρ_AB), directly relating LOCC overhead to robustness of entanglement.The robustness measure is defined through separable-state decompositions involving nonnegative coefficients.
  • Bell-pair preparation: Joint preparation of two Bell states is cheaper than preparing two Bell states individually because the parallel process can use entanglement across the corresponding subsystems.The underlying overhead is strictly submultiplicative under tensor products.

4 Optimal decompositions for single instances

For single two-qubit unitary instances, the paper compares optimal overheads with local operations and classical communication. For a broad class including Clifford and controlled-rotation gates, communication provides no advantage and analytical decompositions are optimal.

  • Single-gate overheads: The paper characterizes γ_LOCC(U), γ_LO→CC(U), and γ_LO(U) for single two-qubit unitaries by matching a communication-based lower bound with a local-operation upper bound.Equality of these bounds establishes equality of the three overheads for the considered class.
  • Single-gate overheads: The analysis uses the Choi state of U, whose Schmidt coefficients provide a lower bound on the LOCC sampling overhead.The Choi state is formed using maximally entangled states on copies of the input systems.
  • Analytical characterization: For the theorem’s parameterized class, the overhead is expressed as 1 + 4|sin θX cos θX| + 4|sin θY cos θY| + 8|sin θX cos θX sin θY cos θY|.The parameters arise from the KAK decomposition of the two-qubit unitary.
  • Analytical characterization: For two-qubit Clifford gates and controlled rotation gates, classical communication offers no advantage for a single gate instance.Because the relevant upper bound is tight, the QPD introduced in prior work is optimal for these gates.

5 Reducing overhead for multiple instances

Gate teleportation converts repeated nonlocal-gate simulation into entangled-state preparation, trading quantum memory for lower effective sampling overhead. The method extends to Clifford gates and gives partial improvements for non-Clifford controlled rotations and one-way communication.

  • 5 Reducing overhead for multiple instances: Under LOCC, CNOT gates and Bell pairs are equally powerful resources, allowing n nonlocal CNOT simulations to be reduced to preparing n Bell pairs.Gate teleportation consumes preexisting Bell pairs to realize CNOT gates.
  • 5 Reducing overhead for multiple instances: Increasing the entanglement-factory size k lowers the effective γ-factor per CNOT but increases the additional quantum memory required.A factory producing k Bell pairs uses 2k additional qubits.
  • 5.1 General Clifford gates: For n nonlocal CNOT gates, LOCC reduces the sampling overhead to O(4^n), while SWAP overhead is reduced to O(16^n).These scalings follow from the corresponding Choi-state Schmidt coefficients.
  • 5.1 General Clifford gates: For Clifford gates, gate teleportation works through their Choi states because the resulting correction operators are local Pauli operations.This generalizes the multiple-instance CNOT technique to arbitrary Clifford unitaries.
  • 5.2 Non-Clifford gates: For CRX(θ), classical communication reduces sampling overhead when π/3 < θ < 5π/3, while the remaining θ values remain unresolved.The asymptotic effective γ-factor is bounded between 1 + |sin(θ/2)| and 1 + 2|sin(θ/2)|.
  • 5.3 One-way classical communication: With one-way classical communication, simulating n nonlocal CNOT gates scales as O(8^n), improving over O(9^n) under local operations.Postselection replaces communication in one direction but adds a factor of two per gate.

A Non-positive superoperators in quasiprobability simulation

The framework permits trace-nonincreasing and certain non-completely-positive operations in quasiprobability decompositions because measurement and postselection can simulate them.

  • A Non-positive superoperators in quasiprobability simulation: Trace-nonincreasing maps can be embedded in trace-preserving completely positive maps and simulated by measuring an auxiliary qubit with postselection.An undesired measurement outcome contributes zero to the final circuit result.
  • A Non-positive superoperators in quasiprobability simulation: A non-completely positive map can be represented as the difference of two completely positive trace-nonincreasing maps, with outcomes weighted by +1 or −1.The component maps must sum to another completely positive trace-nonincreasing map.

B The γ-factor is well-defined

The γ-factor minimum is well-defined because the relevant compact operation sets yield compact convex hulls, allowing continuous optimization to attain its minimum.

  • B The γ-factor is well-defined: Compactness of the operation set implies compactness of its convex hull.This provides the compact feasible region used in the optimization argument.
  • B The γ-factor is well-defined: The optimized quantity is well-defined because it minimizes a continuous function over a compact set.Equivalent quasiprobability decompositions preserve the same sampling overhead.
  • B The γ-factor is well-defined: Finite-round LOCC protocols form a compact set, and the optimizer is often a protocol with few rounds.The paper uses bounded-round LOCC protocols because the conventional LOCC set is not closed.

C Proofs

The appendix moves selected proofs out of the main manuscript and notes that the coefficients in the optimization need not be arbitrarily large.

  • C Proofs: Some proofs are placed in the appendix to improve manuscript readability.This is an organizational choice rather than a change to the results.
  • C Proofs: The quasiprobability coefficients can be restricted to finite values because every relevant operation admits a decomposition with finite sampling overhead.This supports the optimization argument for the γ-factor.

C.1 Proof of Lemma 3.1

The proof establishes the equivalence of the relevant simulation overhead factors by comparing separable-state and LOCC constructions in both directions.

  • The proof reduces the desired equality to showing γSEP(ρAB) ≤ γLOCC(ρAB) and γLO(ρAB) ≤ γSEP(ρAB).
  • Each completely-positive trace-nonincreasing LOCC component produces a separable, possibly subnormalized state from the unentangled input.The decomposition uses Fi = Fi,+ − Fi,− and states σi,± = Fi,±(|0⟩⟨0|AB).
  • Conversely, separable states can be decomposed into product states and prepared locally, supplying the reverse comparison needed for the equality.The product-state components are prepared by operations in LO(A, B).
  • Together, the two inequalities prove the assertion.

C.2 Proof of Theorem 4.3

The proof uses local-unitary invariance and KAK-form expressions to match lower and upper bounds for the relevant two-qubit gates. Under the stated assumptions, both bounds reduce to the same trigonometric expression.

  • Local-unitary invariance permits assuming U = exp(iθX X⊗X + iθY Y⊗Y + iθZ Z⊗Z).The proof then compares the lower bound from Lemma 4.1 with the upper bound from Lemma 4.2.
  • Assumption 1: Under θZ = 0, the upper bound becomes 1 + 4|sin θX cos θX| + 4|sin θY cos θY| + 8|sin θX cos θX sin θY cos θY|.
  • The Schmidt coefficients are obtained from singular values of the coefficient matrix D.The stated singular values are |cos θX cos θZ|, |cos θX sin θZ|, |sin θX cos θY|, and |sin θX sin θY|.
  • Assumption 1: The lower-bound expression is the same trigonometric quantity, so combining the two equations proves the assertion.
  • Upper-bound calculation: The operator expansion gives u0 = cos θX cos θY, u1 = i sin θX cos θY, u2 = i cos θX sin θY, and u3 = −sin θX sin θY.These coefficients are real or imaginary, simplifying the absolute-value terms in the upper-bound calculation.
  • Assumption 2: Under the second assumption, the gate is locally equivalent to SWAP, whose Choi state is effectively two Bell pairs.The proof separately derives matching lower and upper bounds for this case.
  • Assumption 2: For the SWAP case, the resulting expression evaluates to 7.

C.3 Proof of Corollary 4.4

The corollary reduces representative rotation and controlled-rotation gates to RXX forms using local basis changes. It also reduces two-qubit Clifford gates to four canonical representatives.

  • Rotation gates: Rσσ(θ) can be reduced to RXX(θ), which is locally equivalent to RXX(−θ).The KAK angles for RXX(−θ) are (θ/2, 0, 0).
  • Controlled-rotation gates: CRσ(θ) can be reduced to CRX(θ) by a target-qubit basis transformation.CRX(θ) is equivalent to RXX(−θ/2) up to local unitaries.
  • Clifford gates: Every two-qubit Clifford gate is locally equivalent to one of I, CNOT, iSWAP, or SWAP.Their KAK angles are respectively (0,0,0), (π/4,0,0), (π/4,π/4,0), and (π/4,π/4,π/4).
  • Clifford gates: These reductions allow the corollary to be completed by analyzing only the canonical gate representatives.
Loading 2205.00016v3…