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

Armin Tavakoli; Marek Żukowski; Časlav Brukner

doi:10.22331/q-2020-09-07-316

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

Armin Tavakoli¹, Marek Żukowski², and Časlav Brukner^3,4

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

Published:	2020-09-07, volume 4, page 316
Eprint:	arXiv:1907.01322v3
Doi:	https://doi.org/10.22331/q-2020-09-07-316
Citation:	Quantum 4, 316 (2020).

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

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

► BibTeX data

@article{Tavakoli2020doesviolationofbell,
  doi = {10.22331/q-2020-09-07-316},
  url = {https://doi.org/10.22331/q-2020-09-07-316},
  title = {Does violation of a {B}ell inequality always imply quantum advantage in a communication complexity problem?},
  author = {Tavakoli, Armin and {\.{Z}}ukowski, Marek and Brukner, {\v{C}}aslav},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {316},
  month = sep,
  year = {2020}
}

► 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] Armin Tavakoli, Jef Pauwels, Erik Woodhead, and Stefano Pironio, "Correlations in Entanglement-Assisted Prepare-and-Measure Scenarios", PRX Quantum 2 4, 040357 (2021).

[2] Hui-Xian Meng, Zhong-Yan Li, Xing-Yan Fan, Jia-Le Miao, Hong-Ye Liu, Yi-Jia Liu, Wei-Min Shang, Jie Zhou, and Jing-Ling Chen, "Robust coincidence Bell inequalities for the noisy n -qutrit Greenberger-Horne-Zeilinger state", Physical Review A 105 6, 062215 (2022).

[3] Jef Pauwels, Stefano Pironio, Emmanuel Zambrini Cruzeiro, and Armin Tavakoli, "Adaptive Advantage in Entanglement-Assisted Communications", Physical Review Letters 129 12, 120504 (2022).

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

[5] A. K. Pan, "Oblivious communication game, self-testing of projective and nonprojective measurements, and certification of randomness", Physical Review A 104 2, 022212 (2021).

[6] S. Gómez, D. Uzcátegui, I. Machuca, E. S. Gómez, S. P. Walborn, G. Lima, and D. Goyeneche, "Optimal strategy to certify quantum nonlocality", Scientific Reports 11 1, 20489 (2021).

[7] Marcin Wieśniak, "Symmetrized persistency of Bell correlations for Dicke states and GHZ-based mixtures", Scientific Reports 11 1, 14333 (2021).

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

[9] Jef Pauwels, Armin Tavakoli, Erik Woodhead, and Stefano Pironio, "Entanglement in prepare-and-measure scenarios: many questions, a few answers", New Journal of Physics 24 6, 063015 (2022).

[10] Joseph Ho, George Moreno, Samuraí Brito, Francesco Graffitti, Christopher L. Morrison, Ranieri Nery, Alexander Pickston, Massimiliano Proietti, Rafael Rabelo, Alessandro Fedrizzi, and Rafael Chaves, "Entanglement-based quantum communication complexity beyond Bell nonlocality", npj Quantum Information 8 1, 13 (2022).

[11] Amélie Piveteau, Alastair A. Abbott, Sadiq Muhammad, Mohamed Bourennane, and Armin Tavakoli, "Weak entanglement improves quantum communication using only passive linear optics", arXiv:2303.07907, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-06-05 15:38:07) and SAO/NASA ADS (last updated successfully 2023-06-05 15:38:08). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.