Consequences and limits of nonlocal strategies

By Richard Cleve, Peter Høyer, B. Toner, John Watrous. Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004., 2004

494 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/ee32d5b21498e94aa621154558288cb5f2f18ea9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Marius Junge
2. Carlos Palazuelos
3. John Watrous
4. David E. Roberson
5. Stephanie Wehner
6. B. Toner
7. Gilles Pisier
8. R. Myers

In Atomic and Molecular Physics, and Optics

1. Marius Junge
2. Carlos Palazuelos
3. John Watrous
4. Stephanie Wehner
5. B. Toner
6. Gilles Pisier

Citations in the corpus

• Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities (2005, background): “[6] have also remarked that Tsirelson’s constructions leads to an approach by semidefinite programming in the context of multiple interactive proof systems with entanglement.”
• Large Violation of Bell Inequalities with Low Entanglement (2010, background): “it enriches the theory of multipartite interactive proof systems ([7, 19, 18, 32, 24, 41, 39]), communication complexity (see the recent review [15]); Estimates for the dimension of the underlying Hilbert space ([11, 13, 57, 71, 73]), entangled games ([41, 40]), etc.”
• Monogamy of non-local quantum correlations (2006, background): “Formally, we define a 2-player game G OC as follows: Let n ≥ 3 be an odd integer, let π be uniform over the set { ( q 1 , q 2 ) ∈ Z n × Z n : q 1 = q 2 or q 1 + 1 ≡ q 2 (mod n ) and let V be defined by a , | ) [ a | + 6 Braunstein & Caves (1990) and Cleve et al. (2004) that ω c ( G OC ) = 1 − 1 / 2 n ”
• Quantum entanglement (2007, unknown): “Namely, basing on the earlier results concerning a link between the security of quantum communication protocols and violation of Bell’s inequalities (Scarani and Gisin, 2001a) and theory of nonlocal games (Cleve et al., 2004), Toner proved the CHSH inequality is monogamous (Toner, 2006).”
• Quantum Computational Complexity (2008, background): “Indeed, there exist two-prover interactive proof systems that are sound against classical provers, but can be cheated by entangled quantum provers [37].”
• Variations on a Theme: Graph Homomorphisms (2013, background): “Initially, only a special case of the homomorphism game, the graph coloring game, was introduced in [17, 9].”