A Caltech Library Service

Anchored Parallel Repetition for Nonlocal Games

Bavarian, Mohammad and Vidick, Thomas and Yuen, Henry (2022) Anchored Parallel Repetition for Nonlocal Games. SIAM Journal on Computing, 51 (2). pp. 214-253. ISSN 0097-5397. doi:10.1137/21m1405927.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We introduce a simple transformation on two-player nonlocal games, called “anchoring,” and prove an exponential-decay parallel repetition theorem for all anchored games in the setting of quantum entangled players. This transformation is inspired in part by the Feige--Kilian transformation [SIAM J. Comput., 30 (2000), pp. 324--346], and has the property that if the quantum value of the original game G is v, then the quantum value of the anchored game G⊥ is 1−(1−α)²⋅(1−v), where α is a parameter of the transformation. In particular the anchored game has quantum value 1 if and only if the original game G has quantum value 1. This provides the first gap amplification technique for general two-player nonlocal games that achieves exponential decay of the quantum value.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemDiscussion Paper
Vidick, Thomas0000-0002-6405-365X
Yuen, Henry0000-0002-2684-1129
Alternate Title:Anchoring games for parallel repetition
Additional Information:Funding: The second author is supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award FA9550-16-1-0495, MURI Grant FA9550-18-1-0161, and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). The third author is supported by an NSERC Discovery Grant, a Google Research Award, and AFOSR award FA9550-21-1-0040. We thank anonymous referees from STOC and SICOMP for their helpful feedback. We thank Ashutosh Satyajit Marwah for catching some minor errors in a previous draft.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0161
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Google Faculty Research AwardUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-21-1-0040
Issue or Number:2
Record Number:CaltechAUTHORS:20221011-459044000.22
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:117333
Deposited By: Donna Wrublewski
Deposited On:12 Oct 2022 14:23
Last Modified:12 Oct 2022 14:23

Repository Staff Only: item control page