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 -