We show a parallel repetition theorem for the entangled value ω*(G) of any two-player one-round game G where the questions (x, y) ∈ X × Y to Alice and Bob are drawn from a product distribution on X × Y. We show that for the k-fold product Gkof the game G (which represents the game G played in parallel k times independently) ω*(Gk) = (1 - (1 - ω*(G))3)Ω(k/Iog(|A|·|B|)where A and B represent the sets from which the answers of Alice and Bob are drawn. The arguments we use are information theoretic and are broadly on similar lines as that of Raz [1] and Holenstein [2] for classical games. The additional quantum ingredients we need, to deal with entangled games, are inspired by the work of Jain, Radhakrishnan, and Sen [3], where quantum information theoretic arguments were used to achieve message compression in quantum communication protocols.
We show a parallel repetition theorem for the entangled value ω*(G) of any two-player one-round game G where the questions (x, y) ∈ X × Y to Alice and Bob are drawn from a product distribution on X × Y. We show that for the k-fold product Gkof the game G (which represents the game G played in parallel k times independently) ω*(Gk) = (1 - (1 - ω*(G))3)Ω(k/Iog(|A|·|B|)where A and B represent the sets from which the answers of Alice and Bob are drawn. The arguments we use are information theoretic and are broadly on similar lines as that of Raz [1] and Holenstein [2] for classical games. The additional quantum ingredients we need, to deal with entangled games, are inspired by the work of Jain, Radhakrishnan, and Sen [3], where quantum information theoretic arguments were used to achieve message compression in quantum communication protocols.
We present two parallel repetition theorems for the entangled value of multi-player, one-round free games (games where the inputs come from a product distribution). Our first theorem shows that for a k-player free game G with entangled value val∗(G)=1−ε, the n-fold repetition of G has entangled value val∗(G⊗n) at most (1−ε3/2)Ω(n/sk4), where s is the answer length of any player. In contrast, the best known parallel repetition theorem for the classical value of two-player free games is val(G⊗n)≤(1−ε2)Ω(n/s), due to Barak, et al. (RANDOM 2009). This suggests the possibility of a separation between the behavior of entangled and classical free games under parallel repetition. Our second theorem handles the broader class of free games G where the players can output (possibly entangled) quantum states. For such games, the repeated entangled value is upper bounded by (1−ε2)Ω(n/sk2). We also show that the dependence of the exponent on k is necessary: we exhibit a k-player free game G and n≥1 such that val∗(G⊗n)≥val∗(G)n/k. Our analysis exploits the novel connection between communication protocols and quantum parallel repetition, first explored by Chailloux and Scarpa (ICALP 2014). We demonstrate that better communication protocols yield better parallel repetition theorems: our first theorem crucially uses a quantum search protocol by Aaronson and Ambainis, which gives a quadratic speed-up for distributed search problems. Finally, our results apply to a broader class of games than were previously considered before; in particular, we obtain the first parallel repetition theorem for entangled games involving more than two players, and for games involving quantum outputs.
We present a strong parallel repetition theorem for the entangled value of multi-player, one-round free games (games where the inputs come from a product distribution). Our result is the first parallel repetition theorem for entangled games involving more than two players. Furthermore, our theorem applies to games where the players are allowed to output (possibly entangled) quantum states as answers. More specifically, let G be a k-player free game, with entangled value val∗(G)=1−ε. We show that the entangled value of the n-fold repetition of G, val∗(G⊗n), is at most (1−ε)Ω(n/k2). In the traditional setting of k=2 players, our parallel repetition theorem is optimal in terms of its dependence on ε and n. For an arbitrary number of players, our result is nearly optimal: for all k, we exhibit a k-player free game G and n>1 such that val∗(G⊗n)≥val∗(G)n/k. Hence, exponent of the repeated game value cannot be improved beyond Ω(n/k). Our parallel repetition theorem improves on the prior results of [Jain, et al. 2014] and [Chailloux, Scarpa 2014] in a number of ways: (1) our theorem applies to a larger class of games (arbitrary number of players, quantum outputs); (2) we demonstrate that strong parallel repetition holds for the entangled value of free games: i.e., the base of the repeated game value is 1−ε, rather than 1−ε2; and (3) there is no dependence of the repeated game value on the input and output alphabets of G. In contrast, it is known that the repeated game value of classical free games must depend on the output size. Thus our results demonstrate a seperation between the behavior of entangled games and classical games.
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 Q1−(1−ε)Ω(ζ6k/log∣Z∣)1(fk)=Ω(k(ζ5⋅Qε+12ζ1(f)−loglog(1/ζ))), where Qε1(f) represents the one-way entanglement-assisted quantum communication complexity of f with worst-case error ε and fk 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,X×Y,A×B,V) where q is a distribution on X×Y anchored on any one side with anchoring probability ζ, then ω∗(Gk)=(1−(1−ω∗(G))5)Ω(log(∣A∣⋅∣B∣)ζ2k) 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.
We prove a direct product theorem for the one-way entanglement-assisted 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 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 the quantum communication complexity of a general relation - direct sum theorems were previously known for one-way 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 two-player non-local 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 one-way 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(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, 𝒳×𝒴, 𝒜×ℬ, 𝖵) 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.
We study the behavior of the entangled value of two-player one-round projection games under parallel repetition. We show that for any projection game G of entangled value 1-eps < 1, the value of the k-fold repetition of G goes to zero as O((1-eps^c)^k), for some universal constant c\geq 1. Previously parallel repetition with an exponential decay in k was only known for the case of XOR and unique games. To prove the theorem we extend an analytical framework recently introduced by Dinur and Steurer for the study of the classical value of projection games under parallel repetition. Our proof, as theirs, relies on the introduction of a simple relaxation of the entangled value that is perfectly multiplicative. The main technical component of the proof consists in showing that the relaxed value remains tightly connected to the entangled value, thereby establishing the parallel repetition theorem. More generally, we obtain results on the behavior of the entangled value under products of arbitrary (not necessarily identical) projection games. Relating our relaxed value to the entangled value is done by giving an algorithm for converting a relaxed variant of quantum strategies that we call "vector quantum strategy" to a quantum strategy. The algorithm is considerably simpler in case the bipartite distribution of questions in the game has good expansion properties. When this is not the case, rounding relies on a quantum analogue of Holenstein's correlated sampling lemma which may be of independent interest. Our "quantum correlated sampling lemma" generalizes results of van Dam and Hayden on universal embezzlement.
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 k ≥ 1, we show that [EQUATION] where Q1e(f) represents the one-way entanglement-assisted quantum communication complexity of f with worst-case error e and fk 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 one-way 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 two-player non-local games, under product distributions due to Jain, Pereszlenyi and Yao [24], and under anchored distributions due to Bavarian, Vidick and Yuen [4], as well as message compression for quantum protocols due to Jain, Radhakrishnan and Sen [29]. 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 [EQUATION] which has an anchored distribution q close to p, such that a protocol that fails with probability at most e for [EQUATION] under q can be used to give a protocol that fails with probability at most e + ζ 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 constant anchoring probability, then [EQUATION] where ω* (G) represents the entangled value of the game G. This is a generalization of the result of [4], 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.