{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T07:04:48Z","timestamp":1776495888301,"version":"3.51.2"},"reference-count":37,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,9,7]],"date-time":"2020-09-07T00:00:00Z","timestamp":1599436800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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, \\cite{BZ02}; 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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>I<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mn>3322<\/mml:mn><\/mml:mrow><\/mml:msub><\/mml:math> 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<\/jats:p>","DOI":"10.22331\/q-2020-09-07-316","type":"journal-article","created":{"date-parts":[[2020,9,7]],"date-time":"2020-09-07T15:59:48Z","timestamp":1599494388000},"page":"316","source":"Crossref","is-referenced-by-count":18,"title":["Does violation of a Bell inequality always imply quantum advantage in a communication complexity problem?"],"prefix":"10.22331","volume":"4","author":[{"given":"Armin","family":"Tavakoli","sequence":"first","affiliation":[{"name":"D\u00e9partement de Physique Appliqu\u00e9e, Universit\u00e9 de Gen\u00e8ve, CH-1211 Gen\u00e8ve, Switzerland"}]},{"given":"Marek","family":"\u017bukowski","sequence":"additional","affiliation":[{"name":"International Centre for Theory of Quantum Technologies (ICTQT), University of Gdansk, 80-308 Gdansk, Poland"}]},{"given":"\u010caslav","family":"Brukner","sequence":"additional","affiliation":[{"name":"Faculty of Physics, University of Vienna, Boltzmanngasse 5, A-1090 Vienna, Austria"},{"name":"Institute of Quantum Optics and Quantum Information, Austrian Academy of Sciences, Boltzmanngasse 3, A-1090 Vienna, Austria"}]}],"member":"9598","published-online":{"date-parts":[[2020,9,7]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1109\/TIT.2002.802612"},{"key":"1","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.118.200503"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.69.2881"},{"key":"3","doi-asserted-by":"publisher","unstructured":"G. Brassard, Quantum Communication Complexity, Foundations of Physics 33, 11 (2003).","DOI":"10.1023\/A:1026009100467"},{"key":"4","doi-asserted-by":"publisher","unstructured":"R. Cleve and H. Buhrman, Substituting Quantum Entanglement for Communication, Phys. Rev. A 56, 1201 (1997).","DOI":"10.1103\/PhysRevA.56.1201"},{"key":"5","doi-asserted-by":"publisher","unstructured":"P. Trojek, C. Schmid, M. Bourennane, C. Brukner, M \u017bukowski, H. Weinfurter, Experimental quantum communication complexity, Phys. Rev. A 72, 050305 (2005).","DOI":"10.1103\/PhysRevA.72.050305"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.87.077902"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1145\/1132516.1132602"},{"key":"8","doi-asserted-by":"publisher","unstructured":"S. Laplante, M. Lauri\u00e8re, A. Nolin, J. Roland, and G. Senno, Robust Bell inequalities from communication complexity, Quantum 2, 72 (2018).","DOI":"10.22331\/q-2018-06-07-72"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.98.052333"},{"key":"10","doi-asserted-by":"publisher","unstructured":"S. Muhammad, A. Tavakoli, M. Kurant, M. Paw\u0142owski, M. \u017bukowski, and M. Bourennane, Quantum Bidding in Bridge, Phys. Rev. X 4, 021047 (2014).","DOI":"10.1103\/PhysRevX.4.021047"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1145\/276698.276713"},{"key":"12","doi-asserted-by":"publisher","unstructured":"R. Raz, Exponential separation of quantum and classical communication complexity, In Proceedings of 31st ACM STOC, 358 (1999).","DOI":"10.1145\/301250.301343"},{"key":"13","doi-asserted-by":"publisher","unstructured":"G. Brassard, R. Cleve and A. Tapp, Cost of exactly simulating quantum entanglement with classical communication, Phys. Rev. Lett. 83, 1874 (1999).","DOI":"10.1103\/PhysRevLett.83.1874"},{"key":"14","doi-asserted-by":"publisher","unstructured":"M. Paw\u0142owski and M. \u017bukowski, Entanglement assisted random access codes, Phys. Rev. A 81, 042326 (2010).","DOI":"10.1103\/PhysRevA.81.042326"},{"key":"15","doi-asserted-by":"publisher","unstructured":"A. Tavakoli, M. Paw\u0142owski, M. \u017bukowski, and M. Bourennane, Dimensional discontinuity in quantum communication complexity at dimension seven, Phys. Rev. A 95, 020302(R) (2017).","DOI":"10.1103\/PhysRevA.95.020302"},{"key":"16","doi-asserted-by":"publisher","unstructured":"H. Buhrman, \u0141. 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).","DOI":"10.1073\/pnas.1507647113"},{"key":"17","doi-asserted-by":"publisher","unstructured":"H. Buhrman, R. Cleve and W. van Dam, Quantum entanglement and communication complexity, SIAM J. Comput. 30, 1829 (2001).","DOI":"10.1137\/S0097539797324886"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.23.880"},{"key":"19","doi-asserted-by":"publisher","unstructured":"N. D. Mermin, Extreme quantum entanglement in a superposition of macroscopically distinct states, Phys. Rev. Lett. 65, 1838 (1990).","DOI":"10.1103\/PhysRevLett.65.1838"},{"key":"20","doi-asserted-by":"publisher","unstructured":"D. Collins, N. Gisin, N. Linden, S. Massar, and S. Popescu, Bell Inequalities for Arbitrarily High-Dimensional Systems, Phys. Rev. Lett. 88, 040404 (2002).","DOI":"10.1103\/PhysRevLett.88.040404"},{"key":"21","doi-asserted-by":"publisher","unstructured":"C. Brukner, M. \u017bukowski, and A. Zeilinger, Quantum Communication Complexity Protocol with Two Entangled Qutrits, Phys. Rev. Lett. 89, 197901 (2002).","DOI":"10.1103\/PhysRevLett.89.197901"},{"key":"22","doi-asserted-by":"publisher","unstructured":"C. Brukner, T. Paterek, and M. \u017bukowski, Quantum communication complexity protocols based on higher-dimensional entangled systems, Int J of Quant Inf. 1, 4 (2003).","DOI":"10.1142\/S0219749903000395"},{"key":"23","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1007\/978-1-4020-9107-0_9"},{"key":"24","doi-asserted-by":"publisher","unstructured":"J. Oppenheim and S. Wehner, The Uncertainty Principle Determines the Nonlocality of Quantum Mechanics Science 19, 330 (2010).","DOI":"10.1126\/science.1192065"},{"key":"25","doi-asserted-by":"publisher","unstructured":"A. Tavakoli, B. Marques, M. Paw\u0142owski, and M. Bourennane, Spatial versus sequential correlations for random access coding, Phys. Rev. A 93, 032336 (2016).","DOI":"10.1103\/PhysRevA.93.032336"},{"key":"26","doi-asserted-by":"publisher","unstructured":"A. Hameedi, D. Saha, P. Mironowicz, M. Paw\u0142owski, and M. Bourennane, Complementarity between entanglement-assisted and quantum distributed random access code, Phys. Rev. A 95, 052345 (2017).","DOI":"10.1103\/PhysRevA.95.052345"},{"key":"27","unstructured":"T. Lawson, N. Linden, and S. Popescu, Biased nonlocal quantum games, arXiv:1011.6245."},{"key":"28","doi-asserted-by":"publisher","unstructured":"A. Tavakoli and M. \u017bukowski, 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).","DOI":"10.1103\/PhysRevA.95.042305"},{"key":"29","doi-asserted-by":"publisher","unstructured":"C. Brukner, M. \u017bukowski, J-W. Pan, and A. Zeilinger, Bell's Inequalities and Quantum Communication Complexity, Phys. Rev. Lett. 92, 127901 (2004).","DOI":"10.1103\/PhysRevLett.92.127901"},{"key":"30","doi-asserted-by":"publisher","unstructured":"H. Buhrman, R. Cleve, S. Massar, and R. de Wolf, Nonlocality and communication complexity, Rev. Mod. Phys. 82, 665 (2010).","DOI":"10.1103\/RevModPhys.82.665"},{"key":"31","doi-asserted-by":"publisher","unstructured":"M. Navascu\u00e9s, S. Pironio, and A. Ac\u00edn, Bounding the Set of Quantum Correlations, Phys. Rev. Lett. 98, 010401 (2007).","DOI":"10.1103\/PhysRevLett.98.010401"},{"key":"32","doi-asserted-by":"publisher","unstructured":"D. Mart\u00ednez, A. Tavakoli, M. Casanova, G. Ca\u00f1as, B. Marques, and G. Lima, High-Dimensional Quantum Communication Complexity beyond Strategies Based on Bell's Theorem, Phys. Rev. Lett. 121, 150504 (2018).","DOI":"10.1103\/PhysRevLett.121.150504"},{"key":"33","doi-asserted-by":"crossref","unstructured":"L. Vandenberghe and S. Boyd, SIAM Review 38, 49 (1996).","DOI":"10.1137\/1038003"},{"key":"34","doi-asserted-by":"publisher","unstructured":"M. Froissart, Constructive generalization of Bells inequalities, Il Nuovo Cimento B 64, 241 (1981).","DOI":"10.1007\/BF02903286"},{"key":"35","doi-asserted-by":"publisher","unstructured":"D. Collins, and N. Gisin, A Relevant Two Qubit Bell Inequality Inequivalent to the CHSH Inequality, J. Phys. A: Math. Gen. 37 1775 (2004).","DOI":"10.1088\/0305-4470\/37\/5\/021"},{"key":"36","doi-asserted-by":"publisher","unstructured":"R. Horodecki, P. Horodecki and M. Horodecki, Violating Bell inequality by mixed states: necessary and sufficient condition, Phys. Lett. A 200, 340 (1995).","DOI":"10.1016\/0375-9601(95)00214-N"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-09-07-316\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,9,7]],"date-time":"2020-09-07T15:59:52Z","timestamp":1599494392000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-09-07-316\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,7]]},"references-count":37,"URL":"https:\/\/doi.org\/10.22331\/q-2020-09-07-316","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,7]]},"article-number":"316"}}