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)

The set of 60 real rays in four dimensions derived from the vertices of a 600-cell is shown to possess numerous subsets of rays and bases that provide basis-critical parity proofs of the Bell-Kochen-Specker (BKS) theorem (a basis-critical proof is one that fails if even a single basis is deleted from it). The proofs vary considerably in size, with the smallest having 26 rays and 13 bases and the largest 60 rays and 41 bases. There are at least 90 basic (...) types of proofs, with each coming in a number of geometrically distinct varieties. The replicas of all the proofs under the symmetries of the 600-cell yield a total of almost a hundred million parity proofs of the BKS theorem. The proofs are all very transparent and take no more than simple counting to verify. A few of the proofs are exhibited, both in tabular form as well as in the form of MMP hypergraphs that assist in their visualization. A survey of the proofs is given, simple procedures for generating some of them are described and their applications are discussed. It is shown that all four-dimensional parity proofs of the BKS theorem can be turned into experimental disproofs of noncontextuality. (shrink)

It is shown that the 33 complex rays in three dimensions used by Penrose to prove the Bell-Kochen-Specker theorem have the same orthogonality relations as the 33 real rays of Peres, and therefore provide an isomorphic proof of the theorem. It is further shown that the Peres and Penrose rays are just two members of a continuous three-parameter family of unitarily inequivalent rays that prove the theorem.