On Quantum Speedups For Nonconvex Optimization Via Quantum Tunneling Walks

Republicat de Platon

Urmaritori: 0

Yizhou Liu¹, Weijie J. Su², și Tongyang Li^3,4

¹Departamentul de Inginerie Mecanică, Universitatea Tsinghua, 100084 Beijing, China
²Departamentul de Statistică și Știința Datelor, Universitatea din Pennsylvania
³Centrul de Studii privind Frontierele Informaticii, Universitatea Peking, 100871 Beijing, China
⁴Școala de Informatică, Universitatea Peking, 100871 Beijing, China

Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.

Abstract

Algoritmii clasici nu sunt adesea eficienți pentru rezolvarea problemelor de optimizare neconvexe în care minimele locale sunt separate de bariere înalte. În această lucrare, explorăm posibile accelerări cuantice pentru optimizarea neconvexă prin valorificarea efectului $global$ al tunelului cuantic. În mod specific, introducem un algoritm cuantic denumit mersul de tunel cuantic (QTW) și îl aplicăm problemelor neconvexe în care minimele locale sunt aproximativ minime globale. Arătăm că QTW realizează o accelerare cuantică față de coborârile clasice de gradient stocastic (SGD) atunci când barierele dintre diferitele minime locale sunt mari, dar subțiri, iar minimele sunt plate. Pe baza acestei observații, construim un peisaj specific cu două puțuri, în care algoritmii clasici nu pot atinge eficient o țintă cunoscând bine cealaltă, dar QTW poate atunci când li se oferă stări inițiale adecvate lângă puțul cunoscut. În cele din urmă, coroborăm constatările noastre cu experimente numerice.

[Conținutul încorporat]

Rezumat popular

Algoritmii clasici nu sunt adesea eficienți pentru rezolvarea problemelor de optimizare neconvexe în care minimele locale sunt separate de bariere înalte. În această lucrare, explorăm posibile accelerări cuantice pentru optimizarea neconvexă prin valorificarea efectului global al tunelului cuantic. În mod specific, introducem un algoritm cuantic denumit mersul de tunel cuantic (QTW) și îl aplicăm problemelor neconvexe în care minimele locale sunt aproximativ minime globale. Arătăm că QTW realizează o accelerare cuantică față de coborârile clasice de gradient stocastic (SGD) atunci când barierele dintre diferitele minime locale sunt mari, dar subțiri, iar minimele sunt plate. Pe baza acestei observații, construim un peisaj specific cu două puțuri, în care algoritmii clasici nu pot atinge eficient o țintă cunoscând bine cealaltă, dar QTW poate atunci când li se oferă stări inițiale adecvate lângă puțul cunoscut. În cele din urmă, coroborăm constatările noastre cu experimente numerice.

► Date BibTeX

@article{Liu2023quantumspeedups, doi = {10.22331/q-2023-06-02-1030}, url = {https://doi.org/10.22331/q-2023-06-02-1030}, titlu = {On { Q}uantum {S}peedups pentru {N}onconvex {O}ptimizare prin {Q}uantum {T}unneling {W}alks}, autor = {Liu, Yizhou and Su, Weijie J. and Li, Tongyang}, jurnal = {{Quantum}}, issn = {2521-327X}, editor = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volum = {7}, pagini = {1030} , luna = iunie, anul = {2023} }

► Referințe

[1] Zeyuan Allen-Zhu și Yuanzhi Li. Neon2: Găsirea minimelor locale prin oracole de ordinul întâi. În Advances in Neural Information Processing Systems, paginile 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 și Matus Telgarsky. Descompunerea tensorilor pentru învățarea modelelor de variabile latente. 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 și Julie Clutterbuck. Dovada conjecturii decalajului fundamental. 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/ stabil / 23072145

[4] Joran van Apeldoorn și András Gilyén. Îmbunătățiri în rezolvarea SDP cuantică cu aplicații. În Proceedings of the 46th International Coloquium on Automata, Languages, and Programming, volumul 132 din Leibniz International Proceedings in Informatics (LIPIcs), paginile 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 și Ronald de Wolf. Rezolvatoare cuantice SDP: limite superioare și inferioare mai bune. În lucrările celui de-al 58-lea simpozion anual privind fundamentele informaticii. 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 și Ronald de Wolf. Optimizare convexă folosind oracole cuantice. 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 și Adam Zalcman. Hartree-Fock pe un computer cuantic qubit supraconductor. 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 și Shantanav Chakraborty. Limite superioare îmbunătățite pentru timpii de lovire ai plimbărilor cuantice. Physical Review A, 104: 032215, septembrie 2021. ISSN 2469-9934. 10.1103/physreva.104.032215. Adresa 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 și Riccardo Zecchina. Eficiența recoacirii cuantice vs. clasice în problemele de învățare neconvexe. Proceedings of the National Academy of Sciences, 115 (7): 1457–1462, ian 2018. ISSN 1091-6490. 10.1073/pnas.1711456115. Adresa 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 și Umesh Vazirani. Punctele forte și punctele slabe ale calculului cuantic. SIAM Journal on Computing, 26 (5): 1510–1523, 1997. 10.1137/S0097539796300933. Adresa 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 și Ashia C Wilson. Despre optimizarea simplectică, 2018. arXiv:1802.03653.
arXiv: 1802.03653

[12] Sergio Boixo și Rolando D. Somma. Condiție necesară pentru aproximarea adiabatică cuantică. Physical Review A, 81 (3): 032308, 2010. 10.1103/PhysRevA.81.032308. Adresa 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 GSL Brandão și Krysta Svore. Accelerări cuantice pentru programare semidefinită. În Proceedings of the 58th Annual Symposium on Foundations of Computer Science, paginile 415–426, 2017. 10.1109/FOCS.2017.45. arXiv:1609.05537.
https: / / doi.org/ 10.1109 / FOCS.2017.45
arXiv: 1609.05537

[14] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore și Xiaodi Wu. Rezolvatori cuantici SDP: Accelerări mari, optimitate și aplicații pentru învățarea cuantică. În Proceedings of the 46th International Coloquium on Automata, Languages, and Programming, volumul 132 din Leibniz International Proceedings in Informatics (LIPIcs), paginile 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 și Xiaodi Wu. Algoritmi cuantici și limite inferioare pentru optimizarea convexă. 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 și Jérémie Roland. Cât de repede se amestecă plimbările cuantice? Physical Review Letters, 124: 050501, februarie 2020. 10.1103/PhysRevLett.124.050501. Adresa 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 și Stefano Soatto. Coborârea gradientului stocastic efectuează inferențe variaționale, converge pentru a limita cicluri pentru rețelele adânci. În 2018 Atelierul de Teoria și Aplicațiile Informației (ITA), paginile 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 și Daniel A. Spielman. Accelerare algoritmică exponențială printr-o plimbare cuantică. În Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC '03, pagina 59–68, New York, NY, SUA, 2003. Asociația pentru mașini de calcul. 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 și Aaron Ostrander. Algoritmi cuantici de înaltă precizie pentru ecuații cu diferențe parțiale. Quantum, 5: 574, noiembrie 2021. ISSN 2521-327X. 10.22331/q-2021-11-10-574. Adresa 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 și André LF De Almeida. Descompuneri tensorale, alternarea celor mai mici pătrate și alte povești. Journal of Chemometrics, 23: 393–405, august 2009. 10.1002/cem.1236. Adresa URL https:///hal.archives-ouvertes.fr/hal-00410057.
https:///doi.org/10.1002/cem.1236
https:///hal.archives-ouvertes.fr/hal-00410057

[21] Pedro CS Costa, Stephen Jordan și Aaron Ostrander. Algoritm cuantic pentru simularea ecuației de undă. Physical Review A, 99: 012323, ianuarie 2019. 10.1103/PhysRevA.99.012323. Adresa 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 și Nicolas Boumal. Curbura negativă împiedică accelerarea pentru optimizarea geodezică convexă, chiar și cu oracole exacte de ordinul întâi, 2021. arXiv:2111.13263.
arXiv: 2111.13263

[23] Elizabeth Crosson și Aram W. Harrow. Recoacere cuantică simulată poate fi exponențial mai rapidă decât recoacere simulată clasică. În 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), paginile 714–723. IEEE, oct 2016. 10.1109/focs.2016.81. Adresa 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 și Johannes Sjöstrand. Asimptotice spectrale în limita semi-clasică. 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 și Fred Hamprecht. În esență, nu există bariere în peisajul energetic al rețelei neuronale. În Conferința internațională privind învățarea automată, paginile 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. Teorema adiabatică cuantică revizuită, 2020. arXiv:2003.03063v1.
arXiv: 2003.03063v1

[27] John Duchi, Elad Hazan și Yoram Singer. Metode adaptive subgradient pentru învățarea online și optimizarea stocastică. 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ć și Mikhail D. Lukin . Fazele cuantice ale materiei pe un simulator cuantic programabil de 256 de atomi. 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 și Tong Zhang. Păianjen: optimizare neconvexă aproape optimă prin estimator diferențial stocastic integrat. În Advances in Neural Information Processing Systems, paginile 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 și Tong Zhang. Analiză clară pentru SGD neconvex care scapă din punctele șei. În Conference on Learning Theory, paginile 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 și Daniel Preda. Un algoritm de evoluție adiabatică cuantică aplicat instanțelor aleatorii ale unei probleme NP-complete. Science, 292 (5516): 472–475, apr 2001. ISSN 1095-9203. 10.1126/știință.1057726. Adresa 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] AB Finnila, MA Gomez, C. Sebenik, C. Stenson și JD Doll. Recoacere cuantică: O nouă metodă de minimizare a funcțiilor multidimensionale. Chemical Physics Letters, 219 (5-6): 343–348, martie 1994. ISSN 0009-2614. 10.1016/0009-2614(94)00117-0. Adresa 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. Schema de salturi simplectice, 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 și Ravi Kannan. Învățarea transformărilor liniare. În Proceedings of 37th Conference on Foundations of Computer Science, paginile 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 și Andrew Gordon Wilson. Suprafețe de pierdere, conectivitate în mod și asamblare rapidă a DNN-urilor. În Advances in Neural Information Processing Systems, paginile 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 și Tengyu Ma. Despre peisajul de optimizare al descompunerilor tensorale. Programare matematică, paginile 1–47, 2020. ISSN 1436-4646. 10.1007/s10107-020-01579-x. Adresa 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 și Yang Yuan. Evadarea din punctele de șa – gradient stocastic online pentru descompunerea tensorului. În Proceedings of the 28th Conference on Learning Theory, volumul 40 din Proceedings of Machine Learning Research, paginile 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 și Tengyu Ma. Finalizarea matricei nu are un minim local fals. În Advances in Neural Information Processing Systems, paginile 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, VM Bastidas, Kae Nemoto, WJ Munro, Yong-Heng Huo, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu și Jian-Wei Pan. Quantum merge pe un procesor superconductor programabil bidimensional de 62 de qubiți. 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 și David E. Manolopoulos. Integratori simplectici adaptați ecuației Schrödinger dependente de timp. 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. Analiză semi-clasică pentru operatorul și aplicațiile Schrödinger. Note de curs la matematică. Springer, 1988. 10.1007/BFb0078115.
https: / / doi.org/ 10.1007 / BFb0078115

[42] Bernard Helffer și Johannes Sjöstrand. Puțuri multiple în limita semi-clasică I. Communications in Partial Differential Equations, 9 (4): 337–408, 1984. 10.1080/03605308408820335.
https: / / doi.org/ 10.1080 / 03605308408820335

[43] Bernard Helffer și Johannes Sjöstrand. Puțuri multiple în limita semiclasică III – interacțiune prin sonde nerezonante. Mathematische Nachrichten, 124 (1): 263–313, 1985. https:///doi.org/10.1002/mana.19851240117. Adresa URL https:///onlinelibrary.wiley.com/doi/abs/10.1002/mana.19851240117.
https:///doi.org/10.1002/mana.19851240117

[44] Sepp Hochreiter. Problema gradientului care dispare în timpul învățării rețelelor neuronale recurente și a soluțiilor problemelor. Jurnalul internațional de incertitudine, neclaritate și sisteme bazate pe cunoaștere, 6 (02): 107–116, 1998. 10.1142/S0218488598000094. Adresa URL https:///dl.acm.org/doi/abs/10.1142/S0218488598000094.
https: / / doi.org/ 10.1142 / S0218488598000094

[45] Aapo Hyvarinen. ICA rapidă pentru date zgomotoase folosind momente gaussiene. În 1999 IEEE International Symposium on Circuits and Systems (ISCAS), volumul 5, paginile 57–61, 1999. 10.1109/ISCAS.1999.777510.
https:///doi.org/10.1109/ISCAS.1999.777510

[46] Frédéric Hérau, Michael Hitrik și Johannes Sjöstrand. Efect de tunel și simetrii pentru operatorii de tip kramers–fokker–planck. Revista Institutului de Matematică din 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 și Michael I. Jordan. Cum să scapi eficient de punctele de șa. În Proceedings of the 34th International Conference on Machine Learning, volumul 70, paginile 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 și Michael I. Jordan. Pe minimele locale ale riscului empiric. În Advances in Neural Information Processing Systems, volumul 31, pagina 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 și Michael I. Jordan. Despre optimizarea neconvexă pentru învățarea automată: gradienți, stocasticitate și puncte de șa. Journal of the ACM (JACM), 68 (2): 1–29, 2021. 10.1145/3418526. Adresa 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. Perspective dinamice, simplectice și stocastice asupra optimizării bazate pe gradient. În Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, paginile 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 și Leslie Pack Kaelbling. Fiecare valoare minimă locală este valoarea minimă globală a modelului indus în învățarea automată neconvexă. 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 și Jimmy Ba. Adam: O metodă de optimizare stocastică. În cea de-a 3-a Conferință Internațională pentru Reprezentațiile învățării, 2015. URL https:///openreview.net/forum?id=8gmWwjFyLj. arXiv:1412.6980.
arXiv: 1412.6980
https:///openreview.net/forum?id=8gmWwjFyLj

[53] Alexei Kitaev și William A. Webb. Pregătirea și reeșantionarea funcției de undă folosind un computer cuantic, 2008. arXiv:0801.0342.
arXiv: 0801.0342

[54] Bobby Kleinberg, Yuanzhi Li și Yang Yuan. O viziune alternativă: când SGD scapă de minimele locale? În Conferința internațională privind învățarea automată, paginile 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 și Ohad Shamir. Complexitatea Oracle în optimizarea neconvexă. În 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 și Sanjeev Arora. Explicarea conectivității peisajului a soluțiilor low-cost pentru rețele multistrat. 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- rețele multistrat. 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 și G. George Yin. Stochastic Aproximation and Recursive Algorithms and Applications, volumul 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 și Guilu Long. Optimizarea unei funcții polinomiale pe un procesor cuantic. 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 și Sanjeev Arora. Despre validitatea modelării SGD cu ecuații diferențiale stocastice (SDE). În progrese în sistemele de procesare a informațiilor neuronale, 2021b. Adresa 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 și Nathan Wiebe. Simulare hamiltoniană în imaginea de interacțiune, 2019. URL https:///arxiv.org/abs/1805.00675v2. arXiv:1805.00675v2.
arXiv: 1805.00675v2

[61] Cong Ma, Kaizheng Wang, Yuejie Chi și Yuxin Chen. Regularizare implicită în estimarea statistică neconvexă: coborârea gradientului converge liniar pentru recuperarea fazei și completarea matricei. În Conferința internațională privind învățarea automată, paginile 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. De ce metodele locale rezolvă problemele neconvexe?, pag. 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 și Michael I. Jordan. Eșantionarea poate fi mai rapidă decât optimizarea. 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 și Cédric Villani. Despre tendința de echilibru pentru ecuația Fokker-Planck: o interacțiune între fizică și analiza funcțională. 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. Despre mici valori proprii ale laplacianului Witten. 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 și Daniel A. Lidar. Tunnelare și accelerare în optimizarea cuantică pentru probleme de permutare-simetrică. Physical Review X, 6: 031010, iulie 2016. ISSN 2160-3308. 10.1103/physrevx.6.031010. Adresa 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. Pe seturile de subnivel conectate în deep learning. În Conferința internațională privind învățarea automată, paginile 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 și Isaac L. Chuang. Calcul cuantic și informații cuantice: ediția a 10-a aniversare. Cambridge University Press, 2010. 10.1017 / CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[69] Grigorios A. Pavliotis. Procese și aplicații stocastice: procese de difuzie, ecuațiile Fokker-Planck și Langevin, volumul 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 și Zhihui Zhu. Analiza peisajelor de optimizare pentru învățarea reprezentării supracomplete, 2019. arXiv:1912.02427.
arXiv: 1912.02427

[71] Gianluca Rastelli. Formula semiclasică pentru tunelarea cuantică în potențiale asimetrice cu două godeuri. Physical Review A, 86: 012106, iulie 2012. 10.1103/PhysRevA.86.012106. Adresa 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 și Marco Pistoia. Pregătirea eficientă a distribuțiilor normale în registre cuantice. Quantum, 5: 609, 2021. 10.22331/q-2021-12-23-609. Adresa 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 și Seth Lloyd. Coborârea gradientului cuantic și metoda lui Newton pentru optimizarea polinomială constrânsă. 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 şi Rolando D. Somma. Simulare hamiltoniană în subspațiul de energie joasă. npj Quantum Information, 7 (1): 1–5, 2021. 10.1038/s41534-021-00451-w. Adresa 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] JM Schmidt, AN Cleland și John Clarke. Tunnel rezonant în joncțiuni Josephson mici, polarizate de curent. Physical Review B, 43: 229–238, ianuarie 1991. 10.1103/PhysRevB.43.229. Adresa URL https:///link.aps.org/doi/10.1103/PhysRevB.43.229.
https: / / doi.org/ 10.1103 / PhysRevB.43.229

[76] Alexander Shevchenko și Marco Mondelli. Conectivitatea peisagistică și stabilitatea abandonului soluțiilor SGD pentru rețelele neuronale supra-parametrate. În Conferința internațională privind învățarea automată, paginile 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 și Michael I. Jordan. Despre ratele de învățare și operatorii Schrödinger, 2020. arXiv:2004.06977.
arXiv: 2004.06977

[78] Bin Shi, Simon S. Du, Michael I. Jordan și Weijie J. Su. Înțelegerea fenomenului de accelerație prin ecuații diferențiale de înaltă rezoluție. Programare matematică, paginile 1–70, 2021. 10.1007/s10107-021-01681-8. Adresa 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 și Emmanuel J. Candes. O ecuație diferențială pentru modelarea metodei gradientului accelerat a lui Nesterov: Teorie și perspective. The Journal of Machine Learning Research, 17 (1): 5312–5354, 2016. 10.5555/2946645.3053435. Adresa 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 Soare. Optimizare pentru învățarea profundă: teorie și algoritmi, 2019. arXiv:1912.08957.
arXiv: 1912.08957

[81] Kunal Talwar. Separări computaționale între eșantionare și optimizare. 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, și Xian-Min Jin. Plimbare cuantică bidimensională experimentală pe un cip fotonic. 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. Hipocoercivitate, volumul 202 din Memoriile Societății Americane de Matematică. Societatea Americană de Matematică, 2009. 10.1090/S0065-9266-09-00567-5. arXiv:math/0609050.
https://doi.org/10.1090/S0065-9266-09-00567-5
arXiv: math / 0609050

[84] Andre Wibisono, Ashia C. Wilson și Michael I. Jordan. O perspectivă variațională asupra metodelor accelerate în optimizare. Proceedings of the National Academy of Sciences, 113 (47): E7351–E7358, 2016. 10.1073/pnas.1614734113. Adresa URL https:///doi.org/10.1073/pnas.1614734113. arXiv:1603.04245.
https: / / doi.org/ 10.1073 / pnas.1614734113
arXiv: 1603.04245

[85] Chenyi Zhang și Tongyang Li. Evadați punctele de șa printr-un algoritm simplu bazat pe coborâre în gradient. În Advances in Neural Information Processing Systems, volumul 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 și Tongyang Li. Algoritmi cuantici pentru evadarea din punctele de șa. 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 și Dacheng Tao. Algoritm cuantic pentru găsirea direcției de curbură negativă în optimizarea neconvexă, 2019. arXiv:1909.07622.
arXiv: 1909.07622

[88] Yuqian Zhang, Qing Qu și John Wright. De la simetrie la geometrie: probleme tratabile neconvexe, 2021b. arXiv:2007.06753.
arXiv: 2007.06753

Citat de

[1] Weiyuan Gong, Chenyi Zhang și Tongyang Li, „Robustness of Quantum Algorithms for Nonconvex Optimization”, arXiv: 2212.02548, (2022).

Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2023-06-02 12:31:17). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.

Nu a putut să aducă Date citate încrucișate în ultima încercare 2023-06-02 12:31:15: Nu s-au putut prelua date citate pentru 10.22331 / q-2023-06-02-1030 de la Crossref. Acest lucru este normal dacă DOI a fost înregistrat recent.

Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.

Distribuție de conținut bazat pe SEO și PR. Amplifică-te astăzi.
PlatoAiStream. Web3 Data Intelligence. Cunoștințe amplificate. Accesați Aici.
Mintând viitorul cu Adryenn Ashley. Accesați Aici.
Cumpărați și vindeți acțiuni în companii PRE-IPO cu PREIPO®. Accesați Aici.
Sursa: https://quantum-journal.org/papers/q-2023-06-02-1030/

Timestamp-ul: 2 Iunie, 2023

Timestamp-ul: Iulie 7, 2022

Către amintiri cuantice unice din hardware-ul fără stat

Cluster sursă:

Jurnalul cuantic

Nodul sursă: 806211

Timestamp-ul: Aprilie 8, 2021

Pe Quantum Speedups pentru optimizarea neconvexă prin Quantum Tunneling Walks

Republicat de Platon

Abstract

Rezumat popular

► Date BibTeX

► Referințe

Citat de

Mai mult de la Jurnalul cuantic

Proiectarea circuitelor cuantice moleculare: o abordare bazată pe grafice

Filtru de măsurare adaptiv: strategie eficientă pentru estimarea optimă a lanțurilor cuantice Markov

Supraconductivitate chirală în modelul Fermi-Hubbard cu rețea triunghiulară dopată în două dimensiuni

Traiectorii obiective în dinamica hibridă clasic-cuantică

Amplificatori de pregătire de stat pentru calculul cuantic cu toleranță la erori timpurii

Formule de troterizare minimă pentru un Hamiltonian dependent de timp

Constrângeri stricte asupra convertibilității probabilistice a stărilor cuantice

Apel pentru editori 2023

Metode cuantice pentru rețele neuronale și aplicare la clasificarea imaginilor medicale

Tomografie cu proces cuantică proiectată cu cele mai mici pătrate

Metoda de verificare împărțiți și cuceriți pentru calculul cuantic zgomotos la scară intermediară

Către amintiri cuantice unice din hardware-ul fără stat

Despre noi

Căutare verticală și Ai

Platformă

Rămâneți conectat

Cont