论文标题
量子下限，用于查找非凸功能的固定点
Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions
论文作者
论文摘要
优化问题的量子算法是普遍关注的。尽管在不同设置和凸优化的量子下限下，在经典的下限中进行了经典下限的最新进展，但非convex优化的量子下限仍然广泛开放。在本文中，我们对量子查询下限进行了系统研究，以查找$ε$ - 非convex函数的固定点，我们考虑以下两个重要设置：1）可以访问$ p $ th订单衍生品；或2）可以使用随机梯度。在第一个设置中，经典查询的下限为$ω\ big（ε^{ - \ frac {1+p} {p}} \ big）$，而第二个设置（或$ω（或$ω（ε^{ - 3}）$，If $ω（ε^{ - 4}）$ IF $ω（ε^{ - 3}）$均为均匀的平稳函数。在本文中，我们将所有这些经典的下限扩展到量子设置。它们分别匹配经典算法结果，表明没有或没有均值平滑度假设的$ p $ thorder阶导数输入或随机梯度输入的非convex函数的$ε$定位点或随机梯度输入。从技术上讲，我们的量子下限是通过证明所有这些设置中经典硬实例的顺序性质也适用于量子查询的，从而阻止了除了依次揭示固定点的信息之外的任何量子加速。
Quantum algorithms for optimization problems are of general interest. Despite recent progress in classical lower bounds for nonconvex optimization under different settings and quantum lower bounds for convex optimization, quantum lower bounds for nonconvex optimization are still widely open. In this paper, we conduct a systematic study of quantum query lower bounds on finding $ε$-approximate stationary points of nonconvex functions, and we consider the following two important settings: 1) having access to $p$-th order derivatives; or 2) having access to stochastic gradients. The classical query lower bounds is $Ω\big(ε^{-\frac{1+p}{p}}\big)$ regarding the first setting, and $Ω(ε^{-4})$ regarding the second setting (or $Ω(ε^{-3})$ if the stochastic gradient function is mean-squared smooth). In this paper, we extend all these classical lower bounds to the quantum setting. They match the classical algorithmic results respectively, demonstrating that there is no quantum speedup for finding $ε$-stationary points of nonconvex functions with $p$-th order derivative inputs or stochastic gradient inputs, whether with or without the mean-squared smoothness assumption. Technically, our quantum lower bounds are obtained by showing that the sequential nature of classical hard instances in all these settings also applies to quantum queries, preventing any quantum speedup other than revealing information of the stationary points sequentially.
