CaltechAUTHORS
  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 . http://resolver.caltech.edu/CaltechAUTHORS:20170710-152910604

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

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20170710-152910604

Abstract

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
https://doi.org/10.1145/3055399.3055433DOIArticle
https://dl.acm.org/citation.cfm?doid=3055399.3055433PublisherArticle
ORCID:
AuthorORCID
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, IQIM
Funders:
Funding AgencyGrant Number
NSFCCF-0939370
NSFCCF-1420956
NSFCCF-1553477
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
NSFPHY-1125565
Gordon and Betty Moore FoundationGBMF-12500028
Simons Foundation360893
NSF Graduate Research FellowshipDGE-1122374
NSF1218547
Subject Keywords:Theory of computation → Quantum complexity theory, Entangled games, parallel repetition, hardness amplification
Record Number:CaltechAUTHORS:20170710-152910604
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20170710-152910604
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: https://doi.org/10.1145/3055399.3055433
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:78913
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:10 Jul 2017 22:45
Last Modified:10 Jul 2017 22:45

Repository Staff Only: item control page