`nonlocal_games.xor_game`¶

Two-player XOR game.

Module Contents¶

Classes¶

XORGame

Create two-player XOR game object.

class nonlocal_games.xor_game.XORGame(prob_mat, pred_mat, reps=1, tol=None)¶

Create two-player XOR game object.

Calculates the optimal probability that Alice and Bob win the game if they are allowed to determine a join strategy beforehand, but not allowed to communicate during the game itself.

The quantum value of an XOR game can be solved via the semidefinite program from [2].

This function is adapted from the QETLAB package.

A tutorial is available in the documentation. Go to Calculating the quantum and classical value of a two-player XOR game.

Examples

The CHSH game

The CHSH game is a two-player nonlocal game with the following probability distribution and question and answer sets [3].

\[\begin{equation} \begin{aligned} \pi(x,y) = \frac{1}{4}, \qquad (x,y) \in \Sigma_A \times \Sigma_B, \qquad \text{and} \qquad (a, b) \in \Gamma_A \times \Gamma_B, \end{aligned} \end{equation}\]

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 CHSH game if and only if the following equation is satisfied

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

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

The optimal quantum value of CHSH is \(\cos(\pi/8)^2 \approx 0.8536\) where the optimal classical value is \(3/4\).

In order to specify the CHSH game, we can define the probability matrix and predicate matrix for the CHSH game as numpy arrays 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]])

In toqito, we can calculate both the quantum and classical value of the CHSH game as follows.

>>> import numpy as np
>>> from toqito.nonlocal_games.xor_game import XORGame
>>> chsh = XORGame(prob_mat, pred_mat)
>>> '%.2f' % chsh.quantum_value()
'0.85'
>>>
>>> chsh.classical_value()
0.75

Note

You do not need to use ‘%.2f’ % when you use this function.

We use this to format our output such that doctest compares the calculated output to the expected output upto two decimal points only. The accuracy of the solvers can calculate the float output to a certain amount of precision such that the value deviates after a few digits of accuracy.

The odd cycle game

The odd cycle game is another XOR game [2]. For this game, we can specify the probability and predicate matrices as follows.

>>> 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],
... ]
... )
>>> 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],
... ]
... )

In toqito, we can calculate both the quantum and classical value of the odd cycle game as follows.

>>> import numpy as np
>>> from toqito.nonlocal_games.xor_game import XORGame
>>> odd_cycle = XORGame(prob_mat, pred_mat)
>>> '%.2f' % odd_cycle.quantum_value()
'0.98'
>>> '%.1f' % odd_cycle.classical_value()
'0.9'

Note

You do not need to use ‘%.2f’ % or ‘%.1f’ % when you use this function.

References

[1]

John Watrous. Theory of quantum information lecture notes. https://cs.uwaterloo.ca/ watrous/TQI-notes/, 2011.

[2] (1,2)

Richard Cleve, Peter Hoyer, Ben Toner, and John Watrous. Consequences and limits of nonlocal strategies. 2010. arXiv:quant-ph/0404076.

[3]

Richard Cleve, William Slofstra, Falk Unger, and Sarvagya Upadhyay. Strong parallel repetition theorem for quantum xor proof systems. 2008. arXiv:quant-ph/0608146.

Parameters:

prob_mat (numpy.ndarray)
pred_mat (numpy.ndarray)
reps (int)
tol (float)

quantum_value()¶

Compute the quantum value of the XOR game.

To obtain the quantum value of the XOR game, we calculate the following simplified dual problem of the semidefinite program from the set of notes: Lecture 6 of [1]

\[\begin{split}\begin{equation} \begin{aligned} \text{minimize:} \quad & \frac{1}{2} \sum_{x \in X} u(x) + \frac{1}{2} \sum_{ y \in Y} v(y) \\ \text{subject to:} \quad & \begin{pmatrix} \text{Diag}(u) & -D \\ -D^* & \text{Diag}(v) \end{pmatrix} \geq 0, \\ & u \in \mathbb{R}^X, \ v \in \mathbb{R}^Y. \end{aligned} \end{equation}\end{split}\]

where \(D\) is the matrix defined to be

\[D(x,y) = \pi(x, y) (-1)^{f(x,y)}\]

In other words, \(\pi(x, y)\) corresponds to prob_mat[x, y], and \(f(x,y)\) corresponds to pred_mat[x, y].

return:

A value between [0, 1] representing the quantum value.

Return type:: float

classical_value()¶

Compute the classical value of the XOR game.

Returns:: A value between [0, 1] representing the classical value.
Return type:: float

nonsignaling_value()¶

Compute the nonsignaling value of an XOR game.

Here, the exising function in the NonlocalGame class is called.

Returns:: A value between [0, 1] representing the nonsignaling value.
Return type:: float

to_nonlocal_game()¶

Given an XOR game, compute a predicate matrix representing the more generic NonlocalGame equivalent.

Returns:: A NonlocalGame object equivalent to the XOR game.
Return type:: toqito.nonlocal_games.nonlocal_game.NonlocalGame

nonlocal_games.xor_game¶

Module Contents¶

Classes¶

`nonlocal_games.xor_game`¶