On relating one-way classical and quantum communication complexities

Abstract

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}\to \mathcal{Z}\cup \{\perp \}$ be a partial function and $\hat{I}¼$ be a distribution with support contained in $f^{-1}(\mathcal{Z})$. Denote $d=|\mathcal{Z}|$. Let ${\mathsf{R}}_{\hat{I}}^{1,\hat{I}¼}\mu (f)$ be the classical one-way communication complexity of $f$; ${\mathsf{Q}}_{\hat{I}}^{1,\hat{I}¼}\mu (f)$ be the quantum one-way communication complexity of $f$ and ${\mathsf{Q}}_{\hat{I}}^{1,\hat{I}¼,\ast }\mu (f)$ be the entanglement-assisted quantum one-way communication complexity of $f$, each with distributional error (average error over $\hat{I}¼$) at most $\hat{I}\mu$. We show: 1) If $\hat{I}¼$ is a product distribution, $\hat{I}\cdot >0$ and $0\le \hat{I}\mu \le 1-1/d$, then, $${\mathsf{R}}_{2\hat{I}\mu -d\hat{I}{\mu }^2/(d-1)+\hat{I}\cdot }^{1,\hat{I}¼}(f)\le 2{\mathsf{Q}}_{\hat{I}}^{1,\hat{I}¼,\ast }\mu (f)+O(\log \log (1/\hat{I}\cdot )).$$ 2)If $\hat{I}¼$ is a non-product distribution and $\mathcal{Z}=\{0,1\}$, then $\forall \hat{I}\mu ,\hat{I}\cdot >0$ such that $\hat{I}\mu /\hat{I}\cdot +\hat{I}\cdot <0.5$, $${\mathsf{R}}_{3\hat{I}\cdot }^{1,\hat{I}¼}(f)=O({\mathsf{Q}}_{\hat{I}\mu }^{1,\hat{I}¼}(f)\cdot \mathsf{CS}(f)/\hat{I}{\cdot }^3),$$ where \[\mathsf{CS}(f) = \max_{y} \min_{z\in\{0,1\}} \vert \{x~|~f(x,y)=z\} \vert \enspace.\]