Теплый запуск QAOA с использованием специальных смесителей доказуемо сходится и в вычислительном отношении превосходит Max-Cut Гоеманса-Вильямсона при малых глубинах контура

Теплый запуск QAOA с использованием специальных смесителей доказуемо сходится и в вычислительном отношении превосходит Max-Cut Гоеманса-Вильямсона при малых глубинах контура

Отметка времени: 26 сентября 2023 г., 9:22

Рубен Тейт1, Джай Мундра2, Брайан Гард3, Грег Молер3и Свати Гупта4

1CCS-3 Информационные науки, Национальная лаборатория Лос-Аламоса, Лос-Аламос, Нью-Мексико 87544, США
2Технологический институт Джорджии, Атланта, Джорджия 30332, США
3Технологический исследовательский институт Джорджии, Атланта, Джорджия 30332, США
4Школа менеджмента Слоана, Массачусетский технологический институт, Кембридж, Массачусетс 02142, США

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

Абстрактные

Мы обобщаем алгоритм квантовой приближенной оптимизации (QAOA) Фархи и др. (2014), чтобы учесть произвольные разделяемые начальные состояния с соответствующими смесителями, так что начальное состояние является наиболее возбужденным состоянием гамильтониана смешивания. Мы демонстрируем эту версию QAOA, которую мы называем $QAOA-теплый$, путем моделирования Max-Cut на взвешенных графах. Мы инициализируем начальное состояние как $теплый старт$, используя $2$- и $3$-мерные аппроксимации, полученные с использованием рандомизированных проекций решений полуопределенной программы Max-Cut, и определяем $пользовательский микшер$, зависящий от теплого старта. Мы показываем, что эти теплые старты инициализируют схему QAOA с аппроксимациями постоянного фактора $0.658$ для $2$-мерных и $0.585$ для $3$-мерных тёплых стартов для графов с неотрицательными весами ребер, улучшая ранее известную тривиальную задачу ( т. е. $0.5$ для стандартной инициализации) границы наихудшего случая при $p=0$. Фактически эти факторы ограничивают приближение, достигнутое для Max-Cut на более высоких глубинах схемы, поскольку мы также показываем, что самое теплое QAOA с любым отделимым начальным состоянием сходится к Max-Cut в адиабатическом пределе как $prightarrow infty$. Однако выбор «теплого старта» существенно влияет на скорость сходимости к Max-Cut, и мы эмпирически показываем, что наш «теплый старт» обеспечивает более быструю сходимость по сравнению с существующими подходами. Кроме того, наше численное моделирование показывает более высокое качество разрезов по сравнению со стандартным QAOA, классическим алгоритмом Гоеманса-Вильямсона и горячим запуском QAOA без пользовательских микшеров для библиотеки экземпляров с графами стоимостью $1148$ (до $11$ узлов) и глубиной $p=8. $. Далее мы показываем, что QAOA-warmest превосходит стандартный QAOA Фархи и др. в экспериментах на современном оборудовании IBM-Q и Quantinuum.

Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson’s Max-Cut at Low Circuit Depths PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Рекомендованное изображение: Производительность самого теплого QAOA (с теплым запуском) и стандартного QAOA как функция глубины QAOA для идеального (пунктир) и шумного моделирования (пунктир). Для выбранного 20-узлового графа GW достигает коэффициента аппроксимации 0.912, тогда как в идеальном случае самый теплый QAOA превосходит GW при $p geq 2$, в то время как стандартный QAOA требует $p > 4$. Моделирование шума основано на данных калибровки устройства IBM-Q Guadalupe.

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

Алгоритм квантовой аппроксимационной оптимизации (QAOA) — это гибридный квантово-классический метод комбинаторной оптимизации, который обещает быть более мощным, чем любой классический оптимизатор. В этой работе мы иллюстрируем его потенциал на фундаментальной задаче комбинаторной оптимизации, известной как Max-Cut, где лучшим из возможных классических алгоритмов является алгоритм Гоеманса и Уильямсона (GW). Мы достигаем этого, вводя в QAOA классически полученные теплые старты с модифицированными операторами смешивания и демонстрируя вычислительными методами, что это превосходит GW. Мы соответствующим образом модифицируем квантовый алгоритм, чтобы сохранить связь с квантовыми адиабатическими вычислениями; мы обсуждаем теорию и предоставляем численные и экспериментальные данные, показывающие перспективность нашего подхода.

► Данные BibTeX

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

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

[2] Арам В. Харроу и Эшли Монтанаро. «Квантовое вычислительное превосходство». Природа 549, 203–209 (2017).
https: / / doi.org/ 10.1038 / nature23458

[3] Эдвард Фархи, Джеффри Голдстоун и Сэм Гутманн. «Квантовый приближенный алгоритм оптимизации» (2014).

[4] Иэн Даннинг, Свати Гупта и Джон Силберхольц. «Что и когда работает лучше всего? Систематическая оценка эвристики для Max-Cut и QUBO». ИНФОРМС Журнал по вычислительной технике 30 (2018).
https: / / doi.org/ 10.1287 / ijoc.2017.0798

[5] Мишель X Гоеманс и Дэвид П. Уильямсон. «Улучшенные алгоритмы аппроксимации задач максимального разреза и выполнимости с использованием полуопределенного программирования». Журнал ACM (JACM) 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684

[6] Сэмюэл Бюрер и Ренато Д.С. Монтейру. «Алгоритм нелинейного программирования для решения полуопределенных программ посредством факторизации низкого ранга». Математическое программирование 95, 329–357 (2003).
https:/​/​doi.org/​10.1007/​s10107-002-0352-8

[7] Эктор Абрахам, АдуОффей, Рочиша Агарвал, Исмаил Юнус Ахалвая, Гади Александрович и др. «Qiskit: платформа с открытым исходным кодом для квантовых вычислений» (2019).

[8] Мэделин Кейн, Эдвард Фархи, Сэм Гутманн, Дэниел Ранард и Юджин Танг. «QAOA застревает, начиная с хорошей классической струны» (2022).

[9] Дэниел Дж. Эггер, Якуб Маречек и Стефан Вернер. «Квантовая оптимизация с теплым запуском». Квант 5, 479 (2021).
https:/​/​doi.org/​10.22331/​q-2021-06-17-479

[10] Стефан Х. Сак, Раймель А. Медина, Ричард Куенг и Максим Сербин. «Рекурсивная жадная инициализация алгоритма квантовой аппроксимации с гарантированным улучшением». Физическое обозрение А 107, 062404 (2023).
https: / / doi.org/ 10.1103 / PhysRevA.107.062404

[11] Стефан Сак и Максим Сербин. «Инициализация квантового отжига алгоритма квантовой аппроксимированной оптимизации». квант 5, 491 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-01-491

[12] Лео Чжоу, Шэн-Тао Ван, Сунвон Чой, Ханнес Пихлер и Михаил Д. Лукин. «Алгоритм квантовой аппроксимационной оптимизации: производительность, механизм и реализация на устройствах ближайшего будущего». Физическое обозрение X 10, 021067 (2020).
https: / / doi.org/ 10.1103 / PhysRevX.10.021067

[13] Руслан Шайдулин, Филип С. Лотшоу, Джеффри Ларсон, Джеймс Островски и Трэвис С. Хамбл. «Передача параметров для квантовой аппроксимационной оптимизации взвешенного maxcut». Транзакции ACM на квантовых вычислениях 4, 1–15 (2023).
https: / / doi.org/ 10.1145 / 3584706

[14] Алексей Галда, Сяоюань Лю, Данил Лыков, Юрий Алексеев и Илья Сафро. «Перенос оптимальных параметров QAOA между случайными графами». В 2021 году пройдет Международная конференция IEEE по квантовым вычислениям и инженерии (QCE). Страницы 171–180. IEEE (2021).
https: / / doi.org/ 10.1109 / QCE52317.2021.00034

[15] Йоханнес Вайденфеллер, Люсия К. Валор, Жюльен Гакон, Кэролайн Торноу, Лучано Белло, Стефан Вернер и Дэниел Дж. Эггер. «Масштабирование алгоритма квантовой аппроксимированной оптимизации на аппаратном обеспечении на основе сверхпроводящих кубитов». Квант 6, 870 (2022).
https:/​/​doi.org/​10.22331/​q-2022-12-07-870

[16] Филип С. Лотшоу, Тьен Нгуен, Энтони Сантана, Александр Маккаски, Ребекка Херрман, Джеймс Островски, Джордж Сиопсис и Трэвис С. Хамбл. «Масштабирование квантовой аппроксимационной оптимизации на ближайшем оборудовании». Научные отчеты 12, 12388 (2022 г.).
HTTPS: / / doi.org/ 10.1038 / s41598-022-14767-ш

[17] Джан Джакомо Геррески и Энн Мацуура. «QAOA для максимального сокращения требует сотен кубитов для квантового ускорения». Научные доклады 9, 1–7 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-43176-9

[18] Шарль Мусса, Анри Каландра и Ведран Дунько. «Квантовать или не квантовать: к выбору алгоритма в краткосрочной квантовой оптимизации». Квантовая наука и технологии 5, 044009 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb8e5

[19] Колин Кэмпбелл и Эдвард Даль. «QAOA высшего порядка». В 2022 году пройдет 19-я Международная конференция IEEE по программной архитектуре (ICSA-C). Страницы 141–146. IEEE (2022 г.).
https://doi.org/10.1109/ICSA-C54293.2022.00035

[20] Ребекка Херрман, Лорна Трефферт, Джеймс Островски, Филип С. Лотшоу, Трэвис С. Хамбл и Джордж Сиопсис. «Влияние графовых структур QAOA на maxcut». Квантовая обработка информации 20, 1–21 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03232-8

[21] Гопал Чандра Сантра, Фред Енджеевски, Филипп Хауке и Дэниел Дж. Эггер. «Сжатие и квантовая приближенная оптимизация» (2022).

[22] Руслан Шайдулин, Стюарт Хэдфилд, Тэд Хогг и Илья Сафро. «Классические симметрии и алгоритм квантовой аппроксимации». Квантовая обработка информации 20, 1–28 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03298-4

[23] Джонатан Вурц и Питер Лав. «Гарантии производительности алгоритма квантовой аппроксимированной оптимизации Maxcut при p> 1». Физическое обозрение А 103, 042612 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042612

[24] Эдвард Фархи, Джеффри Голдстоун и Сэм Гутманн. «Квантовые алгоритмы для архитектур с фиксированным кубитом» (2017).

[25] Сергей Бравый, Александр Клиш, Роберт Кениг и Юджин Танг. «Препятствия вариационной квантовой оптимизации из-за защиты симметрии». Письма о физическом обзоре 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[26] Эдвард Фархи, Дэвид Гамарник и Сэм Гутманн. «Алгоритм квантовой аппроксимационной оптимизации должен видеть весь граф: типичный случай» (2020).

[27] Сергей Бравый, Александр Клиш, Роберт Кениг и Юджин Танг. «Гибридные квантово-классические алгоритмы приближенной раскраски графов». Квант 6, 678 (2022).
https:/​/​doi.org/​10.22331/​q-2022-03-30-678

[28] Мэтью Б. Гастингс. «Классические и квантовые алгоритмы аппроксимации с ограниченной глубиной» (2019).

[29] Кунал Марваха. «Локальный классический алгоритм max-cut превосходит $ p= 2$ QAOA на регулярных графах большого обхвата». Квант 5, 437 (2021).
https:/​/​doi.org/​10.22331/​q-2021-04-20-437

[30] Боаз Барак и Кунал Марваха. «Классические алгоритмы и квантовые ограничения для максимального разреза на графах большого обхвата» (2021).
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2022.14

[31] Рубен Тейт, Маджид Фархади, Крестон Херольд, Грег Молер и Свати Гупта. «Объединение классического и квантового с помощью SDP, инициализировавшего теплые старты для QAOA». Транзакции ACM по квантовым вычислениям (2022 г.).
https: / / doi.org/ 10.1145 / 3549554

[32] Стюарт Хэдфилд, Чжихуэй Ван, Брайан О'Горман, Элеонора Г. Риффель, Давиде Вентурелли и Рупак Бисвас. «От алгоритма квантовой аппроксимированной оптимизации к квантовому анзацу знакопеременного оператора». Алгоритмы 12 (2019).
https: / / doi.org/ 10.3390 / a12020034

[33] Чжихуэй Ван, Николас К. Рубин, Джейсон М. Домини и Элеонора Г. Риффель. «Смесители $xy$: аналитические и численные результаты для квантового знакопеременного оператора анзац». Физ. Ред. А 101, 012320 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.012320

[34] Линхуа Чжу, Хо Лунь Тан, Джордж С. Бэррон, Ф.А. Кальдерон-Варгас, Николас Дж. Мэйхолл, Эдвин Барнс и София Э. Эконому. «Адаптивный квантовый алгоритм приближенной оптимизации для решения комбинаторных задач на квантовом компьютере». Физ. Ред. Исследования 4, 033029 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033029

[35] Андреас Берчи и Стефан Эйденбенц. «Смесители Grover для QAOA: переход от конструкции миксера к подготовке состояния». В 2020 году Международная конференция IEEE по квантовым вычислениям и инженерии (QCE). Страницы 72–82. ИИЭР (2020).
https: / / doi.org/ 10.1109 / QCE49297.2020.00020

[36] Чжан Цзян, Элеонора Дж. Риффель и Чжихуэй Ван. «Почти оптимальная квантовая схема для неструктурированного поиска Гровера с использованием поперечного поля». Физическое обозрение А 95, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.062317

[37] Лов К. Гровер. «Быстрый квантово-механический алгоритм поиска в базе данных». В материалах двадцать восьмого ежегодного симпозиума ACM по теории вычислений. Страницы 212–219. (1996).
https: / / doi.org/ 10.1145 / 237814.237866

[38] Инь Чжан, Сэмюэл Бурер и Ренато Д.С. Монтейро. «Эвристика релаксации ранга 2 для max-cut и других двоичных квадратичных программ». SIAM Journal on Optimization 12, 503–521 (2001).
https: / / doi.org/ 10.1137 / S1052623400382467

[39] Сон Мэй, Теодор Мисякевич, Андреа Монтанари и Роберто Имбузейро Оливейра. «Решение задач синхронизации и максимального сокращения с помощью неравенства Гротендика». На конференции по теории обучения. Страницы 1476–1515. ПМЛР (2017).
https://​/​doi.org/​10.48550/​arXiv.1703.08729

[40] Оджас Парех и Кевин Томпсон. «Оптимальное приближение состояния продукта для 2-локальных квантовых гамильтонианов с положительными членами» (2022). arXiv: 2206.08342.
Arxiv: 2206.08342

[41] Рубен Тейт и Свати Гупта. «Цы-кубе». Репозиторий GitHub (2021 г.). URL: https://github.com/swati1729/CI-QuBe.
https://github.com/swati1729/CI-QuBe

[42] Говард Карлофф. «Насколько хорош алгоритм Гоеманса-Вильямсона MAX-CUT?». SIAM Journal on Computing 29, 336–350 (1999).
https: / / doi.org/ 10.1137 / S0097539797321481

[43] Мэтью П. Харриган, Кевин Дж. Санг, Мэтью Нили, Кевин Дж. Сатцингер, Фрэнк Арут, Кунал Арья, Хуан Аталая, Джозеф С. Бардин, Рами Барендс, Серджио Бойшо и др. «Квантовая аппроксимационная оптимизация задач с неплоскими графами на планарном сверхпроводящем процессоре». Физика природы 17, 332–336 (2021).
https: / / doi.org/ 10.1038 / s41567-020-01105-й

[44] Сергей Бравый, Сара Шелдон, Абхинав Кандала, Дэвид К. Маккей и Джей М. Гамбетта. «Уменьшение ошибок измерения в многокубитных экспериментах». Физ. Ред. А 103, 042605 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042605

[45] Джордж С. Бэррон и Кристофер Дж. Вуд. «Уменьшение ошибок измерения для вариационных квантовых алгоритмов» (2020).

[46] Мартин Абади, Ашиш Агарвал, Пол Бархам, Юджин Бревдо, Чжифэн Чен, Крэйг Ситро, Грег С. Коррадо, Энди Дэвис, Джеффри Дин, Матье Девин, Санджай Гемават, Иэн Гудфеллоу, Эндрю Харп, Джеффри Ирвинг, Майкл Айсард, Янцин Цзя, Рафал Йозефович, Лукаш Кайзер, Манджунат Кудлур, Джош Левенберг, Одуванчик Мане, Раджат Монга, Шерри Мур, Дерек Мюррэй, Крис Ола, Майк Шустер, Джонатон Шленс, Бенуа Штайнер, Илья Суцкевер, Кунал Талвар, Пол Такер, Винсент Ванхук, Виджай Васудеван , Фернанда Виегас, Ориол Виньялс, Пит Уорден, Мартин Ваттенберг, Мартин Вике, Юань Юй и Сяоцян Чжэн. «TensorFlow: крупномасштабное машинное обучение в гетерогенных системах» (2015).

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

[48] Роджер Флетчер. «Практические методы оптимизации (2-е издание)». Джон Уайли и сыновья. Нью-Йорк, штат Нью-Йорк, США (1987).
https: / / doi.org/ 10.1002 / 9781118723203

[49] МДжД Пауэлл. «Метод прямой поисковой оптимизации, моделирующий целевые и ограничивающие функции посредством линейной интерполяции». Достижения в оптимизации и численном анализе 275, 51–67 (1994).
https:/​/​doi.org/​10.1007/​978-94-015-8330-5_4

[50] Алан Дж. Лауб. «Матричный анализ для ученых и инженеров». Том 91. Сиам. (2005).
https: / / doi.org/ 10.1137 / 1.9780898717907

[51] Георг Фробениус. «Очень матрица из ничего негативного элемента». Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften, страницы 456–477 (1912).

[52] А. Каве и Х. Рахами. «Единый метод собственного разложения графовых произведений». Коммуникации в числовых методах в инженерии с биомедицинскими приложениями 21, 377–388 (2005).
https://​/​doi.org/​10.1002/​cnm.753

[53] Симон Шпакапан. «Связность декартовых произведений графов». Письма по прикладной математике 21, 682–685 (2008).
https: / / doi.org/ 10.1016 / j.aml.2007.06.010

[54] Яцек Гондзио и Андреас Гроти. «Решение задач нелинейного финансового планирования с использованием 109 переменных решения в массово-параллельных архитектурах». WIT Transactions по моделированию и симуляции 43 (2006).
https: / / doi.org/ 10.2495 / CF060101

[55] Фан Р.К. Чанг. «Спектральная теория графов». Том 92. Американское математическое соц. (1997).
https://doi.org/10.1090/cbms/092

[56] М. А. Нильсен и И. Л. Чуанг. «Квантовые вычисления и квантовая информация: издание к 10-летию». Издательство Кембриджского университета, Нью-Йорк. (2011).
https: / / doi.org/ 10.1017 / CBO9780511976667

[57] Винсент Р. Паскуцци, Андре Хе, Кристиан В. Бауэр, Вибе А. де Йонг и Бенджамин Нахман. «Вычислительно эффективная экстраполяция с нулевым шумом для уменьшения ошибок квантовых вентилей». Физическое обозрение А 105, 042406 (2022).
https: / / doi.org/ 10.1103 / PhysRevA.105.042406

[58] Эвоут Ван Ден Берг, Златко К. Минев, Абхинав Кандала и Кристан Темме. «Вероятностное подавление ошибок с помощью разреженных моделей Паули – Линдблада на шумных квантовых процессорах». Физика природы, страницы 1–6 (2023 г.).
https:/​/​doi.org/​10.1038/​s41567-023-02042-2

[59] Натан Крислок, Жером Малик и Фредерик Рупен. «BiqCrunch: полуопределенный метод ветвей и границ для решения бинарных квадратичных задач». Транзакции ACM в математическом программном обеспечении 43 (2017).
https: / / doi.org/ 10.1145 / 3005345

[60] Андрис Э. Брауэр, Себастьян М. Чиоабэ, Фердинанд Ирингер и Мэтт МакГиннис. «Наименьшие собственные значения графов Хэмминга, графов Джонсона и других дистанционно регулярных графов с классическими параметрами». Журнал комбинаторной теории, серия B 133, 88–121 (2018).
https: // doi.org/ 10.1016 / j.jctb.2018.04.005

[61] Дональд Кнут. «Комбинаторные матрицы». Избранные статьи по дискретной математике (2000).
https:/​/​doi.org/​10.1016/​S0898-1221(04)90150-2

Цитируется

[1] Йоханнес Вайденфеллер, Люсия С. Валор, Жюльен Гакон, Кэролайн Торноу, Лучано Белло, Стефан Вернер и Дэниел Дж. Эггер, «Масштабирование алгоритма квантовой приближенной оптимизации на оборудовании на основе сверхпроводящих кубитов», Квант 6, 870 (2022).

[2] Цзычан Хэ, Руслан Шайдулин, Шуваник Чакрабарти, Дилан Херман, Чанхао Ли, Юэ Сун и Марко Пистойя, «Согласование исходного состояния и микшера улучшает производительность QAOA для оптимизации портфеля с ограничениями», Arxiv: 2305.03857, (2023).

[3] В. Виджендран, Аритра Дас, Дакс Эншан Кох, Сайед М. Асад и Пинг Кой Лам, «Выразительный анзац для малоглубинной квантовой оптимизации», Arxiv: 2302.04479, (2023).

[4] Эндрю Влашич, Сальваторе Черто и Ань Фам, «Дополнительный алгоритм поиска Гровера: реализация подавления амплитуды», Arxiv: 2209.10484, (2022).

[5] Мара Виццузо, Джанлука Пассарелли, Джованни Кантеле и Проколо Лучиньяно, «Конвергенция оцифрованного противодиабатического QAOA: глубина схемы в зависимости от свободных параметров», Arxiv: 2307.14079, (2023).

[6] Филлип К. Лотшоу, Кевин Д. Баттлс, Брайан Гард, Жиль Букс, Трэвис С. Хамбл и Крестон Д. Херольд, «Моделирование шума в глобальных взаимодействиях Мёлмера-Сёренсена применительно к квантовой аппроксимационной оптимизации», Физический обзор A 107 6, 062406 (2023).

[7] Гуомин Ван, «Алгоритм квантовой оптимизации с классическим усилением», Arxiv: 2203.13936, (2022).

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

On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2023-09-27 01:31:17).

Эта статья опубликована в Quantum под Creative Commons Attribution 4.0 International (CC BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.

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

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