Про квантове прискорення для опуклої оптимізації за допомогою квантового тунелювання

Перевидано Платоном

читають: 0

Ічжоу Лю¹, Weijie J. Su², і Тонъян Лі^3,4

¹Факультет інженерної механіки, Університет Цінхуа, 100084 Пекін, Китай
²Відділ статистики та даних, Університет Пенсільванії
³Center on Frontiers of Computing Studies, Peking University, 100871 Beijing, China
⁴Школа інформатики, Пекінський університет, 100871 Пекін, Китай

Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на SciRate.

абстрактний

Класичні алгоритми часто неефективні для вирішення неопуклих задач оптимізації, де локальні мінімуми розділені високими бар’єрами. У цій статті ми досліджуємо можливі квантові прискорення для неопуклої оптимізації шляхом використання $глобального$ ефекту квантового тунелювання. Зокрема, ми представляємо квантовий алгоритм, який називається квантовим тунельним блуканням (QTW), і застосовуємо його до неопуклих задач, де локальні мінімуми є приблизно глобальними мінімумами. Ми показуємо, що QTW досягає квантового прискорення порівняно з класичними стохастичними градієнтними спусками (SGD), коли бар’єри між різними локальними мінімумами високі, але тонкі, а мінімуми плоскі. Грунтуючись на цьому спостереженні, ми будуємо особливий ландшафт подвійних ям, де класичні алгоритми не можуть ефективно вразити одну ціль, добре знаючи іншу, але QTW може, якщо задані належні початкові стани поблизу відомої ями. Нарешті, ми підтверджуємо наші висновки чисельними експериментами.

[Вбудоване вміст]

► Дані 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}quantum {S}peedups for {N}onconvex {O}ptimization via {Q}uantum {T}unneling {W}alks}, автор = {Liu, Yizhou and Su, Weijie J. and Li, Tongyang}, журнал = {{Quantum}}, issn = {2521-327X}, видавець = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, обсяг = {7}, сторінок = {1030} , місяць = червень, рік = {2023} }

► Список літератури

[1] Zeyuan Allen-Zhu та Yuanzhi Li. Neon2: Пошук локальних мінімумів через оракули першого порядку. У Advances in Neural Information Processing Systems, сторінки 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] Анімашрі Анандкумар, Ронг Ге, Даніель Хсу, Шам М. Какаде та Матус Телгарскі. Тензорні розкладання для вивчення моделей латентних змінних. Журнал дослідження машинного навчання, 15: 2773–2832, 2014. URL https:///jmlr.org/papers/volume15/anandkumar14b/. arXiv:1210.7559v4.
arXiv: 1210.7559v4
https:///jmlr.org/papers/volume15/anandkumar14b/

[3] Бен Ендрюс і Джулі Клаттербак. Доказ гіпотези про фундаментальну розрив. Журнал Американського математичного товариства, 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] Йоран ван Апелдорн і Андраш Гільєн. Покращення квантового розв’язування SDP за допомогою програм. У матеріалах 46-го Міжнародного колоквіуму з автоматів, мов і програмування, том 132 Leibniz International Proceedings in Informatics (LIPIcs), сторінки 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] Йоран ван Апелдорн, Андраш Гільєн, Сандер Гріблінг і Рональд де Вольф. Квантові розв'язувачі SDP: кращі верхні та нижні межі. У матеріалах 58-го щорічного симпозіуму з основ інформатики. IEEE, 2017. 10.1109/FOCS.2017.44. arXiv:1705.01843.
https:///doi.org/10.1109/FOCS.2017.44
arXiv: 1705.01843

[6] Йоран ван Апелдорн, Андраш Гільєн, Сандер Гріблінг і Рональд де Вольф. Опукла оптимізація за допомогою квантових оракулів. 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] Френк Аруте, Кунал Арья, Райан Беббуш, Дейв Бейкон, Джозеф С. Бардін, Рамі Барендс, Серджіо Бойшо, Майкл Бротон, Боб Б. Баклі, Девід А. Буелл, Брайан Беркетт, Ніколас Бушнелл, Ю Чен, Цзіцзюн Чен, Бенджамін Чіаро , Роберто Коллінз, Вільям Кортні, Шон Демура, Ендрю Дансуорт, Едвард Фархі, Остін Фаулер, Брукс Фоксен, Крейг Гідні, Марісса Джустина, Роб Графф, Стів Хабеггер, Метью П. Гарріган, Алан Хо, Сабріна Хонг, Трент Хуанг, Вільям Дж. Хаггінс, Лев Іоффе, Сергій В. Ісаков, Еван Джеффрі, Чжан Цзян, Коді Джонс, Двір Кафрі, Костянтин Кечеджі, Джуліан Келлі, Сеон Кім, Пол В. Клімов, Олександр Коротков, Федір Костріца, Девід Ландхуіс, Павло Лаптєв, Майк Ліндмарк, Ерік Лусеро, Оріон Мартін, Джон М. Мартініс, Джаррод Р. МакКлін, Метт МакЮен, Ентоні Мегрант, Сяо Мі, Масуд Мохсені, Войцех Мручкевич, Джош Мутус, Офер Нааман, Меттью Нілі, Чарльз Нілл, Хартмут Невен, Мерфі Южен Ніу, Томас Е. О'Браєн, Ерік Остбі, Андре Пєтухов, Гаральд Путтерман, Кріс Кінтана, Педрам Роушан, Ніколас К. Рубін, Деніел Санк, Кевін Дж. Сатцінгер, Вадим Смілянський, Дуг Стрейн, Кевін Дж. Сунг, Марко Салай , Тайлер Ю. Такешіта, Аміт Вайнсенчер, Теодор Вайт, Натан Вібе, З. Джеймі Яо, Пінг Є та Адам Залкман. Хартрі-Фока на квантовому комп’ютері з надпровідним кубітом. Наука, 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] Йосі Атіа та Шантанав Чакраборті. Покращено верхні межі для часу потрапляння квантових блукань. Physical Review A, 104: 032215, вересень 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] Карло Бальдассі та Ріккардо Зеккіна. Ефективність квантового проти класичного відпалу в неопуклих задачах навчання. Праці Національної академії наук, 115 (7): 1457–1462, січень 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] Чарльз Х. Беннетт, Ітан Бернштейн, Жиль Брассар і Умеш Вазірані. Сильні та слабкі сторони квантових обчислень. 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] Майкл Бетанкур, Майкл І. Джордан і Ашіа С. Вілсон. Про симплектичну оптимізацію, 2018. arXiv:1802.03653.
arXiv: 1802.03653

[12] Серхіо Бойхо та Роландо Д. Сомма. Необхідна умова квантово-адіабатичного наближення. 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] Фернандо Дж. С. Л. Брандао та Кріста Своре. Квантові прискорення для напіввизначеного програмування. У матеріалах 58-го щорічного симпозіуму з основ інформатики, сторінки 415–426, 2017 р. 10.1109/FOCS.2017.45. arXiv:1609.05537.
https:///doi.org/10.1109/FOCS.2017.45
arXiv: 1609.05537

[14] Фернандо Дж. С. Л. Брандао, Амір Калев, Тонг’ян Лі, Седрік Єн-Ю Лін, Кріста М. Своре та Сяоді Ву. Розв’язувачі Quantum SDP: великі прискорення, оптимальність і застосування для квантового навчання. У матеріалах 46-го Міжнародного колоквіуму з автоматів, мов і програмування, том 132 Leibniz International Proceedings in Informatics (LIPIcs), сторінки 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] Шуванік Чакрабарті, Ендрю М. Чайлдс, Тонг’ян Лі та Сяоді Ву. Квантові алгоритми та нижні межі опуклої оптимізації. 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] Шантанав Чакраборті, Кайл Лу та Джеремі Роланд. Як швидко змішуються квантові прогулянки? Physical Review Letters, 124: 050501, лютий 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] Пратік Чаудхарі та Стефано Соатто. Стохастичний градієнтний спуск виконує варіаційний висновок, збігається до граничних циклів для глибоких мереж. У 2018 році Семінар з теорії інформації та застосування (ITA), сторінки 1–10, 2018. 10.1109/ITA.2018.8503224. arXiv:1710.11029v2.
https:///doi.org/10.1109/ITA.2018.8503224
arXiv: 1710.11029v2

[18] Ендрю М. Чайлдс, Річард Клів, Енріко Деотто, Едвард Фархі, Сем Гутманн і Деніел А. Шпільман. Експоненціальне алгоритмічне прискорення квантовою прогулянкою. У матеріалах тридцять п’ятого щорічного симпозіуму ACM з теорії обчислень, STOC '03, сторінки 59–68, Нью-Йорк, Нью-Йорк, США, 2003. Асоціація обчислювальної техніки. 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] Ендрю М. Чайлдс, Джин-Пен Лю та Аарон Острандер. Високоточні квантові алгоритми для рівнянь у частинних похідних. Quantum, 5: 574, листопад 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] П’єр Комон, Ксав’є Лучані та Андре Л. Ф. Де Алмейда. Тензорні розкладання, чергування найменших квадратів та інші казки. Journal of Chemometrics, 23: 393–405, серпень 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] Педро КС Коста, Стівен Джордан і Аарон Острандер. Квантовий алгоритм для моделювання хвильового рівняння. Physical Review A, 99: 012323, січень 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] Крістофер Крісцієлло та Ніколя Бумаль. Від’ємна кривина перешкоджає прискоренню для геодезично опуклої оптимізації, навіть з точними оракулами першого порядку, 2021. arXiv:2111.13263.
arXiv: 2111.13263

[23] Елізабет Кроссон і Арам В. Харроу. Імітований квантовий відпал може бути експоненціально швидшим, ніж класичний імітований відпал. У 2016 році 57-й щорічний симпозіум IEEE з основ комп’ютерних наук (FOCS), сторінки 714–723. IEEE, жовтень 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] Муез Дімассі та Йоганнес Шьостранд. Спектральна асимптотика в напівкласичній межі. Серія лекцій Лондонського математичного товариства. Cambridge University Press, 1999. 10.1017/CBO9780511662195.
https:///doi.org/10.1017/CBO9780511662195

[25] Фелікс Дракслер, Камбіс Вешгіні, Манфред Зальмхофер і Фред Хампрехт. По суті, немає перешкод в енергетичному ландшафті нейронної мережі. У Міжнародній конференції з машинного навчання, сторінки 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] Руняо Дуань. Перегляд квантової адіабатичної теореми, 2020. arXiv:2003.03063v1.
arXiv: 2003.03063v1

[27] Джон Дучі, Елад Хазан і Йорам Сінгер. Адаптивні субградієнтні методи для онлайн-навчання та стохастичної оптимізації. 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 Vuletic, and Mikhail D. Lukin . Квантові фази речовини на 256-атомному програмованому квантовому симуляторі. 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] Цун Фанг, Кріс Цзюньчі Лі, Чжоучен Лін і Тонг Чжан. Павук: майже оптимальна неопукла оптимізація за допомогою стохастичної інтегрованої траєкторії диференціальної оцінки. У Advances in Neural Information Processing Systems, сторінки 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] Цун Фан, Чжоучен Лінь і Тун Чжан. Різкий аналіз неопуклої SGD, що виходить із сідлових точок. На конференції з теорії навчання, сторінки 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] Едвард Фархі, Джеффрі Голдстоун, Сем Гутманн, Джошуа Лапан, Ендрю Лундгрен і Даніель Преда. Алгоритм квантової адіабатичної еволюції, застосований до випадкових випадків NP-повної проблеми. Наука, 292 (5516): 472–475, квітень 2001 р. ISSN 1095-9203. 10.1126/наук.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 і JD Doll. Квантовий відпал: новий метод мінімізації багатовимірних функцій. Chemical Physics Letters, 219 (5-6): 343–348, березень 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] Може Франсуа. Симплектична схема стрибуни, 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] Алан Фріз, Марк Джерум і Раві Каннан. Вивчення лінійних перетворень. У матеріалах 37-ї конференції з основ інформатики, сторінки 359–368, 1996 р. 10.1109/SFCS.1996.548495.
https:///doi.org/10.1109/SFCS.1996.548495

[35] Тимур Гаріпов, Павло Ізмайлов, Дмитро Подопріхін, Дмитро Вєтров та Ендрю Гордон Вілсон. Поверхні втрат, підключення режимів і швидке ансамблювання DNN. У Advances in Neural Information Processing Systems, сторінки 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] Жун Ге і Тенью Ма. Про оптимізаційний ландшафт тензорних розкладів. Математичне програмування, сторінки 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] Жун Ге, Фуронг Хуан, Чі Цзінь і Ян Юань. Вихід із сідлових точок – онлайн-стохастичний градієнт для тензорного розкладання. У матеріалах 28-ї конференції з теорії навчання, том 40 Proceedings of Machine Learning Research, сторінки 797–842, 2015 р. URL-адреса http://proceedings.mlr.press/v40/Ge15. arXiv:1503.02101.
arXiv: 1503.02101
http:///proceedings.mlr.press/v40/Ge15

[38] Ронг Ге, Джейсон Д. Лі та Тенгю Ма. Завершення матриці не має хибного локального мінімуму. У Advances in Neural Information Processing Systems, сторінки 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] Мін Гун, Шию Ван, Чень Чжа, Мін-Чен Чен, Хе-Лян Хуан, Юлінь Ву, Цінлін Чжу, Ювей Чжао, Шаовей Лі, Шаоцзюнь Го, Хаорань Цянь, Янсен Є, Фушен Чен, Чонг Ін, Цзяле Юй, Даоцзінь Фан, Дачао Ву, Хун Су, Хуей Ден, Хао Жун, Кайлі Чжан, Сіруй Цао, Цзінь Лінь, Юй Сюй, Ліхуа Сунь, Ченг Гуо, На Лі, Футіан Лян, В. М. Бастідас, Кае Немото, В. Дж. Мунро, Йон-Хен Хо, Чао-Ян Лу, Чен-Жі Пен, Сяобо Чжу та Цзянь-Вей Пан. Quantum прогулянки на програмованому двовимірному 62-кубітному надпровідному процесорі. Наука, 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] Стівен К. Грей і Девід Е. Манолопулос. Симплектичні інтегратори, адаптовані до залежного від часу рівняння Шредінгера. Журнал хімічної фізики, 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] Бернард Хелффер. Напівкласичний аналіз для оператора Шредінгера та застосування. Конспект лекцій з математики. Springer, 1988. 10.1007/BFb0078115.
https:///doi.org/10.1007/BFb0078115

[42] Бернард Хельффер і Йоганнес Шьостранд. Кілька ям у напівкласичній межі I. Комунікації в часткових диференціальних рівняннях, 9 (4): 337–408, 1984. 10.1080/03605308408820335.
https: / / doi.org/ 10.1080 / 03605308408820335

[43] Бернард Хельффер і Йоганнес Шьостранд. Множинні ями в напівкласичному межі III – взаємодія через нерезонансні ями. 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] Зеп Хохрайтер. Проблема зникаючого градієнта під час навчання рекурентних нейронних мереж і розв’язків задач. Міжнародний журнал невизначеності, нечіткості та систем, заснованих на знаннях, 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] Аапо Гіварінен. Швидка ICA для шумових даних із використанням моментів Гауса. У 1999 році Міжнародний симпозіум IEEE зі схем і систем (ISCAS), том 5, сторінки 57–61, 1999. 10.1109/ISCAS.1999.777510.
https:///doi.org/10.1109/ISCAS.1999.777510

[46] Фредерік Еро, Майкл Хітрік і Йоганнес Шьостранд. Тунельний ефект і симетрії для операторів типу Крамерса–Фоккера–Планка. Журнал Інституту математики Жюссьє, 10 (3): 567–634, 2011. 10.1017/S1474748011000028.
https: / / doi.org/ 10.1017 / S1474748011000028

[47] Чі Джин, Ронг Ге, Праніт Нетрапаллі, Шам М. Какаде та Майкл І. Джордан. Як ефективно уникнути сідлових точок. У матеріалах 34-ї Міжнародної конференції з машинного навчання, том 70, сторінки 1724–1732, 2017 р. URL-адреса http://proceedings.mlr.press/v70/jin17a. arXiv:1703.00887.
arXiv: 1703.00887
http:///proceedings.mlr.press/v70/jin17a

[48] Чі Цзінь, Лідія Т. Лю, Жун Ге та Майкл І. Джордан. Про локальні мінімуми емпіричного ризику. У Досягнення в нейронних системах обробки інформації, том 31, сторінки 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] Чі Джин, Праніт Нетрапаллі, Ронг Ге, Шам М. Какаде та Майкл І. Джордан. Про неопуклу оптимізацію для машинного навчання: градієнти, стохастичність і сідлові точки. Журнал 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] Михайло Іванович Йордан. Динамічні, симплектичні та стохастичні перспективи оптимізації на основі градієнта. У матеріалах Міжнародного конгресу математиків: Ріо-де-Жанейро 2018, сторінки 523–549. World Scientific, 2018. URL https:///doi.org/10.1142/9789813272880_0022.
https:///doi.org/10.1142/9789813272880_0022

[51] Кендзі Кавагуті, Цзяоян Хуан і Леслі Пак Кейлблінг. Кожне локальне мінімальне значення є глобальним мінімальним значенням індукованої моделі в невипуклому машинному навчанні. Нейронні обчислення, 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] Дідерік П. Кінгма та Джиммі Ба. Адам: Метод стохастичної оптимізації. На 3-й Міжнародній конференції з питань навчання, 2015. URL https:///openreview.net/forum?id=8gmWwjFyLj. arXiv:1412.6980.
arXiv: 1412.6980
https:///openreview.net/forum?id=8gmWwjFyLj

[53] Олексій Китаєв і Вільям А. Вебб. Підготовка хвильової функції та повторна вибірка за допомогою квантового комп’ютера, 2008. arXiv:0801.0342.
arXiv: 0801.0342

[54] Боббі Кляйнберг, Юаньчжі Лі та Ян Юань. Альтернативний погляд: коли SGD виходить за межі локальних мінімумів? У Міжнародній конференції з машинного навчання, сторінки 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] Гай Корновський і Охад Шамір. Складність Oracle у негладкій неопуклій оптимізації. Досягнення в системах обробки нейронної інформації, 2021. URL https:///openreview.net/forum?id=aMZJBOiOOPg. arXiv:2104.06763v2.
arXiv: 2104.06763v2
https:///openreview.net/forum?id=aMZJBOiOOPg

[56] Рохіт Кудітіпуді, Сян Ван, Холден Лі, Ї Чжан, Чжіюань Лі, Вей Ху, Ронг Ге та Санджив Арора. Пояснення ландшафтного підключення недорогих рішень для багатошарових мереж. 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- багатошарові сітки. arXiv:1906.06247.
arXiv: 1906.06247
http://papers.nips.cc/paper/9602-explaining-landscape-connectivity-of-low-cost-solutions-for-multilayer-nets

[57] Гарольд Дж. Кушнер і Г. Джордж Інь. Стохастичне наближення та рекурсивні алгоритми та застосування, том 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] Керен Лі, Шицзе Вей, Пан Гао, Фейхао Чжан, Зенгронг Чжоу, Тао Сінь, Сяотін Ван, Патрік Ребентрост і Гуйлу Лонг. Оптимізація поліноміальної функції на квантовому процесорі. npj Квантова інформація, 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] Чжіюань Лі, Садхіка Малладі та Санджив Арора. Про достовірність моделювання СГД за допомогою стохастичних диференціальних рівнянь (СДУ). Досягнення нейронних систем обробки інформації, 2021b. URL-адреса https:///openreview.net/forum?id=goEdyJ_nVQI. arXiv:2102.12470.
arXiv: 2102.12470
https:///openreview.net/forum?id=goEdyJ_nVQI

[60] Гуан Хао Лоу та Натан Вібе. Гамільтоніанське моделювання у картині взаємодії, 2019. URL https:///arxiv.org/abs/1805.00675v2. arXiv:1805.00675v2.
arXiv: 1805.00675v2

[61] Цун Ма, Кайчжен Ван, Юецзі Чі та Юсінь Чен. Неявна регуляризація в невипуклій статистичній оцінці: градієнтний спуск сходиться лінійно для фазового пошуку та завершення матриці. У Міжнародній конференції з машинного навчання, сторінки 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] Тенгю Ма. Чому локальні методи вирішують неопуклі проблеми?, сторінки 465–485. Cambridge University Press, 2021. 10.1017/9781108637435.027. arXiv:2103.13462.
https: / / doi.org/ 10.1017 / 9781108637435.027
arXiv: 2103.13462

[63] Ї-Ань Ма, Юансі Чен, Чі Цзінь, Ніколас Фламмаріон і Майкл І. Джордан. Вибірка може бути швидшою за оптимізацію. 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] Пітер А. Маркович і Седрік Віллані. Про тенденцію до рівноваги для рівняння Фоккера-Планка: взаємодія між фізикою та функціональним аналізом. 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] Лоран Мішель. Про малі власні значення лапласіана Віттена. Чистий і прикладний аналіз, 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] Сіддхарт Мутукрішнан, Тамім Албаш і Деніел А. Лідар. Тунелювання та прискорення в квантовій оптимізації для переставно-симетричних проблем. Physical Review X, 6: 031010, липень 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] Квін Нгуєн. Про пов’язані набори підрівнів у глибинному навчанні. У Міжнародній конференції з машинного навчання, сторінки 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] Майкл А. Нільсен та Ісаак Л. Чуанг. Квантові обчислення та квантова інформація: видання до 10-ї річниці. Видавництво Кембриджського університету, 2010. 10.1017/CBO9780511976667.
https:///doi.org/10.1017/CBO9780511976667

[69] Григоріос А. Павліотіс. Стохастичні процеси та застосування: дифузійні процеси, рівняння Фоккера-Планка та Ланжевена, том 60. Springer, 2014. 10.1007/978-1-4939-1323-7.
https://doi.org/10.1007/978-1-4939-1323-7

[70] Цін Цюй, Юєсян Чжай, Сяо Лі, Юцянь Чжан і Чжіхуей Чжу. Аналіз оптимізаційних ландшафтів для навчання надповного представлення, 2019. arXiv:1912.02427.
arXiv: 1912.02427

[71] Джанлука Растеллі. Напівкласична формула для квантового тунелювання в асиметричних двоямних потенціалах. Physical Review A, 86: 012106, липень 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] Артур Г. Раттью, Юе Сун, П’єр Мінссен і Марко Пістоя. Ефективна підготовка нормальних розподілів у квантових регістрах. 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] Патрік Ребентрост, Марія Шульд, Леонард Воссніг, Франческо Петруччоне та Сет Ллойд. Квантовий градієнтний спуск і метод Ньютона для поліноміальної оптимізації з обмеженнями. 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] Бурак Шагіноглу та Роландо Д. Сомма. Гамільтоніанське моделювання в низькоенергетичному підпросторі. npj Квантова інформація, 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] Дж. М. Шмідта, А. Н. Клеланда та Джона Кларка. Резонансне тунелювання в малих джозефсонівських переходах зі зміщенням струму. Physical Review B, 43: 229–238, січень 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] Олександр Шевченко та Марко Монделлі. Ландшафтна зв’язність і стабільність відключення рішень SGD для надпараметризованих нейронних мереж. У Міжнародній конференції з машинного навчання, сторінки 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] Бін Ши, Вейцзе Дж. Су та Майкл І. Джордан. Про темпи навчання та оператори Шредінгера, 2020. arXiv:2004.06977.
arXiv: 2004.06977

[78] Бін Ши, Саймон С. Ду, Майкл І. Джордан і Вейдзі Дж. Су. Розуміння явища прискорення за допомогою диференціальних рівнянь високої роздільної здатності. Математичне програмування, сторінки 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] Вейдзі Су, Стівен Бойд та Еммануель Дж. Кандес. Диференціальне рівняння для моделювання прискореного градієнтного методу Нестерова: теорія та ідеї. Журнал досліджень машинного навчання, 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] Руоюй Сонце. Оптимізація для глибокого навчання: теорія та алгоритми, 2019. arXiv:1912.08957.
arXiv: 1912.08957

[81] Кунал Талвар. Обчислювальні поділу між вибіркою та оптимізацією. 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] Хао Тан, Сяо-Фен Лінь, Жень Фен, Цзін-Юань Чень, Цзюнь Гао, Ке Сун, Чао-Юе Ван, Пен-Чен Лай, Сяо-Юнь Сю, Яо Ван, Лу-Фен Цяо, Ай-Лінь Ян, і Сіань-Мінь Цзінь. Експериментальна двовимірна квантова блукання на фотонному чіпі. Наукові досягнення, 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] Седрік Віллані. Гіпокоерцітивність, том 202 Мемуарів Американського математичного товариства. Американське математичне товариство, 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] Андре Вібісоно, Ашіа К. Вілсон і Майкл І. Джордан. Варіаційний погляд на прискорені методи оптимізації. Праці Національної академії наук, 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] Ченьі Чжан і Тун'ян Лі. Уникайте сідлових точок за допомогою простого алгоритму на основі градієнтного спуску. У «Досягнення в нейронних системах обробки інформації», том 34, 2021. URL-адреса https://openreview.net/forum?id=lEf52hTHq0Q. arXiv:2111.14069.
arXiv: 2111.14069
https:///openreview.net/forum?id=lEf52hTHq0Q

[86] Ченьі Чжан, Цзяці Ленг і Тунян Лі. Квантові алгоритми виходу із сідлових точок. 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] Каінін Чжан, Мін-Сю Сє, Лю Лю та Дачен Тао. Квантовий алгоритм для знаходження негативного напрямку кривини в неопуклій оптимізації, 2019. arXiv:1909.07622.
arXiv: 1909.07622

[88] Юцянь Чжан, Цин Цюй і Джон Райт. Від симетрії до геометрії: трактовані неопуклі проблеми, 2021b. arXiv:2007.06753.
arXiv: 2007.06753

Цитується

[1] Weiyuan Gong, Chenyi Zhang і Tongyang Li, «Надійність квантових алгоритмів для неопуклої оптимізації», arXiv: 2212.02548, (2022).

Вищезазначені цитати від SAO / NASA ADS (останнє оновлення успішно 2023-06-02 12:31:17). Список може бути неповним, оскільки не всі видавці надають відповідні та повні дані про цитування.

Не вдалося отримати Перехресне посилання, наведене за даними під час останньої спроби 2023-06-02 12:31:15: Не вдалося отримати цитовані дані для 10.22331/q-2023-06-02-1030 з Crossref. Це нормально, якщо DOI був зареєстрований нещодавно.

Ця стаття опублікована в Quantum під Creative Commons Attribution 4.0 International (CC на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.

Розповсюдження контенту та PR на основі SEO. Отримайте посилення сьогодні.
PlatoAiStream. Web3 Data Intelligence. Розширення знань. Доступ тут.
Карбування майбутнього з Адріенн Ешлі. Доступ тут.
Купуйте та продавайте акції компаній, які вийшли на IPO, за допомогою PREIPO®. Доступ тут.
джерело: https://quantum-journal.org/papers/q-2023-06-02-1030/

Часова мітка: 2 Червня, 2023.

Часова мітка: Липень 7, 2022

До квантових одноразових спогадів від апаратного забезпечення без громадянства

Кластер джерел:

Квантовий журнал

Вихідний вузол: 806211

Часова мітка: Квітень 8, 2021

Про квантове прискорення для неопуклої оптимізації через квантові тунельні маршрути

Перевидано Платоном

абстрактний

Популярне резюме

► Дані BibTeX

► Список літератури

Цитується

Більше від Квантовий журнал

Молекулярний квантовий дизайн схеми: підхід на основі графів

Адаптивний вимірювальний фільтр: ефективна стратегія для оптимальної оцінки квантових ланцюгів Маркова

Кіральна надпровідність у легованій моделі Фермі-Хаббарда з трикутною решіткою у двох вимірах

Об'єктивні траєкторії в гібридній класично-квантовій динаміці

Прискорювачі підготовки стану для ранніх відмовостійких квантових обчислень

Мінімальні формули Троттеризації для гамільтоніана, що залежить від часу

Жорсткі обмеження ймовірнісної конвертованості квантових станів

Виклик до редакції 2023

Квантові методи для нейронних мереж і застосування до класифікації медичних зображень

Прогнозована квантова томографія найменших квадратів

Метод перевірки «розділяй і володарюй» для галасливих квантових обчислень середнього масштабу

До квантових одноразових спогадів від апаратного забезпечення без громадянства

Про нас

Вертикальний пошук & Ai

платформа

Залишайтеся на зв'язку

рахунки