Finite-sum optimization has wide applications in machine learning, covering
important problems such as support vector machines, regression, etc. In this
paper, we initiate the study of solving finite-sum optimization problems by
quantum computing. Specifically, let
$f_1,\ldots,f_n\colon\mathbb{R}^d\to\mathbb{R}$ be $\ell$-smooth convex
functions and $\psi\colon\mathbb{R}^d\to\mathbb{R}$ be a $\mu$-strongly convex
proximal function. The goal is to find an $\epsilon$-optimal point for
$F(\mathbf{x})=\frac{1}{n}\sum_{i=1}^n f_i(\mathbf{x})+\psi(\mathbf{x})$. We
give a quantum algorithm with complexity
$\tilde{O}\big(n+\sqrt{d}+\sqrt{\ell/\mu}\big(n^{1/3}d^{1/3}+n^{-2/3}d^{5/6}\big)\big)$,
improving the classical tight bound
$\tilde{\Theta}\big(n+\sqrt{n\ell/\mu}\big)$. We also prove a quantum lower
bound $\tilde{\Omega}(n+n^{3/4}(\ell/\mu)^{1/4})$ when $d$ is large enough.
Both our quantum upper and lower bounds can extend to the cases where $\psi$ is
not necessarily strongly convex, or each $f_i$ is Lipschitz but not necessarily
smooth. In addition, when $F$ is nonconvex, our quantum algorithm can find an
$\epsilon$-critial point using
$\tilde{O}(n+\ell(d^{1/3}n^{1/3}+\sqrt{d})/\epsilon^2)$ queries.

通过量子计算，我们提出了一个具有改进复杂性的量子算法来解决有限和优化问题，使得我们可以找到一个 ε- 最优解点。