A Direct Product Theorem for One-Way Quantum Communication

Abstract

We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $f\subseteq \mathcal{X}\times \mathcal{Y}\times \mathcal{Z}$. For any $\epsilon ,\zeta >0$ and any $k\ge 1$, we show that \[ \mathrm{Q}^1_{1-(1-\varepsilon)^{Ω(ζ^6k/\log|\mathcal{Z}|)}}(f^k) = Ω\left(k\left(ζ^5\cdot\mathrm{Q}^1_{\varepsilon + 12ζ}(f) - \log\log(1/ζ)\right)\right),\] where ${\mathrm{Q}}_{\epsilon }^1(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with worst-case error $\epsilon$ and $f^k$ denotes $k$ parallel instances of $f$. As far as we are aware, this is the first direct product theorem for quantum communication. Our techniques are inspired by the parallel repetition theorems for the entangled value of two-player non-local games, under product distributions due to Jain, Pereszlényi and Yao, and under anchored distributions due to Bavarian, Vidick and Yuen, as well as message-compression for quantum protocols due to Jain, Radhakrishnan and Sen. Our techniques also work for entangled non-local games which have input distributions anchored on any one side. In particular, we show that for any game $G=(q,\mathcal{X}\times \mathcal{Y},\mathcal{A}\times \mathcal{B},\mathsf{V})$ where $q$ is a distribution on $\mathcal{X}\times \mathcal{Y}$ anchored on any one side with anchoring probability $\zeta$, then \[ ω^*(G^k) = \left(1 - (1-ω^*(G))^5\right)^{Ω\left(\frac{ζ^2 k}{\log(|\mathcal{A}|\cdot|\mathcal{B}|)}\right)}\] where ${\omega }^{\ast }(G)$ represents the entangled value of the game $G$. This is a generalization of the result of Bavarian, Vidick and Yuen, who proved a parallel repetition theorem for games anchored on both sides, and potentially a simplification of their proof.

arXiv comment31 pages, 1 figure