ParallelRepetition

ParallelRepetition
Computes coefficients of parallel repetition of a nonlocal game
Other toolboxes required	CVX
Related functions	BCSGameValue BellInequalityMax NPAHierarchy XORGameValue
Function category	Nonlocality and Bell inequalities
Usable within CVX?	no

ParallelRepetition is a function that generates the coefficients of the parallel repetition of a nonlocal game, a concept widely used in computer science.

Syntax

• NGVAL = NonlocalGameValue(G,REPT)

Argument descriptions

• G: 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 \(G(a,b,x,y) = \mu(x,y)V(a,b,x,y)\), where \(\mu(x,y)\) 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)$.
• REPT: 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. We can do 2 parallel repetitions:

>> G = chshd(2);                
>> G2 = ParallelRepetition(G,2);
>> desc = size(G2);
>> BellInequalityMax(G2,desc,'fp','classical')

ans =

    0.6250

We see that the local bound is 10/16, which is larger than \((3/4)^2\). We can also do 3 parallel repetitions:

>> 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

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

The Fortnow-Feige-Lovász game

The Fortnow-Feige-Lovász (FFL) game 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:

>> G = ffl();                   
>> desc = size(G);
>> BellInequalityMax(G,desc,'fp','classical') 

ans =

    0.6667

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

ans =

    0.6667

The FFL game is interesting because the classical value of two parallel repetitions is still $2/3$:.

>> G = ffl();                   
>> G2 = ParallelRepetition(G,2);
>> desc = size(G2);
>> BellInequalityMax(G2,desc,'fp','classical')         

ans =

    0.6667

We can also compute the classical value of three parallel repetitions, which decreases to $14/27$:

>> G = ffl();                   
>> G3 = ParallelRepetition(G,3);
>> desc = size(G3);
>> BellInequalityMax(G3,desc,'fp','classical')

ans =

    0.5185

Source code

Click here to view this function's source code on github.

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 REPT, making 4 or more parallel repetitions intractable.