Sobre acelerações quânticas para otimização não convexa por meio de caminhadas por túneis quânticos

Sobre acelerações quânticas para otimização não convexa por meio de caminhadas por túneis quânticos

Carimbo de data / hora: 2 de junho de 2023 8h23
Nó Fonte: 2694596

Yizhou Liu1, Weijie J. Su2e Tongyang Li3,4

1Departamento de Mecânica de Engenharia, Universidade de Tsinghua, 100084 Pequim, China
2Departamento de Estatística e Ciência de Dados, Universidade da Pensilvânia
3Center on Frontiers of Computing Studies, Universidade de Pequim, 100871 Pequim, China
4Escola de Ciência da Computação, Universidade de Pequim, 100871 Pequim, China

Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.

Sumário

Os algoritmos clássicos muitas vezes não são eficazes para resolver problemas de otimização não convexa, onde os mínimos locais são separados por altas barreiras. Neste artigo, exploramos possíveis acelerações quânticas para otimização não convexa, aproveitando o efeito $global$ do tunelamento quântico. Especificamente, introduzimos um algoritmo quântico denominado quantum tunneling walk (QTW) e o aplicamos a problemas não convexos em que mínimos locais são aproximadamente mínimos globais. Mostramos que o QTW atinge um aumento de velocidade quântica sobre descendentes de gradiente estocástico clássico (SGD) quando as barreiras entre diferentes mínimos locais são altas, mas finas e os mínimos são planos. Com base nessa observação, construímos uma paisagem específica de poço duplo, onde os algoritmos clássicos não podem atingir um alvo com eficiência, conhecendo bem o outro, mas o QTW pode, quando dados os estados iniciais adequados próximos ao poço conhecido. Finalmente, corroboramos nossos achados com experimentos numéricos.

[Conteúdo incorporado]

Resumo popular

Os algoritmos clássicos muitas vezes não são eficazes para resolver problemas de otimização não convexa, onde os mínimos locais são separados por altas barreiras. Neste artigo, exploramos possíveis acelerações quânticas para otimização não convexa, aproveitando o efeito global do tunelamento quântico. Especificamente, introduzimos um algoritmo quântico denominado quantum tunneling walk (QTW) e o aplicamos a problemas não convexos em que mínimos locais são aproximadamente mínimos globais. Mostramos que o QTW atinge um aumento de velocidade quântica sobre descendentes de gradiente estocástico clássico (SGD) quando as barreiras entre diferentes mínimos locais são altas, mas finas e os mínimos são planos. Com base nessa observação, construímos uma paisagem específica de poço duplo, onde os algoritmos clássicos não podem atingir um alvo com eficiência, conhecendo bem o outro, mas o QTW pode, quando dados os estados iniciais adequados próximos ao poço conhecido. Finalmente, corroboramos nossos achados com experimentos numéricos.

► dados BibTeX

► Referências

[1] Zeyuan Allen-Zhu e Yuanzhi Li. Neon2: Encontrando mínimos locais via oráculos de primeira ordem. Em Advances in Neural Information Processing Systems, páginas 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 e Matus Telgarsky. Decomposições tensorais para aprendizagem de modelos de variáveis ​​latentes. 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 e Julie Clutterbuck. Prova da conjectura do intervalo 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/ stable / 23072145

[4] Joran van Apeldoorn e András Gilyén. Melhorias na solução SDP quântica com aplicativos. Em Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 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 e Ronald de Wolf. Solucionadores SDP quânticos: Melhores limites superior e inferior. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science. IEEE, 2017. 10.1109/​FOCS.2017.44. arXiv:1705.01843.
https: / / doi.org/ 10.1109 / FOCS.2017.44
arXiv: 1705.01843

[6] Joran van Apeldoorn, András Gilyén, Sander Gribling e Ronald de Wolf. Otimização convexa usando oráculos quânticos. 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 e Adam Zalcman. Hartree-Fock em um computador quântico qubit supercondutor. 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 e Shantanav Chakraborty. Limites superiores aprimorados para os tempos de acerto de caminhadas quânticas. Physical Review A, 104: 032215, setembro de 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 e Riccardo Zecchina. Eficiência do recozimento quântico vs. clássico em problemas de aprendizado não convexos. Proceedings of the National Academy of Sciences, 115 (7): 1457–1462, janeiro de 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 e Umesh Vazirani. Pontos fortes e fracos da computação quântica. 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 e Ashia C Wilson. Sobre otimização simplética, 2018. arXiv:1802.03653.
arXiv: 1802.03653

[12] Sergio Boixo e Rolando D. Somma. Condição necessária para a aproximação adiabática quântica. 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 e Krysta Svore. Aceleração quântica para programação semidefinida. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science, páginas 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 e Xiaodi Wu. Solucionadores SDP quânticos: Grandes aumentos de velocidade, otimização e aplicações para aprendizado quântico. Em Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 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 e Xiaodi Wu. Algoritmos quânticos e limites inferiores para otimização convexa. 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 e Jérémie Roland. Com que rapidez as caminhadas quânticas se misturam? Physical Review Letters, 124: 050501, fevereiro de 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 e Stefano Soatto. A descida do gradiente estocástico executa inferência variacional, converge para limitar os ciclos para redes profundas. Em 2018 Information Theory and Applications Workshop (ITA), páginas 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 e Daniel A. Spielman. Aceleração algorítmica exponencial por uma caminhada quântica. Em Anais do Trigésimo Quinto Simpósio Anual da ACM sobre Teoria da Computação, STOC '03, página 59–68, Nova York, NY, EUA, 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 e Aaron Ostrander. Algoritmos quânticos de alta precisão para equações diferenciais parciais. Quantum, 5: 574, novembro de 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 e André LF De Almeida. Decomposições tensorais, mínimos quadrados alternados e outros contos. Journal of Chemometrics, 23: 393–405, agosto de 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 e Aaron Ostrander. Algoritmo quântico para simulação da equação de onda. Physical Review A, 99: 012323, janeiro de 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 e Nicolas Boumal. A curvatura negativa obstrui a aceleração para otimização geodesicamente convexa, mesmo com oráculos exatos de primeira ordem, 2021. arXiv:2111.13263.
arXiv: 2111.13263

[23] Elizabeth Crosson e Aram W. Harrow. O recozimento quântico simulado pode ser exponencialmente mais rápido do que o recozimento simulado clássico. Em 2016 IEEE 57º Simpósio Anual sobre Fundamentos da Ciência da Computação (FOCS), páginas 714–723. IEEE, out 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 e Johannes Sjöstrand. Assintóticas Espectrais no Limite Semi-Clássico. 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 e Fred Hamprecht. Essencialmente sem barreiras no cenário de energia da rede neural. Na Conferência Internacional sobre Machine Learning, páginas 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 adiabático quântico revisitado, 2020. arXiv:2003.03063v1.
arXiv: 2003.03063v1

[27] John Duchi, Elad Hazan e Yoram Singer. Métodos subgradientes adaptativos para aprendizado online e otimização estocástica. 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ć e Mikhail D. Lukin . Fases quânticas da matéria em um simulador quântico programável de 256 átomos. 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 e Tong Zhang. Spider: Otimização não convexa quase ideal via estimador diferencial estocástico integrado ao caminho. Em Advances in Neural Information Processing Systems, páginas 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 e Tong Zhang. Análise nítida para SGD não convexo escapando de pontos de sela. Em Conference on Learning Theory, páginas 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 e Daniel Preda. Um algoritmo de evolução adiabática quântica aplicado a instâncias aleatórias de um problema NP-completo. Science, 292 (5516): 472–475, abril de 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 e JD Doll. Recozimento Quântico: Um novo método para minimizar funções multidimensionais. Chemical Physics Letters, 219 (5-6): 343–348, março de 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. Esquema Symplectic Leap Frog, 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 e Ravi Kannan. Aprendendo transformações lineares. Em Proceedings of 37th Conference on Foundations of Computer Science, páginas 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 e Andrew Gordon Wilson. Superfícies de perda, conectividade de modo e montagem rápida de DNNs. Em Advances in Neural Information Processing Systems, páginas 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 e Tengyu Ma. Sobre o cenário de otimização de decomposições de tensores. Programação matemática, páginas 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 e Yang Yuan. Escapando de pontos de sela – gradiente estocástico online para decomposição tensorial. Em Proceedings of the 28th Conference on Learning Theory, volume 40 de Proceedings of Machine Learning Research, páginas 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 e Tengyu Ma. A completação da matriz não tem mínimos locais espúrios. Em Advances in Neural Information Processing Systems, páginas 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 e Jian-Wei Pan. Quantum caminha sobre um processador supercondutor bidimensional programável 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

[40] Stephen K. Gray e David E. Manolopoulos. Integradores simpléticos adaptados à equação de Schrödinger dependente do tempo. 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. Análise Semi-Clássica para o Operador de Schrödinger e Aplicações. Notas de aula em matemática. Springer, 1988. 10.1007/​BFb0078115.
https: / / doi.org/ 10.1007 / BFb0078115

[42] Bernard Helffer e Johannes Sjöstrand. Poços múltiplos no limite semiclássico I. Communications in Partial Differential Equations, 9 (4): 337–408, 1984. 10.1080/03605308408820335.
https: / / doi.org/ 10.1080 / 03605308408820335

[43] Bernard Helffer e Johannes Sjöstrand. Poços múltiplos no limite semiclássico III – interação através de poços não ressonantes. 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. O problema do gradiente de fuga durante o aprendizado de redes neurais recorrentes e soluções de problemas. 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. Fast ICA para dados ruidosos usando momentos gaussianos. Em 1999 IEEE International Symposium on Circuits and Systems (ISCAS), volume 5, páginas 57–61, 1999. 10.1109/​ISCAS.1999.777510.
https://​/​doi.org/​10.1109/​ISCAS.1999.777510

[46] Frédéric Hérau, Michael Hitrik e Johannes Sjöstrand. Efeito túnel e simetrias para operadores do tipo kramers-fokker-planck. Journal of the Institute of Mathematics of Jussieu, 10 (3): 567–634, 2011. 10.1017/​S1474748011000028.
https: / / doi.org/ 10.1017 / S1474748011000028

[47] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade e Michael I. Jordan. Como escapar dos pontos de sela com eficiência. Em Proceedings of the 34th International Conference on Machine Learning, volume 70, páginas 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 e Michael I. Jordan. Sobre os mínimos locais do risco empírico. Em Advances in Neural Information Processing Systems, volume 31, página 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 e Michael I. Jordan. Na otimização não convexa para aprendizado de máquina: Gradientes, estocasticidade e pontos de sela. 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. Perspectivas dinâmicas, simpléticas e estocásticas na otimização baseada em gradiente. Em Anais do Congresso Internacional de Matemáticos: Rio de Janeiro 2018, páginas 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 e Leslie Pack Kaelbling. Cada valor mínimo local é o valor mínimo global do modelo induzido no aprendizado de máquina não convexo. 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 e Jimmy Ba. Adam: Um método para otimização estocástica. 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 e William A. Webb. Preparação e reamostragem da função de onda usando um computador quântico, 2008. arXiv:0801.0342.
arXiv: 0801.0342

[54] Bobby Kleinberg, Yuanzhi Li e Yang Yuan. Uma visão alternativa: quando SGD escapa de mínimos locais? Na Conferência Internacional sobre Machine Learning, páginas 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 e Ohad Shamir. Complexidade do Oracle em otimização não suave e não convexa. 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 e Sanjeev Arora. Explicando a conectividade de paisagem de soluções de baixo custo para redes multicamadas. 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- redes multicamadas. 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 e G. George Yin. Aproximação estocástica e algoritmos recursivos e aplicações, 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

[58] Keren Li, Shijie Wei, Pan Gao, Feihao Zhang, Zengrong Zhou, Tao Xin, Xiaoting Wang, Patrick Rebentrost e Guilu Long. Otimizando uma função polinomial em um processador quântico. 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 e Sanjeev Arora. Sobre a validade da modelagem SGD com equações diferenciais estocásticas (SDEs). Em Avanços em Sistemas de Processamento de Informação Neural, 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 e Nathan Wiebe. Simulação hamiltoniana na imagem de interação, 2019. URL https:/​/​arxiv.org/​abs/​1805.00675v2. arXiv:1805.00675v2.
arXiv: 1805.00675v2

[61] Cong Ma, Kaizheng Wang, Yuejie Chi e Yuxin Chen. Regularização implícita na estimativa estatística não convexa: a descida do gradiente converge linearmente para recuperação de fase e conclusão da matriz. Na Conferência Internacional sobre Machine Learning, páginas 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. Por que os métodos locais resolvem problemas não convexos?, página 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 e Michael I. Jordan. A amostragem pode ser mais rápida que a otimização. 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 e Cédric Villani. Sobre a tendência ao equilíbrio para a equação de Fokker-Planck: uma interação entre física e análise funcional. 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. Sobre pequenos autovalores do laplaciano de Witten. Análise Pura e Aplicada, 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 e Daniel A. Lidar. Tunneling e speedup em otimização quântica para problemas de permutação simétrica. Physical Review X, 6: 031010, julho de 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. Em conjuntos de subníveis conectados em aprendizado profundo. Na Conferência Internacional sobre Machine Learning, páginas 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 e Isaac L. Chuang. Computação Quântica e Informação Quântica: Edição do 10º Aniversário. Cambridge University Press, 2010. 10.1017 / CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[69] Grigorios A. Pavliotis. Processos estocásticos e aplicações: processos de difusão, equações de Fokker-Planck e Langevin, volume 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 e Zhihui Zhu. Análise das paisagens de otimização para aprendizagem de representação supercompleta, 2019. arXiv:1912.02427.
arXiv: 1912.02427

[71] Gianluca Rastelli. Fórmula semiclássica para tunelamento quântico em potenciais de poço duplo assimétricos. Physical Review A, 86: 012106, julho de 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 e Marco Pistoia. A preparação eficiente de distribuições normais em registradores quânticos. 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 e Seth Lloyd. Descida de gradiente quântico e método de Newton para otimização polinomial restrita. 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 e Rolando D. Somma. Simulação hamiltoniana no subespaço de baixa energia. 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 e John Clarke. Tunelamento ressonante em pequenas junções Josephson polarizadas por corrente. Physical Review B, 43: 229–238, janeiro de 1991. 10.1103/PhysRevB.43.229. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevB.43.229.
https: / / doi.org/ 10.1103 / PhysRevB.43.229

[76] Alexander Shevchenko e Marco Mondelli. Conectividade de paisagem e estabilidade de dropout de soluções SGD para redes neurais superparametrizadas. Na Conferência Internacional sobre Machine Learning, páginas 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 e Michael I. Jordan. Sobre taxas de aprendizado e operadores de Schrödinger, 2020. arXiv:2004.06977.
arXiv: 2004.06977

[78] Bin Shi, Simon S. Du, Michael I. Jordan e Weijie J. Su. Compreender o fenómeno da aceleração através de equações diferenciais de alta resolução. Programação matemática, páginas 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 e Emmanuel J. Candes. Uma equação diferencial para modelar o método de gradiente acelerado de Nesterov: Teoria e percepções. 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. Otimização para aprendizado profundo: teoria e algoritmos, 2019. arXiv:1912.08957.
arXiv: 1912.08957

[81] Kunal Talwar. Separações computacionais entre amostragem e otimização. 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, e Xian-Min Jin. Caminhada quântica bidimensional experimental em um chip fotônico. 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. Hipocoercividade, volume 202 de Memoirs of the American Mathematical Society. American Mathematical Society, 2009. 10.1090/​S0065-9266-09-00567-5. arXiv:math/0609050.
https:/​/​doi.org/​10.1090/​S0065-9266-09-00567-5
arXiv: math / 0609050

[84] Andre Wibisono, Ashia C. Wilson e Michael I. Jordan. Uma perspectiva variacional sobre métodos acelerados em otimização. 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 e Tongyang Li. Escape dos pontos de sela por um algoritmo simples baseado em gradiente descendente. In 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

[86] Chenyi Zhang, Jiaqi Leng e Tongyang Li. Algoritmos quânticos para escapar de pontos de sela. 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 e Dacheng Tao. Algoritmo quântico para encontrar a direção da curvatura negativa na otimização não convexa, 2019. arXiv:1909.07622.
arXiv: 1909.07622

[88] Yuqian Zhang, Qing Qu e John Wright. Da simetria à geometria: problemas não convexos tratáveis, 2021b. arXiv:2007.06753.
arXiv: 2007.06753

Citado por

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

As citações acima são de SAO / NASA ADS (última atualização com êxito 2023-06-02 12:31:17). A lista pode estar incompleta, pois nem todos os editores fornecem dados de citação adequados e completos.

Não foi possível buscar Dados citados por referência cruzada durante a última tentativa 2023-06-02 12:31:15: Não foi possível buscar os dados citados por 10.22331 / q-2023-06-02-1030 do Crossref. Isso é normal se o DOI foi registrado recentemente.

Este artigo é publicado na Quantum sob o Atribuição 4.0 do Creative Commons Internacional (CC BY 4.0) licença. Os direitos autorais permanecem com os detentores originais, como os autores ou suas instituições.

Carimbo de hora:

Mais de Diário Quântico