×

Quantum communication complexity advantage implies violation of a Bell inequality. (English) Zbl 1355.81046

Summary: 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.

MSC:

81P45 Quantum information, communication, networks (quantum-theoretic aspects)
94A05 Communication theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bell, On the Einstein-Podolsky-Rosen paradox, Physics 1 (3) pp 195– (1964)
[2] Yao A-C (1979) Some complexity questions related to distributed computing. Proceedings of 11th Annual ACM Symposium on the Theory of Computing, eds Fischer MJ Demillo RA Lynch NA Burkhard WA Aho AV (ACM Press, New York), pp 209–213
[3] Yao A-C (1993) Quantum circuit complexity. Proceedings of 34th IEEE Symposium on Foundations of Computer Science (IEEE Computer Society, Palo Alto, CA), pp 352–360
[4] DOI: 10.1103/PhysRevA.56.1201 · doi:10.1103/PhysRevA.56.1201
[5] Raz R (1999) Exponential separation of quantum and classical communication. Proceedings of 31st Annual ACM Symposium on the Theory of Computing, eds Vitter JS Larmore L Leighton T (ACM, New York), pp 358–367 · Zbl 1345.68134 · doi:10.1145/301250.301343
[6] DOI: 10.1103/RevModPhys.82.665 · doi:10.1103/RevModPhys.82.665
[7] DOI: 10.1137/S0097539797324886 · Zbl 0980.68051 · doi:10.1137/S0097539797324886
[8] Regev O Klartag B (2011) Quantum one-way communication can be exponentially stronger than classical communication. Proceedings of 43rd Annual ACM Symposium on Theory of Computing, ed Vadhan S (ACM, New York), Vol 31, pp 31–40 · Zbl 1288.68074 · doi:10.1145/1993636.1993642
[9] Buhrman H Scarpa G de Wolf R (2010) Better non-local games from hidden matching. arXiv:1007.2359
[10] DOI: 10.1103/PhysRevLett.92.127901 · Zbl 1267.81086 · doi:10.1103/PhysRevLett.92.127901
[11] DOI: 10.1007/s00220-010-1125-5 · Zbl 1211.46068 · doi:10.1007/s00220-010-1125-5
[12] DOI: 10.1103/PhysRevLett.101.240501 · doi:10.1103/PhysRevLett.101.240501
[13] DOI: 10.1103/PhysRevA.79.042306 · doi:10.1103/PhysRevA.79.042306
[14] Kremer I (1995) Quantum communication. Master’s thesis (Hebrew University, Jerusalem)
[15] DOI: 10.1109/TIT.2004.839476 · Zbl 1285.81011 · doi:10.1109/TIT.2004.839476
[16] Buhrman H Regev O Scarpa G de Wolf R (2011) Near-optimal and explicit Bell inequality violations. IEEE Conference on Computational Complexity (IEEE Computer Society, Washington, DC), Vol 157, pp 157–166 · Zbl 1298.81034 · doi:10.1109/CCC.2011.30
[17] Palazuelos C (2012) On the largest Bell violation attainable by a quantum state. arXiv:1206.3695 · Zbl 1295.81023
[18] DOI: 10.1007/s00220-011-1296-8 · Zbl 1230.81011 · doi:10.1007/s00220-011-1296-8
[19] Pirandola S Eisert J Weedbrook C Furusawa A Braunstein S (2015) Advances in quantum teleportation. arXiv:1505.07831
[20] Kushilevitz E Nisan N (2006) Communication Complexity (Cambridge Univ Press, Cambridge, UK) · Zbl 0869.68048
[21] de Wolf R (2001) Quantum computing and communication complexity. PhD thesis (University of Amsterdam, Amsterdam)
[22] Buhrman (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.