# Calculating the quantum and classical value of a two-player XOR game¶

In this tutorial, we will cover the concept of an *XOR game*. We will also
showcase how the `toqito`

software package can be used to calculate the
classical and quantum value of a given XOR game.

For readers who are already familiar with XOR games and who simply want to see
how to use `toqito`

to study these objects, they are welcome to consult the
documentation page, and more specifically the function xor_game_value.

Further information beyond the scope of this tutorial on the notion of XOR games along with the method of computing their quantum value may be found in [tCSUU08].

## Two-player XOR games¶

A two-player XOR game is a nonlocal game in which the winning condition is predicated on an XOR function. For more information on the more general class of nonlocal games along with how one defines classical and quantum strategies for these games, please refer to the example:

Note

It is *not* known how to directly compute the quantum value of an arbitrary
nonlocal game. For the subset of XOR games, it turns out that it is
possible to directly calculate the quantum value by solving a semidefinite
program. The `toqito`

package obtains the quantum value of an XOR game
in this manner.

The rest of this tutorial is concerned with analyzing specific XOR games.

## The CHSH game¶

The *CHSH game* is a two-player XOR game with the following probability
distribution and question and answer sets.

where

Alice and Bob win the CHSH game if and only if the following equation is satisfied

Recall that \(\oplus\) refers to the XOR operation.

For each question scenario, the following table provides what the winning condition must be equal to for each question tuple to induce a winning outcome.

\(x\) | \(y\) | \(a \oplus b\) |
---|---|---|

\(0\) | \(0\) | \(0\) |

\(0\) | \(1\) | \(0\) |

\(1\) | \(0\) | \(0\) |

\(1\) | \(1\) | \(1\) |

In order to specify an XOR game in `toqito`

, we will define two matrices:

`prob_mat`

: A matrix whose \((x, y)^{th}\) entry corresponds to the probability that Alice receives question \(x\) and Bob receives question \(y\).`pred_mat`

: A matrix whose \((x, y)^{th}\) entry corresponds to the winning choice of \(a\) and \(b\) when Alice receives \(x\) and Bob receives \(y\) from the referee.

For the CHSH game, the prob_mat and pred_mat variables are defined as follows.

```
>>> import numpy as np
>>> prob_mat = np.array([[1/4, 1/4],
>>> [1/4, 1/4]])
>>> pred_mat = np.array([[0, 0],
>>> [0, 1]])
```

That is, the `prob_mat`

matrix encapsulates that each question pair
\(\{(0,0), (0, 1), (1, 0), (1, 1)\}\) is equally likely.

The `pred_mat`

matrix indicates what the winning outcome of Alice and Bob
should be. For instance, `pred_mat[0][0] = 0`

describes the scenario where
Alice and Bob both receive \(0\) as input. As we want to satisfy the
winning condition \(x \land y = a \oplus b\), we must have that \(a
\oplus b = 0\) to satisfy the case when both \(x\) and \(y\) are equal
to zero. A similar logic can be followed to populate the remaining entries of
the `pred_mat`

variable.

We will use both of the `prob_mat`

and `pred_mat`

variables in the
coming subsections to make use of the `toqito`

package to compute both the
classical and quantum value of the CHSH game.

### A classical strategy for the CHSH game¶

We can begin by asking; is it possible for Alice and Bob to win for every single question pair they receive with certainty? If Alice and Bob use a classical strategy, the answer to this question is “no”. To see why, consider the following equations:

In the above equation, \(a_x\) is Alice’s answer in the event that she receives question \(x\) from the referee for \(x \in \Sigma_A\). Similarly, \(b_y\) is Bob’s answer when Bob receives question \(y\) from the referee for \(y \in \Sigma_B\). These equations express the winning conditions that Alice and Bob must satisfy in order to perfectly win the CHSH game. That is, if it’s possible to satisfy all of these equations simultaneously, it’s not possible for them to lose.

One could perform a brute-force check to see that there is no possible way for Alice and Bob to simultaneously satisfy all four equations. The best they can do is satisfy three out of the four equations

They can achieve this if they either have answers \(a_0 = b_0 = a_1 = b_1 = 0\) or \(a_0 = b_0 = a_1 = b_1 = 1\).

Since it is not possible to satisfy all four equations, but it is possible to satisfy three out of the four equations, the classical value of the CHSH game is \(3/4\), or stated in an equivalent way

We can verify this by making use of `toqito`

to compute the classical
value of the CHSH game.

```
>>> from toqito.nonlocal_games.xor_game import XORGame
>>> chsh = XORGame(prob_mat, pred_mat)
>>> chsh.classical_value()
0.75
```

### A quantum strategy for the CHSH game¶

What is very intriguing about the CHSH game is that it is an example of a
nonlocal game where the players can do *strictly better* if they make use of a
quantum strategy instead of a classical one. The quantum strategy that allows
the players to do strictly better is composed of the following shared state and
sets of measurements.

State: The players prepare and share the state:

\[\begin{equation} | \psi \rangle = \frac{1}{\sqrt{2}} \left(| 00 \rangle + | 11 \rangle \right). \end{equation}\]Measurements: The players measure with respect to the following basis

\[\begin{split}\begin{equation} \begin{aligned} | \phi_0 \rangle &= \cos(\theta)|0 \rangle + \sin(\theta)|1 \rangle, \\ | \phi_1 \rangle &= -\sin(\theta)|0 \rangle + \cos(\theta)|1 \rangle, \end{aligned} \end{equation}\end{split}\]

such that

- If \(x = 0\) Alice sets \(\theta = 0\). Otherwise, if \(x = 1\), Alice sets \(\theta = \pi/4\).
- If \(y = 0\) Bob sets \(\theta = \pi/8\). Otherwise, if \(y = 1\), Bob sets \(\theta = -\pi/8\).

We can now analyze how well this particular quantum strategy performs by analyzing what occurs in each of the four possible scenarios. For brevity, we will just analyze the first case, but analyzing the remaining cases follows a similar analysis.

- Case: \(x = 0, y = 0\):

In this case, Alice and Bob win if \(a = b = 0\) or if \(a = b = 1\). Alice receives question \(x\) and selects her measurements constructed from the basis as specified in the strategy.

where

In a similar way, since Bob receives question \(y = 0\), he selects his measurements from the basis

where the measurement operators themselves are defined as

Using these measurements, we can calculate the probability that Alice and Bob win on the inputs \(x = 0\) and \(y = 0\) as

Calculating the above equation and normalizing by a factor of \(1/4\), we obtain the value of \(\cos^2(\pi/8)\). Calculating the remaining three cases of \((x = 0, y = 1), (x = 1, y = 0)\), and \((x = 1, y = 1)\) follow a similar analysis.

We can see that using this quantum strategy the players win the CHSH game with a probability of \(\cos^2(\pi/8) \approx 0.85355\), which is quite a bit better than the best classical strategy yielding a probability of \(3/4\) to win. As it turns out, the winning probability \(\cos^2(\pi/8)\) using a quantum strategy is optimal, which we can represent as \(\omega^*(G_{CHSH}) = \cos^2(\pi/8)\).

We can calculate the quantum value of the CHSH game using `toqito`

as
follows:

```
>>> chsh.quantum_value()
0.8535533885683664
```

For reference, the complete code to calculate both the classical and quantum values of the CHSH game is provided below.

```
>>> import numpy as np
>>> from toqito.nonlocal_games.xor_game import XORGame
>>> prob_mat = np.array([[1/4, 1/4],
>>> [1/4, 1/4]])
>>> pred_mat = np.array([[0, 0],
>>> [0, 1]])
>>> chsh = XORGame(prob_mat, pred_mat)
>>> chsh.classical_value()
0.75
>>> chsh.quantum_value()
0.8535533885683664
```

## The odd cycle game¶

The *odd cycle game* is another two-player XOR game with the following question and answer sets

where \(\pi\) is the uniform probability distribution over the question set.

As an example, we can specify the odd cycle game for \(n=5\) and calculate the classical and quantum values of this game.

```
>>> import numpy as np
>>> from toqito.nonlocal_games.xor_game import XORGame
>>>
>>> # Define the probability matrix.
>>> prob_mat = np.array([
>>> [0.1, 0.1, 0, 0, 0],
>>> [0, 0.1, 0.1, 0, 0],
>>> [0, 0, 0.1, 0.1, 0],
>>> [0, 0, 0, 0.1, 0.1],
>>> [0.1, 0, 0, 0, 0.1]])
>>>
>>> # Define the predicate matrix.
>>> pred_mat = np.array([
>>> [0, 1, 0, 0, 0],
>>> [0, 0, 1, 0, 0],
>>> [0, 0, 0, 1, 0],
>>> [0, 0, 0, 0, 1],
>>> [1, 0, 0, 0, 0]])
>>>
>>> # Compute the classical and quantum values.
>>> odd_cycle = XORGame(prob_mat, pred_mat)
>>> odd_cycle.classical_value()
0.9
>>> odd_cycle.quantum_value()
0.9755282544736033
```

Note that the odd cycle game is another example of an XOR game where the players are able to win with a strictly higher probability if they adopt a quantum strategy. For a general XOR game, Alice and Bob may perform equally well whether they adopt either a quantum or classical strategy. It holds that the quantum value for any XOR game is a natural upper bound on the classical value. That is, for an XOR game, \(G\), it holds that

for every XOR game \(G\).

## References¶

[tCSUU08] | Cleve, Richard, Slofstra, William, Unger, Falk, and Upadhyay, Sarvagya “Perfect parallel repetition theorem for quantum XOR proof systems” Computational Complexity 17.2 (2008): 282-299. https://arxiv.org/abs/quant-ph/0608146 |