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

**INSPIRE:** [3049346](https://inspirehep.net/literature/3049346)
**arXiv:** [1909\.07622](https://arxiv.org/abs/1909.07622)

**Authors:** Zhang, Kaining, Hsieh, Min\-Hsiu, Liu Liu, Tao, Dacheng

**Submitted:** 17 September 2019

**Subjects:**
- quant\-ph
- cs\.LG
- Quantum Physics
- Computing

**Citations:** 3

## Abstract

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 /\\sqrtε\)\. 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\.