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[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
- ↑ 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
- ↑ U. Feige, L. Lovász, In Proceedings of the 24th ACM STOC, pages 733-744, 1992.
- ↑ L. Fortnow, PhD thesis, Massachusetts Institute of Technology, Technical Report MIT/LCS/TR-447, May 1989.
- ↑ 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