HW4 - Problem 3

Problem 3: Implausible consequences from beating the CHSH game

In class I stated the optimal win rate for the CHSH game with quantum information is approximately 85%. We won’t prove that upper bound, but let’s see why we don’t believe that it’s possible to get to 100%.

Suppose there existed super-quantum non-local frogs that allowed us to win the CHSH game. That is, if Alice and Bob each took one of these frogs to their respective planets, when Alice gives a bit \(x\) to her frog, it responds with a bit \(a\) and when Bob gives a bit \(y\) to his frog, it responds with a bit \(b\) such that

\(xy = (a + b)(\text{mod }2)\)

would always be true.

  1. Enlist the help of these frogs to design a strategy for Alice and Bob to win the CHSH game 100% of the time.

Now imagine that Alice and Bob each had \(n\) of these frogs, Alice has an \(n\)-bit string \(X\), and Bob has a different \(n\)-bit string \(Y\). Instead of playing the CHSH game, they want to compute the inner product of their bit strings. That is, they need to calculate

\(X\cdot Y = (x_1\cdot y_1 + \cdots + x_n\cdot y_n) \mod2\)

where \(x_i\), \(y_i\) are the \(i\)-th bits of \(A\) and \(B\) respectively.

  1. Let’s try an example to make sure you have the right idea of the inner product. Verify that the inner product between \(X=11001\) and \(Y=11110\) is 0.
  2. Outline a strategy where Alice and Bob use as many frogs as needed and Alice sends \(n\) bits to Bob, and Bob sends \(n\) bits to Alice such that both of them can learn the answer to \(X \cdot Y\) afterwards.
  3. Outline a strategy where Alice and Bob use as many frogs as needed and Alice sends 1 bit to Bob, and Bob sends 1 bit to Alice such that both of them can learn the answer to \(X \cdot Y\).
  4. (Challenge) Outline a strategy where Alice and Bob use as many frogs as needed and only Alice sends one bit to Bob, such that both of them can learn the answer to \(X \cdot Y\).

We won’t prove it here, but it is possible to show that any Boolean function \(f\) that takes as input \(2n\) bits, can be expressed as

\(f(x_1, x_2, \ldots, x_n, y_1, y_2, \ldots, y_n) = \sum_{j=1}^N A_j(X)\cdot B_j(Y) \text{ (mod 2)}.\)

That is, we can compute the function by doing some set of operations on the first \(n\) bits (the \(A_j\)’s), another set of operations on the second \(n\) bits (the \(B_j\)’s), then taking the inner product of the results.

Suppose that we are able to compute all the \(A_j\) and \(B_j\) functions

  1. (Challenge) Show that we can use any number of frogs and one bit of communication from Alice to Bob so that both of them know the answer to \(f\).

The consequence of the last two problems makes it incredibly hard to believe that the CHSH game could be beaten with a probability of 100%, since this would imply that any function that depends on \(2n\) bits of input can be computed at long distances by communicating only a single bit of information!