We give an explicit family of XOR games with O(n)-bit questions requiring 2n ebits to play near-optimally. More generally, we introduce a new technique for proving lower bounds on the amount of entanglement required by an XOR game: we show that near-optimal strategies for an XOR game G correspond to approximate representations of a certain C*-algebra associated to G. Our results extend an earlier theorem of Tsirelson characterising the set of quantum strategies which implement extremal quantum correlations.
We give an explicit family of XOR games with O(n)-bit questions requiring 2n ebits to play near-optimally. More generally, we introduce a new technique for proving lower bounds on the amount of entanglement required by an XOR game: we show that near-optimal strategies for an XOR game G correspond to approximate representations of a certain C*-algebra associated to G. Our results extend an earlier theorem of Tsirelson characterising the set of quantum strategies which implement extremal quantum correlations.
We characterize the amount of entanglement that is sufficient to play any XOR game near-optimally. We show that for any XOR game G and \eps>0 there is an \eps-optimal strategy for G using \lceil \eps^{-1} \rceil ebits of entanglement, irrespective of the number of questions in the game. By considering the family of XOR games CHSH(n) introduced by Slofstra (Jour. Math. Phys. 2011), we show that this bound is nearly tight: for any \eps>0 there is an n=\Theta(\eps^{-1/5}) such that \Omega(\eps^{-1/5}) ebits are required for any strategy achieving bias that is at least a multiplicative factor (1-\eps) from optimal in CHSH(n).
We study optimal and nearly-optimal quantum strategies for non-local XOR games. First, we prove the following general result: for every non-local XOR game, there exists a set of relations with the properties: (1) a quantum strategy is optimal for the game if and only if it satisfies the relations, and (2) a quantum strategy is nearly optimal for the game if and only if it approximately satisfies the relations. Next, we focus attention on a specific infinite family of XOR games: the CHSH(n) games. This family generalizes the well-known CHSH game. We describe the general form of CHSH(n) optimal strategies. Then, we adapt the concept of intertwining operator from representation theory and use that to characterize nearly-optimal CHSH(n) strategies.
We establish approximate rigidity results for several well-known families of nonlocal games. In particular, we show that near-perfect quantum strategies for boolean constraint system (BCS) games are approximate representations of the corresponding BCS algebra. Likewise, for the class of XOR nonlocal games, we show that near-optimal quantum strategies are approximate representations of the corresponding ∗-algebra associated with optimal quantum values for the game. In both cases, the approximate representations are with respect to the normalized Hilbert-Schmidt norm and independent of the Hilbert space or quantum state employed in the strategy. We also show that approximate representation of the BCS (resp. XOR-algebra) yields measurement operators for near-perfect (resp. near-optimal) quantum strategies where the players employ a maximally entangled state in the game. As a corollary, every near-perfect BCS (resp. near-optimal XOR) quantum strategy is close to a near-perfect (resp. near-optimal) quantum strategy using a maximally entangled state. Lastly, we establish that every synchronous algebra is ∗-isomorphic to a certain BCS algebra called the SynchBCS algebra. This allows us to apply our BCS rigidity results to the class of synchronous games as well.
We prove an explicit upper bound on the amount of entanglement required by any strategy in a two-player cooperative game with classical questions and quantum answers. Specifically, we show that every strategy for a game with n-bit questions and n-qubit answers can be implemented exactly by players who share an entangled state of no more than 5n qubits--a bound which is optimal to within a factor of 5/2. Previously, no upper bound at all was known on the amount of entanglement required even to approximate such a strategy. It follows that the problem of computing the value of these games is in NP, whereas previously this problem was not known to be computable.
We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical biases, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, Pérez-García et al. proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form Σiαi|i〉... |i〉 for arbitrary amplitudes αi. Our results have the following surprising consequence: classical three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.
How much entanglement does near-optimal play of a two-player nonlocal game require? We give an explicit binary linear system game, with 1687 equations in 1993 variables and at most three variables in each equation, whose quantum value is one, and in which every strategy that wins with probability 1−ε needs entanglement entropy ε−1+o(1), hence local dimension exp(ε−1+o(1)). The same bound holds for the entanglement of formation of mixed strategies, and a strategy on a maximally entangled state of local dimension exp(Cε−1log(1/ε)) suffices, so the exponent is sharp. For explicit two-player games of quantum value one, the best previous lower bound was polynomial in 1/ε. The game comes from a finitely generated, elementary amenable group: a lamplighter whose lamps are Pauli pairs indexed by finite sets of points on the three rays on which Houghton's group acts. Exponentially many of these pairs share one central involution, yet the relation that any two of them commute can be derived from a fixed finite set of relations in a number of steps only quasi-polynomial in the number of points. Two tools may be of independent use. The first counts qubits from approximate Pauli relations measured in an arbitrary state, with the errors of different pairs adding in squares. The second identifies, in both directions and at the natural precision ε, the near-optimal strategies of a linear system game with approximate representations of its solution group measured in the players' actual state, so that no power of ε is lost by passing to a flat state. The same tools give sharp rates for two earlier examples: the CHSH(n) games need Θ(min(n,1/ε)) ebits, and the linear system game of Slofstra and Vidick needs local dimension Θ(ε−1/2).