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. Journal articles
  4. Anchored Parallel Repetition for Nonlocal Games
 
research article

Anchored Parallel Repetition for Nonlocal Games

Bavarian, Mohammad
•
Vidick, Thomas  orcid-logo
•
Yuen, Henry
2022
SIAM Journal on Computing

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 - α)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.

  • Details
  • Metrics
Type
research article
DOI
10.1137/21M1405927
Scopus ID

2-s2.0-85129461935

Author(s)
Bavarian, Mohammad

Massachusetts Institute of Technology

Vidick, Thomas  orcid-logo

California Institute of Technology

Yuen, Henry

The Fu Foundation School of Engineering and Applied Science

Date Issued

2022

Published in
SIAM Journal on Computing
Volume

51

Issue

2

Start page

214

End page

253

Subjects

gap amplification

•

hardness amplification

•

nonlocal games

•

parallel repetition

•

quantum complexity theory

•

quantum information

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
Non-EPFL  
FunderFunding(s)Grant NumberGrant URL

NSERC

AFOSR

FA9550-16-1-0495

Gordon and Betty Moore Foundation

GBMF-12500028

Show more
Available on Infoscience
November 13, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/255835
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