Generalized XOR games with outcomes and the task of non-local computation
arXiv:1502.02974 · doi:10.1103/PhysRevA.93.022333
Abstract
A natural generalization of the binary XOR games to the class of XOR-d games with 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 . 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 outcomes for prime , 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.
arXiv comment10 pages
References in corpus (23)
- Device-independent security of quantum cryptography against collective attacks
- Random Numbers Certified by Bell's Theorem
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- Non-locality and Communication Complexity
- A limit on nonlocality in any world in which communication complexity is not trivial
- Private Randomness Expansion With Untrusted Devices
- Efficient Toffoli Gates Using Qudits
- Device-independent witnesses of genuine multipartite entanglement
- Almost quantum correlations
- Guess your neighbour's input: a multipartite non-local game with no quantum advantage
- No quantum advantage for nonlocal computation
- Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities
- Quantum Pseudo-Telepathy
- Quantum key distribution session with 16-dimensional photonic states
- Weak randomness in device independent quantum key distribution and the advantage of using high dimensional entanglement
- Causality and Cirel'son bounds
- Reexamination of a multisetting Bell inequality for qudits
- Practical relativistic bit commitment
- Multi-setting Bell inequality for qudits
- Tight Bell inequalities with no quantum violation from qubit unextendible product bases
- 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 (11)
- No quantum realization of extremal no-signaling boxes
- 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 -outcome CHSH games
- Constructive nonlocal games with very small classical values
- Generalized XOR non-locality games with graph description on a square lattice