Understanding the GHZ game

Question

I am trying to understand the basics of the GHZ nonlocal game in quantum information theory. I have searched for all the info i could find, thought i understood, but still face some basic misunderstandings of the game. I have divided my confusion up into 4 concrete questions.

For this example (and the background for my question) let us assume a GHZ game with three players Alice, Bob and Charlie. The rules of the game are described in details in this lecture note from John Watrous (see the second page for a detailed description). In my questions underneath i will not use anything specific to these lectures that requires others to have read the whole thing. All will be written in the general context of this typical example of a nonlocal game. I have only provided a link to share all relevant information as possible.

Question 1) How would a typical round in the game proceed like? More specifically how does a string bit 0 or 1 correspond to a question posed by a referee? Does it in fact correspond to the "true" value/answer of the question? Say the referee asks Alice "0" - this for me does not make any sense. How can "0" be a question? Does the referee ask a question where the true answer is "0", and if Alice answers with "0", the referee sees it as a valid answer? This seems so fundamental, but i simply can not wrap my head around it. Say we make up a dummy question: "Is grass green?". How would this question be represented by either a "0" or "1"? I understand that the answer can be represented by "0" or "1" simply as true or false.

Another possibility (seems more plausible to me): Is it rather that we only have two questions per round: question 0 and question 1 - and these two questions are the same two questions that by random gets chosen and distributed to the three players by the referee. So they may all receive the same question or at least two players are bound to get the same question (because there are two questions but three players). The players' answer is then 0 if they answer true/yes and 1 if they answer false/no. This understanding then does not explain what the true answer is - that is how does the referee validates whether the correct answer to question 0 is in fact yes (0) or no (1)?

Question 2) The winning condition is described in the table as:

$$ r s t \qquad \qquad a \oplus b \oplus c \\ ----------- \\ 000 \qquad \qquad \qquad 0 \\ 011 \qquad \qquad \qquad 1 \\ 101 \qquad \qquad \qquad 1 \\ 110 \qquad \qquad \qquad 1 $$

where r,s and t are the questions posed to Alice, Bob and Charlie respectively. I have never used mod 2 addition before, but i see that in this case it is simply a XOR gate (exclusive OR gate).

From what i understand this means the criteria for answering a question correct is:

$$a \oplus b \oplus c = r \lor s \lor t \qquad \qquad \qquad (eq. 1)$$

where the right-hand side is just a logical OR, and not and XOR. This does not make any sense to me. Why are we interested in having exclusive OR on the left, but regular OR on the right?

Question 3) Out of the 8 combinations for r,s,t: (000,110,011,101,100,001,010,111) only the first four in the list are used, but not the last four. When i calculate $a \oplus b \oplus c$ with a=r,b=s,c=t i get that the first four equal 0 and the last four equal 1. I see there is a symmetry. Is it correct then, that it is in fact arbitrary if we use the first four or the last four, as long as we are consistent with our choice of true/false (0/1)? I see that all textbooks, lecture notes, youtube videos and so on use the convention above - so i must be missing something?

Is the reason we do not include them just because {100,010,001} mean that at least two players answered correctly - but this is already included if at least one answered correctly {110,101,011}? And the last combination {111} then corresponds to all players getting the answers wrong.

My first understanding seems confusing but would explain that the probability of winning with a classical strategy is 75% (3 out of 4 cases is a win: 110,011,101 but not 000 since all answers were wrong) which is the correct probability. I am not sure my reasoning is correct though. My second understanding would provide a probability of 87.5% of winning with a classical strategy (7 out of 8 cases is a win). The players would thus only loose in the one case of 000/111 by symmetry it again does not matter if 0 is true or 1 is true and vice versa, one of them corresponds to all players getting all questions wrong.

Question 4) How does this criteria (winning condition) translate into words? That is, how does the referee validate the answers? So as i understand it we can split it up into two cases. The first where rst=000 and the other three of rst={110,011,101}. Case 1: If the three players all get question 0 then the only way they can win is if they all answer 0 of course. Therefore $0 \oplus 0 \oplus 0 = 0$ because we have odd parity of three zero's thus equals zero. That makes sense. Case 2: If the three players answer something where they do not all agree, but at least differ in one answer, then eq. 1 is fulfilled both when the left-hand side is 0 and 1 - that means it is a guaranteed win. This seems like an odd game, where you win no matter what - where did i go wrong? Do they win if just one player answers correct? When i calculate these cases i get all three $(1\oplus1\oplus0)$ and $(0\oplus1\oplus1)$ and $(1\oplus0\oplus1)$ to equal zero. This can quickly be seen because the 1's come in pairs of two, which has even parity and they can never equal 1. The 0's on the other hand always comes in odd parity, and thus the three terms all equal zero. This is NOT what the table from the linked lecture notes (or all other sources) tell me. Again, i can not see the logic behind this.

This might seem like the most basic thing in the world to some, and apparently since nobody explains it in more detail it should be trivial. Maybe i am overthinking this, but i do not understand the GHZ game at all. Hope someone can clarify. Thanks!

Answer 1

1)

The "question" posed by the referee is a three-bit string taken from the set $\{000, 011, 101, 110\}$. The task of Alice, Bob and Charlie is then to give the correct "global" answer for any given input. At every turn, each of them can answer with "$0$" or with "$1$".

Correct here means that it must satisfy a specific set of winning conditions. More specifically, if the referee says $000$, then A&B&C win if and only if the binary sum of their answers is $0$. For example, the answer $000$ wins, and so does the answer $110$. On the other hand, the answer $010$ is wrong and makes them lose.

When on the other hand the "question" (that is, again, the given bitstring) is one of the others, say $110$, then the winning conditions are inverted, so that for example $000$ loses and $010$ wins.

So again, the round proceeds as follows:

1. Referee chooses one of the four possible words $000$, $011$, $101$, $110$.
2. The first bit of the chosen word is given to Alice, the second to Bob, and the third to Charlie.
3. Alice, Bob and Charlie each answer with either $0$ or $1$ (the choice of $0$ or $1$ here is just conventional, other references use $+1$ and $-1$, or just two different generic symbols).
4. Alice, Bob and Charlie win or lose depending on whether they gave the correct answer or not, according to a specific "truth table".

2)

Why use that specific rule to decide whether they win or lose the game? Simply because it works! In other words, it turns out (and this is exactly what is being explained in the text) that with that particular choice of winning condition one can show easily that any classical strategy cannot do better than a specific amount, while quantum mechanics allows to do better.

The arbitrariness of the rule is not important here, what it shows is that there exist circumstances in which QM allows to win a game better than what is possible with only classical rules.

3)

I do not fully understand what you write, but the reason only those particular four words are given by the referee is, again, because it results in a game that displays the characteristics we are looking for. You can change the game by allowing the referee to give addition question words, and then see if you get the same classical/quantum performances.

4)

Maybe it would help to completely change the notation?

Let us say that the referee has a bunch of apples ($0$) and bananas ($1$). At every round it distributes them among Alice Bob and Charlie, but not in a random fashion: he either gives apples to everyone, or an apple to someone and bananas to the others.

Alice Bob and Charlie answer by each giving back, say, a mango ($0$) or a papaya ($1$). The winning conditions are as follows:

1. If everyone got an apple, then they must give back either zero or two papayas.
2. If someone (that is, two people) got a banana, then they must give back either one or three papayas.

This is of course totally equivalent to the version with $0$s and $1$s. The only difference is that when using $0$s and $1$s (or $+1$ and $-1$) it can be easier to express some of the winning rules, using logical operators and such.