Über Quantenbeschleunigungen für die nichtkonvexe Optimierung mittels Quantum Tunneling Walks

Neuauflage von Plato

Verfolger: 0

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

¹Abteilung für technische Mechanik, Tsinghua-Universität, 100084 Peking, China
²Institut für Statistik und Datenwissenschaft, University of Pennsylvania
³Center on Frontiers of Computing Studies, Universität Peking, 100871 Peking, China
⁴Fakultät für Informatik, Universität Peking, 100871 Peking, China

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Klassische Algorithmen sind oft nicht effektiv zur Lösung nichtkonvexer Optimierungsprobleme, bei denen lokale Minima durch hohe Barrieren getrennt sind. In diesem Artikel untersuchen wir mögliche Quantenbeschleunigungen für die nichtkonvexe Optimierung, indem wir den globalen Effekt des Quantentunnelns nutzen. Konkret führen wir einen Quantenalgorithmus namens Quantum Tunneling Walk (QTW) ein und wenden ihn auf nichtkonvexe Probleme an, bei denen lokale Minima annähernd globale Minima sind. Wir zeigen, dass QTW eine Quantenbeschleunigung gegenüber klassischen stochastischen Gradientenabstiegen (SGD) erreicht, wenn die Barrieren zwischen verschiedenen lokalen Minima hoch, aber dünn und die Minima flach sind. Basierend auf dieser Beobachtung konstruieren wir eine spezifische Doppelbrunnenlandschaft, in der klassische Algorithmen einen Zielbrunnen nicht effizient treffen können, wenn sie den anderen Brunnen kennen, QTW jedoch, wenn geeignete Anfangszustände in der Nähe des bekannten Brunnens gegeben sind. Abschließend untermauern wir unsere Ergebnisse mit numerischen Experimenten.

[Eingebetteten Inhalt]

Populäre Zusammenfassung

► BibTeX-Daten

@article{Liu2023quantumspeedups, doi = {10.22331/q-2023-06-02-1030}, url = {https://doi.org/10.22331/q-2023-06-02-1030}, title = {On { Q}uantum {S}peedups für {N}onconvex {O}optimierung mittels {Q}uantum {T}unneling {W}alks}, Autor = {Liu, Yizhou und Su, Weijie J. und Li, Tongyang}, Zeitschrift = {{Quantum}}, issn = {2521-327X}, verleger = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, Band = {7}, Seiten = {1030} , Monat = Juni, Jahr = {2023} }

► Referenzen

[1] Zeyuan Allen-Zhu und Yuanzhi Li. Neon2: Lokale Minima mithilfe von Orakeln erster Ordnung finden. In Advances in Neural Information Processing Systems, Seiten 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 und Matus Telgarsky. Tensorzerlegungen zum Lernen latenter Variablenmodelle. 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 und Julie Clutterbuck. Beweis der fundamentalen Lückenvermutung. 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 und András Gilyén. Verbesserungen bei der Quanten-SDP-Lösung mit Anwendungen. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Band 132 der Leibniz International Proceedings in Informatics (LIPIcs), Seiten 99:1–99:15. Schloss Dagstuhl–Leibniz-Zentrum für 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 und Ronald de Wolf. Quanten-SDP-Löser: Bessere Ober- und Untergrenzen. In Proceedings des 58. Jahressymposiums über Grundlagen der Informatik. 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 und Ronald de Wolf. Konvexe Optimierung mit Quantenorakeln. 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 und Adam Zalcman. Hartree-Fock über einen supraleitenden Qubit-Quantencomputer. 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 und Shantanav Chakraborty. Verbesserte Obergrenzen für die Trefferzeiten von Quantenwanderungen. 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 und Riccardo Zecchina. Effizienz von Quanten- und klassischem Annealing bei nichtkonvexen Lernproblemen. Proceedings of the National Academy of Sciences, 115 (7): 1457–1462, Januar 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 und Umesh Vazirani. Stärken und Schwächen des Quantencomputings. 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 und Ashia C Wilson. Zur symplektischen Optimierung, 2018. arXiv:1802.03653.
arXiv: 1802.03653

[12] Sergio Boixo und Rolando D. Somma. Notwendige Bedingung für die quantenadiabatische Näherung. 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 GSL Brandão und Krysta Svore. Quantenbeschleunigungen für semidefinite Programmierung. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science, Seiten 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 und Xiaodi Wu. Quanten-SDP-Löser: Große Beschleunigungen, Optimalität und Anwendungen für das Quantenlernen. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Band 132 der Leibniz International Proceedings in Informatics (LIPIcs), Seiten 27:1–27:14. Schloss Dagstuhl–Leibniz-Zentrum für 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 und Xiaodi Wu. Quantenalgorithmen und Untergrenzen für die konvexe Optimierung. 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 und Jérémie Roland. Wie schnell mischen sich Quantenwanderungen? 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 und Stefano Soatto. Der stochastische Gradientenabstieg führt eine Variationsinferenz durch und konvergiert, um Zyklen für tiefe Netzwerke zu begrenzen. Im Jahr 2018 Information Theory and Applications Workshop (ITA), Seiten 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 und Daniel A. Spielman. Exponentielle algorithmische Beschleunigung durch einen Quantenspaziergang. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC '03, Seite 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 und Aaron Ostrander. Hochpräzise Quantenalgorithmen für partielle Differentialgleichungen. Quantum, 5: 574, November 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 und André LF De Almeida. Tensorzerlegungen, alternierende kleinste Quadrate und andere Geschichten. Journal of Chemmetrics, 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 CS Costa, Stephen Jordan und Aaron Ostrander. Quantenalgorithmus zur Simulation der Wellengleichung. 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 und Nicolas Boumal. Negative Krümmung behindert die Beschleunigung für geodätisch-konvexe Optimierung, selbst bei exakten Orakeln erster Ordnung, 2021. arXiv:2111.13263.
arXiv: 2111.13263

[23] Elizabeth Crosson und Aram W. Harrow. Simuliertes Quantenglühen kann exponentiell schneller sein als klassisches simuliertes Glühen. Im Jahr 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), Seiten 714–723. IEEE, Okt. 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 und Johannes Sjöstrand. Spektrale Asymptotik im semiklassischen Grenzfall. Vorlesungsreihe der London Mathematical Society. Cambridge University Press, 1999. 10.1017/CBO9780511662195.
https: / / doi.org/ 10.1017 / CBO9780511662195

[25] Felix Draxler, Kambis Veschgini, Manfred Salmhofer und Fred Hamprecht. Im Wesentlichen keine Hindernisse in der Energielandschaft neuronaler Netze. In International Conference on Machine Learning, Seiten 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. Quantenadiabatischer Satz überarbeitet, 2020. arXiv:2003.03063v1.
arXiv: 2003.03063v1

[27] John Duchi, Elad Hazan und Yoram Singer. Adaptive Subgradientenmethoden für Online-Lernen und stochastische Optimierung. 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ć und Mikhail D. Lukin . Quantenphasen der Materie auf einem programmierbaren Quantensimulator mit 256 Atomen. 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 und Tong Zhang. Spider: Nahezu optimale nichtkonvexe Optimierung mittels stochastischem pfadintegriertem Differentialschätzer. In Advances in Neural Information Processing Systems, Seiten 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 und Tong Zhang. Scharfe Analyse für nichtkonvexes SGD, das aus Sattelpunkten austritt. In Conference on Learning Theory, Seiten 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 und Daniel Preda. Ein quantenadiabatischer Evolutionsalgorithmus, der auf zufällige Instanzen eines NP-vollständigen Problems angewendet wird. 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] AB Finnila, MA Gomez, C. Sebenik, C. Stenson und JD Doll. Quantenglühen: Eine neue Methode zur Minimierung mehrdimensionaler Funktionen. Chemical Physics Letters, 219 (5-6): 343–348, März 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. Symplektisches Leap-Frog-Schema, 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 und Ravi Kannan. Lineare Transformationen lernen. In Proceedings of 37th Conference on Foundations of Computer Science, Seiten 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 und Andrew Gordon Wilson. Verlustflächen, Modenkonnektivität und schnelle Zusammenstellung von DNNs. In Advances in Neural Information Processing Systems, Seiten 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 und Tengyu Ma. Zur Optimierungslandschaft von Tensorzerlegungen. Mathematische Programmierung, Seiten 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 und Yang Yuan. Flucht aus Sattelpunkten – stochastischer Online-Gradient für die Tensorzerlegung. In Proceedings of the 28th Conference on Learning Theory, Band 40 von Proceedings of Machine Learning Research, Seiten 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 und Tengyu Ma. Die Matrixvervollständigung hat kein falsches lokales Minimum. In Advances in Neural Information Processing Systems, Seiten 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 und Jian-Wei Pan. Quantum läuft auf einem programmierbaren zweidimensionalen supraleitenden 62-Qubit-Prozessor. 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 und David E. Manolopoulos. Auf die zeitabhängige Schrödinger-Gleichung zugeschnittene symplektische Integratoren. 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. Semiklassische Analyse für den Schrödinger-Operator und Anwendungen. Vorlesungsunterlagen in Mathematik. Springer, 1988. 10.1007/BFb0078115.
https: / / doi.org/ 10.1007 / BFb0078115

[42] Bernard Helffer und Johannes Sjöstrand. Mehrere Brunnen im semiklassischen Limes I. Communications in Partial Differential Equations, 9 (4): 337–408, 1984. 10.1080/03605308408820335.
https: / / doi.org/ 10.1080 / 03605308408820335

[43] Bernard Helffer und Johannes Sjöstrand. Mehrere Brunnen im semiklassischen Grenzwert III – Interaktion durch nichtresonante Brunnen. 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. Das Problem des verschwindenden Gradienten beim Lernen wiederkehrender neuronaler Netze und Problemlösungen. 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. Schnelle ICA für verrauschte Daten mit Gaußschen Momenten. 1999 IEEE International Symposium on Circuits and Systems (ISCAS), Band 5, Seiten 57–61, 1999. 10.1109/ISCAS.1999.777510.
https:///doi.org/10.1109/ISCAS.1999.777510

[46] Frédéric Hérau, Michael Hitrik und Johannes Sjöstrand. Tunneleffekt und Symmetrien für Kramers-Fokker-Planck-Operatoren. 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 und Michael I. Jordan. So umgehen Sie Sattelpunkte effizient. In Proceedings of the 34th International Conference on Machine Learning, Band 70, Seiten 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 und Michael I. Jordan. Über die lokalen Minima des empirischen Risikos. In Advances in Neural Information Processing Systems, Band 31, Seite 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 und Michael I. Jordan. Zur nichtkonvexen Optimierung für maschinelles Lernen: Gradienten, Stochastizität und Sattelpunkte. 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. Dynamische, symplektische und stochastische Perspektiven zur gradientenbasierten Optimierung. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, Seiten 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 und Leslie Pack Kaelbling. Jeder lokale Minimalwert ist der globale Minimalwert des induzierten Modells beim nichtkonvexen maschinellen Lernen. 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 und Jimmy Ba. Adam: Eine Methode zur stochastischen Optimierung. In 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 und William A. Webb. Wellenfunktionsvorbereitung und Resampling mit einem Quantencomputer, 2008. arXiv:0801.0342.
arXiv: 0801.0342

[54] Bobby Kleinberg, Yuanzhi Li und Yang Yuan. Eine alternative Sichtweise: Wann entgeht der SGD lokalen Minima? In International Conference on Machine Learning, Seiten 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 und Ohad Shamir. Oracle-Komplexität bei nicht glatter, nicht konvexer Optimierung. 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 und Sanjeev Arora. Erläutern der Landschaftskonnektivität kostengünstiger Lösungen für mehrschichtige Netze. 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- Mehrschichtnetze. 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 und G. George Yin. Stochastic Approximation and Recursive Algorithms and Applications, Band 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 und Guilu Long. Optimierung einer Polynomfunktion auf einem Quantenprozessor. 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 und Sanjeev Arora. Zur Gültigkeit der SGD-Modellierung mit stochastischen Differentialgleichungen (SDEs). In Fortschritte in neuronalen Informationsverarbeitungssystemen, 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 und Nathan Wiebe. Hamilton-Simulation im Interaktionsbild, 2019. URL https:///arxiv.org/abs/1805.00675v2. arXiv:1805.00675v2.
arXiv: 1805.00675v2

[61] Cong Ma, Kaizheng Wang, Yuejie Chi und Yuxin Chen. Implizite Regularisierung bei der nichtkonvexen statistischen Schätzung: Der Gradientenabstieg konvergiert linear zur Phasenabfrage und Matrixvervollständigung. In International Conference on Machine Learning, Seiten 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. Warum lösen lokale Methoden nichtkonvexe Probleme?, Seite 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 und Michael I. Jordan. Die Probenahme kann schneller sein als die Optimierung. 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 und Cédric Villani. Zum Trend zum Gleichgewicht der Fokker-Planck-Gleichung: Ein Zusammenspiel von Physik und Funktionalanalysis. 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. Über kleine Eigenwerte des Witten-Laplace-Operators. 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 und Daniel A. Lidar. Tunneln und Beschleunigung in der Quantenoptimierung für permutationssymmetrische Probleme. Physical Review X, 6: 031010, Juli 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. Auf verbundenen Unterebenen setzt Deep Learning ein. In International Conference on Machine Learning, Seiten 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 und Isaac L. Chuang. Quantenberechnung und Quanteninformationen: Ausgabe zum 10. Jubiläum. Cambridge University Press, 2010. 10.1017/CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[69] Grigorios A. Pavliotis. Stochastische Prozesse und Anwendungen: Diffusionsprozesse, die Fokker-Planck- und Langevin-Gleichungen, Band 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 und Zhihui Zhu. Analyse der Optimierungslandschaften für übervollständiges Repräsentationslernen, 2019. arXiv:1912.02427.
arXiv: 1912.02427

[71] Gianluca Rastelli. Halbklassische Formel für Quantentunneln in asymmetrischen Doppeltopfpotentialen. 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 und Marco Pistoia. Die effiziente Vorbereitung von Normalverteilungen in Quantenregistern. 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 und Seth Lloyd. Quantengradientenabstieg und Newtons Methode zur Optimierung eingeschränkter Polynome. 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 und Rolando D. Somma. Hamilton-Simulation im Niedrigenergie-Unterraum. 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] JM Schmidt, AN Cleland und John Clarke. Resonanztunneln in kleinen stromvorgespannten Josephson-Kontakten. 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 Schewtschenko und Marco Mondelli. Landschaftskonnektivität und Dropout-Stabilität von SGD-Lösungen für überparametrisierte neuronale Netze. In International Conference on Machine Learning, Seiten 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 und Michael I. Jordan. Zu Lernraten und Schrödinger-Operatoren, 2020. arXiv:2004.06977.
arXiv: 2004.06977

[78] Bin Shi, Simon S. Du, Michael I. Jordan und Weijie J. Su. Verständnis des Beschleunigungsphänomens mithilfe hochauflösender Differentialgleichungen. Mathematische Programmierung, Seiten 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 und Emmanuel J. Candes. Eine Differentialgleichung zur Modellierung der beschleunigten Gradientenmethode von Nesterov: Theorie und Erkenntnisse. 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. Optimierung für Deep Learning: Theorie und Algorithmen, 2019. arXiv:1912.08957.
arXiv: 1912.08957

[81] Kunal Talwar. Rechnerische Trennungen zwischen Probenahme und Optimierung. 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, und Xian-Min Jin. Experimenteller zweidimensionaler Quantenspaziergang auf einem photonischen Chip. Wissenschaftliche Fortschritte, 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. Hypokoerzitivkraft, Band 202 der Memoiren der 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: math / 0609050

[84] Andre Wibisono, Ashia C. Wilson und Michael I. Jordan. Eine Variationsperspektive auf beschleunigte Methoden in der Optimierung. 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 und Tongyang Li. Escape-Sattelpunkte durch einen einfachen, auf Gradientenabstieg basierenden Algorithmus. In Advances in Neural Information Processing Systems, Band 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 und Tongyang Li. Quantenalgorithmen zur Flucht aus Sattelpunkten. 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 und Dacheng Tao. Quantenalgorithmus zum Finden der negativen Krümmungsrichtung bei der nichtkonvexen Optimierung, 2019. arXiv:1909.07622.
arXiv: 1909.07622

[88] Yuqian Zhang, Qing Qu und John Wright. Von der Symmetrie zur Geometrie: Behandelbare nichtkonvexe Probleme, 2021b. arXiv:2007.06753.
arXiv: 2007.06753

Zitiert von

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

Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2023, 06:02:12 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.

Konnte nicht abrufen Crossref zitiert von Daten während des letzten Versuchs 2023-06-02 12:31:15: Von Crossref konnten keine zitierten Daten für 10.22331 / q-2023-06-02-1030 abgerufen werden. Dies ist normal, wenn der DOI kürzlich registriert wurde.

Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.

SEO-gestützte Content- und PR-Distribution. Holen Sie sich noch heute Verstärkung.
PlatoAiStream. Web3-Datenintelligenz. Wissen verstärkt. Hier zugreifen.
Die Zukunft prägen mit Adryenn Ashley. Hier zugreifen.
Kaufen und verkaufen Sie Anteile an PRE-IPO-Unternehmen mit PREIPO®. Hier zugreifen.
Quelle: https://quantum-journal.org/papers/q-2023-06-02-1030/

Zeitstempel: 2. Juni 2023

Zeitstempel: 7. Juli 2022

Auf dem Weg zu einmaligen Quantenspeicher von zustandsloser Hardware

Quellcluster:

Quantenjournal

Quellknoten: 806211

Zeitstempel: 8. April 2021

Über Quantenbeschleunigungen für die nichtkonvexe Optimierung durch Quantentunnelspaziergänge

Neuauflage von Plato

Abstrakt

Populäre Zusammenfassung

► BibTeX-Daten

► Referenzen

Zitiert von

Mehr von Quantenjournal

Molekulares Quantenschaltkreisdesign: Ein graphbasierter Ansatz

Adaptive Messfilter: effiziente Strategie zur optimalen Schätzung von Quanten-Markov-Ketten

Chirale Supraleitung im dotierten Dreiecksgitter-Fermi-Hubbard-Modell in zwei Dimensionen

Objektive Trajektorien in hybrider klassischer Quantendynamik

Zustandsvorbereitungs-Booster für frühe fehlertolerante Quantenberechnung

Minimale Trotterisierungsformeln für einen zeitabhängigen Hamilton-Operator

Strenge Einschränkungen für die probabilistische Konvertierbarkeit von Quantenzuständen

Aufruf zur Redaktion 2023

Quantenmethoden für neuronale Netze und Anwendung auf die medizinische Bildklassifizierung

Projizierte Kleinste-Quadrate-Quantenprozesstomographie

Divide-and-Conquer-Verifizierungsverfahren für verrauschte Quantenberechnungen im mittleren Maßstab

Auf dem Weg zu einmaligen Quantenspeicher von zustandsloser Hardware

Über uns

Vertikale Suche & Ai

Plattform

Bleiben Sie in Verbindung

Konto