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 1973948469
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 show that any language in nondeterministic time @math , where the number of iterated exponentials is an arbitrary function @math , can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness @math and soundness @math , where the number of iterated exponentials is @math and @math is a universal constant. The result was previously known for @math and @math ; we obtain it for any time-constructible function @math . The result is based on a compression technique for interactive proof systems with entangled provers that significantly simplifies and strengthens a protocol compression result of Ji (STOC'17). As a separate consequence of this technique we obtain a different proof of Slofstra's recent result (unpublished) on the uncomputability of the entangled value of multiprover games. Finally, we show that even minor improvements to our compression result would yield remarkable consequences in computational complexity theory and the foundations of quantum mechanics: first, it would imply that the class MIP* contains all computable languages; second, it would provide a negative resolution to a multipartite version of Tsirelson's problem on the relation between the commuting operator and tensor product models for quantum correlations. We show a parallel repetition theorem for the entangled value @math of any two-player one-round game @math where the questions @math to Alice and Bob are drawn from a product distribution on @math . We show that for the @math -fold product @math of the game @math (which represents the game @math played in parallel @math times independently), @math , where @math and @math represent the sets from which the answers of Alice and Bob are drawn. This paper investigates various aspects of the nonlocal effects that can arise when entangled quantum information is shared between two parties. A natural framework for studying nonlocality is that of cooperative games with incomplete information, where two cooperating players may share entanglement. Here, nonlocality can be quantified in terms of the values of such games. We review some examples of non-locality and show that it can profoundly affect the soundness of two-prover interactive proof systems. We then establish limits on nonlocal behavior by upper-bounding the values of several of these games. These upper bounds can be regarded as generalizations of the so-called Tsirelson inequality. We also investigate the amount of entanglement required by optimal and nearly optimal quantum strategies.