BCSGameValue

From QETLAB
Jump to: navigation, search
BCSGameValue
Computes the maximum value of a binary constraint system (BCS) game
Other toolboxes required cvx
Related functions BellInequalityMax
NonlocalGameValue
XORGameValue
Function category Nonlocality and Bell inequalities
Usable within CVX? no

BCSGameValue is a function that computes the maximum possible value of a given binary constraint system (BCS) game[1] 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).

A binary constraint system game is a non-local game in which there is a finite set of variables $v_1, v_2, \ldots, v_k$ and a finite set of constraints placed on those variables: $$ f_1(v_1,v_2,\ldots,v_k) = 1 \quad \quad f_2(v_1,v_2,\ldots,v_k) = 1 \quad \cdots \quad f_m(v_1,v_2,\ldots,v_k) = 1. $$ One of the constraints $f_i$ is chosen (at random, with equal probability) and given to Alice, and one of the variables $v_j$ appearing in $f_i$ is chosen (at random, with equal probability) and given to Bob. Alice and Bob win the game if and only if (1) Alice returns an assignment for every variable that satisfies her constraint, and (2) Bob returns a value for his variable that agrees with the value that Alice chose for that particular variable.

Syntax

  • BCSVAL = BCSGameValue(C)
  • BCSVAL = BCSGameValue(C,MTYPE)
  • BCSVAL = BCSGameValue(C,MTYPE,K)

Argument descriptions

  • C: A cell, each of whose elements is a constraint in the BCS. The constraints themselves are specified as $2 \times 2 \times 2 \times \cdots$ binary arrays, where the $(i,j,k,\ldots)$-entry is 1 if and only if setting $v_1=i, v_2=j, v_3=k, \ldots$ satisfies that constraint.
  • MTYPE (optional, default 'classical'): A string indicating which type of theory should be used when computing the maximum value of the BCS 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 game

The (quite trivial) BCS game consisting of the following two constraints is equivalent to the CHSH inequality: $$ v_1 \oplus v_2 = 0 \quad \quad \quad v_1 \oplus v_2 = 1 $$ We can compute the classical and quantum values of the game with the following code: 

>> C{1} = zeros(2,2);
   C{2} = zeros(2,2);
   for v1 = 0:1
       for v2 = 0:1
           % Set up the first constraint: we win if v1+v2 is even.
           if(mod(v1+v2,2) == 0)
               C{1}(v1+1,v2+1) = 1;
           end
 
            % Set up the first constraint: we win if v1+v2 is odd.
           if(mod(v1+v2,2) == 1)
               C{2}(v1+1,v2+1) = 1;
           end
       end
   end
>> BCSGameValue(C,'classical') % should give 3/4
 
ans =
 
   0.7500
 
>> BCSGameValue(C,'quantum') % should give cos^2(pi/8)
 
ans =
 
   0.8536

The generalized CHSH game

By extending the CHSH game above to have more variables (say $k$ of them), we get the game defined by the following slightly more complicated constraints:: $$ v_1 \oplus v_2 \oplus \cdots \oplus v_k = 0 \quad \quad \quad v_1 \oplus v_2 \oplus \cdots \oplus v_k = 1 $$ We can compute the classical value and bound the quantum value of the game in the $k = 3$ case with the following code: 

>> C{1} = zeros(2,2,2);
   C{2} = zeros(2,2,2);
   for v1 = 0:1
       for v2 = 0:1
           for v3 = 0:1
               % Set up the first constraint: we win if v1+v2+v3 is even.
               if(mod(v1+v2+v3,2) == 0)
                   C{1}(v1+1,v2+1,v3+1) = 1;
               end
               % Set up the first constraint: we win if v1+v2+v3 is odd.
               if(mod(v1+v2+v3,2) == 1)
                   C{2}(v1+1,v2+1,v3+1) = 1;
               end
           end
       end
   end
>> BCSGameValue(C,'classical')
 
ans =
 
   0.8333
 
>> BCSGameValue(C,'quantum',1)
 
ans =
 
   1.0000
 
>> BCSGameValue(C,'quantum','1+ab')
 
ans =
 
   0.9082

Note that the first level of the NPA hierarchy above just gave the (useless) upper bound of 1 on the game's value. However, increasing the level of the NPA hierarchy to the 1+AB level was sufficient to give a non-trivial upper bound.

The "four-line" BCS game

The BCS game defined by the following four constraints was shown by Speelman not to have a quantum strategy giving a value of 1 (see Section 5 of [1]): $$ v_1 \oplus v_2 \oplus v_3 = 0 \quad \quad \quad v_3 \oplus v_4 \oplus v_5 = 0 \\ v_5 \oplus v_6 \oplus v_1 = 0 \quad \quad \quad v_2 \oplus v_4 \oplus v_6 = 1. $$ We can compute the classical value and bound the quantum value of this game with the following code: 

>> C{1} = zeros(2,2,2,2,2,2);
   C{2} = zeros(2,2,2,2,2,2);
   C{3} = zeros(2,2,2,2,2,2);
   C{4} = zeros(2,2,2,2,2,2);
   for v1 = 0:1
     for v2 = 0:1
       for v3 = 0:1
         for v4 = 0:1
           for v5 = 0:1
             for v6 = 0:1
               % Set up the first constraint.
               if(mod(v1+v2+v3,2) == 0)
                 C{1}(v1+1,v2+1,v3+1,v4+1,v5+1,v6+1) = 1;
               end
 
               % Set up the second constraint.
               if(mod(v3+v4+v5,2) == 0)
                 C{2}(v1+1,v2+1,v3+1,v4+1,v5+1,v6+1) = 1;
               end
 
               % Set up the third constraint.
               if(mod(v5+v6+v1,2) == 0)
                 C{3}(v1+1,v2+1,v3+1,v4+1,v5+1,v6+1) = 1;
               end
 
               % Set up the fourth constraint.
               if(mod(v2+v4+v6,2) == 1)
                 C{4}(v1+1,v2+1,v3+1,v4+1,v5+1,v6+1) = 1;
               end
             end
           end
         end
       end
     end
   end
>> BCSGameValue(C,'classical')
 
ans =
 
   0.9167
 
>> BCSGameValue(C,'quantum',1)
 
ans =
 
   1.0000
 
>> BCSGameValue(C,'quantum','1+ab')
 
ans =
 
   0.9789

Just like in the previous example, the first level of the NPA hierarchy above just gave the (useless) upper bound of 1 on the game's value. However, increasing the level of the NPA hierarchy to the 1+AB level was sufficient to give a non-trivial upper bound.

Source code

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

  1. %%  BCSGAMEVALUE    Computes the maximum value of a binary constraint system (BCS) game
  2. %   This function has one required input argument:
  3. %     C: A cell, each of whose elements is a constraint in the BCS. The
  4. %        constraints themselves are specified as 2-by-2-by-2-by-... binary
  5. %        arrays, where the (i,j,k,...)-entry is 1 if and only if setting
  6. %        v1=i, v2=j, v3=k, ... satisfies that constraint.
  7. %
  8. %   BCSVAL = BCSGameValue(C) is the maximum value that the specified 
  9. %   BCS game can take on in classical mechanics. For the maximum quantum
  10. %   or no-signalling value, see the optional arguments described below.
  11. %
  12. %   This function has two optional input arguments:
  13. %     MTYPE (default 'classical'): one of 'classical', 'quantum', or
  14. %       'nosignal', indicating what type of BCS game value should be
  15. %       computed. IMPORTANT NOTE: if MTYPE='quantum' then only an upper
  16. %       bound on the nonlocal game value is computed, not its exact value
  17. %       (see the argument K below).
  18. %     K (default 1): if MYTPE='quantum', then K is a non-negative integer
  19. %       or string indicating what level of the NPA hierarchy to use to
  20. %       bound the nonlocal game (higher values give better bounds, but
  21. %       require more computation time). See the NPAHierarchy function for
  22. %       details.
  23. %
  24. %   BCSVAL = BCSGameValue(C,MTYPE,K) is the maximum value that the
  25. %   specified nonlocal game can take on in the setting (classical, quantum,
  26. %   or no-signalling) specified by MTYPE.
  27. %
  28. %   URL: http://www.qetlab.com/BCSGameValue
  29.  
  30. %   requires: CVX (http://cvxr.com/cvx/), bcs_to_nonlocal.m,
  31. %             NonlocalGameValue.m, opt_args.m
  32. %
  33. %   author: Nathaniel Johnston (nathaniel@njohnston.ca)
  34. %   package: QETLAB
  35. %   last updated: June 24, 2015
  36.  
  37. function bcsval = BCSGameValue(C,varargin)
  38.  
  39.     % set optional argument defaults: MTYPE='classical', K=1
  40.     [mtype,k] = opt_args({ 'classical', 1 },varargin{:});
  41.  
  42.     % Convert the BCS description of the game to the more general non-local
  43.     % description of the game.
  44.     [p,V] = bcs_to_nonlocal(C);
  45.  
  46.     % Compute the value of this non-local game.
  47.     bcsval = NonlocalGameValue(p,V,mtype,k);
  48. end

References

  1. ↑ 1.0 1.1 R. Cleve and R. Mittal. Characterization of binary constraint system games. Lecture Notes in Computer Science, 8572:320–331, 2014. E-print: arXiv:1209.2729 [quant-ph]
Retrieved from "http://www.qetlab.com/wiki/index.php?title=BCSGameValue&oldid=813"