Теплий запуск QAOA з користувальницькими змішувачами доведено конвергує та обчислювально перевершує Max-Cut Goemans-Williamson на низькій глибині контуру

Теплий запуск QAOA з користувальницькими змішувачами доведено конвергує та обчислювально перевершує Max-Cut Goemans-Williamson на низькій глибині контуру

Мітка часу: 26 вересня 2023 р., 9:22

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

1CCS-3 Information Sciences, Los Alamos National Laboratory, Los Alamos, NM 87544, USA
2Технологічний інститут Джорджії, Атланта, Джорджія 30332, США
3Інститут технічних досліджень Джорджії, Атланта, Джорджія 30332, США
4Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA 02142, USA

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

абстрактний

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

Теплий запуск QAOA з користувальницькими змішувачами доведено конвергує та обчислювально перевершує Max-Cut Goemans-Williamson на низькій глибині контуру PlatoBlockchain Data Intelligence. Вертикальний пошук. Ai.

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

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

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

► Дані BibTeX

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

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

[2] Арам В. Харроу та Ешлі Монтанаро. «Квантова обчислювальна перевага». Nature 549, 203–209 (2017).
https: / / doi.org/ 10.1038 / nature23458

[3] Едвард Фархі, Джеффрі Голдстоун і Сем Гутман. «Алгоритм квантової наближеної оптимізації» (2014).

[4] Йен Даннінг, Сваті Гупта та Джон Зільберхольц. «Що працює найкраще, коли? Систематичне оцінювання евристик для Max-Cut і QUBO». INFORMS Journal on Computing 30 (2018).
https://​/​doi.org/​10.1287/​ijoc.2017.0798

[5] Мішель Х Гоманс і Девід Вільямсон. «Покращені алгоритми наближення для задач максимального розрізу та виконуваності з використанням напіввизначеного програмування». Журнал 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] Héctor Abraham, AduOffei, Rochisha Agarwal, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz та ін. «Qiskit: фреймворк з відкритим кодом для квантових обчислень» (2019).

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

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

[10] Стефан Сак, Раймель Медіна, Річард Куенг і Максим Сербин. “Рекурсивна жадібна ініціалізація алгоритму квантової наближеної оптимізації з гарантованим покращенням”. Physical Review A 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] Лео Чжоу, Шенг-Тао Ван, Сунвон Чой, Ханнес Піхлер і Михайло Д Лукін. «Алгоритм квантової наближеної оптимізації: продуктивність, механізм і реалізація на пристроях короткострокового використання». Physical Review X 10, 021067 (2020).
https: / / doi.org/ 10.1103 / PhysRevX.10.021067

[13] Руслан Шайдулін, Філіп К. Лотшоу, Джеффрі Ларсон, Джеймс Островскі та Тревіс Хамбл. “Передача параметрів для квантової наближеної оптимізації зваженого maxcut”. ACM Transactions on Quantum Computing 4, 1–15 (2023).
https: / / doi.org/ 10.1145 / 3584706

[14] Олексій Галда, Сяоюань Лю, Данило Ликов, Юрій Алексєєв та Ілля Сафро. «Передача оптимальних параметрів QAOA між випадковими графами». У 2021 році IEEE International Conference on Quantum Computing and Engineering (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-w

[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 році IEEE 19-та міжнародна конференція з програмного забезпечення архітектури Companion (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». Physical Review A 103, 042612 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042612

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

[25] Сергій Бравий, Олександр Кліш, Роберт Кеніг і Євген Танг. «Перешкоди для варіаційної квантової оптимізації від захисту симетрії». Physical Review Letters 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$: аналітичні та числові результати для анзаца квантового змінного оператора”. фіз. Rev. A 101, 012320 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.012320

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

[35] Андреас Бертчі та Стефан Ейденбенц. «Змішувачі Grover для QAOA: перенесення складності від конструкції змішувача до підготовки стану». У 2020 році IEEE International Conference on Quantum Computing and Engineering (QCE). Сторінки 72–82. IEEE (2020).
https: / / doi.org/ 10.1109 / QCE49297.2020.00020

[36] Чжан Цзян, Елеонора Дж. Ріффель і Чжіхуй Ван. «Майже оптимальна квантова схема для неструктурованого пошуку Гровера з використанням поперечного поля». Physical Review A 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] Сонг Мей, Теодор Місякевич, Андреа Монтанарі та Роберто Імбузейро Олівейра. «Вирішення проблем sdps для синхронізації та maxcut за допомогою нерівності Гротендіка». На конференції з теорії навчання. Сторінки 1476–1515. PMLR (2017).
https://​/​doi.org/​10.48550/​arXiv.1703.08729

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

[41] Рубен Тейт і Сваті Гупта. «Ci-qube». Репозиторій GitHub (2021). url: https://​/​github.com/​swati1729/​CI-QuBe.
https://​/​github.com/​swati1729/​CI-QuBe

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

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

[44] Сергій Бравій, Сара Шелдон, Абхінав Кандала, Девід С. Маккей і Джей М. Гамбетта. «Зменшення помилок вимірювання в багатокубітних експериментах». фіз. Rev. A 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] MJD Powell. «Метод оптимізації прямого пошуку, який моделює цільові функції та функції обмежень шляхом лінійної інтерполяції». Досягнення в оптимізації та числовому аналізі 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] Георг Фробеніус. “Ueber matrizen aus nicht negativen elementen”. Sitzungsberichte der Königlich Preussischen Akademie der WissenschaftenPages 456–477 (1912).

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

[53] Симон Шпакапан. “Зв’язність декартових добутків графів”. Applied Mathematics Letters 21, 682–685 (2008).
https://​/​doi.org/​10.1016/​j.aml.2007.06.010

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

[55] Фанат Р. К. Чунга. “Спектральна теорія графів”. Том 92. American Mathematical Soc. (1997).
https://​/​doi.org/​10.1090/​cbms/​092

[56] М. А. Нільсена та І. Л. Чуанга. “Квантові обчислення та квантова інформація: 10-те ювілейне видання”. Cambridge University Press, Нью-Йорк. (2011).
https://​/​doi.org/​10.1017/​CBO9780511976667

[57] Вінсент Р. Паскуцці, Андре Ге, Крістіан В. Бауер, Вібе А. де Йонг і Бенджамін Нахман. “Обчислювально ефективна екстраполяція з нульовим шумом для пом’якшення помилки квантового затвора”. Physical Review A 105, 042406 (2022).
https: / / doi.org/ 10.1103 / PhysRevA.105.042406

[58] Евут Ван Ден Берг, Златко К Мінєв, Абхінав Кандала та Крістан Темме. “Скасування імовірнісної помилки з розрідженими моделями Паулі–Ліндблада на шумних квантових процесорах”. Nature PhysicsPages 1–6 (2023).
https:/​/​doi.org/​10.1038/​s41567-023-02042-2

[59] Натан Кріслок, Жером Малік і Фредерік Рупен. “BiqCrunch: напіввизначений метод розгалужень і зв’язків для вирішення бінарних квадратичних задач”. ACM Transactions on Mathematical Software 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] Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun і Marco Pistoia, «Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Portfolio Optimization», arXiv: 2305.03857, (2023).

[3] В. Вієндран, Арітра Дас, Дакс Еншан Ко, Саїд М. Асад і Пінг Кой Лам, «Експресивний анзац для квантової оптимізації на низькій глибині», arXiv: 2302.04479, (2023).

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

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

[6] Phillip C. Lotshaw, Kevin D. Battles, Bryan Gard, Gilles Buchs, Travis S. Humble, and Creston D. Herold, “Modeling noise in global Mølmer-Sørensen interakcijи, застосовані до квантової наближеної оптимізації”, Фізичний огляд A 107 6, 062406 (2023).

[7] Guoming Wang, «Алгоритм квантової оптимізації з класичним посиленням», arXiv: 2203.13936, (2022).

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

On Служба, на яку посилається Crossref даних про цитування робіт не знайдено (остання спроба 2023-09-27 01:31:17).

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

Часова мітка:

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