Quantum one-way communication can be exponentially stronger than classical communication.

Oded Regev, Bo'az Klartag

Browse the full STOC paper archive.