# Quantum algorithm for finding the negative curvature direction in non-convex optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Sep 2019.

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

- [On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks](https://mlsanity.com/paper/2209.14501/) (2022)

## Abstract (arXiv)

We present an efficient quantum algorithm aiming to find the negative curvature direction for escaping the saddle point, which is the critical subroutine for many second-order non-convex optimization algorithms. We prove that our algorithm could produce the target state corresponding to the negative curvature direction with query complexity O(polylog(d) /ε), where d is the dimension of the optimization function. The quantum negative curvature finding algorithm is exponentially faster than any known classical method which takes time at least O(d /√ε). Moreover, we propose an efficient quantum algorithm to achieve the classical read-out of the target state. Our classical read-out algorithm runs exponentially faster on the degree of d than existing counterparts.