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 nature of quantum computation is discussed. It is argued that, in terms of the amount of information manipulated in a given time, quantum and classical computation are equally efficient. Quantum superposition does not permit quantum computers to ''perform many computations simultaneously'' except in a highly qualified and to some extent misleading sense. Quantum computation is therefore not well described by interpretations of quantum mechanics which invoke the concept of vast numbers of parallel universes. Rather, entanglement makes available types of (...) computation processes which, while not exponentially larger than classical ones, are unavailable to classical systems. The essence of quantum computation is that it uses entanglement to generate and manipulate a physical representation of the correlations between logical entities, without the need to completely represent the logical entities themselves. (shrink)

This book compares various approaches to the interpretation of quantum mechanics, in particular those which are related to the key words "the Copenhagen interpretation", "the antirealist view", "quantum logic" and "hidden variable theory". Using the concept of "correlation" carefully analyzed in the context of classical probability and in quantum theory, the author provides a framework to compare these approaches. He also develops an extension of probability theory to construct a local hidden variable theory. The book should be of interest for (...) physicists and philosophers of science interested in the foundations of quantum theory. (shrink)

First-ever comprehensive introduction to the major new subject of quantum computing and quantum information.

An extraordinary and challenging synthesis of ideas uniting Quantum Theory, and the theories of Computation, Knowledge and Evolution, Deutsch's extraordinary book explores the deep connections between these strands which reveal the fabric ...