1Лабораторія квантового штучного інтелекту (QuAIL), дослідницький центр Еймса НАСА, Моффетт Філд, Каліфорнія
2USRA Research Institute for Advanced Computer Science (RIACS), Маунтін-В’ю, Каліфорнія
3Берклійський центр квантової інформації та обчислень, Каліфорнійський університет, Берклі, Каліфорнія
4Департамент комп'ютерних наук Чиказького університету, Чикаго, Іллінойс
Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на SciRate.
абстрактний
Ми розглядаємо потужність локальних алгоритмів для приблизного розв’язання Max $k$XOR, узагальнення двох проблем із задоволенням обмежень, які раніше вивчалися за допомогою класичних і квантових алгоритмів (MaxCut і Max E3LIN2). У Max $k$XOR кожне обмеження є XOR точно $k$ змінних і біта парності. Для випадків із випадковими знаками (парності) або без речень, що перекриваються, і речень $D+1$ на змінну, ми обчислюємо очікувану задовольняючу частку QAOA глибини 1 за Фархі та ін. [arXiv:1411.4028] і порівнюємо з узагальненням локальний пороговий алгоритм від Hirvonen та інших [arXiv:1402.2543]. Примітно, що квантовий алгоритм перевершує пороговий алгоритм для $k$$gt$$4$.
З іншого боку, ми підкреслюємо потенційні труднощі для QAOA у досягненні обчислювальної квантової переваги в цій проблемі. Спочатку ми обчислюємо жорстку верхню межу максимально задовольняючої частки майже всіх великих випадкових регулярних випадків Max $k$XOR шляхом чисельного розрахунку щільності енергії основного стану $P(k)$ $k$-спінового скла середнього поля [ arXiv:1606.02365]. Верхня межа зростає з $k$ набагато швидше, ніж продуктивність обох однолокальних алгоритмів. Ми також ідентифікуємо новий результат обструкції для квантових ланцюгів малої глибини (включаючи QAOA), коли $k=3$, узагальнюючи результат Bravyi та інших [arXiv:1910.08980], коли $k=2$. Ми припускаємо, що подібна перешкода існує для всіх $k$.
Рекомендоване зображення: порівняння задовольняючої частки (продуктивності) порогового алгоритму та глибини 1 QAOA для Max kXOR при великих $D$ (і $D gg k$). Константа $C_k$ для QAOA зростає швидше з $k$, ніж для порогового алгоритму. Хоча пороговий алгоритм перевершує QAOA глибини 1 для $k у {2,3,4}$, за всіх інших k QAOA є кращим алгоритмом.
[Вбудоване вміст]
► Дані BibTeX
► Список літератури
[1] А. Ауфінгер і В.-К. Чен. Про властивості паризьких мір. arXiv:1303.3573, doi:10.1007/s00440-014-0563-y.
https: / / doi.org/ 10.1007 / s00440-014-0563-y
arXiv: 1303.3573
[2] А. Ауфінгер і В.-К. Чен. Формула Parisi має унікальний мінімайзер. Communications in Mathematical Physics, 335(3):1429–1444, листопад 2014 р. arXiv:1402.5132, doi:10.1007/s00220-014-2254-z.
https: / / doi.org/ 10.1007 / s00220-014-2254-z
arXiv: 1402.5132
[3] А. Ауфінгер і В.-К. Чен. Формула Парізі для енергії основного стану в моделі змішаного p-спіну. arXiv:1606.05335, doi:10.1214/16-aop1173.
https:///doi.org/10.1214/16-aop1173
arXiv: 1606.05335
[4] А. Е. Алауї та А. Монтанарі. Алгоритмічні пороги в спінових окулярах середнього поля. arXiv:2009.11481.
arXiv: 2009.11481
[5] А. Е. Алауї, А. Монтанарі та М. Селке. Оптимізація спінових стекол середнього поля. arXiv:2001.00904, doi:10.1214/21-aop1519.
https:///doi.org/10.1214/21-aop1519
arXiv: 2001.00904
[6] С. Бравий, А. Кліш, Р. Кеніг, Е. Танг. Перешкоди для підготовки стану та варіаційної оптимізації від захисту симетрії. Препринт arXiv, 2019. arXiv:1910.08980.
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
arXiv: 1910.08980
[7] Б. Барак і К. Марваха. Класичні алгоритми та квантові обмеження для максимального розрізу на графіках з високим обхватом. arXiv:2106.05900, doi:10.4230/LIPIcs.ITCS.2022.14.
https:///doi.org/10.4230/LIPIcs.ITCS.2022.14
arXiv: 2106.05900
[8] Б. Барак, А. Мойтра, Р. О'Доннелл та ін. Подолання випадкового призначення в задачах задоволення обмежень обмеженого ступеня. arXiv:1505.03424.
arXiv: 1505.03424
[9] В.-К. Чен, Д. Гамарник, Д. Панченко, М. Рахман. Субоптимальність локальних алгоритмів для класу задач максимального розрізу. The Annals of Probability, 47(3), травень 2019 р. arXiv:1707.05386, doi:10.1214/18-aop1291.
https:///doi.org/10.1214/18-aop1291
arXiv: 1707.05386
[10] К.-Н. Чоу, PJ Love, JS Sandhu та J. Shi. Обмеження локальних квантових алгоритмів на Random Max-k-XOR і далі. arXiv:2108.06049.
arXiv: 2108.06049
[11] А. Крізанті та Т. Ріццо. Аналіз рішення $infty$-репліки порушення симетрії моделі Шеррінгтона-Кіркпатріка. Physical Review E, 65(4), квітень 2002 р. arXiv:cond-mat/0111037, doi:10.1103/physreve.65.046137.
https:///doi.org/10.1103/physreve.65.046137
arXiv:cond-mat/0111037
[12] Б. Дерріда. Модель випадкової енергії: точно розв’язувана модель невпорядкованих систем. фіз. B, 24:2613–2626, вересень 1981. doi:10.1103/PhysRevB.24.2613.
https:///doi.org/10.1103/PhysRevB.24.2613
[13] А. Дембо, А. Монтанарі та С. Сен. Екстремальні розрізи розріджених випадкових графів. The Annals of Probability, 45(2):1190–1217, 2017. arXiv:1503.03923, doi:10.1214/15-aop1084.
https:///doi.org/10.1214/15-aop1084
arXiv: 1503.03923
[14] Л. Елдар і А. В. Харроу. Локальні гамільтоніани, основні стани яких важко апроксимувати. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), жовтень 2017 р. arXiv:1510.02082, doi:10.1109/focs.2017.46.
https:///doi.org/10.1109/focs.2017.46
arXiv: 1510.02082
[15] Е. Фархі, Дж. Голдстоун і С. Гутман. Алгоритм квантової наближеної оптимізації. arXiv:1411.4028.
arXiv: 1411.4028
[16] Е. Фархі, Дж. Голдстоун і С. Гутман. Алгоритм квантової наближеної оптимізації, застосований до проблеми обмеження появи. arXiv:1412.6062.
arXiv: 1412.6062
[17] Е. Фархі, Д. Гамарник, С. Гутман. Алгоритм квантової наближеної оптимізації повинен бачити весь графік: типовий випадок. arXiv:2004.09002.
arXiv: 2004.09002
[18] Дж. Фрідман. Доказ гіпотези другого власного значення Алона та пов’язаних проблем. arXiv:cs/0405020, doi:10.1090/memo/0910.
https:///doi.org/10.1090/memo/0910
arXiv:cs/0405020
[19] С. Хедфілд. Квантові алгоритми для наукових обчислень та наближеної оптимізації. Колумбійський університет, 2018, arXiv:1805.03265.
arXiv: 1805.03265
[20] J. Håstad. Деякі оптимальні результати неапроксимації. Журнал ACM (JACM), 48(4):798–859, 2001. doi:10.1145/258533.258536, URL http://www.cs.umd.edu/gasarch/BLOGPAPERS/max3satl. pdf.
https: / / doi.org/ 10.1145 / 258533.258536
http:///www.cs.umd.edu/~gasarch/BLOGPAPERS/max3satl.pdf
[21] М. Б. Гастінгс. Тривіальні низькоенергетичні стани для комутуючих гамільтоніанів і квантова гіпотеза PCP. Квантова інформація та обчислення, 13, 2013. arXiv:1201.3387, doi:10.26421/qic13.5-6-3.
https:///doi.org/10.26421/qic13.5-6-3
arXiv: 1201.3387
[22] М. Б. Гастінгс. Алгоритми класичної та квантової обмеженої глибинної апроксимації. arXiv:1905.07047, doi:10.26421/qic19.13-14-3.
https:///doi.org/10.26421/qic19.13-14-3
arXiv: 1905.07047
[23] В. В. Хо та Т. Х. Сі. Ефективне варіаційне моделювання нетривіальних квантових станів. arXiv:1803.00026, doi:10.21468/scipostphys.6.3.029.
https:///doi.org/10.21468/scipostphys.6.3.029
arXiv: 1803.00026
[24] Й. Хірвонен, Й. Рибіцкі, С. Шмід, Я. Суомела. Великі розрізи з локальними алгоритмами на графах без трикутників. Електронний журнал комбінаторики, сторінки P4–21, 2017. arXiv:1402.2543, doi:10.37236/6862.
https: / / doi.org/ 10.37236 / 6862
arXiv: 1402.2543
[25] CY-Y. Лінь і Ю. Чжу. Продуктивність QAOA на типових прикладах задач задоволення обмежень з обмеженим ступенем. arXiv:1601.01744.
arXiv: 1601.01744
[26] К. Марваха. Локальний класичний алгоритм MAX-CUT перевершує $p=2$ QAOA на регулярних графіках з великим обхватом. Quantum, 5:437, квітень 2021 р. arXiv:2101.05513, doi:10.22331/q-2021-04-20-437.
https://doi.org/10.22331/q-2021-04-20-437
arXiv: 2101.05513
[27] А. Монтанарі. Оптимізація гамільтоніана Шеррінгтона–Кіркпатріка. arXiv:1812.10897, doi:10.1109/focs.2019.00087.
https:///doi.org/10.1109/focs.2019.00087
arXiv: 1812.10897
[28] П. Обзарський та А. Ястжбскі. Розфарбування ребер 3-рівномірних гіперграфів. Дискретна прикладна математика, 217:48–52, 2017, Комбінаторна оптимізація: теорія, обчислення та застосування. doi:10.1016/j.dam.2016.06.009.
https:///doi.org/10.1016/j.dam.2016.06.009
[29] Д. Панченко. Знайомство з моделлю SK. arXiv:1412.0170, doi:10.4310/cdm.2014.v2014.n1.a4.
https://doi.org/10.4310/cdm.2014.v2014.n1.a4
arXiv: 1412.0170
[30] Д. Панченко. На $k$-sat моделі з великою кількістю пунктів. arXiv:1608.06256, doi:10.1002/rsa.20748.
https:///doi.org/10.1002/rsa.20748
arXiv: 1608.06256
[31] Г. Парізі. Послідовність наближених розв’язків моделі SK для спінових окулярів. Journal of Physics A: Mathematical and General, 13(4):L115–L121, apr 1980. doi:10.1088/0305-4470/13/4/009.
https://doi.org/10.1088/0305-4470/13/4/009
[32] С. Сен. Оптимізація на розріджених випадкових гіперграфах і спінових окулярах. arXiv:1606.02365, doi:10.1002/rsa.20774.
https:///doi.org/10.1002/rsa.20774
arXiv: 1606.02365
[33] Р. Шайдулін, С. Хедфілд, Т. Хогг, І. Сафро. Класичні симетрії та квантовий наближений алгоритм оптимізації. Квантова обробка інформації, 20(11):1–28, 2021. arXiv:2012.04713, doi:10.1007/s11128-021-03298-4.
https://doi.org/10.1007/s11128-021-03298-4
arXiv: 2012.04713
[34] М. Талагранд. Формула Парізі. Annals of Mathematics, 163:221–263, 2006. doi:10.4007/annals.2006.163.221, URL https://annals.math.princeton.edu/wp-content/uploads/annals-v163 -n1-p04.pdf.
https:///doi.org/10.4007/annals.2006.163.221
https:///annals.math.princeton.edu/wp-content/uploads/annals-v163-n1-p04.pdf
[35] Z. Wang, S. Hadfield, Z. Jiang та EG Rieffel. Алгоритм квантової наближеної оптимізації для maxcut: ферміонний погляд. фіз. Rev. A, 97:022304, лютий 2018 р. arXiv:1706.02998, doi:10.1103/PhysRevA.97.022304.
https: / / doi.org/ 10.1103 / PhysRevA.97.022304
arXiv: 1706.02998
Цитується
[1] Жоао Бассо, Едвард Фархі, Кунал Марваха, Бенджамін Віллалонга та Лео Чжоу, «Алгоритм квантової наближеної оптимізації на великій глибині для MaxCut на регулярних графіках великого обхвату та моделі Шеррінгтона-Кіркпатріка», arXiv: 2110.14206.
[2] Nicolas PD Sawaya, Albert T Schmitz і Stuart Hadfield, «Кодування компромісів і набори інструментів проектування в квантових алгоритмах для дискретної оптимізації: розфарбовування, маршрутизація, планування та інші проблеми», arXiv: 2203.14432.
[3] Яш Дж. Пател, Соф’єн Джербі, Томас Бек і Ведран Дунько, «Рекурсивна система QAOA з підкріпленням навчання», arXiv: 2207.06294.
Вищезазначені цитати від SAO / NASA ADS (останнє оновлення успішно 2022-07-26 13:36:03). Список може бути неповним, оскільки не всі видавці надають відповідні та повні дані про цитування.
On Служба, на яку посилається Crossref даних про цитування робіт не знайдено (остання спроба 2022-07-26 13:36:00).
Ця стаття опублікована в Quantum під Creative Commons Attribution 4.0 International (CC на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.
