Quantum advantages of communication complexity from Bell nonlocality
arXiv:2004.05098 · doi:10.3390/e23060724
Abstract
Communication games are crucial tools for investigating the limitations of physical theories. The communication complexity (CC) problem is a typical example, for which several distributed parties attempt to jointly calculate a given function with limited classical communications. In this work, we present a method to construct CC problems from Bell tests in a graph-theoretic way. Starting from an experimental compatibility graph and the corresponding Bell test function, a target function which encodes the information of each edge can be constructed, then using this target function we could construct an CC function for which by pre-sharing entangled states, the success probability will exceed that for arbitrary classical strategy. The non-signaling protocol based on Popescu-Rohrlich box is also discussed, and the success probability in this case would reach one.
References in corpus (20)
- Quantum entanglement
- Bell nonlocality
- Quantum Random Number Generators
- Non-locality and Communication Complexity
- A limit on nonlocality in any world in which communication complexity is not trivial
- The Communication Cost of Simulating Bell Correlations
- Graph-Theoretic Approach to Quantum Correlations
- Violation of Bell's inequality: criterion for quantum communication complexity advantage
- Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities
- Quantum Entanglement and Communication Complexity
- Generalized monogamy of contextual inequalities from the no-disturbance principle
- Implausible Consequences of Superstrong Nonlocality
- Quantum communication complexity advantage implies violation of a Bell inequality
- The communication complexity of non-signaling distributions
- Necessary and sufficient condition for contextuality from incompatibility
- Does violation of a Bell inequality always imply quantum advantage in a communication complexity problem?
- Monogamy Relation in No-disturbance Theories
- Robust Bell inequalities from communication complexity
- Entropic No-Disturbance as a Physical Principle
- The Exclusivity Principle Determines the Correlation Monogamy