Quantum algorithm for finding the negative curvature direction in non-convex optimization
- Publication Type:
- Journal Article
- Citation:
- 2019
- Issue Date:
- 2019-09-17
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
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) /{\epsilon}), 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{\epsilon}). 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.
Please use this identifier to cite or link to this item: