På Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks

På Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks

Tidsstempel: 2. juni 2023 8:23
Kilde node: 2694596

Yizhou Liu1, Weijie J. Su2og Tongyang Li3,4

1Institutt for ingeniørmekanikk, Tsinghua University, 100084 Beijing, Kina
2Institutt for statistikk og datavitenskap, University of Pennsylvania
3Center on Frontiers of Computing Studies, Peking University, 100871 Beijing, Kina
4School of Computer Science, Peking University, 100871 Beijing, Kina

Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.

Abstrakt

Klassiske algoritmer er ofte ikke effektive for å løse ikke-konvekse optimaliseringsproblemer der lokale minima er atskilt med høye barrierer. I denne artikkelen utforsker vi mulige kvantehastigheter for ikke-konveks optimalisering ved å utnytte den $globale$ effekten av kvantetunnelering. Spesifikt introduserer vi en kvantealgoritme kalt kvantetunnelvandring (QTW) og bruker den på ikke-konvekse problemer der lokale minima er tilnærmet globale minima. Vi viser at QTW oppnår kvantehastighet i forhold til klassiske stokastiske gradientnedstigninger (SGD) når barrierene mellom ulike lokale minima er høye, men tynne og minimaene er flate. Basert på denne observasjonen, konstruerer vi et spesifikt dobbeltbrønnslandskap, der klassiske algoritmer ikke effektivt kan treffe ett mål godt kjent med det andre, men QTW kan når det gis riktige starttilstander nær den kjente brønnen. Til slutt bekrefter vi funnene våre med numeriske eksperimenter.

[Innebygd innhold]

Populært sammendrag

Klassiske algoritmer er ofte ikke effektive for å løse ikke-konvekse optimaliseringsproblemer der lokale minima er atskilt med høye barrierer. I denne artikkelen utforsker vi mulige kvantehastigheter for ikke-konveks optimalisering ved å utnytte den globale effekten av kvantetunnelering. Spesifikt introduserer vi en kvantealgoritme kalt kvantetunnelvandring (QTW) og bruker den på ikke-konvekse problemer der lokale minima er tilnærmet globale minima. Vi viser at QTW oppnår kvantehastighet i forhold til klassiske stokastiske gradientnedstigninger (SGD) når barrierene mellom ulike lokale minima er høye, men tynne og minimaene er flate. Basert på denne observasjonen, konstruerer vi et spesifikt dobbeltbrønnslandskap, der klassiske algoritmer ikke effektivt kan treffe ett mål godt kjent med det andre, men QTW kan når det gis riktige starttilstander nær den kjente brønnen. Til slutt bekrefter vi funnene våre med numeriske eksperimenter.

► BibTeX-data

► Referanser

[1] Zeyuan Allen-Zhu og Yuanzhi Li. Neon2: Finne lokale minima via førsteordens orakler. I Advances in Neural Information Processing Systems, side 3716–3726, 2018. URL http://​/​papers.neurips.cc/​paper/​7629-neon2-finding-local-minima-via-first-order-oracles. pdf. arXiv:1711.06673.
arxiv: 1711.06673
http://​/​papers.neurips.cc/​paper/​7629-neon2-finding-local-minima-via-first-order-oracles.pdf

[2] Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade og Matus Telgarsky. Tensordekomponeringer for å lære latente variable modeller. Journal of machine learning research, 15: 2773–2832, 2014. URL https://​/​jmlr.org/​papers/​volume15/​anandkumar14b/​. arXiv:1210.7559v4.
arxiv: 1210.7559v4
https://​/​jmlr.org/​papers/​volume15/​anandkumar14b/​

[3] Ben Andrews og Julie Clutterbuck. Bevis på den grunnleggende gapsformodningen. Journal of the American Mathematical Society, 24 (3): 899–916, 2011. ISSN 08940347, 10886834. URL http://​/​www.jstor.org/​stable/​23072145. arXiv:1006.1686.
arxiv: 1006.1686
http: / / www.jstor.org/ stable / 23072145

[4] Joran van Apeldoorn og András Gilyén. Forbedringer i kvante-SDP-løsning med applikasjoner. I Proceedings of the 46th International Colloquium on Automata, Languages ​​and Programming, bind 132 av Leibniz International Proceedings in Informatics (LIPIcs), side 99:1–99:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. 10.4230/​LIPIcs.ICALP.2019.99. arXiv:1804.05058.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.99
arxiv: 1804.05058

[5] Joran van Apeldoorn, András Gilyén, Sander Gribling og Ronald de Wolf. Quantum SDP-løsere: Bedre øvre og nedre grenser. I Proceedings of the 58th Annual Symposium on Foundations of Computer Science. IEEE, 2017. 10.1109/​FOCS.2017.44. arXiv:1705.01843.
https: / / doi.org/ 10.1109 / FOCS.2017.44
arxiv: 1705.01843

[6] Joran van Apeldoorn, András Gilyén, Sander Gribling og Ronald de Wolf. Konveks optimalisering ved bruk av kvanteorakler. Quantum, 4: 220, 2020. 10.22331/​q-2020-01-13-220. arXiv:1809.00643.
https:/​/​doi.org/​10.22331/​q-2020-01-13-220
arxiv: 1809.00643

[7] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B. Buckley, David A. Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Benjamin Chiaro , Roberto Collins, William Courtney, Sean Demura, Andrew Dunsworth, Edward Farhi, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Matthew P. Harrigan, Alan Ho, Sabrina Hong, Trent Huang, William J Huggins, Lev Ioffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V. Klimov, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Erik Lucero, Orion Martin, John M. Martinis, Jarrod R. McClean, Matt McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Hartmut Neven, Murphy Yuezhen Niu, Thomas E. O'Brien, Eric Ostby, Andre Petukhov, Harald Putterman, Chris Quintana, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Doug Strain, Kevin J. Sung, Marco Szalay , Tyler Y. Takeshita, Amit Vainsencher, Theodore White, Nathan Wiebe, Z. Jamie Yao, Ping Yeh og Adam Zalcman. Hartree-Fock på en superledende qubit kvantedatamaskin. Science, 369 (6507): 1084–1089, 2020. 10.1126/​science.abb9811. URL https://​science.sciencemag.org/​content/​369/​6507/​1084.abstract. arXiv:2004.04174.
https: / / doi.org/ 10.1126 / science.abb9811
arxiv: 2004.04174
https://​science.sciencemag.org/​content/​369/​6507/​1084.abstract

[8] Yosi Atia og Shantanav Chakraborty. Forbedrede øvre grenser for trefftidene for kvantevandringer. Physical Review A, 104: 032215, september 2021. ISSN 2469-9934. 10.1103/​physreva.104.032215. URL http://​/​dx.doi.org/​10.1103/​PhysRevA.104.032215. arXiv:2005.04062v5.
https: / / doi.org/ 10.1103 / physreva.104.032215
arxiv: 2005.04062v5

[9] Carlo Baldassi og Riccardo Zecchina. Effektivitet av kvante versus klassisk annealing i ikke-konvekse læringsproblemer. Proceedings of the National Academy of Sciences, 115 (7): 1457–1462, jan 2018. ISSN 1091-6490. 10.1073/​pnas.1711456115. URL http://​dx.doi.org/​10.1073/​pnas.1711456115. arXiv:1706.08470.
https: / / doi.org/ 10.1073 / pnas.1711456115
arxiv: 1706.08470

[10] Charles H. Bennett, Ethan Bernstein, Gilles Brassard og Umesh Vazirani. Styrker og svakheter ved kvanteberegning. SIAM Journal on Computing, 26 (5): 1510–1523, 1997. 10.1137/​S0097539796300933. URL https://​/​doi.org/​10.1137/​S0097539796300933. arXiv:quant-ph/​9701001.
https: / / doi.org/ 10.1137 / S0097539796300933
arxiv: Quant-ph / 9701001

[11] Michael Betancourt, Michael I. Jordan og Ashia C Wilson. Om symplektisk optimalisering, 2018. arXiv:1802.03653.
arxiv: 1802.03653

[12] Sergio Boixo og Rolando D. Somma. Nødvendig betingelse for kvanteadiabatisk tilnærming. Physical Review A, 81 (3): 032308, 2010. 10.1103/​PhysRevA.81.032308. URL https://​journals.aps.org/​pra/​abstract/​10.1103/​PhysRevA.81.032308. arXiv:0911.1362.
https: / / doi.org/ 10.1103 / PhysRevA.81.032308
arxiv: 0911.1362

[13] Fernando G.S.L. Brandão og Krysta Svore. Quantum speed-ups for semidefinite programmering. I Proceedings of the 58th Annual Symposium on Foundations of Computer Science, side 415–426, 2017. 10.1109/​FOCS.2017.45. arXiv:1609.05537.
https: / / doi.org/ 10.1109 / FOCS.2017.45
arxiv: 1609.05537

[14] Fernando G.S.L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore og Xiaodi Wu. Quantum SDP-løsere: Store hastigheter, optimalitet og applikasjoner for kvantelæring. I Proceedings of the 46th International Colloquium on Automata, Languages ​​and Programming, bind 132 av Leibniz International Proceedings in Informatics (LIPIcs), side 27:1–27:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. 10.4230/​LIPIcs.ICALP.2019.27. arXiv:1710.02581.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.27
arxiv: 1710.02581

[15] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li og Xiaodi Wu. Kvantealgoritmer og nedre grenser for konveks optimalisering. Quantum, 4: 221, 2020. 10.22331/​q-2020-01-13-221. arXiv:1809.01731.
https:/​/​doi.org/​10.22331/​q-2020-01-13-221
arxiv: 1809.01731

[16] Shantanav Chakraborty, Kyle Luh og Jérémie Roland. Hvor fort blandes kvantevandringer? Physical Review Letters, 124: 050501, februar 2020. 10.1103/​PhysRevLett.124.050501. URL https://​/​link.aps.org/​doi/​10.1103/​PhysRevLett.124.050501. arXiv:2001.06305v1.
https: / / doi.org/ 10.1103 / PhysRevLett.124.050501
arxiv: 2001.06305v1

[17] Pratik Chaudhari og Stefano Soatto. Stokastisk gradientnedstigning utfører variasjonsslutning, konvergerer for å begrense sykluser for dype nettverk. I 2018 Information Theory and Applications Workshop (ITA), side 1–10, 2018. 10.1109/​ITA.2018.8503224. arXiv:1710.11029v2.
https://doi.org/ 10.1109/ITA.2018.8503224
arxiv: 1710.11029v2

[18] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann og Daniel A. Spielman. Eksponentiell algoritmisk hastighetsøkning med en kvantevandring. I Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’03, side 59–68, New York, NY, USA, 2003. Association for Computing Machinery. ISBN 1581136749. 10.1145/​780542.780552. URL https://​/​doi.org/​10.1145/​780542.780552. arXiv:quant-ph/​0209131v2.
https: / / doi.org/ 10.1145 / 780542.780552
arXiv: quant-ph / 0209131v2

[19] Andrew M. Childs, Jin-Peng Liu og Aaron Ostrander. Kvantealgoritmer med høy presisjon for partielle differensialligninger. Quantum, 5: 574, nov 2021. ISSN 2521-327X. 10.22331/​q-2021-11-10-574. URL http://​dx.doi.org/​10.22331/​q-2021-11-10-574. arXiv:2002.07868.
https:/​/​doi.org/​10.22331/​q-2021-11-10-574
arxiv: 2002.07868

[20] Pierre Comon, Xavier Luciani og André L. F. De Almeida. Tensor-nedbrytninger, alternerende minste kvadrater og andre historier. Journal of Chemometrics, 23: 393–405, august 2009. 10.1002/​cem.1236. URL https://​/​hal.archives-ouvertes.fr/​hal-00410057.
https://​/​doi.org/​10.1002/​cem.1236
https: / / hal.archives-ouvertes.fr/ hal-00410057

[21] Pedro C. S. Costa, Stephen Jordan og Aaron Ostrander. Kvantealgoritme for simulering av bølgeligningen. Physical Review A, 99: 012323, januar 2019. 10.1103/​PhysRevA.99.012323. URL https://​/​link.aps.org/​doi/​10.1103/​PhysRevA.99.012323. arXiv:1711.05394.
https: / / doi.org/ 10.1103 / PhysRevA.99.012323
arxiv: 1711.05394

[22] Christopher Criscitiello og Nicolas Boumal. Negativ krumning hindrer akselerasjon for geodetisk konveks optimalisering, selv med eksakte førsteordens orakler, 2021. arXiv:2111.13263.
arxiv: 2111.13263

[23] Elizabeth Crosson og Aram W. Harrow. Simulert kvantegløding kan være eksponentielt raskere enn klassisk simulert gløding. I 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), side 714–723. IEEE, oktober 2016. 10.1109/​focs.2016.81. URL http://​dx.doi.org/​10.1109/​FOCS.2016.81. arXiv:1601.03030.
https: / / doi.org/ 10.1109 / focs.2016.81
arxiv: 1601.03030

[24] Mouez Dimassi og Johannes Sjöstrand. Spektral asymptotikk i den semi-klassiske grensen. London Mathematical Society Lecture Note Series. Cambridge University Press, 1999. 10.1017/​CBO9780511662195.
https: / / doi.org/ 10.1017 / CBO9780511662195

[25] Felix Draxler, Kambis Veschgini, Manfred Salmhofer og Fred Hamprecht. I hovedsak ingen barrierer i energilandskapet for nevrale nettverk. I International Conference on Machine Learning, side 1309–1318. PMLR, 2018. URL http://​/​proceedings.mlr.press/​v80/​draxler18a.html. arXiv:1803.00885.
arxiv: 1803.00885
http://​/​proceedings.mlr.press/​v80/​draxler18a.html

[26] Runyao Duan. Kvanteadiabatisk teorem revisited, 2020. arXiv:2003.03063v1.
arxiv: 2003.03063v1

[27] John Duchi, Elad Hazan og Yoram Singer. Adaptive subgradient-metoder for nettbasert læring og stokastisk optimalisering. Journal of Machine Learning Research, 12 (61): 2121–2159, 2011. URL https://​/​www.jmlr.org/​papers/​volume12/​duchi11a/​duchi11a.pdf.
https://​/​www.jmlr.org/​papers/​volume12/​duchi11a/​duchi11a.pdf

[28] Sepehr Ebadi, Tout T. Wang, Harry Levine, Alexander Keesling, Giulia Semeghini, Ahmed Omran, Dolev Bluvstein, Rhine Samajdar, Hannes Pichler, Wen Wei Ho, Soonwon Choi, Subir Sachdev, Markus Greiner, Vladan Vuletić og Mikhail D. Lukin . Kvantefaser av materie på en 256-atom programmerbar kvantesimulator. Nature, 595 (7866): 227–232, 2021. 10.1038/​s41586-021-03582-4. URL https://www.nature.com/​articles/​s41586-021-03582-4.
https:/​/​doi.org/​10.1038/​s41586-021-03582-4
https: / / www.nature.com/ articles / s41586-021-03582-4

[29] Cong Fang, Chris Junchi Li, Zhouchen Lin og Tong Zhang. Edderkopp: Nesten optimal ikke-konveks optimalisering via stokastisk baneintegrert differensialestimator. In Advances in Neural Information Processing Systems, side 689–699, 2018. URL https://​/​dl.acm.org/​doi/​abs/​10.5555/​3326943.3327007. arXiv:1807.01695.
arxiv: 1807.01695
https: / / dl.acm.org/ doi / abs / 10.5555 / 3326943.3327007

[30] Cong Fang, Zhouchen Lin og Tong Zhang. Skarp analyse for ikke-konveks SGD som rømmer fra setepunkter. I Conference on Learning Theory, side 1192–1234, 2019. URL http://​/​proceedings.mlr.press/​v99/​fang19a.html. arXiv:1902.00247.
arxiv: 1902.00247
http://​/​proceedings.mlr.press/​v99/​fang19a.html

[31] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren og Daniel Preda. En kvante-adiabatisk evolusjonsalgoritme brukt på tilfeldige tilfeller av et NP-komplett problem. Science, 292 (5516): 472–475, april 2001. ISSN 1095-9203. 10.1126/​science.1057726. URL http://​dx.doi.org/​10.1126/​science.1057726. arXiv:quant-ph/​0104129.
https: / / doi.org/ 10.1126 / science.1057726
arxiv: Quant-ph / 0104129

[32] A.B. Finnila, M.A. Gomez, C. Sebenik, C. Stenson og J.D. Doll. Quantum annealing: En ny metode for å minimere flerdimensjonale funksjoner. Chemical Physics Letters, 219 (5-6): 343–348, mars 1994. ISSN 0009-2614. 10.1016/​0009-2614(94)00117-0. URL http://​dx.doi.org/​10.1016/​0009-2614(94)00117-0. arXiv:chem-ph/​9404003.
https:/​/​doi.org/​10.1016/​0009-2614(94)00117-0
arXiv:chem-ph/9404003

[33] Mauger François. Symplectic leap frog scheme, 2020. URL https://​/​www.mathworks.com/​matlabcentral/​fileexchange/​38652-symplectic-leap-frog-scheme. https: /​/​www.mathworks.com /​matlabcentral /​fileexchange /​38652-symplectic-leap-frog-scheme.
https://www.mathworks.com/ matlabcentral/fileexchange/38652-symplectic-leap-frog-scheme

[34] Alan Frieze, Mark Jerrum og Ravi Kannan. Lære lineære transformasjoner. I Proceedings of 37th Conference on Foundations of Computer Science, side 359–368, 1996. 10.1109/​SFCS.1996.548495.
https: / / doi.org/ 10.1109 / SFCS.1996.548495

[35] Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry Vetrov og Andrew Gordon Wilson. Tapte overflater, modustilkobling og rask sammensetting av DNN-er. In Advances in Neural Information Processing Systems, side 8803–8812, 2018. URL https://​/​dl.acm.org/​doi/​abs/​10.5555/​3327546.3327556. arXiv:1802.10026.
arxiv: 1802.10026
https: / / dl.acm.org/ doi / abs / 10.5555 / 3327546.3327556

[36] Rong Ge og Tengyu Ma. Om optimaliseringslandskapet til tensornedbrytninger. Matematisk programmering, side 1–47, 2020. ISSN 1436-4646. 10.1007/​s10107-020-01579-x. URL https://​/​doi.org/​10.1007/​s10107-020-01579-x. arXiv:1706.05598v1.
https: / / doi.org/ 10.1007 / s10107-020-01579-x
arxiv: 1706.05598v1

[37] Rong Ge, Furong Huang, Chi Jin og Yang Yuan. Rømme fra setepunkter – online stokastisk gradient for tensornedbrytning. I Proceedings of the 28th Conference on Learning Theory, bind 40 av Proceedings of Machine Learning Research, side 797–842, 2015. URL http://​/​proceedings.mlr.press/​v40/​Ge15. arXiv:1503.02101.
arxiv: 1503.02101
http://​/​proceedings.mlr.press/​v40/​Ge15

[38] Rong Ge, Jason D. Lee og Tengyu Ma. Matrisefullføring har ikke noe falskt lokalt minimum. I Advances in Neural Information Processing Systems, side 2981–2989, 2016. URL https://​/​dl.acm.org/​doi/​abs/​10.5555/​3157382.3157431. arXiv:1605.07272.
arxiv: 1605.07272
https: / / dl.acm.org/ doi / abs / 10.5555 / 3157382.3157431

[39] Ming Gong, Shiyu Wang, Chen Zha, Ming-Cheng Chen, He-Liang Huang, Yulin Wu, Qingling Zhu, Youwei Zhao, Shaowei Li, Shaojun Guo, Haoran Qian, Yangsen Ye, Fusheng Chen, Chong Ying, Jiale Yu, Daojin Fan, Dachao Wu, Hong Su, Hui Deng, Hao Rong, Kaili Zhang, Sirui Cao, Jin Lin, Yu Xu, Lihua Sun, Cheng Guo, Na Li, Futian Liang, V. M. Bastidas, Kae Nemoto, W. J. Munro, Yong-Heng Huo, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu og Jian-Wei Pan. Quantum går på en programmerbar todimensjonal 62-qubit superledende prosessor. Science, 372 (6545): 948–952, 2021. 10.1126/​science.abg7812. URL https://​science.sciencemag.org/​content/​372/​6545/​948.abstract. arXiv:2102.02573.
https://doi.org/ 10.1126/science.abg7812
arxiv: 2102.02573
https://​science.sciencemag.org/​content/​372/​6545/​948.abstract

[40] Stephen K. Gray og David E. Manolopoulos. Symplektiske integratorer skreddersydd til den tidsavhengige Schrödinger-ligningen. The Journal of Chemical Physics, 104 (18): 7099–7112, 1996. 10.1063/​1.471428. URL https://​/​doi.org/​10.1063/​1.471428.
https: / / doi.org/ 10.1063 / 1.471428

[41] Bernard Helffer. Semi-klassisk analyse for Schrödinger-operatøren og applikasjoner. Forelesningsnotater i matematikk. Springer, 1988. 10.1007/​BFb0078115.
https: / / doi.org/ 10.1007 / BFb0078115

[42] Bernard Helffer og Johannes Sjöstrand. Flere brønner i den semi-klassiske grensen I. Communications in Partial Differential Equations, 9 (4): 337–408, 1984. 10.1080/​03605308408820335.
https: / / doi.org/ 10.1080 / 03605308408820335

[43] Bernard Helffer og Johannes Sjöstrand. Flere brønner i den semi-klassiske grensen III – interaksjon gjennom ikke-resonante brønner. Mathematische Nachrichten, 124 (1): 263–313, 1985. https:/​/​doi.org/​10.1002/​mana.19851240117. URL https://​/​onlinelibrary.wiley.com/​doi/​abs/​10.1002/​mana.19851240117.
https: / / doi.org/ 10.1002 / mana.19851240117

[44] Sepp Hochreiter. Problemet med forsvinnende gradient under læring av tilbakevendende nevrale nett og problemløsninger. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 6 (02): 107–116, 1998. 10.1142/​S0218488598000094. URL https://​/​dl.acm.org/​doi/​abs/​10.1142/​S0218488598000094.
https: / / doi.org/ 10.1142 / S0218488598000094

[45] Aapo Hyvarinen. Rask ICA for støyende data ved hjelp av gaussiske øyeblikk. I 1999 IEEE International Symposium on Circuits and Systems (ISCAS), bind 5, side 57–61, 1999. 10.1109/​ISCAS.1999.777510.
https://​/​doi.org/​10.1109/​ISCAS.1999.777510

[46] Frédéric Hérau, Michael Hitrik og Johannes Sjöstrand. Tunneleffekt og symmetrier for operatører av typen kramers–fokker–planck. Journal of the Institute of Mathematics of Jussieu, 10 (3): 567–634, 2011. 10.1017/​S1474748011000028.
https: / / doi.org/ 10.1017 / S1474748011000028

[47] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade og Michael I. Jordan. Hvordan unnslippe setepunkter effektivt. I Proceedings of the 34th International Conference on Machine Learning, bind 70, side 1724–1732, 2017. URL http://​/​proceedings.mlr.press/​v70/​jin17a. arXiv:1703.00887.
arxiv: 1703.00887
http://​/​proceedings.mlr.press/​v70/​jin17a

[48] Chi Jin, Lydia T. Liu, Rong Ge og Michael I. Jordan. På det lokale minimaet for den empiriske risikoen. I Advances in Neural Information Processing Systems, bind 31, side 4901–4910. Curran Associates, Inc., 2018. URL https://​/​proceedings.neurips.cc/​paper/​2018/​file/​da4902cb0bc38210839714ebdcf0efc3-Paper.pdf. arXiv:1803.09357.
arxiv: 1803.09357
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​da4902cb0bc38210839714ebdcf0efc3-Paper.pdf

[49] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade og Michael I. Jordan. Om ikke-konveks optimalisering for maskinlæring: Gradienter, stokastisitet og setepunkter. Journal of the ACM (JACM), 68 (2): 1–29, 2021. 10.1145/​3418526. URL https://​/​dl.acm.org/​doi/​abs/​10.1145/​3418526. arXiv:1902.04811.
https: / / doi.org/ 10.1145 / 3418526
arxiv: 1902.04811

[50] Michael I. Jordan. Dynamiske, symplektiske og stokastiske perspektiver på gradientbasert optimalisering. I Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, side 523–549. World Scientific, 2018. URL https://​/​doi.org/​10.1142/​9789813272880_0022.
https: / / doi.org/ 10.1142 / 9789813272880_0022

[51] Kenji Kawaguchi, Jiaoyang Huang og Leslie Pack Kaelbling. Hver lokal minimumsverdi er den globale minimumsverdien for indusert modell i ikke-konveks maskinlæring. Neural Computation, 31 (12): 2293–2323, 12 2019. ISSN 0899-7667. 10.1162/​neco_a_01234. URL https://​/​doi.org/​10.1162/​neco_a_01234. arXiv:1904.03673v3.
https://​/​doi.org/​10.1162/​neco_a_01234
arxiv: 1904.03673v3

[52] Diederik P. Kingma og Jimmy Ba. Adam: En metode for stokastisk optimalisering. I 3rd International Conference for Learning Representations, 2015. URL https://​/​openreview.net/​forum?id=8gmWwjFyLj. arXiv:1412.6980.
arxiv: 1412.6980
https://​/​openreview.net/​forum?id=8gmWwjFyLj

[53] Alexei Kitaev og William A. Webb. Bølgefunksjonsforberedelse og resampling ved bruk av en kvantedatamaskin, 2008. arXiv:0801.0342.
arxiv: 0801.0342

[54] Bobby Kleinberg, Yuanzhi Li og Yang Yuan. Et alternativt syn: Når slipper SGD unna lokale minima? I International Conference on Machine Learning, side 2698–2707. PMLR, 2018. URL http://​/​proceedings.mlr.press/​v80/​kleinberg18a.html. arXiv:1802.06175.
arxiv: 1802.06175
http://​/​proceedings.mlr.press/​v80/​kleinberg18a.html

[55] Guy Kornowski og Ohad Shamir. Oracle-kompleksitet i ikke-jevn ikke-konveks optimalisering. In Advances in Neural Information Processing Systems, 2021. URL https://​/​openreview.net/​forum?id=aMZJBOiOOPg. arXiv:2104.06763v2.
arxiv: 2104.06763v2
https://​/​openreview.net/​forum?id=aMZJBOiOOPg

[56] Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Rong Ge og Sanjeev Arora. Forklarer landskapstilkoblingen til lavkostløsninger for flerlagsnett. Advances in Neural Information Processing Systems, 32: 14601–14610, 2019. URL http://​/​papers.nips.cc/​paper/​9602-explaining-landscape-connectivity-of-low-cost-solutions-for- flerlagsnett. arXiv:1906.06247.
arxiv: 1906.06247
http://​/​papers.nips.cc/​paper/​9602-explaining-landscape-connectivity-of-low-cost-solutions-for-multilayer-nets

[57] Harold J. Kushner og G. George Yin. Stokastisk approksimasjon og rekursive algoritmer og applikasjoner, bind 35. Springer Science & Business Media, 2003. 10.1007/​978-1-4471-4285-0_3.
https:/​/​doi.org/​10.1007/​978-1-4471-4285-0_3

[58] Keren Li, Shijie Wei, Pan Gao, Feihao Zhang, Zengrong Zhou, Tao Xin, Xiaoting Wang, Patrick Rebentrost og Guilu Long. Optimalisering av en polynomfunksjon på en kvanteprosessor. npj Quantum Information, 7 (1): 1–7, 2021a. 10.1038/​s41534-020-00351-5. arXiv:1804.05231.
https:/​/​doi.org/​10.1038/​s41534-020-00351-5
arxiv: 1804.05231

[59] Zhiyuan Li, Sadhika Malladi og Sanjeev Arora. Om gyldigheten av modellering av SGD med stokastiske differensialligninger (SDE). In Advances in Neural Information Processing Systems, 2021b. URL https://​/​openreview.net/​forum?id=goEdyJ_nVQI. arXiv:2102.12470.
arxiv: 2102.12470
https://​/​openreview.net/​forum?id=goEdyJ_nVQI

[60] Guang Hao Low og Nathan Wiebe. Hamiltonsk simulering i interaksjonsbildet, 2019. URL https://​/​arxiv.org/​abs/​1805.00675v2. arXiv:1805.00675v2.
arxiv: 1805.00675v2

[61] Cong Ma, Kaizheng Wang, Yuejie Chi og Yuxin Chen. Implisitt regularisering i ikke-konveks statistisk estimering: Gradientnedstigning konvergerer lineært for fasehenting og matrisefullføring. I International Conference on Machine Learning, side 3345–3354. PMLR, 2018. URL http://​/​proceedings.mlr.press/​v80/​ma18c.html. arXiv:1711.10467.
arxiv: 1711.10467
http://​/​proceedings.mlr.press/​v80/​ma18c.html

[62] Tengyu Ma. Hvorfor løser lokale metoder ikke-konvekse problemer?, side 465–485. Cambridge University Press, 2021. 10.1017/​9781108637435.027. arXiv:2103.13462.
https: / / doi.org/ 10.1017 / 9781108637435.027
arxiv: 2103.13462

[63] Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion og Michael I. Jordan. Sampling kan være raskere enn optimalisering. Proceedings of the National Academy of Sciences, 116 (42): 20881–20885, 2019. URL https://​/​www.pnas.org/​content/​116/​42/​20881.short. arXiv:.
https: / / doi.org/ 10.1073 / pnas.1820003116
https://​/​www.pnas.org/​content/​116/​42/​20881.short

[64] Peter A. Markowich og Cédric Villani. Om trenden til likevekt for Fokker-Planck-ligningen: Et samspill mellom fysikk og funksjonell analyse. In Physics and Functional Analysis, Matematica Contemporanea (SBM) 19. Citeseer, 1999. URL http://​/​citeseerx.ist.psu.edu/​viewdoc/​summary?doi=10.1.1.35.2278.
http://​/​citeseerx.ist.psu.edu/​viewdoc/​summary?doi=10.1.1.35.2278

[65] Laurent Michel. Om små egenverdier til Witten Laplacian. Pure and Applied Analysis, 1 (2): 149 – 206, 2019. 10.2140/​paa.2019.1.149. URL https://​/​doi.org/​10.2140/​paa.2019.1.149. arXiv:1702.01837.
https://​/​doi.org/​10.2140/​paa.2019.1.149
arxiv: 1702.01837

[66] Siddharth Muthukrishnan, Tameem Albash og Daniel A. Lidar. Tunnelering og fremskyndelse i kvanteoptimalisering for permutasjonssymmetriske problemer. Physical Review X, 6: 031010, jul 2016. ISSN 2160-3308. 10.1103/​physrevx.6.031010. URL http://​dx.doi.org/​10.1103/​PhysRevX.6.031010. arXiv:1511.03910.
https: / / doi.org/ 10.1103 / physrevx.6.031010
arxiv: 1511.03910

[67] Quynh Nguyen. På tilkoblet undernivå setter i dyp læring. I International Conference on Machine Learning, side 4790–4799. PMLR, 2019. URL http://​/​proceedings.mlr.press/​v97/​nguyen19a.html. arXiv:1901.07417.
arxiv: 1901.07417
http://​/​proceedings.mlr.press/​v97/​nguyen19a.html

[68] Michael A. Nielsen og Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. 10.1017 / CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[69] Grigorios A. Pavliotis. Stokastiske prosesser og applikasjoner: diffusjonsprosesser, Fokker-Planck- og Langevin-ligningene, bind 60. Springer, 2014. 10.1007/​978-1-4939-1323-7.
https:/​/​doi.org/​10.1007/​978-1-4939-1323-7

[70] Qing Qu, Yuexiang Zhai, Xiao Li, Yuqian Zhang og Zhihui Zhu. Analyse av optimaliseringslandskapene for overfullstendig representasjonslæring, 2019. arXiv:1912.02427.
arxiv: 1912.02427

[71] Gianluca Rastelli. Semiklassisk formel for kvantetunnelering i asymmetriske dobbeltbrønnpotensialer. Physical Review A, 86: 012106, juli 2012. 10.1103/​PhysRevA.86.012106. URL https://​/​link.aps.org/​doi/​10.1103/​PhysRevA.86.012106. arXiv:1205.0366.
https: / / doi.org/ 10.1103 / PhysRevA.86.012106
arxiv: 1205.0366

[72] Arthur G. Rattew, Yue Sun, Pierre Minssen og Marco Pistoia. Den effektive utarbeidelsen av normalfordelinger i kvanteregistre. Quantum, 5: 609, 2021. 10.22331/​q-2021-12-23-609. URL https://​/​quantum-journal.org/​papers/​q-2021-12-23-609/​. arXiv:2009.06601.
https:/​/​doi.org/​10.22331/​q-2021-12-23-609
arxiv: 2009.06601
https: / / quantum-journal.org/ papers / q-2021-12-23-609 /

[73] Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione og Seth Lloyd. Kvantegradientnedstigning og Newtons metode for begrenset polynomoptimalisering. New Journal of Physics, 21 (7): 073023, 2019. 10.1088/​1367-2630/​ab2a9e. arXiv:1612.01789.
https:/​/​doi.org/​10.1088/​1367-2630/​ab2a9e
arxiv: 1612.01789

[74] Burak Şahinoğlu og Rolando D. Somma. Hamiltonsimulering i lavenergiunderrommet. npj Quantum Information, 7 (1): 1–5, 2021. 10.1038/​s41534-021-00451-w. URL https://www.nature.com/​articles/​s41534-021-00451-w. arXiv:2006.02660.
https: / / doi.org/ 10.1038 / s41534-021-00451-w
arxiv: 2006.02660
https://​/​www.nature.com/​articles/​s41534-021-00451-w

[75] J.M. Schmidt, A.N. Cleland og John Clarke. Resonant tunnelering i små strømforspente Josephson-kryss. Physical Review B, 43: 229–238, januar 1991. 10.1103/​PhysRevB.43.229. URL https://​/​link.aps.org/​doi/​10.1103/​PhysRevB.43.229.
https: / / doi.org/ 10.1103 / PhysRevB.43.229

[76] Alexander Shevchenko og Marco Mondelli. Landskapstilkobling og frafallsstabilitet for SGD-løsninger for overparameteriserte nevrale nettverk. I International Conference on Machine Learning, side 8773–8784. PMLR, 2020. URL http://​/​proceedings.mlr.press/​v119/​shevchenko20a.html. arXiv:1912.10095.
arxiv: 1912.10095
http://​/​proceedings.mlr.press/​v119/​shevchenko20a.html

[77] Bin Shi, Weijie J. Su og Michael I. Jordan. Om læringsrater og Schrödinger-operatører, 2020. arXiv:2004.06977.
arxiv: 2004.06977

[78] Bin Shi, Simon S. Du, Michael I. Jordan og Weijie J. Su. Forstå akselerasjonsfenomenet via høyoppløselige differensialligninger. Matematisk programmering, side 1–70, 2021. 10.1007/​s10107-021-01681-8. URL https://​/​doi.org/​10.1007/​s10107-021-01681-8. arXiv:1810.08907.
https:/​/​doi.org/​10.1007/​s10107-021-01681-8
arxiv: 1810.08907

[79] Weijie Su, Stephen Boyd og Emmanuel J. Candes. En differensialligning for modellering av Nesterovs akselererte gradientmetode: Teori og innsikt. The Journal of Machine Learning Research, 17 (1): 5312–5354, 2016. 10.5555/​2946645.3053435. URL https://​/​dl.acm.org/​doi/​abs/​10.5555/​2946645.3053435. arXiv:1503.01243.
https: / / doi.org/ 10.5555 / 2946645.3053435
arxiv: 1503.01243

[80] Ruoyu Sun. Optimalisering for dyp læring: teori og algoritmer, 2019. arXiv:1912.08957.
arxiv: 1912.08957

[81] Kunal Talwar. Beregningsmessige separasjoner mellom sampling og optimalisering. Advances in Neural Information Processing Systems, 32: 15023–15033, 2019. URL http://​/​papers.nips.cc/​paper/​9639-computational-separations-between-sampling-and-optimization. arXiv:1911.02074.
arxiv: 1911.02074
http://​/​papers.nips.cc/​paper/​9639-computational-separations-between-sampling-and-optimization

[82] Hao Tang, Xiao-Feng Lin, Zhen Feng, Jing-Yuan Chen, Jun Gao, Ke Sun, Chao-Yue Wang, Peng-Cheng Lai, Xiao-Yun Xu, Yao Wang, Lu-Feng Qiao, Ai-Lin Yang, og Xian-Min Jin. Eksperimentell todimensjonal kvantevandring på en fotonisk brikke. Science advances, 4 (5): eaat3174, 2018. 10.1126/​sciadv.aat3174. URL https://​/​www.science.org/​doi/​10.1126/​sciadv.aat3174. arXiv:1704.08242.
https: / / doi.org/ 10.1126 / sciadv.aat3174
arxiv: 1704.08242

[83] Cédric Villani. Hypocoercivity, bind 202 av Memoirs of the American Mathematical Society. American Mathematical Society, 2009. 10.1090/​S0065-9266-09-00567-5. arXiv:math/​0609050.
https:/​/​doi.org/​10.1090/​S0065-9266-09-00567-5
arxiv: matematikk / 0609050

[84] Andre Wibisono, Ashia C. Wilson og Michael I. Jordan. Et variasjonsperspektiv på akselererte metoder i optimalisering. Proceedings of the National Academy of Sciences, 113 (47): E7351–E7358, 2016. 10.1073/​pnas.1614734113. URL https://​/​doi.org/​10.1073/​pnas.1614734113. arXiv:1603.04245.
https: / / doi.org/ 10.1073 / pnas.1614734113
arxiv: 1603.04245

[85] Chenyi Zhang og Tongyang Li. Unngå setepunkter med en enkel gradient-nedstigningsbasert algoritme. In Advances in Neural Information Processing Systems, bind 34, 2021. URL https://​/​openreview.net/​forum?id=lEf52hTHq0Q. arXiv:2111.14069.
arxiv: 2111.14069
https://​/​openreview.net/​forum?id=lEf52hTHq0Q

[86] Chenyi Zhang, Jiaqi Leng og Tongyang Li. Kvantealgoritmer for å rømme fra setepunkter. Quantum, 5: 529, 2021a. 10.22331/​q-2021-08-20-529. arXiv:2007.10253.
https:/​/​doi.org/​10.22331/​q-2021-08-20-529
arxiv: 2007.10253

[87] Kaining Zhang, Min-Hsiu Hsieh, Liu Liu og Dacheng Tao. Kvantealgoritme for å finne den negative krumningsretningen i ikke-konveks optimalisering, 2019. arXiv:1909.07622.
arxiv: 1909.07622

[88] Yuqian Zhang, Qing Qu og John Wright. Fra symmetri til geometri: Håndterbare ikke-konvekse problemer, 2021b. arXiv:2007.06753.
arxiv: 2007.06753

Sitert av

[1] Weiyuan Gong, Chenyi Zhang og Tongyang Li, "Robustness of Quantum Algorithms for Nonconvex Optimization", arxiv: 2212.02548, (2022).

Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2023-06-02 12:31:17). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.

Kunne ikke hente Crossref sitert av data under siste forsøk 2023-06-02 12:31:15: Kunne ikke hente siterte data for 10.22331 / q-2023-06-02-1030 fra Crossref. Dette er normalt hvis DOI nylig ble registrert.

Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.

Tidstempel:

Mer fra Kvantejournal