Quantum Communication Complexity

Abstract

This paper surveys the field of quantum communication complexity. Some interesting recent results are collected concerning relations to classical communication, lower bound methods, one-way communication, and applications of quantum communication complexity.

11 pages, LaTeX, to appear in: Workshop Proceedings of the 27th International Colloquium on Automata, Languages and Programming 2000, Workshop on Boolean Functions and Applications

References in corpus (4)

• Substituting Quantum Entanglement for Communication
• Quantum vs. Classical Communication and Computation
• Bounds for Small-Error and Zero-Error Quantum Algorithms
• An Almost-Quadratic Lower Bound for Quantum Formula Size

Cited by in corpus (8)

• Non-locality and Communication Complexity
• A limit on nonlocality in any world in which communication complexity is not trivial
• Experimental Quantum Fingerprinting
• Lower bounds on the entanglement needed to play XOR non-local games
• Oblivious communication game, self-testing of projective and non-projective measurements and certification of randomness
• Generalizations of the distributed Deutsch-Jozsa promise problem
• Compressibility of positive semidefinite factorizations and quantum models
• Communication complexity of promise problems and their applications to finite automata