{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T12:36:29Z","timestamp":1783082189382,"version":"3.54.6"},"reference-count":77,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,8,20]],"date-time":"2021-08-20T00:00:00Z","timestamp":1629417600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["CCF-1816695"],"award-info":[{"award-number":["CCF-1816695"]}]},{"name":"IBM","award":["IBM PhD Fellowship"],"award-info":[{"award-number":["IBM PhD Fellowship"]}]},{"name":"National Science Foundation","award":["DMR-1747426"],"award-info":[{"award-number":["DMR-1747426"]}]},{"name":"National Science Foundation","award":["PHY-1818914"],"award-info":[{"award-number":["PHY-1818914"]}]},{"name":"U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research","award":["Quantum Algorithms Teams program"],"award-info":[{"award-number":["Quantum Algorithms Teams program"]}]},{"DOI":"10.13039\/100004358","name":"Samsung","doi-asserted-by":"crossref","award":["Samsung Advanced Institute of Technology Global Research Partnership"],"award-info":[{"award-number":["Samsung Advanced Institute of Technology Global Research Partnership"]}],"id":[{"id":"10.13039\/100004358","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"We initiate the study of quantum algorithms for escaping from saddle points with provable guarantee. Given a functionf<\/mml:mi>:<\/mml:mo>R<\/mml:mi><\/mml:mrow>n<\/mml:mi><\/mml:mrow><\/mml:msup>\u2192<\/mml:mo>R<\/mml:mi><\/mml:mrow><\/mml:math>, our quantum algorithm outputs an\u03f5<\/mml:mi><\/mml:math>-approximate second-order stationary point usingO<\/mml:mi>~<\/mml:mo><\/mml:mover><\/mml:mrow>(<\/mml:mo>log<\/mml:mi>2<\/mml:mn><\/mml:mrow><\/mml:msup>\u2061<\/mml:mo>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo>\/<\/mml:mo><\/mml:mrow>\u03f5<\/mml:mi>1.75<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math>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. withO<\/mml:mi>~<\/mml:mo><\/mml:mover><\/mml:mrow>(<\/mml:mo>log<\/mml:mi>6<\/mml:mn><\/mml:mrow><\/mml:msup>\u2061<\/mml:mo>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo>\/<\/mml:mo><\/mml:mrow>\u03f5<\/mml:mi>1.75<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math>queries to the gradient oracle (i.e., the first-order oracle), our quantum algorithm is polynomially better in terms oflog<\/mml:mi>\u2061<\/mml:mo>n<\/mml:mi><\/mml:math>and matches its complexity in terms of1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>\u03f5<\/mml:mi><\/mml:math>. 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 withlog<\/mml:mi>\u2061<\/mml:mo>n<\/mml:mi><\/mml:math>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.<\/jats:p>","DOI":"10.22331\/q-2021-08-20-529","type":"journal-article","created":{"date-parts":[[2021,8,20]],"date-time":"2021-08-20T11:48:15Z","timestamp":1629460095000},"page":"529","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":13,"title":["Quantum algorithms for escaping from saddle points"],"prefix":"10.22331","volume":"5","author":[{"given":"Chenyi","family":"Zhang","sequence":"first","affiliation":[{"name":"Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiaqi","family":"Leng","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tongyang","family":"Li","sequence":"additional","affiliation":[{"name":"Center on Frontiers of Computing Studies, Peking University, Beijing, China"},{"name":"Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA, USA"},{"name":"Department of Computer Science and Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2021,8,20]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma, Finding approximate local minima faster than gradient descent, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195\u20131199, 2017, arXiv:1611.01146. https:\/\/doi.org\/10.1145\/3055399.3055464.","DOI":"10.1145\/3055399.3055464"},{"key":"1","unstructured":"Zeyuan Allen-Zhu, Natasha 2: Faster non-convex optimization than SGD, Advances in Neural Information Processing Systems, pp. 2675\u20132686, 2018, arXiv:1708.08694."},{"key":"2","unstructured":"Zeyuan Allen-Zhu and Yuanzhi Li, Neon2: Finding local minima via first-order oracles, Advances in Neural Information Processing Systems, pp. 3716\u20133726, 2018, arXiv:1711.06673."},{"key":"3","doi-asserted-by":"publisher","unstructured":"Joran van Apeldoorn and Andr\u00e1s Gily\u00e9n, Improvements in quantum SDP-solving with applications, Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 99:1\u201399:15, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 2019, arXiv:1804.05058. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.99.","DOI":"10.4230\/LIPIcs.ICALP.2019.99"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Joran van Apeldoorn, Andr\u00e1s Gily\u00e9n, Sander Gribling, and Ronald de Wolf, Quantum SDP-solvers: Better upper and lower bounds, 58th Annual Symposium on Foundations of Computer Science, IEEE, 2017, arXiv:1705.01843. https:\/\/doi.org\/10.22331\/q-2020-02-14-230.","DOI":"10.22331\/q-2020-02-14-230"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Joran van Apeldoorn, Andr\u00e1s Gily\u00e9n, Sander Gribling, and Ronald de Wolf, Convex optimization using quantum oracles, Quantum 4 (2020), 220, arXiv:1809.00643. https:\/\/doi.org\/10.22331\/q-2020-01-13-220.","DOI":"10.22331\/q-2020-01-13-220"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Frank Arute et al., Quantum supremacy using a programmable superconducting processor, Nature 574 (2019), no. 7779, 505\u2013510, arXiv:1910.11333. https:\/\/doi.org\/10.1038\/s41586-019-1666-5.","DOI":"10.1038\/s41586-019-1666-5"},{"key":"7","doi-asserted-by":"crossref","unstructured":"Ivo Babu\u0161ka and Manil Suri, The $h$-$p$ version of the finite element method with quasiuniform meshes, ESAIM: Mathematical Modelling and Numerical Analysis-Mod\u00e9lisation Math\u00e9matique et Analyse Num\u00e9rique 21 (1987), no. 2, 199\u2013238.","DOI":"10.1051\/m2an\/1987210201991"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders, Efficient quantum algorithms for simulating sparse Hamiltonians, Communications in Mathematical Physics 270 (2007), no. 2, 359\u2013371, arXiv:quant-ph\/0508139. https:\/\/doi.org\/10.1007\/s00220-006-0150-x.","DOI":"10.1007\/s00220-006-0150-x"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Andrew M. Childs, and Robin Kothari, Hamiltonian simulation with nearly optimal dependence on all parameters, Proceedings of the 56th Annual Symposium on Foundations of Computer Science, pp. 792\u2013809, IEEE, 2015, arXiv:1501.01715. https:\/\/doi.org\/10.1109\/FOCS.2015.54.","DOI":"10.1109\/FOCS.2015.54"},{"key":"10","unstructured":"Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro, Global optimality of local search for low rank matrix recovery, Advances in Neural Information Processing Systems, pp. 3880\u20133888, 2016, arXiv:1605.07221."},{"key":"11","doi-asserted-by":"publisher","unstructured":"Jean Bourgain, Growth of Sobolev norms in linear Schr\u00f6dinger equations with quasi-periodic potential, Communications in Mathematical Physics 204 (1999), no. 1, 207\u2013247. https:\/\/doi.org\/10.1007\/s002200050644.","DOI":"10.1007\/s002200050644"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Jean Bourgain, On growth of Sobolev norms in linear Schr\u00f6dinger equations with smooth time dependent potential, Journal d\u2019Analyse Math\u00e9matique 77 (1999), no. 1, 315\u2013348. https:\/\/doi.org\/10.1007\/BF02791265.","DOI":"10.1007\/BF02791265"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Fernando G.S.L. Brand\u00e3o, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu, Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning, Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 27:1\u201327:14, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 2019, arXiv:1710.02581. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.27.","DOI":"10.4230\/LIPIcs.ICALP.2019.27"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Fernando G.S.L. Brand\u00e3o and Krysta Svore, Quantum speed-ups for semidefinite programming, Proceedings of the 58th Annual Symposium on Foundations of Computer Science, pp. 415\u2013426, 2017, arXiv:1609.05537. https:\/\/doi.org\/10.1109\/FOCS.2017.45.","DOI":"10.1109\/FOCS.2017.45"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Alan J. Bray and David S. Dean, Statistics of critical points of Gaussian fields on large-dimensional spaces, Physical Review Letters 98 (2007), no. 15, 150201, arXiv:cond-mat\/0611023. https:\/\/doi.org\/10.1103\/PhysRevLett.98.150201.","DOI":"10.1103\/PhysRevLett.98.150201"},{"key":"16","unstructured":"David Bulger, Quantum basin hopping with gradient-based local optimisation, 2005, arXiv:quant-ph\/0507193."},{"key":"17","doi-asserted-by":"publisher","unstructured":"Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford, Accelerated methods for nonconvex optimization, SIAM Journal on Optimization 28 (2018), no. 2, 1751\u20131772, arXiv:1611.00756. https:\/\/doi.org\/10.1137\/17M1114296.","DOI":"10.1137\/17M1114296"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu, Quantum algorithms and lower bounds for convex optimization, Quantum 4 (2020), 221, arXiv:1809.01731. https:\/\/doi.org\/10.22331\/q-2020-01-13-221.","DOI":"10.22331\/q-2020-01-13-221"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Nai-Hui Chia, Andr\u00e1s Gily\u00e9n, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang, Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning, Proceedings of the 52nd Annual ACM Symposium on Theory of Computing, pp. 387\u2013400, ACM, 2020, arXiv:1910.06151. https:\/\/doi.org\/10.1145\/3357713.3384314.","DOI":"10.1145\/3357713.3384314"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Nai-Hui Chia, Andr\u00e1s Gily\u00e9n, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang, Quantum-inspired algorithms for solving low-rank linear equation systems with logarithmic dependence on the dimension, Proceedings of the 31st International Symposium on Algorithms and Computation, vol. 181, p. 47, Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2020. https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2020.47.","DOI":"10.4230\/LIPIcs.ISAAC.2020.47"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang, Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming, 45th International Symposium on Mathematical Foundations of Computer Science, 2020, arXiv:1901.03254. https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.23.","DOI":"10.4230\/LIPIcs.MFCS.2020.23"},{"key":"22","unstructured":"Andrew M. Childs, Lecture notes on quantum algorithms, https:\/\/www.cs.umd.edu\/%7Eamchilds\/qa\/qa.pdf, 2017."},{"key":"23","doi-asserted-by":"crossref","unstructured":"Andrew M. Childs and Robin Kothari, Limitations on the simulation of non-sparse Hamiltonians, Quantum Information & Computation 10 (2010), no. 7, 669\u2013684, arXiv:0908.4398.","DOI":"10.26421\/QIC10.7-8-7"},{"key":"24","doi-asserted-by":"crossref","unstructured":"Andrew M. Childs, Jin-Peng Liu, and Aaron Ostrander, High-precision quantum algorithms for partial differential equations, 2020, arXiv:2002.07868.","DOI":"10.22331\/q-2021-11-10-574"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, Theory of Trotter error with commutator scaling, Physical Review X 11 (2021), no. 1, 011020, arXiv:1912.08854. https:\/\/doi.org\/10.1103\/PhysRevX.11.011020.","DOI":"10.1103\/PhysRevX.11.011020"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Pedro C.S. Costa, Stephen Jordan, and Aaron Ostrander, Quantum algorithm for simulating the wave equation, Physical Review A 99 (2019), no. 1, 012323, arXiv:1711.05394. https:\/\/doi.org\/10.1103\/PhysRevA.99.012323.","DOI":"10.1103\/PhysRevA.99.012323"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Frank E. Curtis, Daniel P. Robinson, and Mohammadreza Samadi, A trust region algorithm with a worst-case iteration complexity of $\\mathcal{O}(\\epsilon^{-3\/2})$ for nonconvex optimization, Mathematical Programming 162 (2017), no. 1-2, 1\u201332. https:\/\/doi.org\/10.1007\/s10107-016-1026-2.","DOI":"10.1007\/s10107-016-1026-2"},{"key":"28","unstructured":"Yann N. Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio, Identifying and attacking the saddle point problem in high-dimensional non-convex optimization, Advances in Neural Information Processing Systems, pp. 2933\u20132941, 2014, arXiv:1406.2572."},{"key":"29","unstructured":"Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang, Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator, Advances in Neural Information Processing Systems, pp. 689\u2013699, 2018, arXiv:1807.01695."},{"key":"30","unstructured":"Cong Fang, Zhouchen Lin, and Tong Zhang, Sharp analysis for nonconvex SGD escaping from saddle points, Conference on Learning Theory, pp. 1192\u20131234, 2019, arXiv:1902.00247."},{"key":"31","unstructured":"Mauger Fran\u00e7ois, Symplectic leap frog scheme, https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/38652-symplectic-leap-frog-scheme, 2020."},{"key":"32","doi-asserted-by":"publisher","unstructured":"Yan V. Fyodorov and Ian Williams, Replica symmetry breaking condition exposed by random matrix calculation of landscape complexity, Journal of Statistical Physics 129 (2007), no. 5-6, 1081\u20131116, arXiv:cond-mat\/0702601. https:\/\/doi.org\/10.1007\/s10955-007-9386-x.","DOI":"10.1007\/s10955-007-9386-x"},{"key":"33","unstructured":"Xuefeng Gao, Mert G\u00fcrb\u00fczbalaban, and Lingjiong Zhu, Global convergence of stochastic gradient Hamiltonian monte carlo for non-convex stochastic optimization: Non-asymptotic performance bounds and momentum-based acceleration, 2018, arXiv:1809.04618."},{"key":"34","unstructured":"Rong Ge, Furong Huang, Chi Jin, and Yang Yuan, Escaping from saddle points \u2013 online stochastic gradient for tensor decomposition, Conference on Learning Theory, pp. 797\u2013842, 2015, arXiv:1503.02101."},{"key":"35","unstructured":"Rong Ge, Jason D. Lee, and Tengyu Ma, Matrix completion has no spurious local minimum, Advances in Neural Information Processing Systems, pp. 2981\u20132989, 2016, arXiv:1605.07272."},{"key":"36","unstructured":"Rong Ge, Jason D. Lee, and Tengyu Ma, Learning one-hidden-layer neural networks with landscape design, International Conference on Learning Representations, 2018, arXiv:1711.00501."},{"key":"37","unstructured":"Rong Ge and Tengyu Ma, On the optimization landscape of tensor decompositions, Advances in Neural Information Processing Systems, pp. 3656\u20133666, Curran Associates Inc., 2017, arXiv:1706.05598."},{"key":"38","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, Srinivasan Arunachalam, and Nathan Wiebe, Optimizing quantum optimization algorithms via faster quantum gradient computation, Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1425\u20131444, Society for Industrial and Applied Mathematics, 2019, arXiv:1711.00465. https:\/\/doi.org\/10.1137\/1.9781611975482.87.","DOI":"10.1137\/1.9781611975482.87"},{"key":"39","unstructured":"Andr\u00e1s Gily\u00e9n, Zhao Song, and Ewin Tang, An improved quantum-inspired algorithm for linear regression, 2020, arXiv:2009.07268."},{"key":"40","doi-asserted-by":"publisher","unstructured":"Stephen K. Gray and David E. Manolopoulos, Symplectic integrators tailored to the time-dependent Schr\u00f6dinger equation, The Journal of chemical physics 104 (1996), no. 18, 7099\u20137112. https:\/\/doi.org\/10.1063\/1.471428.","DOI":"10.1063\/1.471428"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, pp. 212\u2013219, ACM, 1996, arXiv:quant-ph\/9605043. https:\/\/doi.org\/10.1145\/237814.237866.","DOI":"10.1145\/237814.237866"},{"key":"42","unstructured":"Moritz Hardt, Tengyu Ma, and Benjamin Recht, Gradient descent learns linear dynamical systems, Journal of Machine Learning Research 19 (2018), no. 29, 1\u201344, arXiv:1609.05191."},{"key":"43","doi-asserted-by":"publisher","unstructured":"Daniel Hsu, Sham Kakade, and Tong Zhang, A tail inequality for quadratic forms of subgaussian random vectors, Electronic Communications in Probability 17 (2012), 1\u20136, arXiv:1110.2842. https:\/\/doi.org\/10.1214\/ECP.v17-2079.","DOI":"10.1214\/ECP.v17-2079"},{"key":"44","unstructured":"Prateek Jain, Chi Jin, Sham Kakade, and Praneeth Netrapalli, Global convergence of non-convex gradient descent for computing matrix squareroot, Artificial Intelligence and Statistics, pp. 479\u2013488, 2017, arXiv:1507.05854."},{"key":"45","unstructured":"Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan, How to escape saddle points efficiently, Conference on Learning Theory, pp. 1724\u20131732, 2017, arXiv:1703.00887."},{"key":"46","doi-asserted-by":"publisher","unstructured":"Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, and Michael I. Jordan, On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points, Journal of the ACM 68.2 (2021), 1\u201329. arXiv:1902.04811. https:\/\/doi.org\/10.1145\/3418526.","DOI":"10.1145\/3418526"},{"key":"47","unstructured":"Chi Jin, Praneeth Netrapalli, and Michael I. Jordan, Accelerated gradient descent escapes saddle points faster than gradient descent, Conference on Learning Theory, pp. 1042\u20131085, 2018, arXiv:1711.10456."},{"key":"48","doi-asserted-by":"crossref","unstructured":"Michael I. Jordan, On gradient-based optimization: Accelerated, distributed, asynchronous and stochastic optimization, https:\/\/www.youtube.com\/watch?v=VE2ITg%5FhGnI, 2017.","DOI":"10.1145\/3078505.3078506"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Stephen P. Jordan, Fast quantum algorithm for numerical gradient estimation, Physical Review Letters 95 (2005), no. 5, 050501, arXiv:quant-ph\/0405146. https:\/\/doi.org\/10.1103\/PhysRevLett.95.050501.","DOI":"10.1103\/PhysRevLett.95.050501"},{"key":"50","unstructured":"Stephen P. Jordan, Quantum computation beyond the circuit model, Ph.D. thesis, Massachusetts Institute of Technology, 2008, arXiv:0809.2307."},{"key":"51","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis and Anupam Prakash, Quantum recommendation systems, Proceedings of the 8th Innovations in Theoretical Computer Science Conference, pp. 49:1\u201349:21, 2017, arXiv:1603.08675. https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2017.49.","DOI":"10.4230\/LIPIcs.ITCS.2017.49"},{"key":"52","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis and Anupam Prakash, A quantum interior point method for LPs and SDPs, ACM Transactions on Quantum Computing, pp. 1\u201332, ACM, 2020, arXiv:1808.09266. https:\/\/doi.org\/10.1145\/3406306.","DOI":"10.1145\/3406306"},{"key":"53","unstructured":"Alexei Kitaev and William A. Webb, Wavefunction preparation and resampling using a quantum computer, 2008, arXiv:0801.0342."},{"key":"54","unstructured":"Kfir Y. Levy, The power of normalization: Faster evasion of saddle points, 2016, arXiv:1611.04831."},{"key":"55","doi-asserted-by":"publisher","unstructured":"Jianping Li, General explicit difference formulas for numerical differentiation, Journal of Computational and Applied Mathematics 183 (2005), no. 1, 29\u201352. https:\/\/doi.org\/10.1016\/j.cam.2004.12.026.","DOI":"10.1016\/j.cam.2004.12.026"},{"key":"56","doi-asserted-by":"publisher","unstructured":"Seth Lloyd, Universal quantum simulators, Science 273 (1996), no. 5278, 1073. https:\/\/doi.org\/10.1126\/science.273.5278.1073.","DOI":"10.1126\/science.273.5278.1073"},{"key":"57","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L. Chuang, Optimal Hamiltonian simulation by quantum signal processing, Physical Review Letters 118 (2017), no. 1, 010501, arXiv:1606.02685. https:\/\/doi.org\/10.1103\/PhysRevLett.118.010501.","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"58","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L. Chuang, Hamiltonian simulation by qubitization, Quantum 3 (2019), 163, arXiv:1610.06546. https:\/\/doi.org\/10.22331\/q-2019-07-12-163.","DOI":"10.22331\/q-2019-07-12-163"},{"key":"59","unstructured":"Guang Hao Low and Nathan Wiebe, Hamiltonian simulation in the interaction picture, 2018, arXiv:1805.00675."},{"key":"60","doi-asserted-by":"publisher","unstructured":"Yurii Nesterov and Boris T. Polyak, Cubic regularization of Newton method and its global performance, Mathematical Programming 108 (2006), no. 1, 177\u2013205. https:\/\/doi.org\/10.1007\/s10107-006-0706-8.","DOI":"10.1007\/s10107-006-0706-8"},{"key":"61","unstructured":"Yurii E. Nesterov, A method for solving the convex programming problem with convergence rate ${O}(1\/k^{2})$, Soviet Mathematics Doklady, vol. 27, pp. 372\u2013376, 1983."},{"key":"62","doi-asserted-by":"publisher","unstructured":"John Preskill, Quantum computing in the NISQ era and beyond, Quantum 2 (2018), 79, arXiv:1801.00862. https:\/\/doi.org\/10.22331\/q-2018-08-06-79.","DOI":"10.22331\/q-2018-08-06-79"},{"key":"63","unstructured":"Changpeng Shao and Ashley Montanaro, Faster quantum-inspired algorithms for solving linear systems, 2021, arXiv:2103.10309."},{"key":"64","doi-asserted-by":"publisher","unstructured":"Ju Sun, Qing Qu, and John Wright, A geometric analysis of phase retrieval, Foundations of Computational Mathematics 18 (2018), no. 5, 1131\u20131198, arXiv:1602.06664 https:\/\/doi.org\/10.1007\/s10208-017-9365-9.","DOI":"10.1007\/s10208-017-9365-9"},{"key":"65","doi-asserted-by":"publisher","unstructured":"Ewin Tang, Quantum-inspired classical algorithms for principal component analysis and supervised clustering, 2018, arXiv:1811.00414. https:\/\/doi.org\/10.1103\/PhysRevLett.127.060503.","DOI":"10.1103\/PhysRevLett.127.060503"},{"key":"66","doi-asserted-by":"publisher","unstructured":"Ewin Tang, A quantum-inspired classical algorithm for recommendation systems, Proceedings of the 51st Annual ACM Symposium on Theory of Computing, pp. 217\u2013228, ACM, 2019, arXiv:1807.04271. https:\/\/doi.org\/10.1145\/3313276.3316310.","DOI":"10.1145\/3313276.3316310"},{"key":"67","unstructured":"Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael I. Jordan, Stochastic cubic regularization for fast nonconvex optimization, Advances in Neural Information Processing Systems, pp. 2899\u20132908, 2018, arXiv:1711.02838."},{"key":"68","doi-asserted-by":"publisher","unstructured":"Christian Weedbrook, Stefano Pirandola, Ra\u00fal Garc\u00eda-Patr\u00f3n, Nicolas J. Cerf, Timothy C. Ralph, Jeffrey H. Shapiro, and Seth Lloyd, Gaussian quantum information, Reviews of Modern Physics 84 (2012), no. 2, 621, arXiv:1110.3234. https:\/\/doi.org\/10.1103\/RevModPhys.84.621.","DOI":"10.1103\/RevModPhys.84.621"},{"key":"69","unstructured":"Stephen Wiesner, Simulations of many-body quantum systems by a quantum computer, 1996, arXiv:quant-ph\/9603028."},{"key":"70","unstructured":"Yi Xu, Rong Jin, and Tianbao Yang, NEON+: Accelerated gradient methods for extracting negative curvature for non-convex optimization, 2017, arXiv:1712.01033."},{"key":"71","unstructured":"Yi Xu, Rong Jin, and Tianbao Yang, First-order stochastic algorithms for escaping from saddle points in almost linear time, Advances in Neural Information Processing Systems, pp. 5530\u20135540, 2018, arXiv:1711.01944."},{"key":"72","doi-asserted-by":"publisher","unstructured":"Christof Zalka, Efficient simulation of quantum systems by quantum computers, Fortschritte der Physik: Progress of Physics 46 (1998), no. 6-8, 877\u2013879. https:\/\/doi.org\/10.1002\/(SICI)1521-3978(199811)46:6\/8<877::AID-PROP877>3.0.CO;2-A.","DOI":"10.1002\/(SICI)1521-3978(199811)46:6\/8<877::AID-PROP877>3.0.CO;2-A"},{"key":"73","doi-asserted-by":"publisher","unstructured":"Christof Zalka, Simulating quantum systems on a quantum computer, Proceedings of the Royal Society of London Series A: Mathematical, Physical and Engineering Sciences 454 (1998), no. 1969, 313\u2013322, arXiv:quant-ph\/9603026. https:\/\/doi.org\/10.1098\/rspa.1998.0162.","DOI":"10.1098\/rspa.1998.0162"},{"key":"74","unstructured":"Kaining Zhang, Min-Hsiu Hsieh, Liu Liu, and Dacheng Tao, Quantum algorithm for finding the negative curvature direction in non-convex optimization, 2019, arXiv:1909.07622."},{"key":"75","unstructured":"Yuchen Zhang, Percy Liang, and Moses Charikar, A hitting time analysis of stochastic gradient Langevin dynamics, Conference on Learning Theory, pp. 1980\u20132022, 2017, arXiv:1702.05575."},{"key":"76","unstructured":"Dongruo Zhou and Quanquan Gu, Stochastic recursive variance-reduced cubic regularization methods, International Conference on Artificial Intelligence and Statistics, pp. 3980\u20133990, 2020, arXiv:1901.11518."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-08-20-529\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,1,7]],"date-time":"2023-01-07T19:00:25Z","timestamp":1673118025000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-08-20-529\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,20]]},"references-count":77,"URL":"https:\/\/doi.org\/10.22331\/q-2021-08-20-529","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,20]]},"article-number":"529"}}