Nonlocal Games

Bell's theorem becomes far easier to reason about — and to turn into protocols — once it is recast as a game between cooperating players and a referee. The CHSH inequality is the prototype, so we restate it in game form and pin down the best a classical team can do.

The CHSH game

A referee picks two bits $x,y\in\{0,1\}$ , each uniformly and independently, and sends $x$ to Alice and $y$ to Bob. The players are separated and cannot communicate during the round. Alice replies with a bit $a$ , Bob with a bit $b$ . They win the round if and only if

a \oplus b = x \wedge y,

that is, the XOR of their answers must equal the AND of their inputs. The players know the rule and may agree on any strategy — including shared randomness or shared entanglement — before the inputs are handed out.

Translating the inequality into a payoff

Map bits to signs via $a\mapsto(-1)^a$ . A short calculation shows the win probability and the CHSH correlator $S$ are affinely related:

p_{\text{win}} = \frac{1}{2} + \frac{S}{8},

where $S = E(0,0)+E(0,1)+E(1,0)-E(1,1)$ and $E(x,y)=\langle(-1)^{a\oplus b}\rangle$ . The classical bound $S\le 2$ becomes a winning-probability ceiling of $\tfrac12 + \tfrac28 = \tfrac34$ , and the quantum value $S=2\sqrt2$ becomes $\tfrac12 + \tfrac{2\sqrt2}{8} = \cos^2(\pi/8)\approx 0.854$ .

The classical value is exactly 3/4

By convexity, the best classical strategy is deterministic: any randomised strategy is a mixture of deterministic ones and cannot beat the best of them. A deterministic strategy is just two functions, $a=a(x)$ and $b=b(y)$ . The win condition over all four equally likely inputs reads

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.

Adding all four equations modulo $2$ gives $0=1$ — a contradiction. So no strategy can satisfy all four; at most three of the four conditions hold. Since each input is equally likely,

p_{\text{win}}^{\,\text{classical}} = \frac{3}{4}.

A concrete optimum: both players always answer $0$ . Then $a\oplus b=0$ , which matches $x\wedge y$ for the three inputs other than $(1,1)$ .

Why the game framing pays off

Phrasing nonlocality as a game makes the resource explicit: a strategy is good or bad by a single number, the win probability, and "beating $3/4$ " is an operational signature of entanglement that needs no assumptions about the devices' internals. This is the language in which device-independent protocols are stated for the rest of the module.

Try it

Compute the optimal classical winning probability of the CHSH game by brute-forcing all $16$ deterministic strategies and scoring each over the four equally likely input pairs. You should recover exactly $3/4$ .

Run your code to see the quantum state.