我们研究了使用比较Oracle进行光滑函数的梯度测试和估计。给定任意光滑函数 $f:\mathbb R^n\to\mathbb R$，点 $\mathbf{x}\in\mathbb R^n$，以及 $\varepsilon > 0$，我们设计了一种梯度测试算法，该算法通过 $O(1)$ 次查询判断归一化梯度 $\nabla f(\mathbf{x})/\|\nabla f(\mathbf{x})\|$ 是否与给定单位向量 $\mathbf{v}$ 的距离小于 $\varepsilon$ 或大于 $2\varepsilon$。
此外，我们还设计了一种梯度估计算法，通过 $O(n\log(1/\varepsilon))$ 次查询输出 $\nabla f(\mathbf{x})/\|\nabla f(\mathbf{x})\|$ 的 $\varepsilon$ 估计，并证明了其最优性。
我们进一步研究了量子比较Oracle模型中的梯度估计，开发了一种量子算法，使用 $O(\log (n/\varepsilon))$ 次查询。
博主点评： 本文提出的梯度测试和估计算法在查询复杂度上表现出色，尤其是量子模型的应用，展示了量子计算在优化问题中的潜力。这些进展将为未来的研究提供新的思路和工具。