Generalized XOR games with $d$ outcomes and the task of non-local computation

Abstract

A natural generalization of the binary XOR games to the class of XOR-d games with $d>2$ outcomes is studied. We propose an algebraic bound to the quantum value of these games and use it to derive several interesting properties of these games. As an example, we re-derive in a simple manner a recently discovered bound on the quantum value of the CHSH-d game for prime $d$. It is shown that no total function XOR-d game with uniform inputs can be a pseudo-telepathy game, there exists a quantum strategy to win the game only when there is a classical strategy also. We then study the principle of lack of quantum advantage in the distributed non-local computation of binary functions which is a well-known information-theoretic principle designed to pick out quantum correlations from amongst general no-signaling ones. We prove a large-alphabet generalization of this principle, showing that quantum theory provides no advantage in the task of non-local distributed computation of a restricted class of functions with $d$ outcomes for prime $d$, while general no-signaling boxes do. Finally, we consider the question whether there exist two-party tight Bell inequalities with no quantum advantage, and show that the binary non-local computation game inequalities for the restricted class of functions are not facet defining for any number of inputs.

10 pages

References in corpus (9)

• Device-independent security of quantum cryptography against collective attacks
• A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
• Private Randomness Expansion With Untrusted Devices
• Efficient Toffoli Gates Using Qudits
• Almost quantum correlations
• Multi-setting Bell inequality for qudits
• Maximum nonlocality and minimum uncertainty using magic states
• Quantum bounds on multiplayer linear games and device-independent witness of genuine tripartite entanglement
• Linear game non-contextuality and Bell inequalities - a graph-theoretic approach

Cited by in corpus (10)

• Trade-offs in multi-party Bell inequality violations in qubit networks
• On the tightness of correlation inequalities with no quantum violation
• Measurement uncertainty from no-signaling and non-locality
• Information causality as a tool for bounding the set of quantum correlations
• Quantum Strategies for Rendezvous and Domination Tasks on Graphs with Mobile Agents
• All two-party facet Bell inequalities are violated by Almost Quantum correlations
• Tight bound on the classical value of generalized Clauser-Horne-Shimony-Holt games
• Quantum bounds for compiled XOR games and $d$-outcome CHSH games
• Constructive nonlocal games with very small classical values
• Generalized XOR non-locality games with graph description on a square lattice