  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.
