ECCC-Report TR20-131https://eccc.weizmann.ac.il/report/2020/131Comments and Revisions published for TR20-131en-usSun, 06 Sep 2020 08:33:09 +0300
Paper TR20-131
| A Direct Product Theorem for One-Way Quantum Communication |
Srijita Kundu,
Rahul Jain
https://eccc.weizmann.ac.il/report/2020/131We 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 $\varepsilon, \zeta > 0$ and any $k\geq1$, we show that
\[ \mathrm{Q}^1_{1-(1-\varepsilon)^{\Omega(\zeta^6k/\log|\mathcal{Z}|)}}(f^k) = \Omega\left(k\left(\zeta^5\cdot\mathrm{Q}^1_{\varepsilon + 12\zeta}(f) - \log\log(1/\zeta)\right)\right),\]
where $\mathrm{Q}^1_{\varepsilon}(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with worst-case error $\varepsilon$ 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 -- direct sum theorems were previously known for one-way quantum protocols. 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\'{e}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. In particular, we show that a direct product theorem holds for the distributional one-way quantum communication complexity of $f$ under any distribution $q$ on $\mathcal{X}\times\mathcal{Y}$ that is anchored on one side, i.e., there exists a $y^*$ such that $q(y^*)$ is constant and $q(x|y^*) = q(x)$ for all $x$. This allows us to show a direct product theorem for general distributions, since for any relation $f$ and any distribution $p$ on its inputs, we can define a modified relation $\tilde{f}$ which has an anchored distribution $q$ close to $p$, such that a protocol that fails with probability at most $\varepsilon$ for $\tilde{f}$ under $q$ can be used to give a protocol that fails with probability at most $\varepsilon + \zeta$ for $f$ under $p$.
Our techniques also work for entangled non-local games which have input distributions anchored on any one side, i.e., either there exists a $y^*$ as previously specified, or there exists an $x^*$ such that $q(x^*)$ is constant and $q(y|x^*) = q(y)$ for all $y$. In particular, we show that for any game $G = (q, \mathcal{X}\times\mathcal{Y}, \mathcal{A}\times\mathcal{B}, V)$ where $q$ is a distribution on $\mathcal{X}\times\mathcal{Y}$ anchored on any one side with anchoring probability $\zeta$, then
\[ \omega^*(G^k) = \left(1 - (1-\omega^*(G))^5\right)^{\Omega\left(\frac{\zeta^2 k}{\log(|\mathcal{A}|\cdot|\mathcal{B}|)}\right)}\]
where $\omega^*(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, i.e., where both a special $x^*$ and a special $y^*$ exist, and potentially a simplification of their proof.Sun, 06 Sep 2020 08:33:09 +0300https://eccc.weizmann.ac.il/report/2020/131