{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T19:24:46Z","timestamp":1780514686936,"version":"3.54.1"},"reference-count":23,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T00:00:00Z","timestamp":1729641600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CIF-1910840"],"award-info":[{"award-number":["CIF-1910840"]}]},{"name":"NSF","award":["CIF-2115200"],"award-info":[{"award-number":["CIF-2115200"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>We consider a quantum and a classical version of a multi-party function computation problem with n players, where players 2,\u2026,n need to communicate appropriate information to player 1 so that a \u201cgeneralized\u201d inner product function with an appropriate promise can be calculated. In the quantum version of the protocol, the players have access to entangled qudits but the communication is still classical. The communication complexity of a given protocol is the total number of classical bits that need to be communicated. When n is prime, and for our chosen function, we exhibit a quantum protocol (with complexity (n\u22121)(logn) bits) and a classical protocol (with complexity ((n\u22121)2(logn2) bits)). Furthermore, we present an integer linear programming formulation for determining a lower bound on the classical communication complexity. This demonstrates that our quantum protocol is strictly better than classical protocols.<\/jats:p>","DOI":"10.3390\/e26110896","type":"journal-article","created":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T09:07:04Z","timestamp":1729674424000},"page":"896","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Communication Complexity of Entanglement-Assisted Multi-Party Computation"],"prefix":"10.3390","volume":"26","author":[{"given":"Ruoyu","family":"Meng","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, Iowa State University, Ames, IA 50011, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3448-1271","authenticated-orcid":false,"given":"Aditya","family":"Ramamoorthy","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Iowa State University, Ames, IA 50011, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2024,10,23]]},"reference":[{"key":"ref_1","unstructured":"Yao, A.C.C. (May, January 30). Some Complexity Questions Related to Distributive Computing(Preliminary Report). Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC \u201979, Atlanta, GA, USA."},{"key":"ref_2","unstructured":"Chi-Chih Yao, A. (1993, January 3\u20135). Quantum circuit complexity. Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, Palo Alto, CA, USA."},{"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":"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_5","doi-asserted-by":"crossref","first-page":"1201","DOI":"10.1103\/PhysRevA.56.1201","article-title":"Substituting quantum entanglement for communication","volume":"56","author":"Cleve","year":"1997","journal-title":"Phys. Rev. A"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0304-3975(02)00377-8","article-title":"Quantum communication and complexity","volume":"287","year":"2002","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1895","DOI":"10.1103\/PhysRevLett.70.1895","article-title":"Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels","volume":"70","author":"Bennett","year":"1993","journal-title":"Phys. Rev. Lett."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., and Wigderson, A. (1998, January 24\u201326). Quantum vs. Classical Communication and Computation. Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC \u201998, Dallas, TX, USA.","DOI":"10.1145\/276698.276713"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.tcs.2012.12.012","article-title":"Quantum entanglement and the communication complexity of the inner product function","volume":"486","author":"Cleve","year":"2013","journal-title":"Theor. Comput. Sci."},{"key":"ref_10","unstructured":"Buhrman, H., and de Wolf, R. (2001, January 18\u201321). Communication Complexity Lower Bounds by Polynomials. Proceedings of the Computational Complexity. Sixteenth Annual IEEE Conference, Los Alamitos, CA, USA."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1070\/IM2003v067n01ABEH000422","article-title":"Quantum communication complexity of symmetric predicates","volume":"67","author":"Razborov","year":"2003","journal-title":"Izv. Math."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1137\/S0097539702405620","article-title":"Lower Bounds for Quantum Communication Complexity","volume":"37","author":"Klauck","year":"2007","journal-title":"SIAM J. Comput."},{"key":"ref_13","unstructured":"van Dam, W., and Hayden, P. (2002). Renyi-entropic bounds on quantum communication. arXiv, Available online: http:\/\/arxiv.org\/abs\/quant-ph\/0204093."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"062608","DOI":"10.1103\/PhysRevA.102.062608","article-title":"Optical quantum communication complexity in the simultaneous-message-passing model","volume":"102","author":"Marwah","year":"2020","journal-title":"Phys. Rev. A"},{"key":"ref_15","unstructured":"Casta neda, A., and Rodr\u00edguez-Henr\u00edquez, F. (2022, January 7\u201311). Bounds on Oblivious Multiparty Quantum Communication Complexity. Proceedings of the LATIN 2022: Theoretical Informatics, Guanajuato, Mexico."},{"key":"ref_16","first-page":"6:1","article-title":"Multiparty Quantum Communication Complexity of Triangle Finding","volume":"Volume 73","author":"Wilde","year":"2018","journal-title":"Proceedings of the 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Lee, T., Schechtman, G., and Shraibman, A. (2009, January 15\u201318). Lower Bounds on Quantum Multiparty Communication Complexity. Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, Paris, France.","DOI":"10.1109\/CCC.2009.24"},{"key":"ref_18","unstructured":"Briet, J., Buhrman, H., Lee, T., and Vidick, T. (2009). Multiplayer XOR games and quantum communication complexity with clique-wise entanglement. arXiv."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2737","DOI":"10.1103\/PhysRevA.60.2737","article-title":"Multiparty quantum communication complexity","volume":"60","author":"Buhrman","year":"1999","journal-title":"Phys. Rev. A"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1088\/1464-4266\/3\/4\/304","article-title":"Three-party quantum communication complexity via entangled tripartite pure states","volume":"3","author":"Xue","year":"2001","journal-title":"J. Opt. B Quantum Semiclass. Opt."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"012318","DOI":"10.1103\/PhysRevA.65.012318","article-title":"Feasible quantum communication complexity protocol","volume":"65","year":"2001","journal-title":"Phys. Rev. A"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/TIT.1956.1056798","article-title":"The zero error capacity of a noisy channel","volume":"2","author":"Shannon","year":"1956","journal-title":"IRE Trans. Inf. Theory"},{"key":"ref_23","unstructured":"(2024, October 18). Python Code for ILP in Sec. V. Available online: https:\/\/github.com\/mengruoyu\/ILP."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/26\/11\/896\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T16:18:43Z","timestamp":1760113123000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/26\/11\/896"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,23]]},"references-count":23,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2024,11]]}},"alternative-id":["e26110896"],"URL":"https:\/\/doi.org\/10.3390\/e26110896","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,23]]}}}