Multi-party Pseudo-Telepathy

Quantum entanglement, perhaps the most non-classical manifestation of quantum information theory, cannot be used to transmit information between remote parties. Yet, it can be used to reducethe amount of communication required to process a variety of distributedcomputational tasks. We speak of pseudo-telepathy when quantum entanglementserves to eliminate the classical need to communicate. In earlier examples of pseudo-telepathy, classical protocols could succeedwith high probability unless the inputs were very large. Here we present a simple multi-party distributed problem for which the inputsand outputsconsist of a single bit per player, and we present a perfectquantum protocolfor it. We prove that no classical protocol can succeedwith a probability that differs from 1/2 by more than a fraction that is exponentially small in the number of players. This could be used to circumvent the detection loophole in experimental tests of nonlocality.