Araujoms: created page to document new

2022-11-11T12:39:14Z

created page to document new

New page

{{Function
|name=ParallelRepetition
|desc=Computes coefficients of parallel repetition of a nonlocal game
|rel=[[BCSGameValue]]<br />[[BellInequalityMax]]<br />[[NPAHierarchy]]<br />[[XORGameValue]]
|req=[http://cvxr.com/cvx/ CVX]
|cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]
|upd=March 6, 2015
|cvx=no}}

<tt>'''ParallelRepetition'''</tt> is a [[List of functions|function]] that generates the coefficients of the parallel repetition of a nonlocal game, a concept widely used in computer science.

==Syntax==
* <tt>NGVAL = NonlocalGameValue(G,REPT)</tt>

==Argument descriptions==
* <tt>G</tt>: A 4-D array whose $(a,b,x,y)$-entry gives the coefficient needed to compute the probability of winning the nonlocal game. It is defined as <math>G(a,b,x,y) = \mu(x,y)V(a,b,x,y)</math>, where <math>\mu(x,y)</math> is the probability that the referee asks Alice question $x$ and Bob question $y$, and V(a,b,x,y) is the probability Alice and Bob win the game if they reply with answers $(a,b)$ to questions $(x,y)$.
* <tt>REPT</tt>: A positive integer indicating the number of parallel copies of the nonlocal game.

==Examples==
===The CHSH game===
A well-known result is that the parallel repetition of the CHSH game has local bound higher then the product of the local bounds<ref>J. Barrett, D. Collins, L. Hardy, A. Kent and S. Popescu. ‘Quantum nonlocality, Bell inequalities, and the memory loophole’. Physical Review A 66 042111 (2002). [http://arxiv.org/abs/quant-ph/0205016 arXiv:quant-ph/0205016]</ref>. We can do 2 parallel repetitions:
<syntaxhighlight>
>> G = chshd(2);
>> G2 = ParallelRepetition(G,2);
>> desc = size(G2);
>> BellInequalityMax(G2,desc,'fp','classical')

ans =

0.6250

</syntaxhighlight>
We see that the local bound is 10/16, which is larger than <math>(3/4)^2</math>. We can also do 3 parallel repetitions:
<syntaxhighlight>
>> G = chshd(2);
>> G3 = ParallelRepetition(G,3);
>> desc = size(G3);
>> BellInequalityMax(G3,desc,'fp','classical')
Starting parallel pool (parpool) using the 'local' profile ...
connected to 2 workers.

ans =

0.4844

</syntaxhighlight>
We see that the local bound is 31/64, which is larger than <math>(3/4)^3</math>. The code cannot handle 4 or more parallel repetitions.

===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., 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:
<syntaxhighlight>
>> G = ffl();
>> desc = size(G);
>> BellInequalityMax(G,desc,'fp','classical')

ans =

0.6667

>> BellInequalityMax(G,desc,'fp','quantum',2)

ans =

0.6667

</syntaxhighlight>

The FFL game is interesting because the classical value of two parallel repetitions is still $2/3$:<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>.
<syntaxhighlight>
>> G = ffl();
>> G2 = ParallelRepetition(G,2);
>> desc = size(G2);
>> BellInequalityMax(G2,desc,'fp','classical')

ans =

0.6667

</syntaxhighlight>
We can also compute the classical value of three parallel repetitions, which decreases to $14/27$:
<syntaxhighlight>
>> G = ffl();
>> G3 = ParallelRepetition(G,3);
>> desc = size(G3);
>> BellInequalityMax(G3,desc,'fp','classical')

ans =

0.5185

</syntaxhighlight>

{{SourceCode|name=ParallelRepetition}}

==Notes==
* The algorithm for computing the classical value is parallelized, which leads to much faster performance on computers with multiple CPUs. Nevertheless, the complexity is still superexponential in <tt>REPT</tt>, making 4 or more parallel repetitions intractable.
==References==
<references />

ParallelRepetition - Revision history

Araujoms: created page to document new