ParallelRepetition

From QETLAB
Jump to navigation Jump to search
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[1]. 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[2][3] 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$:[4].

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

References

  1. 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). arXiv:quant-ph/0205016
  2. U. Feige, L. Lovász, In Proceedings of the 24th ACM STOC, pages 733-744, 1992.
  3. L. Fortnow, PhD thesis, Massachusetts Institute of Technology, Technical Report MIT/LCS/TR-447, May 1989.
  4. 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: arXiv:quant-ph/0608146