Recent advances in communication complexity in a setting where quantum information is available are reviewed. Holevo's Theorem implies that n qubits (quantum bits) cannot convey more classical information than n bits. Nevertheless, there are information processing tasks that require communication and for which using qubits instead of bits results in substantial savings. It is also natural to view Bell's Theorem about nonlocality in the context of communication complexity. We give examples of scenarios where quantum entanglement can be used to circumvent communication.

Host: Kim Skak Larsen