Quantum Communication Complexity and Pseudo Telepathy

by Prof. Gilles Brassard

Thursday 10 Jul 2008, 16:00 → 18:00 Europe/Rome

Aula 5 (Dip. di Fisica - ed. E.Fermi)

Consider a computational task for which the input is distributed betweentwo parties, who wish to collaborate to compute the output. We areinterested in minimising the amount of communication needed toachieve this goal. Even though entanglement is a nonsignalling resource,could it serve to solve such problems more efficiently even if we arerestricted to classical communication?