Published by the Department of Computer Science, The University of Chicago.
Department de Física: Grup d'Informaciò Quántica
Universitat Autònoma de Barcelona
08193 Bellaterra, Barcelona, Spain
Insitució Catalana de Recerca i Estudis Avançats
Pg. Lluís Companys, 23, 08010 Barcelona, Spain
andreas.winter AT uab DOT cat
We use a recently discovered constrained de Finetti reduction (aka “Post-Selection Lemma”) to study the parallel repetition of multi-player non-local games under no-signalling strategies. Since the technique allows us to reduce general strategies to independent plays, we obtain parallel repetition (corresponding to winning all rounds) in the same way as exponential concentration of the probability to win a fraction larger than the value of the game. Our proof technique leads us naturally to a relaxation of no-signalling (NS) strategies, which we dub sub-no-signalling (SNOS). While for two players the two concepts coincide, they differ for three or more players. Our results are most complete and satisfying for arbitrary number of sub-no-signalling players, where we get universal parallel repetition and concentration for any game, while the no-signalling case is obtained as a corollary, but only for games with “full support”.
Submitted August 4, 2015, revised July 18, 2016, and in final form August 16, 2016, published August 18, 2016.