![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Tuesday 29 March 2011, 10:00-11:00
Quantum one-way communication can be exponentially stronger than classical communication
- 👤 Speaker: Regev, O (Tel Aviv)
- 📅 Date & Time: Tuesday 29 March 2011, 10:00 - 11:00
- 📍 Venue: 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.
Series This talk is part of the Isaac Newton Institute Seminar Series series.
Included in Lists
- All CMS events
- bld31
- dh539
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
Note: Ex-directory lists are not shown.