We use a few cookies

Essential cookies keep the library working. With your permission, we'd also like to use analytics to see what's useful and improve the experience. Read our Privacy Policy or Cookie Policy.

Skip to main content
Home/e-Resources/Physics/Quantum algorithms for escaping from saddle points
PeriodicalsPhysics

Quantum algorithms for escaping from saddle points

arXiv2020

Checking your access to this record.

Abstract & Overview

We initiate the study of quantum algorithms for escaping from saddle points with provable guarantee. Given a function $f\colon\mathbb{R}^{n}\to\mathbb{R}$, our quantum algorithm outputs an $ε$-approximate second-order stationary point using $\tilde{O}(\log^{2} (n)/ε^{1.75})$ queries to the quantum evaluation oracle (i.e., the zeroth-order oracle). Compared to the classical state-of-the-art algorithm by Jin et al. with $\tilde{O}(\log^{6} (n)/ε^{1.75})$ queries to the gradient oracle (i.e., the first-order oracle), our quantum algorithm is polynomially better in terms of $\log n$ and matches its complexity in terms of $1/ε$. Technically, our main contribution is the idea of replacing the classical perturbations in gradient descent methods by simulating quantum wave equations, which constitutes the improvement in the quantum query complexity with $\log n$ factors for escaping from saddle points. We also show how to use a quantum gradient computation algorithm due to Jordan to replace the classical gradient queries by quantum evaluation queries with the same complexity. Finally, we also perform numerical experiments that support our theoretical findings.

Cite this record

Chenyi Zhang, Jiaqi Leng, Tongyang Li (2020). Quantum algorithms for escaping from saddle points. arXiv. https://library.shubhaarti.com/content/cf85ecfc-e3ee-4feb-a699-5f0dbd522e16

Copy in another style

Zhang, C., Leng, J., & Li, T. (2020). Quantum algorithms for escaping from saddle points. arXiv. https://library.shubhaarti.com/content/cf85ecfc-e3ee-4feb-a699-5f0dbd522e16
Author names are used as deposited, so check their order before you submit.

Metadata is harvested from open-access indexes and can be incomplete. Check a citation against the published version before relying on it — see our open access & attribution policy.