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 $\mu$ be a distribution with support contained in $f^{-1}(\mathcal{Z})$. Denote $d=|\mathcal{Z}|$. Let ${\mathsf{R}}_{\epsilon }^{1,\mu }(f)$ be the classical one-way communication complexity of $f$; ${\mathsf{Q}}_{\epsilon }^{1,\mu }(f)$ be the quantum one-way communication complexity of $f$ and ${\mathsf{Q}}_{\epsilon }^{1,\mu ,\ast }(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 >0$ and $0\le \epsilon \le 1-1/d$, then, $${\mathsf{R}}_{2\epsilon -d{\epsilon }^2/(d-1)+\eta }^{1,\mu }(f)\le 2{\mathsf{Q}}_{\epsilon }^{1,\mu ,\ast }(f)+O(\log \log (1/\eta )).$$ 2)If $\mu$ is a non-product distribution and $\mathcal{Z}=\{0,1\}$, then $\forall \epsilon ,\eta >0$ such that $\epsilon /\eta +\eta <0.5$, $${\mathsf{R}}_{3\eta }^{1,\mu }(f)=O({\mathsf{Q}}_{\epsilon }^{1,\mu }(f)\cdot \mathsf{CS}(f)/{\eta }^3),$$ where \[\mathsf{CS}(f) = \max_{y} \min_{z\in\{0,1\}} \vert \{x~|~f(x,y)=z\} \vert \enspace.\]

References in corpus (8)

• Quantum fingerprinting
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Min- and Max- Relative Entropies and a New Entanglement Monotone
• Reversing quantum dynamics with near-optimal quantum and classical fidelity
• The Quantum Reverse Shannon Theorem based on One-Shot Information Theory
• Multiparty Quantum Communication Complexity
• The Bounded Storage Model in The Presence of a Quantum Adversary
• Better bounds on optimal measurement and entanglement recovery, with applications to uncertainty and monogamy relations