# Quantum spectral method for gradient and Hessian estimation

arXiv: https://arxiv.org/abs/2407.03833 · HTML: https://mlsanity.com/paper/2407.03833/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jul 2024.

## Built on by (most cited first, 1 of 1)

- [Quantum Deep Learning Still Needs a Quantum Leap](https://mlsanity.com/paper/2511.01253/) (2025)

## Abstract (arXiv)

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.