Jain, Rahul ;
Kundu, Srijita
A Direct Product Theorem for OneWay Quantum Communication
Abstract
We prove a direct product theorem for the oneway entanglementassisted quantum communication complexity of a general relation f ⊆ 𝒳×𝒴×𝒵. For any 0 < ε < δ < 1/2 and any k≥1, we show that
Q¹_{1(1ε)^{Ω(k/log𝒵)}}(f^k) = Ω(k⋅Q¹_{δ}(f)),
where Q¹_{ε}(f) represents the oneway entanglementassisted quantum communication complexity of f with worstcase error ε and f^k denotes k parallel instances of f.
As far as we are aware, this is the first direct product theorem for the quantum communication complexity of a general relation  direct sum theorems were previously known for oneway quantum protocols for general relations, while direct product theorems were only known for special cases. Our techniques are inspired by the parallel repetition theorems for the entangled value of twoplayer nonlocal games, under product distributions due to Jain, Pereszlényi and Yao [Rahul Jain et al., 2014], and under anchored distributions due to Bavarian, Vidick and Yuen [Bavarian et al., 2017], as well as message compression for quantum protocols due to Jain, Radhakrishnan and Sen [Rahul Jain et al., 2005]. In particular, we show that a direct product theorem holds for the distributional oneway quantum communication complexity of f under any distribution q on 𝒳×𝒴 that is anchored on one side, i.e., there exists a y^* such that q(y^*) is constant and q(xy^*) = 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 f̃ which has an anchored distribution q close to p, such that a protocol that fails with probability at most ε for f̃ under q can be used to give a protocol that fails with probability at most ε + ζ for f under p.
Our techniques also work for entangled nonlocal 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(yx^*) = q(y) for all y. In particular, we show that for any game G = (q, 𝒳×𝒴, 𝒜×ℬ, 𝖵) where q is a distribution on 𝒳×𝒴 anchored on any one side with constant anchoring probability, then
ω^*(G^k) = (1  (1ω^*(G))⁵) ^{Ω(k/(log(𝒜⋅ℬ)))}
where ω^*(G) represents the entangled value of the game G. This is a generalization of the result of [Bavarian et al., 2017], 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.
BibTeX  Entry
@InProceedings{jain_et_al:LIPIcs.CCC.2021.27,
author = {Jain, Rahul and Kundu, Srijita},
title = {{A Direct Product Theorem for OneWay Quantum Communication}},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {27:127:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771931},
ISSN = {18688969},
year = {2021},
volume = {200},
editor = {Kabanets, Valentine},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14301},
URN = {urn:nbn:de:0030drops143017},
doi = {10.4230/LIPIcs.CCC.2021.27},
annote = {Keywords: Direct product theorem, parallel repetition theorem, quantum communication, oneway protocols, communication complexity}
}
08.07.2021
Keywords: 

Direct product theorem, parallel repetition theorem, quantum communication, oneway protocols, communication complexity 
Seminar: 

36th Computational Complexity Conference (CCC 2021)

Issue date: 

2021 
Date of publication: 

08.07.2021 