A direct product theorem for one-way quantum communication

DOI10.4230/LIPICS.CCC.2021.27arXiv2008.08963OpenAlexW3091154708MaRDI QIDQ6115390

Publication date: 12 July 2023

Abstract: We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation

f s u b s e t e q m a t h c a l X i m e s m a t h c a l Y i m e s m a t h c a l Z

. For any

v a r e p s i l o n, z e t a > 0

and any

k g e q 1

, we show that [ mathrm{Q}^1_{1-(1-varepsilon)^{Omega(zeta^6k/log|mathcal{Z}|)}}(f^k) = Omegaleft(kleft(zeta^5cdotmathrm{Q}^1_{varepsilon + 12zeta}(f) - loglog(1/zeta) ight) ight),] where

m a t h r m Q_{v a r e p s i l o n}^{1} (f)

represents the one-way entanglement-assisted quantum communication complexity of

f

with worst-case error

v a r e p s i l o n

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'{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. 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, m a t h c a l X i m e s m a t h c a l Y, m a t h c a l A i m e s m a t h c a l B, m a t h s f V)

where

q

is a distribution on

m a t h c a l X i m e s m a t h c a l Y

anchored on any one side with anchoring probability

z e t a

, then [ omega^*(G^k) = left(1 - (1-omega^*(G))^5 ight)^{Omegaleft(frac{zeta^2 k}{log(|mathcal{A}|cdot|mathcal{B}|)} ight)}] where

o m e g a^{*} (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.

Full work available at URL: https://arxiv.org/abs/2008.08963

zbMATH Keywords

quantum communication communication complexity direct product theorem parallel repetition theorem one-way protocols

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)