Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Hardness amplification for entangled games via anchoring
 
conference paper

Hardness amplification for entangled games via anchoring

Bavarian, Mohammad
•
Vidick, Thomas  orcid-logo
•
Yuen, Henry
McKenzie, Pierre
•
King, Valerie
Show more
June 19, 2017
Proceedings of the Annual ACM Symposium on Theory of Computing
49 ACM SIGACT Symposium on Theory of Computing

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.

  • Details
  • Metrics
Type
conference paper
DOI
10.1145/3055399.3055433
Scopus ID

2-s2.0-85024397567

Author(s)
Bavarian, Mohammad

Massachusetts Institute of Technology

Vidick, Thomas  orcid-logo
Yuen, Henry

University of California, Berkeley

Editors
McKenzie, Pierre
•
King, Valerie
•
Hatami, Hamed
Date Issued

2017-06-19

Publisher

Association for Computing Machineryacmhelp@acm.org

Publisher place

New York, NY, USA

Published in
Proceedings of the Annual ACM Symposium on Theory of Computing
ISBN of the book

9781450345286

Book part number

Part F128415

Start page

303

End page

316

Subjects

Entangled games

•

Hardness amplification

•

Parallel repetition

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
Non-EPFL  
Event nameEvent acronymEvent placeEvent date
49 ACM SIGACT Symposium on Theory of Computing

Montreal, Canada

2017-06-19 - 2017-06-23

FunderFunding(s)Grant NumberGrant URL

NFS

PHY-1125565

NSF Physics Frontiers Center

NSF

1122374,1218547,1650733,CCF-0939370,CCF-1420956,CCF-1553477

Show more
Available on Infoscience
November 18, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/255975
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés