Nonlocal Games

A number of nonlocal game-related functions.

XOR Games

Two-player XOR game.

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

Bases: object

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 [CHTW04].

This function is adapted from the QETLAB package.

Examples

The CHSH game

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

\[\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)
>>> chsh.quantum_value()
0.8535533885683664
>>>
>>> chsh.classical_value()
0.75

The odd cycle game

The odd cycle game is another XOR game [CHTW04]. 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)
>>> odd_cycle.quantum_value()
0.9755282544736033
>>> odd_cycle.classical_value()
0.9

References

[CSUU08]

Richard Cleve, William Slofstra, Falk Unger, Sarvagya Upadhyay “Strong parallel repetition theorem for quantum XOR proof systems”, 2008, https://arxiv.org/abs/quant-ph/0608146

[CHTW04] (1,2)

Richard Cleve, Peter Hoyer, Ben Toner, John Watrous “Consequences and limits of nonlocal strategies.” Proceedings. 19th IEEE Annual Conference on Computational Complexity, IEEE, 2004. https://arxiv.org/abs/quant-ph/0404076

classical_value()

Compute the classical value of the XOR game.

Raises:

ValueError – Does not support parallel repetitions.

Returns:

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

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: https://cs.uwaterloo.ca/~watrous/CS867.Winter2017/Notes/06.pdf

\[\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].

Returns:

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

Nonlocal Games

Two-player nonlocal game.

class toqito.nonlocal_games.nonlocal_game.NonlocalGame(prob_mat, pred_mat, reps=1)

Bases: object

Create two-player nonlocal game object.

Nonlocal games are a mathematical framework that abstractly models a physical system. This game is played between two players, Alice and Bob, who are not allowed to communicate with each other once the game has started and who play cooperative against an adversary referred to as the referee.

The nonlocal game framework was originally introduced in [CHTW04_2].

References

[CHTW04_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

classical_value()

Compute the classical value of the nonlocal game.

This function has been adapted from the QETLAB package.

Returns:

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

commuting_measurement_value_upper_bound(k=1)

Compute an upper bound on the commuting measurement value of the nonlocal game.

This function calculates an upper bound on the commuting measurement value by using k-levels of the NPA hierarchy [NPA]. The NPA hierarchy is a uniform family of semidefinite programs that converges to the commuting measurement value of any nonlocal game.

You can determine the level of the hierarchy by a positive integer or a string of a form like ‘1+ab+aab’, which indicates that an intermediate level of the hierarchy should be used, where this example uses all products of one measurement, all products of one Alice and one Bob measurement, and all products of two Alice and one Bob measurements.

References

[NPA]

Miguel Navascues, Stefano Pironio, Antonio Acin, “A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations.” https://arxiv.org/abs/0803.4290

Parameters:

k – The level of the NPA hierarchy to use (default=1).

Returns:

The upper bound on the commuting strategy value of a nonlocal game.

classmethod from_bcs_game(constraints, reps=1)

Construct nonlocal game object from a binary constraint system game.

Raises:

ValueError – At least one constraint needs to be supplied.

Parameters:

• constraints – A list of m matrices corresponding to the m constraints in the BCS game. Each constraint matrix is an n-dimensional matrix of shape 2 x 2 x … x 2. The (i, j, k, …)-th entry is 1 if and only if the contraint is satisfied given the values v_1 = i, v_2 = j, v_3 = k, …, and otherwise 0.

• reps – Number of parallel repetitions to perform. Default is 1.

Returns:

An instance of a nonlocal game object.

nonsignaling_value()

Compute the non-signaling value of the nonlocal game.

Returns:

A value between [0, 1] representing the non-signaling value.

quantum_value_lower_bound(dim=2, iters=5, tol=1e-05)

Compute a lower bound on the quantum value of a nonlocal game [LD07].

Calculates a lower bound on the maximum value that the specified nonlocal game can take on in quantum mechanical settings where Alice and Bob each have access to dim-dimensional quantum system.

This function works by starting with a randomly-generated POVM for Bob, and then optimizing Alice’s POVM and the shared entangled state. Then Alice’s POVM and the entangled state are fixed, and Bob’s POVM is optimized. And so on, back and forth between Alice and Bob until convergence is reached.

Note that the algorithm is not guaranteed to obtain the optimal local bound and can get stuck in local minimum values. The alleviate this, the iter parameter allows one to run the algorithm some pre-specified number of times and keep the highest value obtained.

The algorithm is based on the alternating projections algorithm as it can be applied to Bell inequalities as shown in [LD07].

The alternating projection algorithm has also been referred to as the “see-saw” algorithm as it goes back and forth between the following two semidefinite programs:

\[\begin{split}\begin{equation} \begin{aligned} \textbf{SDP-1:} \quad & \\ \text{maximize:} \quad & \sum_{(x,y \in \Sigma)} \pi(x,y) \sum_{(a,b) \in \Gamma} V(a,b|x,y) \langle B_b^y, A_a^x \rangle \\ \text{subject to:} \quad & \sum_{a \in \Gamma_{\mathsf{A}}}= \tau, \qquad \qquad \forall x \in \Sigma_{\mathsf{A}}, \\ \quad & A_a^x \in \text{Pos}(\mathcal{A}), \qquad \forall x \in \Sigma_{\mathsf{A}}, \ \forall a \in \Gamma_{\mathsf{A}}, \\ & \tau \in \text{D}(\mathcal{A}). \end{aligned} \end{equation}\end{split}\]

\[\begin{split}\begin{equation} \begin{aligned} \textbf{SDP-2:} \quad & \\ \text{maximize:} \quad & \sum_{(x,y \in \Sigma)} \pi(x,y) \sum_{(a,b) \in \Gamma} V(a,b|x,y) \langle B_b^y, A_a^x \rangle \\ \text{subject to:} \quad & \sum_{b \in \Gamma_{\mathsf{B}}}= \mathbb{I}, \qquad \qquad \forall y \in \Sigma_{\mathsf{B}}, \\ \quad & B_b^y \in \text{Pos}(\mathcal{B}), \qquad \forall y \in \Sigma_{\mathsf{B}}, \ \forall b \in \Gamma_{\mathsf{B}}. \end{aligned} \end{equation}\end{split}\]

Examples

The CHSH game

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

\[\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\).

>>> import numpy as np
>>> from toqito.nonlocal_games.nonlocal_game import NonlocalGame
>>>
>>> dim = 2
>>> num_alice_inputs, num_alice_outputs = 2, 2
>>> num_bob_inputs, num_bob_outputs = 2, 2
>>> prob_mat = np.array([[1 / 4, 1 / 4], [1 / 4, 1 / 4]])
>>> 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 np.mod(a_alice + b_bob + x_alice * y_bob, dim) == 0:
>>>                    pred_mat[a_alice, b_bob, x_alice, y_bob] = 1
>>>
>>> chsh = NonlocalGame(prob_mat, pred_mat)
>>> chsh.quantum_value_lower_bound()
0.8535533840915605

References

[LD07] (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

Parameters:

• dim – The dimension of the quantum system that Alice and Bob have access to (default = 2).

• iters – The number of times to run the alternating projection algorithm.

• tol – The tolerance before quitting out of the alternating projection semidefinite program.

Returns:

The lower bound on the quantum value of a nonlocal game.

Extended Nonlocal Games

Two-player extended nonlocal game.

class toqito.nonlocal_games.extended_nonlocal_game.ExtendedNonlocalGame(prob_mat, pred_mat, reps=1)

Bases: object

Create two-player extended nonlocal game object.

Extended nonlocal games are a superset of nonlocal games in which the players share a tripartite state with the referee. In such games, the winning conditions for Alice and Bob may depend on outcomes of measurements made by the referee, on its part of the shared quantum state, in addition to Alice and Bob’s answers to the questions sent by the referee.

Extended nonlocal games were initially defined in [JMRW16] and more information on these games can be found in [Russo17].

References

[JMRW16]

Nathaniel Johnston, Rajat Mittal, Vincent Russo, John Watrous “Extended non-local games and monogamy-of-entanglement games”, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 472.2189 (2016), https://arxiv.org/abs/1510.02083

[Russo17]

Vincent Russo “Extended nonlocal games” https://arxiv.org/abs/1704.07375

commuting_measurement_value_upper_bound(k=1)

Compute an upper bound on the commuting measurement value of an extended nonlocal game.

This function calculates an upper bound on the commuting measurement value by using k-levels of the NPA hierarchy [NPA]. The NPA hierarchy is a uniform family of semidefinite programs that converges to the commuting measurement value of any extended nonlocal game.

You can determine the level of the hierarchy by a positive integer or a string of a form like ‘1+ab+aab’, which indicates that an intermediate level of the hierarchy should be used, where this example uses all products of one measurement, all products of one Alice and one Bob measurement, and all products of two Alice and one Bob measurements.

References

[NPA]

Miguel Navascues, Stefano Pironio, Antonio Acin, “A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations.” https://arxiv.org/abs/0803.4290

Parameters:

k – The level of the NPA hierarchy to use (default=1).

Returns:

The upper bound on the commuting strategy value of an extended nonlocal game.

nonsignaling_value()

Calculate the non-signaling value of an extended nonlocal game.

The non-signaling value of an extended nonlocal game is the supremum value of the winning probability of the game taken over all non-signaling strategies for Alice and Bob.

A non-signaling strategy for an extended nonlocal game consists of a function

\[K : \Gamma_A \times \Gamma_B \times \Sigma_A \times \Sigma_B \rightarrow \text{Pos}(\mathcal{R})\]

such that

\[\sum_{a \in \Gamma_A} K(a,b|x,y) = \rho_b^y \quad \text{and} \quad \sum_{b \in \Gamma_B} K(a,b|x,y) = \sigma_a^x,\]

for all \(x \in \Sigma_A\) and \(y \in \Sigma_B\) where \(\{\rho_b^y : y \in \Sigma_A, \ b \in \Gamma_B\}\) and \(\{\sigma_a^x : x \in \Sigma_A, \ a \in \Gamma_B\}\) are collections of operators satisfying

\[\sum_{a \in \Gamma_A} \rho_b^y = \tau = \sum_{b \in \Gamma_B} \sigma_a^x,\]

for every choice of \(x \in \Sigma_A\) and \(y \in \Sigma_B\) where \(\tau \in \text{D}(\mathcal{R})\) is a density operator.

Returns:

The non-signaling value of the extended nonlocal game.

quantum_value_lower_bound(iters=5, tol=1e-05)

Calculate lower bound on the quantum value of an extended nonlocal game.

Test

Returns:

The quantum value of the extended nonlocal game.

unentangled_value()

Calculate the unentangled value of an extended nonlocal game.

The unentangled value of an extended nonlocal game is the supremum value for Alice and Bob’s winning probability in the game over all unentangled strategies. Due to convexity and compactness, it is possible to calculate the unentangled extended nonlocal game by:

\[\omega(G) = \max_{f, g} \lVert \sum_{(x,y) \in \Sigma_A \times \Sigma_B} \pi(x,y) V(f(x), g(y)|x, y) \rVert\]

where the maximum is over all functions \(f : \Sigma_A \rightarrow \Gamma_A\) and \(g : \Sigma_B \rightarrow \Gamma_B\).

Returns:

The unentangled value of the extended nonlocal game.

Quantum Hedging Protocols

Semidefinite programs for obtaining values of quantum hedging scenarios.

class toqito.nonlocal_games.quantum_hedging.QuantumHedging(q_a, num_reps)

Bases: object

Calculate optimal winning probabilities for hedging scenarios.

Calculate the maximal and minimal winning probabilities for quantum hedging to occur in certain two-party scenarios [MW12], [AMR13].

Examples

This example illustrates the initial example of perfect hedging when Alice and Bob play two repetitions of the game where Alice prepares the maximally entangled state:

\[u = \frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle,\]

and Alice applies the measurement operator defined by vector

\[v = \cos(\pi/8)|00\rangle + \sin(\pi/8)|11\rangle.\]

As was illustrated in [MW12], the hedging value of the above scenario is \(\cos(\pi/8)^2 \approx 0.8536\)

>>> from numpy import kron, cos, sin, pi, sqrt, isclose
>>> from toqito.states import basis
>>> from toqito.nonlocal_games.quantum_hedging import QuantumHedging
>>>
>>> e_0, e_1 = basis(2, 0), basis(2, 1)
>>> e_00, e_01 = kron(e_0, e_0), kron(e_0, e_1)
>>> e_10, e_11 = kron(e_1, e_0), kron(e_1, e_1)
>>>
>>> alpha = 1 / sqrt(2)
>>> theta = pi / 8
>>> w_var = alpha * cos(theta) * e_00 + sqrt(1 - alpha ** 2) * sin(theta) * e_11
>>>
>>> l_1 = -alpha * sin(theta) * e_00 + sqrt(1 - alpha ** 2) * cos(theta) * e_11
>>> l_2 = alpha * sin(theta) * e_10
>>> l_3 = sqrt(1 - alpha ** 2) * cos(theta) * e_01
>>>
>>> q_1 = w_var * w_var.conj().T
>>> q_0 = l_1 * l_1.conj().T + l_2 * l_2.conj().T + l_3 * l_3.conj().T
>>> molina_watrous = QuantumHedging(q_0, 1)
>>>
>>> # cos(pi/8)**2 \approx 0.8536
>>> molina_watrous.max_prob_outcome_a_primal()
0.853553390038077

References

[MW12] (1,2)

Molina, Abel, and Watrous, John. “Hedging bets with correlated quantum strategies.” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 468.2145 (2012): 2614-2629. https://arxiv.org/abs/1104.1140

[AMR13]

Arunachalam, Srinivasan, Molina, Abel and Russo, Vincent. “Quantum hedging in two-round prover-verifier interactions.” arXiv preprint arXiv:1310.7954 (2013). https://arxiv.org/pdf/1310.7954.pdf

max_prob_outcome_a_dual()

Compute the maximal probability for calculating outcome “a”.

The dual problem for the maximal probability of “a” is given as:

\[\begin{split}\begin{equation} \begin{aligned} \text{minimize:} \quad & \text{Tr}(Y) \\ \text{subject to:} \quad & \pi \left(I_{\mathcal{Y}_1 \otimes \ldots \otimes \mathcal{Y}_n} \otimes Y \right) \pi^* \geq Q_{a_1} \otimes \ldots \otimes Q_{a_n}, \\ & Y \in \text{Herm} \left(\mathcal{X} \otimes \ldots \otimes \mathcal{X}_n \right) \end{aligned} \end{equation}\end{split}\]

Returns:

The optimal maximal probability for obtaining outcome “a”.

max_prob_outcome_a_primal()

Compute the maximal probability for calculating outcome “a”.

The primal problem for the maximal probability of “a” is given as:

\[\begin{split}\begin{equation} \begin{aligned} \text{maximize:} \quad & \langle Q_{a_1} \otimes \ldots \otimes Q_{a_n}, X \rangle \\ \text{subject to:} \quad & \text{Tr}_{\mathcal{Y}_1 \otimes \ldots \otimes \mathcal{Y}_n}(X) = I_{\mathcal{X}_1 \otimes \ldots \otimes \mathcal{X}_n},\\ & X \in \text{Pos}(\mathcal{Y}_1 \otimes \mathcal{X}_1 \otimes \ldots \otimes \mathcal{Y}_n \otimes \mathcal{X}_n) \end{aligned} \end{equation}\end{split}\]

Returns:

The optimal maximal probability for obtaining outcome “a”.

min_prob_outcome_a_dual()

Compute the minimal probability for calculating outcome “a”.

The dual problem for the minimal probability of “a” is given as:

\[\begin{split}\begin{equation} \begin{aligned} \text{maximize:} \quad & \text{Tr}(Y) \\ \text{subject to:} \quad & \pi \left(I_{\mathcal{Y}_1 \otimes \ldots \otimes \mathcal{Y}_n} \otimes Y \right) \pi^* \leq Q_{a_1} \otimes \ldots \otimes Q_{a_n}, \\ & Y \in \text{Herm} \left(\mathcal{X} \otimes \ldots \otimes \mathcal{X}_n \right) \end{aligned} \end{equation}\end{split}\]

Returns:

The optimal minimal probability for obtaining outcome “a”.

min_prob_outcome_a_primal()

Compute the minimal probability for calculating outcome “a”.

The primal problem for the minimal probability of “a” is given as:

\[\begin{split}\begin{equation} \begin{aligned} \text{minimize:} \quad & \langle Q_{a_1} \otimes \ldots \otimes Q_{a_n}, X \rangle \\ \text{subject to:} \quad & \text{Tr}_{\mathcal{Y}_1 \otimes \ldots \otimes \mathcal{Y}_n}(X) = I_{\mathcal{X}_1 \otimes \ldots \otimes \mathcal{X}_n},\\ & X \in \text{Pos}(\mathcal{Y}_1 \otimes \mathcal{X}_1 \otimes \ldots \otimes \mathcal{Y}_n \otimes \mathcal{X}_n) \end{aligned} \end{equation}\end{split}\]

Returns:

The optimal minimal probability for obtaining outcome “a”.