Quantum advantage in zero-error function computation with side information
<|reference_start|>Quantum advantage in zero-error function computation with side information: 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.<|reference_end|>
@article{meng2024quantum,
    title={Quantum advantage in zero-error function computation with side
  information},
    author={Ruoyu Meng and Aditya Ramamoorthy},
    journal={arXiv preprint arXiv:2402.01549},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.01549},
    primaryClass={cs.IT math.CO math.IT quant-ph}
}