Соображения о задержке для стохастических оптимизаторов в вариационных квантовых алгоритмах

Соображения о задержке для стохастических оптимизаторов в вариационных квантовых алгоритмах

Исходный узел: 2015562

Мэтт Меникелли1, Юнсу Ха2и Мэтью Оттен3

1Отделение математики и информатики, Аргоннская национальная лаборатория, 9700 S. Cass Ave., Lemont, IL 60439
2Эдвард П. Фиттс, факультет промышленного и системного проектирования, Университет штата Северная Каролина, 915 Partners Way, Raleigh, NC 27601
3HRL Laboratories, LLC, 3011 Malibu Canyon Road, Малибу, Калифорния 90265

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

Абстрактные

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

Вариационные квантовые алгоритмы являются многообещающими кандидатами для решения практических задач квантовых компьютеров ближайшего времени. Однако процесс оптимизации этих алгоритмов может быть дорогостоящим в вычислительном отношении из-за двух потребностей: 1) выполнять повторные измерения (выстрелы) на квантовом компьютере и 2) настраивать параметры квантовой схемы. Здесь мы предлагаем новый алгоритм стохастической оптимизации под названием SHOALS (адаптивный поиск линии SHOt), который разработан в предположении, что время, затрачиваемое на выполнение оптимизационных выстрелов, доминирует над временем, затрачиваемым на оптимизацию, выполняющую настройки схемы. Мы демонстрируем, что SHOALS превосходит другие алгоритмы стохастической оптимизации в этой настройке. Наоборот, когда время выстрела сравнимо со временем переключения цепи, алгоритмы стохастического градиентного спуска оказываются более эффективными. Рассматривая компромиссы между временем выстрела, временем переключения схемы и эффективностью алгоритма оптимизации, мы показываем, что общее время выполнения вариационных квантовых алгоритмов может быть значительно сокращено.

► Данные BibTeX

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

[1] Бенджамин П. Ланьон, Джеймс Д. Уитфилд, Джефф Г. Джиллетт, Майкл Э. Гоггин, Марсело П. Алмейда, Иван Кассал, Джейкоб Д. Биамонте, Масуд Мохсени, Бен Дж. Пауэлл, Марко Барбьери и др. «К квантовой химии на квантовом компьютере». Химия природы 2, 106–111 (2010).
https: / / doi.org/ 10.1038 / nchem.483

[2] Ян Клоэт, Мэтью Р. Дитрих, Джон Аррингтон, Алексей Базавов, Майкл Бишоф, Адам Фриз, Алексей В. Горшков, Анна Грасселлино, Каутар Хафиди, Зубин Джейкоб и др. «Возможности ядерной физики и квантовой информатики» (2019). архив: 1903.05453.
Arxiv: 1903.05453

[3] Адам Смит, М.С. Ким, Фрэнк Поллманн и Йоханнес Кнолле. «Моделирование квантовой динамики многих тел на современном цифровом квантовом компьютере». npj Квантовая информация 5, 1–13 (2019).
https:/​/​doi.org/​10.1038/​s41534-019-0217-0

[4] Бенджамин Нахман, Давиде Провасоли, Вибе А де Йонг и Кристиан В. Бауэр. «Квантовый алгоритм для моделирования физики высоких энергий». Письма о физическом обзоре 126, 062001 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.062001

[5] Джейкоб Биамонте, Питер Виттек, Никола Панкотти, Патрик Ребентрост, Натан Виб и Сет Ллойд. «Квантовое машинное обучение». Природа 549, 195–202 (2017).
https: / / doi.org/ 10.1038 / nature23474

[6] Роман Орус, Самуэль Мюгель и Энрике Лизасо. «Квантовые вычисления для финансов: обзор и перспективы». Обзоры по физике 4, 100028 (2019).
https: / / doi.org/ 10.1016 / j.revip.2019.100028

[7] Джон Прескилл. «Квантовые вычисления в эпоху NISQ и позже». Квант 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[8] У. Дорнер, Р. Демкович-Добжански, Б. Дж. Смит, Дж. С. Лундин, В. Василевски, К. Банашек и И. А. Уолмсли. «Оптимальная квантовая фазовая оценка». Письма о физическом обзоре 102, 040403 (2009 г.).
https: / / doi.org/ 10.1103 / PhysRevLett.102.040403

[9] Джон Прескилл. «Отказоустойчивые квантовые вычисления». Введение в квантовые вычисления и информацию. Страницы 213–269. Мировой научный (1998).

[10] Марко Сересо, Эндрю Аррасмит, Райан Бэббуш, Саймон С. Бенджамин, Сугуру Эндо, Кейсуке Фуджи, Джаррод Р. МакКлин, Косуке Митараи, Сяо Юань, Лукаш Чинчио и др. «Вариационные квантовые алгоритмы». Nature Reviews Physics, страницы 1–20 (2021).
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[11] Питер Дж. Дж. О'Мэлли, Райан Бэббуш, Ян Д. Кивличан, Джонатан Ромеро, Джаррод Р. МакКлин, Рами Барендс, Джулиан Келли, Педрам Рушан, Эндрю Трантер, Нэн Дин и др. «Масштабируемое квантовое моделирование молекулярных энергий». Физический обзор X 6, 031007 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.031007

[12] Сяо Юань, Сугуру Эндо, Ци Чжао, Ин Ли и Саймон С. Бенджамин. «Теория вариационного квантового моделирования». Квант 3, 191 (2019).
https:/​/​doi.org/​10.22331/​q-2019-10-07-191

[13] Мэтью Оттен, Кристиан Л. Кортес и Стивен К. Грей. «Помехоустойчивая квантовая динамика с использованием сохраняющих симметрию анзацев» (2019). архив: 1910.06284.
Arxiv: 1910.06284

[14] Абхинав Кандала, Антонио Меццакапо, Кристан Темме, Майка Такита, Маркус Бринк, Джерри М. Чоу и Джей М. Гамбетта. «Аппаратно-эффективный вариационный квантовый решатель для малых молекул и квантовых магнитов». Природа 549, 242–246 (2017).
https: / / doi.org/ 10.1038 / nature23879

[15] Косуке Митараи, Макото Негоро, Масахиро Китагава и Кейсуке Фуджи. «Квантовое схемное обучение». Физический обзор A 98, 032309 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.032309

[16] Мэтью Оттен, Имен Р. Гумири, Бенджамин В. Прист, Джордж Ф. Чаплайн и Майкл Д. Шнайдер. «Квантовое машинное обучение с использованием гауссовских процессов с высокопроизводительными квантовыми ядрами» (2020). архив: 2004.11280.
Arxiv: 2004.11280

[17] Роберт М. Пэрриш, Эдвард Г. Хохенштейн, Питер Л. МакМахон и Тодд Дж. Мартинес. «Квантовый расчет электронных переходов с использованием вариационного квантового собственного решателя». Письма о физическом обзоре 122, 230401 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.230401

[18] Кевин Дж. Сун, Цзяхао Яо, Мэтью П. Харриган, Николас С. Рубин, Чжан Цзян, Лин Лин, Райан Баббуш и Джаррод Р. МакКлин. «Использование моделей для улучшения оптимизаторов для вариационных квантовых алгоритмов». Квантовая наука и технологии 5, 044008 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb6d9

[19] Джей Гамбетта, В. А. Брафф, А. Валлрафф, С. М. Гирвин и Р. Дж. Шолкопф. «Протоколы для оптимального считывания кубитов с использованием непрерывного квантового измерения без разрушения». Физический обзор A 76, 012325 (2007).
https: / / doi.org/ 10.1103 / PhysRevA.76.012325

[20] Сьюзан М. Кларк, Дэниел Лобсер, Мелисса С. Ревелл, Кристофер Г. Йейл, Дэвид Боссерт, Эшлин Д. Берч, Мэтью Н. Чоу, Крейг В. Хогл, Меган Айвори, Джессика Пер и др. «Разработка открытого пользовательского испытательного стенда для квантовых научных вычислений». IEEE Transactions on Quantum Engineering 2, 1–32 (2021).
https: / / doi.org/ 10.1109 / TQE.2021.3096480

[21] Колин Д. Брузевич, Джон Чиаверини, Роберт МакКоннелл и Джереми М. Сейдж. «Квантовые вычисления с захваченными ионами: прогресс и проблемы». Обзоры прикладной физики 6, 021314 (2019).
https: / / doi.org/ 10.1063 / 1.5088164

[22] Йонас М. Кюблер, Эндрю Аррасмит, Лукаш Синчио и Патрик Дж. Коулз. «Адаптивный оптимизатор для экономичных вариационных алгоритмов». Квант 4, 263 (2020).
https:/​/​doi.org/​10.22331/​q-2020-05-11-263

[23] Дидерик П. Кингма и Джимми Ба. «Адам: метод стохастической оптимизации» (2014). архив: 1412.6980.
Arxiv: 1412.6980

[24] Трюгве Хельгакер, Пол Йоргенсен и Йеппе Олсен. «Молекулярная теория электронной структуры». Джон Уайли и сыновья. (2014).
https: / / doi.org/ 10.1002 / 9781119019572

[25] Том Шаул, Иоаннис Антоноглу и Дэвид Сильвер. «Юнит-тесты для стохастической оптимизации». В Yoshua Bengio и Yann LeCun, редакторы, 2-я Международная конференция по представительствам в обучении, ICLR 2014, Banff, AB, Канада, 14-16 апреля 2014 г., материалы конференции. (2014). URL: http://​/​arxiv.org/​abs/​1312.6055.
Arxiv: 1312.6055

[26] Хилал Аси и Джон К. Дучи. «Важность лучших моделей в стохастической оптимизации». Труды Национальной академии наук 116, 22924–22930 (2019).
https: / / doi.org/ 10.1073 / pnas.1908018116

[27] Билли Джин, Катя Шейнберг и Мяолан Се. «Границы сложности высокой вероятности для линейного поиска на основе стохастических оракулов» (2021). архив: 2106.06454.
Arxiv: 2106.06454

[28] Хосе Бланше, Коралия Картис, Мэтт Меникелли и Катя Шейнберг. «Анализ скорости сходимости стохастического метода доверительной области с помощью супермартингейлов». Журнал по оптимизации ИНФОРМ 1, 92–119 (2019).
https://​/​doi.org/​10.1287/​ijoo.2019.0016

[29] Кортни Пакетт и Катя Шейнберг. «Стохастический метод линейного поиска с анализом ожидаемой сложности». Журнал SIAM по оптимизации 30, 349–376 (2020).
https: / / doi.org/ 10.1137 / 18M1216250

[30] Альберт С. Берахас, Лиюань Цао и Катя Шейнберг. «Глобальный анализ скорости сходимости общего алгоритма линейного поиска с шумом». Журнал SIAM по оптимизации 31, 1489–1518 (2021).
https: / / doi.org/ 10.1137 / 19M1291832

[31] Коралия Картис, Николас И. М. Гулд и Ф. Л. Тойнт. «О сложности наискорейшего спуска, Ньютона и регуляризованных методов Ньютона для невыпуклых задач оптимизации без ограничений». Сиамский журнал по оптимизации 20, 2833–2852 (2010).
https: / / doi.org/ 10.1137 / 090774100

[32] Коралия Картис, Николас И. М. Гулд и Филипп Л. Туан. «О оракуловой сложности алгоритмов первого порядка и алгоритмов без производных для гладкой невыпуклой минимизации». Журнал SIAM по оптимизации 22, 66–86 (2012).
https: / / doi.org/ 10.1137 / 100812276

[33] Яир Кармон, Джон К. Дучи, Оливер Хиндер и Аарон Сидфорд. «Нижние оценки для нахождения стационарных точек I». Математическое программирование 184, 71–120 (2020).
https: / / doi.org/ 10.1007 / s10107-019-01406-й

[34] Яир Кармон, Джон К. Дучи, Оливер Хиндер и Аарон Сидфорд. ««выпуклый, пока не доказана вина»: безразмерное ускорение градиентного спуска на невыпуклых функциях». На международной конференции по машинному обучению. Страницы 654–663. ПМЛР (2017).
https: / / doi.org/ 10.5555 / 3305381.3305449

[35] Чи Джин, Пранит Нетрапалли и Майкл Джордан. «Ускоренный градиентный спуск избегает седловых точек быстрее, чем градиентный спуск». На конференции по теории обучения. Страницы 1042–1085. ПМЛР (2018). URL: https://​/​proceedings.mlr.press/​v75/​jin18a.html.
https://​/​proceedings.mlr.press/​v75/​jin18a.html

[36] Саид Гадими и Гуанхуи Лан. «Стохастические методы первого и нулевого порядка для невыпуклого стохастического программирования». Журнал SIAM по оптимизации 23, 2341–2368 (2013).
https: / / doi.org/ 10.1137 / 120880811

[37] Йосси Арджевани, Яир Кармон, Джон К. Дучи, Дилан Дж. Фостер, Натан Сребро и Блейк Вудворт. «Нижние оценки для невыпуклой стохастической оптимизации» (2019). архив: 1912.02365.
Arxiv: 1912.02365

[38] Конг Фан, Крис Джунчи Ли, Чжоучэнь Линь и Тонг Чжан. «Паук: почти оптимальная невыпуклая оптимизация с помощью стохастической интегральной дифференциальной оценки». В S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi и R. Garnett, редакторы, Advances in Neural Information Processing Systems. Том 31. Curran Associates, Inc. (2018). URL: https://​/​proceedings.neurips.cc/​paper/​2018/​file/​1543843a4723ed2ab08e18053ae6dc5b-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​1543843a4723ed2ab08e18053ae6dc5b-Paper.pdf

[39] Широ Тамия и Хаята Ямасаки. «Стохастическая градиентная линия байесовской оптимизации: сокращение количества измерений при оптимизации параметризованных квантовых схем» (2021 г.). архив: 2111.07952.
https:/​/​doi.org/​10.1038/​s41534-022-00592-6
Arxiv: 2111.07952

[40] Паскуаль Джордан и Юджин Пол Вигнер. «über das paulische äquivalenzverbot». В Собрании сочинений Юджина Пауля Вигнера. Страницы 109–129. Спрингер (1993).

[41] Мария Шульд, Вилле Бергхольм, Кристиан Гоголин, Джош Исаак и Натан Киллоран. «Оценка аналитических градиентов на квантовом оборудовании». Физический обзор A 99, 032331 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.032331

[42] Джунхо Ли, Уильям Дж. Хаггинс, Мартин Хед-Гордон и К. Биргитта Уэйли. «Обобщенные унитарно-связанные кластерные волновые функции для квантовых вычислений». Журнал химической теории и вычислений 15, 311–324 (2018).
https: / / doi.org/ 10.1021 / acs.jctc.8b01004

[43] Альберто Перуццо, Джаррод МакКлин, Питер Шадболт, Ман-Хонг Юнг, Сяо-Ци Чжоу, Питер Дж. Лав, Алан Аспуру-Гузик и Джереми Л. О'Брайен. «Вариационный решатель собственных значений на фотонном квантовом процессоре». Сообщения о природе 5, 1–7 (2014). URL-адрес: https://​/​doi.org/​10.1038/​ncomms5213.
https: / / doi.org/ 10.1038 / ncomms5213

[44] Илья Г Рябинкин, Цзы-Чинг Йен, Скотт Н Генин и Артур Ф Измайлов. «Метод связанных кластеров кубитов: систематический подход к квантовой химии на квантовом компьютере». Журнал химической теории и вычислений 14, 6317–6326 (2018).
https: / / doi.org/ 10.1021 / acs.jctc.8b00932

[45] Хо Лун Тан, В.О. Школьников, Джордж С. Бэррон, Харпер Р. Гримсли, Николас Дж. Мэйхолл, Эдвин Барнс и София Э. Эконому. «qubit-ADAPT-VQE: адаптивный алгоритм построения аппаратно-эффективного анзаца на квантовом процессоре». PRX Quantum 2, 020310 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.020310

[46] Дмитрий А. Федоров, Юрий Алексеев, Стивен К. Грей и Мэтью Оттен. «Унитарно-селективный метод связанных кластеров». Квант 6, 703 (2022).
https:/​/​doi.org/​10.22331/​q-2022-05-02-703

[47] Пранав Гокхале, Оливия Ангиули, Юншан Дин, Кайвен Гуй, Тиг Томеш, Мартин Сучара, Маргарет Мартоноси и Фредерик Т Чонг. «$ o (n^3) $ стоимость измерения для вариационного квантового собственного решателя на молекулярных гамильтонианах». IEEE Transactions on Quantum Engineering 1, 1–24 (2020).
https: / / doi.org/ 10.1109 / TQE.2020.3035814

[48] Рубинг Чен, Мэтт Меникелли и Катя Шейнберг. «Стохастическая оптимизация с использованием метода доверительной области и случайных моделей». Математическое программирование 169, 447–487 (2018).
https:/​/​doi.org/​10.1007/​s10107-017-1141-8

[49] Леон Ботту, Фрэнк Э. Кертис и Хорхе Носедаль. «Методы оптимизации для крупномасштабного машинного обучения». Siam Review 60, 223–311 (2018).
https: / / doi.org/ 10.1137 / 16M1080173

[50] Йоэль Дрори и Охад Шамир. «Сложность поиска стационарных точек при стохастическом градиентном спуске». На международной конференции по машинному обучению. Страницы 2658–2667. ПМЛР (2020). URL: https://​/​proceedings.mlr.press/​v119/​drori20a.html.
https://​/​proceedings.mlr.press/​v119/​drori20a.html

[51] Конг Фан, Чжоучэнь Линь и Тонг Чжан. «Точный анализ невыпуклого SGD, выходящего из седловых точек». На конференции по теории обучения. Страницы 1192–1234. ПМЛР (2019). URL: https://​/​proceedings.mlr.press/​v99/​fang19a.html.
https://​/​proceedings.mlr.press/​v99/​fang19a.html

[52] С. Редди, Манзил Захир, Девендра Сачан, Сатьен Кале и Санджив Кумар. «Адаптивные методы невыпуклой оптимизации». В материалах 32-й конференции по системам обработки нейронной информации (NIPS 2018). (2018). URL: https://​/​proceedings.neurips.cc/​paper/​2018/​file/​90365351ccc7437a1309dc64e4db32a3-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​90365351ccc7437a1309dc64e4db32a3-Paper.pdf

[53] Леон Ботту и Оливье Буске. «Компромиссы крупномасштабного обучения». В J. Platt, D. Koller, Y. Singer и S. Roweis, редакторы, Advances in Neural Information Processing Systems. Том 20. Curran Associates, Inc. (2007). URL: https://​/​proceedings.neurips.cc/​paper/​2007/​file/​0d3180d672e08b4c5312dcdafdf6ef36-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2007/​file/​0d3180d672e08b4c5312dcdafdf6ef36-Paper.pdf

[54] Питер Дж. Каралекас, Николас А. Тезак, Эрик С. Петерсон, Колм А. Райан, Маркус П. да Силва и Роберт С. Смит. «Квантово-классическая облачная платформа, оптимизированная для вариационных гибридных алгоритмов». Квантовая наука и технологии 5, 024003 (2020).
https: / / doi.org/ 10.1088 / 2058-9565 / ab7559

[55] Г. Дж. Бригель, Томмазо Каларко, Дитер Якш, Хуан Игнасио Сирак и Петер Золлер. «Квантовые вычисления с нейтральными атомами». Журнал современной оптики 47, 415–451 (2000).
https: / / doi.org/ 10.1080 / 09500340008244052

[56] Сергей Бравый, Джей М. Гамбетта, Антонио Меццакапо и Кристан Темме. «Сужение кубитов для моделирования фермионных гамильтонианов» (2017). архив: 1701.08213.
Arxiv: 1701.08213

[57] Доктор медицинских наук САЖИД АНИС, Эктор Абрахам, АдуОффей, Рочиша Агарвал, Габриэле Альярди, Мерав Аарони, Исмаил Юнус Ахалвая, Гади Александрович, Томас Александр, Мэтью Эми, Сашват Анаголум, Эли Арбель, Авраам Асфау, Аниш Атали, Артур Авхадиев и др. «Qiskit: платформа с открытым исходным кодом для квантовых вычислений» (2021 г.).

[58] Цию Чжу, Ричард Х. Берд, Пейхуан Лу и Хорхе Ноцедаль. «Алгоритм 778: L-BFGS-B: подпрограммы Фортрана для крупномасштабной оптимизации с ограничениями». Транзакции ACM по математическому программному обеспечению (TOMS) 23, 550–560 (1997).
https: / / doi.org/ 10.1145 / 279232.279236

[59] Рагху Боллапрагада, Ричард Берд и Хорхе Носедал. «Стратегии адаптивной выборки для стохастической оптимизации». Журнал SIAM по оптимизации 28, 3312–3343 (2018).
https: / / doi.org/ 10.1137 / 17M1154679

[60] Рагху Боллапрагада, Хорхе Носедал, Дхеватса Мудигере, Хао-Джун Ши и Пинг Так Питер Тан. «Метод прогрессивной пакетной обработки L-BFGS для машинного обучения». На международной конференции по машинному обучению. Страницы 620–629. ПМЛР (2018). URL: https://​/​proceedings.mlr.press/​v80/​bollapragada18a.html.
https://​/​proceedings.mlr.press/​v80/​bollapragada18a.html

[61] Рагху Пасупати, Питер Глинн, Сумьядип Гош и Фатемех С. Хашеми. «О частоте дискретизации в рекурсиях на основе моделирования». Журнал SIAM по оптимизации 28, 45–73 (2018).
https: / / doi.org/ 10.1137 / 140951679

[62] Эндрю Аррасмит, Лукаш Чинчио, Роландо Д. Сомма и Патрик Дж. Коулз. «Операторная выборка для экономичной оптимизации в вариационных алгоритмах» (2020). архив: 2004.06252.
Arxiv: 2004.06252

[63] Янъян Сюй и Вотао Инь. «Блочная итерация стохастического градиента для выпуклой и невыпуклой оптимизации». Журнал SIAM по оптимизации 25, 1686–1716 (2015).
https: / / doi.org/ 10.1137 / 140983938

Цитируется

[1] Мэтт Меникелли, Стефан М. Уайлд и Миаолан Се, «Стохастический квазиньютоновский метод в отсутствие обычных случайных чисел», Arxiv: 2302.09128, (2023).

[2] Косуке Ито, «Адаптивное распределение импульсов с учетом задержки для эффективных вариационных квантовых алгоритмов во время выполнения», Arxiv: 2302.04422, (2023).

Приведенные цитаты из САО / НАСА ADS (последнее обновление успешно 2023-03-16 18:30:45). Список может быть неполным, поскольку не все издатели предоставляют подходящие и полные данные о цитировании.

Не удалось получить Перекрестная ссылка на данные во время последней попытки 2023-03-16 18:30:43: Не удалось получить цитируемые данные для 10.22331 / q-2023-03-16-949 от Crossref. Это нормально, если DOI был зарегистрирован недавно.

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

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