1QuSoft, Амстердам, Нидерланды.
2Университет Амстердама, Нидерланды.
3Университет Амстердама, Нидерланды.
Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.
Абстрактные
Брандао и Своре [14] недавно дал квантовые алгоритмы приближенного решения полуопределенных программ, которые в некоторых режимах быстрее наилучших из возможных классических алгоритмов по размерности $n$ задачи и количеству $m$ ограничений, но хуже по различным другие параметры. В этой статье мы улучшаем их алгоритмы несколькими способами, улучшая зависимость от этих других параметров. С этой целью мы разрабатываем новые методы для квантовых алгоритмов, например, общий способ эффективной реализации гладких функций разреженных гамильтонианов и обобщенную процедуру поиска минимума.
Мы также показываем ограничения этого подхода для квантовых SDP-решателей, например, для задач комбинаторной оптимизации, которые имеют большую симметрию. Наконец, мы доказываем некоторые общие нижние оценки, показывающие, что в худшем случае сложность каждого квантового LP-решателя (и, следовательно, также SDP-решателя) должна масштабироваться линейно с $mn$, когда $m приблизительно n$, что совпадает с классический.
Популярное резюме
► Данные 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 был зарегистрирован недавно.
Эта статья опубликована в Quantum под Creative Commons Attribution 4.0 International (CC BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.
Источник: https://quantum-journal.org/papers/q-2020-02-14-230/