QuOne Lab, Центр исследований и инноваций Phanous, Тегеран, Иран
Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.
Абстрактные
Ожидается, что эволюции локальных гамильтонианов за короткое время останутся локальными и, следовательно, ограниченными. В этой статье мы подтверждаем эту интуицию, доказывая некоторые ограничения на кратковременную эволюцию локальных гамильтонианов, зависящих от времени. Показано, что распределение результатов измерения кратковременных (не более логарифмических) эволюций локальных гамильтонианов является $концентрированным$ и удовлетворяет $textit{изопериметрическому неравенству}$. Чтобы продемонстрировать явное применение наших результатов, мы изучили задачу $M$$small{AX}$$C$$small{UT}$ и пришли к выводу, что для квантового отжига требуется по крайней мере время выполнения, которое логарифмически масштабируется по размеру задачи, чтобы превзойти классические алгоритмы на $M$$small{AX}$$C$$small{UT}$. Чтобы подтвердить наши результаты, мы также доказываем границу Либа-Робинсона, которая работает для зависящих от времени гамильтонианов, которые могут представлять самостоятельный интерес.
Рекомендуемое изображение: На этой иллюстрации показано распределение вероятностей веса Хэмминга трех различных состояний $n$-кубитов при $n=100$. Центральное распределение в середине (синее) — это типичное распределение для начального состояния продукта (например, $|+rangle^{otimes n}$). Распределение с пиком справа (оранжевое) представляет собой распределение после кратковременной эволюции начального состояния, описанного в теореме 2 рукописи. Распределение, которое имеет два пика по обе стороны спектра (зеленый цвет), является приближением для состояния GHZ. Это показывает, что GHZ-состояние не может быть создано даже приблизительно кратковременным квантовым отжигом.
Популярное резюме
► Данные BibTeX
► Рекомендации
[1] Т. Кадоваки и Х. Нисимори. Квантовый отжиг в поперечной модели Изинга. Physical Review E 58, 5355–5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355
[2] Э. Фархи, Дж. Голдстоун, С. Гутманн и М. Сипсер. Квантовые вычисления с помощью адиабатической эволюции. arXiv: 0001106 [квант-ф] (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 де адиабатенсатс. 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] С. Пури, К. К. Андерсен, А. Л. Гримсмо и А. Блейс. Квантовый отжиг с полностью связанными нелинейными генераторами. Сообщения о природе 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-г
[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] Л. Стелла, Г. Э. Санторо и Э. Тосатти. Оптимизация квантовым отжигом: уроки простых случаев. Физический обзор 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] А. Мотт, Дж. Джоб, Дж.-Р. Влимант, Д. Лидар и М. Спиропулу. Решение задачи оптимизации Хиггса с квантовым отжигом для машинного обучения. Природа 550, 375–379 (2017).
https: / / doi.org/ 10.1038 / nature24047
[14] К. Л. Пуденц, Т. Альбаш и Д. А. Лидар. Квантовая поправка отжига для случайных задач Изинга. Физический обзор A 91, 042302 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.042302
[15] А. Пердомо-Ортис, Н. Диксон, М. Дрю-Брук, Г. Роуз и А. Аспуру-Гузик. Нахождение низкоэнергетических конформаций моделей решетчатых белков с помощью квантового отжига. Научные отчеты 2, 571 (2012).
https: / / doi.org/ 10.1038 / srep00571
[16] К. Л. Пуденц, Т. Альбаш и Д. А. Лидар. Квантовый отжиг с коррекцией ошибок с сотнями кубитов. Связи с природой 5, 1–10 (2014).
https: / / doi.org/ 10.1038 / ncomms4243
[17] Р. Мартонак, Г. Э. Санторо и Э. Тосатти. Квантовый отжиг задачи коммивояжера. Физический обзор E 70, 057701 (2004).
https: / / doi.org/ 10.1103 / PhysRevE.70.057701
[18] С.Х. Адачи и М.П. Хендерсон. Применение квантового отжига для обучения глубоких нейронных сетей. arXiv: 1510.06356 [квант-ф] (2015).
https:///doi.org/10.48550/arXiv.1510.06356
Arxiv: 1510.06356
[19] М. В. Джонсон и др. Квантовый отжиг с искусственными спинами. Природа 473, 194–198 (2011).
https: / / doi.org/ 10.1038 / nature10012
[20] С. Бойшо, Т. Альбаш, Ф. М. Спедальери, Н. Чанселлор, Д. А. Лидар. Экспериментальная подпись программируемого квантового отжига. Связи с природой 4, 1–8 (2013).
https: / / doi.org/ 10.1038 / ncomms3067
[21] А. Д. Кинг и др. Когерентный квантовый отжиг в программируемой цепочке Изинга на 2000 кубитов. arXiv: 2202.05847 [квант-ф] (2022).
https:///doi.org/10.48550/arXiv.2202.05847
Arxiv: 2202.05847
[22] Б. Фоксен и др. Демонстрация непрерывного набора двухкубитных вентилей для краткосрочных квантовых алгоритмов. Письма о физическом обзоре 125, 120504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.120504
[23] К. Райт и др. Тестирование квантового компьютера с 11 кубитами. Связи с природой 10, 1–6 (2019).
https://doi.org/10.1038/s41467-019-13534-2
[24] Э. Дж. Кроссон и Д. А. Лидар. Перспективы квантового усиления с помощью диабатического квантового отжига. Nature Reviews Physics 3, 466–489 (2021).
https://doi.org/10.1038/s42254-021-00313-6
[25] Э. Фархи, Дж. Голдстоун и С. Гутманн. Алгоритм квантовой приближенной оптимизации. arXiv: 1411.4028 [квант-ф] (2014).
https:///doi.org/10.48550/arXiv.1411.4028
Arxiv: 1411.4028
[26] Э. Фархи, Д. Гамарник и С. Гутманн. Алгоритм квантовой приближенной оптимизации должен видеть весь график: примеры наихудшего случая. arXiv: 2005.08747 [квант-ф] (2020).
https:///doi.org/10.48550/arXiv.2005.08747
Arxiv: 2005.08747
[27] Э. Фархи, Д. Гамарник и С. Гутманн. Алгоритм квантовой приближенной оптимизации должен видеть весь график: типичный случай. arXiv: 2004.09002 [квант-ф] (2020).
https:///doi.org/10.48550/arXiv.2004.09002
Arxiv: 2004.09002
[28] С. Бравый, А. Клиш, Р. Кениг, Э. Танг. Препятствия для вариационной квантовой оптимизации из-за защиты симметрии. Письма о физическом обзоре 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
[29] С. Брави, Д. Госсет и Р. Мовасса. Классические алгоритмы для квантовых средних значений. Физика природы 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 г. состоялся 58-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS), 427–438 (2017 г.).
https: / / doi.org/ 10.1109 / FOCS.2017.46
[32] Брейди Л.Т., Болдуин Ч.Л., Бапат А., Харьков Ю., Горшков А.В. Оптимальные протоколы в задачах алгоритмов квантового отжига и квантовой приближенной оптимизации. Письма о физическом обзоре 126, 070505 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.070505
[33] Брейди Л.Т., Косиа Л., Биниас П., Бапат А., Харьков Ю., Горшков А.В. Поведение аналоговых квантовых алгоритмов. arXiv: 2107.01218 [квант-ф] (2021).
https:///doi.org/10.48550/arXiv.2107.01218
Arxiv: 2107.01218
[34] Л. С. Венути, Д. Д'Алессандро и Д. А. Лидар. Оптимальное управление для квантовой оптимизации закрытых и открытых систем. Physical Review Applied 16, 054023 (2021).
https: / / doi.org/ 10.1103 / PhysRevApplied.16.054023
[35] А. М. Чайлдс, Ю. Су, М. С. Тран, Н. Вибе и С. Чжу. Теория ошибки Троттера с масштабированием коммутатора. Физический обзор 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] С. Брави, М.Б. Гастингс и Ф. Верстрате. Границы Либ-Робинсона, генерация корреляций и топологический квантовый порядок. Письма о физическом обзоре 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] Дж. Хаах, М. Б. Гастингс, Р. Котари и Г. Х. Лоу. Квантовый алгоритм для моделирования эволюции решёточных гамильтонианов в реальном времени. 2018-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS), 59 г., 350–360 (2018 г.).
https: / / doi.org/ 10.1109 / FOCS.2018.00041
[42] А. Любоцкий, Р. Филлипс и П. Сарнак. Графики Рамануджана. Комбинаторика 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] А. В. Маркус, Д. А. Спилман и Н. Шривастава. Переплетающиеся семейства IV: двудольные графы Рамануджана всех размеров. В 2015 г. состоялся 56-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS), 1358–1377 (2015 г.).
https: / / doi.org/ 10.1109 / FOCS.2015.87
[45] А. В. Маркус, Д. А. Спилман и Н. Шривастава. Переплетающиеся семейства IV: двудольные графы Рамануджана всех размеров. SIAM Journal on Computing 47, 2488–2509 (2018).
https: / / doi.org/ 10.1137 / 16M106176X
[46] К. Холл, Д. Пудер и В. Ф. Савин. Покрытия Рамануджана графов. Успехи в математике 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] Р. Д. Сомма, Д. Нагай и М. Киферова. Квантовое ускорение с помощью квантового отжига. Письма о физическом обзоре 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] А. Гильен, М.Б. Гастингс и У. Вазирани. (Суб)экспоненциальное преимущество адиабатических квантовых вычислений без проблем со знаками. В материалах ежегодного симпозиума ACM по теории вычислений (STOC), 1357–1369 (2021 г.).
https: / / doi.org/ 10.1145 / 3406325.3451060
[51] Р. Бхатия. Матричный анализ. Тексты для выпускников по математике. Спрингер Нью-Йорк (1996).
https://doi.org/10.1007/978-1-4612-0653-8
[52] Р. Бхатия. Положительно определенные матрицы. Издательство Принстонского университета, (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] А. Дембо, А. Монтанари, С. Сен. Экстремальные разрезы разреженных случайных графов. Анналы вероятности 45, 1190–1217 (2017).
https: / / doi.org/ 10.1214 / 15-AOP1084
Цитируется
[1] Джакомо Де Пальма, Милад Марвиан, Камбис Рузе и Даниэль Стилк Франса, «Ограничения вариационных квантовых алгоритмов: квантовый подход к оптимальной транспортировке», Arxiv: 2204.03455.
Приведенные цитаты из САО / НАСА ADS (последнее обновление успешно 2022-07-19 03:10:09). Список может быть неполным, поскольку не все издатели предоставляют подходящие и полные данные о цитировании.
On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2022-07-19 03:10:07).
Эта статья опубликована в Quantum под Creative Commons Attribution 4.0 International (CC BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.
