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 (d/) for a class of smooth functions of d variables, where 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 (x) which are well-defined over the complex field. Given phase oracles to query the real and imaginary parts of f (x) respectively, we propose a quantum algorithm that returns an -approximation of its gradient with query complexity O (1/). This achieves exponential speedup over classical algorithms in terms of the dimension d. 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 O (d/) and O (d^1. 5/), respectively, under different assumptions. Moreover, if the Hessian is promised to be s-sparse, we then have two new quantum algorithms with query complexity O (s/) and O (sd/), respectively. The former achieves exponential speedup over classical algorithms. We also prove a lower bound of (d) for Hessian estimation in the general case.