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.
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.
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 nonlocality 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. 1.
This paper investigates the powers and limitations of quantum entanglement in the context of cooperative games of incomplete information. We give several examples of such nonlocal games where strategies that make use of entanglement outperform all possible classical strategies. One implication of these examples is that entanglement can profoundly affect the soundness property of two-prover interactive proof systems. We then establish limits on the probability with which strategies making use of entanglement can win restricted types of nonlocal games. These upper bounds may be regarded as generalizations of Tsirelson-type inequalities, which place bounds on the extent to which quantum information can allow for the violation of Bell inequalities. We also investigate the amount of entanglement required by optimal and nearly optimal quantum strategies for some games.
Quantum mechanics is nonlocal, meaning it cannot be described by any classical local hidden variable model. In this thesis we study two aspects of quantum nonlocality. Part I addresses the question of what classical resources are required to simulate nonlocal quantum correlations. We start by constructing new local models for noisy entangled quantum states. These constructions exploit the connection between nonlocality and Grothendieck's inequality, first noticed by Tsirelson. Next, we consider local models augmented by a limited amount of classical communication. After generalizing Bell inequalities to this setting, we show that (i) one bit of communication is sufficient to simulate the correlations of projective measurements on a maximally entangled state of two qubits, and (ii) five bits of communication are sufficient to simulate the joint correlation of two-outcome measurements on any bipartite quantum state. The latter result can be interpreted as a stronger (constrained) version of Grothendieck's inequality. In part II, we investigate the monogamy of nonlocal correlations. In a setting where three parties, A, B, and C, share an entangled quantum state of arbitrary dimension, we: (i) bound the trade-off between AB's and AC's violation of the CHSH inequality, obtaining an intriguing generalization of Tsirelson's bound, and (ii) demonstrate that forcing B and C to be classically correlated prevents A and B from violating certain Bell inequalities. We study not only correlations that arise within quantum theory, but also arbitrary correlations that do not allow signaling between separate groups of parties. These results are based on new techniques for obtaining Tsirelson bounds, or bounds on the quantum value of a Bell inequality, and have applications to interactive proof systems and cryptography.
A central question in quantum information theory and computational complexity is how powerful nonlocal strategies are in cooperative games with imperfect information, such as multi-prover interactive proof systems. This paper develops a new method for proving limits of nonlocal strategies that make use of prior entanglement among players (or, provers, in the terminology of multi-prover interactive proofs). Instead of proving the limits for usual isolated provers who initially share entanglement, this paper proves the limits for "commuting-operator provers", who share private space, but can apply only such operators that are commutative with any operator applied by other provers. Obviously, these commuting-operator provers are at least as powerful as usual isolated but prior-entangled provers, and thus, limits in the model with commuting-operator provers immediately give limits in the usual model with prior-entangled provers. Using this method, we obtain an n-party generalization of the Tsirelson bound for the Clauser-Horne-Shimony-Holt inequality, for every n. Our bounds are tight in the sense that, in every n-party case, the equality is achievable by a usual nonlocal strategy with prior entanglement. We also apply our method to a three-prover one-round binary interactive proof system for NEXP. Combined with the technique developed by Kempe, Kobayashi, Matsumoto, Toner and Vidick to analyze the soundness of the proof system, it is proved to be NP-hard to distinguish whether the entangled value of a three-prover one-round binary-answer game is equal to one or at most 1-1/p(n) for some polynomial p, where n is the number of questions. This is in contrast to the two-prover one-round binary-answer case, where the corresponding problem is efficiently decidable. Alternatively, NEXP has a three-prover one-round binary interactive proof system with perfect completeness and soundness 1 middot 2-poly.
Nonlocal games provide a unified framework for studying the distinction between classical, quantum, and more general no-signaling correlations. In this work, we develop this perspective by connecting the Bell-locality framework to several complementary mathematical representations of nonlocal games and quantum strategies. We begin with local hidden-variable models, the CHSH inequality, and the role of Bell nonlocality as a device-independent witness of entanglement, and then introduce nonlocal games through the standard predicate/verifier formalism.
We next examine a set of representative examples, including XOR games, the GHZ game, graph-based coloring games, the Mermin-Peres magic square game, and Hardy's paradox as a related logical manifestation of nonlocality. Building on this foundation, we compare four closely related representation frameworks: conditional-probability and correlation descriptions, Bell-functional formulations, entangled-value optimization, and the quantum-operator approach together with the Navascues-Pironio-Acin (NPA) hierarchy. These viewpoints are then instantiated for the CHSH, magic square, and GHZ games, showing how each representation emphasizes a different aspect of the same underlying task.
Taken together, these examples show that nonlocal games can be studied simultaneously as geometric objects in correlation space, optimization problems over entangled resources, and operator-theoretic constructions. This multi-representation viewpoint clarifies the relation between Bell inequality violations, perfect quantum strategies, pseudo-telepathy, and semidefinite relaxations of quantum correlations.
Quantum entanglement, and the resulting peculiar non-classical correlations are one of the most counter-intuitive aspects of quantum mechanics.
The formalism of interactive games from computational complexity theory provides a useful framework in which to understand the power of entanglement. In an interactive game, a verifier interacts with a number of infinitely powerful provers who are allowed to share quantum entanglement but otherwise can't communicate. The ability of the verifier to extract useful information from the provers, whom he does not trust, provides an interesting measure of the ability of the provers to coordinate using their shared entanglement. Two particular interactive games we'll look at are Magic Square and 3SAT.
The Magic Square game is the iconic example of a game where two classical provers cannot perfectly coordinate their strategies using shared randomness, but quantum provers with shared entanglement can win with probability 1. We show that by adding an extra prover, we disallow perfect cheating. For 3SAT with three provers we also show that perfect cheating is not possible.
We then generalize the results for Magic Square and 3SAT by looking at non-commuting provers, a superset of entangled provers (communication is allowed, but operators applied by different provers must commute). Using this method, we obtain a generalized Tsirelson inequality that we apply to the Magic Square. Hence, we are able to give provably optimal strategies for the general Magic Square with n players. We also recover a similar result for 3SAT as with entangled provers, and we improve on it by showing that the gap is inverse exponential in the input size.
The no-signaling principle, which forbids faster than light communication, is a fundamental constraint on the non-local correlations resulting from quantum entanglement. However, no-signaling allows distributions that are more general than those arising from quantum mechanics. In particular, using a specific unit of general non-local correlation (the Popescu-Rohlich box), we show that there are classes that are equal to NEXP classically, but collapse to AM once such correlations are allowed. We also show that MIP where the verifier only looks at the XOR of the answers collapses to PSPACE. For the second approach, we show that by writing general non-local correlations as linear constraints, MIP is included in EXP under such correlations (vs NEXP classically).
We can extend these results to entangled quantum provers, by formulating an artificial MIP-like class built on a promise problem, that classically is equal to NEXP, but that also collapses to AM when quantum correlations are present.