# Nonlocal games¶

In this tutorial, we are going to cover the notion of a *nonlocal game*; a
mathematical framework that abstractly models a physical system. The simplest
instance of a nonlocal game involves two players, Alice and Bob, who are not
allowed to communicate with each other once the game has started and who play
cooperatively against an adversary referred to as the referee.

A primary challenge that arises when studying these games is to determine the maximum probability with which Alice and Bob are able to achieve a winning outcome.

This probability is highly dependent on the type of *strategy* that Alice and
Bob use in the game. A *classical strategy* is one in which Alice and Bob have
access to classical resources. The best that Alice and Bob can do using a
classical strategy is known as the *classical value* of the game. Similarly, a
*quantum strategy* is one in which Alice and Bob have access to quantum
resources. The best that Alice and Bob can do using a quantum strategy is known
as the *quantum value* of the game.

Calculating the classical value of a game is NP-hard as we need to perform a brute-force check to see which strategy yields the classical value of the game.

Using `toqito`

, we will be able to specify a nonlocal game and be able to
directly calculate the classical value and also place lower bounds on the
quantum value.

Further information beyond the scope of this tutorial on nonlocal games can be found in [tCHTW04]. Further information on the lower bound technique can be found in [tLD07].

## Two-player nonlocal games¶

A *two-player nonlocal game* consists of players that we give the names *Alice*
and *Bob*:

Alice and Bob are in separate locations and cannot communicate once the game
begins. Prior to the game however, Alice and Bob are free to communicate with
each other. In addition to the players, there is also another party in this
game that is referred to as the *referee*.

Alice and Bob want to play in a cooperative fashion against the referee.

Now that we have set the stage with respect to the actors and actresses we will encounter in this game, let us see how the game is actually played.

A nonlocal game unfolds in the following manner.

- The referee randomly generates questions denoted as \(x\) and \(y\). The referee sends the question \(x\) to Alice and the question \(y\) to Bob. The referee also keeps a copy of \(x\) and \(y\) for reference.
- Alice and Bob each receive their respective questions. They are then each expected to respond to their questions with answers that we denote as \(a\) and \(b\). Alice sends \(a\) to the referee, and Bob sends \(b\).
- When the referee receives \(a\) and \(b\) from Alice and Bob, the referee evaluates a particular function that is predicated on the questions \(x\) and \(y\) as well as the answers \(a\) and \(b\). The outcome of this function is either \(0\) or \(1\), where an outcome of \(0\) indicates a loss for Alice and Bob and an outcome of \(1\) indicates a win for Alice and Bob.

Alice and Bob’s goal in the above game is to get the function in Step-3 to
output a \(1\), or equivalently, to indicate a winning outcome. This type
of game is referred to as a *nonlocal game*.

## Classical and Quantum Strategies¶

Now that we have the framework for a nonlocal game, we can consider the
player’s *strategy*; how the players play the game given access to certain
resources. There are a number of strategies that the players can use, but for
simplicity, we will restrict our attention to two types of strategies.

*Classical strategies*: The players answer the questions in a deterministic manner.*Quantum strategies*: The players make use of quantum resources in the form of a shared quantum state and respective sets of measurements.

### Classical strategies¶

A *classical strategy* for a nonlocal game is one where the players
deterministically produce an output for every possible combination of inputs
they may receive in the game. The *classical value* of a nonlocal game is the
maximum probability achieved by the players over all classical strategies. For
a nonlocal game, \(G\), we use \(\omega(G)\) to represent the classical
value of \(G\).

One question you may have is whether a classical strategy can be improved by introducing randomness. If the players randomly select their answers, is it possible for them to do potentially better than if they had just played deterministically? As it happens, probabilistic classical strategies cannot perform any better than deterministic classical strategies.

There is therefore no loss in generality in restricting our analysis of classical strategies to deterministic ones and it is assumed that when we use the term classical strategy that we implicitly mean a classical strategy that is played deterministically.

### Quantum strategies¶

A *quantum strategy* for a nonlocal game is one where the players prepare a
quantum state prior to the start of the game along with respective sets of
measurements that they apply to their respective portions of the shared state
during the game based on the questions they receive to generate their answers.
The *quantum value* of a nonlocal game is the maximum probability achieved by
the players over all quantum strategies. For a nonlocal game, \(G\), we use
\(\omega^*(G)\) to represent the quantum value of \(G\).

Let us describe the high-level steps for how Alice and Bob play using a quantum strategy.

- Alice and Bob prepare a state \(\sigma \in \text{D}(\mathcal{U} \otimes \mathcal{V})\) prior to the start of the game. We use \(\textsf{U}\) and \(\textsf{V}\) to denote the respective registers of spaces \(\textsf{U}\) and \(\textsf{V}\).
- The referee sends question \(x \in \Sigma_A\) to Alice and \(y \in \Sigma_B\) to Bob.
- Alice and Bob perform a
*measurement*on their system. The outcome of this measurement yields their answers \(a \in \Gamma_A\) and \(b \in \Gamma_B\). Specifically, Alice and Bob have collections of measurements

such that the measurements satisfy

- The referee determines whether Alice and Bob win or lose, based on the questions \(x\) and \(y\) as well as the answers \(a\) and \(b\).

For certain games, the probability that the players obtain a winning outcome is higher if they use a quantum strategy as opposed to a classical one. This striking separation is one primary motivation to study nonlocal games, as it provides examples of tasks that benefit from the manipulation of quantum information.

## Calculating the classical value¶

(Coming soon)

## Calculating the quantum value¶

The ability to calculate the quantum value for an arbitrary nonlocal game is a highly non-trivial task. Indeed, the quantum value is only known in special cases for certain nonlocal games.

For an arbitrary nonlocal game, there exist approaches that place upper and lower bounds on the quantum value. The lower bound approach is calculated using the technique of semidefinite programming [tLD07]. While this method is efficient to carry out, it does not guarantee convergence to the quantum value (although in certain cases, it is attained).

The primary idea of this approach is to note that fixing the measurements on one system yields the optimal measurements of the other system via an SDP. The algorithm proceeds in an iterative manner between two SDPs. In the first SDP, we assume that Bob’s measurements are fixed, and Alice’s measurements are to be optimized over. In the second SDP, we take Alice’s optimized measurements from the first SDP and now optimize over Bob’s measurements. This method is repeated until the quantum value reaches a desired numerical precision.

For completeness, the first SDP where we fix Bob’s measurements and optimize over Alice’s measurements is given as SDP-1.

Similarly, the second SDP where we fix Alice’s measurements and optimize over Bob’s measurements is given as SDP-2.

## Lower bounding the quantum value in toqito¶

The `toqito`

software implements both of these optimization problems using
the `cvxpy`

library. We see-saw between the two SDPs until the value we
obtain reaches a specific precision threshold.

As we are not guaranteed to obtain the true quantum value of a given nonlocal
game as this approach can get stuck in a local minimum, the `toqito`

function allows the user to specify an `iters`

argument that runs the
see-saw approach a number of times and then returns the highest of the values
obtained.

### Example: Lower bounding the quantum value of the CHSH game¶

Let us consider calculating the lower bound on the quantum value of the CHSH game.

Note

As the CHSH game is a subtype of nonlocal game referred to as an XOR game, we do not necessarily need to resort to this lower bound technique as there exists a specific SDP formulation that one can use to directly compute the quantum value of an XOR game. More information on how one defines the CHSH game as well as this method to directly calculate the quantum value of an XOR game is provided in “Calculating the Quantum and Classical Value of a Two-Player XOR Game”

We will use the CHSH game here as an illustrative example as we already know what the optimal quantum value should be.

The first step is to use `numpy`

to encode a matrix that encapsulates the
probabilities with which the questions are asked to Alice and Bob. As defined in
the CHSH game, each of the four pairs
\(\{(0, 0), (0, 1), (1, 0), (1, 1)\}\) are all equally likely. We encode
this in the matrix as follows.

```
>>> # Creating the probability matrix.
>>> import numpy as np
>>> prob_mat = np.array([[1 / 4, 1 / 4], [1 / 4, 1 / 4]])
```

Next, we want to loop through all possible combinations of question and answer pairs and populate the :math:(a, b, x, y)^{th}` entry of that matrix with a \(1\) in the event that the winning condition is satisfied. Otherwise, if the winning condition is not satisfied for that particular choice of \(a, b, x,\) and \(y\), we place a \(0\) at that position.

The following code performs this operation and places the appropriate entries
in this matrix into the `pred_mat`

variable.

```
>>> # Creating the predicate matrix.
>>> import numpy as np
>>> num_alice_inputs, num_alice_outputs = 2, 2
>>> num_bob_inputs, num_bob_outputs = 2, 2
>>>
>>> pred_mat = np.zeros(
>>> (num_alice_outputs, num_bob_outputs, num_alice_inputs, num_bob_inputs)
>>> )
>>>
>>> for a_alice in range(num_alice_outputs):
>>> for b_bob in range(num_bob_outputs):
>>> for x_alice in range(num_alice_inputs):
>>> for y_bob in range(num_bob_inputs):
>>> if a_alice ^ b_bob == x_alice * y_bob:
>>> pred_mat[a_alice, b_bob, x_alice, y_bob] = 1
>>> print(pred_mat)
[[[[1. 1.]
[1. 0.]]
[[0. 0.]
[0. 1.]]]
[[[0. 0.]
[0. 1.]]
[[1. 1.]
[1. 0.]]]]
```

Now that we have both `prob_mat`

and `pred_mat`

defined, we can
use `toqito`

to determine the lower bound on the quantum value.

```
>>> from toqito.nonlocal_games.nonlocal_game import NonlocalGame
>>> chsh = NonlocalGame(prob_mat, pred_mat)
>>> chsh.quantum_value_lower_bound()
0.8535539268303678
```

In this case, we can see that the quantum value of the CHSH game is in fact attained as \(\cos^2(\pi/8) \approx 0.85355\).

## The FFL game¶

The *FFL (Fortnow, Feige, Lovasz) game* is a nonlocal game specified as
follows.

where

\[\begin{equation} \Sigma_A = \{0, 1\}, \quad \Sigma_B = \{0, 1\}, \quad \Gamma_A = \{0,1\}, \quad \text{and} \quad \Gamma_B = \{0, 1\}. \end{equation}\]

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

\[\begin{equation} a \lor x = b \lor y. \end{equation}\]

It is well-known that both the classical and quantum value of this nonlocal
game is \(2/3\) [tCHTW04]. We can verify this fact using `toqito`

.
The following example encodes the FFL game. We then calculate the classical
value and calculate lower bounds on the quantum value of the FFL game.

```
>>> import numpy as np
>>> from toqito.nonlocal_games.nonlocal_game import NonlocalGame
>>>
>>> # Specify the number of inputs, and number of outputs.
>>> num_alice_in, num_alice_out = 2, 2
>>> num_bob_in, num_bob_out = 2, 2
>>>
>>> # Define the probability matrix of the FFL game.
>>> prob_mat = np.array([[1/3, 1/3], [1/3, 0]])
>>>
>>>
>>> # Define the predicate matrix of the FFL game.
>>> pred_mat = np.zeros((num_alice_out, num_bob_out, num_alice_in, num_bob_in))
>>> for a_alice in range(num_alice_out):
>>> for b_bob in range(num_bob_out):
>>> for x_alice in range(num_alice_in):
>>> for y_bob in range(num_bob_in):
>>> if (a_alice or x_alice) != (b_bob or y_bob):
>>> pred_mat[a_alice, b_bob, x_alice, y_bob] = 1
>>> # Define the FFL game object.
>>> ffl = NonlocalGame(prob_mat, pred_mat)
>>> ffl.classical_value()
0.6666666666666666
>>> ffl.quantum_value_lower_bound()
0.6666857549041076
```

In this case, we obtained the correct quantum value of \(2/3\), however, the lower bound technique is not guaranteed to converge to the true quantum value in general.

## Parallel repetitions of nonlocal games¶

(Coming soon).

## References¶

[tCHTW04] | (1, 2) Cleve, Richard, Hoyer, Peter, Toner, Benjamin, and Watrous, John
“Consequences and limits of nonlocal strategies”
Computational Complexity 2004. Proceedings. 19th IEEE Annual Conference.
https://arxiv.org/abs/quant-ph/0404076 |

[tLD07] | (1, 2) Liang, Yeong-Cherng, and Andrew C. Doherty.
“Bounds on quantum correlations in Bell-inequality experiments.”
Physical Review A 75.4 (2007): 042103.
https://arxiv.org/abs/quant-ph/0608128 |