Volume 2016
Article 5
Published by the Department of Computer Science, The University of Chicago.
On deciding the existence of perfect entangled strategies for nonlocal games
Laura Mančinska
University of Bristol
Bristol, UK;
laura AT locc DOT la
David E. Roberson
University College London
London, UK;
davidroberson AT gmail DOT com
Antonios Varvisotis
Nanyang Technological University
Singapore
and
Centre for Quantum Technologies
Singapore
avarvits AT gmail DOT com
April 28, 2016
Abstract
First, we consider the problem of deciding whether a nonlocal game admits a
perfect {finite dimensional} entangled strategy that uses projective measurements
on a maximally entangled shared state. Via a polynomial-time Karp reduction,
we show
that independent set games are the hardest instances of this problem. Secondly, we
show that if every independent set game whose entangled value is equal to one
admits a perfect entangled strategy, then the same holds for all symmetric
synchronous games. Finally, we identify combinatorial lower bounds on the
classical and entangled values of synchronous games in terms of variants of the
independence number of appropriate graphs. Our results suggest that independent set
games might be representative of all nonlocal games when dealing with questions
concerning perfect entangled strategies.
- The article: PDF (284 KB)
- Source material: ZIP (70 KB)
- BibTeX entry for this
article (334 bytes)
Submitted September 4, 2015, revised December 22, 2015 and April 12, 2016, published April 28, 2016.
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/up.gif)
Volume 2016, Article 4
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/down.gif)
Article 6
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
Volume 2016
Published articles
![[CJCTS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif)
Licensed under a Creative Commons Attribution License