Repository logo
 

Quantum communication complexity advantage implies violation of a Bell inequality.

Accepted version
Peer-reviewed

Repository DOI


Type

Article

Change log

Authors

Buhrman, Harry 
Czekaj, Łukasz 
Grudka, Andrzej 
Horodecki, Michał 
Horodecki, Paweł 

Abstract

We obtain a general connection between a large quantum advantage in communication complexity and Bell nonlocality. We show that given any protocol offering a sufficiently large quantum advantage in communication complexity, there exists a way of obtaining measurement statistics that violate some Bell inequality. Our main tool is port-based teleportation. If the gap between quantum and classical communication complexity can grow arbitrarily large, the ratio of the quantum value to the classical value of the Bell quantity becomes unbounded with the increase in the number of inputs and outputs.

Description

Keywords

Bell inequality, communication complexity, nonlocality, port-based teleportation, quantum

Journal Title

Proc Natl Acad Sci U S A

Conference Name

Journal ISSN

0027-8424
1091-6490

Volume Title

113

Publisher

Proceedings of the National Academy of Sciences
Sponsorship
The work is supported by EC IP QESSENCE, ERC AdG QOLAPS, EU project RAQUEL, Grant NCN Maestro (DEC- 2011/02/A/ST2/00305), the EU project SIQS and MNiSW grant IdP2011 000361. Sergii Strelchuk acknowledges the support of Sidney Sussex College. Part of this work was done at National Quantum Information Centre of Gdansk as well as during Program on Mathematical Challenges in Quantum Information, Isaac Newton Institute for Mathematical Sciences, 2013.