Quantum Spectral Method for Gradient and Hessian Estimation

Quantum Scientific Computation and Quantum Artificial Intelligence

Organizer：

Jin-Peng Liu 刘锦鹏

Speaker：

Yuxin Zhang (AMSS)

Time：

Tues., 13:30-14:30

Dec. 31, 2024

Venue：

B626, Shuangqing Complex Building A

Title：

Quantum Spectral Method for Gradient and Hessian Estimation

Abstract:

Gradient and Hessian estimation of multivariable functions plays a vital role across a wide range of fields, including optimization problems, machine learning, and others.

In this talk, we begin by revisiting the gradient estimation algorithms proposed by Jordan in 2005 and further improved by Gilyén, Arunachalam, and Wiebe in 2019, based on the finite difference method. We will then introduce our novel quantum algorithm for gradient estimation based on the spectral method, which achieves exponential speedup over classical algorithms in terms of the dimension d. As an extension, quantum algorithms for Hessian estimation are developed using either finite difference method or spectral method. We show that our quantum spectral method for Hessian estimation is optimal in terms of dimension d by proving a nontrivial lower bound.

Furthermore, when the Hessian is sparse, we can obtain better results.

References:

[Jor05] Stephen Jordan. Fast quantum algorithm for numerical gradient estimation. PRL, 2005.

[GAW19] András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe. Optimizing quantum optimization algorithms via faster quantum gradient computation. SODA, 2019.

[ZS24] Yuxin Zhang, and Changpeng Shao. Quantum spectral method for gradient and Hessian estimation. arXiv:2407.03833, 2024.

Speaker: Yuxin Zhang is a PhD student at the Academy of Mathematics and Systems Science, Chinese Academy of Sciences. Her research interests include quantum algorithms, quantum complexity theory, and other intriguing fields yet to be explored.