  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 data set. 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 $\epsilon$: the best one among the
existing proposals is $O(\epsilon^{-2})$. In this paper, we propose the new
quantum algorithm for linear regression, which has the complexity of
$O(\epsilon^{-1})$ and keeps the 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 the
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.
