Optimal entanglement-assisted source coding under a balanced-difference promise

Technical Summary: Optimal Entanglement-Assisted Source Coding under a Balanced-Difference Promise

Problem Statement
This paper addresses the fundamental limits of entanglement assistance in zero-error source coding. Specifically, it investigates a task where a sender (Alice) receives a word $x \in \mathbb{Z}_q^n$ and a receiver (Bob) receives an unordered pair of candidates $\{u, v\}$ containing $x$. Alice does not know the pair. The goal is for Alice to send a single classical message to Bob, enabling him to identify $x$ with zero error, utilizing a shared finite-dimensional quantum state and local measurements. The candidates are constrained by a balanced-difference promise: for $n = q\ell$, the coordinatewise difference $v - u$ contains every residue modulo $q$ exactly $\ell$ times.

The central question is whether entanglement can reduce the number of required classical messages below what is achievable classically, and if so, what the exact minimum cost is for all parameter regimes ($q \ge 2, \ell \ge 1$).

Methodology
The author translates the coding task into a graph-theoretic problem. They define the balanced cyclic generalized Hadamard graph $\Omega(\mathbb{Z}_q)_n = \text{Cay}(\mathbb{Z}_q^n, S_{q,n})$, where vertices are words and edges connect pairs satisfying the balanced-difference promise. The minimum number of messages required for zero-error recovery corresponds to the entanglement-assisted chromatic number of this graph.

The proof strategy proceeds in three main stages:

1. Spectral Reduction: Using Fourier analysis on the abelian group $\mathbb{Z}_q^n$, the author diagonalizes the graph's adjacency matrix. The eigenvalues are expressed as averages of phase factors over the set of balanced shifts. This reduces the problem of finding the smallest eigenvalue (which provides a lower bound on the message count via the Lovász theta number and spectral bounds) to a combinatorial counting problem involving polynomial coefficients.
2. Combinatorial Counting: The author employs a switching argument to bound the number of "valid" assignments (those corresponding to specific polynomial coefficients) relative to the total number of assignments within non-monochromatic composition classes. They prove that for non-monochromatic compositions, the fraction of valid assignments is at most $1/(n-1)$.
3. Synthesis: Combining the spectral lower bound derived from the least eigenvalue with explicit protocol constructions (both entanglement-assisted and deterministic), they establish tight upper and lower bounds on the communication cost.

Key Contributions and Results
The paper provides a complete classification of the optimal communication cost based on the parity of $(q-1)\ell$:

• Odd Parity Case ($(q-1)\ell$ is odd):

  • The author constructs an explicit bipartition of the vertex set based on the sum of coordinates modulo $q$. They prove that every allowed candidate pair contains exactly one word from each partition class.
  • Result: The optimal protocol requires exactly 2 messages (1 classical bit).
  • Significance: This optimal cost is achieved by a deterministic protocol without any shared entanglement. Thus, entanglement provides no advantage in the odd-parity regime. The quantum chromatic number is 2, matching the classical chromatic number.

• Even Parity Case ($(q-1)\ell$ is even):

  • The author proves that the existing entanglement-assisted protocol, which uses $n$ messages (encoded in $\lceil \log_2 n \rceil$ bits), is optimal.
  • Result: The minimum number of messages is exactly $n$.
  • Significance: This establishes that even with arbitrary finite-dimensional shared states and arbitrary local POVMs, no protocol can use fewer than $n$ messages. This resolves a spectral assertion from Cao et al.'s Conjecture 6.3, proving that the least adjacency eigenvalue is $-D/(n-1)$ for all admissible lengths, removing previous restrictions on $n$.
  • Quantum Chromatic Number: The quantum chromatic number is determined to be $n$, matching the entanglement-assisted message count.

Additional Findings

• Block Coding: For $m$ independent instances of the task, the optimal message counts scale linearly: $n^m$ for even parity and $2^m$ for odd parity. Collective encoding does not reduce the message alphabet size below the product of single-instance optima.
• Variations: The results extend to cases where one residue occurs $\ell-1$ times (instead of $\ell$) in the difference, requiring $n+1$ messages in the even-parity regime.
• Formal Verification: All lemmas, theorems, and corollaries in the paper have been formally verified using the Lean 4 proof assistant with the Mathlib library.

Significance and Claims
The paper claims to settle the optimality of entanglement-assisted source coding for the balanced-difference promise across all integer parameters.

• In the even-parity regime, it demonstrates a strict separation between classical and quantum resources: while classical protocols require $\Theta(n)$ bits for large $n$, the entanglement-assisted protocol achieves the task with $\lceil \log_2 n \rceil$ bits. However, the paper emphasizes that entanglement cannot reduce the message count below $n$; it only compresses the bit-length of those messages.
• In the odd-parity regime, it shows that entanglement offers no advantage, as a simple deterministic partition suffices for optimal performance.
• The work resolves open spectral questions regarding generalized Hadamard graphs and provides a unified framework connecting graph spectra, Fourier analysis, and combinatorial counting to determine the precise limits of quantum communication advantages.