Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters

Abstract

Linear regression is one of the most fundamental linear algebra problems. Given a dense matrix A R^n d and a vector b, the goal is to find x' such that \| Ax' - b \|_2^2 (1+) _x \| A x - b \|_2^2 . The best classical algorithm takes O(nd) + poly(d/) time [Clarkson and Woodruff STOC 2013, Nelson and Nguyen FOCS 2013]. On the other hand, quantum linear regression algorithms can achieve exponential quantum speedups, as shown in [Wang Phys. Rev. A 96, 012335, Kerenidis and Prakash ITCS 2017, Chakraborty, Gily\'en and Jeffery ICALP 2019]. However, the running times of these algorithms depend on some quantum linear algebra-related parameters, such as (A), the condition number of A. In this work, we develop a quantum algorithm that runs in O(^-1nd^1.5) + poly(d/) time. It provides a quadratic quantum speedup in n over the classical lower bound without any dependence on data-dependent parameters. In addition, we also show our result can be generalized to multiple regression and ridge linear regression.

Tasks

Reproductions