NonlocalGameValue

From QETLAB
Revision as of 17:31, 10 July 2015 by Nathaniel (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
NonlocalGameValue
Computes the maximum value of a two-player non-local game

Other toolboxes required cvx
Related functions BCSGameValue
BellInequalityMax
NPAHierarchy
XORGameValue
Function category Nonlocality and Bell inequalities
Usable within CVX? no

NonlocalGameValue is a function that computes the maximum possible value of a given non-local game under either classical mechanics, quantum mechanics, or general no-signalling theories. In the classical and non-signalling cases, an exact value is computed, whereas the value computed in the quantum case is only an upper bound (found using the NPA hierarchy).

Syntax

  • NGVAL = NonlocalGameValue(P,V)
  • NGVAL = NonlocalGameValue(P,V,MTYPE)
  • NGVAL = NonlocalGameValue(P,V,MTYPE,K)

Argument descriptions

  • P: A probability matrix whose $(x,y)$-entry gives the probability that the referee asks Alice question $x$ and Bob question $y$.
  • V: A 4-D array whose $(a,b,x,y)$-entry gives the value awarded to Alice and Bob if they reply with answers $(a,b)$ to questions $(x,y)$.
  • MTYPE (optional, default 'classical'): A string indicating which type of theory should be used when computing the maximum value of the non-local game. Must be one of 'classical', 'quantum', or 'nosignal'. If MTYPE = 'quantum' then only an upper bound on the non-local game is computed, not necessarily the best upper bound (see the argument K below).
  • K (optional, default 1): If MTYPE = 'quantum' then this is a non-negative integer indicating what level of the NPA hierarchy should be used when bounding the value of the non-local game. Higher values of K give better bounds, but require more memory and time. Alternatively, K can be 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 1 measurement, all products of one Alice and one Bob measurement, and all products of two Alice and one Bob measurement. Use plus signs to separate the different categories of products, as above. The first character of this string should always be a number, indicating the base level to use. If MTYPE is anything other than 'quantum' then K has no effect.

Examples

The CHSH inequality

One formulation of the CHSH inequality[1] is as follows:

  • A referee asks Alice a question $x \in \{0,1\}$ and Bob a question $y \in \{0,1\}$.
  • Alice and Bob then reply with answers $a \in \{0,1\}$ and $b \in \{0,1\}$ respectively.
  • Alice and Bob win if and only if $a \oplus b = xy$.

The optimal probability with which Alice and Bob can win this game in classical, quantum, and no-signalling theories are as follows:

>> d = 2;
>> p = ones(d,d)/d^2;
>> V = zeros(d,d,d,d);
>> for a = 1:d
     for b = 1:d
       for x = 1:d
         for y = 1:d
           if(mod(a+b+x*y,d)==0)
             V(a,b,x,y) = 1;
           end
         end
       end
     end
   end
>> NonlocalGameValue(p,V,'classical')
 
ans =
 
    0.7500
 
>> NonlocalGameValue(p,V,'quantum',1)
 
ans =
 
    0.8536
 
>> NonlocalGameValue(p,V,'nosignal')
 
ans =
 
    1.0000

The CHSH-d inequality

A generalization of the CHSH inequality to higher dimensions is exactly as above, except each of $a,b,x,y$ are taken from the set $\{0,1,\ldots,d-1\}$.[2] The following code computes the values of the CHSH-3 game:

>> d = 3;
>> p = ones(d,d)/d^2;
>> V = zeros(d,d,d,d);
>> for a = 1:d
     for b = 1:d
       for x = 1:d
         for y = 1:d
           if(mod(a+b+x*y,d)==0)
             V(a,b,x,y) = 1;
           end
         end
       end
     end
   end
>> NonlocalGameValue(p,V,'classical')
 
ans =
 
    0.6667
 
>> NonlocalGameValue(p,V,'quantum',1)
 
ans =
 
    0.7182
 
>> NonlocalGameValue(p,V,'quantum',2)
 
ans =
 
    0.7182
 
>> NonlocalGameValue(p,V,'quantum','2+aab')
 
ans =
 
    0.7124
 
>> NonlocalGameValue(p,V,'nosignal')
 
ans =
 
    1.0000

The Fortnow-Feige-Lovász game

The Fortnow-Feige-Lovász (FFL) game[3][4] is well-known example of a non-local game for which perfect parallel repetition does not hold (i.e., quantum players playing two copies of the game in parallel can do better than they can by playing the games in succession).

The game has binary inputs and outputs, and is defined by the rule that the referee asks Alice and Bob the question pair $(x,y) = (0,0)$, $(0,1)$, or $(1,0)$ with probability $1/3$ each, and Alice and Bob win if and only if their answers satisfy $x \vee a \neq y \vee b$, where $\vee$ denotes the bitwise OR operation.

It is known that both the classical value and quantum value of this game equal $2/3$, which we can verify as follows:

>> p = [1 1;1 0]/3;
>> V = zeros(2,2,2,2);
>> for a = 1:2
       for b = 1:2
           for x = 1:2
               for y = 1:2
                   if(max(x,a) ~= max(y,b))
                       V(a,b,x,y) = 1;
                   end
               end
           end
       end
   end
>> NonlocalGameValue(p,V,'classical')
 
ans =
 
    0.6667
 
>> NonlocalGameValue(p,V,'quantum',1)
 
ans =
 
    0.6667

Parallel repetition

In fact, we can even compute the classical and quantum values of two copies of the FFL game being run in parallel: we simply specify the REPT input argument to be 2:

>> NonlocalGameValue(p,V,'classical',1,2)
 
ans =
 
    0.6667
 
>> NonlocalGameValue(p,V,'quantum',1,2)
 
ans =
 
    0.6667

Indeed, the fact that both of these values also equal $2/3$ is a known fact [5]. Note that in the command NonlocalGameValue(p,V,'classical',1,2), the "1" that is provided as the value of K does not do anything: it is simply provided as a placeholder so that we can set REPT = 2 in the next input argument (e.g., we could have just as well entered the command NonlocalGameValue(p,V,'classical',9873,2), and the same calculation would have been carried out).

Source code

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

  1. %%  NONLOCALGAMEVALUE    Computes the maximum value of a two-player non-local game
  2. %   This function has two required input arguments:
  3. %     P: a matrix whose (x,y)-entry is the probability that the referee
  4. %        asks Alice question x and Bob question y
  5. %     V: a 4-D array whose (a,b,x,y)-entry is the value given to Alice and
  6. %        Bob when they provide answers a and b respectively to questions x
  7. %        and y.
  8. %
  9. %   NGVAL = NonlocalGameValue(P,V) is the maximum value that the specified 
  10. %   non-local game can take on in classical mechanics. For the maximum
  11. %   quantum or no-signalling value, see the optional arguments described
  12. %   below.
  13. %
  14. %   This function has three optional input arguments:
  15. %     MTYPE (default 'classical'): one of 'classical', 'quantum', or
  16. %       'nosignal', indicating what type of nonlocal game value should be
  17. %       computed. IMPORTANT NOTE: if MTYPE='quantum' then only an upper
  18. %       bound on the non-local game value is computed, not its exact value
  19. %       (see the argument K below).
  20. %     K (default 1): if MYTPE='quantum', then K is a non-negative integer
  21. %       or string indicating what level of the NPA hierarchy to use to
  22. %       bound the non-local game (higher values give better bounds, but
  23. %       require more computation time). See the NPAHierarchy function for
  24. %       details. If MTYPE is anything else, then K is simply ignored.
  25. %     REPT (default 1): the number of times that the non-local game should
  26. %       be played in parallel (i.e., the number of repetitions of the
  27. %       game).
  28. %
  29. %   NGVAL = NonlocalGameValue(P,V,MTYPE,K,REPT) is the maximum value that
  30. %   the specified non-local game can take on in the setting (classical,
  31. %   quantum or no-signalling) specified by MTYPE.
  32. %
  33. %   URL: http://www.qetlab.com/NonlocalGameValue
  34.  
  35. %   requires: CVX (http://cvxr.com/cvx/), NPAHierarchy.m, opt_args.m,
  36. %             update_odometer.m
  37. %
  38. %   author: Nathaniel Johnston (nathaniel@njohnston.ca)
  39. %   package: QETLAB
  40. %   last updated: July 10, 2015
  41.  
  42. function ngval = NonlocalGameValue(p,V,varargin)
  43.  
  44.     % set optional argument defaults: MTYPE='classical', K=1, REPT=1
  45.     [mtype,k,rept] = opt_args({ 'classical', 1, 1 },varargin{:});
  46.  
  47.     % Get some basic values.
  48.     [ma,mb] = size(p);
  49.     oa = size(V,1);
  50.     ob = size(V,2);
  51.  
  52.     % Are we playing the game multiple times? If so, adjust p and V
  53.     % accordingly.
  54.     if(rept > 1)
  55.         % Create the new probability array.
  56.         p = Tensor(p,rept);
  57.  
  58.         % Create the new winning output array (this is more complicated
  59.         % since MATLAB doesn't have any built-in functions for tensoring
  60.         % together 4D arrays).
  61.         V2 = zeros(oa^rept,ob^rept,ma^rept,mb^rept);
  62.         i_ind = zeros(1,rept);
  63.         j_ind = zeros(1,rept);
  64.         for i = 1:ma^rept
  65.             for j = 1:mb^rept
  66.                 for l = rept:-1:1
  67.                     to_tensor{l} = V(:,:,i_ind(l)+1,j_ind(l)+1);
  68.                 end
  69.                 V2(:,:,i,j) = Tensor(to_tensor);
  70.  
  71.                 j_ind = update_odometer(j_ind,mb*ones(1,rept));
  72.             end
  73.             i_ind = update_odometer(i_ind,ma*ones(1,rept));
  74.         end
  75.         V = V2;
  76.  
  77.         % Update some computed values.
  78.         ma = ma^rept;
  79.         mb = mb^rept;
  80.         oa = oa^rept;
  81.         ob = ob^rept;
  82.     end
  83.  
  84.     % The no-signalling maximum is just implemented by taking the zero-th
  85.     % level of the NPA (quantum) hierarchy.
  86.     if(strcmpi(mtype,'nosignal'))
  87.         mtype = 'quantum';
  88.         k = 0;
  89.     end
  90.  
  91.     % Compute the maximum value of the non-local game, depending on which
  92.     % type of maximum was requested.
  93.     if(strcmpi(mtype,'quantum'))
  94.         cvx_begin quiet
  95.             variable q(oa,ob,ma,mb);
  96.             maximize sum(sum(p.*squeeze(sum(sum(V.*q,1),2))))
  97.             subject to
  98.                 NPAHierarchy(q,k) == 1;
  99.         cvx_end
  100.  
  101.         ngval = cvx_optval;
  102.  
  103.         % Deal with error messages.
  104.         if(strcmpi(cvx_status,'Inaccurate/Solved'))
  105.             warning('NonlocalGameValue:NumericalProblems','Minor numerical problems encountered by CVX. Consider adjusting the tolerance level TOL and re-running the script.');
  106.         elseif(strcmpi(cvx_status,'Inaccurate/Infeasible'))
  107.             warning('NonlocalGameValue:NumericalProblems','Minor numerical problems encountered by CVX. Consider adjusting the tolerance level TOL and re-running the script.');
  108.         elseif(strcmpi(cvx_status,'Unbounded') || strcmpi(cvx_status,'Inaccurate/Unbounded') || strcmpi(cvx_status,'Failed'))
  109.             error('NonlocalGameValue:NumericalProblems',strcat('Numerical problems encountered (CVX status: ',cvx_status,'). Please try adjusting the tolerance level TOL.'));
  110.         end
  111.     elseif(strcmpi(mtype,'classical'))
  112.         % Compute the classical maximum value just by brute-forcing over
  113.         % all possibilities.
  114.         ngval = -Inf;
  115.         a_ind = zeros(1,ma);
  116.         b_ind = zeros(1,mb);
  117.         a_ind(ma) = oa-2;
  118.         b_ind(mb) = ob-2;
  119.         p = permute(repmat(p,[1,1,oa,ob]),[3,4,1,2]);
  120.         ab_prob = zeros(oa,ob,ma,mb);
  121.  
  122.         for i = 1:oa^ma
  123.             for j = 1:ob^mb
  124.                 for x = 1:ma
  125.                     for y = 1:mb
  126.                         ab_prob(:,:,x,y) = zeros(oa,ob);
  127.                         ab_prob(a_ind(x)+1,b_ind(y)+1,x,y) = 1;
  128.                     end
  129.                 end
  130.                 tgval = sum(sum(sum(sum(p.*V.*ab_prob))));
  131.                 if(tgval >= ngval - 0.000001)
  132.                     ngval = max(ngval, sum(sum(sum(sum(p.*V.*ab_prob)))));
  133.                 end
  134.                 b_ind = update_odometer(b_ind, ob*ones(1,mb));
  135.             end
  136.             a_ind = update_odometer(a_ind, oa*ones(1,ma));
  137.         end
  138.     else
  139.         error('NonlocalGameValue:InvalidMTYPE','MTYPE must be one of ''classical'', ''quantum'', or ''nosignal''.');
  140.     end
  141. end

Notes

In practice, K probably can't be any larger than 4 when MTYPE = 'quantum', due to memory and time restrictions.

References

  1. J.F. Clauser, M.A. Horne, A. Shimony, R.A. Holt. Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett., 23(15):880–884, 1969.
  2. M. Howard. Maximum nonlocality and minimum uncertainty using magic states. E-print: arXiv:arXiv:1501.05319 [quant-ph], 2015.
  3. U. Feige, L. Lovász, In Proceedings of the 24th ACM STOC, pages 733-744, 1992.
  4. L. Fortnow, PhD thesis, Massachusetts Institute of Technology, Technical Report MIT/LCS/TR-447, May 1989.
  5. R. Cleve, W. Slofstra, F. Unger, and S. Upadhyay. Perfect parallel repetition theorem for quantum XOR proof systems. Computational Complexity, 17:282–299, 2008. E-print: arXiv:quant-ph/0608146