Anchored Parallel Repetition for Nonlocal Games

Abstract

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.