title: Quantum communication complexity advantage implies violation of a Bell inequality.
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.
authors.affiliation: Algorithms and Complexity Unit, Centrum Wiskunde & Informatica, 1098 XG Amsterdam, The Netherlands; Department of Computer Science, University of Amsterdam, 1012 WX Amsterdam, The Netherlands; QuSoft, 1098 XG Amsterdam, The Netherlands;
authors.forename: Harry
authors.initials: H
authors.lastname: Buhrman
authors.affiliation: Faculty of Mathematics, Physics and Informatics, Gdańsk University, 80-952 Gdańsk, Poland;
authors.forename: Łukasz
authors.initials: Ł
authors.lastname: Czekaj
authors.affiliation: Faculty of Physics, Adam Mickiewicz University, 61-614 Poznań, Poland;
authors.forename: Andrzej
authors.initials: A
authors.lastname: Grudka
authors.affiliation: Faculty of Mathematics, Physics and Informatics, Gdańsk University, 80-952 Gdańsk, Poland; Faculty of Physics, Adam Mickiewicz University, 61-614 Poznań, Poland;
authors.forename: Michał
authors.initials: M
authors.lastname: Horodecki
authors.affiliation: Faculty of Physics, Adam Mickiewicz University, 61-614 Poznań, Poland; Faculty of Applied Physics and Mathematics, Gdańsk University of Technology, 80-952 Gdańsk, Poland;
authors.forename: Paweł
authors.initials: P
authors.lastname: Horodecki
authors.affiliation: Institute of Physics, Jagiellonian University, 30-348 Krakow, Poland.
authors.forename: Marcin
authors.initials: M
authors.lastname: Markiewicz
authors.affiliation: Algorithms and Complexity Unit, Centrum Wiskunde & Informatica, 1098 XG Amsterdam, The Netherlands;
authors.forename: Florian
authors.initials: F
authors.lastname: Speelman
authors.affiliation: Faculty of Mathematics, Physics and Informatics, Gdańsk University, 80-952 Gdańsk, Poland; ss870@cam.ac.uk.
authors.forename: Sergii
authors.initials: S
authors.lastname: Strelchuk
keywords: Bell inequality; communication complexity; nonlocality; port-based teleportation; quantum