论文标题
非convex优化的量子算法的鲁棒性
Robustness of Quantum Algorithms for Nonconvex Optimization
论文作者
论文摘要
最近的结果表明，量子计算机具有加快非凸优化问题的潜力。但是，实施量子优化算法的关键因素是它们针对实验和统计噪声的鲁棒性。在本文中，我们系统地研究了寻找$ε$ - 二阶固定点（$ε$ -sosp）的量子算法，这些算法是$ d $ d $二维的非convex功能，这是非convex优化中的基本问题，具有嘈杂的Zeroth-Zeroth-或一阶oracles或一阶oracles。我们首先证明，最多可达到$ o（ε^{10}/d^5）$的噪声，加速了带量子梯度估计的摄入梯度下降，需要$ o（\ log d/ε^{1.75}）$量子查询以找到$ε$ -SOSP。然后，我们证明，在$ o（ε^6/d^4）$和$ o（ε/d^{0.5+ζ}）$ $ o（ε^6/d^4）的噪音中，分别为$ζ> 0 $ $ o（ε^6/d^4）$（ε^6/d^4）$（ε/d^{0.5+ζ}）$，分别为$ζ> 0 $，分别提供了量子algorithm a Quantum algorithm具有多重质量的Query Query Query Query Query Query Query Query Query。然后，我们使用量子平均噪声平滑的量子平均估计提出了一种随机梯度下降算法，该量子的噪音平滑，这是鲁棒至$ o（ε^{1.5}/d）$和$ O（ε/\ sqrt {d}）$的$（ε^{1.5}/d）$。量子算法取$ O（d^{2.5}/ε^{3.5}）$和$ o（d^2/ε^3）$对两个Oracles的查询，对经典对话者提供了多项式加速。此外，我们表征了量子算法可以在$ d $中找到的$ε$ -SOSP，其中包括$ d $ $ d $的查询数量，或者问题在理论上是信息在理论上是无法解决的。此外，对于任何随机的经典和量子算法，我们证明了$ω（ε^{ - 12/7}）$下限$ε$，以使用嘈杂的零零或一阶式甲壳来找到$ε$ -SOSP。
Recent results suggest that quantum computers possess the potential to speed up nonconvex optimization problems. However, a crucial factor for the implementation of quantum optimization algorithms is their robustness against experimental and statistical noises. In this paper, we systematically study quantum algorithms for finding an $ε$-approximate second-order stationary point ($ε$-SOSP) of a $d$-dimensional nonconvex function, a fundamental problem in nonconvex optimization, with noisy zeroth- or first-order oracles as inputs. We first prove that, up to noise of $O(ε^{10}/d^5)$, accelerated perturbed gradient descent with quantum gradient estimation takes $O(\log d/ε^{1.75})$ quantum queries to find an $ε$-SOSP. We then prove that perturbed gradient descent is robust to the noise of $O(ε^6/d^4)$ and $O(ε/d^{0.5+ζ})$ for $ζ>0$ on the zeroth- and first-order oracles, respectively, which provides a quantum algorithm with poly-logarithmic query complexity. We then propose a stochastic gradient descent algorithm using quantum mean estimation on the Gaussian smoothing of noisy oracles, which is robust to $O(ε^{1.5}/d)$ and $O(ε/\sqrt{d})$ noise on the zeroth- and first-order oracles, respectively. The quantum algorithm takes $O(d^{2.5}/ε^{3.5})$ and $O(d^2/ε^3)$ queries to the two oracles, giving a polynomial speedup over the classical counterparts. Moreover, we characterize the domains where quantum algorithms can find an $ε$-SOSP with poly-logarithmic, polynomial, or exponential number of queries in $d$, or the problem is information-theoretically unsolvable even by an infinite number of queries. In addition, we prove an $Ω(ε^{-12/7})$ lower bound in $ε$ for any randomized classical and quantum algorithm to find an $ε$-SOSP using either noisy zeroth- or first-order oracles.
