Source code for toqito.nonlocal_games.xor_game

"""Two-player XOR game."""
import cvxpy
import numpy as np


[docs]class XORGame: r""" 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]_. .. math:: \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 .. math:: \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 .. math:: \begin{equation} a \oplus b = x \land y. \end{equation} Recall that :math:`\oplus` refers to the XOR operation. The optimal quantum value of CHSH is :math:`\cos(\pi/8)^2 \approx 0.8536` where the optimal classical value is :math:`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 :code:`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] 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 """ def __init__( self, prob_mat: np.ndarray, pred_mat: np.ndarray, reps: int = 1, tol: float = None, ) -> None: """ Construct XOR game object. :raises ValueError: If dimension of probability matrix is not equal to dimension of predicate matrix. :param prob_mat: A matrix whose (q_0, q_1)-entry gives the probability that the referee will give Alice the value `q_0` and Bob the value `q_1`. :param pred_mat: A binary matrix whose (q_0, q_1)-entry indicates the winning choice (either 0 or 1) when Alice and Bob receive values `q_0` and `q_1` from the referee. :param tol: The error tolerance for the value. """ self.prob_mat = prob_mat self.pred_mat = pred_mat self.reps = reps q_0, q_1 = self.prob_mat.shape if tol is None: self.tol = np.finfo(float).eps * q_0**2 * q_1**2 else: self.tol = tol # Perform some basic error checking to ensure the probability and # predicate matrices are well-defined. if (q_0, q_1) != self.pred_mat.shape: raise ValueError( "Invalid: The matrices `prob_mat` and `pred_mat` must" " be matrices of the same size." ) if -np.min(np.min(self.prob_mat)) > self.tol: raise ValueError( "Invalid: The variable `prob_mat` must be a " "probability matrix: its entries must be " "non-negative." ) if np.abs(np.sum(np.sum(self.prob_mat)) - 1) > self.tol: raise ValueError( "Invalid: The variable `prob_mat` must be a " "probability matrix: its entries must sum to 1." )
[docs] def quantum_value(self) -> float: r""" 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 .. math:: \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} where :math:`D` is the matrix defined to be .. math:: D(x,y) = \pi(x, y) (-1)^{f(x,y)} In other words, :math:`\pi(x, y)` corresponds to :code:`prob_mat[x, y]`, and :math:`f(x,y)` corresponds to :code:`pred_mat[x, y]`. :return: A value between [0, 1] representing the quantum value. """ alice_in, bob_in = self.prob_mat.shape d_mat = np.zeros([alice_in, bob_in]) for x_alice in range(alice_in): for y_bob in range(bob_in): d_mat[x_alice, y_bob] = self.prob_mat[x_alice, y_bob] * (-1) ** ( self.pred_mat[x_alice, y_bob] ) u_vec = cvxpy.Variable(alice_in, complex=False) v_vec = cvxpy.Variable(bob_in, complex=False) objective = cvxpy.Minimize(cvxpy.sum(u_vec) + cvxpy.sum(v_vec)) constraints = [ cvxpy.bmat( [ [cvxpy.diag(u_vec), -d_mat], [np.negative(d_mat.conj().T), cvxpy.diag(v_vec)], ] ) >> 0 ] problem = cvxpy.Problem(objective, constraints) problem.solve() if self.reps == 1: return np.real(problem.value) / 4 + 1 / 2 # It holds from (https://arxiv.org/abs/quant-ph/0608146) that the # quantum value of any XOR game obeys strong parallel repetition. That # is, it holds that: # \omega^*(G^{^n}) = \omega^*(G)^n, # where G^{^n} denotes playing the game G n-times. return (np.real(problem.value) / 4 + 1 / 2) ** self.reps
[docs] def classical_value(self) -> float: """ Compute the classical value of the XOR game. :raises ValueError: Does not support parallel repetitions. :return: A value between [0, 1] representing the classical value. """ if self.reps == 1: q_0, q_1 = self.prob_mat.shape # At worst, out winning probability is 0. Now, try to improve. val = 0 # Find the maximum probability of winning (this is NP-hard, so don't # expect an easy way to do it: just loop over all strategies. # Loop over Alice's answers for a_ans in range(2**q_0): # Loop over Bob's answers: for b_ans in range(2**q_1): a_vec = (a_ans >> np.arange(q_0)) & 1 b_vec = (b_ans >> np.arange(q_1)) & 1 # Now compute the winning probability under this strategy: # XOR together Alice's responses and Bob's responses, then # check where the XORed value equals the value in the given # matrix. Where the values match, multiply by the # probability of getting that pair of questions (i.e., # multiply by the probability of getting that pair of # questions (i.e., multiply entry-wise by P) and then sum # over the rows and columns. classical_strategy = np.mod( np.multiply(a_vec.conj().T.reshape(-1, 1), np.ones((1, q_1))) + np.multiply(np.ones((q_0, 1)), b_vec), 2, ) p_win = np.sum( np.sum(np.multiply(classical_strategy == self.pred_mat, self.prob_mat)) ) # Is this strategy better than other ones tried so far? val = max(val, p_win) # Already optimal? Quit. if val >= 1 - self.tol: return val return val raise ValueError( "Error: toqito currently does not support " "multiple repetitions for the classical value of " "a nonlocal game." )