2015/09/24 by Mohammad Bavarian, Thomas Vidick, Bavarian, Mohammad +3
Mathematics · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Mathematical Dynamics and Fractals #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1509.07466
openalex publication_date 2015/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (SICOMP 2000), 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_\bot is 1 - (1 - α)2 ⋅ (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.