Sur les accélérations quantiques pour l'optimisation non convexe via des parcours de tunneling quantique

Republié par Platon

Suiveurs: 0

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

¹Département d'ingénierie mécanique, Université Tsinghua, 100084 Pékin, Chine
²Département de statistiques et de science des données, Université de Pennsylvanie
³Centre sur les frontières des études informatiques, Université de Pékin, 100871 Pékin, Chine
⁴École d'informatique, Université de Pékin, 100871 Pékin, Chine

Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.

Abstract

Les algorithmes classiques ne sont souvent pas efficaces pour résoudre des problèmes d’optimisation non convexes où les minima locaux sont séparés par des barrières élevées. Dans cet article, nous explorons les accélérations quantiques possibles pour l'optimisation non convexe en tirant parti de l'effet $global$ du tunneling quantique. Plus précisément, nous introduisons un algorithme quantique appelé marche tunnel quantique (QTW) et l'appliquons à des problèmes non convexes où les minima locaux sont approximativement des minima globaux. Nous montrons que QTW atteint une accélération quantique par rapport aux descentes de gradient stochastiques classiques (SGD) lorsque les barrières entre les différents minima locaux sont élevées mais minces et que les minima sont plats. Sur la base de cette observation, nous construisons un paysage spécifique à double puits, dans lequel les algorithmes classiques ne peuvent pas atteindre efficacement une cible en connaissant bien l'autre, mais QTW le peut lorsqu'on lui donne des états initiaux appropriés à proximité du puits connu. Enfin, nous corroborons nos résultats par des expériences numériques.

[Contenu intégré]

Résumé populaire

Les algorithmes classiques ne sont souvent pas efficaces pour résoudre des problèmes d’optimisation non convexes où les minima locaux sont séparés par des barrières élevées. Dans cet article, nous explorons les accélérations quantiques possibles pour l’optimisation non convexe en tirant parti de l’effet global du tunnel quantique. Plus précisément, nous introduisons un algorithme quantique appelé marche tunnel quantique (QTW) et l'appliquons à des problèmes non convexes où les minima locaux sont approximativement des minima globaux. Nous montrons que QTW atteint une accélération quantique par rapport aux descentes de gradient stochastiques classiques (SGD) lorsque les barrières entre les différents minima locaux sont élevées mais minces et que les minima sont plats. Sur la base de cette observation, nous construisons un paysage spécifique à double puits, dans lequel les algorithmes classiques ne peuvent pas atteindre efficacement une cible en connaissant bien l'autre, mais QTW le peut lorsqu'on lui donne des états initiaux appropriés à proximité du puits connu. Enfin, nous corroborons nos résultats par des expériences numériques.

► Données BibTeX

@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 pour {N}onconvex {O}ptimisation via {Q}uantum {T}unneling {W}alks}, auteur = {Liu, Yizhou et Su, Weijie J. et Li, Tongyang}, journal = {{Quantum}}, issn = {2521-327X}, éditeur = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {1030} , mois = juin, année = {2023} }

► Références

Zeyuan Allen-Zhu et Yuanzhi Li. Neon2 : Recherche de minima locaux via des oracles de premier ordre. Dans Advances in Neural Information Processing Systems, pages 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

Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade et Matus Telgarsky. Décompositions tensorielles pour l'apprentissage de modèles à variables latentes. Journal of machine learning search, 15 : 2773–2832, 2014. URL https:///jmlr.org/papers/volume15/anandkumar14b/. arXiv : 1210.7559v4.
arXiv: 1210.7559v4
https:///jmlr.org/papers/volume15/anandkumar14b/

Ben Andrews et Julie Clutterbuck. Preuve de la conjecture fondamentale de l’écart. 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

Joran van Apeldoorn et András Gilyén. Améliorations de la résolution SDP quantique avec les applications. Dans Actes du 46e Colloque international sur les automates, les langages et la programmation, volume 132 de Leibniz International Proceedings in Informatics (LIPIcs), pages 99 :1–99 :15. Château 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

Joran van Apeldoorn, András Gilyén, Sander Gribling et Ronald de Wolf. Solveurs Quantum SDP : meilleures limites supérieures et inférieures. Dans Actes du 58e Symposium annuel sur les fondements de l'informatique. IEEE, 2017. 10.1109/FOCS.2017.44. arXiv : 1705.01843.
https: / / doi.org/ 10.1109 / FOCS.2017.44
arXiv: 1705.01843

Joran van Apeldoorn, András Gilyén, Sander Gribling et Ronald de Wolf. Optimisation convexe à l'aide d'oracles quantiques. Quantique, 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

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 et Adam Zalcman. Hartree-Fock sur un ordinateur quantique à qubits supraconducteurs. 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

Yosi Atia et Shantanav Chakraborty. Limites supérieures améliorées pour les temps d’atteinte des marches quantiques. Examen physique A, 104 : 032215, septembre 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

Carlo Baldassi et Riccardo Zecchina. Efficacité du recuit quantique par rapport au recuit classique dans les problèmes d'apprentissage non convexes. Actes de l'Académie nationale des sciences, 115 (7) : 1457-1462, janvier 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

Charles H. Bennett, Ethan Bernstein, Gilles Brassard et Umesh Vazirani. Forces et faiblesses de l'informatique quantique. 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

Michael Betancourt, Michael I. Jordan et Ashia C Wilson. Sur l'optimisation symplectique, 2018. arXiv:1802.03653.
arXiv: 1802.03653

Sergio Boixo et Rolando D. Somma. Condition nécessaire pour l’approximation adiabatique quantique. Examen physique 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

Fernando GSL Brandão et Krysta Svore. Accélérations quantiques pour une programmation semi-définie. Dans Actes du 58e Symposium annuel sur les fondements de l'informatique, pages 415-426, 2017. 10.1109/FOCS.2017.45. arXiv : 1609.05537.
https: / / doi.org/ 10.1109 / FOCS.2017.45
arXiv: 1609.05537

Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore et Xiaodi Wu. Solveurs Quantum SDP : accélérations importantes, optimalité et applications à l'apprentissage quantique. Dans Actes du 46e Colloque international sur les automates, les langages et la programmation, volume 132 de Leibniz International Proceedings in Informatics (LIPIcs), pages 27 :1–27 :14. Château 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

Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li et Xiaodi Wu. Algorithmes quantiques et limites inférieures pour l'optimisation convexe. Quantique, 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

Shantanav Chakraborty, Kyle Luh et Jérémie Roland. À quelle vitesse les marches quantiques se mélangent-elles ? Lettres d'examen physique, 124 : 050501, février 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

Pratik Chaudhari et Stefano Soatto. La descente de gradient stochastique effectue une inférence variationnelle et converge pour limiter les cycles pour les réseaux profonds. En 2018, Atelier sur la théorie de l'information et ses applications (ITA), pages 1 à 10, 2018. 10.1109/ITA.2018.8503224. arXiv:1710.11029v2.
https:///doi.org/10.1109/ITA.2018.8503224
arXiv: 1710.11029v2

Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann et Daniel A. Spielman. Accélération algorithmique exponentielle par une marche quantique. Dans Actes du trente-cinquième symposium annuel de l'ACM sur la théorie de l'informatique, STOC '03, pages 59-68, New York, NY, États-Unis, 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

Andrew M. Childs, Jin-Peng Liu et Aaron Ostrander. Algorithmes quantiques de haute précision pour les équations aux dérivées partielles. Quantum, 5 : 574, novembre 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

Pierre Comon, Xavier Luciani et André LF De Almeida. Décompositions tensorielles, alternance des moindres carrés et autres contes. Journal of Chemometrics, 23 : 393-405, août 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

Pedro CS Costa, Stephen Jordan et Aaron Ostrander. Algorithme quantique pour simuler l'équation des ondes. Examen physique A, 99 : 012323, janvier 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

Christophe Criscitiello et Nicolas Boumal. Une courbure négative obstrue l'accélération pour l'optimisation géodésiquement convexe, même avec des oracles exacts de premier ordre, 2021. arXiv : 2111.13263.
arXiv: 2111.13263

Elizabeth Crosson et Aram W. Harrow. Le recuit quantique simulé peut être exponentiellement plus rapide que le recuit simulé classique. En 2016, 57e Symposium annuel de l'IEEE sur les fondements de l'informatique (FOCS), pages 714-723. IEEE, octobre 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

Mouez Dimassi et Johannes Sjöstrand. Asymptotique spectrale dans la limite semi-classique. Série de notes de cours de la London Mathematical Society. Cambridge University Press, 1999. 10.1017/CBO9780511662195.
https: / / doi.org/ 10.1017 / CBO9780511662195

Félix Draxler, Kambis Veschgini, Manfred Salmhofer et Fred Hamprecht. Essentiellement aucune barrière dans le paysage énergétique des réseaux neuronaux. Dans Conférence internationale sur l'apprentissage automatique, pages 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

Runyao Duan. Théorème adiabatique quantique revisité, 2020. arXiv:2003.03063v1.
arXiv: 2003.03063v1

John Duchi, Elad Hazan et Yoram Singer. Méthodes de sous-gradient adaptatives pour l'apprentissage en ligne et l'optimisation stochastique. 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

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ć et Mikhail D. Lukin . Phases quantiques de la matière sur un simulateur quantique programmable de 256 atomes. 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

Cong Fang, Chris Junchi Li, Zhouchen Lin et Tong Zhang. Spider : optimisation non convexe quasi optimale via un estimateur différentiel stochastique intégré au chemin. Dans Advances in Neural Information Processing Systems, pages 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

Cong Fang, Zhouchen Lin et Tong Zhang. Analyse précise des SGD non convexes s'échappant des points de selle. Dans Conférence sur la théorie de l'apprentissage, pages 1192-1234, 2019. URL http://proceedings.mlr.press/v99/fang19a.html. arXiv : 1902.00247.
arXiv: 1902.00247
http:///proceedings.mlr.press/v99/fang19a.html

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren et Daniel Preda. Un algorithme d'évolution adiabatique quantique appliqué à des instances aléatoires d'un problème NP-complet. Science, 292 (5516) : 472-475, avril 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

AB Finnila, MA Gomez, C. Sebenik, C. Stenson et JD Doll. Recuit quantique : Une nouvelle méthode pour minimiser les fonctions multidimensionnelles. 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

Mauger François. Schéma de saut de grenouille symplectique, 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

Alan Frieze, Mark Jerrum et Ravi Kannan. Apprentissage des transformations linéaires. Dans Actes de la 37e Conférence sur les fondements de l'informatique, pages 359-368, 1996. 10.1109/SFCS.1996.548495.
https: / / doi.org/ 10.1109 / SFCS.1996.548495

Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry Vetrov et Andrew Gordon Wilson. Surfaces de perte, connectivité des modes et assemblage rapide des DNN. Dans Advances in Neural Information Processing Systems, pages 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

Rong Ge et Tengyu Ma. Sur le paysage d'optimisation des décompositions tensorielles. Programmation mathématique, pages 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

Rong Ge, Furong Huang, Chi Jin et Yang Yuan. S'échapper des points selle – gradient stochastique en ligne pour la décomposition tensorielle. Dans Actes de la 28e Conférence sur la théorie de l'apprentissage, volume 40 de Proceedings of Machine Learning Research, pages 797-842, 2015. URL http://proceedings.mlr.press/v40/Ge15. arXiv : 1503.02101.
arXiv: 1503.02101
http:///proceedings.mlr.press/v40/Ge15

Rong Ge, Jason D. Lee et Tengyu Ma. L’achèvement de la matrice n’a pas de minimum local parasite. Dans Advances in Neural Information Processing Systems, pages 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

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 et Jian-Wei Pan. Quantum marche sur un processeur supraconducteur bidimensionnel programmable de 62 qubits. 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

Stephen K. Gray et David E. Manolopoulos. Intégrateurs symplectiques adaptés à l'équation de Schrödinger dépendant du temps. 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

Bernard Helffer. Analyse semi-classique pour l'opérateur de Schrödinger et ses applications. Notes de cours en mathématiques. Springer, 1988. 10.1007/BFb0078115.
https: / / doi.org/ 10.1007 / BFb0078115

Bernard Helffer et Johannes Sjöstrand. Puits multiples dans la limite semi-classique I. Communications in Partial Differential Equations, 9 (4) : 337-408, 1984. 10.1080/03605308408820335.
https: / / doi.org/ 10.1080 / 03605308408820335

Bernard Helffer et Johannes Sjöstrand. Puits multiples dans la limite semi-classique III – interaction par puits non résonants. 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

Sepp Hochreiter. Le problème du gradient de disparition lors de l'apprentissage des réseaux neuronaux récurrents et des solutions aux problèmes. Journal international de l'incertitude, du flou et des systèmes basés sur la connaissance, 6 (02) : 107-116, 1998. 10.1142/S0218488598000094. URL https:///dl.acm.org/doi/abs/10.1142/S0218488598000094.
https: / / doi.org/ 10.1142 / S0218488598000094

Aapo Hyvarinen. ICA rapide pour les données bruitées utilisant des moments gaussiens. En 1999 Symposium international de l'IEEE sur les circuits et les systèmes (ISCAS), volume 5, pages 57-61, 1999. 10.1109/ISCAS.1999.777510.
https:///doi.org/10.1109/ISCAS.1999.777510

Frédéric Hérau, Michael Hitrik et Johannes Sjöstrand. Effet tunnel et symétries pour les opérateurs de type Kramers-Fokker-Planck. Journal de l'Institut de Mathématiques de Jussieu, 10 (3) : 567–634, 2011. 10.1017/S1474748011000028.
https: / / doi.org/ 10.1017 / S1474748011000028

Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade et Michael I. Jordan. Comment échapper efficacement aux points de selle. Dans Actes de la 34e Conférence internationale sur l'apprentissage automatique, volume 70, pages 1724-1732, 2017. URL http://proceedings.mlr.press/v70/jin17a. arXiv : 1703.00887.
arXiv: 1703.00887
http:///proceedings.mlr.press/v70/jin17a

Chi Jin, Lydia T. Liu, Rong Ge et Michael I. Jordan. Sur les minima locaux du risque empirique. Dans Advances in Neural Information Processing Systems, volume 31, pages 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

Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade et Michael I. Jordan. Sur l'optimisation non convexe pour l'apprentissage automatique : gradients, stochasticité et points selle. Journal de l'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

Michael I. Jordanie. Perspectives dynamiques, symplectiques et stochastiques sur l'optimisation basée sur les gradients. Dans Actes du Congrès international des mathématiciens : Rio de Janeiro 2018, pages 523-549. Monde scientifique, 2018. URL https://doi.org/10.1142/9789813272880_0022.
https: / / doi.org/ 10.1142 / 9789813272880_0022

Kenji Kawaguchi, Jiaoyang Huang et Leslie Pack Kaelbling. Chaque valeur minimale locale est la valeur minimale globale du modèle induit dans l'apprentissage automatique non convexe. Calcul neuronal, 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

Diederik P. Kingma et Jimmy Ba. Adam : Une méthode d'optimisation stochastique. Dans 3e Conférence internationale sur les représentations d'apprentissage, 2015. URL https://openreview.net/forum?id=8gmWwjFyLj. arXiv : 1412.6980.
arXiv: 1412.6980
https:///openreview.net/forum?id=8gmWwjFyLj

Alexei Kitaev et William A. Webb. Préparation et rééchantillonnage de fonctions d'onde à l'aide d'un ordinateur quantique, 2008. arXiv :0801.0342.
arXiv: 0801.0342

Bobby Kleinberg, Yuanzhi Li et Yang Yuan. Un point de vue alternatif : quand SGD échappe-t-il aux minima locaux ? Dans Conférence internationale sur l'apprentissage automatique, pages 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

Guy Kornowski et Ohad Shamir. Complexité Oracle dans l'optimisation non fluide et non convexe. Dans 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

Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Rong Ge et Sanjeev Arora. Expliquer la connectivité paysagère des solutions à faible coût pour les réseaux multicouches. 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- réseaux multicouches. arXiv : 1906.06247.
arXiv: 1906.06247
http:///papers.nips.cc/paper/9602-explaining-landscape-connectivity-of-low-cost-solutions-for-multilayer-nets

Harold J. Kushner et G. George Yin. Approximation stochastique et algorithmes et applications récursifs, volume 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

Keren Li, Shijie Wei, Pan Gao, Feihao Zhang, Zengrong Zhou, Tao Xin, Xiaoting Wang, Patrick Rebentrost et Guilu Long. Optimisation d'une fonction polynomiale sur un processeur quantique. 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

Zhiyuan Li, Sadhika Malladi et Sanjeev Arora. Sur la validité de la modélisation SGD avec des équations différentielles stochastiques (SDE). Dans Avancées des systèmes de traitement de l’information neuronale, 2021b. URL https:///openreview.net/forum?id=goEdyJ_nVQI. arXiv :2102.12470.
arXiv: 2102.12470
https:///openreview.net/forum?id=goEdyJ_nVQI

Guang Hao Low et Nathan Wiebe. Simulation hamiltonienne dans l'image d'interaction, 2019. URL https://arxiv.org/abs/1805.00675v2. arXiv:1805.00675v2.
arXiv: 1805.00675v2

Cong Ma, Kaizheng Wang, Yuejie Chi et Yuxin Chen. Régularisation implicite dans l'estimation statistique non convexe : la descente de gradient converge linéairement pour la récupération de phase et l'achèvement de la matrice. Dans Conférence internationale sur l'apprentissage automatique, pages 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

Tengyu Ma. Pourquoi les méthodes locales résolvent-elles les problèmes non convexes ?, pages 465 à 485. Cambridge University Press, 2021. 10.1017/9781108637435.027. arXiv :2103.13462.
https: / / doi.org/ 10.1017 / 9781108637435.027
arXiv: 2103.13462

Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion et Michael I. Jordan. L'échantillonnage peut être plus rapide que l'optimisation. Actes de l'Académie nationale des 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

Peter A. Markowich et Cédric Villani. Sur la tendance à l'équilibre pour l'équation de Fokker-Planck : Une interaction entre physique et analyse fonctionnelle. Dans Physique et analyse fonctionnelle, 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

Laurent Michel. À propos des petites valeurs propres du laplacien de Witten. Analyse pure et appliquée, 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

Siddharth Muthukrishnan, Tameem Albash et Daniel A. Lidar. Tunneling et accélération dans l'optimisation quantique pour les problèmes de symétrie de permutation. Examen physique X, 6 : 031010, juillet 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

Quynh Nguyen. Sur les ensembles de sous-niveaux connectés dans l'apprentissage profond. Dans Conférence internationale sur l'apprentissage automatique, pages 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

Michael A. Nielsen et Isaac L. Chuang. Calcul quantique et information quantique : édition du 10e anniversaire. Cambridge University Press, 2010. 10.1017/CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

Grigorios A. Pavliotis. Processus stochastiques et applications : processus de diffusion, équations de Fokker-Planck et Langevin, volume 60. Springer, 2014. 10.1007/978-1-4939-1323-7.
https://doi.org/10.1007/978-1-4939-1323-7

Qing Qu, Yuexiang Zhai, Xiao Li, Yuqian Zhang et Zhihui Zhu. Analyse des paysages d'optimisation pour l'apprentissage des représentations surcomplètes, 2019. arXiv : 1912.02427.
arXiv: 1912.02427

Gianluca Rastelli. Formule semi-classique pour l'effet tunnel quantique dans les potentiels asymétriques à double puits. Examen physique A, 86 : 012106, juillet 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

Arthur G. Rattew, Yue Sun, Pierre Minssen et Marco Pistoia. La préparation efficace des distributions normales dans les registres quantiques. Quantique, 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 /

Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione et Seth Lloyd. Descente de gradient quantique et méthode de Newton pour l'optimisation polynomiale contrainte. Nouveau 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

Burak Şahinoğlu et Rolando D. Somma. Simulation hamiltonienne dans le sous-espace des basses énergies. 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

JM Schmidt, AN Cleland et John Clarke. Tunneling résonnant dans les petites jonctions Josephson polarisées par le courant. Physical Review B, 43 : 229–238, janvier 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

Alexandre Chevtchenko et Marco Mondelli. Connectivité paysagère et stabilité des décrochages des solutions SGD pour les réseaux neuronaux surparamétrés. Dans Conférence internationale sur l'apprentissage automatique, pages 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

Bin Shi, Weijie J. Su et Michael I. Jordan. Sur les taux d'apprentissage et les opérateurs de Schrödinger, 2020. arXiv :2004.06977.
arXiv: 2004.06977

Bin Shi, Simon S. Du, Michael I. Jordan et Weijie J. Su. Comprendre le phénomène d'accélération via des équations différentielles à haute résolution. Programmation mathématique, pages 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

Weijie Su, Stephen Boyd et Emmanuel J. Candes. Une équation différentielle pour modéliser la méthode du gradient accéléré de Nesterov : théorie et connaissances. Le 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

Soleil Ruoyu. Optimisation pour l'apprentissage profond : théorie et algorithmes, 2019. arXiv :1912.08957.
arXiv: 1912.08957

Kunal Talwar. Séparations informatiques entre échantillonnage et optimisation. 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

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, et Xian-Min Jin. Marche quantique expérimentale bidimensionnelle sur puce photonique. Avancées scientifiques, 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

Cédric Villani. Hypocoercivité, volume 202 des Mémoires de l'American Mathematical Society. Société mathématique américaine, 2009. 10.1090/S0065-9266-09-00567-5. arXiv:math/0609050.
https://doi.org/10.1090/S0065-9266-09-00567-5
arXiv: math / 0609050

André Wibisono, Ashia C. Wilson et Michael I. Jordan. Une perspective variationnelle sur les méthodes accélérées en optimisation. Actes de l'Académie nationale des 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

Chenyi Zhang et Tongyang Li. Échappez aux points de selle grâce à un simple algorithme basé sur la descente de gradient. Dans Advances in Neural Information Processing Systems, volume 34, 2021. URL https:///openreview.net/forum?id=lEf52hTHq0Q. arXiv :2111.14069.
arXiv: 2111.14069
https:///openreview.net/forum?id=lEf52hTHq0Q

Chenyi Zhang, Jiaqi Leng et Tongyang Li. Algorithmes quantiques pour s'échapper des points de selle. Quantique, 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

Kaining Zhang, Min-Hsiu Hsieh, Liu Liu et Dacheng Tao. Algorithme quantique pour trouver la direction de courbure négative dans l'optimisation non convexe, 2019. arXiv :1909.07622.
arXiv: 1909.07622

Yuqian Zhang, Qing Qu et John Wright. De la symétrie à la géométrie : problèmes non convexes traitables, 2021b. arXiv :2007.06753.
arXiv: 2007.06753

Cité par

[1] Weiyuan Gong, Chenyi Zhang et Tongyang Li, « Robustesse des algorithmes quantiques pour l'optimisation non convexe », arXiv: 2212.02548, (2022).

Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2023-06-02 12:31:17). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.

Impossible de récupérer Données de référence croisée lors de la dernière tentative 2023-06-02 12:31:15: Impossible de récupérer les données citées par 10.22331 / q-2023-06-02-1030 de Crossref. C'est normal si le DOI a été enregistré récemment.

Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.

Contenu propulsé par le référencement et distribution de relations publiques. Soyez amplifié aujourd'hui.
PlatoAiStream. Intelligence des données Web3. Connaissance Amplifiée. Accéder ici.
Frapper l'avenir avec Adryenn Ashley. Accéder ici.
Achetez et vendez des actions de sociétés PRE-IPO avec PREIPO®. Accéder ici.
La source: https://quantum-journal.org/papers/q-2023-06-02-1030/

Horodatage: Le 2 juin 2023

Horodatage: Le 7 juillet 2022

Vers des mémoires uniques quantiques à partir de matériel sans état

Cluster source:

Journal quantique

Nœud source: 806211

Horodatage: 8 avril 2021

Sur les accélérations quantiques pour l'optimisation non convexe via les marches de tunnel quantique

Republié par Platon

Abstract

Résumé populaire

► Données BibTeX

► Références

Cité par

Plus de Journal quantique

Conception de circuits quantiques moléculaires : une approche basée sur les graphes

Filtre de mesure adaptatif : stratégie efficace pour une estimation optimale des chaînes de Markov quantiques

Supraconductivité chirale dans le modèle de Fermi-Hubbard à réseau triangulaire dopé en deux dimensions

Trajectoires objectives en dynamique hybride classique-quantique

Amplificateurs de préparation d'état pour le calcul quantique précoce tolérant aux pannes

Formules de trottérisation minimale pour un hamiltonien dépendant du temps

Contraintes strictes sur la convertibilité probabiliste des états quantiques

Appel à rédaction 2023

Méthodes quantiques pour les réseaux de neurones et application à la classification des images médicales

Tomographie par processus quantique projetée des moindres carrés

Méthode de vérification diviser pour mieux régner pour le calcul quantique bruyant à échelle intermédiaire

Vers des mémoires uniques quantiques à partir de matériel sans état

À propos de nous

Recherche verticale et Ai

Plateforme

Restez à l'affût

Compte