Abstract
We consider the problem of zero-error function computation with side information. Alice and Bob have correlated sources X,Y with joint p.m.f. p_XY(·, ·). Bob wants to calculate f(X,Y) with zero error. Alice encodes m-length blocks (m ≥ 1) of her observations to Bob over error-free channels, which can be classical or quantum. We consider two classical settings. (i) Alice communicates via a fixed length code (FLC), and (ii) Alice communicates via a variable length code (VLC). In the FLC scenario, the minimum communication rate depends on the asymptotic growth of the chromatic number of an appropriately defined m-instance ``confusion graph'' G^(m). In the VLC scenario, the corresponding rate is characterized by the asymptotics of the chromatic entropy of G^(m). %and has single-letter characterization in terms of K\"orner's graph entropy if G^(m) is m-times graph OR product. In the quantum setting, we only consider fixed length codes; the corresponding rate depends on the asymptotic growth of the orthogonal rank of the complement of G^(m). The behavior of the communication rates depends critically on G^(m), which is shown to be sandwiched between G^ m (m-times strong product) and G^∨ m (m-times OR product) respectively. Our work presents necessary and sufficient conditions on the function f(·, ·) and joint p.m.f. p_XY(·,·) such that G^(m) equals either G^ m or G^∨ m. Our work explores the multitude of possible behaviors of the quantum and classical (FLC/VLC) rates in the single-instance case and the asymptotic (in m) case for several classes of confusion graphs.