Reducing the Entanglement Cost of Distributed Bipartite Quantum Computation with Constant Qubit Overhead

Technical Summary: Reducing the Entanglement Cost of Distributed Bipartite Quantum Computation with Constant Qubit Overhead

Problem Statement
Distributed quantum computation (DQC) connects multiple quantum processing units (QPUs) via quantum communication to execute large-scale tasks exceeding the capacity of a single device. A critical challenge in DQC is balancing two competing resource constraints: entanglement cost (the number of shared Bell pairs consumed) and qubit overhead (the number of auxiliary qubits required beyond the input state).

Existing literature establishes that for exact deterministic implementations of bipartite unitaries, the operator Schmidt rank ($\text{OpSch}(U)$) provides a fundamental lower bound on entanglement cost when qubit overhead is unrestricted. Specifically, the number of Bell pairs $k$ must satisfy $k \ge \lceil \log_2 \text{OpSch}(U) \rceil$. While this bound is known to be attainable for Clifford unitaries using gate teleportation, such methods typically require storing the Choi state of the unitary, resulting in a qubit overhead proportional to the system size (e.g., $2n_A, 2n_B$).

The central problem addressed in this work is whether this optimal entanglement lower bound can be approached or attained while restricting the qubit overhead to a constant (independent of the system size). Prior studies have optimized gate placement or grouping to reduce communication under qubit constraints but have not established if the theoretical lower bounds on entanglement are reachable under these strict constant-overhead conditions.

Methodology
The authors analyze the problem within an entanglement-assisted model where nonlocal gates are implemented via Local Operations and Classical Communication (LOCC) assisted by shared Bell pairs. The protocol allows for intermediate measurements, qubit resetting, and reuse of auxiliary qubits.

1. Clifford Unitaries:
   The authors introduce a decomposition lemma (Lemma 2) that breaks any bipartite Clifford unitary $U_c$ into a sequence of "elementary blocks." An elementary block is defined as a local Clifford transformation surrounding one of three core operations: the identity ($I_A \otimes I_B$), a nonlocal Controlled-Z ($CZ_{AB}$), or a nonlocal SWAP ($SWAP_{AB}$).

   • The authors prove that for any Clifford unitary, there exists a decomposition $U_c = e^{i\theta} G_1 G_2 \dots G_N$ such that the sum of the logarithms of the operator Schmidt ranks of the blocks equals the logarithm of the operator Schmidt rank of the total unitary: $\sum \log_2 \text{OpSch}(G_j) = \log_2 \text{OpSch}(U_c)$.
   • They demonstrate that each elementary block can be implemented with minimal entanglement (0, 1, or 2 Bell pairs respectively) and a constant qubit overhead of at most $(1, 2)$.
   • By sequentially implementing these blocks and resetting/reusing the auxiliary qubits between steps, the total overhead remains constant.

2. Non-Clifford Unitaries (Clifford+T):
   For unitaries specified by exact Clifford+T decompositions with a T-count of $t$, the authors construct an implementation by commuting Clifford factors to isolate the non-Clifford components.

   • They show that the non-Clifford components can be converted into a sequence of unitaries controlled by single qubits (or local operations), each implementable with at most one Bell pair and constant overhead.
   • The total entanglement cost is bounded by the lower bound for the underlying Clifford structure plus an excess term dependent on the T-count.

Key Contributions and Results

• Attainability of Lower Bounds for Clifford Unitaries:
  The paper proves Theorem 3: Every bipartite Clifford unitary admits an exact deterministic LOCC implementation that consumes exactly $\lceil \log_2 \text{OpSch}(U_c) \rceil$ Bell pairs (the theoretical minimum) while using at most two auxiliary qubits per QPU (qubit overhead $(2, 2)$). This result confirms that restricting qubit overhead to a constant does not increase the minimum entanglement cost for Clifford operations.

• Upper Bound for Non-Clifford Unitaries:
  The paper presents Theorem 4: For a bipartite unitary $U$ defined by a Clifford+T decomposition with T-count $t$, there exists an implementation with qubit overhead $(2, 2)$ consuming $K$ Bell pairs, where:
  $$K \le \lfloor \log_2 \text{OpSch}(U) \rfloor + 2t$$
  This bound indicates that the excess entanglement cost scales linearly with the T-count and is independent of the circuit depth or total gate count.

• Comparison with Existing Methods:
  Through a specific four-qubit example (Fig. 5), the authors demonstrate that their decomposition method achieves an entanglement cost of 3 ebits. This is strictly lower than previous methods: the hypergraph method (Andr´es-Mart´ınez and Heunen) required 5 ebits, and the packing method (Wu et al.) required 4 ebits, under the same fixed qubit allocation.

Significance and Claims
The authors claim that this work resolves the open question of whether the operator Schmidt rank lower bound is attainable under constant qubit overhead.

• For Clifford unitaries, the answer is affirmative: the optimal entanglement cost is achievable with a constant overhead of just two auxiliary qubits per party.
• For non-Clifford unitaries, the work provides a concrete upper bound on the "excess" entanglement cost, showing it is bounded solely by the T-count of the decomposition.

The paper modestly acknowledges that for non-Clifford unitaries, the derived upper bound is not necessarily tight, and the exact minimum entanglement cost under qubit-space constraints remains an open problem. However, the results establish that constant qubit overhead is sufficient to approach the fundamental limits of entanglement efficiency for a broad class of quantum operations, facilitating more resource-efficient distributed quantum computing architectures.