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
PublisherAssociation for Computing Machinery
Pages31-40
Number of pages10
ISBN (Print)9781450306911
DOIs
StatePublished - 2011
Event43rd ACM Symposium on Theory of Computing, STOC 2011 - San Jose, United States
Duration: Jun 6 2011Jun 8 2011

Publication series

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

Conference

Conference43rd ACM Symposium on Theory of Computing, STOC 2011
Country/TerritoryUnited States
CitySan Jose
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