Quantum one-way communication can be exponentially stronger than classical communication
55 mins 42 secs,
206.53 MB,
iPod Video
480x270,
29.97 fps,
44100 Hz,
506.24 kbits/sec
Share this media item:
Embed this media item:
Embed this media item:
About this item
| Description: |
Regev, O (Tel Aviv)
Tuesday 29 March 2011, 10:00-11:00 |
|---|
| Created: | 2011-03-31 14:21 | ||||
|---|---|---|---|---|---|
| Collection: | Discrete Analysis | ||||
| Publisher: | Isaac Newton Institute | ||||
| Copyright: | Regev, O | ||||
| Language: | eng (English) | ||||
| Credits: |
|
||||
| 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. |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 640x360 | 1.85 Mbits/sec | 773.16 MB | View | Download | |
| WebM | 640x360 | 1.49 Mbits/sec | 624.05 MB | View | Download | |
| Flash Video | 484x272 | 568.73 kbits/sec | 232.02 MB | View | Download | |
| iPod Video * | 480x270 | 506.24 kbits/sec | 206.53 MB | View | Download | |
| MP3 | 44100 Hz | 125.01 kbits/sec | 50.80 MB | Listen | Download | |
| Auto | (Allows browser to choose a format it supports) | |||||