Om Quantum Speedups til ikke-konveks optimering via Quantum Tunneling Walks

Genudgivet af Platon

Abonnenter: 0

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

¹Department of Engineering Mechanics, Tsinghua University, 100084 Beijing, Kina
²Institut for Statistik og Datavidenskab, University of Pennsylvania
³Center on Frontiers of Computing Studies, Peking University, 100871 Beijing, Kina
⁴School of Computer Science, Peking University, 100871 Beijing, Kina

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Klassiske algoritmer er ofte ikke effektive til at løse ikke-konvekse optimeringsproblemer, hvor lokale minima er adskilt af høje barrierer. I dette papir undersøger vi mulige kvantehastigheder for ikke-konveks optimering ved at udnytte den $globale$ effekt af kvantetunnelering. Specifikt introducerer vi en kvantealgoritme kaldet quantum tunneling walk (QTW) og anvender den på ikke-konvekse problemer, hvor lokale minima er omtrent globale minima. Vi viser, at QTW opnår kvantehastigheder i forhold til klassiske stokastiske gradientnedstigninger (SGD), når barriererne mellem forskellige lokale minima er høje, men tynde, og minima er flade. Baseret på denne observation konstruerer vi et specifikt dobbeltbrøndslandskab, hvor klassiske algoritmer ikke effektivt kan ramme det ene mål velkendende til det andet, men QTW kan, når det gives korrekte begyndelsestilstande nær den kendte brønd. Til sidst bekræfter vi vores resultater med numeriske eksperimenter.

[Indlejret indhold]

Populært resumé

Klassiske algoritmer er ofte ikke effektive til at løse ikke-konvekse optimeringsproblemer, hvor lokale minima er adskilt af høje barrierer. I dette papir undersøger vi mulige kvantehastigheder til ikke-konveks optimering ved at udnytte den globale effekt af kvantetunnelering. Specifikt introducerer vi en kvantealgoritme kaldet quantum tunneling walk (QTW) og anvender den på ikke-konvekse problemer, hvor lokale minima er omtrent globale minima. Vi viser, at QTW opnår kvantehastigheder i forhold til klassiske stokastiske gradientnedstigninger (SGD), når barriererne mellem forskellige lokale minima er høje, men tynde, og minima er flade. Baseret på denne observation konstruerer vi et specifikt dobbeltbrøndslandskab, hvor klassiske algoritmer ikke effektivt kan ramme det ene mål velkendende til det andet, men QTW kan, når det gives korrekte begyndelsestilstande nær den kendte brønd. Til sidst bekræfter vi vores resultater med numeriske eksperimenter.

► BibTeX-data

@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 for {N}onkonveks {O}-optimering via {Q}uantum {T}unneling {W}alks}, forfatter = {Liu, Yizhou og Su, Weijie J. og Li, Tongyang}, tidsskrift = {{Quantum}}, issn = {2521-327X}, udgiver = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, bind = {7}, sider = {1030} , måned = jun, år = {2023} }

► Referencer

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

[2] Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade og Matus Telgarsky. Tensornedbrydninger til indlæring af latente variable modeller. Journal of machine learning research, 15: 2773–2832, 2014. URL https:///jmlr.org/papers/volume15/anandkumar14b/. arXiv:1210.7559v4.
arXiv:1210.7559v4
https:///jmlr.org/papers/volume15/anandkumar14b/

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

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

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

[6] Joran van Apeldoorn, András Gilyén, Sander Gribling og Ronald de Wolf. Konveks optimering ved hjælp af kvanteorakler. Quantum, 4: 220, 2020. 10.22331/q-2020-01-13-220. arXiv:1809.00643.
https://doi.org/10.22331/q-2020-01-13-220
arXiv: 1809.00643

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

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

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

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

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

[12] Sergio Boixo og Rolando D. Somma. Nødvendig betingelse for den kvanteadiabatiske tilnærmelse. 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 og Krysta Svore. Kvantehastigheder til semidefinite programmering. I Proceedings of the 58th Annual Symposium on Foundations of Computer Science, side 415-426, 2017. 10.1109/FOCS.2017.45. arXiv:1609.05537.
https:///doi.org/10.1109/FOCS.2017.45
arXiv: 1609.05537

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

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

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

[17] Pratik Chaudhari og Stefano Soatto. Stokastisk gradientnedstigning udfører variationsslutning, konvergerer for at begrænse cyklusser for dybe netværk. I 2018 Information Theory and Applications Workshop (ITA), side 1-10, 2018. 10.1109/ITA.2018.8503224. arXiv:1710.11029v2.
https:///doi.org/10.1109/ITA.2018.8503224
arXiv:1710.11029v2

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

[19] Andrew M. Childs, Jin-Peng Liu og Aaron Ostrander. Højpræcisions kvantealgoritmer til partielle differentialligninger. Quantum, 5: 574, nov 2021. ISSN 2521-327X. 10.22331/q-2021-11-10-574. URL http://dx.doi.org/10.22331/q-2021-11-10-574. arXiv:2002.07868.
https://doi.org/10.22331/q-2021-11-10-574
arXiv: 2002.07868

[20] Pierre Comon, Xavier Luciani og André LF De Almeida. Tensor-nedbrydninger, skiftevis mindste kvadrater og andre fortællinger. Journal of Chemometrics, 23: 393–405, august 2009. 10.1002/cem.1236. URL https:///hal.archives-ouvertes.fr/hal-00410057.
https:///doi.org/10.1002/cem.1236
https:///hal.archives-ouvertes.fr/hal-00410057

[21] Pedro CS Costa, Stephen Jordan og Aaron Ostrander. Kvantealgoritme til simulering af bølgeligningen. Physical Review A, 99: 012323, jan 2019. 10.1103/PhysRevA.99.012323. URL https:///link.aps.org/doi/10.1103/PhysRevA.99.012323. arXiv:1711.05394.
https:///doi.org/10.1103/PhysRevA.99.012323
arXiv: 1711.05394

[22] Christopher Criscitiello og Nicolas Boumal. Negativ krumning hindrer acceleration for geodætisk konveks optimering, selv med nøjagtige førsteordens orakler, 2021. arXiv:2111.13263.
arXiv: 2111.13263

[23] Elizabeth Crosson og Aram W. Harrow. Simuleret kvanteudglødning kan være eksponentielt hurtigere end klassisk simuleret udglødning. I 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), side 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 og Johannes Sjöstrand. Spektral asymptotik i den semi-klassiske grænse. London Mathematical Society Lecture Note Series. Cambridge University Press, 1999. 10.1017/CBO9780511662195.
https:///doi.org/10.1017/CBO9780511662195

[25] Felix Draxler, Kambis Veschgini, Manfred Salmhofer og Fred Hamprecht. I det væsentlige ingen barrierer i det neurale netværks energilandskab. I International Conference on Machine Learning, side 1309-1318. PMLR, 2018. URL http:///proceedings.mlr.press/v80/draxler18a.html. arXiv:1803.00885.
arXiv: 1803.00885
http:///proceedings.mlr.press/v80/draxler18a.html

[26] Runyao Duan. Kvanteadiabatisk sætning revisited, 2020. arXiv:2003.03063v1.
arXiv:2003.03063v1

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

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

[29] Cong Fang, Chris Junchi Li, Zhouchen Lin og Tong Zhang. Spider: Næsten optimal ikke-konveks optimering via stokastisk vej-integreret differentialestimator. In Advances in Neural Information Processing Systems, side 689-699, 2018. URL https:///dl.acm.org/doi/abs/10.5555/3326943.3327007. arXiv:1807.01695.
arXiv: 1807.01695
https:///dl.acm.org/doi/abs/10.5555/3326943.3327007

[30] Cong Fang, Zhouchen Lin og Tong Zhang. Skarp analyse for ikke-konveks SGD, der undslipper fra saddelpunkter. I Conference on Learning Theory, side 1192-1234, 2019. URL http:///proceedings.mlr.press/v99/fang19a.html. arXiv:1902.00247.
arXiv: 1902.00247
http:///proceedings.mlr.press/v99/fang19a.html

[31] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren og Daniel Preda. En kvante-adiabatisk evolutionsalgoritme anvendt på tilfældige tilfælde af et NP-komplet problem. Science, 292 (5516): 472-475, apr 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 og JD Doll. Quantum annealing: En ny metode til at minimere multidimensionelle funktioner. Chemical Physics Letters, 219 (5-6): 343-348, Mar 1994. ISSN 0009-2614. 10.1016/0009-2614(94)00117-0. URL http://dx.doi.org/10.1016/0009-2614(94)00117-0. arXiv:chem-ph/9404003.
https://doi.org/10.1016/0009-2614(94)00117-0
arXiv:chem-ph/9404003

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

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

[35] Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry Vetrov og Andrew Gordon Wilson. Tabsflader, tilstandsforbindelse og hurtig sammensætning af DNN'er. In Advances in Neural Information Processing Systems, side 8803–8812, 2018. URL https:///dl.acm.org/doi/abs/10.5555/3327546.3327556. arXiv:1802.10026.
arXiv: 1802.10026
https:///dl.acm.org/doi/abs/10.5555/3327546.3327556

[36] Rong Ge og Tengyu Ma. Om optimeringslandskabet af tensornedbrydninger. Matematisk programmering, side 1-47, 2020. ISSN 1436-4646. 10.1007/s10107-020-01579-x. URL https://doi.org/10.1007/s10107-020-01579-x. arXiv:1706.05598v1.
https:///doi.org/10.1007/s10107-020-01579-x
arXiv:1706.05598v1

[37] Rong Ge, Furong Huang, Chi Jin og Yang Yuan. Undslippe fra saddelpunkter - online stokastisk gradient til tensornedbrydning. I Proceedings of the 28th Conference on Learning Theory, bind 40 af Proceedings of Machine Learning Research, side 797–842, 2015. URL http:///proceedings.mlr.press/v40/Ge15. arXiv:1503.02101.
arXiv: 1503.02101
http:///proceedings.mlr.press/v40/Ge15

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

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

[40] Stephen K. Gray og David E. Manolopoulos. Symplektiske integratorer skræddersyet til den tidsafhængige schrödinger-ligning. The Journal of Chemical Physics, 104 (18): 7099–7112, 1996. 10.1063/1.471428. URL https://doi.org/10.1063/1.471428.
https:///doi.org/10.1063/1.471428

[41] Bernard Helffer. Semi-klassisk analyse for Schrödinger-operatøren og applikationer. Forelæsningsnotater i matematik. Springer, 1988. 10.1007/BFb0078115.
https://doi.org/10.1007/BFb0078115

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

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

[44] Sepp Hochreiter. Problemet med forsvindende gradient under indlæring af tilbagevendende neurale net og problemløsninger. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 6 (02): 107–116, 1998. 10.1142/S0218488598000094. URL https:///dl.acm.org/doi/abs/10.1142/S0218488598000094.
https:///doi.org/10.1142/S0218488598000094

[45] Aapo Hyvarinen. Hurtig ICA til støjende data ved hjælp af gaussiske øjeblikke. I 1999 IEEE International Symposium on Circuits and Systems (ISCAS), bind 5, side 57-61, 1999. 10.1109/ISCAS.1999.777510.
https:///doi.org/10.1109/ISCAS.1999.777510

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

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

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

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

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

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

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

[53] Alexei Kitaev og William A. Webb. Bølgefunktionsforberedelse og resampling ved hjælp af en kvantecomputer, 2008. arXiv:0801.0342.
arXiv: 0801.0342

[54] Bobby Kleinberg, Yuanzhi Li og Yang Yuan. Et alternativt synspunkt: Hvornår undslipper SGD lokale minima? I International Conference on Machine Learning, side 2698-2707. PMLR, 2018. URL http:///proceedings.mlr.press/v80/kleinberg18a.html. arXiv:1802.06175.
arXiv: 1802.06175
http:///proceedings.mlr.press/v80/kleinberg18a.html

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

[56] Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Rong Ge og Sanjeev Arora. Forklaring af landskabelige tilslutningsmuligheder for lavprisløsninger til flerlagsnet. 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- flerlags-net. arXiv:1906.06247.
arXiv: 1906.06247
http:///papers.nips.cc/paper/9602-explaining-landscape-connectivity-of-low-cost-solutions-for-multilayer-nets

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

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

[59] Zhiyuan Li, Sadhika Malladi og Sanjeev Arora. Om gyldigheden af modellering af SGD med stokastiske differentialligninger (SDE'er). In Advances in Neurale Information Processing Systems, 2021b. URL https:///openreview.net/forum?id=goEdyJ_nVQI. arXiv:2102.12470.
arXiv: 2102.12470
https:///openreview.net/forum?id=goEdyJ_nVQI

[60] Guang Hao Low og Nathan Wiebe. Hamiltonsimulering i interaktionsbilledet, 2019. URL https:///arxiv.org/abs/1805.00675v2. arXiv:1805.00675v2.
arXiv:1805.00675v2

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

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

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

[64] Peter A. Markowich og Cédric Villani. Om tendensen til ligevægt for Fokker-Planck-ligningen: Et samspil mellem fysik og funktionel analyse. In Physics and Functional Analysis, Matematica Contemporanea (SBM) 19. Citeseer, 1999. URL http:///citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.2278.
http:///citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.2278

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

[66] Siddharth Muthukrishnan, Tameem Albash og Daniel A. Lidar. Tunnelering og fremskyndelse af kvanteoptimering til permutationssymmetriske problemer. Fysisk gennemgang X, 6: 031010, jul 2016. ISSN 2160-3308. 10.1103/physrevx.6.031010. URL http://dx.doi.org/10.1103/PhysRevX.6.031010. arXiv:1511.03910.
https:///doi.org/10.1103/physrevx.6.031010
arXiv: 1511.03910

[67] Quynh Nguyen. På forbundet underniveau sætter i dyb læring. I International Conference on Machine Learning, side 4790–4799. PMLR, 2019. URL http:///proceedings.mlr.press/v97/nguyen19a.html. arXiv:1901.07417.
arXiv: 1901.07417
http:///proceedings.mlr.press/v97/nguyen19a.html

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

[69] Grigorios A. Pavliotis. Stokastiske processer og anvendelser: diffusionsprocesser, Fokker-Planck- og Langevin-ligningerne, bind 60. Springer, 2014. 10.1007/978-1-4939-1323-7.
https://doi.org/10.1007/978-1-4939-1323-7

[70] Qing Qu, Yuexiang Zhai, Xiao Li, Yuqian Zhang og Zhihui Zhu. Analyse af optimeringslandskaberne for overkomplet repræsentationslæring, 2019. arXiv:1912.02427.
arXiv: 1912.02427

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

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

[73] Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione og Seth Lloyd. Quantum gradient descent og Newtons metode til begrænset polynomiel optimering. New Journal of Physics, 21 (7): 073023, 2019. 10.1088/1367-2630/ab2a9e. arXiv:1612.01789.
https://doi.org/10.1088/1367-2630/ab2a9e
arXiv: 1612.01789

[74] Burak Şahinoğlu og Rolando D. Somma. Hamiltonsimulering i lavenergiunderrummet. 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 og John Clarke. Resonant tunneling i små strømforspændte Josephson-kryds. Physical Review B, 43: 229–238, jan 1991. 10.1103/PhysRevB.43.229. URL https://link.aps.org/doi/10.1103/PhysRevB.43.229.
https:///doi.org/10.1103/PhysRevB.43.229

[76] Alexander Shevchenko og Marco Mondelli. Landskabsforbindelse og dropout-stabilitet af SGD-løsninger til overparameteriserede neurale netværk. I International Conference on Machine Learning, side 8773–8784. PMLR, 2020. URL http:///proceedings.mlr.press/v119/shevchenko20a.html. arXiv:1912.10095.
arXiv: 1912.10095
http:///proceedings.mlr.press/v119/shevchenko20a.html

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

[78] Bin Shi, Simon S. Du, Michael I. Jordan og Weijie J. Su. Forståelse af accelerationsfænomenet via højopløselige differentialligninger. Matematisk programmering, side 1-70, 2021. 10.1007/s10107-021-01681-8. URL https:///doi.org/10.1007/s10107-021-01681-8. arXiv:1810.08907.
https://doi.org/10.1007/s10107-021-01681-8
arXiv: 1810.08907

[79] Weijie Su, Stephen Boyd og Emmanuel J. Candes. En differentialligning til modellering af Nesterovs accelererede gradientmetode: Teori og indsigt. 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. Optimering til dyb læring: teori og algoritmer, 2019. arXiv:1912.08957.
arXiv: 1912.08957

[81] Kunal Talwar. Beregningsmæssige adskillelser mellem sampling og optimering. Advances in Neural Information Processing Systems, 32: 15023–15033, 2019. URL http:///papers.nips.cc/paper/9639-computational-separations-between-sampling-and-optimization. arXiv:1911.02074.
arXiv: 1911.02074
http:///papers.nips.cc/paper/9639-computational-separations-between-sampling-and-optimization

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

[83] Cédric Villani. Hypocoercivity, bind 202 af 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 og Michael I. Jordan. Et variationsperspektiv på accelererede metoder til optimering. Proceedings of the National Academy of Sciences, 113 (47): E7351–E7358, 2016. 10.1073/pnas.1614734113. URL https:///doi.org/10.1073/pnas.1614734113. arXiv:1603.04245.
https:///doi.org/10.1073/pnas.1614734113
arXiv: 1603.04245

[85] Chenyi Zhang og Tongyang Li. Undslippe sadelpunkter med en simpel gradient-nedstigningsbaseret algoritme. In Advances in Neural Information Processing Systems, bind 34, 2021. URL https:///openreview.net/forum?id=lEf52hTHq0Q. arXiv:2111.14069.
arXiv: 2111.14069
https:///openreview.net/forum?id=lEf52hTHq0Q

[86] Chenyi Zhang, Jiaqi Leng og Tongyang Li. Kvantealgoritmer til at flygte fra saddelpunkter. Quantum, 5: 529, 2021a. 10.22331/q-2021-08-20-529. arXiv:2007.10253.
https://doi.org/10.22331/q-2021-08-20-529
arXiv: 2007.10253

[87] Kaining Zhang, Min-Hsiu Hsieh, Liu Liu og Dacheng Tao. Kvantealgoritme til at finde den negative krumningsretning i ikke-konveks optimering, 2019. arXiv:1909.07622.
arXiv: 1909.07622

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

Citeret af

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

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2023-06-02 12:31:17). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

Kunne ikke hente Crossref citeret af data under sidste forsøg 2023-06-02 12:31:15: Kunne ikke hente citerede data for 10.22331/q-2023-06-02-1030 fra Crossref. Dette er normalt, hvis DOI blev registreret for nylig.

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.

SEO Powered Content & PR Distribution. Bliv forstærket i dag.
PlatoAiStream. Web3 Data Intelligence. Viden forstærket. Adgang her.
Udmøntning af fremtiden med Adryenn Ashley. Adgang her.
Køb og sælg aktier i PRE-IPO-virksomheder med PREIPO®. Adgang her.
Kilde: https://quantum-journal.org/papers/q-2023-06-02-1030/

Tidsstempel: 2. Juni, 2023

Tidsstempel: Juli 7, 2022

Mod Quantum One-Time Memories fra statsløs hardware

Kildeklynge:

Quantum Journal

Kildeknude: 806211

Tidsstempel: April 8, 2021

Om Quantum Speedups til ikke-konveks optimering via Quantum Tunneling Walks

Genudgivet af Platon

Abstrakt

Populært resumé

► BibTeX-data

► Referencer

Citeret af

Mere fra Quantum Journal

Molecular Quantum Circuit Design: En grafbaseret tilgang

Adaptivt målefilter: effektiv strategi til optimal estimering af kvante Markov-kæder

Chiral superledning i den doterede Fermi-Hubbard-model med trekantet gitter i to dimensioner

Objektive baner i hybrid klassisk-kvantedynamik

State Preparation Boosters for tidlig fejltolerant kvanteberegning

Minimum trotterization formler for en tidsafhængig Hamiltonian

Strenge begrænsninger på probabilistisk konvertibilitet af kvantetilstande

Indkaldelse til redaktører 2023

Kvantemetoder til neurale netværk og anvendelse til medicinsk billedklassificering

Projiceret mindste kvadraters kvanteprocestomografi

Del-og-hersk-verifikationsmetode til støjende kvanteberegninger i mellemskala

Mod Quantum One-Time Memories fra statsløs hardware

Om os

Vertikal søgning & Ai

perron

Stay Connected

Konto