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

Bo'az Klartag, Oded Regev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish (US)
Title of host publicationSTOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing
Pages31-40
Number of pages10
DOIs
StatePublished - 2011
Event43rd ACM Symposium on Theory of Computing, STOC'11 - San Jose, CA, United States
Duration: Jun 6 2011Jun 8 2011

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other43rd ACM Symposium on Theory of Computing, STOC'11
CountryUnited States
CitySan Jose, CA
Period6/6/116/8/11

Keywords

  • communication complexity
  • hypercontractive inequality
  • sampling
  • sphere

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Quantum one-way communication can be exponentially stronger than classical communication'. Together they form a unique fingerprint.

  • Cite this

    Klartag, B., & Regev, O. (2011). Quantum one-way communication can be exponentially stronger than classical communication. In STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing (pp. 31-40). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/1993636.1993642