XORGameValue

	XORQuantumValue
	Computes the quantum value of a nonlocal binary XOR game
Other toolboxes required	cvx
Function category	Nonlocal games

XORQuantumValue is a function that computes the quantum value of a nonlocal binary XOR game. That is, it computes the optimal probability of two parties (Alice and Bob) winning such a game, assuming that they can share entanglement but can not communicate during the game.

Syntax

WG = XORQuantumValue(P,F)

Argument descriptions

P: A matrix whose (s,t)-entry gives the probability that the referee will give Alice the value s and Bob the value t. The sum of all entries of this matrix must be 1.
F: A binary matrix (of the same size as P) whose (s,t)-entry indicates the winning choice (either 0 or 1) when Alice and Bob receive values s and t from the referee.

Examples

The odd cycles game

The odd cycles game^[1] is a game where Alice and Bob try to convince the referee that an cycle of length n has a 2-coloring, which is impossible when n is odd. The referee gives each of Alice and Bob a number from 1 to n (representing the n different vertices of the n-cycle), and Alice and Bob respond with a color (0 or 1). They win the game if either (1) the referee gave Alice and Bob the same number and Alice and Bob's responses are the same; or (2) the referee gave Alice and Bob numbers that differ by 1 (corresponding to adjacent vertices) and Alice and Bob's responses are different. Otherwise, they lose the game.

It is known that the maximum probability of winning this game with shared entanglement is $\cos^2(\pi/4n)$ if $n$ is odd and $1$ if $n$ is even, which is verified by the following code when $n = 5$:

>> n = 5;
>> % first compute the probability matrix (see the cited paper for details)
>> p = diag([1,1,1,1,1])/10 + circshift(diag([1,1,1,1,1]),-1)/10

p =

    0.1000    0.1000         0         0         0
         0    0.1000    0.1000         0         0
         0         0    0.1000    0.1000         0
         0         0         0    0.1000    0.1000
    0.1000         0         0         0    0.1000

>> % now we specify the winning condition matrix
>> f = circshift(diag([1,1,1,1,1]),-1)

f =

     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

>> XORQuantumValue(p,f)

ans =

    0.9755

>> cos(pi/(4*n))^2 % compare the answer to the known theoretical answer

ans =

    0.9755

Source code

Click here to view this function's source code on github.

References

↑ R. Cleve, P. Hoyer, B. Toner, and J. Watrous. Consequences and limits of nonlocal strategies. In Proceedings of 19th IEEE Conference on Computational Complexity (CCC 2004). E-print: arXiv:quant-ph/0404076

[1] R. Cleve, P. Hoyer, B. Toner, and J. Watrous. Consequences and limits of nonlocal strategies. In Proceedings of 19th IEEE Conference on Computational Complexity (CCC 2004). E-print: arXiv:quant-ph/0404076

[1]