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

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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

► BibTeX data

► 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).

[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).

[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).

[4] G. Brassard, Quantum Communication Complexity, Foundations of Physics 33, 11 (2003).

[5] R. Cleve and H. Buhrman, Substituting Quantum Entanglement for Communication, Phys. Rev. A 56, 1201 (1997).

[6] P. Trojek, C. Schmid, M. Bourennane, C. Brukner, M Żukowski, H. Weinfurter, Experimental quantum communication complexity, Phys. Rev. A 72, 050305 (2005).

[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).

[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).

[9] S. Laplante, M. Laurière, A. Nolin, J. Roland, and G. Senno, Robust Bell inequalities from communication complexity, Quantum 2, 72 (2018).

[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).

[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).

[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).

[13] R. Raz, Exponential separation of quantum and classical communication complexity, In Proceedings of 31st ACM STOC, 358 (1999).

[14] G. Brassard, R. Cleve and A. Tapp, Cost of exactly simulating quantum entanglement with classical communication, Phys. Rev. Lett. 83, 1874 (1999).

[15] M. Pawłowski and M. Żukowski, Entanglement assisted random access codes, Phys. Rev. A 81, 042326 (2010).

[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).

[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).

[18] H. Buhrman, R. Cleve and W. van Dam, Quantum entanglement and communication complexity, SIAM J. Comput. 30, 1829 (2001).

[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).

[20] N. D. Mermin, Extreme quantum entanglement in a superposition of macroscopically distinct states, Phys. Rev. Lett. 65, 1838 (1990).

[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).

[22] C. Brukner, M. Żukowski, and A. Zeilinger, Quantum Communication Complexity Protocol with Two Entangled Qutrits, Phys. Rev. Lett. 89, 197901 (2002).

[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).

[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:/​/​​abs/​quant-ph/​0702021.

[25] J. Oppenheim and S. Wehner, The Uncertainty Principle Determines the Nonlocality of Quantum Mechanics Science 19, 330 (2010).

[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).

[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).

[28] T. Lawson, N. Linden, and S. Popescu, Biased nonlocal quantum games, 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).

[30] C. Brukner, M. Żukowski, J-W. Pan, and A. Zeilinger, Bell's Inequalities and Quantum Communication Complexity, Phys. Rev. Lett. 92, 127901 (2004).

[31] H. Buhrman, R. Cleve, S. Massar, and R. de Wolf, Nonlocality and communication complexity, Rev. Mod. Phys. 82, 665 (2010).

[32] M. Navascués, S. Pironio, and A. Acín, Bounding the Set of Quantum Correlations, Phys. Rev. Lett. 98, 010401 (2007).

[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).

[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).

[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).

[37] R. Horodecki, P. Horodecki and M. Horodecki, Violating Bell inequality by mixed states: necessary and sufficient condition, Phys. Lett. A 200, 340 (1995).

Cited by

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

[2] Zhih-Ahn Jia, Lu Wei, Yu-Chun Wu, and Guang-Can Guo, "Quantum Advantages of Communication Complexity from Bell Nonlocality", Entropy 23 6, 744 (2021).

[3] Joseph Ho, George Moreno, Samuraí Brito, Francesco Graffitti, Christopher L. Morrison, Ranieri Nery, Alexander Pickston, Massimiliano Proietti, Rafael Rabelo, Alessandro Fedrizzi, and Rafael Chaves, "Quantum communication complexity beyond Bell nonlocality", arXiv:2106.06552.

The above citations are from Crossref's cited-by service (last updated successfully 2021-06-17 21:15:52) and SAO/NASA ADS (last updated successfully 2021-06-17 21:15:53). The list may be incomplete as not all publishers provide suitable and complete citation data.