Nonlocal Games

A nonlocal game asks separated players to coordinate answers to questions they cannot exchange during a round. Its classical value is the best score achievable with shared randomness and local responses. Shared entanglement can improve some scores, making the game a task-based formulation of Bell nonlocality.

Questions, answers and a verifier

The verifier samples questions $(x,y)$ from a specified distribution $\pi(x,y)$, sends one to each player, receives answers $(a,b)$ and awards a score $V(a,b,x,y)$. The success probability is

$$\omega=\sum_{x,y}\pi(x,y)\sum_{a,b}V(a,b,x,y)p(a,b\mid x,y).$$

The question distribution is part of the game. Changing it can change the classical value and the experiment’s statistical efficiency. Shared randomness coordinates a pre-agreed strategy; it does not allow the players to learn each other’s current question.

The CHSH game

Choose independent uniform question bits $x,y$ and require $a\oplus b=xy$. A deterministic classical strategy would have to satisfy

$$a_0\oplus b_0=0,\quad a_0\oplus b_1=0,\quad a_1\oplus b_0=0,\quad a_1\oplus b_1=1.$$

XOR of the left sides is zero because every answer occurs twice, while XOR of the right sides is one. At least one question pair must lose. Three can be won, so the optimal classical score is $3/4$; mixtures cannot improve it.

For sign outcomes $A=(-1)^a,B=(-1)^b$, the winning indicator is $[1+(-1)^{xy}AB]/2$. Averaging gives

$$\omega=\frac12+\frac18(E_{00}+E_{01}+E_{10}-E_{11}).$$

The CHSH quantum calculation therefore gives optimal score $\cos^2(\pi/8)=(2+\sqrt2)/4$. The players use locally measured entanglement; no question is transmitted between them during the round.

Why a game is useful experimentally

A score gives a direct statistic per trial and makes the permitted resources explicit. It also exposes postselection: a player must return a declared output even when a detector fails unless the rules include a justified abort mechanism. Declaring losses only after seeing the questions changes the game.

Winning above the classical value witnesses nonlocality subject to independent inputs and separated responses. It does not automatically certify a particular state, a secret key or a quantity of extractable randomness. Those require additional theorems and robustness bounds. Device-Independent Reasoning develops that distinction.

Exercise: biased questions

Suppose one CHSH question pair occurs with probability $\epsilon\le1/4$ and the other three share the remaining probability equally. What is the optimal deterministic classical score?

Solution

Every strategy loses at least one pair, and a strategy can be chosen to lose any designated single pair. It should lose the least likely one, yielding $1-\epsilon$. The uniform-input bound $3/4$ is inapplicable to this changed distribution. Input bias must be included in the null model rather than ignored in the data analysis.

References

• Cleve, Richard, Peter Høyer, Benjamin Toner, and John Watrous, “Consequences and limits of nonlocal strategies,” Proceedings of the 19th IEEE Conference on Computational Complexity, 236–249 (2004), arXiv:quant-ph/0404076.
• Clauser, John F., Michael A. Horne, Abner Shimony, and Richard A. Holt, “Proposed experiment to test local hidden-variable theories,” Physical Review Letters 23, 880–884 (1969), doi:10.1103/PhysRevLett.23.880.