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

Add to your list(s) Download to your calendar using vCal

• Regev, O (Tel Aviv)
• Tuesday 29 March 2011, 10:00-11:00
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact Mustapha Amrani.

Discrete Analysis

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.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.