Is Communication Complexity Physical?
arXiv:0709.1602 · doi:10.1103/PhysRevA.77.032120
Abstract
Recently, Brassard et. al. conjectured that the fact that the maximal possible correlations between two non-local parties are the quantum-mechanical ones is linked to a reasonable restriction on communication complexity. We provide further support for the conjecture in the multipartite case. We show that any multipartite communication complexity problem could be reduced to triviality, had Nature been more non-local than quantum-mechanics by a quite small gap for any number of parties. Intriguingly, the multipartite nonlocal-box that we use to show the result corresponds to the generalized Bell inequality that manifests maximal violation in respect to a local hidden-variable theory.
References in corpus (7)
- All multipartite Bell correlation inequalities for two dichotomic observables per site
- A limit on nonlocality in any world in which communication complexity is not trivial
- Bell-type inequalities to detect true n-body non-separability
- Bell inequality, Bell states and maximally entangled states for n qubits
- Violation of Bell's inequality: criterion for quantum communication complexity advantage
- Bell-type inequalities for partial separability in N-particle systems and quantum mechanical violations
- Popescu-Rohrlich correlations as a unit of nonlocality