期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-31
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation f ⊆ X × Y × Z. For any ε, ζ > 0 and any k ≥ 1, we show that Q 1 1−(1−ε)Ω(ζ6k/ log |Z|) (f k ) = Ω k ζ 5 · Q 1 ε 12ζ (f) − log log(1/ζ) , where Q1 ε (f) represents the one-way entanglement-assisted quantum communication complexity of f with worst-case error ε 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´enyi and Yao [JPY14], and under anchored distributions due to Bavarian, Vidick and Yuen [BVY17], as well as message-compression for quantum protocols due to Jain, Radhakrishnan and Sen [JRS05]. 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 X ×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 ˜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 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, X × Y, A × B, V) where q is a distribution on X × Y anchored on any one side with anchoring probability ζ, then ω ∗ (G k ) = 1 − (1 − ω ∗ (G))5 Ω ζ 2k log(|A|·|B|) where ω ∗ (G) represents the entangled value of the game G. This is a generalization of the result of [BVY17], 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.
