A Caltech Library Service

A parallel repetition theorem for entangled projection games

Dinur, Irit and Steurer, David and Vidick, Thomas (2014) A parallel repetition theorem for entangled projection games. In: Proceedings of the Annual IEEE Conference on Computational Complexity. IEEE , Piscataway, NJ, pp. 197-208. ISBN 978-1-4799-3626-7.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We study the behavior of the entangled value of two-player one-round projection games under parallel repetition. We show that for any projection game G of entangled value 1 - ε <; 1, the value of the k-fold repetition of G goes to zero as O((1 - ε^c)^k), for some universal constant c ≥ 1. Previously parallel repetition with an exponential decay in k was only known for the case of XOR and unique games. To prove the theorem we extend an analytical framework recently introduced by Dinur and Steurer for the study of the classical value of projection games under parallel repetition. Our proof, as theirs, relies on the introduction of a simple relaxation of the entangled value that is perfectly multiplicative. The main technical component of the proof consists in showing that the relaxed value remains tightly connected to the entangled value, thereby establishing the parallel repetition theorem. More generally, we obtain results on the behavior of the entangled value under products of arbitrary (not necessarily identical) projection games. Relating our relaxed value to the entangled value is done by giving an algorithm for converting a relaxed variant of quantum strategies that we call “vector quantum strategy” to a quantum strategy. The algorithm is considerably simpler in case the bipartite distribution of questions in the game has good expansion properties. When this is not the case, rounding relies on a quantum analogue of Holenstein's correlated sampling lemma which may be of independent interest. Our “quantum correlated sampling lemma” generalizes results of van Dam and Hayden on universal embezzlement to the following approximate scenario: two isolated parties, given classical descriptions of arbitrary bipartite states |ψ〉, |φ〉 respectively such that |ψ〉 ≈ |φ〉, are able to locally generate a joint entangled state|- Ψ〉 ≈ |ψ〉 ≈ |φ〉 using an initial entangled state that is independent of their inputs.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ItemJournal Article Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2014 IEEE. We thank Attila Pereszlényi for comments on an earlier version of this manuscript. Irit Dinur’s research was supported by ERC grant number 239985. Thomas Vidick was partially supported by the Ministry of Education, Singapore under the Tier 3 grant MOE2012-T3-1-009. Part of the work was done while the first author was visiting MIT supported by NSF Contract CCF-1018064, and by Simons Investigator Award of Shafi Goldwasser; the second author was at Microsoft Research New England and the third author at the Newton Institute in Cambrdige, UK.
Funding AgencyGrant Number
European Research Council (ERC)239985
Ministry of Education (Singapore)MOE2012-T3-1-009
Simons FoundationUNSPECIFIED
Subject Keywords:parallel repetition; multiplayer games; entangled games; projection games
Record Number:CaltechAUTHORS:20140910-132001940
Persistent URL:
Official Citation:Dinur, I; Steurer, D.; Vidick, T., "A Parallel Repetition Theorem for Entangled Projection Games," Computational Complexity (CCC), 2014 IEEE 29th Conference on , vol., no., pp.197,208, 11-13 June 2014 doi: 10.1109/CCC.2014.28
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49549
Deposited By: Ruth Sustaita
Deposited On:10 Sep 2014 21:55
Last Modified:10 Nov 2021 18:45

Repository Staff Only: item control page