Current browse context:
cs.IT
Change to browse by:
References & Citations
Computer Science > Information Theory
Title: Quantum advantage in zero-error function computation with side information
(Submitted on 2 Feb 2024 (v1), last revised 4 Mar 2024 (this version, v2))
Abstract: We consider the problem of zero-error function computation with side information. Alice has a source $X$ and Bob has correlated source $Y$ and they can communicate via either classical or a quantum channel. Bob wants to calculate $f(X,Y)$ with zero error. We aim to characterize the minimum amount of information that Alice needs to send to Bob for this to happen with zero-error. In the classical setting, this quantity depends on the asymptotic growth of $\chi(G^{(m)})$, the chromatic number of an appropriately defined $m$-instance "confusion graph". In this work we present structural characterizations of $G^{(m)}$ and demonstrate two function computation scenarios that have the same single-instance confusion graph. However, in one case there a strict advantage in using quantum transmission as against classical transmission, whereas there is no such advantage in the other case.
Submission history
From: Meng Ruoyu [view email][v1] Fri, 2 Feb 2024 16:41:36 GMT (27kb)
[v2] Mon, 4 Mar 2024 23:02:26 GMT (0kb,I)
Link back to: arXiv, form interface, contact.