A Caltech Library Service

Hardness amplification for entangled games via anchoring

Bavarian, Mohammad and Vidick, Thomas and Yuen, Henry (2017) Hardness amplification for entangled games via anchoring. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2017. ACM , New York, NY, pp. 303-316. ISBN 978-1-4503-4528-6.

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

Use this Persistent URL to link to this item:


We study the parallel repetition of one-round games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate - in other words, does an analogue of Raz's parallel repetition theorem hold for games with players sharing quantum entanglement? Previous results only apply to special classes of games. We introduce a class of games we call anchored. We then introduce a simple transformation on games called anchoring, inspired in part by the Feige-Kilian transformation, that turns any (multiplayer) game into an anchored game. Unlike the Feige-Kilian transformation, our anchoring transformation is completeness preserving. We prove an exponential-decay parallel repetition theorem for anchored games that involve any number of entangled players. We also prove a threshold version of our parallel repetition theorem for anchored games. Together, our parallel repetition theorems and anchoring transformation provide the first hardness amplification techniques for general entangled games. We give an application to the games version of the Quantum PCP Conjecture.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2017 ACM. We thank Mark Braverman and Ankit Garg for useful discussions. MB was supported by NSF under CCF-0939370 and CCF-1420956. TV was supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award number FA9550-16-1-0495, and the IQIM, an NSF Physics Frontiers Center (NFS Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). HY was supported by Simons Foundation grant #360893, and National Science Foundation Grants 1122374 and 1218547.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Gordon and Betty Moore FoundationGBMF-12500028
Simons Foundation360893
NSF Graduate Research FellowshipDGE-1122374
Subject Keywords:Theory of computation → Quantum complexity theory, Entangled games, parallel repetition, hardness amplification
Record Number:CaltechAUTHORS:20170710-152910604
Persistent URL:
Official Citation:Mohammad Bavarian, Thomas Vidick, and Henry Yuen. 2017. Hardness amplification for entangled games via anchoring. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017). ACM, New York, NY, USA, 303-316. DOI:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:78913
Deposited On:10 Jul 2017 22:45
Last Modified:15 Nov 2021 17:44

Repository Staff Only: item control page