aiqbench analysis
This research establishes the fundamental limits of entanglement-assisted zero-error source coding by resolving Cao et al.'s conjecture for balanced cyclic generalized Hadamard graphs. By combining Fourier analysis with combinatorial counting, the authors prove that communication costs depend strictly on the parity of specific parameters, formalizing these results in Lean to ensure rigorous verification. The work provides definitive answers on when shared quantum states reduce classical message requirements versus when deterministic classical protocols suffice.
Optimal entanglement-assisted source coding under a balanced-difference promise
arXiv:2609.15757v1 Announce Type: new 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 $\mathbb{Z}_q^n$ with $n=q\ell$, each residue modulo $q$ occurs exactly $\ell$ times in their coordinatewise difference. For all integers $q\geq2$ and $\ell\geq1$, we prove that the task requires exactly $n$ messages when $(q-1)\ell$ 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.
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 $\mathbb{Z}_q^n$ with $n=q\ell$, each residue modulo $q$ occurs exactly $\ell$ times in their coordinatewise difference. For all integers $q\geq2$ and $\ell\geq1$, we prove that the task requires exactly $n$ messages when $(q-1)\ell$ 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.
arXiv:2609.15757 [quant-ph]
(or arXiv:2609.15757v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2609.15757 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 330 words
