A Direct Product Theorem for One-Way Quantum Communication

We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation fsubseteqmathcal{X}timesmathcal{Y}timesmathcal{Z}. For any varepsilon, ζ> 0 and any kgeq1, we show that \[ \mathrm{Q}^1_{1-1-varepsilon^{Ωζ^6k/log|mathcal{Z}|}}f^k = Ω\leftkleft(ζ^5cdotQ1_{varepsilon + 12ζ}(f - \log\log(1/ζ)\right)\right),\] where Q¹_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. 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}timesmathcal{Y}, mathcal{A}timesmathcal{B}, mathsf{V}\) where q is a distribution on mathcal{X}timesmathcal{Y} anchored on any one side with anchoring probability ζ, then \[ ω^*G^k = \left1 - (1-ω^*(G)^5\right)^{Ω\leftfrac{ζ² k}{log(|mathcal{A}|cdot|mathcal{B}|}\right)}\] where ω^*(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.