Улучшенный алгоритм аппроксимации квантового максимального разреза на графах без треугольников

Улучшенный алгоритм аппроксимации квантового максимального разреза на графах без треугольников

Отметка времени: 9 ноября 2023 г., 6:44

Робби Кинг

Департамент вычислительной техники и математических наук Калифорнийского технологического института

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

Абстрактные

Мы даем аппроксимационный алгоритм для Quantum Max-Cut, который работает путем округления релаксации SDP до запутанного квантового состояния. SDP используется для выбора параметров вариационной квантовой схемы. Запутанное состояние тогда представляется как квантовая схема, примененная к состоянию-продукту. На графиках без треугольников достигается коэффициент аппроксимации 0.582. Предыдущие лучшие алгоритмы Аншу, Госсета, Моренца и Пареха и Томпсона достигли коэффициентов аппроксимации 0.531 и 0.533 соответственно. Кроме того, мы изучаем гамильтониан ЭПР, который, по нашему мнению, является естественной промежуточной проблемой, изолирующей некоторые ключевые квантовые особенности локальных гамильтоновых задач. Для гамильтониана ЭПР дан алгоритм аппроксимации с коэффициентом аппроксимации $1/sqrt{2}$ на всех графах.

Улучшенный алгоритм аппроксимации квантового максимального разреза на графах без треугольников. PlatoBlockchain Data Intelligence. Вертикальный поиск. Ай.

Рекомендованное изображение: Локальная окрестность ребра в графе без треугольников.

[Встраиваемое содержимое]

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

Как мы можем округлить релаксацию SDP до запутанного квантового состояния? И как нам оптимизировать вариационный анзац схемы? В данной работе мы решаем эти две задачи, объединяя их: Используем решение SDP для выбора параметров вариационной схемы.

► Данные BibTeX

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

[1] Анураг Аншу, Дэвид Госсет и Карен Моренц. За пределами аппроксимации состояния продукта для квантового аналога максимального разреза. На 15-й конференции по теории квантовых вычислений, связи и криптографии, 2020 г. https://doi.org/10.4230/LIPIcs.TQC.2020.7.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.7

[2] Анураг Аншу, Дэвид Госсет, Карен Моренц и Мехди Сулейманифар. Улучшенные алгоритмы аппроксимации локальных гамильтонианов ограниченной степени. Physical Review Letters, 127(25):250502, 2021. https://doi.org/10.1103/PhysRevLett.127.250502.
https: / / doi.org/ 10.1103 / PhysRevLett.127.250502

[3] Жоп Бриэ, Фернандо Марио де Оливейра Фильо и Фрэнк Валлентин. Неравенства Гротендика для полуопределенных программ с ограничением ранга. Theory OF Computing, 10(4):77–105, 2014. https://doi.org/10.4086/toc.2014.v010a004.
https: / / doi.org/ 10.4086 / toc.2014.v010a004

[4] Сергей Бравый, Дэвид Госсет, Роберт Кениг и Кристан Темме. Алгоритмы аппроксимации квантовых задач многих тел. Журнал математической физики, 60(3):032203, 2019. https://doi.org/10.1063/1.5085428.
https: / / doi.org/ 10.1063 / 1.5085428

[5] Фернандо ГСЛ Брандао и Арам В. Харроу. Приближения состояний-продуктов к квантовым состояниям. Коммуникации в математической физике, 342:47–80, 2016. https://doi.org/10.1007/s00220-016-2575-1.
https:/​/​doi.org/​10.1007/​s00220-016-2575-1

[6] Тоби Кабитт и Эшли Монтанаро. Классификация сложности локальных гамильтоновых задач. SIAM Journal on Computing, 45(2):268–316, 2016. https://doi.org/10.1137/140998287.
https: / / doi.org/ 10.1137 / 140998287

[7] Уриэль Файги и Гидеон Шехтман. Об оптимальности метода случайного округления гиперплоскости для максимального разреза. Случайные структуры и алгоритмы, 20(3):403–440, 2002. https://doi.org/10.1002/rsa.10036.
https: / / doi.org/ 10.1002 / rsa.10036

[8] Севаг Гарибян и Юлия Кемпе. Алгоритмы аппроксимации qma-полных задач. SIAM Journal on Computing, 41(4):1028–1050, 2012. https://doi.org/10.1137/110842272.
https: / / doi.org/ 10.1137 / 110842272

[9] Севаг Гарибян и Оджас Парех. Почти оптимальные классические аппроксимационные алгоритмы для квантового обобщения max-cut. В аппроксимации, рандомизации и комбинаторной оптимизации. Алгоритмы и методы (ПРИБЛИЗИТЕЛЬНО/СЛУЧАЙНО, 2019 г.). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. https://​/​doi.org/​10.4230/​LIPIcs.APPROX-RANDOM.2019.31.
https: / / doi.org/ 10.4230 / LIPIcs.APPROX-RANDOM.2019.31

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

[11] Йохан Хостад. Некоторые оптимальные результаты о неаппроксимируемости. Журнал ACM (JACM), 48(4):798–859, 2001. https://doi.org/10.1145/502090.502098.
https: / / doi.org/ 10.1145 / 502090.502098

[12] Ёну Хван, Джо Ниман, Оджас Парех, Кевин Томпсон и Джон Райт. Уникальные игры, сложность квантового максимального разреза и предполагаемое векторное неравенство Борелла. В материалах ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2023 г., страницы 1319–1384. СИАМ, 2023. https://doi.org/10.1137/1.9781611977554.ch48.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch48

[13] Субхаш Хот, Гай Киндлер, Эльчанан Моссел и Райан О'Доннелл. Оптимальные результаты неаппроксимируемости для max-cut и других csps с двумя переменными? SIAM Journal on Computing, 2(37):1–319, 357. https://doi.org/2007/S10.1137.
https: / / doi.org/ 10.1137 / S0097539705447372

[14] Юну Ли. Оптимизация параметров квантовой схемы через SDP. На 33-м Международном симпозиуме по алгоритмам и вычислениям (ISAAC 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. https://​/​doi.org/​10.4230/​LIPIcs.ISAAC.2022.48.
https: / / doi.org/ 10.4230 / LIPIcs.ISAAC.2022.48

[15] Стивен Пиддок и Эшли Монтанаро. Сложность антиферромагнитных взаимодействий и 2d-решеток. Quantum Information & Computation, 17(7-8):636–672, 2017. https://dl.acm.org/doi/abs/10.5555/3179553.3179559.
https: / / dl.acm.org/ дои / ABS / 10.5555 / 3179553.3179559

[16] Оджас Парех и Кевин Томпсон. Применение квантовой иерархии Лассера второго уровня в алгоритмах квантовой аппроксимации. На 2-м Международном коллоквиуме по автоматам, языкам и программированию (ICALP 48). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. https://​/​doi.org/​2021/​LIPIcs.ICALP.10.4230.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.102

[17] Оджас Парех и Кевин Томпсон. Избиение случайного назначения для аппроксимации квантовых 2-локальных гамильтоновых задач. На 29-м ежегодном европейском симпозиуме по алгоритмам (ESA 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.ESA.2021.74.
https: / / doi.org/ 10.4230 / LIPIcs.ESA.2021.74

[18] Оджас Парех и Кевин Томпсон. Оптимальное приближение состояния продукта для 2-локальных квантовых гамильтонианов с положительными членами. Препринт arXiv arXiv:2206.08342, 2022. https://doi.org/10.48550/arXiv.2206.08342.
https://​/​doi.org/​10.48550/​arXiv.2206.08342
Arxiv: 2206.08342

Цитируется

[1] Николас П.Д. Савая, Дэниел Марти-Дафчик, Ян Хо, Дэниел П. Табор, Дэвид Бернал, Алисия Б. Маганн, Шавиндра Премаратне, Прадип Дубей, Энн Мацуура, Натан Бишоп, Вибе А де Йонг, Саймон Бенджамин, Оджас Д. Парех, Норм Табман, Кэтрин Климко и Даан Кэмпс, «HamLib: библиотека гамильтонианов для сравнительного анализа квантовых алгоритмов и оборудования», Arxiv: 2306.13126, (2023).

[2] Дмитрий Гринько и Марис Озолс, «Линейное программирование с унитарно-эквивариантными ограничениями», Arxiv: 2207.05713, (2022).

[3] Чарли Карлсон, Закари Хоркера, Александра Колла, Стивен Кордонови и Стюарт Уэйланд, «Алгоритмы аппроксимации для Quantum Max-$d$-Cut», Arxiv: 2309.10957, (2023).

[4] Адам Бене Уоттс, Анирбан Чоудхури, Эйдан Эпперли, Дж. Уильям Хелтон и Игорь Клеп, «Релаксации и точные решения для разрезания квантового максимума с помощью алгебраической структуры операторов перестановки», Arxiv: 2307.15661, (2023).

[5] Эндрю Чжао и Николас Рубин, «Расширение возможностей квантовой оптимизации с помощью фермионных вложений», Arxiv: 2301.01778, (2023).

[6] Стивен Хейлман, «Сферная шумовая стабильность и квантовая твердость MAX-CUT», Arxiv: 2306.03912, (2023).

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

Не удалось получить Перекрестная ссылка на данные во время последней попытки 2023-11-09 11:49:08: Не удалось получить цитируемые данные для 10.22331 / q-2023-11-09-1180 от Crossref. Это нормально, если DOI был зарегистрирован недавно.

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

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

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