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 that goes beyond the abilities of classical information processing devices. Communication complexity is an area of classical computer science that aims at quantifying the amount of communication necessary to solve distributed computational problems. Quantum communication complexity uses quantum mechanics to reduce the amount of communication that would be classically required.Pseudo-telepathy is a surprising application of (...) quantum information processing to communication complexity. Thanks to entanglement, perhaps the most nonclassical manifestation of quantum mechanics, two or more quantum players can accomplish a distributed task with no need for communication whatsoever, which would be an impossible feat for classical players. After a detailed overview of the principle and purpose of pseudo-telepathy, we present a survey of recent and not-so-recent work on the subject. In particular, we describe and analyse all the pseudo-telepathy games currently known to the authors. (shrink)

Can quantum communication be more efficient than its classical counterpart? Holevo's theorem rules out the possibility of communicating more than n bits of classical information by the transmission of n quantum bits—unless the two parties are entangled, in which case twice as many classical bits can be communicated but no more. In apparent contradiction, there are distributed computational tasks for which quantum communication cannot be simulated efficiently by classical means. In some cases, the effect of transmitting quantum bits cannot be (...) achieved classically short of transmitting an exponentially larger number of bits. In a similar vein, can entanglement be used to save on classical communication? It is well known that entanglement on its own is useless for the transmission of information. Yet, there are distributed tasks that cannot be accomplished at all in a classical world when communication is not allowed, but that become possible if the non-communicating parties share prior entanglement. This leads to the question of how expensive it is, in terms of classical communication, to provide an exact simulation of the spooky power of entanglement. (shrink)

In an earlier paper written in loving memory of Asher Peres, we gave a critical analysis of the celebrated 1935 paper in which Einstein, Podolsky and Rosen (EPR) challenged the completeness of quantum mechanics. There, we had pointed out logical shortcomings in the EPR paper. Now, we raise additional questions concerning their suggested program to find a theory that would “provide a complete description of the physical reality”. In particular, we investigate the extent to which the EPR argumentation could have (...) lead to the more dramatic conclusion that quantum mechanics is in fact incorrect. With this in mind, we propose a speculation, made necessary by a logical shortcoming in the EPR paper caused by the lack of a necessary condition for “elements of reality”, and surmise that an eventually complete theory would either be inconsistent with quantum mechanics, or would at least violate Heisenberg’s Uncertainty Principle. (shrink)