Quantum spectral method for gradient and Hessian estimation

Gradient descent is one of the most basic algorithms for solving continuous optimization problems. In [Jordan, PRL, 95(5):050501, 2005], Jordan proposed the first quantum algorithm for estimating gradients of functions close to linear, with exponential speedup in the black-box model. This quantum algorithm was greatly enhanced and developed by [Gily'en, Arunachalam, and Wiebe, SODA, pp. 1425-1444, 2019], providing a quantum algorithm with optimal query complexity widetildeTheta(√d/varepsilon) for a class of smooth functions of d variables, where varepsilon is the accuracy. This is quadratically faster than classical algorithms for the same problem. In this work, we continue this research by proposing a new quantum algorithm for another class of functions, namely, analytic functions f(boldsymbolx) which are well-defined over the complex field. Given phase oracles to query the real and imaginary parts of f(boldsymbolx) respectively, we propose a quantum algorithm that returns an varepsilon-approximation of its gradient with query complexity widetildeO(1/varepsilon). As an extension, we also propose two quantum algorithms for Hessian estimation, aiming to improve quantum analogs of Newton's method. The two algorithms have query complexity widetildeO(d/varepsilon) and widetildeO(d1.5/varepsilon), respectively, under different assumptions. Moreover, if the Hessian is promised to be s-sparse, we then have two new quantum algorithms with query complexity widetildeO(s/varepsilon) and widetildeO(sd/varepsilon), respectively. We also prove a lower bound of widetildeOmega(d) for Hessian estimation in the general case.