On relating one-way classical and quantum communication complexities

Quantum 7, 1010 (2023).

https://doi.org/10.22331/q-2023-05-22-1010

Communication complexity is the amount of communication needed to compute a function when the function inputs are distributed over multiple parties. In its simplest form, one-way communication complexity, Alice and Bob compute a function $f(x,y)$, where $x$ is given to Alice and $y$ is given to Bob, and only one message from Alice to Bob is allowed. A fundamental question in quantum information is the relationship between one-way quantum and classical communication complexities, i.e., how much shorter the message can be if Alice is sending a quantum state instead of bit strings? We make some progress towards this question with the following results.
Let $f :mathcal{X} times mathcal{Y} rightarrow mathcal{Z} cup {bot}$ be a partial function and $mu$ be a distribution with support contained in $f^{-1}(mathcal{Z})$. Denote $d=|mathcal{Z}|$. Let $mathsf{R}^{1,mu}_epsilon(f)$ be the classical one-way communication complexity of $f$; $mathsf{Q}^{1,mu}_epsilon(f)$ be the quantum one-way communication complexity of $f$ and $mathsf{Q}^{1,mu, *}_epsilon(f)$ be the entanglement-assisted quantum one-way communication complexity of $f$, each with distributional error (average error over $mu$) at most $epsilon$. We show:

1) If $mu$ is a product distribution, $eta gt 0$ and $0 leq epsilon leq 1-1/d$, then,

$mathsf{R}^{1,mu}_{2epsilon -depsilon^2/(d-1)+ eta}(f) leq 2mathsf{Q}^{1,mu, *}_{epsilon}(f) + O(loglog (1/eta))enspace.$

2)If $mu$ is a non-product distribution and $mathcal{Z}={ 0,1}$, then $forall epsilon, eta gt 0$ such that $epsilon/eta + eta lt 0.5$,

$mathsf{R}^{1,mu}_{3eta}(f) = O(mathsf{Q}^{1,mu}_{epsilon}(f) cdot mathsf{CS}(f)/eta^3)enspace,$

where

$mathsf{CS}(f) = max_{y} min_{zin{0,1}} vert {x~|~f(x,y)=z} vert enspace.$