{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:06:05Z","timestamp":1760234765840,"version":"build-2065373602"},"reference-count":35,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2021,6,13]],"date-time":"2021-06-13T00:00:00Z","timestamp":1623542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Communication games are crucial tools for investigating the limitations of physical theories. The communication complexity (CC) problem is a typical example, for which several distributed parties attempt to jointly calculate a given function with limited classical communications. In this work, we present a method to construct CC problems from Bell tests in a graph-theoretic way. Starting from an experimental compatibility graph and the corresponding Bell test function, a target function that encodes the information of each edge can be constructed; then, using this target function, we can construct a CC function, and by pre-sharing entangled states, its success probability exceeds that of the arbitrary classical strategy. The non-signaling protocol based on the Popescu\u2013Rohrlich box is also discussed, and the success probability in this case reaches one.<\/jats:p>","DOI":"10.3390\/e23060744","type":"journal-article","created":{"date-parts":[[2021,6,14]],"date-time":"2021-06-14T10:30:25Z","timestamp":1623666625000},"page":"744","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Quantum Advantages of Communication Complexity from Bell Nonlocality"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8588-173X","authenticated-orcid":false,"given":"Zhih-Ahn","family":"Jia","sequence":"first","affiliation":[{"name":"CAS Key Laboratory of Quantum Information, School of Physical Sciences, University of Science and Technology of China, Hefei 230026, China"},{"name":"CAS Center For Excellence in Quantum Information and Quantum Physics, University of Science and Technology of China, Hefei 230026, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Wei","sequence":"additional","affiliation":[{"name":"School of the Gifted Young, University of Science and Technology of China, Hefei 230026, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu-Chun","family":"Wu","sequence":"additional","affiliation":[{"name":"CAS Key Laboratory of Quantum Information, School of Physical Sciences, University of Science and Technology of China, Hefei 230026, China"},{"name":"CAS Center For Excellence in Quantum Information and Quantum Physics, University of Science and Technology of China, Hefei 230026, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guang-Can","family":"Guo","sequence":"additional","affiliation":[{"name":"CAS Key Laboratory of Quantum Information, School of Physical Sciences, University of Science and Technology of China, Hefei 230026, China"},{"name":"CAS Center For Excellence in Quantum Information and Quantum Physics, University of Science and Technology of China, Hefei 230026, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,6,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1103\/PhysRev.47.777","article-title":"Can quantum-mechanical description of physical reality be considered complete?","volume":"47","author":"Einstein","year":"1935","journal-title":"Phys. Rev."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195","article-title":"On the Einstein Podolsky Rosen paradox","volume":"1","author":"Bell","year":"1964","journal-title":"Physics"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1103\/RevModPhys.81.865","article-title":"Quantum entanglement","volume":"81","author":"Horodecki","year":"2009","journal-title":"Rev. Mod. Phys."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1103\/RevModPhys.86.419","article-title":"Bell nonlocality","volume":"86","author":"Brunner","year":"2014","journal-title":"Rev. Mod. Phys."},{"key":"ref_5","unstructured":"Nielsen, M.A., and Chuang, I.L. (2010). Quantum Computation and Quantum Information, Cambridge University Press."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1103\/PhysRevLett.67.661","article-title":"Quantum cryptography based on Bell\u2019s theorem","volume":"67","author":"Ekert","year":"1991","journal-title":"Phys. Rev. Lett."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"015004","DOI":"10.1103\/RevModPhys.89.015004","article-title":"Quantum random number generators","volume":"89","year":"2017","journal-title":"Rev. Mod. Phys."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1103\/RevModPhys.82.665","article-title":"Nonlocality and communication complexity","volume":"82","author":"Buhrman","year":"2010","journal-title":"Rev. Mod. Phys."},{"key":"ref_9","unstructured":"Yao, A.C.C. Some Complexity Questions Related to Distributive Computing (Preliminary Report). Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"127901","DOI":"10.1103\/PhysRevLett.92.127901","article-title":"Bell\u2019s Inequalities and Quantum Communication Complexity","volume":"92","author":"Brukner","year":"2004","journal-title":"Phys. Rev. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Degorre, J., Kaplan, M., Laplante, S., and Roland, J. (2009). The communication complexity of non-signaling distributions. International Symposium on Mathematical Foundations of Computer Science, Springer.","DOI":"10.1007\/978-3-642-03816-7_24"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/s11128-018-1883-0","article-title":"Classical versus quantum communication in XOR games","volume":"17","author":"Junge","year":"2018","journal-title":"Quantum Inf. Process."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"316","DOI":"10.22331\/q-2020-09-07-316","article-title":"Does violation of a Bell inequality always imply quantum advantage in a communication complexity problem?","volume":"4","author":"Tavakoli","year":"2020","journal-title":"Quantum"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"3191","DOI":"10.1073\/pnas.1507647113","article-title":"Quantum communication complexity advantage implies violation of a Bell inequality","volume":"113","author":"Buhrman","year":"2016","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"72","DOI":"10.22331\/q-2018-06-07-72","article-title":"Robust Bell inequalities from communication complexity","volume":"2","author":"Laplante","year":"2018","journal-title":"Quantum"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"880","DOI":"10.1103\/PhysRevLett.23.880","article-title":"Proposed Experiment to Test Local Hidden-Variable Theories","volume":"23","author":"Clauser","year":"1969","journal-title":"Phys. Rev. Lett."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"012111","DOI":"10.1103\/PhysRevA.94.012111","article-title":"Monogamy relation in no-disturbance theories","volume":"94","author":"Jia","year":"2016","journal-title":"Phys. Rev. A"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF02058098","article-title":"Quantum nonlocality as an axiom","volume":"24","author":"Popescu","year":"1994","journal-title":"Found. Phys."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"050404","DOI":"10.1103\/PhysRevLett.109.050404","article-title":"Generalized Monogamy of Contextual Inequalities from the No-Disturbance Principle","volume":"109","author":"Ramanathan","year":"2012","journal-title":"Phys. Rev. Lett."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1137\/1108047","article-title":"Markov measures and Markov extensions","volume":"8","year":"1963","journal-title":"Probab. Theory Appl."},{"key":"ref_21","first-page":"289","article-title":"Coalitional games","volume":"12","year":"1967","journal-title":"Probab. Theory Appl."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1103\/PhysRevLett.48.291","article-title":"Hidden Variables, Joint Probability, and the Bell Inequalities","volume":"48","author":"Fine","year":"1982","journal-title":"Phys. Rev. Lett."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"020103","DOI":"10.1103\/PhysRevA.99.020103","article-title":"Necessary and sufficient condition for contextuality from incompatibility","volume":"99","author":"Xu","year":"2019","journal-title":"Phys. Rev. A"},{"key":"ref_24","unstructured":"Jia, Z.A., Cai, G.D., Wu, Y.C., Guo, G.C., and Cabello, A. (2017). The Exclusivity Principle Determines the Correlation Monogamy. arXiv."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"052128","DOI":"10.1103\/PhysRevA.97.052128","article-title":"Entropic no-disturbance as a physical principle","volume":"97","author":"Jia","year":"2018","journal-title":"Phys. Rev. A"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"662","DOI":"10.1103\/PhysRevLett.61.662","article-title":"Information-theoretic Bell inequalities","volume":"61","author":"Braunstein","year":"1988","journal-title":"Phys. Rev. Lett."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"022110","DOI":"10.1103\/PhysRevA.73.022110","article-title":"Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities","volume":"73","author":"Wehner","year":"2006","journal-title":"Phys. Rev. A"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"040401","DOI":"10.1103\/PhysRevLett.112.040401","article-title":"Graph-Theoretic Approach to Quantum Correlations","volume":"112","author":"Cabello","year":"2014","journal-title":"Phys. Rev. Lett."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., and Nisan, N. (1996). Communication Complexity, Cambridge University Press.","DOI":"10.1017\/CBO9780511574948"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Arora, S., and Barak, B. (2009). Computational Complexity: A Modern Approach, Cambridge University Press.","DOI":"10.1017\/CBO9780511804090"},{"key":"ref_31","unstructured":"Hromkovi\u010d, J. (2013). Communication Complexity and Parallel Computing, Springer Science & Business Media."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1829","DOI":"10.1137\/S0097539797324886","article-title":"Quantum entanglement and communication complexity","volume":"30","author":"Buhrman","year":"2001","journal-title":"SIAM J. Comput."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"187904","DOI":"10.1103\/PhysRevLett.91.187904","article-title":"Communication cost of simulating bell correlations","volume":"91","author":"Toner","year":"2003","journal-title":"Phys. Rev. Lett."},{"key":"ref_34","unstructured":"Van Dam, W. (2005). Implausible consequences of superstrong nonlocality. arXiv."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"250401","DOI":"10.1103\/PhysRevLett.96.250401","article-title":"Limit on nonlocality in any world in which communication complexity is not trivial","volume":"96","author":"Brassard","year":"2006","journal-title":"Phys. Rev. Lett."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/6\/744\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:13:56Z","timestamp":1760163236000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/6\/744"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,13]]},"references-count":35,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,6]]}},"alternative-id":["e23060744"],"URL":"https:\/\/doi.org\/10.3390\/e23060744","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,6,13]]}}}