XORGameValue

	XORGameValue
	Computes the classical or quantum value of a nonlocal binary XOR game
Other toolboxes required	CVX
Related functions	BCSGameValue; BellInequalityMax; NonlocalGameValue
Function category	Nonlocality and Bell inequalities

XORGameValue is a function that computes the classical or 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 communicate before the game, but not during the game, and either (1) they cannot share entanglement, or (2) they can share entanglement.

Syntax

VAL = XORGameValue(P,F)
VAL = XORGameValue(P,F,VTYPE)

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.
VTYPE (optional, default 'classical'): One of 'classical' or 'quantum', indicating whether or not Alice and Bob can use quantum strategies (i.e., shared entanglement).

Examples

The CHSH game

The CHSH game^[1] is a game in which the referee (uniformly at random) gives each of Alice and Bob a single bit, and Alice and Bob win if the XOR of their responses is the AND of the bits received by the referee. That is, Alice and Bob want the XOR of their responses to be 1 if and only if they both received a 1 from the referee.

It is well-known that the maximum probability of winning this game if Alice and Bob share entanglement is $\cos^2(\pi/8)$, whereas the maximum probability of winning this game without entanglement is $3/4$. The following code demonstrates this fact: the p matrix has each entry 1/4 because each of the 4 possible combinations of bits from the referee are equally likely, and the matrix f equals [0 0;0 1] because Alice and Bob want the XOR of their answers to be 1 only when they both receive a 1 from the referee (the first row of the matrix corresponds to Alice receiving a 0, the second row of the matrix corresponds to Alice receiving a 1, and the columns are similar for Bob).

>> p = [1/4 1/4;1/4 1/4];
>> f = [0 0;0 1];
>> XORGameValue(p,f,'quantum')
 
ans =
 
    0.8536
 
>> cos(pi/8)^2 % compare the answer to the known theoretical answer
 
ans =
 
    0.8536
 
>> XORGameValue(p,f,'classical') % compare to the classical value of this game
 
ans =
 
    0.7500

The odd cycles game

The odd cycles game^[2] 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.

If $n$ is odd, it is known that the maximum probability of winning this game with shared entanglement is $\cos^2(\pi/4n)$, whereas the maximum probability of winning this game without entanglement is $1 - 1/(2n)$. These facts are verified by the following code when $n = 5$:

>> n = 5;
>> % first compute the probability matrix (see the cited paper for details)
>> p = diag(ones(1,n))/(2*n) + circshift(diag(ones(1,n)),-1)/(2*n)
 
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(ones(1,n)),-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
 
>> XORGameValue(p,f,'quantum')
 
ans =
 
    0.9755
 
>> cos(pi/(4*n))^2 % compare the answer to the known theoretical answer
 
ans =
 
    0.9755
 
>> XORGameValue(p,f,'classical') % compare to the classical value of this game
 
ans =
 
    0.9000

Source code

Click on "expand" to the right to view the MATLAB source code for this function.

%%  XORGAMEVALUE    Computes the classical or quantum value of a nonlocal binary XOR game

%   This function has two required input arguments:

%     P: a matrix whose (s,t)-entry gives the probability that the referee

%        will give Alice the value s and Bob the value t

%     F: a binary matrix whose (s,t)-entry indicates the winning choice

%        (either 0 or 1) when Alice and Bob receive values s and t from the

```
%        referee
```
```
%
```

%   VAL = XORQuantumValue(P,F) is the classical value of the XOR game

%   specified by the probability matrix P and the binary matrix of winning

%   values F. That is, it is the optimal probability that Alice and Bob can

%   win the game if they are allowed determine a joint strategy beforehand,

%   but not allowed to communicate during the game itself.

```
%
```

%   This function has one optional input argument:

%     VTYPE (default 'classical'): one of 'classical' or 'quantum',

%     indicating what type of value of the game should be computed.

```
%
```

%   VAL = XORQuantumValue(P,F,VTYPE) is the value of the specified XOR game

%   in the setting where Alice and Bob can use strategies in the setting

%   (classical, quantum, or no-signalling) specified by VTYPE.

```
%
```

%   URL: http://www.qetlab.com/XORGameValue

```
 
```

%   requires: cvx (http://cvxr.com/cvx/)

```
%
```

%   author: Nathaniel Johnston (nathaniel@njohnston.ca)

```
%   package: QETLAB
```
```
%   last updated: March 6, 2015
```
```
 
```

function val = XORGameValue(p,f,varargin)

```
 
```
```
[s,t] = size(p);
```
```
 
```

% set optional argument defaults: VTYPE='classical'

[vtype] = opt_args({ 'classical' },varargin{:});

```
 
```
```
% do some error checking
```
```
tol = eps*s^2*t^2;
```
```
if(abs(sum(sum(p)) - 1) > tol)
```

    error('XORGameValue:InvalidP','P must be a probability matrix: its entries must sum to 1.');

```
elseif(min(min(p)) < -tol)
```

    error('XORGameValue:InvalidP','P must be a probability matrix: its entries must be nonnegative.');

```
elseif(~all([s,t] == size(f)))
```

    error('XORGameValue:InvalidDims','P and F must be matrices of the same size.');

```
end
```
```
 
```
```
 
```

% Compute the value of the game, depending on which type of value was

```
% requested.
```
```
if(strcmpi(vtype,'quantum'))
```

    % use semidefinite programming to compute the value of the game

```
    P = p.*(1-2*f);
```
```
    Q = [zeros(s),P;P',zeros(t)];
```
```
 
```
```
    cvx_begin sdp quiet
```
```
        cvx_precision default;
```
```
        variable X(s+t,s+t) symmetric
```
```
        maximize trace(Q*X)
```
```
        subject to
```
```
            diag(X) == 1;
```
```
            X >= 0;
```
```
    cvx_end
```
```
 
```

    % The above SDP actually computes the bias of the game. Convert it to the

```
    % value of the game now.
```
```
    val = real(cvx_optval)/4 + 1/2;
```
```
elseif(strcmpi(vtype,'classical'))
```

    val = 0; % at worst, our winning probability is 0... now try to improve

```
 
```

    % 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).

    for a_ans = 0:2^s-1 % loop over Alice's answers

        for b_ans = 0:2^t-1 % loop over Bob's answers

```
            a_vec = bitget(a_ans,1:s);
```
```
            b_vec = bitget(b_ans,1:t);
```
```
 
```

            % 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 F. Where the

            % values match, 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.
```

            p_win = sum(sum((mod(a_vec.'*ones(1,t) + ones(s,1)*b_vec,2) == f).*p));

```
 
```

            val = max(val,p_win); % is this strategy better than other ones tried so far?

            if(val >= 1 - tol) % already optimal? quit

```
                return;
```
```
            end
```
```
        end
```
```
    end
```
```
else
```

    error('XORGameValue:InvalidVTYPE','VTYPE must be one of ''classical'' or ''quantum''.');

```
end
```

References

↑ John Watrous. Lecture 20: Bell inequalities and nonlocality, Quantum Computation Lecture Notes, 2006.
↑ 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] John Watrous. Lecture 20: Bell inequalities and nonlocality, Quantum Computation Lecture Notes, 2006.

[2] 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]

[2]

XORGameValue

Contents

Syntax

Argument descriptions

Examples

The CHSH game

The odd cycles game

Source code

References

Navigation menu

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

Tools