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⊆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.
In a two-player game, two cooperating but non communicating players, Alice and Bob, receive inputs taken from a probability distribution. Each of them produces an output and they win the game if they satisfy some predicate on their inputs/outputs. The entangled value ω∗(G) of a game G is the maximum probability that Alice and Bob can win the game if they are allowed to share an entangled state prior to receiving their inputs. The n-fold parallel repetition Gn of G consists of n instances of G where Alice and Bob receive all the inputs at the same time and must produce all the outputs at the same time. They win Gn if they win each instance of G. Recently, there has been a series of works showing parallel repetition with exponential decay for projection games [DSV13], games on the uniform distribution [CS14] and for free games, i.e. games on a product distribution [JPY13]. This article is meant to be a follow up of [CS14], where we improve and simplify several parts of our previous paper. Our main result is that for any free game G with value ω∗(G)=1−ε, we have ω∗(Gn)≤(1−ε2)Ω(log(l)n) where l is the size of the output set of the game. This result improves on both the results in [JPY13] and [CS14]. The framework we use can also be extended to free projection games. We show that for a free projection game G with value ω∗(G)=1−ε, we have ω∗(Gn)≤(1−ε)Ω(n).