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.
These results characterize the dimension of exactly optimal strategies in any XOR game. To the best of our knowledge, even if one considers arbitrary two-player games the @math game remains the most efficient (in terms of total number of inputs and outputs per party) test for @math -qubit maximally entangled states. In particular, although there is strong indication that certain Bell inequalities, such as the @math inequality, have a quantum bound that may only be achieved in the limit of infinite dimensions @cite_9 , no such result has been rigorously proven. There are examples of two-player one round games which provably require infinite-dimensional entanglement in order to be played optimally @cite_14 @cite_3 , but these require the exchange of quantum messages between the referee and the players. Recently Slofstra @cite_10 showed the existence of a game for which a value @math can be attained using infinite-dimensional commuting-operator strategies, but it is not known if there exists a tensor product strategy achieving this value; in particular there is no optimal entangled state'' for this game.
@cite_9 @cite_14 @cite_10 @cite_3
2073801892 2163684974 2409246750 2232305496
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. Bell inequality violations correspond to behavior of entangled quantum systems that cannot be simulated classically. We give two new two-player games with Bell inequality violations that are stronger, fully explicit, and arguably simpler than earlier work.The first game is based on the Hidden Matching problem of quantum communication complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with probability 1 by a quantum strategy using a maximally entangled state with local dimension n (e.g., log n EPR-pairs), while we show that the winning probability of any classical strategy differs from 1 2 by at most O(log(n) sqrt(n)).The second game is based on the integrality gap for Unique Games by Khot and Vishnoi and the quantum rounding procedure of Kempe, Regev, and Toner. Here n-dimensional entanglement allows to win the game with probability 1 (log n)^2, while the best winning probability without entanglement is 1 n. This near-linear ratio ( Bell inequality violation'') is near-optimal, both in terms of the local dimension of the entangled state, and in terms of the number of possible outputs of the two players. 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. We consider two-player games played for an infinite number of rounds, with ω-regular winning conditions. The games may be concurrent, in that the players choose their moves simultaneously and independently, and probabilistic, in that the moves determine a probability distribution for the successor state. We introduce quantitative game µ-calculus, and we show that the maximal probability of winning such games can be expressed as the fixpoint formulas in this calculus. We develop the arguments both for deterministic and for probabilistic concurrent games; as a special case, we solve probabilistic turn-based games with ω-regular winning conditions, which was also open. We also characterize the optimality, and the memory requirements, of the winning strategies. In particular, we show that while memoryless strategies suffice for winning games with safety and reachability conditions, Buchi conditions require the use of strategies with infinite memory. The existence of optimal strategies, as opposed to e-optimal, is only guaranteed in games with safety winning conditions. 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. 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. By introducing a quantitative degree of commutativity'' in terms of the angle between spin observables we present two tight quantitative trade-off relations in the case of two qubits. First, for entangled states, between the degree of commutativity of local observables and the maximal amount of violation of the Bell inequality: if both local angles increase from zero to @math (i.e., the degree of local commutativity decreases), the maximum violation of the Bell inequality increases. Secondly, a converse trade-off relation holds for separable states: if both local angles approach @math the maximal value obtainable for the correlations in the Bell inequality decreases and thus the non-violation increases. As expected, the extremes of these relations are found in the case of anticommuting local observables where, respectively, the bounds of @math and @math hold for the expectation value of the Bell operator. The trade-off relations show that noncommmutativity gives a more than classical result'' for entangled states, whereas a less than classical result'' is obtained for separable states. The experimental relevance of the trade-off relation for separable states is that it provides an experimental test for two qubit entanglement. Its advantages are twofold: in comparison to violations of Bell inequalities it is a stronger criterion and in comparison to entanglement witnesses it needs to make less strong assumptions about the observables implemented in the experiment. A quantum algorithm for an oracle problem can be understood as a quantum strategy for a player in a two-player zero-sum game in which the other player is constrained to play classically. I formalize this correspondence and give examples of games (and hence oracle problems) for which the quantum player can do better than would be possible classically. The most remarkable example is the Bernstein-Vazirani quantum search algorithm which I show creates no entanglement at any timestep. 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 study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is @math -complete to decide whether the classical value of a non-local game is 1 or @math . Furthermore, as long as @math is small enough, this result does not depend on the gap @math . In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap @math decreases. In this paper, we show that this also holds for the commuting-operator value of a game. Specifically, in the language of multi-prover interactive proofs, we show that the power of @math (proofs with two provers, one round, completeness probability @math , soundness probability @math , and commuting-operator strategies) can increase without bound as the gap @math gets arbitrarily small. Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class @math - @math of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap @math gets arbitrarily small. While we do not know any computable time upper bound on the class @math , a result of the first author and Vidick shows that for @math and @math , the class @math , with constant communication from the provers, is contained in @math . We give a lower bound of @math (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis. The I sub 3322 inequality is the simplest bipartite two-outcome Bell inequality beyond the Clauser-Horne-Shimony-Holt (CHSH) inequality, consisting of three two-outcome measurements per party. In the case of the CHSH inequality the maximal quantum violation can already be attained with local two-dimensional quantum systems; however, there is no such evidence for the I sub 3322 inequality. In this paper a family of measurement operators and states is given which enables us to attain the maximum quantum value in an infinite-dimensional Hilbert space. Further, it is conjectured that our construction is optimal in the sense that measuring finite-dimensional quantum systems is not enough to achieve the true quantum maximum. We also describe an efficient iterative algorithm for computing quantum maximum of an arbitrary two-outcome Bell inequality in any given Hilbert space dimension. This algorithm played a key role in obtaining our results for the I sub 3322 inequality, and we also applied it to improve on our previous results concerning the maximum quantum violation of several bipartite two-outcome Bell inequalities with up to five settings per party. We propose a simple yet rich model to extend strategic games to the quantum setting, in which we define quantum Nash and correlated equilibria and study the relations between classical and quantum equilibria. Unlike all previous work that focused on qualitative questions on specific games of very small sizes, we quantitatively address the following fundamental question for general games of growing sizes: How much "advantage" can playing quantum strategies provide, if any? Two measures of the advantage are studied. 1. Since game mainly is about each player trying to maximize individual payoff, a natural measure is the increase of payoff by playing quantum strategies. We consider natural mappings between classical and quantum states, and study how well those mappings preserve equilibrium properties. Among other results, we exhibit a correlated equilibrium p whose quantum superposition counterpart [EQUATION] is far from being a quantum correlated equilibrium; actually a player can increase her payoff from almost 0 to almost 1 in a [0, 1]-normalized game. We achieve this by a tensor product construction on carefully designed base cases. The result can also be interpreted as in Meyer's comparison [47]: In a state no classical player can gain, one player using quantum computers has an huge advantage than continuing to play classically. 2. Another measure is the hardness of generating correlated equilibria, for which we propose to study correlation complexity, a new complexity measure for correlation generation. We show that there are n-bit correlated equilibria which can be generated by only one EPR pair followed by local operation (without communication), but need at least log2(n) classical shared random bits plus communication. The randomized lower bound can be improved to n, the best possible, assuming (even a much weaker version of) a recent conjecture in linear algebra. We believe that the correlation complexity, as a complexity-theoretical counterpart of the celebrated Bell's inequality, has independent interest in both physics and computational complexity theory and deserves more explorations. 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. This paper investigates a zero-sum game played on a weighted connected graph @math between two players, the tree player and the edge player. At each play, the tree player chooses a spanning tree @math and the edge player chooses an edge @math . The payoff to the edge player is @math , defined as follows: If @math lies in the tree @math then @math ; if @math does not lie in the tree then @math , where @math is the weight of edge @math and @math is the weight of the unique cycle formed when edge @math is added to the tree @math . The main result is that the value of the game on any @math -vertex graph is bounded above by @math . It is conjectured that the value of the game is @math . The game arises in connection with the @math -server problem on a road network; i.e., a metric space that can be represented as a multigraph @math in which each edge @math represents a road of length @math . It is shown that, if the value of the game on @math is @math , then there is a randomized strategy that achieves a competitive ratio of @math against any oblivious adversary. Thus, on any @math -vertex road network, there is a randomized algorithm for the @math -server problem that is @math competitive against oblivious adversaries. At the heart of the analysis of the game is an algorithm that provides an approximate solution for the simple network design problem. Specifically, for any @math -vertex weighted, connected multigraph, the algorithm constructs a spanning tree @math such that the average, over all edges @math , of @math is less than or equal to @math . This result has potential application to the design of communication networks. It also improves substantially known estimates concerning the existence of a sparse basis for the cycle space of a graph. We consider repeated games in which the player, instead of observing the action chosen by the opponent in each game round, receives a feedback generated by the combined choice of the two players. We study Hannan-consistent players for these games, that is, randomized playing strategies whose per-round regret vanishes with probability one as the number n of game rounds goes to infinity. We prove a general lower bound of Ω(n-1 3) for the convergence rate of the regret, and exhibit a specific strategy that attains this rate for any game for which a Hannan-consistent player exists. 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 analyze and solve a game in which a player chooses which of several Markov chains to advance, with the object of minimizing the expected time (or cost) for one of the chains to reach a target state. The solution entails computing (in polynomial time) a function @math ---a variety of "Gittins index"---on the states of the individual chains, the minimization of which produces an optimal strategy. It turns out that @math is a useful cousin of the expected hitting time of a Markov chain but is defined, for example, even for random walks on infinite graphs. We derive the basic properties of @math and consider its values in some natural situations. We analyse a randomized pursuit-evasion game played by two players on a graph, a hunter and a rabbit. Let @math be any connected, undirected graph with @math nodes. The game is played in rounds and in each round both the hunter and the rabbit are located at a node of the graph. Between rounds both the hunter and the rabbit can stay at the current node or move to another node. The hunter is assumed to be restricted to the graph @math : in every round, the hunter can move using at most one edge. For the rabbit we investigate two models: in one model the rabbit is restricted to the same graph as the hunter, and in the other model the rabbit is unrestricted, i.e., it can jump to an arbitrary node in every round.We say that the rabbit is caught as soon as hunter and rabbit are located at the same node in a round. The goal of the hunter is to catch the rabbit in as few rounds as possible, whereas the rabbit aims to maximize the number of rounds until it is caught. Given a randomized hunter strategy for @math , the escape length for that strategy is the worst case expected number of rounds it takes the hunter to catch the rabbit, where the worst case is with regard to all (possibly randomized) rabbit strategies. Our main result is a hunter strategy for general graphs with an escape length of only @math against restricted as well as unrestricted rabbits. This bound is close to optimal since @math is a trivial lower bound on the escape length in both models. Furthermore, we prove that our upper bound is optimal up to constant factors against unrestricted rabbits. Two players are about to play a discounted infinitely repeated bimatrix game. Each player knows his own payoff matrix and chooses a strategy which is a best response to some private beliefs over strategies chosen by his opponent. If both players' beliefs contain a grain of truth (each assigns some positive probability to the strategy chosen by the opponent), then they will eventually (a) accurately predict the future play of the game and (b) play a Nash equilibrium of the repeated game. An immediate corollary is that in playing a Harsanyi-Nash equilibrium of a discounted repeated game of incomplete information about opponents' payoffs, the players will eventually play an equilibrium of the real game as if they had complete information. Consider the following probabilistic one-player game: The board is a graph with @math vertices, which initially contains no edges. In each step, a new edge is drawn uniformly at random from all nonedges and is presented to the player, henceforth called Painter. Painter must assign one of @math available colors to each edge immediately, where @math is a fixed integer. The game is over as soon as a monochromatic copy of some fixed graph @math has been created, and Painter's goal is to “survive” for as many steps as possible before this happens. We present a new technique for deriving upper bounds on the threshold of this game, i.e., on the typical number of steps Painter will survive with an optimal strategy. More specifically, we consider a deterministic two-player variant of the game where the edges are chosen not randomly, but by a second player Builder. However, Builder has to adhere to the restriction that, for some real number @math , the ratio of edges to vertices in all subgraphs of the evolving board ne...