Quantum spectral method for gradient and Hessian estimation

Abstract

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én, Arunachalam, and Wiebe, SODA, pp. 1425-1444, 2019], providing a quantum algorithm with optimal query complexity $\tilde{\hat{I}}˜(\sqrt{d}/\epsilon )$ for a class of smooth functions of $d$ variables, where $\epsilon$ 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(\mathbf{x})$ which are well-defined over the complex field. Given phase oracles to query the real and imaginary parts of $f(\mathbf{x})$ respectively, we propose a quantum algorithm that returns an $\epsilon$-approximation of its gradient with query complexity $\tilde{O}(1/\epsilon )$. 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 $\tilde{O}(d/\epsilon )$ and $\tilde{O}(d^{1.5}/\epsilon )$, respectively, under different assumptions. Moreover, if the Hessian is promised to be $s$-sparse, we then have two new quantum algorithms with query complexity $\tilde{O}(s/\epsilon )$ and $\tilde{O}(sd/\epsilon )$, respectively. We also prove a lower bound of $\tilde{\hat{I}}\text{c◯}(d)$ for Hessian estimation in the general case.