Is Communication Complexity Physical - Quantum PhysicsReport as inadecuate

Is Communication Complexity Physical - Quantum Physics - Download this document for free, or read online. Document in PDF available to download.

Abstract: Recently, Brassard et. al. conjectured that the fact that the maximalpossible correlations between two non-local parties are the quantum-mechanicalones is linked to a reasonable restriction on communication complexity. Weprovide further support for the conjecture in the multipartite case. We showthat any multipartite communication complexity problem could be reduced totriviality, had Nature been more non-local than quantum-mechanics by a quitesmall gap for any number of parties. Intriguingly, the multipartitenonlocal-box that we use to show the result corresponds to the generalized Bellinequality that manifests maximal violation in respect to a localhidden-variable theory.

Author: Samuel Marcovitch, Benni Reznik



Related documents