We show that for any @math there is an XOR game @math with @math inputs for one player and @math inputs for the other player such that @math ebits are required for any strategy achieving bias that is at least a multiplicative factor @math from optimal. This gives an exponential improvement in both the number of inputs or outputs and the noise tolerance of any previously-known self-test for highly entangled states. Up to the exponent @math the scaling of our bound with @math is tight: for any XOR game there is an @math -optimal strategy using @math ebits, irrespective of the number of questions in the game.
The general study of optimal strategies in XOR games was initiated by Tsirelson, who shows @cite_18 that for any XOR game with @math and @math inputs per party there is an optimal strategy that uses a maximally entangled state of dimension at most @math , where @math is the largest integer that satisfies @math and @math . To establish this Tsirelson first proves that to each player's input in the game can be associated a real @math -dimensional unit vector, @math for Alice and @math for Bob, such that the correlations @math achieve the optimal quantum bias in the game. Tsirelson then uses a clever construction, based on a representation of the Clifford algebra, to show that these vectors can be mapped to observables and a maximally entangled state in dimension @math that achieve precisely the same correlations. Slofstra @cite_24 shows that Tsirelson's bound is tight for a slight variant of the @math game.
@cite_24 @cite_18
2089619338 2232305496 2409246750 2609741941
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 introduce quantum XOR games, a model of two-player, one-round games that extends the model of XOR games by allowing the referee’s questions to the players to be quantum states. We give examples showing that quantum XOR games exhibit a wide range of behaviors that are known not to exist for standard XOR games, such as cases in which the use of entanglement leads to an arbitrarily large advantage over the use of no entanglement. By invoking two deep extensions of Grothendieck’s inequality, we present an efficient algorithm that gives a constant-factor approximation to the best performance that players can obtain in a given game, both in the case that they have no shared entanglement and that they share unlimited entanglement. As a byproduct of the algorithm, we prove some additional interesting properties of quantum XOR games, such as the fact that sharing a maximally entangled state of arbitrary dimension gives only a small advantage over having no entanglement at all. Tsirelson's problem asks whether the commuting operator model for two-party quantum correlations is equivalent to the tensor-product model. We give a negative answer to this question by showing that there are non-local games which have perfect commuting-operator strategies, but do not have perfect tensor-product strategies. The weak Tsirelson problem, which is known to be equivalent to Connes embedding problem, remains open. The examples we construct are instances of (binary) linear system games. For such games, previous results state that the existence of perfect strategies is controlled by the solution group of the linear system. Our main result is that every finitely-presented group embeds in some solution group. As an additional consequence, we show that the problem of determining whether a linear system game has a perfect commuting-operator strategy is undecidable. We construct a linear system non-local game which can be played perfectly using a limit of finite-dimensional quantum strategies, but which cannot be played perfectly on any finite-dimensional Hilbert space, or even with any tensor-product strategy. In particular, this shows that the set of (tensor-product) quantum correlations is not closed. The constructed non-local game provides another counterexample to the "middle" Tsirelson problem, with a shorter proof than our previous paper (though at the loss of the universal embedding theorem). We also show that it is undecidable to determine if a linear system game can be played perfectly with a finite-dimensional strategy, or a limit of finite-dimensional quantum strategies.