Lower bounds for quantum-inspired classical algorithms via communication complexity

Mande, Nikhil S ORCID: 0000-0002-9520-7340 and Shao, Changpeng (2025) Lower bounds for quantum-inspired classical algorithms via communication complexity QUANTUM, 9. p. 1593. ISSN 2521-327X, 2521-327X

PDF REF_MS25_Quantum.pdf - Open Access published version Download (755kB) | Preview

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.

Item Type:	Article
Uncontrolled Keywords:	49 Mathematical Sciences
Divisions:	Faculty of Science & Engineering Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	21 Jan 2025 15:09
Last Modified:	23 May 2026 09:43
DOI:	10.22331/q-2025-01-14-1593
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3189799
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.