# ParallelRepetition

 Other toolboxes required ParallelRepetition Computes coefficients of parallel repetition of a nonlocal game CVX BCSGameValueBellInequalityMaxNPAHierarchyXORGameValue Nonlocality and Bell inequalities 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