XORGameValue - Revision history

Rmmateri at 16:39, 13 June 2018

2018-06-13T16:39:01Z

Nathaniel at 13:16, 24 June 2015

2015-06-24T13:16:54Z

Nathaniel at 14:30, 20 January 2015

2015-01-20T14:30:40Z

Nathaniel: Nathaniel moved page XORQuantumValue to XORGameValue: Changed function (merge with ClassicalValue)

2015-01-20T14:24:58Z

Nathaniel moved page XORQuantumValue to XORGameValue: Changed function (merge with ClassicalValue)

Nathaniel at 18:23, 16 December 2014

2014-12-16T18:23:57Z

Nathaniel: /* The odd cycles game */ Make example more general

2014-11-20T13:54:17Z

The odd cycles game: Make example more general

Nathaniel: Added XORClassicalValue examples

2014-11-20T00:19:58Z

Added XORClassicalValue examples

Nathaniel: Added CHSH game example

2014-10-16T17:13:32Z

Added CHSH game example

Nathaniel: Created page with "{{Function |name=XORQuantumValue |desc=Computes the quantum value of a nonlocal binary XOR game |req=[http://cvxr.com/cvx/ cvx] |cat=List of functions#Nonlocal_games|Nonloca..."

2014-10-16T15:58:31Z

Created page with "{{Function |name=XORQuantumValue |desc=Computes the quantum value of a nonlocal binary XOR game |req=[http://cvxr.com/cvx/ cvx] |cat=List of functions#Nonlocal_games|Nonloca..."

New page

{{Function
|name=XORQuantumValue
|desc=Computes the quantum value of a nonlocal binary XOR game
|req=[http://cvxr.com/cvx/ cvx]
|cat=[[List of functions#Nonlocal_games|Nonlocal games]]
|upd=October 16, 2014
|v=0.50}}
<tt>'''XORQuantumValue'''</tt> is a [[List of functions|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==
* <tt>WG = XORQuantumValue(P,F)</tt>

==Argument descriptions==
* <tt>P</tt>: 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.
* <tt>F</tt>: A binary matrix (of the same size as <tt>P</tt>) 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<ref>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: [http://arxiv.org/abs/quant-ph/0404076 arXiv:quant-ph/0404076]</ref> 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$:
<syntaxhighlight>
>> 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
</syntaxhighlight>

{{SourceCode|name=XORQuantumValue}}

==References==
<references />

@@ Line 3: / Line 3: @@
 |desc=Computes the classical or quantum value of a nonlocal binary XOR game
 |rel=[[BCSGameValue]]<br />[[BellInequalityMax]]<br />[[NonlocalGameValue]]
-|req=[http://cvxr.com/cvx/ cvx]
+|req=[http://cvxr.com/cvx/ CVX]
 |cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]
 |upd=January 15, 2015}}

@@ Line 2: / Line 2: @@
 |name=XORGameValue
 |desc=Computes the classical or quantum value of a nonlocal binary XOR game
-|rel=[[BellInequalityMax]]
+|rel=[[BCSGameValue]]<br />[[BellInequalityMax]]<br />[[NonlocalGameValue]]
 |req=[http://cvxr.com/cvx/ cvx]
 |cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]

@@ Line 1: / Line 1: @@
 {{Function
-|name=XORQuantumValue
+|name=XORGameValue
-|desc=Computes the quantum value of a nonlocal binary XOR game
+|desc=Computes the classical or quantum value of a nonlocal binary XOR game
-|rel=[[XORClassicalValue]]
+|rel=[[BellInequalityMax]]
 |req=[http://cvxr.com/cvx/ cvx]
 |cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]
-|upd=October 16, 2014
+|upd=January 15, 2015}}
-|v=0.50}}
+<tt>'''XORGameValue'''</tt> is a [[List of functions|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==
-* <tt>WG = XORQuantumValue(P,F)</tt>
+* <tt>VAL = XORGameValue(P,F)</tt>
 ==Argument descriptions==
 * <tt>P</tt>: 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.
 * <tt>F</tt>: A binary matrix (of the same size as <tt>P</tt>) 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==
@@ Line 24: / Line 25: @@
 >> p = [1/4 1/4;1/4 1/4];
 >> f = [0 0;0 1];
->> XORQuantumValue(p,f)
+>> XORGameValue(p,f,'quantum')
 ans =
@@ Line 36: / Line 37: @@
 .8536
->> XORClassicalValue(p,f) % compare to the classical value of this game
+>> XORGameValue(p,f,'classical') % compare to the classical value of this game
 ans =
@@ Line 71: / Line 72: @@
      0     0     0     0
->> XORQuantumValue(p,f)
+>> XORGameValue(p,f,'quantum')
 ans =
@@ Line 83: / Line 84: @@
 .9755
->> XORClassicalValue(p,f) % compare to the classical value of this game
+>> XORGameValue(p,f,'classical') % compare to the classical value of this game
 ans =
@@ Line 90: / Line 91: @@
 </syntaxhighlight>
-{{SourceCode|name=XORQuantumValue}}
+{{SourceCode|name=XORGameValue}}
 ==References==
 <references />

← Older revision	Revision as of 14:24, 20 January 2015
(No difference)

@@ Line 50: / Line 50: @@
 >> 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 = diag(ones(1,n))/(2*n) + circshift(diag(ones(1,n)),-1)/(2*n)
 p =
@@ Line 61: / Line 61: @@
 >> % now we specify the winning condition matrix
->> f = circshift(diag([1,1,1,1,1]),-1)
+>> f = circshift(diag(ones(1,n)),-1)
 f =

@@ Line 2: / Line 2: @@
 |name=XORQuantumValue
 |desc=Computes the quantum value of a nonlocal binary XOR game
 |req=[http://cvxr.com/cvx/ cvx]
 |cat=[[List of functions#Nonlocal_games|Nonlocal games]]
@@ Line 19: / Line 20: @@
 The CHSH game<ref>John Watrous. [https://cs.uwaterloo.ca/~watrous/CPSC519/LectureNotes/20.pdf Lecture 20: Bell inequalities and nonlocality], ''Quantum Computation Lecture Notes'', 2006.</ref> 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)$. The following code demonstrates this fact: the <tt>p</tt> matrix has each entry <tt>1/4</tt> because each of the 4 possible combinations of bits from the referee are equally likely, and the matrix <tt>f</tt> equals <tt>[0 0;0 1]</tt> 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).
+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 <tt>p</tt> matrix has each entry <tt>1/4</tt> because each of the 4 possible combinations of bits from the referee are equally likely, and the matrix <tt>f</tt> equals <tt>[0 0;0 1]</tt> 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).
 <syntaxhighlight>
 >> p = [1/4 1/4;1/4 1/4];
@@ Line 34: / Line 35: @@
 .8536
 </syntaxhighlight>
@@ Line 39: / Line 46: @@
 The odd cycles game<ref>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: [http://arxiv.org/abs/quant-ph/0404076 arXiv:quant-ph/0404076]</ref> 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$:
+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$:
 <syntaxhighlight>
 >> n = 5;
@@ Line 75: / Line 82: @@
 .9755
 </syntaxhighlight>