Логотип Зефирнет

Квантовые SDP-решатели: лучшие верхние и нижние границы

Дата:


Джоран ван Апелдорн1,2Андраш Гильен1,2Сандер Гриблинг1,2и Рональд де Вольф1,2,3

1QuSoft, Амстердам, Нидерланды.
2Университет Амстердама, Нидерланды.
3Университет Амстердама, Нидерланды.

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

Абстрактные

Брандао и Своре [14] недавно дал квантовые алгоритмы приближенного решения полуопределенных программ, которые в некоторых режимах быстрее наилучших из возможных классических алгоритмов по размерности $n$ задачи и количеству $m$ ограничений, но хуже по различным другие параметры. В этой статье мы улучшаем их алгоритмы несколькими способами, улучшая зависимость от этих других параметров. С этой целью мы разрабатываем новые методы для квантовых алгоритмов, например, общий способ эффективной реализации гладких функций разреженных гамильтонианов и обобщенную процедуру поиска минимума.

Мы также показываем ограничения этого подхода для квантовых SDP-решателей, например, для задач комбинаторной оптимизации, которые имеют большую симметрию. Наконец, мы доказываем некоторые общие нижние оценки, показывающие, что в худшем случае сложность каждого квантового LP-решателя (и, следовательно, также SDP-решателя) должна масштабироваться линейно с $mn$, когда $m приблизительно n$, что совпадает с классический.

Полуопределенные программы (SDP) являются важным инструментом в задачах выпуклой оптимизации и алгоритмах аппроксимации. Они позволяют оптимизировать линейную функцию над положительно полуопределенными матрицами при линейных ограничениях на эти матрицы, и они решаются за полиномиальное время на классическом компьютере. Брандао и Своре недавно предложили квантовый алгоритм для решения полуопределенных программ, который (в некоторых режимах) работает быстрее, чем лучший из возможных классический алгоритм. В этой статье мы улучшаем их алгоритм несколькими способами, в частности, мы получаем 4-е корень улучшения времени выполнения по отношению к требуемой точности. Мы также показываем сильные ограничения для этого конкретного подхода к квантовым SDP-решателям, например, для задач комбинаторной оптимизации, которые имеют большую симметрию, и мы доказываем некоторые общие ограничения для квантовых SDP-решателей.

► Данные BibTeX

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

[1] Санджив Арора, Элад Хазан и Сатьен Кале. Метод обновления мультипликативных весов: метаалгоритм и приложения. ток, 8(6):121–164, 2012.
https: / / doi.org/ 10.4086 / toc.2012.v008a006

[2] Санджив Арора и Сатьен Кале. Комбинаторный, прямо-двойственный подход к полуопределенным программам. jacm, 63(2):12:1–12:35, 2016. Более ранняя версия в STOC'07.
https: / / doi.org/ 10.1145 / 2837020

[3] Андрис Амбаинис. Алгоритм квантового блуждания для четкости элементов. siamjc, 37(1):210–239, 2007. Более ранняя версия в FOCS'04. arXiv: quant-ph/​0311001?.
https: / / doi.org/ 10.1137 / S0097539705447311
Arxiv: колич-фот / 0311001

[4] Йоран ван Апелдорн и Андраш Гильен. Улучшения в квантовом решении SDP с приложениями. В icalp46th, страницы 99:1–99:15, 2019 г. arXiv: 1804.05058?.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.99
Arxiv: 1804.05058

[5] Йоран ван Апелдорн и Андраш Гильен. Квантовые алгоритмы для игр с нулевой суммой. arXiv: 1904.03180?, 2019.
Arxiv: 1904.03180

[6] Йоран ван Апелдорн, Андраш Гильен, Сандер Гриблинг и Рональд де Вольф. Квантовые SDP-решатели: лучшие верхние и нижние границы. В focs58th, страницы 403–414, 2017. arXiv: 1705.01843?.
https: / / doi.org/ 10.1109 / FOCS.2017.44
Arxiv: 1705.01843

[7] Йоран ван Апелдорн, Андраш Гильен, Сандер Гриблинг и Рональд де Вольф. Выпуклая оптимизация с использованием квантовых оракулов. квант, 4:220, 2020. arXiv: 1809.00643?.
https:/​/​doi.org/​10.22331/​q-2020-01-13-220
Arxiv: 1809.00643

[8] Нога Алон и Джоэл Х. Спенсер. Вероятностный метод. Wiley-Interscience, третье издание, 2008 г.
https: / / doi.org/ 10.1002 / 0471722154

[9] Мишель Буайе, Жиль Брассар, Петер Хойер и Ален Тэпп. Жесткие ограничения на квантовый поиск. Fortschritte der Physik, 46(4–5):493–505, 1998. arXiv: quant-ph/​9605034?.
Arxiv: колич-фот / 9605034

[10] Доминик В. Берри, Эндрю М. Чайлдс, Ричард Клив, Робин Котари и Роландо Д. Сомма. Моделирование гамильтоновой динамики с помощью усеченного ряда Тейлора. prl, 114(9):090502, 2015. arXiv: 1412.4687?.
https: / / doi.org/ 10.1103 / PhysRevLett.114.090502
Arxiv: 1412.4687

[11] Доминик В. Берри, Эндрю М. Чайлдс и Робин Котари. Гамильтоновое моделирование с почти оптимальной зависимостью от всех параметров. В focs56th, страницы 792–809, 2015. arXiv: 1501.01715?.
https: / / doi.org/ 10.1109 / FOCS.2015.54
Arxiv: 1501.01715

[12] Жиль Брассар, Питер Хойер, Мишель Моска и Ален Тэпп. Квантовое усиление и оценка амплитуды. В «Квантовые вычисления и квантовая информация: том тысячелетия», том 305 из серии «Современная математика», страницы 53–74. AMS, 2002. arXiv: quant-ph/​0005055?.
HTTPS: / / doi.org/ 10.1090 / conm / 305/05215
Arxiv: колич-фот / 0005055

[13] Фернандо ГСЛ Брандао, Амир Калев, Тонъян Ли, Седрик Йен-Ю Линь, Криста М. Своре и Сяоди Ву. Квантовые решатели SDP: значительное ускорение, оптимальность и приложения для квантового обучения. В icalp46th, страницы 27:1–27:14, 2019 г. arXiv: 1710.02581?.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.27
Arxiv: 1710.02581

[14] Фернандо ГСЛ Брандао и Криста М. Своре. Квантовые ускорения для решения полуопределенных программ. В focs58th, страницы 415–426, 2017. arXiv: 1609.05537?.
https: / / doi.org/ 10.1109 / FOCS.2017.45
Arxiv: 1609.05537

[15] Шуваник Чакрабарти, Эндрю М. Чайлдс, Тонъян Ли и Сяоди Ву. Квантовые алгоритмы и нижние оценки для выпуклой оптимизации. квант, 4:221, 2020. arXiv: 1809.01731?.
https:/​/​doi.org/​10.22331/​q-2020-01-13-221
Arxiv: 1809.01731

[16] Ричард Клив, Артур Экерт, Кьяра Маккиавелло и Микеле Моска. Новый взгляд на квантовые алгоритмы. rspa, 454(1969):339–354, 1998. arXiv: quant-ph/​9708016?.
https: / / doi.org/ 10.1098 / rspa.1998.0164
Arxiv: колич-фот / 9708016

[17] Эндрю М. Чайлдс, Робин Котари и Роландо Д. Сомма. Квантовый алгоритм для систем линейных уравнений с экспоненциально улучшающейся зависимостью от точности. siamjc, 46(6):1920–1950, 2017. arXiv: 1511.02306?.
https: / / doi.org/ 10.1137 / 16M1087072
Arxiv: 1511.02306

[18] Анирбан Нараян Чоудхури и Роландо Д. Сомма. Квантовые алгоритмы выборки Гиббса и оценки времени попадания. qic, 17(1&2):41–64, 2017. arXiv: 1603.02940?.
https: / / doi.org/ 10.26421 / QIC17.1-2
Arxiv: 1603.02940

[19] Эндрю М. Чайлдс и Натан Виб. Гамильтоново моделирование с использованием линейных комбинаций унитарных операций. qic, 12(11&12):901–924, 2012. arXiv: 1202.5822?.
https: / / doi.org/ 10.26421 / QIC12.11-12
Arxiv: 1202.5822

[20] Джордж Б. Данциг. Максимизация линейной функции переменных с учетом линейных неравенств. В Анализе деятельности по производству и распределению, Монография Комиссии Коулза № 13, стр. 339.
–347. John Wiley & Sons Inc., Нью-Йорк, 1951 г.

[21] Кристоф Дюрр и Петер Хойер. Квантовый алгоритм поиска минимума. arXiv: quant-ph/​9607014?, 1996.
Arxiv: колич-фот / 9607014

[22] Кристоф Дюрр, Марк Хейлигман, Петер Хойер и Мехди Мхалла. Квантовая сложность запросов некоторых графовых задач. siamjc, 35(6):1310–1328, 2006. Более ранняя версия в ICALP'04. arXiv: квант-тел/​0401091?.
https: / / doi.org/ 10.1137 / 050644719
Arxiv: колич-фот / 0401091

[23] Мартин Гротшель, Ласло Ловаш и Александр Шрайвер. Метод эллипсоидов и его последствия в комбинаторной оптимизации. гребень, 1 (2): 169–197, 1981.
https: / / doi.org/ 10.1007 / BF02579273

[24] Мартин Грёчел, Ласло Ловаш и Александр Шрайвер. Геометрические алгоритмы и комбинаторная оптимизация. Springer, 1988.

[25] Лов Гровер и Терри Рудольф. Создание суперпозиций, соответствующих эффективно интегрируемым распределениям вероятностей. arXiv: quant-ph/​0208112?, 2002.
Arxiv: колич-фот / 0208112

[26] Лов К. Гровер. Быстрый квантово-механический алгоритм поиска в базе данных. In stoc28th, страницы 212–219, 1996. arXiv: quant-ph/​9605043?.
https: / / doi.org/ 10.1145 / 237814.237866
Arxiv: колич-фот / 9605043

[27] Андраш Гильен, Юань Су, Гуан Хао Лоу и Натан Вибе. Квантовое преобразование сингулярных значений и не только: экспоненциальные улучшения квантовой матричной арифметики. In stoc51st, страницы 193–204, 2019 г. arXiv: 1806.01838?.
https: / / doi.org/ 10.1145 / 3313276.3316366
Arxiv: 1806.01838

[28] Мишель X. Гоэманс и Дэвид П. Уильямсон. Улучшенные алгоритмы аппроксимации для задач максимального сечения и выполнимости с использованием полуопределенного программирования. jacm, 42(6):1115–1145, 1995. Более ранняя версия в STOC'94.
https: / / doi.org/ 10.1145 / 227683.227684

[29] Арам В. Харроу, Авинатан Хасидим и Сет Ллойд. Квантовый алгоритм для линейных систем уравнений. prl, 103(15):150502, 2009. arXiv: 0811.3171?.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
Arxiv: 0811.3171

[30] Шелби Киммел. Квантовый противник (верхняя) граница. cjtcs, 2013:4:1–14, 2013. Более ранняя версия в ICALP'12. arXiv: 1101.0797?.
https: / / doi.org/ 10.4086 / cjtcs.2013.004
Arxiv: 1101.0797

[31] Субхаш Хот, Гай Киндлер, Эльханан Моссел и Райан О'Доннелл. Оптимальные результаты неаппроксимации для MAX-CUT и других CSP с двумя переменными? siamjc, 2(37):1–319, 357. Более ранняя версия в FOCS'2007.
https: / / doi.org/ 10.1137 / S0097539705447372

[32] Иорданис Керенидис и Анупам Пракаш. Квантовый метод внутренних точек для LP и SDP. arXiv: 1808.09266?, 2018.
Arxiv: 1808.09266

[33] Гуанг Хао Лоу и Исаак Л. Чуанг. Оптимальное моделирование гамильтониана с помощью квантовой обработки сигналов. prl, 118(1):010501, 2017. arXiv: 1606.02685?.
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501
Arxiv: 1606.02685

[34] Гуанг Хао Лоу и Исаак Л. Чуанг. Моделирование гамильтониана путем кубитизации. квант, 3:163, 2019. arXiv: 1610.06546?.
https:/​/​doi.org/​10.22331/​q-2019-07-12-163
Arxiv: 1610.06546

[35] Инь Тат Ли, Аарон Сидфорд и Сэм Чиу-вай Вонг. Более быстрый метод секущей плоскости и его значение для комбинаторной и выпуклой оптимизации. В focs56th, страницы 1049–1065, 2015 г. arXiv: 1508.04874?.
https: / / doi.org/ 10.1109 / FOCS.2015.68
Arxiv: 1508.04874

[36] Майкл А. Нильсен и Исаак Л. Чуанг. Квантовые вычисления и квантовая информация. Издательство Кембриджского университета, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667

[37] Ю. Нестеров и А. Немировский. Полиномиальные алгоритмы внутренней точки в выпуклом программировании, том 13 SIAM Studies in Applied Mathematics. Общество промышленной и прикладной математики (SIAM), 1994.
https: / / doi.org/ 10.1137 / 1.9781611970791

[38] Дэвид Пулин и Павел Вочан. Подготовка основных состояний квантовых систем многих тел на квантовом компьютере. prl, 102(13):130503, 2009. arXiv: 0809.2705?.
https: / / doi.org/ 10.1103 / PhysRevLett.102.130503
Arxiv: 0809.2705

[39] Дэвид Пулин и Павел Вочан. Выборка из теплового квантового состояния Гиббса и оценка статистической суммы с помощью квантового компьютера. prl, 103(22):220502, 2009. arXiv: 0905.2199?.
https: / / doi.org/ 10.1103 / PhysRevLett.103.220502
Arxiv: 0905.2199

[40] Джеймс Ренегар. «Эффективные» субградиентные методы для общей выпуклой оптимизации. siamjc, 26(4):2649–2676, 2016. arXiv: 1605.08712?.
https: / / doi.org/ 10.1137 / 15M1027371
Arxiv: 1605.08712

[41] Джеймс Ренегар. Ускоренные методы первого порядка для гиперболического программирования. Математическое программирование, 173(1):1–35, 2019. arXiv: 1512.07569?.
https: / / doi.org/ 10.1007 / s10107-017-1203-й
Arxiv: 1512.07569

[42] Александр Шрайвер. Теория линейного и целочисленного программирования. John Wiley & Sons, Inc., Нью-Йорк, США, 1986 г.

[43] Питер В. Шор. Полиномиальные алгоритмы простой факторизации и дискретного логарифмирования на квантовом компьютере. siamjc, 26(5):1484–1509, 1997. Более ранняя версия в FOCS'94. arXiv: quant-ph/​9508027?.
https: / / doi.org/ 10.1137 / S0097539795293172
Arxiv: колич-фот / 9508027

[44] Кодзи Цуда, Гуннар Ратч и Манфред К. Вармут. Обновления матричного экспоненциального градиента для онлайн-обучения и проекции Брегмана. Журнал исследований машинного обучения, 6: 995–1018, 2005 г. Более ранняя версия в NIPS'04.
http://​/​jmlr.csail.mit.edu/​papers/​volume6/​tsuda05a/​tsuda05a.pdf

[45] Манфред К. Вармут и Дима Кузьмин. Минимизация онлайн-дисперсии. Machine Learning, 87(1):1–32, 2012. Более ранняя версия в COLT'06.
https:/​/​doi.org/​10.1007/​s10994-011-5269-0

Цитируется

[1] Андраш Гильен, Юань Су, Гуан Хао Лоу и Натан Вибе, «Квантовое преобразование сингулярных значений и не только: экспоненциальные улучшения для квантовой матричной арифметики», Arxiv: 1806.01838.

[2] Карло Чилиберто, Марк Хербстер, Алессандро Давиде Ялонго, Массимилиано Понтил, Андреа Роккетто, Симоне Северини и Леонард Воссниг, «Квантовое машинное обучение: классический взгляд», Слушания Лондонского королевского общества, серия A 474 2209, 20170551 (2018).

[3] Патрик Ребентрост и Сет Ллойд, «Квантовые вычислительные финансы: квантовый алгоритм для оптимизации портфеля», Arxiv: 1811.03975.

[4] Джоран ван Апелдорн и Андраш Гильен, «Квантовые алгоритмы для игр с нулевой суммой», Arxiv: 1904.03180.

[5] Андрас Гильен, Шринивасан Аруначалам и Натан Вибе, «Оптимизация алгоритмов квантовой оптимизации с помощью более быстрого вычисления квантового градиента», Arxiv: 1711.00465.

[6] Патрик Ребентрост, Мария Шульд, Леонард Воссниг, Франческо Петруччионе и Сет Ллойд, «Квантовый градиентный спуск и метод Ньютона для полиномиальной оптимизации с ограничениями», Arxiv: 1612.01789.

[7] Фернандо Г.С.Л. Брандао, Амир Калев, Тонъянг Ли, Седрик Йен-Ю Лин, Криста М. Своре и Сяоди Ву, «Квантовые решатели SDP: большие ускорения, оптимальность и приложения к квантовому обучению», Arxiv: 1710.02581.

[8] Джоран ван Апелдорн и Андраш Гильен, «Улучшения в квантовом SDP-решении с приложениями», Arxiv: 1804.05058.

[9] Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin и Chunhao Wang, «Классический сублинейный алгоритм с квантовым временем для решения полуопределенного программирования низкого ранга с помощью методов выборки», Arxiv: 1901.03254.

[10] Саймон Аперс, «Выборка квантовых прогулок путем выращивания наборов семян», Arxiv: 1904.11446.

[11] Йоран ван Апелдорн, Андраш Гильен, Сандер Гриблинг и Рональд де Вольф, «Выпуклая оптимизация с использованием квантовых оракулов», Arxiv: 1809.00643.

[12] Шуваник Чакрабарти, Эндрю М. Чайлдс, Тонгьянг Ли и Сяоди Ву, «Квантовые алгоритмы и нижние оценки для выпуклой оптимизации», Arxiv: 1809.01731.

[13] Йимин Ге, Хорди Тура и Дж. Игнасио Чирак, «Быстрая подготовка основного состояния и высокоточная оценка основной энергии с меньшим количеством кубитов», Arxiv: 1712.03193.

[14] Иван Барде и Камбиз Рузе, «Гиперсжимаемость и логарифмическое неравенство Соболева для непримитивных квантовых марковских полугрупп и оценка скорости декогеренции», Arxiv: 1803.05379.

[15] Эшли Монтанаро, «Квантовое ускорение алгоритмов ветвей и границ», Arxiv: 1906.10375.

[16] Йоханнес Бауш, Сатьявагисвар Субраманиан и Стивен Пиддок, «Квантовый поисковый декодер для обработки естественного языка», Arxiv: 1909.05023.

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

Не удалось получить Перекрестная ссылка на данные во время последней попытки 2020-02-14 09:28:13: Не удалось получить цитируемые данные для 10.22331 / q-2020-02-14-230 от Crossref. Это нормально, если DOI был зарегистрирован недавно.

Источник: https://quantum-journal.org/papers/q-2020-02-14-230/

Spot_img

Последняя разведка

Spot_img