Friday, June 17, 2005

Recasting Mermin's multi-player game into the framework of pseudo-telepathy

Preprint by Gilles Brassard, Anne Broadbent, Alain Tapp
Entanglement is perhaps the most non-classical manifestation of quantum mechanics. Among its many interesting applications to information processing, it can be harnessed to reduce the amount of communication required to process a variety of distributed computational tasks. Can it be used to eliminate communication altogether? Even though it cannot serve to signal information between remote parties, there are distributed tasks that can be performed without any need for communication, provided the parties share prior entanglement: this is the realm of pseudo-telepathy.
One of the earliest uses of multi-party entanglement was presented by Mermin in 1990. Here we recast his idea in terms of pseudo-telepathy: we provide a new computer-scientist-friendly analysis of this game. We prove an upper bound on the best possible classical strategy for attempting to play this game, as well as a novel, matching lower bound. This leads us to considerations on how well imperfect quantum-mechanical apparatus must perform in order to exhibit a behaviour that would be classically impossible to explain. Our results include improved bounds that could help vanquish the infamous detection loophole.

In Mermin's game, n players are given a simple task which definitely requires communication in a classical setting. By using quantum techniques (involving the notorious concept of entanglement), the task can be performed without any communication at all - hence the "pseudo-telepathy".

The problem, by the way is very simple. It requires three or more players. Each is given an input bit (0 or 1). They are promised that the total number of input 1's is even. They each then produce an output bit. If the sum of the input bits is divisible by four, there should be an odd number of output 1's. If the sum of the input bits is not divisible by four, the sum of output bits should be divisible by two (an even number of output 1's).

No comments: