The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

DAN

Seminar

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

Regev, O (Tel Aviv)
Tuesday 29 March 2011, 10:00-11:00

Seminar Room 1, Newton Institute

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 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 *classical* communication complexity; no knowledge of quantum communication complexity is assumed or required.

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧