The Weizmann Institute of Science
Faculty of Mathematics and Computer Science
Walmart Lecture Series in Cryptography and Complexity
Seminar Room, Room 261, Ziskind Building
on Monday, January 31, 2011
at 14:30
Oded Regev
Tel Aviv University
will speak on
Quantum One-Way Communication Can Be
Exponentially Stronger than Classical Communication
Abstract:
In STOC 1999, Raz presented a (partial) function for which there is a quantum
protocol communicating only $O(\log n)$ qubits, but for which any classical
(randomized, bounded-error) protocol requires ${\rm poly}(n)$ bits of
communication. That quantum protocol requires two rounds of communication.
Ever since Raz's paper it was open whether the same exponential separation can
be achieved with a quantum protocol that uses only one round of communication.
In other words, can quantum one-way communication be exponentially stronger
than classical two-way communication? Here we settle this question in the
affirmative.
Based on joint work with Bo'az Klartag.
NOTE: This talk is about lower bounds for {\bf classical} communication
complexity; no knowledge of quantum communication complexity is assumed or
required.