Characterising the Performance of XOR Games and the Shannon Capacity of Graphs
arXiv:1406.0995 · doi:10.1103/PhysRevLett.113.240401
Abstract
In this paper we give a set of necessary and sufficient conditions such that quantum players of a two-party {\sc xor} game cannot perform any better than classical players. With any such game, we associate a graph and examine its zero-error communication capacity. This allows us to specify a broad new class of graphs for which the Shannon capacity can be calculated. The conditions also enable the parametrisation of new families of games which have no quantum advantage, for arbitrary input probability distributions up to certain symmetries. In the future, these might be used in information-theoretic studies on reproducing the set of quantum non-local correlations.
arXiv comment5 pages. Clarified proof of theorem 1, typos corrected
References in corpus (11)
- Random Numbers Certified by Bell's Theorem
- Information Causality as a Physical Principle
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- A limit on nonlocality in any world in which communication complexity is not trivial
- Graph-Theoretic Approach to Quantum Correlations
- A glance beyond the quantum model
- Local orthogonality as a multipartite principle for quantum correlations
- No quantum advantage for nonlocal computation
- Simple explanation of the quantum violation of a fundamental inequality
- Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities
- Basic exclusivity graphs in quantum correlations
Cited by in corpus (7)
- Quantum bounds on multiplayer linear games and device-independent witness of genuine tripartite entanglement
- All tight correlation Bell inequalities have quantum violations
- On the tightness of correlation inequalities with no quantum violation
- All two-party facet Bell inequalities are violated by Almost Quantum correlations
- Local hidden variable values without optimization procedures
- (Almost-)Quantum Bell Inequalities and Device-Independent Applications
- Social optimality in quantum Bayesian games