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

Zhang, K; Hsieh, M-H; Liu, L; Tao, D

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

Zhang, K Hsieh, M-H Liu, L Tao, D

Permalink

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.

Adobe PDF

Download full textAdobe PDF (597.42 kB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Zhang, K
dc.contributor.author	Hsieh, M-H
dc.contributor.author	Liu, L
dc.contributor.author	Tao, D
dc.date.accessioned	2023-03-13T23:06:58Z
dc.date.available	2023-03-13T23:06:58Z
dc.date.issued	2019-09-17
dc.identifier.citation	2019
dc.identifier.uri	http://hdl.handle.net/10453/167224
dc.description.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) /{\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.
dc.language	en
dc.rights	info:eu-repo/semantics/openAccess
dc.title	Quantum algorithm for finding the negative curvature direction in non-convex optimization
dc.type	Journal Article
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access	*
dc.date.updated	2023-03-13T23:06:56Z

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) /{\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:

http://hdl.handle.net/10453/167224