Structural Conditions for Distributed Quantum Advantage

Technical Summary: Structural Conditions for Distributed Quantum Advantage

Problem Statement
Quantum computing applications often require qubit counts exceeding the capacity of single processors. While distributed computing across multiple chips is a natural scaling strategy, it faces two primary obstacles when implemented via circuit cutting (a technique that removes inter-chip gates, runs subcircuits separately, and classically recombines results):

1. Exponential Sampling Cost: The classical "knitting" of measurement outcomes requires a number of samples that grows exponentially with the number of cut gates.
2. Loss of Quantum Advantage: If the resulting subcircuits are classically easy to simulate, the recombined result is also classically easy, negating any potential quantum advantage.

Furthermore, for variational algorithms, a third obstacle arises: Barren Plateaus, where gradient variances decay exponentially with system size, making training infeasible. The paper asks which circuit families can satisfy the conflicting requirements of affordable knitting, surviving classical hardness, and resolvable gradients simultaneously.

Methodology
The authors formulate a rigorous assessment framework based on three requirements for distributed quantum advantage under a stated resource budget:

1. Cut (Affordable Knitting): The sampling cost ($\Gamma_{cut}$) must remain polynomial (or constant) as the system grows.
2. Sim (Classical Difficulty): The "branch tasks" (the subcircuits with inserted local operations) must remain classically hard to simulate.
3. Train (Resolvable Gradients): For variational circuits, gradient variances must not decay exponentially (avoiding barren plateaus).

These requirements are translated into eight screening criteria (Table I) categorized by evidence tier:

• Tier 1 (Structural): Checks computable from the circuit generator (e.g., interface capacity $\kappa$, local depth $\chi$).
• Tier 2 (Numerical): Diagnostics at sizes reachable by classical simulation (e.g., gradient variance, seam entropy).
• Tier 3 (Theoretical): Proofs or citations regarding hardness or trainability guarantees.

The authors apply these criteria to eighteen circuit families from the literature, ranging from standard variational ansätze (VQE, QAOA) to topological state preparations. They also derive general theorems regarding scaling regimes:

• Theorem 1: If a cut is efficient but all branch tasks are classically easy, the entire distributed computation is classically easy.
• Theorem 2: Growing subcircuits behind a bounded or logarithmically growing interface keeps knitting affordable. Conversely, multiplying fixed-width subcircuits leads to exponential knitting costs.

Key Contributions

1. Formal Requirements: The paper establishes that a distributed advantage requires the coexistence of affordable knitting, classical hardness in subcircuits, and trainability. It proves that these conditions are structurally independent and often mutually exclusive in existing proposals.
2. Screening Framework: The authors provide a concrete set of criteria to evaluate circuit families, identifying that most existing proposals fail at least one condition (e.g., variational circuits often lack trainability guarantees; topological states often have interfaces that grow with system size, making knitting expensive).
3. Identification of FLDCs: The paper identifies Finite Local-Depth Circuits (FLDCs) with bounded interfaces as the only candidate architecture where these requirements might coexist. In FLDCs, the local depth and the number of blocks acting on any qubit are bounded, which theoretically supports gradient resolution even as total depth grows.
4. Experimental Proof of Principle: The authors implement a single-bridge distributed experiment on an IBM Nighthawk processor. They join two field-perturbed toric-code patches (up to 142 spins total) with a single variational entangling gate.
   • Simulation: Confirmed that the knitting cost remains constant and gradient variances do not decay exponentially for sizes up to 48 spins.
   • Hardware: Successfully reconstructed the connected contact correlation across the cut for up to 98 spins. While independent execution predicts zero correlation, the knitted result showed a non-zero correlation (retaining ~20% of the target signal at 98 spins), demonstrating that the bridge reconstruction recovers physically relevant information lost in independent execution.

Results

• Assessment of 18 Families: Most families failed the screening.
  • Cuttable but Easy: Sequential MPS preparation and Clifford toric codes with bounded contacts are cheap to cut but classically easy to simulate (Theorem 1).
  • Hard but Unaffordable: Topological states with extensive seams (e.g., transparent seams in toric codes) have high seam entropy, leading to exponential knitting costs.
  • The Exception: Only Weakly injective isometric tensor-network states (Row 11c) and the single-bridge toric code (Row 12b, this work) showed potential. However, for 11c, hardness is only established in the worst case, and for 12b, the hardness of branch tasks remains an open theoretical question.
• Hardware Experiment:
  • The knitted energies reproduced the field dependence of ideal circuits up to 142 spins, though signal magnitude decayed with depth due to noise.
  • Crucially, the contact correlation ($C_{ab}$) was recovered up to 98 spins, proving that the distributed reconstruction captures correlations that independent execution misses.
  • The experiment confirmed that for a bounded interface, the knitting cost does not grow with system size, and gradients remain resolvable within the tested range.

Significance and Claims
The paper claims to define the structural conditions necessary for distributed quantum advantage, moving beyond the assumption that any circuit can be distributed. It argues that:

• A "cheap" cut is insufficient; the subcircuits must retain classical hardness.
• The interface between subcircuits must be bounded (or grow logarithmically) to prevent exponential sampling costs.
• FLDCs with bounded interfaces represent a viable architectural path, as they theoretically allow for large total depth (necessary for long-range entanglement) while maintaining bounded local depth (necessary for trainability) and bounded interface (necessary for affordable knitting).

The authors are modest in their claims regarding the experimental results: the hardware demonstration is a classically verifiable proof of principle that bridge reconstruction can recover cross-patch correlations. It is not a demonstration of quantum advantage, as the branch tasks for the specific toric-code instance used remain classically tractable at the tested sizes. The primary contribution is the identification of the conditions under which advantage might be possible and the demonstration that a specific architecture (bounded-interface FLDC) satisfies the knitting and trainability criteria, leaving the classical hardness of the branch tasks as the remaining open challenge for future work.