QuOne Lab, Phanous Research and Innovation Center, Тегеран, Іран
Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на SciRate.
абстрактний
Очікується, що еволюції локальних гамільтоніанів за короткий проміжок часу залишатимуться локальними і, отже, обмеженими. У цій статті ми підтверджуємо цю інтуїцію, доводячи деякі обмеження на короткочасні еволюції локальних залежних від часу гамільтоніанів. Ми показуємо, що розподіл результату вимірювання короткочасних (щонайбільше логарифмічних) еволюцій локальних гамільтоніанів є $концентрованим$ і задовольняє $textit{ізопериметричну нерівність}$. Щоб продемонструвати чітке застосування наших результатів, ми вивчаємо проблему $M$$small{AX}$$C$$small{UT}$ і робимо висновок, що для квантового відпалу потрібен принаймні час виконання, який логарифмічно масштабується за розміром проблеми до перемогти класичні алгоритми на $M$$small{AX}$$C$$small{UT}$. Щоб підтвердити наші результати, ми також доведемо межу Ліба-Робінсона, яка працює для залежних від часу гамільтоніанів, які можуть становити незалежний інтерес.
Рекомендоване зображення: на цій ілюстрації зображено розподіл ймовірностей ваги Хеммінга трьох різних станів $n$-кубітів для $n=100$. Центрований розподіл посередині (синій) є типовим розподілом для початкового стану продукту (наприклад, $|+rangle^{otimes n}$). Розподіл із вершиною праворуч (помаранчевий) представляє розподіл після короткочасної еволюції початкового стану, описаного в теоремі 2 рукопису. Розподіл, який має два піки по обидві сторони спектра (зелений), є наближенням для стану ГГЦ. Це показує, що стан GHZ не може бути створений навіть приблизно шляхом короткочасного квантового відпалу.
Популярне резюме
► Дані BibTeX
► Список літератури
[1] Т. Кадовакі та Х. Нішіморі. Квантовий відпал у поперечній моделі Ізінга. Physical Review E 58, 5355–5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355
[2] Е. Фархі, Дж. Голдстоун, С. Гутман і М. Сіпсер. Квантові обчислення шляхом адіабатичної еволюції. arXiv:0001106 [quant-ph] (2000).
https:///doi.org/10.48550/arXiv.quant-ph/0001106
arXiv: 0001106
[3] Т. Като. Про адіабатичній теоремі квантової механіки. Журнал фізичного товариства Японії 5, 435–439 (1950).
https:///doi.org/10.1143/JPSJ.5.435
[4] М. Борн і В. Фок. Beweis des adiabatensatzes. Zeitschrift für Physik 51, 165–180 (1928).
https: / / doi.org/ 10.1007 / BF01343193
[5] Т. Албаш і Д. А. Лідар. Адіабатичне квантове обчислення. Огляди сучасної фізики 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002
[6] І. Хен і Ф. М. Спедальєрі. Квантовий відпал для оптимізації з обмеженнями. Physical Review Applied 5, 034007 (2016).
https: / / doi.org/ 10.1103 / PhysRevApplied.5.034007
[7] С. Пурі, К. К. Андерсен, А. Л. Грімсмо та А. Блейс. Квантовий відпал зі зв'язаними нелінійними осциляторами "всі-на-всіх". Nature Communications 8, 15785 (2017).
https: / / doi.org/ 10.1038 / ncomms15785
[8] В. Лехнер, П. Хауке, П. Цоллер. Архітектура квантового відпалу з підключенням усіх до всіх завдяки локальним взаємодіям. Наукові досягнення 1, e1500838 (2015).
https: / / doi.org/ 10.1126 / sciadv.1500838
[9] С. Цзян, К. А. Брітт, А. Дж. Маккаскі, Т. С. Хамбл і С. Кейс. Квантовий відпал для простої факторизації. Наукові звіти 8, 17667 (2018).
https: / / doi.org/ 10.1038 / s41598-018-36058-z
[10] RY Li, R. Di Felice, R. Rohs і DA Lidar. Квантовий відпал проти класичного машинного навчання в застосуванні до спрощеної задачі обчислювальної біології. Квантова інформація NPJ 4, 1–10 (2018).
https://doi.org/10.1038/s41534-018-0060-8
[11] Л. Стелла, Г. Е. Санторо та Е. Тосатті. Оптимізація шляхом квантового відпалу: уроки простих випадків. Physical Review B 72, 014303 (2005).
https:///doi.org/10.1103/PhysRevB.72.014303
[12] О. Тітілойє та А. Кріспін. Квантовий відпал задачі розфарбовування графа. Дискретна оптимізація 8, 376–384 (2011).
https:///doi.org/10.1016/j.disopt.2010.12.001
[13] А. Мотт, Дж. Йоб, Ж.-Р. Влімант, Д. Лідар, М. Спіропулу. Розв’язування задачі оптимізації Хіггса за допомогою квантового відпалу для машинного навчання. Nature 550, 375–379 (2017).
https: / / doi.org/ 10.1038 / nature24047
[14] К. Л. Пуденц, Т. Албаш і Д. А. Лідар. Поправка квантового відпалу для випадкових задач Ізінга. Physical Review A 91, 042302 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.042302
[15] А. Пердомо-Ортіс, Н. Діксон, М. Дрю-Брук, Г. Роуз, А. Аспуру-Гузік. Знаходження низькоенергетичних конформацій моделей ґратчастих білків методом квантового відпалу. Наукові доповіді 2, 571 (2012).
https:///doi.org/10.1038/srep00571
[16] К. Л. Пуденц, Т. Албаш і Д. А. Лідар. Квантовий відпал із виправленням помилок із сотнями кубітів. Nature Communications 5, 1–10 (2014).
https: / / doi.org/ 10.1038 / ncomms4243
[17] Р. Мартоняк, Г. Е. Санторо та Е. Тосатті. Квантовий відпал проблеми комівояжера. Physical Review E 70, 057701 (2004).
https: / / doi.org/ 10.1103 / PhysRevE.70.057701
[18] SH Adachi і MP Henderson. Застосування квантового відпалу для навчання глибоких нейронних мереж. arXiv:1510.06356 [quant-ph] (2015).
https:///doi.org/10.48550/arXiv.1510.06356
arXiv: 1510.06356
[19] M. W Johnson та ін. Квантовий відпал із виготовленими спінами. Nature 473, 194–198 (2011).
https: / / doi.org/ 10.1038 / nature10012
[20] S. Boixo, T. Albash, FM Spedalieri, N. Chancellor і DA Lidar. Експериментальна сигнатура програмованого квантового відпалу. Nature Communications 4, 1–8 (2013).
https: / / doi.org/ 10.1038 / ncomms3067
[21] AD King та ін. Когерентний квантовий відпал у програмованому 2000-кубітовому ланцюжку Ізінга. arXiv:2202.05847 [quant-ph] (2022).
https:///doi.org/10.48550/arXiv.2202.05847
arXiv: 2202.05847
[22] Б. Фоксен та ін. Демонстрація безперервного набору двокубітових вентилів для короткочасних квантових алгоритмів. Physical Review Letters 125, 120504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.120504
[23] К. Райт та ін. Бенчмаркінг 11-кубітового квантового комп’ютера. Nature Communications 10, 1–6 (2019).
https://doi.org/10.1038/s41467-019-13534-2
[24] EJ Crosson і DA Lidar. Перспективи квантового посилення за допомогою діабатичного квантового відпалу. Nature Reviews Physics 3, 466–489 (2021).
https://doi.org/10.1038/s42254-021-00313-6
[25] Е. Фархі, Дж. Голдстоун і С. Гутман. Алгоритм квантової наближеної оптимізації. arXiv:1411.4028 [квант-ph] (2014).
https:///doi.org/10.48550/arXiv.1411.4028
arXiv: 1411.4028
[26] Е. Фархі, Д. Гамарник, С. Гутман. Алгоритм квантової наближеної оптимізації повинен бачити весь графік: приклади найгіршого випадку. arXiv:2005.08747 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2005.08747
arXiv: 2005.08747
[27] Е. Фархі, Д. Гамарник, С. Гутман. Алгоритм квантової наближеної оптимізації потребує перегляду всього графіка: типовий випадок. arXiv:2004.09002 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2004.09002
arXiv: 2004.09002
[28] С. Бравий, А. Кліш, Р. Кеніг, Е. Танг. Перешкоди для варіаційної квантової оптимізації від захисту симетрії. Physical Review Letters 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
[29] С. Браві, Д. Госсет і Р. Мовассаг. Класичні алгоритми для квантових середніх значень. Nature Physics 17, 337–341 (2021).
https://doi.org/10.1038/s41567-020-01109-8
[30] С. Бравий, А. Кліш, Р. Кеніг, Е. Танг. Гібридні квантово-класичні алгоритми наближеного розфарбовування графів. Квант 6, 678 (2022).
https://doi.org/10.22331/q-2022-03-30-678
[31] Л. Елдар і А. В. Харроу. Локальні гамільтоніани, основні стани яких важко апроксимувати. У 2017 році IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 427–438 (2017).
https:///doi.org/10.1109/FOCS.2017.46
[32] Л. Т. Брейді, К. Л. Болдуін, А. Бапат, Ю. Харьков, А. В. Горшков. Оптимальні протоколи в задачах квантового відпалу та алгоритму квантової наближеної оптимізації. Physical Review Letters 126, 070505 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.070505
[33] Л. Т. Брейді, Л. Кочіа, П. Бієніас, А. Бапат, Ю. Харьков, А. В. Горшков. Поведінка аналогових квантових алгоритмів. arXiv:2107.01218 [quant-ph] (2021).
https:///doi.org/10.48550/arXiv.2107.01218
arXiv: 2107.01218
[34] LC Venuti, D. D'Alessandro та DA Lidar. Оптимальний контроль для квантової оптимізації закритих і відкритих систем. Physical Review Applied 16, 054023 (2021).
https: / / doi.org/ 10.1103 / PhysRevApplied.16.054023
[35] AM Чайлдс, Y. Su, MC Tran, N. Wiebe та S. Zhu. Теорія помилки Троттера з комутаторним масштабуванням. Physical Review X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020
[36] Б. Нахтергаеле, Ю. Огата, Р. Сімс. Розповсюдження кореляцій у системах квантових граток. Журнал статистичної фізики 124, 1–13 (2006).
https://doi.org/10.1007/s10955-006-9143-6
[37] Б. Нахтергале та Р. Сімс. Межі Ліба-Робінсона в квантовій фізиці багатьох тіл. Сучасна математика 529, 141–176 (2010).
https:///doi.org/10.1090/conm/529/10429
[38] S. Bravyi, MB Hastings і F. Verstraete. Межі Ліба-Робінсона та генерація кореляцій та топологічний квантовий порядок. Physical Review Letters 97, 050401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.050401
[39] К.-Ф. Чен і А. Лукас. Границі зростання оператора з теорії графів. Повідомлення в математичній фізиці 385, сторінки 1273–1323 (2021).
https://doi.org/10.1007/s00220-021-04151-6
[40] Е. Х. Ліб і Д. У. Робінсон. Скінченна групова швидкість квантових спінових систем. Повідомлення в математичній фізиці 28, 251–257 (1972).
https: / / doi.org/ 10.1007 / BF01645779
[41] J. Haah, MB Hastings, R. Kothari та GH Low. Квантовий алгоритм для моделювання еволюції гамільтоніанів решітки в реальному часі. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 350–360 (2018).
https:///doi.org/10.1109/FOCS.2018.00041
[42] А. Любоцький, Р. Філіпс, П. Сарнак. Графіки Рамануджана. Combinatorica 8, 261–277 (1988).
https: / / doi.org/ 10.1007 / BF02126799
[43] Б. Мохар. Ізопериметричні числа графів. Журнал комбінаторної теорії, серія B 47, 274–291 (1989).
https://doi.org/10.1016/0095-8956(89)90029-4
[44] AW Marcus, DA Spielman і N. Srivastava. Переплетення сімейств IV: дводольні графи Рамануджана всіх розмірів. У 2015 році IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), 1358–1377 (2015).
https:///doi.org/10.1109/FOCS.2015.87
[45] AW Marcus, DA Spielman і N. Srivastava. Переплетення сімейств IV: дводольні графи Рамануджана всіх розмірів. SIAM Journal on Computing 47, 2488–2509 (2018).
https:///doi.org/10.1137/16M106176X
[46] C. Hall, D. Puder і WF Sawin. Рамануджанські покриття графів. Досягнення математики 323, 367–410 (2018).
https:///doi.org/10.1016/j.aim.2017.10.042
[47] MX Goemans і DP Williamson. Удосконалені алгоритми апроксимації для задач максимального розрізу та виконання з використанням напіввизначеного програмування. Журнал ACM 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684
[48] RD Somma, D. Nagaj і M. Kieferová. Квантове прискорення шляхом квантового відпалу. Physical Review Letters 109, 050501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.050501
[49] М. Б. Гастінгс. Потужність адіабатичного квантового обчислення без проблеми знака. Квант 5, 597 (2021).
https://doi.org/10.22331/q-2021-12-06-597
[50] A. Gilyén, MB Hastings, and U. Vazirani. (Суб)Експоненціальна перевага адіабатичного квантового обчислення без проблеми зі знаком. У матеріалах щорічного симпозіуму ACM з теорії обчислень (STOC), 1357–1369 (2021).
https: / / doi.org/ 10.1145 / 3406325.3451060
[51] Р. Бхатія. Матричний аналіз. Дипломні тексти з математики. Springer New York (1996).
https://doi.org/10.1007/978-1-4612-0653-8
[52] Р. Бхатія. Позитивно визначені матриці. Princeton University Press, (2007).
https: / / doi.org/ 10.1515 / 9781400827787
[53] BD McKay, NC Wormald та B. Wysocka. Короткі цикли у випадкових регулярних графах. Електронний журнал комбінаторики 11, 1–12 (2004).
https: / / doi.org/ 10.37236 / 1819
[54] Ф. Кардош, Д. Краль, Я. Волец. Максимальні кромки в кубічних графах з великим обхватом і у випадкових кубічних графах. Випадкові структури та алгоритми 41, 506–520 (2012).
https:///doi.org/10.1002/rsa.20471
[55] Д. Коперсміт, Д. Гамарник, М. Т. Гаджиагаї, Г. Б. Соркін. Випадковий MAX SAT, випадковий MAX CUT та їхні фазові переходи. Випадкові структури та алгоритми 24, 502–545 (2004).
https:///doi.org/10.1002/rsa.20015
[56] А. Дембо, А. Монтанарі та С. Сен. Екстремальні розрізи розріджених випадкових графів. Annals of Probability 45, 1190–1217 (2017).
https:///doi.org/10.1214/15-AOP1084
Цитується
[1] Джакомо Де Пальма, Мілад Марвіан, Камбіз Рузе та Деніел Стілк Франца, «Обмеження варіаційних квантових алгоритмів: квантовий оптимальний транспортний підхід», arXiv: 2204.03455.
Вищезазначені цитати від SAO / NASA ADS (останнє оновлення успішно 2022-07-19 03:10:09). Список може бути неповним, оскільки не всі видавці надають відповідні та повні дані про цитування.
On Служба, на яку посилається Crossref даних про цитування робіт не знайдено (остання спроба 2022-07-19 03:10:07).
Ця стаття опублікована в Quantum під Creative Commons Attribution 4.0 International (CC на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.
