Lower bounds for quantum-inspired classical algorithms via communication complexity

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.

20 pages, final version

References in corpus (8)

• Quantum algorithm for solving linear systems of equations
• Quantum principal component analysis
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• A quantum-inspired classical algorithm for recommendation systems
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• An improved quantum-inspired algorithm for linear regression
• Quantum states cannot be transmitted efficiently classically