Chicago Journal of Theoretical Computer Science

Volume 2018

Article 4

Published by the Department of Computer Science, The University of Chicago.

Extended Nonlocal Games from Quantum-Classical Games

Vincent Russo
ISARA Corporation
Waterloo ONT
vincentrusso1 AT gmail DOT com


John Watrous
School of Computer Science
University of Waterloo
Waterloo, ONT
watrous AT uwaterloo DOT ca

August 7, 2018


Several variants of nonlocal games have been considered in the study of quantum entanglement and nonlocality. This paper concerns two of these variants, called quantum-classical games and extended nonlocal games. We give a construction of an extended nonlocal game from any quantum-classical game that allows one to translate certain facts concerning quantum-classical games to extended nonlocal games. In particular, based on work of Regev and Vidick, we conclude that there exist extended nonlocal games for which no finite-dimensional entangled strategy can be optimal. While this conclusion is a direct consequence of recent work of Slofstra, who proved a stronger, analogous result for ordinary (non-extended) nonlocal games, the proof based on our construction is considerably simpler, and the construction itself might potentially have other applications in the study of entanglement and nonlocality.

Submitted October 21, 2017, revised July 31, 2018, published August 7, 2018.

DOI: 10.4086/cjtcs.2018.004

[] Volume 2018, Article 3 [] Article 5
[back] Volume 2018 [back] Published articles
[CJCTS home]