Linear regression by quantum amplitude estimation and its extension to convex optimization
Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda, Kazuyoshi Yoshino · Physical Review A · 2021
Linear regression is a basic and widely used methodology in data analysis. It is known that some quantum algorithms efficiently perform least-squares linear regression of an exponentially large dataset. However, if we obtain values of the regression coefficients as classical data, the complexity of the existing quantum algorithms can be larger than the classical method. This is because it depends strongly on the tolerance error $\ensuremath{\epsilon}$: the best one among the existing proposals is $O({\ensuremath{\epsilon}}^{\ensuremath{-}2})$. In this paper, we propose a quantum algorithm for linear regression, which has a complexity of $O({\ensuremath{\epsilon}}^{\ensuremath{-}1})$ and keeps a logarithmic dependence on the number of data points ${N}_{D}$. In this method, we overcome bottleneck parts in the calculation, which take the form of the sum over data points and therefore have a complexity proportional to ${N}_{D}$, using quantum amplitude estimation, and other parts classically. Additionally, we generalize our method to some class of convex optimization problems.