Authors: Anne Broadbent
Comments: Master's Thesis, 136 pages (August 2004)
Quantum information processing is at the crossroads of physics,
mathematics and computer science; it is concerned with what we
can and cannot do with quantum information. This thesis deals
with communication complexity, which is an area of computer
science that aims at quantifying the amount of communication
necessary to solve distributed problems.
Pseudo-telepathy is a surprising application of quantum
information processing to communication complexity. Thanks to a
quantum resource called ``entanglement'', two or more quantum
players can accomplish a task with no communication, whereas this
would be impossible for classical players (who do not have access
to entanglement). A pseudo-telepathy game with n players is the
following: each player receives as input a question. Without
communicating, each player outputs an answer. The players win if
their joint answers satisfy a certain condition. We say that the
game exhibits pseudo-telepathy if quantum players can
systematically succeed at this game, whereas this would be
impossible for classical players.
In this thesis, we describe seven pseudo-telepathy games which
appear in the physics and quantum information processing
literature. We have also included original results of the author.
The games are presented from a computer scientist's perspective,
and in a uniform way, in order to facilitate comparison. Some
points of comparison are: number of players, size of the inputs,
size of outputs, winning condition, shared entangled state and
maximum success probability for classical players.
Keywords: quantum information processing, quantum communication
complexity, nonlocality, entanglement, Bell's theorem, detection
loophole.