Algorithms for Quantum Communication

Andrew Yao

With rapid advances in technology, it appears that computing and communication devices based on quantum principles may become available in the not too distant future. Accompanying this anticipation is the emergence of an energetic new inter-disciplinary field known as quantum information processing. In this talk, we give an exposition of some recent progress made in this area, with special focus on the algorithmic issues for communication tasks. Examples are taken quantum communication complexity and quantum cryptography. Although to understand the theory fully would require specialized knowledge, its essence can be grasped and enjoyed by any computer scientist.