Chicago Journal of Theoretical Computer Science

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
Centre for Quantum Technologies
avarvits AT gmail DOT com

April 28, 2016


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.

Submitted September 4, 2015, revised December 22, 2015 and April 12, 2016, published April 28, 2016.

DOI: 10.4086/cjtcs.2016.005

[] Volume 2016, Article 4 [] Article 6
[back] Volume 2016 [back] Published articles
[CJCTS home]