# Does violation of a Bell inequality always imply quantum advantage in a communication complexity problem?

Armin Tavakoli1, Marek Żukowski2, and Časlav Brukner3,4

1Département de Physique Appliquée, Université de Genève, CH-1211 Genève, Switzerland
2International Centre for Theory of Quantum Technologies (ICTQT), University of Gdansk, 80-308 Gdansk, Poland
3Faculty of Physics, University of Vienna, Boltzmanngasse 5, A-1090 Vienna, Austria
4Institute of Quantum Optics and Quantum Information, Austrian Academy of Sciences, Boltzmanngasse 3, A-1090 Vienna, Austria

### Abstract

Quantum correlations which violate a Bell inequality are presumed to power better-than-classical protocols for solving communication complexity problems (CCPs). How general is this statement? We show that violations of correlation-type Bell inequalities allow advantages in CCPs, when communication protocols are tailored to emulate the Bell no-signaling constraint (by not communicating measurement settings). Abandonment of this restriction on classical models allows us to disprove the main result of, inter alia, [22]; we show that quantum correlations obtained from these communication strategies assisted by a small quantum violation of the CGLMP Bell inequalities do not imply advantages in any CCP in the input/output scenario considered in the reference. More generally, we show that there exists quantum correlations, with nontrivial local marginal probabilities, which violate the $I_{3322}$ Bell inequality, but do not enable a quantum advantange in any CCP, regardless of the communication strategy employed in the quantum protocol, for a scenario with a fixed number of inputs and outputs

### ► References

[1] C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem, IEEE Trans. Inf. Theory 48, 2637 (2002).
https:/​/​doi.org/​10.1109/​TIT.2002.802612

[2] Q. Zhuang, E. Y. Zhu, and P. W. Shor, Additive Classical Capacity of Quantum Channels Assisted by Noisy Entanglement, Phys. Rev. Lett. 118, 200503 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.118.200503

[3] C. H. Bennett, and S. J. Wiesner Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states, Phys. Rev. Lett. 69, 2881 (1992).
https:/​/​doi.org/​10.1103/​PhysRevLett.69.2881

[4] G. Brassard, Quantum Communication Complexity, Foundations of Physics 33, 11 (2003).
https:/​/​doi.org/​10.1023/​A:1026009100467

[5] R. Cleve and H. Buhrman, Substituting Quantum Entanglement for Communication, Phys. Rev. A 56, 1201 (1997).
https:/​/​doi.org/​10.1103/​PhysRevA.56.1201

[6] P. Trojek, C. Schmid, M. Bourennane, C. Brukner, M Żukowski, H. Weinfurter, Experimental quantum communication complexity, Phys. Rev. A 72, 050305 (2005).
https:/​/​doi.org/​10.1103/​PhysRevA.72.050305

[7] C. H. Bennett, D. P. DiVincenzo, P. W. Shor, J. A. Smolin, B. M. Terhal, and W. K. Wootters, Remote state preparation, Phys. Rev. Lett. 87, 077902 (2001).
https:/​/​doi.org/​10.1103/​PhysRevLett.87.077902

[8] D. Gavinsky, J. Kempe, O. Regev, and R. de Wolf, Bounded-error quantum state identification and exponential separations in communication complexity, In Proceedings of 38th ACM STOC, 594 (2006).
https:/​/​doi.org/​10.1145/​1132516.1132602

[9] S. Laplante, M. Laurière, A. Nolin, J. Roland, and G. Senno, Robust Bell inequalities from communication complexity, Quantum 2, 72 (2018).
https:/​/​doi.org/​10.22331/​q-2018-06-07-72

[10] A. Tavakoli, A. A. Abbott, M-O. Renou, N. Gisin, and N. Brunner, Semi-device-independent characterization of multipartite entanglement of states and measurements, Phys. Rev. A 98, 052333 (2018).
https:/​/​doi.org/​10.1103/​PhysRevA.98.052333

[11] S. Muhammad, A. Tavakoli, M. Kurant, M. Pawłowski, M. Żukowski, and M. Bourennane, Quantum Bidding in Bridge, Phys. Rev. X 4, 021047 (2014).
https:/​/​doi.org/​10.1103/​PhysRevX.4.021047

[12] H. Buhrman, R. Cleve and A. Wigderson, Quantum vs. classical communication and computation, Proceedings of the 30th Annual ACM Symposium on Theory of Computin, 63 (1998).
https:/​/​doi.org/​10.1145/​276698.276713

[13] R. Raz, Exponential separation of quantum and classical communication complexity, In Proceedings of 31st ACM STOC, 358 (1999).
https:/​/​doi.org/​10.1145/​301250.301343

[14] G. Brassard, R. Cleve and A. Tapp, Cost of exactly simulating quantum entanglement with classical communication, Phys. Rev. Lett. 83, 1874 (1999).
https:/​/​doi.org/​10.1103/​PhysRevLett.83.1874

[15] M. Pawłowski and M. Żukowski, Entanglement assisted random access codes, Phys. Rev. A 81, 042326 (2010).
https:/​/​doi.org/​10.1103/​PhysRevA.81.042326

[16] A. Tavakoli, M. Pawłowski, M. Żukowski, and M. Bourennane, Dimensional discontinuity in quantum communication complexity at dimension seven, Phys. Rev. A 95, 020302(R) (2017).
https:/​/​doi.org/​10.1103/​PhysRevA.95.020302

[17] H. Buhrman, Ł. Czekaj, A. Grudka, M. Horodecki, P. Horodecki, M. Markiewicz, F. Speelman, and S. Strelchuk, Quantum communication complexity advantage implies violation of a Bell inequality, PNAS 113, 3191 (2016).
https:/​/​doi.org/​10.1073/​pnas.1507647113

[18] H. Buhrman, R. Cleve and W. van Dam, Quantum entanglement and communication complexity, SIAM J. Comput. 30, 1829 (2001).
https:/​/​doi.org/​10.1137/​S0097539797324886

[19] J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, Proposed Experiment to Test Local Hidden-Variable Theories, Phys. Rev. Lett. 23, 880 (1969).
https:/​/​doi.org/​10.1103/​PhysRevLett.23.880

[20] N. D. Mermin, Extreme quantum entanglement in a superposition of macroscopically distinct states, Phys. Rev. Lett. 65, 1838 (1990).
https:/​/​doi.org/​10.1103/​PhysRevLett.65.1838

[21] D. Collins, N. Gisin, N. Linden, S. Massar, and S. Popescu, Bell Inequalities for Arbitrarily High-Dimensional Systems, Phys. Rev. Lett. 88, 040404 (2002).
https:/​/​doi.org/​10.1103/​PhysRevLett.88.040404

[22] C. Brukner, M. Żukowski, and A. Zeilinger, Quantum Communication Complexity Protocol with Two Entangled Qutrits, Phys. Rev. Lett. 89, 197901 (2002).
https:/​/​doi.org/​10.1103/​PhysRevLett.89.197901

[23] C. Brukner, T. Paterek, and M. Żukowski, Quantum communication complexity protocols based on higher-dimensional entangled systems, Int J of Quant Inf. 1, 4 (2003).
https:/​/​doi.org/​10.1142/​S0219749903000395

[24] N. Gisin, Bell inequalities: Many questions, a few answers, in Quantum Reality, Relativistic Causality, and Closing the Epistemic Circle: Essays in Honour of Abner Shimony. The Western Ontario Series in Philosophy of Science (Springer, Berlin, 2009), Vol. 73, p. 125. https:/​/​arxiv.org/​abs/​quant-ph/​0702021.
arXiv:quant-ph/0702021

[25] J. Oppenheim and S. Wehner, The Uncertainty Principle Determines the Nonlocality of Quantum Mechanics Science 19, 330 (2010).
https:/​/​doi.org/​10.1126/​science.1192065

[26] A. Tavakoli, B. Marques, M. Pawłowski, and M. Bourennane, Spatial versus sequential correlations for random access coding, Phys. Rev. A 93, 032336 (2016).
https:/​/​doi.org/​10.1103/​PhysRevA.93.032336

[27] A. Hameedi, D. Saha, P. Mironowicz, M. Pawłowski, and M. Bourennane, Complementarity between entanglement-assisted and quantum distributed random access code, Phys. Rev. A 95, 052345 (2017).
https:/​/​doi.org/​10.1103/​PhysRevA.95.052345

[28] T. Lawson, N. Linden, and S. Popescu, Biased nonlocal quantum games, arXiv:1011.6245.
arXiv:1011.6245

[29] A. Tavakoli and M. Żukowski, Higher-dimensional communication complexity problems: Classical protocols versus quantum ones based on Bell's theorem or prepare-transmit-measure schemes, Phys. Rev. A 95, 042305 (2017).
https:/​/​doi.org/​10.1103/​PhysRevA.95.042305

[30] C. Brukner, M. Żukowski, J-W. Pan, and A. Zeilinger, Bell's Inequalities and Quantum Communication Complexity, Phys. Rev. Lett. 92, 127901 (2004).
https:/​/​doi.org/​10.1103/​PhysRevLett.92.127901

[31] H. Buhrman, R. Cleve, S. Massar, and R. de Wolf, Nonlocality and communication complexity, Rev. Mod. Phys. 82, 665 (2010).
https:/​/​doi.org/​10.1103/​RevModPhys.82.665

[32] M. Navascués, S. Pironio, and A. Acín, Bounding the Set of Quantum Correlations, Phys. Rev. Lett. 98, 010401 (2007).
https:/​/​doi.org/​10.1103/​PhysRevLett.98.010401

[33] D. Martínez, A. Tavakoli, M. Casanova, G. Cañas, B. Marques, and G. Lima, High-Dimensional Quantum Communication Complexity beyond Strategies Based on Bell's Theorem, Phys. Rev. Lett. 121, 150504 (2018).
https:/​/​doi.org/​10.1103/​PhysRevLett.121.150504

[34] L. Vandenberghe and S. Boyd, SIAM Review 38, 49 (1996).

[35] M. Froissart, Constructive generalization of Bells inequalities, Il Nuovo Cimento B 64, 241 (1981).
https:/​/​doi.org/​10.1007/​BF02903286

[36] D. Collins, and N. Gisin, A Relevant Two Qubit Bell Inequality Inequivalent to the CHSH Inequality, J. Phys. A: Math. Gen. 37 1775 (2004).
https:/​/​doi.org/​10.1088/​0305-4470/​37/​5/​021

[37] R. Horodecki, P. Horodecki and M. Horodecki, Violating Bell inequality by mixed states: necessary and sufficient condition, Phys. Lett. A 200, 340 (1995).
https:/​/​doi.org/​10.1016/​0375-9601(95)00214-N

### Cited by

[1] Fabian Bernards and Otfried Gühne, "Generalizing Optimal Bell Inequalities", Physical Review Letters 125 20, 200401 (2020).

The above citations are from Crossref's cited-by service (last updated successfully 2020-11-25 19:57:48). The list may be incomplete as not all publishers provide suitable and complete citation data.

On SAO/NASA ADS no data on citing works was found (last attempt 2020-11-25 19:57:48).