Difference between revisions of "BCSGameValue"
(Created page with "{{Function |name=BCSGameValue |desc=Computes the maximum value of a binary constraint system (BCS) game |rel=BellInequalityMax<br />NonlocalGameValue<br />XORGameVal...") |
(one more example) |
||
Line 54: | Line 54: | ||
0.8536 | 0.8536 | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | ===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: | ||
+ | <syntaxhighlight> | ||
+ | >> 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 | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Note that the first level of the [[NPAHierarchy|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. | ||
+ | |||
+ | {{SourceCode|name=BCSGameValue}} | ||
==References== | ==References== | ||
<references /> | <references /> |
Revision as of 18:49, 23 June 2015
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).
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.
Source code
Click here to view this function's source code on github.
References
- ↑ 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]