Quantum communication complexity advantage implies violation of a Bell inequality
Proceedings of the National Academy of Sciences
National Academy of Sciences
MetadataShow full item record
Buhrman, H., Czekaj, L., Grudka, A., Horodecki, M., Horodecki, P., Markiewicz, M., Speelman, F., & et al. (2016). Quantum communication complexity advantage implies violation of a Bell inequality. Proceedings of the National Academy of Sciences, 113 3191-3196. https://doi.org/10.1073/pnas.1507647113
We obtain a general connection between a large quantum advantage in communication complexity and Bell 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.
communication complexity, Bell non-locality, quantum advantage, quantum information
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.
External DOI: https://doi.org/10.1073/pnas.1507647113
This record's URL: https://www.repository.cam.ac.uk/handle/1810/253878
Attribution-NonCommercial 2.0 UK: England & Wales
Licence URL: http://creativecommons.org/licenses/by-nc/2.0/uk/