{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T07:39:40Z","timestamp":1747208380503,"version":"3.40.5"},"reference-count":21,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,5,22]],"date-time":"2023-05-22T00:00:00Z","timestamp":1684713600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001381","name":"National Research Foundation, Singapore","doi-asserted-by":"crossref","award":["GrantNRF2021-QEP2-02-P05"],"award-info":[{"award-number":["GrantNRF2021-QEP2-02-P05"]}],"id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education, Singapore","doi-asserted-by":"crossref","award":["Research Centers of Excellence Program"],"award-info":[{"award-number":["Research Centers of Excellence Program"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"crossref"}]},{"name":"MOST Grant","award":["110-2222-E-007-002-MY3"],"award-info":[{"award-number":["110-2222-E-007-002-MY3"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Communication complexity is the amount of communication needed to compute a function when the function inputs are distributed over multiple parties. In its simplest form, one-way communication complexity, Alice and Bob compute a function f<\/mml:mi>(<\/mml:mo>x<\/mml:mi>,<\/mml:mo>y<\/mml:mi>)<\/mml:mo><\/mml:math>, where x<\/mml:mi><\/mml:math> is given to Alice and y<\/mml:mi><\/mml:math> is given to Bob, and only one message from Alice to Bob is allowed. A fundamental question in quantum information is the relationship between one-way quantum and classical communication complexities, i.e., how much shorter the message can be if Alice is sending a quantum state instead of bit strings? We make some progress towards this question with the following results.Let f<\/mml:mi>:<\/mml:mo>X<\/mml:mi><\/mml:mrow>&#x00D7;<\/mml:mo>Y<\/mml:mi><\/mml:mrow>&#x2192;<\/mml:mo>Z<\/mml:mi><\/mml:mrow>&#x222A;<\/mml:mo>{<\/mml:mo>&#x22A5;<\/mml:mi>}<\/mml:mo><\/mml:math> be a partial function and &#x03BC;<\/mml:mi><\/mml:math> be a distribution with support contained in f<\/mml:mi>&#x2212;<\/mml:mo>1<\/mml:mn><\/mml:mrow><\/mml:msup>(<\/mml:mo>Z<\/mml:mi><\/mml:mrow>)<\/mml:mo><\/mml:math>. Denote d<\/mml:mi>=<\/mml:mo>|<\/mml:mo><\/mml:mrow>Z<\/mml:mi><\/mml:mrow>|<\/mml:mo><\/mml:mrow><\/mml:math>. Let R<\/mml:mi><\/mml:mrow>&#x03F5;<\/mml:mi>1<\/mml:mn>,<\/mml:mo>&#x03BC;<\/mml:mi><\/mml:mrow><\/mml:msubsup>(<\/mml:mo>f<\/mml:mi>)<\/mml:mo><\/mml:math> be the classical one-way communication complexity of f<\/mml:mi><\/mml:math>; Q<\/mml:mi><\/mml:mrow>&#x03F5;<\/mml:mi>1<\/mml:mn>,<\/mml:mo>&#x03BC;<\/mml:mi><\/mml:mrow><\/mml:msubsup>(<\/mml:mo>f<\/mml:mi>)<\/mml:mo><\/mml:math> be the quantum one-way communication complexity of f<\/mml:mi><\/mml:math> and Q<\/mml:mi><\/mml:mrow>&#x03F5;<\/mml:mi>1<\/mml:mn>,<\/mml:mo>&#x03BC;<\/mml:mi>,<\/mml:mo>&#x2217;<\/mml:mo><\/mml:mrow><\/mml:msubsup>(<\/mml:mo>f<\/mml:mi>)<\/mml:mo><\/mml:math> be the entanglement-assisted quantum one-way communication complexity of f<\/mml:mi><\/mml:math>, each with distributional error (average error over &#x03BC;<\/mml:mi><\/mml:math>) at most &#x03F5;<\/mml:mi><\/mml:math>. We show:1) If &#x03BC;<\/mml:mi><\/mml:math> is a product distribution, &#x03B7;<\/mml:mi>&#x003E;<\/mml:mo>0<\/mml:mn><\/mml:math> and 0<\/mml:mn>&#x2264;<\/mml:mo>&#x03F5;<\/mml:mi>&#x2264;<\/mml:mo>1<\/mml:mn>&#x2212;<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>d<\/mml:mi><\/mml:math>, then,R<\/mml:mi><\/mml:mrow>2<\/mml:mn>&#x03F5;<\/mml:mi>&#x2212;<\/mml:mo>d<\/mml:mi>&#x03F5;<\/mml:mi>2<\/mml:mn><\/mml:msup>\/<\/mml:mo><\/mml:mrow>(<\/mml:mo>d<\/mml:mi>&#x2212;<\/mml:mo>1<\/mml:mn>)<\/mml:mo>+<\/mml:mo>&#x03B7;<\/mml:mi><\/mml:mrow>1<\/mml:mn>,<\/mml:mo>&#x03BC;<\/mml:mi><\/mml:mrow><\/mml:msubsup>(<\/mml:mo>f<\/mml:mi>)<\/mml:mo>&#x2264;<\/mml:mo>2<\/mml:mn>Q<\/mml:mi><\/mml:mrow>&#x03F5;<\/mml:mi><\/mml:mrow>1<\/mml:mn>,<\/mml:mo>&#x03BC;<\/mml:mi>,<\/mml:mo>&#x2217;<\/mml:mo><\/mml:mrow><\/mml:msubsup>(<\/mml:mo>f<\/mml:mi>)<\/mml:mo>+<\/mml:mo>O<\/mml:mi>(<\/mml:mo>log<\/mml:mi>&#x2061;<\/mml:mo>log<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>&#x03B7;<\/mml:mi>)<\/mml:mo>)<\/mml:mo>.<\/mml:mo><\/mml:math>2)If &#x03BC;<\/mml:mi><\/mml:math> is a non-product distribution and Z<\/mml:mi><\/mml:mrow>=<\/mml:mo>{<\/mml:mo>0<\/mml:mn>,<\/mml:mo>1<\/mml:mn>}<\/mml:mo><\/mml:math>, then &#x2200;<\/mml:mi>&#x03F5;<\/mml:mi>,<\/mml:mo>&#x03B7;<\/mml:mi>&#x003E;<\/mml:mo>0<\/mml:mn><\/mml:math> such that &#x03F5;<\/mml:mi>\/<\/mml:mo><\/mml:mrow>&#x03B7;<\/mml:mi>+<\/mml:mo>&#x03B7;<\/mml:mi>&#x003C;<\/mml:mo>0.5<\/mml:mn><\/mml:math>,R<\/mml:mi><\/mml:mrow>3<\/mml:mn>&#x03B7;<\/mml:mi><\/mml:mrow>1<\/mml:mn>,<\/mml:mo>&#x03BC;<\/mml:mi><\/mml:mrow><\/mml:msubsup>(<\/mml:mo>f<\/mml:mi>)<\/mml:mo>=<\/mml:mo>O<\/mml:mi>(<\/mml:mo>Q<\/mml:mi><\/mml:mrow>&#x03F5;<\/mml:mi><\/mml:mrow>1<\/mml:mn>,<\/mml:mo>&#x03BC;<\/mml:mi><\/mml:mrow><\/mml:msubsup>(<\/mml:mo>f<\/mml:mi>)<\/mml:mo>&#x22C5;<\/mml:mo>C<\/mml:mi>S<\/mml:mi><\/mml:mrow>(<\/mml:mo>f<\/mml:mi>)<\/mml:mo>\/<\/mml:mo><\/mml:mrow>&#x03B7;<\/mml:mi>3<\/mml:mn><\/mml:msup>)<\/mml:mo>,<\/mml:mo><\/mml:math>whereC<\/mml:mi>S<\/mml:mi><\/mml:mrow>(<\/mml:mo>f<\/mml:mi>)<\/mml:mo>=<\/mml:mo>max<\/mml:mo>y<\/mml:mi><\/mml:mrow><\/mml:munder>min<\/mml:mo>z<\/mml:mi>&#x2208;<\/mml:mo>{<\/mml:mo>0<\/mml:mn>,<\/mml:mo>1<\/mml:mn>}<\/mml:mo><\/mml:mrow><\/mml:munder>|<\/mml:mo>{<\/mml:mo>x<\/mml:mi>&#xA0;<\/mml:mtext>|<\/mml:mo><\/mml:mrow>&#xA0;<\/mml:mtext>f<\/mml:mi>(<\/mml:mo>x<\/mml:mi>,<\/mml:mo>y<\/mml:mi>)<\/mml:mo>=<\/mml:mo>z<\/mml:mi>}<\/mml:mo>|<\/mml:mo>.<\/mml:mo><\/mml:math><\/jats:p>","DOI":"10.22331\/q-2023-05-22-1010","type":"journal-article","created":{"date-parts":[[2023,5,22]],"date-time":"2023-05-22T13:17:01Z","timestamp":1684761421000},"page":"1010","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":3,"title":["On relating one-way classical and quantum communication complexities"],"prefix":"10.22331","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6595-572X","authenticated-orcid":false,"given":"Naresh Goud","family":"Boddu","sequence":"first","affiliation":[{"name":"NTT Research, Sunnyvale, California, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Jain","sequence":"additional","affiliation":[{"name":"Centre for Quantum Technologies and Department of Computer Science, National University of Singapore and MajuLab, UMI 3654, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5126-0174","authenticated-orcid":false,"given":"Han-Hsuan","family":"Lin","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2023,5,22]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Andris Ambainis, Ashwin Nayak, Ammon Ta-Shma, and Umesh Vazirani. Dense quantum coding and a lower bound for 1-way quantum automata. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC '99, pages 376\u2013383, New York, USA, 1999. Association for Computing Machinery. ISBN 1581130678. 10.1145\/301250.301347.","DOI":"10.1145\/301250.301347"},{"key":"1","doi-asserted-by":"publisher","unstructured":"H. Barnum and E. Knill. Reversing quantum dynamics with near-optimal quantum and classical fidelity. Journal of Mathematical Physics, 43 (5): 2097\u20132106, 04 2002. ISSN 0022-2488. 10.1063\/1.1459754.","DOI":"10.1063\/1.1459754"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Mario Berta, Matthias Christandl, and Renato Renner. The quantum reverse shannon theorem based on one-shot information theory. Communications in Mathematical Physics, 306 (3): 579\u2013615, 2011. 10.1007\/s00220-011-1309-7.","DOI":"10.1007\/s00220-011-1309-7"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Harry Buhrman, Wim van Dam, Peter H\u00f8yer, and Alain Tapp. Multiparty quantum communication complexity. Physical Review A, 60: 2737\u20132741, October 1999. 10.1103\/PhysRevA.60.2737.","DOI":"10.1103\/PhysRevA.60.2737"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Phys. Rev. Lett., 87: 167902, Sep 2001. 10.1103\/PhysRevLett.87.167902. URL https:\/\/link.aps.org\/doi\/10.1103\/PhysRevLett.87.167902.","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Nilanjana Datta. Min- and max-relative entropies and a new entanglement monotone. IEEE Transactions on Information Theory, 55 (6): 2816\u20132826, June 2009. 10.1109\/tit.2009.2018325. URL https:\/\/doi.org\/10.1109.","DOI":"10.1109\/tit.2009.2018325"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, pages 516\u2013525, New York, USA, 2007. Association for Computing Machinery. ISBN 9781595936318. 10.1145\/1250790.1250866. URL https:\/\/doi.org\/10.1145\/1250790.1250866.","DOI":"10.1145\/1250790.1250866"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16 (10): 1050\u20131057, 2020. ISSN 1745-2481. 10.1038\/s41567-020-0932-7. URL https:\/\/doi.org\/10.1038\/s41567-020-0932-7.","DOI":"10.1038\/s41567-020-0932-7"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Rahul Jain and Shengyu Zhang. New bounds on classical and quantum one-way communication complexity. Theoretical Computer Science, 410 (26): 2463\u20132477, 2009. ISSN 0304-3975. https:\/\/doi.org\/10.1016\/j.tcs.2008.10.014. URL https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397508007627.","DOI":"10.1016\/j.tcs.2008.10.014"},{"key":"9","doi-asserted-by":"crossref","unstructured":"Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. A direct sum theorem in communication complexity via message compression. In Proceedings of the 30th international conference on Automata, languages and programming, ICALP'03, pages 300\u2013315, Berlin, Heidelberg, 2003. Springer-Verlag. ISBN 3-540-40493-7. URL http:\/\/dl.acm.org\/citation.cfm?id=1759210.1759242.","DOI":"10.1007\/3-540-45061-0_26"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. Prior entanglement, message compression and privacy in quantum communication. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pages 285\u2013296, Washington, DC, USA, 2005. IEEE Computer Society. ISBN 0-7695-2364-1. 10.1109\/CCC.2005.24. URL http:\/\/dl.acm.org\/citation.cfm?id=1068502.1068658.","DOI":"10.1109\/CCC.2005.24"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Rahul Jain, Hartmut Klauck, and Ashwin Nayak. Direct product theorems for classical communication complexity via subdistribution bounds: Extended abstract. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, pages 599\u2013608, New York, USA, 2008. Association for Computing Machinery. ISBN 9781605580470. 10.1145\/1374376.1374462. URL https:\/\/doi.org\/10.1145\/1374376.1374462.","DOI":"10.1145\/1374376.1374462"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Robert T. Konig and Barbara M. Terhal. The bounded-storage model in the presence of a quantum adversary. IEEE Transactions on Information Theory, 54 (2): 749\u2013762, 2008. 10.1109\/TIT.2007.913245.","DOI":"10.1109\/TIT.2007.913245"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC '95, pages 596\u2013605, New York, USA, 1995. Association for Computing Machinery. ISBN 0897917189. 10.1145\/225058.225277. URL https:\/\/doi.org\/10.1145\/225058.225277.","DOI":"10.1145\/225058.225277"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1996. 10.1017\/CBO9780511574948.","DOI":"10.1017\/CBO9780511574948"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Joseph M. Renes. Better bounds on optimal measurement and entanglement recovery, with applications to uncertainty and monogamy relations. Phys. Rev. A, 96: 042328, Oct 2017. 10.1103\/PhysRevA.96.042328. URL https:\/\/link.aps.org\/doi\/10.1103\/PhysRevA.96.042328.","DOI":"10.1103\/PhysRevA.96.042328"},{"key":"16","doi-asserted-by":"publisher","unstructured":"John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. 10.1017\/9781316848142.","DOI":"10.1017\/9781316848142"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Mark M. Wilde. Quantum Information Theory. Cambridge University Press, 2012. ISBN 9781139525343. 10.1017\/CBO9781139525343.","DOI":"10.1017\/CBO9781139525343"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Andrew Chi-Chih Yao. Some complexity questions related to distributive computing(preliminary report). In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, pages 209\u2013213, New York, USA, 1979. Association for Computing Machinery. ISBN 9781450374385. 10.1145\/800135.804414. URL https:\/\/doi.org\/10.1145\/800135.804414.","DOI":"10.1145\/800135.804414"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Andrew Chi-Chih Yao. Quantum circuit complexity. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 352\u2013361, 1993. 10.1109\/SFCS.1993.366852.","DOI":"10.1109\/SFCS.1993.366852"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 222\u2013227, 1977. 10.1109\/SFCS.1977.24.","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-05-22-1010\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,5,22]],"date-time":"2023-05-22T13:17:11Z","timestamp":1684761431000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-05-22-1010\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,22]]},"references-count":21,"URL":"https:\/\/doi.org\/10.22331\/q-2023-05-22-1010","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"type":"electronic","value":"2521-327X"}],"subject":[],"published":{"date-parts":[[2023,5,22]]},"article-number":"1010"}}