Document Open Access Logo

A Parallel Repetition Theorem for All Entangled Games

Author Henry Yuen

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.77.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

Henry Yuen

Cite As Get BibTex

Henry Yuen. A Parallel Repetition Theorem for All Entangled Games. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 77:1-77:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.77

Abstract

The behavior of games repeated in parallel, when played with quantumly entangled players, has received much attention in recent years. Quantum analogues of Raz's classical parallel repetition theorem have been proved for many special classes of games. However, for general entangled games no parallel repetition theorem was known.

We prove that the entangled value of a two-player game G repeated n times in parallel is at most c_G*n^{-1/4}*log(n) for a constant c_G depending on G, provided that the entangled value of G is less than 1. In particular, this gives the first proof that the entangled value of a parallel repeated game must converge to 0 for all games whose entangled value is less than 1. Central to our proof is a combination of both classical and quantum correlated sampling.

Subject Classification

Keywords
  • parallel repetition
  • direct product theorems
  • entangled games
  • quantum games

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Mohammad Bavarian, Thomas Vidick, and Henry Yuen. Anchoring games for parallel repetition. arXiv preprint arXiv:1509.07466, 2015. Google Scholar
  2. Mohammad Bavarian, Thomas Vidick, and Henry Yuen. Parallel repetition via fortification: analytic view and the quantum case. arXiv preprint arXiv:1603.05349, 2016. Google Scholar
  3. John S Bell. On the Einstein-Podolsky-Rosen paradox. Physics, 1(3), 1964. Google Scholar
  4. Mark Braverman and Ankit Garg. Small value parallel repetition for general games. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), 2015. Google Scholar
  5. Mark Braverman, Anup Rao, Omri Weinstein, and Amir Yehudayoff. Direct products in communication complexity. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 746-755. IEEE, 2013. Google Scholar
  6. André Chailloux and Giannicola Scarpa. Parallel repetition of entangled games with exponential decay via the superposed information cost. In Automata, Languages, and Programming, pages 296-307. Springer, 2014. Google Scholar
  7. Kai-Min Chung, Xiaodi Wu, and Henry Yuen. Parallel repetition for entangled k-player games via fast quantum search. In the 30th Conference on Computational Complexity (CCC), pages 512-536, 2015. Google Scholar
  8. Richard Cleve, William Slofstra, Falk Unger, and Sarvagya Upadhyay. Perfect parallel repetition theorem for quantum xor proof systems. Computational Complexity, 17(2):282-299, 2008. Google Scholar
  9. Irit Dinur, David Steurer, and Thomas Vidick. A parallel repetition theorem for entangled projection games. In the 29th Conference on Computational Complexity (CCC), pages 197-208, 2014. Google Scholar
  10. Uriel Feige and Joe Kilian. Two-prover protocols - low error at affordable rates. SIAM Journal on Computing, 30(1):324-346, 2000. Google Scholar
  11. Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4), 2001. Google Scholar
  12. Thomas Holenstein. Parallel repetition: Simplification and the no-signaling case. Theory of Computing, 5(8):141-172, 2009. URL: http://dx.doi.org/10.4086/toc.2009.v005a008.
  13. Rahul Jain. New strong direct product results in communication complexity. Electronic Colloquium on Computational Complexity (ECCC), 18(24):2, 2011. Google Scholar
  14. Rahul Jain, Attila Pereszlényi, and Penghui Yao. A parallel repetition theorem for entangled two-player one-round games under product distributions. In Proceedings of 29th Conference on Computational Complexity (CCC), pages 209-216, 2014. Google Scholar
  15. Julia Kempe, Oded Regev, and Ben Toner. Unique games with entangled provers are easy. In Proceedings of Foundations of Computer Science (FOCS), 2008. Google Scholar
  16. Julia Kempe and Thomas Vidick. Parallel repetition of entangled games. In Proceedings of the forty-third annual ACM symposium on Theory of computing (STOC), pages 353-362, 2011. Google Scholar
  17. Dana Moshkovitz. Parallel repetition from fortification. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 414-423. IEEE, 2014. Google Scholar
  18. Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge university press, 2010. Google Scholar
  19. Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763-803, 1998. Google Scholar
  20. Wim van Dam and Patrick Hayden. Universal entanglement transformations without communication. Physical Review A, 67(6):060302, 2003. Google Scholar
  21. Mark M Wilde. Quantum information theory. Cambridge University Press, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact