Optimal entanglement-assisted source coding under a balanced-difference promise
Abstract
Entanglement can reduce the communication required for coding tasks, but establishing the minimum achievable cost is essential to understanding its limits. We address this question in a zero-error source-coding task where Alice receives a word and Bob knows an unordered pair of candidates containing it. Alice does not know the pair and must enable Bob to identify her word without error using shared entanglement and one classical message. The candidates satisfy a balanced-difference promise: for words in ℤqn with n=qℓ, each residue modulo q occurs exactly ℓ times in their coordinatewise difference. For all integers q≥2 and ℓ≥1, we prove that the task requires exactly n messages when (q−1)ℓ is even and two messages when it is odd. These minima allow arbitrary finite-dimensional shared states independent of the inputs and arbitrary local measurements. In even parity, this establishes optimality of an existing entanglement-assisted protocol. In odd parity, an explicit deterministic protocol achieves the optimum of one bit without entanglement. Our proof combines Fourier analysis with a combinatorial counting argument to determine the smallest eigenvalue of the associated graphs. In even parity, this resolves the spectral assertion of Cao et al.'s Conjecture 6.3 for balanced cyclic generalized Hadamard graphs. Together with an explicit odd-parity bipartition, this determines the quantum chromatic number as n in even parity and $2$ in odd parity, where the classical chromatic number is also $2$. All lemmas, theorems, and corollaries are formalized and verified in Lean.
Related
- Local flux high-order well-balanced WENO finite-difference methods for hyperbolic systems with source terms
- Solution to a fully coupled McKean-Vlasov forward-backward stochastic difference equation and applications to optimal control with law-delay
- Forbidden Sidon subsets of perfect difference sets, featuring a human-assisted proof
- Balanced Active Subspaces for Optimal Control via Trajectory Optimization
- Unconditional optimal convergence of a relaxation Crank-Nicolson difference scheme for 2D space-fractional NLS
BibTeX
@misc{zeiss2026optimal,
title = {{Optimal entanglement-assisted source coding under a balanced-difference promise}},
author = {Julius A. Zeiss},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15757},
eprint = {2609.15757},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15757},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal entanglement-assisted source coding under a balanced-difference promise
AU - Julius A. Zeiss
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15757
UR - https://arxiv.org/abs/2609.15757
AB - Entanglement can reduce the communication required for coding tasks, but establishing the minimum achievable cost is essential to understanding its limits. We address this question in a zero-error source-coding task where Alice receives a word and Bob knows an unordered pair of candidates containing it. Alice does not know the pair and must enable Bob to identify her word without error using shared entanglement and one classical message. The candidates satisfy a balanced-difference promise: for words in ℤ_q^n with n=qℓ, each residue modulo q occurs exactly ℓ times in their coordinatewise difference. For all integers q≥2 and ℓ≥1, we prove that the task requires exactly n messages when (q−1)ℓ is even and two messages when it is odd. These minima allow arbitrary finite-dimensional shared states independent of the inputs and arbitrary local measurements. In even parity, this establishes optimality of an existing entanglement-assisted protocol. In odd parity, an explicit deterministic protocol achieves the optimum of one bit without entanglement. Our proof combines Fourier analysis with a combinatorial counting argument to determine the smallest eigenvalue of the associated graphs. In even parity, this resolves the spectral assertion of Cao et al.'s Conjecture 6.3 for balanced cyclic generalized Hadamard graphs. Together with an explicit odd-parity bipartition, this determines the quantum chromatic number as n in even parity and $2$ in odd parity, where the classical chromatic number is also $2$. All lemmas, theorems, and corollaries are formalized and verified in Lean.
ER -