Quantum communication complexity advantage implies violation of a Bell inequality

Harry Buhrman; Łukasz Czekaj; Andrzej Grudka; Michał Horodecki; Paweł Horodecki; Marcin Markiewicz; Florian Speelman; Sergii Strelchuk

doi:10.1073/pnas.1507647113

Quantum communication complexity advantage implies violation of a Bell inequality

Abstract

We obtain a general connection between a quantum advantage in communication complexity and non-locality. We show that given any protocol offering a (sufficiently large) quantum advantage in communication complexity, there exists a way of obtaining measurement statistics which 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.

Citations

3 8

CrossRef
0

Web of Science
3 8

Scopus

Authors (8)

Harry Buhrman
- Centrum Wiskunde and Infrmatics Amsterdam
Łukasz Czekaj dr inż.
- Wydział Matematyki Fizyki i Informatyki Uniwersytet Gdański
Andrzej Grudka
- Uniwersytet Adama Mickiewicza Wydział Fizyki
Michał Horodecki
- Wydział Matematyki Fizyki i Informatyki Uniwersytet Gdański
Paweł Horodecki prof. dr hab.
Marcin Markiewicz
- Wydział Matematyki Fizyki i Informatyki Uniwersytet Gdański
Florian Speelman
- Centrum Wiskunde and Infrmatics Amsterdam
Sergii Strelchuk
- University ofg Cambridge Department of Applied Mathematics and Theoretical Physics

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie wyróżnionym w JCR
Published in:: PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA no. 113, edition 12, pages 3191 - 3196,
ISSN: 0027-8424
Language:: English
Publication year:: 2016
Bibliographic description:: Buhrman H., Czekaj Ł., Grudka A., Horodecki M., Horodecki P., Markiewicz M., Speelman F., Strelchuk S.: Quantum communication complexity advantage implies violation of a Bell inequality// PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA. -Vol. 113, iss. 12 (2016), s.3191-3196
DOI:: Digital Object Identifier (open in new tab) 10.1073/pnas.1507647113
Verified by:: Gdańsk University of Technology