Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication

Autor(en)

Philippe Allard Guerin, Adrien Feix, Mateus Araújo, Caslav Brukner

Abstrakt

In communication complexity, a number of distant parties have the task of calculating a distributed function of their inputs, while minimizing the amount of communication between them. It is known that with quantum resources, such as entanglement and quantum channels, one can obtain significant reductions in the communication complexity of some tasks. In this work, we study the role of the quantum superposition of the direction of communication as a resource for communication complexity. We present a tripartite communication task for which such a superposition allows for an exponential saving in communication, compared to one-way quantum (or classical) communication; the advantage also holds when we allow for protocols with bounded error probability.

Organisation(en)

Quantenoptik, Quantennanophysik und Quanteninformation

Journal

Physical Review Letters

Band

117

Anzahl der Seiten

5

ISSN

0031-9007

DOI

https://doi.org/10.1103/PhysRevLett.117.100502

Publikationsdatum

09-2016

Peer-reviewed

Ja

ÖFOS 2012

103025 Quantenmechanik

ASJC Scopus Sachgebiete

Allgemeine Physik und Astronomie

Link zum Portal

https://ucrisportal.univie.ac.at/de/publications/4960ca39-e5da-455c-98c2-c6bf65e3ff7b