О квантовом ускорении для невыпуклой оптимизации с помощью обходов квантового туннелирования

О квантовом ускорении для невыпуклой оптимизации с помощью обходов квантового туннелирования

Отметка времени: 2 июня 2023 г., 8:23
Исходный узел: 2694596

Ичжоу Лю1, Вейцзе Дж. Су2, и Тонгян Ли3,4

1Кафедра инженерной механики, Университет Цинхуа, 100084 Пекин, Китай
2Департамент статистики и науки о данных Пенсильванского университета
3Центр передовых компьютерных исследований, Пекинский университет, 100871 Пекин, Китай
4Школа компьютерных наук Пекинского университета, 100871 Пекин, Китай

Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.

Абстрактные

Классические алгоритмы часто неэффективны для решения задач невыпуклой оптимизации, где локальные минимумы разделены высокими барьерами. В этой статье мы исследуем возможные квантовые ускорения для невыпуклой оптимизации за счет использования $глобального$ эффекта квантового туннелирования. В частности, мы вводим квантовый алгоритм, называемый квантовым туннельным блужданием (QTW), и применяем его к невыпуклым задачам, где локальные минимумы приблизительно совпадают с глобальными минимумами. Мы показываем, что QTW достигает квантового ускорения по сравнению с классическими стохастическими градиентными спусками (SGD), когда барьеры между различными локальными минимумами высокие, но тонкие, а минимумы плоские. Основываясь на этом наблюдении, мы строим специфический ландшафт с двойной лункой, где классические алгоритмы не могут эффективно поразить одну цель, хорошо зная другую, но QTW может, если заданы надлежащие начальные состояния вблизи известной скважины. Наконец, мы подтверждаем наши выводы численными экспериментами.

[Встраиваемое содержимое]

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

Классические алгоритмы часто неэффективны для решения задач невыпуклой оптимизации, где локальные минимумы разделены высокими барьерами. В этой статье мы исследуем возможные квантовые ускорения для невыпуклой оптимизации за счет использования глобального эффекта квантового туннелирования. В частности, мы вводим квантовый алгоритм, называемый квантовым туннельным блужданием (QTW), и применяем его к невыпуклым задачам, где локальные минимумы приблизительно совпадают с глобальными минимумами. Мы показываем, что QTW достигает квантового ускорения по сравнению с классическими стохастическими градиентными спусками (SGD), когда барьеры между различными локальными минимумами высокие, но тонкие, а минимумы плоские. Основываясь на этом наблюдении, мы строим специфический ландшафт с двойной лункой, где классические алгоритмы не могут эффективно поразить одну цель, хорошо зная другую, но QTW может, если заданы надлежащие начальные состояния вблизи известной скважины. Наконец, мы подтверждаем наши выводы численными экспериментами.

► Данные BibTeX

► Рекомендации

[1] Зеюань Аллен-Чжу и Юаньчжи Ли. 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. пдф. архив: 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/​. архив: 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. архив: 1006.1686.
Arxiv: 1006.1686
Http: / / www.jstor.org/ стабильный / 23072145

[4] Йоран ван Апелдорн и Андраш Гильен. Улучшения в квантовом SDP-решении с приложениями. В материалах 46-го Международного коллоквиума по автоматам, языкам и программированию, том 132 Международного журнала Лейбница по информатике (LIPIcs), страницы 99: 1–99: 15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. 10.4230/LIPIcs.ICALP.2019.99. архив: 1804.05058.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.99
Arxiv: 1804.05058

[5] Йоран ван Апелдорн, Андраш Гильен, Сандер Гриблинг и Рональд де Вольф. Квантовые SDP-решатели: лучшие верхние и нижние границы. В материалах 58-го ежегодного симпозиума по основам информатики. IEEE, 2017. 10.1109/​FOCS.2017.44. архив: 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. архив: 1809.00643.
https:/​/​doi.org/​10.22331/​q-2020-01-13-220
Arxiv: 1809.00643

[7] Фрэнк Аруте, Кунал Арья, Райан Бэббуш, Дэйв Бэкон, Джозеф С. Бардин, Рами Барендс, Серхио Бойшо, Майкл Бротон, Боб Б. Бакли, Дэвид А. Бьюэлл, Брайан Беркетт, Николас Бушнелл, Ю Чен, Зиджун Чен, Бенджамин Кьяро , Роберто Коллинз, Уильям Кортни, Шон Демура, Эндрю Дансуорт, Эдвард Фархи, Остин Фаулер, Брукс Фоксен, Крэйг Гидни, Марисса Джустина, Роб Графф, Стив Хабеггер, Мэтью П. Харриган, Алан Хо, Сабрина Хонг, Трент Хуанг, Уильям Дж. Хаггинс, Лев Иоффе, Сергей В. Исаков, Эван Джеффри, Чжан Цзян, Коди Джонс, Двир Кафри, Константин Кечеджи, Джулиан Келли, Сеон Ким, Павел В. Климов, Александр Коротков, Федор Кострица, Дэвид Ландхус, Павел Лаптев, Майк Линдмарк, Эрик Лусеро, Орион Мартин, Джон М. Мартинис, Джаррод Р. МакКлин, Мэтт МакЮэн, Энтони Мегрант, Сяо Ми, Масуд Мохсени, Войцех Мручкевич, Джош Мутус, Офер Нааман, Мэтью Нили, Чарльз Нил, Хартмут Невен, Мерфи Юэжен Ниу, Томас Э. О'Брайен, Эрик Остби, Андре Петухов, Харальд Путтерман, Крис Кинтана, Педрам Роушан, Николас С. Рубин, Дэниел Санк, Кевин Дж. Сатцингер, Вадим Смелянский, Даг Стрейн, Кевин Дж. Санг, Марко Салай , Тайлер Ю. Такешита, Амит Вайнсенчер, Теодор Уайт, Натан Виб, З. Джейми Яо, Пинг Йе и Адам Зальцман. Хартри-Фок о квантовом компьютере со сверхпроводящими кубитами. Science, 369 (6507): 1084–1089, 2020. 10.1126/​science.abb9811. URL https://​/​science.sciencemag.org/​content/​369/​6507/​1084.abstract. архив: 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/​физрева.104.032215. URL http://​/​dx.doi.org/​10.1103/​PhysRevA.104.032215. архив: 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. архив: 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: квант-ф/​9701001.
https: / / doi.org/ 10.1137 / S0097539796300933
Arxiv: колич-фот / 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. архив: 0911.1362.
https: / / doi.org/ 10.1103 / PhysRevA.81.032308
Arxiv: 0911.1362

[13] Фернандо ГСЛ Брандао и Криста Своре. Квантовые ускорения для полуопределенного программирования. В материалах 58-го ежегодного симпозиума по основам компьютерных наук, стр. 415–426, 2017 г. 10.1109/​FOCS.2017.45. архив: 1609.05537.
https: / / doi.org/ 10.1109 / FOCS.2017.45
Arxiv: 1609.05537

[14] Фернандо ГСЛ Брандао, Амир Калев, Тонъян Ли, Седрик Йен-Ю Линь, Криста М. Своре и Сяоди Ву. Квантовые решатели SDP: значительное ускорение, оптимальность и приложения для квантового обучения. В материалах 46-го Международного коллоквиума по автоматам, языкам и программированию, том 132 Международного журнала Лейбница по информатике (LIPIcs), страницы 27: 1–27: 14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. 10.4230/​LIPIcs.ICALP.2019.27. архив: 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. архив: 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. архив: 2001.06305v1.
https: / / doi.org/ 10.1103 / PhysRevLett.124.050501
Arxiv: 2001.06305v1

[17] Пратик Чаудхари и Стефано Соатто. Стохастический градиентный спуск выполняет вариационный вывод, сходится к предельным циклам для глубоких сетей. В 2018 г. Семинар по теории и приложениям информации (ITA), страницы 1–10, 2018 г. 10.1109/​ITA.2018.8503224. архив: 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. архив: 2002.07868.
https:/​/​doi.org/​10.22331/​q-2021-11-10-574
Arxiv: 2002.07868

[20] Пьер Комон, Ксавьер Лучани и Андре Л. Ф. Де Алмейда. Тензорные разложения, чередование наименьших квадратов и другие сказки. Журнал 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/ гал-00410057

[21] Педро К.С. Коста, Стивен Джордан и Аарон Острандер. Квантовый алгоритм моделирования волнового уравнения. Physical Review A, 99: 012323, январь 2019 г. 10.1103/​PhysRevA.99.012323. URL https://​/​link.aps.org/​doi/​10.1103/​PhysRevA.99.012323. архив: 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. архив: 1601.03030.
https: / / doi.org/ 10.1109 / focs.2016.81
Arxiv: 1601.03030

[24] Моуэз Димасси и Йоханнес Шёстранд. Спектральная асимптотика в квазиклассическом пределе. Серия лекций Лондонского математического общества. Издательство Кембриджского университета, 1999. 10.1017/CBO9780511662195.
https: / / doi.org/ 10.1017 / CBO9780511662195

[25] Феликс Дракслер, Камбис Вешгини, Манфред Зальмхофер и Фред Хампрехт. Практически нет барьеров в энергетическом ландшафте нейронной сети. На Международной конференции по машинному обучению, страницы 1309–1318. PMLR, 2018. URL http://​/​proceedings.mlr.press/​v80/​draxler18a.html. архив: 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] Сепер Эбади, Тут Т. Ван, Гарри Левин, Александр Кислинг, Джулия Семегини, Ахмед Омран, Долев Блувштейн, Рейн Самайдар, Ханнес Пихлер, Вен Вэй Хо, Сунвон Чой, Субир Сачдев, Маркус Грейнер, Владан Вулетич и Михаил Д. Лукин . Квантовые фазы вещества на 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/ статьи / s41586-021-03582-4

[29] Конг Фан, Крис Джунчи Ли, Чжоучэнь Линь и Тонг Чжан. Паук: почти оптимальная невыпуклая оптимизация с помощью стохастической дифференциальной оценки, интегрированной по путям. В Достижениях в области нейронных систем обработки информации, страницы 689–699, 2018 г. URL-адрес https://​/​dl.acm.org/​doi/​abs/​10.5555/​3326943.3327007. архив: 1807.01695.
Arxiv: 1807.01695
https: / / dl.acm.org/ дои / ABS / 10.5555 / 3326943.3327007

[30] Конг Фан, Чжоучэнь Линь и Тонг Чжан. Точный анализ невыпуклого SGD, выходящего из седловых точек. В конференции по теории обучения, стр. 1192–1234, 2019 г. URL-адрес http://​/​proceedings.mlr.press/​v99/​fang19a.html. архив: 1902.00247.
Arxiv: 1902.00247
http://​/​proceedings.mlr.press/​v99/​fang19a.html

[31] Эдвард Фархи, Джеффри Голдстоун, Сэм Гутманн, Джошуа Лапан, Эндрю Лундгрен и Дэниел Преда. Алгоритм квантовой адиабатической эволюции, примененный к случайным случаям NP-полной задачи. Science, 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: колич-фот / 0104129

[32] А. Б. Финнила, М. А. Гомес, К. Себеник, К. Стенсон и Дж. Д. Долл. Квантовый отжиг: новый метод минимизации многомерных функций. Письма по химической физике, 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-симплектическая-чехарда-схема

[34] Алан Фриз, Марк Джеррум и Рави Каннан. Изучение линейных преобразований. В материалах 37-й конференции по основам компьютерных наук, стр. 359–368, 1996 г. 10.1109/​SFCS.1996.548495.
https: / / doi.org/ 10.1109 / SFCS.1996.548495

[35] Тимур Гарипов, Павел Измайлов, Дмитрий Подоприхин, Дмитрий Ветров и Эндрю Гордон Уилсон. Поверхности потерь, подключение мод и быстрая сборка DNN. В Достижениях в области нейронных систем обработки информации, страницы 8803–8812, 2018 г. URL-адрес https://​/​dl.acm.org/​doi/​abs/​10.5555/​3327546.3327556. архив: 1802.10026.
Arxiv: 1802.10026
https: / / dl.acm.org/ дои / ABS / 10.5555 / 3327546.3327556

[36] Ронг Гэ и Тэньюй Ма. Об оптимизационном ландшафте тензорных разложений. Математическое программирование, страницы 1–47, 2020. ISSN 1436-4646. 10.1007/​s10107-020-01579-х. URL https://​/​doi.org/​10.1007/​s10107-020-01579-x. архив: 1706.05598v1.
HTTPS: / / doi.org/ 10.1007 / s10107-020-01579-х
Arxiv: 1706.05598v1

[37] Жун Гэ, Фужун Хуан, Чи Цзинь и Ян Юань. Выход из седловых точек — онлайн стохастический градиент для тензорной декомпозиции. В материалах 28-й конференции по теории обучения, том 40 журнала Proceedings of Machine Learning Research, страницы 797–842, 2015 г. URL http://​/​proceedings.mlr.press/​v40/​Ge15. архив: 1503.02101.
Arxiv: 1503.02101
http://​/​proceedings.mlr.press/​v40/​Ge15

[38] Ронг Гэ, Джейсон Д. Ли и Тэнью Ма. Пополнение матрицы не имеет ложного локального минимума. В Достижениях в области нейронных систем обработки информации, страницы 2981–2989, 2016. URL-адрес https://​/​dl.acm.org/​doi/​abs/​10.5555/​3157382.3157431. архив: 1605.07272.
Arxiv: 1605.07272
https: / / dl.acm.org/ дои / ABS / 10.5555 / 3157382.3157431

[39] Мин Гонг, Шию Ван, Чэнь Чжа, Мин-Чэн Чен, Хе-Лян Хуан, Юлинь Ву, Цинлин Чжу, Ювэй Чжао, Шаовэй Ли, Шаоцзюнь Го, Хаоран Цянь, Янсен Е, Фушэн Чен, Чонг Ин, Цзяле Юй, Даоцзинь Фан, Дачао Ву, Хун Су, Хуэй Дэн, Хао Жун, Кайли Чжан, Сируи Цао, Цзинь Линь, Ю Сюй, Лихуа Сунь, Ченг Го, На Ли, Футянь Лян, ВМ Бастидас, Кае Немото, В. Дж. Мунро, Юн-Хэн Хуо, Чао-Ян Лу, Ченг-Чжи Пэн, Сяобо Чжу и Цзянь-Вэй Пан. Квантовые прогулки на программируемом двумерном 62-кубитном сверхпроводящем процессоре. Science, 372 (6545): 948–952, 2021. 10.1126/​science.abg7812. URL https://​/​science.sciencemag.org/​content/​372/​6545/​948.abstract. архив: 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. архив: 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. архив: 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. архив: 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. архив: 1904.03673v3.
https://​/​doi.org/​10.1162/​neco_a_01234
Arxiv: 1904.03673v3

[52] Дидерик П. Кингма и Джимми Ба. Адам: Метод стохастической оптимизации. На 3-й Международной конференции по представительствам в обучении, 2015 г. URL-адрес https://​/​openreview.net/​forum?id=8gmWwjFyLj. архив: 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. архив: 1802.06175.
Arxiv: 1802.06175
http://​/​proceedings.mlr.press/​v80/​kleinberg18a.html

[55] Гай Корновски и Охад Шамир. Сложность Oracle в негладкой невыпуклой оптимизации. In Advances in Neural Information Processing Systems, 2021. URL https://​/​openreview.net/​forum?id=aMZJBOiOOPg. архив: 2104.06763v2.
Arxiv: 2104.06763v2
https://​/​openreview.net/​forum?id=aMZJBOiOOPg

[56] Рохит Кудитипуди, Сян Ван, Холден Ли, Йи Чжан, Чжиюань Ли, Вэй Ху, Ронг Ге и Санджив Арора. Объяснение ландшафтного подключения недорогих решений для многослойных сетей. Достижения в системах обработки нейронной информации, 32: 14601–14610, 2019. URL http://​/​papers.nips.cc/​paper/​9602-explaining-landscape-connectivity-of-low-cost-solutions-for- многослойные сети. архив: 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 Quantum Information, 7 (1): 1–7, 2021a. 10.1038/​s41534-020-00351-5. архив: 1804.05231.
https:/​/​doi.org/​10.1038/​s41534-020-00351-5
Arxiv: 1804.05231

[59] Чжиюань Ли, Садхика Маллади и Санджив Арора. Об обоснованности моделирования СГД стохастическими дифференциальными уравнениями (СДУ). Достижения в области систем обработки нейронной информации, 2021b. URL https://​/​openreview.net/​forum?id=goEdyJ_nVQI. архив: 2102.12470.
Arxiv: 2102.12470
https://​/​openreview.net/​forum?id=goEdyJ_nVQI

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

[61] Конг Ма, Кайчжэн Ван, Юэцзе Чи и Юсинь Чен. Неявная регуляризация в невыпуклой статистической оценке: градиентный спуск линейно сходится для восстановления фазы и завершения матрицы. На Международной конференции по машинному обучению, страницы 3345–3354. PMLR, 2018. URL http://​/​proceedings.mlr.press/​v80/​ma18c.html. архив: 1711.10467.
Arxiv: 1711.10467
http://​/​proceedings.mlr.press/​v80/​ma18c.html

[62] Тенгю Ма. Почему локальные методы решают невыпуклые задачи?, стр. 465–485. Издательство Кембриджского университета, 2021. 10.1017/​9781108637435.027. архив: 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. архив: 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. архив: 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. архив: 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. архив: 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/​. архив: 2009.06601.
https:/​/​doi.org/​10.22331/​q-2021-12-23-609
Arxiv: 2009.06601
https: / / quantum-journal.org/ бумаги / д-2021-12-23-609 /

[73] Патрик Ребентрост, Мария Шульд, Леонард Воссниг, Франческо Петруччионе и Сет Ллойд. Квантовый градиентный спуск и метод Ньютона полиномиальной оптимизации с ограничениями. New Journal of Physics, 21 (7): 073023, 2019. 10.1088/​1367-2630/​ab2a9e. архив: 1612.01789.
https:/​/​doi.org/​10.1088/​1367-2630/​ab2a9e
Arxiv: 1612.01789

[74] Бурак Шахиноглу и Роландо Д. Сомма. Гамильтоново моделирование в низкоэнергетическом подпространстве. npj Quantum Information, 7 (1): 1–5, 2021. 10.1038/​s41534-021-00451-w. URL https://​/​www.nature.com/​articles/​s41534-021-00451-w. архив: 2006.02660.
HTTPS: / / doi.org/ 10.1038 / s41534-021-00451-ш
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. ПМЛР, 2020. URL http://​/​proceedings.mlr.press/​v119/​shevchenko20a.html. архив: 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. архив: 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. архив: 1503.01243.
https: / / doi.org/ 10.5555 / 2946645.3053435
Arxiv: 1503.01243

[80] Руою Сун. Оптимизация для глубокого обучения: теория и алгоритмы, 2019. arXiv:1912.08957.
Arxiv: 1912.08957

[81] Кунал Талвар. Вычислительное разделение между выборкой и оптимизацией. Достижения в системах обработки нейронной информации, 32: 15023–15033, 2019. URL http://​/​papers.nips.cc/​paper/​9639-computational-separations-between-sampling-and-optimization. архив: 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. архив: 1704.08242.
https: / / doi.org/ 10.1126 / sciadv.aat3174
Arxiv: 1704.08242

[83] Седрик Виллани. Гипокоэрцитивность, том 202 Мемуаров Американского математического общества. Американское математическое общество, 2009. 10.1090/​S0065-9266-09-00567-5. arXiv:математика/​0609050.
https:/​/​doi.org/​10.1090/​S0065-9266-09-00567-5
Arxiv: математика / 0609050

[84] Андре Вибисоно, Ашиа С. Уилсон и Майкл И. Джордан. Вариационный взгляд на ускоренные методы оптимизации. Proceedings of the National Academy of Sciences, 113 (47): E7351–E7358, 2016. 10.1073/​pnas.1614734113. URL https://​/​doi.org/​10.1073/​pnas.1614734113. архив: 1603.04245.
https: / / doi.org/ 10.1073 / pnas.1614734113
Arxiv: 1603.04245

[85] Чэньи Чжан и Тонъян Ли. Избегайте седловых точек с помощью простого алгоритма, основанного на градиентном спуске. В Достижениях в области систем обработки нейронной информации, том 34, 2021 г. URL-адрес https://​/​openreview.net/​forum?id=lEf52hTHq0Q. архив: 2111.14069.
Arxiv: 2111.14069
https://​/​openreview.net/​forum?id=lEf52hTHq0Q

[86] Чэньи Чжан, Цзяци Ленг и Тунъян Ли. Квантовые алгоритмы выхода из седловых точек. Квант, 5: 529, 2021а. 10.22331/​q-2021-08-20-529. архив: 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. архив: 2007.06753.
Arxiv: 2007.06753

Цитируется

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

Приведенные цитаты из САО / НАСА 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 BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.

Отметка времени:

Больше от Квантовый журнал