Abstract
Keywords: entanglement, complexity, entropy, measurement
In chapter 1 the basic principles of communication complexity are introduced.
Two-party communication is described explicitly, and multi-party
communication complexity is described in terms of the two-party communication
complexity model. The relation to entropy is described for the classical
communication model. Important concepts from quantum mechanics are
introduced. More advanced concepts, for example the generalized measurement,
are then presented in detail.
In chapter 2 the di erent measures of entanglement are described in detail,
and concrete examples are provided. Measures for both pure states and mixed
states are described in detail. Some results for the Schmidt decomposition
are derived for applications in communication complexity. The Schmidt decomposition
is fundamental in quantum communication and computation,
and thus is presented in considerable detail. Important concepts such as
positive maps and entanglement witnesses are discussed with examples.
Finally, in chapter 3, the communication complexity model for quantum communication
is described. A number of examples are presented to illustrate
the advantages of quantum communication in the communication complexity
scenario. This includes communication by teleportation, and dense coding
using entanglement. A few problems, such as the Deutsch-Jozsa problem, are
worked out in detail to illustrate the advantages of quantum communication.
The communication complexity of sampling establishes some relationships
between communication complexity, the Schmidt rank and entropy. The last
topic is coherent communication complexity, which places communication
complexity completely in the domain of quantum computation. An important
lower bound for the coherent communication complexity in terms of the
Schmidt rank is dervived. This result is the quantum analogue to the log
rank lower bound in classical communication complexity.
Prof. W.H. Steeb