{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T16:13:37Z","timestamp":1774023217607,"version":"3.50.1"},"reference-count":30,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T00:00:00Z","timestamp":1736812800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Key Research Project of China","award":["2023YFA1009403"],"award-info":[{"award-number":["2023YFA1009403"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Quantum-inspired classical algorithms provide us with a new way to understand the computational power of quantum computers for practically-relevant problems, especially in machine learning. In the past several years, numerous efficient algorithms for various tasks have been found, while an analysis of lower bounds is still missing. Using communication complexity, in this work we propose the first method to study lower bounds for these tasks. We mainly focus on lower bounds for solving linear regressions, supervised clustering, principal component analysis, recommendation systems, and Hamiltonian simulations. For those problems, we prove a quadratic lower bound in terms of the Frobenius norm of the underlying matrix. As quantum algorithms are linear in the Frobenius norm for those problems, our results mean that the quantum-classical separation is at least quadratic. As a generalisation, we extend our method to study lower bounds analysis of quantum query algorithms for matrix-related problems using quantum communication complexity. Some applications are given.<\/jats:p>","DOI":"10.22331\/q-2025-01-14-1593","type":"journal-article","created":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T17:53:56Z","timestamp":1736877236000},"page":"1593","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":1,"title":["Lower bounds for quantum-inspired classical algorithms via communication complexity"],"prefix":"10.22331","volume":"9","author":[{"given":"Nikhil S.","family":"Mande","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Liverpool, Liverpool L69 3BX, UK"}]},{"given":"Changpeng","family":"Shao","sequence":"additional","affiliation":[{"name":"Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190 China"}]}],"member":"9598","published-online":{"date-parts":[[2025,1,14]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Ewin Tang. ``A quantum-inspired classical algorithm for recommendation systems''. In Proceedings of the 51st annual ACM SIGACT Symposium on Theory of Computing. Pages 217\u2013228. (2019).","DOI":"10.1145\/3313276.3316310"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Nai-Hui Chia, Andr\u00e1s Pal Gily\u00e9n, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. ``Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning''. Journal of the ACM 69, 1\u201372 (2022).","DOI":"10.1145\/3549524"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Shantanav Chakraborty, Andr\u00e1s Gily\u00e9n, and Stacey Jeffery. ``The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation''. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Volume 132, pages 33:1\u201333:14. (2019).","DOI":"10.4230\/LIPIcs.ICALP.2019.33"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Ainesh Bakshi and Ewin Tang. ``An improved classical singular value transformation for quantum machine learning''. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 2398\u20132453. SIAM (2024).","DOI":"10.1137\/1.9781611977912.86"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Changpeng Shao and Ashley Montanaro. ``Faster quantum-inspired algorithms for solving linear systems''. ACM Transactions on Quantum Computing 3, 1\u201323 (2022).","DOI":"10.1145\/3520141"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, Zhao Song, and Ewin Tang. ``An improved quantum-inspired algorithm for linear regression''. Quantum 6, 754 (2022).","DOI":"10.22331\/q-2022-06-30-754"},{"key":"6","unstructured":"Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. ``Quantum algorithms for supervised and unsupervised machine learning'' (2013). arXiv:1307.0411."},{"key":"7","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis and Anupam Prakash. ``Quantum recommendation systems''. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Page 49:1\u201349:21. (2017).","DOI":"10.4230\/LIPIcs.ITCS.2017.49"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Pages 193\u2013204. (2019).","DOI":"10.1145\/3313276.3316366"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. ``Quantum principal component analysis''. Nature Physics 10, 631\u2013633 (2014).","DOI":"10.1038\/nphys3029"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical Review Letters 103, 150502 (2009).","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Ewin Tang. ``Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions''. Physical Review Letters 127, 060503 (2021).","DOI":"10.1103\/PhysRevLett.127.060503"},{"key":"12","unstructured":"Andr\u00e1s Gily\u00e9n, Seth Lloyd, and Ewin Tang. ``Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension'' (2018). arXiv:1811.04909."},{"key":"13","doi-asserted-by":"publisher","unstructured":"Sevag Gharibian and Fran ccois Le Gall. ``Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum pcp conjecture''. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Pages 19\u201332. (2022).","DOI":"10.1145\/3519935.3519991"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Ashley Montanaro and Changpeng Shao. ``Quantum and classical query complexities of functions of matrices''. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Pages 573\u2013584. (2024).","DOI":"10.1145\/3618260.364966"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Ashley Montanaro and Changpeng Shao. ``Quantum communication complexity of linear regression''. ACM Transactions on Computation Theory 16, 1\u201330 (2024).","DOI":"10.1145\/3625225"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Andrew Chi-Chih Yao. ``Some complexity questions related to distributive computing (preliminary report)''. In Proceedings of the 11th annual ACM Symposium on Theory of Computing. Pages 209\u2013213. (1979).","DOI":"10.1145\/800135.804414"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Ronald de Wolf. ``Quantum communication and complexity''. Theoretical Computer Science 287, 337\u2013353 (2002).","DOI":"10.1016\/S0304-3975(02)00377-8"},{"key":"18","unstructured":"Anup Rao and Amir Yehudayoff. ``Communication complexity: and applications''. Cambridge University Press. Cambridge, U.K. (2020)."},{"key":"19","doi-asserted-by":"publisher","unstructured":"Jeff M Phillips, Elad Verbin, and Qin Zhang. ``Lower bounds for number-in-hand multiparty communication complexity, made easy''. In Proceedings of the twenty-third annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 486\u2013501. SIAM (2012).","DOI":"10.1137\/15M1007525"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Bala Kalyanasundaram and Georg Schintger. ``The probabilistic communication complexity of set intersection''. SIAM Journal on Discrete Mathematics 5, 545\u2013557 (1992).","DOI":"10.1137\/0405044"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Amit Chakrabarti and Oded Regev. ``An optimal lower bound on the communication complexity of gap-hamming-distance''. In Proceedings of the forty-third annual ACM Symposium on Theory of Computing. Pages 51\u201360. (2011).","DOI":"10.1145\/1993636.1993644"},{"key":"22","doi-asserted-by":"publisher","unstructured":"David P Woodruff and Qin Zhang. ``When distributed computation is communication expensive''. Distributed Computing 30, 309\u2013323 (2017).","DOI":"10.1007\/978-3-642-41527-2_2"},{"key":"23","unstructured":"Yi Li, Honghao Lin, and David Woodruff. ``$\\ell_p$-regression in the arbitrary partition model of communication''. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory. Volume 195 of Proceedings of Machine Learning Research, pages 4902\u20134928. PMLR (2023). url: https:\/\/proceedings.mlr.press\/v195\/li23b.html."},{"key":"24","doi-asserted-by":"publisher","unstructured":"Ashley Montanaro. ``Quantum states cannot be transmitted efficiently classically''. Quantum 3, 154 (2019).","DOI":"10.22331\/q-2019-06-28-154"},{"key":"25","unstructured":"Michael A Nielsen and Isaac L Chuang. ``Quantum Computation and Quantum Information''. Cambridge University Press. Cambridge, U.K. (2010)."},{"key":"26","doi-asserted-by":"publisher","unstructured":"Dominic W Berry and Andrew M Childs. ``Black-box Hamiltonian simulation and unitary implementation''. Quantum Information and Computation 12, 29\u201362 (2012).","DOI":"10.26421\/QIC12.1-2-4"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis and Anupam Prakash. ``Quantum Recommendation Systems''. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1\u201349:21. Dagstuhl, Germany (2017). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik.","DOI":"10.4230\/LIPIcs.ITCS.2017.49"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Lov K Grover. ``A fast quantum mechanical algorithm for database search''. In Proceedings of the twenty-eighth annual ACM Symposium on Theory of computing. Pages 212\u2013219. (1996).","DOI":"10.1145\/237814.237866"},{"key":"29","unstructured":"Dong An, Jin-Peng Liu, Daochen Wang, and Qi Zhao. ``A theory of quantum differential equation solvers: limitations and fast-forwarding'' (2022). arXiv:2211.05246."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-01-14-1593\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T17:54:03Z","timestamp":1736877243000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-01-14-1593\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,14]]},"references-count":30,"URL":"https:\/\/doi.org\/10.22331\/q-2025-01-14-1593","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,14]]},"article-number":"1593"}}