University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Quantum one-way communication can be exponentially stronger than classical communication

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

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity