TY - GEN

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

AU - Klartag, Bo'az

AU - Regev, Oded

PY - 2011

Y1 - 2011

N2 - 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. Here we settle this question in the affirmative.

AB - 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. Here we settle this question in the affirmative.

KW - communication complexity

KW - hypercontractive inequality

KW - sampling

KW - sphere

UR - http://www.scopus.com/inward/record.url?scp=79959696265&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79959696265&partnerID=8YFLogxK

U2 - 10.1145/1993636.1993642

DO - 10.1145/1993636.1993642

M3 - Conference contribution

AN - SCOPUS:79959696265

SN - 9781450306911

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 31

EP - 40

BT - STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 43rd ACM Symposium on Theory of Computing, STOC 2011

Y2 - 6 June 2011 through 8 June 2011

ER -