Quantum communication complexity advantage implies violation of a Bell inequality.
Accepted version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
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
1091-6490
Volume Title
113
Publisher
Proceedings of the National Academy of Sciences
Publisher DOI
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.