NonlocalGameValue - Revision history

Nathaniel: Function Removed notice

2022-10-27T19:00:56Z

Function Removed notice

← Older revision		Revision as of 19:00, 27 October 2022
Line 7:		Line 7:
	\|upd=March 6, 2015		\|upd=March 6, 2015
	\|cvx=no}}		\|cvx=no}}
			{\| class="wikitable"
			\|-
			! FUNTION REMOVED
			\|-
			\| This function was removed from QETLAB between versions 0.9 and 1.0, being replaced by [[ParallelRepetition]]. The documentation below is for the version 0.9 version of this function, and will be kept as-is in case it can be useful for users of old versions of QETLAB.
			\|}


	<tt>'''NonlocalGameValue'''</tt> is a [[List of functions\|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 [[NPAHierarchy\|NPA hierarchy]]).		<tt>'''NonlocalGameValue'''</tt> is a [[List of functions\|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 [[NPAHierarchy\|NPA hierarchy]]).

Nathaniel: 'classical' method of computation updated

2020-05-29T16:42:51Z

'classical' method of computation updated

← Older revision		Revision as of 16:42, 29 May 2020
Line 162:		Line 162:

	==Notes==		==Notes==
	In practice, <tt>K</tt> probably can't be any larger than 4 when <tt>MTYPE = 'quantum'</tt>, due to memory and time restrictions.		* In practice, <tt>K</tt> probably can't be any larger than 4 when <tt>MTYPE = 'quantum'</tt>, due to memory and time restrictions.
			* When <tt>MTYPE = 'classical'</tt>, the game's value is computed via the algorithm (which is faster than naive brute force) presented in <ref>M. Araújo, F. Hirsch, and M. T. Quintino. Bell nonlocality with a single shot. E-print: [https://arxiv.org/abs/2005.13418 arXiv:2005.13418]</ref>.

	==References==		==References==
	<references />		<references />

Rmmateri at 16:38, 13 June 2018

2018-06-13T16:38:43Z

← Older revision		Revision as of 16:38, 13 June 2018
Line 3:		Line 3:
	\|desc=Computes the maximum value of a two-player non-local game		\|desc=Computes the maximum value of a two-player non-local game
	\|rel=[[BCSGameValue]]<br />[[BellInequalityMax]]<br />[[NPAHierarchy]]<br />[[XORGameValue]]		\|rel=[[BCSGameValue]]<br />[[BellInequalityMax]]<br />[[NPAHierarchy]]<br />[[XORGameValue]]
	\|req=[http://cvxr.com/cvx/ ~~cvx~~]		\|req=[http://cvxr.com/cvx/ CVX]
	\|cat=[[List of functions#Nonlocality_and_Bell_inequalities\|Nonlocality and Bell inequalities]]		\|cat=[[List of functions#Nonlocality_and_Bell_inequalities\|Nonlocality and Bell inequalities]]
	\|upd=March 6, 2015		\|upd=March 6, 2015

Nathaniel: /* Parallel repetition */

2015-07-10T17:31:21Z

Parallel repetition

← Older revision		Revision as of 17:31, 10 July 2015
Line 157:		Line 157:
	0.6667		0.6667
	</syntaxhighlight>		</syntaxhighlight>
	Indeed, the fact that both of these values also equal $2/3$ is a known fact <ref>R. Cleve, W. Slofstra, F. Unger, and S. Upadhyay. ~~Strong~~ parallel repetition theorem for quantum XOR proof systems. E-print: [http://arxiv.org/abs/quant-ph/0608146 arXiv:quant-ph/0608146]</ref>. Note that in the command <tt>NonlocalGameValue(p,V,'classical',1,2)</tt>, the "1" that is provided as the value of <tt>K</tt> does not do anything: it is simply provided as a placeholder so that we can set <tt>REPT = 2</tt> in the next input argument (e.g., we could have just as well entered the command <tt>NonlocalGameValue(p,V,'classical',9873,2)</tt>, and the same calculation would have been carried out).		Indeed, the fact that both of these values also equal $2/3$ is a known fact <ref>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: [http://arxiv.org/abs/quant-ph/0608146 arXiv:quant-ph/0608146]</ref>. Note that in the command <tt>NonlocalGameValue(p,V,'classical',1,2)</tt>, the "1" that is provided as the value of <tt>K</tt> does not do anything: it is simply provided as a placeholder so that we can set <tt>REPT = 2</tt> in the next input argument (e.g., we could have just as well entered the command <tt>NonlocalGameValue(p,V,'classical',9873,2)</tt>, and the same calculation would have been carried out).

	{{SourceCode\|name=NonlocalGameValue}}		{{SourceCode\|name=NonlocalGameValue}}

Nathaniel: /* The Fortnow-Feige-Lovász game */ parallel repetition example

2015-07-10T17:29:48Z

The Fortnow-Feige-Lovász game: parallel repetition example

@@ Line 141: / Line 141: @@
 .6667
 </syntaxhighlight>
 {{SourceCode|name=NonlocalGameValue}}

Nathaniel: /* The Fortnow-Feige-Lovász game */

2015-07-10T16:45:40Z

The Fortnow-Feige-Lovász game

← Older revision		Revision as of 16:45, 10 July 2015
Line 112:		Line 112:
	The Fortnow-Feige-Lovász (FFL) game<ref>U. Feige, L. Lovász, In Proceedings of the 24th ACM STOC, pages 733-744, 1992.</ref><ref>L. Fortnow, PhD thesis, Massachusetts Institute of Technology, Technical Report MIT/LCS/TR-447, May 1989.</ref> 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 Fortnow-Feige-Lovász (FFL) game<ref>U. Feige, L. Lovász, In Proceedings of the 24th ACM STOC, pages 733-744, 1992.</ref><ref>L. Fortnow, PhD thesis, Massachusetts Institute of Technology, Technical Report MIT/LCS/TR-447, May 1989.</ref> 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$ ~~denoted~~ the bitwise OR operation.		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:		It is known that both the classical value and quantum value of this game equal $2/3$, which we can verify as follows:

Nathaniel: /* The Fortnow-Feige-Lovász game */

2015-07-09T17:24:18Z

The Fortnow-Feige-Lovász game

← Older revision		Revision as of 17:24, 9 July 2015
Line 110:		Line 110:

	===The Fortnow-Feige-Lovász game===		===The Fortnow-Feige-Lovász game===
	The Fortnow-Feige-Lovász (FFL) game<ref>U. Feige, L. Lovász, In Proceedings of the 24th ACM STOC, pages 733-744, 1992.</ref><ref>L. Fortnow, PhD thesis, Massachusetts Institute of Technology, Technical Report MIT/LCS/TR-447, May 1989.</ref> is well-known example of a non-local game for which perfect parallel repetition does not hold (i.e., players playing two copies of the game in parallel can do better than they can by playing the games in succession).		The Fortnow-Feige-Lovász (FFL) game<ref>U. Feige, L. Lovász, In Proceedings of the 24th ACM STOC, pages 733-744, 1992.</ref><ref>L. Fortnow, PhD thesis, Massachusetts Institute of Technology, Technical Report MIT/LCS/TR-447, May 1989.</ref> 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$ denoted the bitwise OR operation.		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$ denoted the bitwise OR operation.

Nathaniel: Added FFL game

2015-07-09T17:15:09Z

Added FFL game

← Older revision		Revision as of 17:15, 9 July 2015
Line 107:		Line 107:

	1.0000		1.0000
			</syntaxhighlight>

			===The Fortnow-Feige-Lovász game===
			The Fortnow-Feige-Lovász (FFL) game<ref>U. Feige, L. Lovász, In Proceedings of the 24th ACM STOC, pages 733-744, 1992.</ref><ref>L. Fortnow, PhD thesis, Massachusetts Institute of Technology, Technical Report MIT/LCS/TR-447, May 1989.</ref> is well-known example of a non-local game for which perfect parallel repetition does not hold (i.e., 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$ denoted 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:
			<syntaxhighlight>
			>> 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
	</syntaxhighlight>		</syntaxhighlight>

Nathaniel: source code

2015-06-23T18:44:16Z

source code

← Older revision		Revision as of 18:44, 23 June 2015
Line 2:		Line 2:
	\|name=NonlocalGameValue		\|name=NonlocalGameValue
	\|desc=Computes the maximum value of a two-player non-local game		\|desc=Computes the maximum value of a two-player non-local game
	\|rel=[[BellInequalityMax]]<br />[[NPAHierarchy]]<br />[[XORGameValue]]		\|rel=[[BCSGameValue]]<br />[[BellInequalityMax]]<br />[[NPAHierarchy]]<br />[[XORGameValue]]
	\|req=[http://cvxr.com/cvx/ cvx]		\|req=[http://cvxr.com/cvx/ cvx]
	\|cat=[[List of functions#Nonlocality_and_Bell_inequalities\|Nonlocality and Bell inequalities]]		\|cat=[[List of functions#Nonlocality_and_Bell_inequalities\|Nonlocality and Bell inequalities]]
Line 108:		Line 108:
	1.0000		1.0000
	</syntaxhighlight>		</syntaxhighlight>

			{{SourceCode\|name=NonlocalGameValue}}

	==Notes==		==Notes==

Nathaniel at 19:14, 22 June 2015

2015-06-22T19:14:01Z

← Older revision		Revision as of 19:14, 22 June 2015
Line 110:		Line 110:

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

	==References==		==References==
	<references />		<references />