Notes - Quantum Information HT24, The CHSH game

Created: February 06, 2024

Give the 4 rules of the CHSH game, write down the payoff table and give an expression for the expected payoff $\omega$.

This is a game involving three players: Alice, Bob and a referee.

  1. Alice and Bob are allowed to meet before the start of the game and to decide their strategy, but after the game starts, they are not allowed to communicate with each other.
  2. Charlie sends one bit $a$ to Alice, and one bit $b$ to Bob, both chosen at random.
  3. Alice answers with one bit $x$ and Bob answers with one bit $y$.
  4. If $a \wedge b = x \oplus y$, then they earn a point, otherwise they lose a point (“$a$lice and $b$ob give $x$ plus $y$”)

The payoff table is

| Across: (x, y)
Down: (a, b) | (0,0) | (0,1) | (1,0) | (1,1) | | —————————— | —– | —– | —– | —– | | (0,0) | +1 | -1 | -1 | +1 | | (0,1) | +1 | -1 | -1 | +1 | | (1,0) | +1 | -1 | -1 | + | | (1,1) | -1 | +1 | +1 | -1 | Let $\omega(x, y \mid a,b)$ denote the payoff for Alice and Bob choosing bits $x$ and $y$ given “question bits” $a$ and $b$. Then this can more compactly be written

\[\omega(x, y \mid a, b) = (-1)^{x + y + ab}\]

Then let $\omega$ denote the expected payoff.

\[\begin{aligned} \omega &= \sum_{a, b} \sum_{x,y} \omega(x, y \mid a, b) p(x, y \mid a, b) p(a, b) \\\\ &= \frac 1 4 \sum_{a, b} \sum_{x, y} (-1)^{x + y + ab} p(x, y \mid a, b) \end{aligned}\]

Suppose Alice, Bob and Charlie are playing the CHSH game with classical resources. For background, the rules of the CHSH game are:

  1. Alice and Bob are allowed to meet before the start of the game and to decide their strategy, but after the game starts, they are not allowed to communicate with each other.
  2. Charlie sends one bit $a$ to Alice, and one bit $b$ to Bob, both chosen at random.
  3. Alice answers with one bit $x$ and Bob answers with one bit $y$.
  4. If $x \oplus y = a \wedge b$, then they earn a point, otherwise they lose a point. (Here $\oplus$ represents XOR)

Since we are in the classical world, the strategies can’t do any better than a deterministic strategy. What does it mean for a strategy to be deterministic mathematically?

The outcomes are functions of their questions, i.e.

\[\begin{aligned} &x = f(a) \\\\ &y = g(b) \end{aligned}\]

for some functions $f, g$.

Suppose Alice, Bob and Charlie are playing the CHSH game with classical resources. For background, the rules of the CHSH game are:

  1. Alice and Bob are allowed to meet before the start of the game and to decide their strategy, but after the game starts, they are not allowed to communicate with each other.
  2. Charlie sends one bit $a$ to Alice, and one bit $b$ to Bob, both chosen at random.
  3. Alice answers with one bit $x$ and Bob answers with one bit $y$.
  4. If $x \oplus y = a \wedge b$, then they earn a point, otherwise they lose a point. (Here $\oplus$ represents XOR)

Suppose the strategies are deterministic, and so $x = f(a)$ and $y = g(b)$ for some function $f$ and $g$. Given that the expected payoff is given by

\[\omega = \frac 1 4 \sum_{a, b} \sum_{x, y} (-1)^{x + y + ab} p(x, y \mid a, b)\]

Quickly show that the maximum expected payoff is bounded above by $1/2$.

We have

\[p(x, y \mid a, b) = \begin{cases} 1 &\text{if } x = f(a), y = g(b) \\\\ 0 &\text{otherwise} \end{cases}\]

(this is just the condition that the strategies are deterministic). Then

\[\begin{aligned} \omega &= \frac 1 4 \sum_{a, b} \sum_{x, y} (-1)^{x + y + ab} p(x, y \mid a, b) \\\\ &= \frac 1 4 \sum_{a, b} (-1)^{f(a) + g(b) + ab} \\\\ &= \frac 1 4 \Big((-1)^{f(0)}\big((-1)^{g(0)} + (-1)^{g(1)})\big) + (-1)^{f(1)} \big((-1)^{g(0)} - (-1)^{g(1)}\big)\Big) \\\\ &= \begin{cases} \frac 1 4 (-1)^{f(0)}\big((-1)^{g(0)} + (-1)^{g(1)})\big) &\text{if }g(0) = g(1) \\\\ \frac 1 4 (-1)^{f(1)} \big((-1)^{g(0)} - (-1)^{g(1)}\big) &\text{if }g(0) \ne g(1) \end{cases} \end{aligned}\]

and each of these terms are at most $\frac 1 2$.

Suppose Alice, Bob and Charlie are playing the CHSH game with classical resources. For background, the rules of the CHSH game are:

  1. Alice and Bob are allowed to meet before the start of the game and to decide their strategy, but after the game starts, they are not allowed to communicate with each other.
  2. Charlie sends one bit $a$ to Alice, and one bit $b$ to Bob, both chosen at random.
  3. Alice answers with one bit $x$ and Bob answers with one bit $y$.
  4. If $x \oplus y = a \wedge b$, then they earn a point, otherwise they lose a point. (Here $\oplus$ represents XOR)

Briefly describe how the quantum strategy for the CHSH game works (the answer contains specifics, but don’t worry about these).
  • Before the game, Alice and Bob prepare two qubits so that together they are in the Bell state $ \vert \Phi^+ \rangle$. Then Alice and Bob seperate and each keep one qubit.
  • If Alice recieves bit $a$, then Alice measures her qubit on the basis $\{ \vert 0, \theta _ a\rangle, \vert 1, \theta _ a\rangle\}$ where $\theta _ 0 = 0$ and $\theta _ 1 = \frac \pi 2$. The outcome is her answer $x$.
  • If Bob recieves bit $b$, Bob measures his qubit on the basis $\{ \vert 0, \tau _ b\rangle, \vert 1, \tau _ b\rangle\}$ with $\tau _ 0 = \frac \pi 4$ and $\tau _ 1 = -\frac \pi 4$. The outcome is his answer $y$.

Suppose Alice, Bob and Charlie are playing the CHSH game with classical resources. For background, the rules of the CHSH game are:

  1. Alice and Bob are allowed to meet before the start of the game and to decide their strategy, but after the game starts, they are not allowed to communicate with each other.
  2. Charlie sends one bit $a$ to Alice, and one bit $b$ to Bob, both chosen at random.
  3. Alice answers with one bit $x$ and Bob answers with one bit $y$.
  4. If $x \oplus y = a \wedge b$, then they earn a point, otherwise they lose a point. (Here $\oplus$ represents XOR)

What is the maximum expected payoff $\omega _ C$ for a general classical strategy, and what is the maximum expected payoff $\omega _ Q$ for a general quantum strategy?
  • Classical: $\omega _ C = \frac 1 2$
  • Quantum: $\omega _ Q = \frac{1}{\sqrt{2} }$

What does it mean formally for the outcomes of measurements on a system $S$ to be pre-determined, and what is a hidden variable in this context?

There exists a parameter $\lambda _ S$ and a function $f _ S$ such that

\[f_S(m, \lambda_S) = x\]

for all measurements $m$ and outcomes $x$.

Here $\lambda _ S$ is a hidden variable.

Suppose Alice, Bob and Charlie are playing the CHSH game with classical resources. For background, the rules of the CHSH game are:

  1. Alice and Bob are allowed to meet before the start of the game and to decide their strategy, but after the game starts, they are not allowed to communicate with each other.
  2. Charlie sends one bit $a$ to Alice, and one bit $b$ to Bob, both chosen at random.
  3. Alice answers with one bit $x$ and Bob answers with one bit $y$.
  4. If $x \oplus y = a \wedge b$, then they earn a point, otherwise they lose a point. (Here $\oplus$ represents XOR)

Given that the maximum expected payoff $\omega _ C$ for a general classical strategy is $\frac 1 2$ and the maximum expected payoff $\omega _ Q$ for a general quantum strategy is $\frac{1}{\sqrt{2}\,}$, briefly describe how this shows quantum theory is incompatible with local realism, and that since real-world experiments have been done that play the CHSH game, the real world also does not have local realism.

Since in any world where we have local realism Alice and Bob’s outcomes must be predetermined, there is no better way of playing the CHSH game than a classical strategy. Since better strategies exist within quantum theory, these two things must be incompatible.

What is the assumption of locality?

When two spatially separated systems are measured at the same time, the choice of measurement on one system does not affect the outcome of the measurement performed on the other system.

What is the assumption of determinism?

The outcomes of measurements are predetermined.

What is the view of “local realism”?
\[\text{local realism} = \text{locality} + \text{determinism}\]

The quantum strategy for the CHSH game involves Alice measuring in $\{ \vert 0, \theta _ a\rangle, \vert 1, \theta _ a \rangle\}$ and Bob measuring in $\{ \vert 0, \tau _ b\rangle, \vert 1, \tau _ b\rangle\}$. What is $\theta _ 0, \theta _ 1, \tau _ 0, \tau _ 1$?
\[0, \frac \pi 2, \frac \pi 4, -\frac \pi 4\]

Proofs



Related posts