{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T11:27:25Z","timestamp":1784287645771,"version":"3.55.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/T001062\/1"],"award-info":[{"award-number":["EP\/T001062\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme","award":["817581"],"award-info":[{"award-number":["817581"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Quantum computers may achieve speedups over their classical counterparts for solving linear algebra problems. However, in some cases\u2014such as for low-rank matrices\u2014dequantized algorithms demonstrate that there cannot be an exponential quantum speedup. In this work, we show that quantum computers have provable polynomial and exponential speedups in terms of communication complexity for some fundamental linear algebra problems if there is no restriction on the rank. We mainly focus on solving linear regression and Hamiltonian simulation. In the quantum case, the task is to prepare the quantum state of the result. To allow for a fair comparison, in the classical case, the task is to sample from the result. We investigate these two problems in two-party and multiparty models, propose near-optimal quantum protocols, and prove quantum\/classical lower bounds. In this process, we propose an efficient quantum protocol for quantum singular value transformation, which is a powerful technique for designing quantum algorithms. We feel this will be helpful in developing efficient quantum protocols for many other problems.<\/jats:p>","DOI":"10.1145\/3625225","type":"journal-article","created":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T04:34:41Z","timestamp":1695443681000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Quantum Communication Complexity of Linear Regression"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5640-0343","authenticated-orcid":false,"given":"Ashley","family":"Montanaro","sequence":"first","affiliation":[{"name":"School of Mathematics, University of Bristol, Bristol, UK and Phasecraft Ltd., Bristol, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3008-7296","authenticated-orcid":false,"given":"Changpeng","family":"Shao","sequence":"additional","affiliation":[{"name":"School of Mathematics, University of Bristol, Bristol, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,12]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238194"},{"key":"e_1_3_4_3_2","first-page":"636","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912)","volume":"14","author":"Ambainis A.","year":"2012","unstructured":"A. Ambainis. 2012. Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912), Vol. 14. 636\u201347."},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979935476"},{"issue":"9","key":"e_1_3_4_5_2","doi-asserted-by":"crossref","first-page":"090502","DOI":"10.1103\/PhysRevLett.114.090502","article-title":"Simulating Hamiltonian dynamics with a truncated Taylor series","volume":"114","author":"Berry Dominic W.","year":"2015","unstructured":"Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. 2015. Simulating Hamiltonian dynamics with a truncated Taylor series. Phys. Rev. Lett. 114, 9 (2015), 090502.","journal-title":"Phys. Rev. Lett."},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.82.665"},{"key":"e_1_3_4_8_2","first-page":"120","volume-title":"Proceedings of the 16th Annual IEEE Conference on Computational Complexity","author":"Buhrman Harry","year":"2001","unstructured":"Harry Buhrman and Ronald de Wolf. 2001. Communication complexity lower bounds by polynomials. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity. IEEE, 120\u2013130."},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.33"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384314"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1087072"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2022-06-30-754"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316366"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"e_1_3_4_16_2","article-title":"Optimal direct sum and privacy trade-off results for quantum and classical communication complexity","author":"Jain Rahul","year":"2008","unstructured":"Rahul Jain, Pranab Sen, and Jaikumar Radhakrishnan. 2008. Optimal direct sum and privacy trade-off results for quantum and classical communication complexity. arXiv preprint arXiv:0807.1267 (2008).","journal-title":"arXiv preprint arXiv:0807.1267"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483706"},{"key":"e_1_3_4_18_2","volume-title":"Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201920)","author":"Jethwani Dhawal","year":"2020","unstructured":"Dhawal Jethwani, Franccois Le Gall, and Sanjay K. Singh. 2020. Quantum-inspired classical algorithms for singular value transformation. In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201920). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_4_19_2","first-page":"253","volume-title":"Communication Complexity and Lower Bounds for Sequential Computation","author":"Kalyanasundaram Bala","year":"1992","unstructured":"Bala Kalyanasundaram and Georg Schnitger. 1992. Communication Complexity and Lower Bounds for Sequential Computation. Vieweg+Teubner Verlag, Wiesbaden, 253\u2013268."},{"key":"e_1_3_4_20_2","first-page":"31","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing","author":"Klartag Bo\u2019az","year":"2011","unstructured":"Bo\u2019az Klartag and Oded Regev. 2011. Quantum one-way communication can be exponentially stronger than classical communication. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing. 31\u201340."},{"key":"e_1_3_4_21_2","first-page":"644","volume-title":"Proceedings of the 32nd Annual ACM Symposium on Theory of Computing","author":"Klauck Hartmut","year":"2000","unstructured":"Hartmut Klauck. 2000. On quantum and probabilistic communication: Las Vegas and one-way protocols. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. 644\u2013651."},{"key":"e_1_3_4_22_2","article-title":"Quantum communication complexity","author":"Klauck Hartmut","year":"2000","unstructured":"Hartmut Klauck. 2000. Quantum communication complexity. arXiv preprint quant-ph\/0005032 (2000).","journal-title":"arXiv preprint quant-ph\/0005032"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050018"},{"key":"e_1_3_4_24_2","first-page":"254","volume-title":"Proceedings of the 24th Annual IEEE Conference on Computational Complexity","author":"Lee Troy","year":"2009","unstructured":"Troy Lee, Gideon Schechtman, and Adi Shraibman. 2009. Lower bounds on quantum multiparty communication complexity. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity. IEEE, 254\u2013262."},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.2.040203"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-06-28-154"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095158"},{"issue":"425","key":"e_1_3_4_28_2","doi-asserted-by":"crossref","first-page":"181","DOI":"10.2307\/3617890","article-title":"Inconsistent systems of linear equations","volume":"63","author":"Planitz M.","year":"1979","unstructured":"M. Planitz. 1979. Inconsistent systems of linear equations. Math. Gaz. 63, 425 (1979), 181\u2013185.","journal-title":"Math. Gaz."},{"key":"e_1_3_4_29_2","first-page":"358","volume-title":"Proceedings of the 31st Annual ACM Symposium on Theory of Computing","author":"Raz Ran","year":"1999","unstructured":"Ran Raz. 1999. Exponential separation of quantum and classical communication complexity. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing. 358\u2013367."},{"key":"e_1_3_4_30_2","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BFb0032036","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming","author":"Razborov Alexander A.","year":"1990","unstructured":"Alexander A. Razborov. 1990. On the distributional complexity of disjointness. In Proceedings of the International Colloquium on Automata, Languages, and Programming. Springer, 249\u2013253."},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1070\/IM2003v067n01ABEH000422"},{"issue":"4","key":"e_1_3_4_32_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3520141","article-title":"Faster quantum-inspired algorithms for solving linear systems","volume":"3","author":"Shao Changpeng","year":"2022","unstructured":"Changpeng Shao and Ashley Montanaro. 2022. Faster quantum-inspired algorithms for solving linear systems. ACM Trans. Quant. Comput. 3, 4 (2022), 1\u201323.","journal-title":"ACM Trans. Quant. Comput."},{"key":"e_1_3_4_33_2","first-page":"477","volume-title":"Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS\u201912)","author":"Sun Xiaoming","year":"2012","unstructured":"Xiaoming Sun and Chengu Wang. 2012. Randomized communication complexity for linear algebra problems over finite fields. In Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS\u201912). LIPIcs, 477\u2013488."},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316310"},{"key":"e_1_3_4_35_2","article-title":"Communication-efficient quantum algorithm for distributed machine learning","author":"Tang Hao","year":"2022","unstructured":"Hao Tang, Boning Li, Guoqing Wang, Haowei Xu, Changhao Li, Ariel Barr, Paola Cappellaro, and Ju Li. 2022. Communication-efficient quantum algorithm for distributed machine learning. arXiv preprint arXiv:2209.04888 (2022).","journal-title":"arXiv preprint arXiv:2209.04888"},{"key":"e_1_3_4_36_2","first-page":"1733","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Vempala Santosh S.","year":"2020","unstructured":"Santosh S. Vempala, Ruosong Wang, and David P. Woodruff. 2020. The communication complexity of optimization. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1733\u20131752."},{"issue":"1","key":"e_1_3_4_37_2","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0304-3975(02)00377-8","article-title":"Quantum communication and complexity","volume":"287","author":"Wolf Ronald de","year":"2002","unstructured":"Ronald de Wolf. 2002. Quantum communication and complexity. Theor. Comput. Sci. 287, 1 (2002), 337\u2013353.","journal-title":"Theor. Comput. Sci."},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-014-0218-3"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"},{"key":"e_1_3_4_40_2","first-page":"352","volume-title":"Proceedings of the IEEE 34th Annual Foundations of Computer Science","author":"Yao Andrew Chi-Chih","year":"1993","unstructured":"Andrew Chi-Chih Yao. 1993. Quantum circuit complexity. In Proceedings of the IEEE 34th Annual Foundations of Computer Science. IEEE, 352\u2013361."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3625225","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3625225","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:03Z","timestamp":1750287003000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3625225"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1145\/3625225"],"URL":"https:\/\/doi.org\/10.1145\/3625225","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]},"assertion":[{"value":"2022-10-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}