Generalized XOR games with d outcomes and the task of nonlocal computation

Abstract

© 2016 American Physical Society. Two-party xor games (correlation Bell inequalities with two outcomes per party) are the most studied Bell inequalities, and one of the few classes for which the optimal quantum value is known to be exactly calculable. We study a natural generalization of the binary xor games to the class of linear games with d>2 outcomes, and propose an easily computable bound on the quantum value of these games. Many interesting properties such as the impossibility of a quantum strategy to win these games, and the quantum bound on the CHSH game generalized to d outcomes are derived. We also use the proposed bound to prove a large-alphabet generalization of the principle of no quantum advantage in nonlocal computation, showing that quantum theory provides no advantage in the task of nonlocal distributed computation of a class of functions with d outcomes for prime d, while general no-signaling boxes do. This task is one of the information-theoretic principles attempting to characterize the set of quantum correlations from amongst general no-signaling ones.