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

INSPIRE: 3049346
arXiv: 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.