Report

Random non-local games Andris Ambainis, Artūrs Bačkurs, Kaspars Balodis, Dmitry Kravchenko, Juris Smotrovs, Madars Virza University of Latvia Non-local games Alice a x Bob b Referee y Referee asks questions a, b to Alice, Bob; Alice and Bob reply by sending x, y; Alice, Bob win if a condition Pa, b(x, y) satisfied. Example 1 [CHSH] Alice a x Bob b Referee y Winning conditions for Alice and Bob (a = 0 or b = 0) x = y. (a = b = 1) x y. Example 2 [Cleve et al., 04] Alice and Bob attempt to “prove” that they have a 2-coloring of a 5-cycle; Referee may ask one question about color of some vertex to each of them. Example 2 Referee either: asks ith vertex to both Alice and Bob; they win if answers equal. Asks the ith vertex to Alice, (i+1)st to Bob, they win if answers different. Non-local games in quantum world Alice Bob Shared quantum state between Alice and Bob: Does not allow them to communicate; Allows to generate correlated random bits. Corresponds to shared random bits in the classical case. Example:CHSH game Alice a x Bob b Referee y Winning condition: Winning probability: (a = 0 or b = 0) x = y. 0.75 classically. 0.85... quantumly. (a = b = 1) x y. A simple way to verify quantum mechanics. Example: 2-coloring game Alice and Bob claim to have a 2-coloring of ncycle, n- odd; 2n pairs of questions by referee. Winning probability: classically. quantumly. Random non-local games Alice a x Bob b Referee y a, b {1, 2, ..., N}; x, y {0, 1}; Condition P(a, b, x, y) – random; Computer experiments: quantum winning probability larger than classical. XOR games For each (a, b), exactly one of x = y and x y is winning outcome for Alice and Bob. The main results Let N be the number of possible questions to Alice and Bob. Classical winning probability pcl satisfies Quantum winning probability pq satisfies Another interpretation Value of the game = pwin – (1-pwin). Quantum advantage: Corresponds to Bell inequality violation Related work Randomized constructions of non-local games/Bell inequalities with large quantum advantage. Junge, Palazuelos, 2010: N questions, N answers, √N/log N advantage. Regev, 2011: √N advantage. Briet, Vidick, 2011: large advantage for XOR games with 3 players. Differences JP10, R10, BV11: Goal: maximize quantum-classical gap; Randomized constructions = tool to achieve this goal; This work: Goal: understand the power of quantum strategies in random games; Methods: quantum Tsirelson’s theorem, 1980: Alice’s strategy - vectors u1, ..., uN, ||u1|| = ... = ||uN|| = 1. Bob’s strategy - vectors v1, ..., vN, ||v1|| = ... = ||vN|| = 1. Quantum advantage Random matrix question What is the value of for a random 1 matrix A? Can be upper-bounded using ||A||=(2+o(1)) √N Upper bound = Upper bound theorem Theorem For a random A, Corollary The advantage achievable by a quantum strategy in a random XOR game is at most Lower bound There exists u: There are many such u: a subspace of dimension f(n), for any f(n)=o(n). Combine them to produce ui, vj: Marčenko-Pastur law Let A – random N·N 1 matrix. W.h.p., all singular values are between 0 and (2o(1)) √N. Theorem (Marčenko, Pastur, 1967) W.h.p., the fraction of singular values i c √N is Modified Marčenko-Pastur law Let e1, e2, ..., eN be the standard basis. Theorem With probability 1-O(1/N), the projection of ei to the subspace spanned by singular values j c √N is Classical results Let N be the number of possible questions to Alice and Bob. Theorem Classical winning probability pcl satisfies Methods: classical Alice’s strategy - numbers u1, ..., uN {-1, 1}. Bob’s strategy - numbers v1, ..., vN {-1, 1}. Classical advantage Classical upper bound Chernoff bounds + union bound: with probability 1-o(1). Classical lower bound Random 1 matrix A; Operations: flip signs in all entries in one column or row; Goal: maximize the sum of entries. Greedy strategy Choose u1, ..., uN one by one. 1 -1 ... ... 1 1 -1 ... -1 ... 1 ... ... ... -1 2 0 -2 ... -1 1 1 ... 1 1 -1 -1 ... -1 k-1 rows that are already chosen 0 Choose the option which maximizes agreements of signs Analysis 2 0 -2 ... 0 -1 1 1 ... 1 1 -1 -1 ... -1 Choose the option which maximizes agreements of signs On average, the best option agrees with fraction of signs. If the column sum is 0, it always increases. Rigorous proof 2 0 -2 ... 0 -1 1 1 ... 1 1 -1 -1 ... -1 Choose the option which maximizes agreements of signs Consider each column separately. Sum of values performs a biased random walk, moving away from 0 with probability in each step. Expected distance from origin = 1.27... √N. Conclusion We studied random XOR games with n questions to Alice and Bob. For both quantum and classical strategies, the best winning probability ½. Quantumly: Classically: Comparison Random XOR game: Biggest gap for XOR games: Open problems 1. 2. 3. We have What is the exact order? Gaussian Aij? Different probability distributions? Random games for other classes of non-local games?