Quantum algorithm for finding the negative curvature direction in non-convex optimization
This provides a potential speedup for non-convex optimization in machine learning and AI, though it is incremental as it builds on existing quantum and classical frameworks.
The paper tackles the problem of escaping saddle points in non-convex optimization by developing a quantum algorithm that finds the negative curvature direction with query complexity O(polylog(d)/ε), exponentially faster than classical methods that require O(d/√ε).
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.