Сложность квантовых машин опорных векторов

Сложность квантовых машин опорных векторов

Отметка времени: 11 января 2024 г., 9:08
Исходный узел: 3057476

Джан Джентинетта1,2, Арне Томсен3,2, Дэвид Саттер2, и Стефан Вернер2

1Институт физики Федеральной политехнической школы Лозанны
2IBM Quantum, IBM Research Europe – Цюрих
3Кафедра физики ETH Zurich

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

Абстрактные

Квантовые машины опорных векторов используют квантовые схемы для определения функции ядра. Было показано, что этот подход обеспечивает доказуемое экспоненциальное ускорение по сравнению с любым известным классическим алгоритмом для определенных наборов данных. Обучение таких моделей соответствует решению задачи выпуклой оптимизации посредством ее простой или двойственной формулировки. Из-за вероятностного характера квантовой механики на алгоритмы обучения влияет статистическая неопределенность, что существенно влияет на их сложность. Мы показываем, что двойственная задача может быть решена с помощью вычислений $O(M^{4.67}/varepsilon^2)$ квантовой схемы, где $M$ обозначает размер набора данных, а $varepsilon$ точность решения по сравнению с идеальной. являются результатом точных ожидаемых значений, которые можно получить только теоретически. В эмпирически мотивированном предположении мы доказываем, что ядровидная основная задача может быть альтернативно решена за $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ оценок, используя обобщение известной классической задачи. алгоритм под названием Pegasos. Сопутствующие эмпирические результаты показывают, что эти аналитические сложности по существу трудны. Кроме того, мы исследуем вариационную аппроксимацию квантовых машин опорных векторов и показываем, что их эвристическое обучение обеспечивает значительно лучшее масштабирование в наших экспериментах.

Рекомендованное изображение: Оценка значения ядра $k(mathbf{x}_i, mathbf{x}_j)$, где $mathcal{E}(mathbf{x}_i)$ обозначает унитарную величину, параметризованную данными $mathbf{x }_i$. Количество выстрелов определяется величиной $R$, которая контролирует точность оценки ядра.

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

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

► Данные BibTeX

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

[1] Дж. Биамонте, П. Виттек, Н. Панкотти, П. Ребентрост, Н. Вибе и С. Ллойд. Квантовое машинное обучение. Nature, 549(7671):195–202, 2017. DOI: 10.1038/​nature23474.
https: / / doi.org/ 10.1038 / nature23474

[2] В. Гавличек, А. Д. Корколес, К. Темме, А. В. Харроу, А. Кандала, Дж. М. Чоу и Дж. М. Гамбетта. Контролируемое обучение с использованием квантово-расширенных пространств функций. Nature, 567(7747):209–212, 2019. DOI: 10.1038/​s41586-019-0980-2.
https:/​/​doi.org/​10.1038/​s41586-019-0980-2

[3] А. Аббас, Д. Саттер, К. Зуфаль, А. Лукки, А. Фигалли и С. Вернер. Сила квантовых нейронных сетей. Nature Computational Science, 1 июня 2020 г. DOI: 10.1038/​s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] Ю. Лю, С. Аруначалам и К. Темме. Строгое и надежное квантовое ускорение контролируемого машинного обучения. Физика природы, 2021. DOI: 10.1038/​s41567-021-01287-z.
HTTPS: / / doi.org/ 10.1038 / s41567-021-01287-г

[5] С. Ааронсон. Прочтите мелкий шрифт. Nature Physics, 11(4):291–293, 2015. DOI: 10.1038/nphys3272.
https: / / doi.org/ 10.1038 / nphys3272

[6] Э. Тан. Классический квантовый алгоритм для рекомендательных систем. В материалах 51-го ежегодного симпозиума ACM SIGACT по теории вычислений, STOC 2019, стр. 217–228, Нью-Йорк, штат Нью-Йорк, США, 2019. Ассоциация вычислительной техники. DOI: 10.1145/​3313276.3316310.
https: / / doi.org/ 10.1145 / 3313276.3316310

[7] Н.-Х. Чиа, А. Гильен, Т. Ли, Х.-Х. Линь, Э. Тан и К. Ван. Сублинейная матричная арифметическая основа низкого ранга на основе выборки для деквантования квантового машинного обучения, стр. 387–400. Ассоциация вычислительной техники, Нью-Йорк, штат Нью-Йорк, США, 2020 г. Доступно онлайн: https://doi.org/10.1145/3357713.3384314.
https: / / doi.org/ 10.1145 / 3357713.3384314

[8] Т. Ли, С. Чакрабарти и К. Ву. Сублинейные квантовые алгоритмы для обучения линейных и ядерных классификаторов. На Международной конференции по машинному обучению, страницы 3815–3824. ПМЛР, 2019.

[9] С. Танасилп, С. Ван, М. Сересо и З. Холмс. Экспоненциальная концентрация и необучаемость в методах квантового ядра, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

[10] С. Шалев-Шварц и Н. Сребро. Оптимизация SVM: обратная зависимость от размера обучающего набора. Материалы 25-й Международной конференции по машинному обучению, страницы 928–935, 2008 г.

[11] А. Томсен. Сравнение квантовых нейронных сетей и квантовых машин опорных векторов. Магистерская диссертация, ETH Zurich, 2021 сентября 09 г. DOI: 06/​20.500.11850.

[12] Б. Э. Бозер, И. М. Гийон, В. Н. Вапник. Алгоритм обучения оптимальных классификаторов маржи. В материалах пятого ежегодного семинара по теории вычислительного обучения, COLT '92, страницы 144–152, Нью-Йорк, штат Нью-Йорк, США, 1992. Ассоциация вычислительной техники. DOI: 10.1145/​130385.130401.
https: / / doi.org/ 10.1145 / 130385.130401

[13] К. Кортес и В. Вапник. Сети опорных векторов. В машинном обучении, страницы 273–297, 1995 г.

[14] В. Н. Вапник. Природа статистической теории обучения. Springer Science+Business Media, LLC, 2000.

[15] Ф. Педрегоса и др. Scikit-learn: машинное обучение на Python. Журнал исследований машинного обучения, 12(85):2825–2830, 2011. Доступно в Интернете: http://jmlr.org/papers/v12/pedregosa11a.html.
http://jmlr.org/papers/v12/pedregosa11a.html

[16] С. Бойд и Л. Ванденберге. Выпуклая оптимизация. Издательство Кембриджского университета, 2004.

[17] С. Шалев-Шварц, Ю. Сингер, Н. Сребро и А. Коттер. Pegasos: первичный расчетный решатель субградиентов для SVM. Математическое программирование, 127(1):3–30, 2011. DOI: 10.1007/​s10107-010-0420-4.
https:/​/​doi.org/​10.1007/​s10107-010-0420-4

[18] M.D.S. Anis et al. Qiskit: Платформа с открытым исходным кодом для квантовых вычислений, 2021. DOI: 10.5281/​zenodo.2573505.
https: / / doi.org/ 10.5281 / zenodo.2573505

[19] П. Ребентрост, М. Мохсени и С. Ллойд. Квантовая машина опорных векторов для классификации больших данных. Physical Review Letters, 113(3):1–5, 2014. DOI: 10.1103/​PhysRevLett.113.130503.
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503

[20] Й. Кюблер, С. Бухгольц и Б. Шёлкопф. Индуктивное смещение квантовых ядер. В М. Ранзато, А. Бейгельцимере, Ю. Дофине, П. Ляне и Дж. В. Вогане, редакторах, «Достижения в области нейронных систем обработки информации», том 34, страницы 12661–12673. Curran Associates, Inc., 2021 г. Доступно онлайн: https://proceedings.neurips.cc/paper_files/paper/2021/file/69adc1e107f7f7d035d7baf04342e1ca-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper_files/​paper/​2021/​file/​69adc1e107f7f7d035d7baf04342e1ca-Paper.pdf

[21] В. Эйро, З. Ли, З. Дени, А. Ле Бойте и К. Сьюти. Шумные машины с квантовым ядром. Физ. Rev. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

[22] CJC Burges и CJC Burges. Учебное пособие по машинам опорных векторов для распознавания образов. Data Mining and Knowledge Discovery, 2:121–167, 1998. Доступно в Интернете: https://www.microsoft.com/en-us/research/publication/a-tutorial-on-support-vector. -машины-для-распознавания образов/​.
https://www.microsoft.com/en-us/research/publication/a-tutorial-on-support-vector-machines-for-pattern-recognition/​

[23] М. Сересо, А. Соне, Т. Волков, Л. Чинчио и П. Дж. Коулз. Бесплодные плато, зависящие от функции стоимости, в неглубоких параметризованных квантовых схемах. Nature Communications, 12(1):1791, 2021. DOI: 10.1038/​s41467-021-21728-w.
HTTPS: / / doi.org/ 10.1038 / s41467-021-21728-ш

[24] Белис, Василис, Гонсалес-Кастильо, Самуэль, Рейссель, Кристина, Вальекорса, София, Комбарро, Элиас Ф., Диссертори, Гюнтер и Райтер, Флорентин. Хиггсовский анализ с помощью квантовых классификаторов. EPJ Web Conf., 251:03070, 2021. DOI: 10.1051/​epjconf/​202125103070.
https: / / doi.org/ 10.1051 / epjconf / 202125103070

[25] М. Сересо, А. Аррасмит, Р. Бэббуш, С. К. Бенджамин, С. Эндо, К. Фуджи, Дж. Р. МакКлин, К. Митараи, К. Юань, Л. Чинсио и П. Дж. Коулз. Вариационные квантовые алгоритмы. Nature Reviews Physics, 3(9):625–644, 2021. DOI: 10.1038/s42254-021-00348-9.
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[26] Р. МакГибборн и др. quadprog: решатель квадратичного программирования (python). https://github.com/quadprog/quadprog, 2022 г.
https://github.com/quadprog/quadprog

[27] Ю. Нестеров. Вводные лекции по выпуклой оптимизации: базовый курс. Прикладная оптимизация. Springer, 2004. DOI: 10.1007/978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] Дж. Сполл. Обзор метода одновременного возмущения для эффективной оптимизации. Технический дайджест Джона Хопкинса APL, 19 (4), страницы 482–492, 1998.

[29] Г. Джентинетта, А. Томсен, Д. Саттер и С. Вернер. Код для рукописи «Сложность квантовых машин опорных векторов». 2022. DOI: https://doi.org/10.5281/zenodo.6303725.
https: / / doi.org/ 10.5281 / zenodo.6303725

[30] Т. Хубрегцен, Д. Вирихс, Э. Гил-Фустер, П.-Дж. Х. С. Деркс, П. К. Ферманн и Дж. Дж. Мейер. Обучение ядер квантового встраивания на квантовых компьютерах ближайшего будущего. Физ. Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] Р. Латала. Некоторые оценки норм случайных матриц. Proceedings of the American Mathematical Society, 133(5):1273–1282, 2005. DOI: 10.1090/​s0002-9939-04-07800-1.
https:/​/​doi.org/​10.1090/​s0002-9939-04-07800-1

[32] Р. Вершинин. Введение в неасимптотический анализ случайных матриц. Сжатое зондирование: теория и приложения, стр. 210–268, 2009 г. DOI: 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

[33] Т. Хофманн, Б. Шёлкопф и А. Дж. Смола. Ядерные методы в машинном обучении. Анналы статистики, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / 009053607000000677

[34] Дж. В. Дэниел. Устойчивость решения определенных квадратичных программ. Математическое программирование, 5(1):41–53, 1973. DOI: 10.1007/​BF01580110.
https: / / doi.org/ 10.1007 / BF01580110

Цитируется

[1] Александр М. Далзелл, Сэм МакАрдл, Марио Берта, Пшемыслав Биениас, Чи-Фанг Чен, Андраш Гильен, Коннор Т. Ханн, Майкл Дж. Касторияно, Эмиль Т. Хабибуллин, Александр Кубица, Грант Солтон, Самсон Ван и Фернандо ГСЛ Брандао, «Квантовые алгоритмы: обзор приложений и сквозных сложностей», Arxiv: 2310.03011, (2023).

[2] Мария Шульд и Натан Киллоран, «Является ли квантовое преимущество правильной целью для квантового машинного обучения?», PRX Quantum 3 3, 030101 (2022).

[3] Мохаммад Хасан Хасаншахи, Марцин Ястржебски, Сара Малик и Офер Лахав, «Машина опорных векторов с квантовыми улучшениями для классификации галактик», РАН «Техника и приборы» 2 1, 752 (2023).

[4] Куан-Ченг Чен, Сяотянь Сюй, Генри Маханов, Хуэй-Сюань Чунг и Чэнь-Ю Лю, «Квантовая машина опорных векторов для крупномасштабной звездной классификации с ускорением графического процессора», Arxiv: 2311.12328, (2023).

[5] Супанут Танасилп, Самсон Ван, М. Сересо и Зои Холмс, «Экспоненциальная концентрация и необучаемость в методах квантового ядра», Arxiv: 2208.11060, (2022).

[6] Кохей Накадзи, Хироюки Тэдзука и Наоки Ямамото, «Квантово-классические гибридные нейронные сети в режиме нейронного касательного ядра», Квантовая наука и техника 9 1, 015022 (2024).

[7] Ясвита Гуджу, Ацуши Мацуо и Руди Рэймонд, «Квантовое машинное обучение на квантовых устройствах краткосрочной перспективе: текущее состояние контролируемых и неконтролируемых методов для реальных приложений», Arxiv: 2307.00908, (2023).

[8] Рауль Хиз, Торе Герлах, Саша Мюке, Сабина Мюллер, Маттиас Якобс и Нико Пятковски, «Объяснение квантовых схем с помощью значений Шепли: на пути к объяснимому квантовому машинному обучению», Arxiv: 2301.09138, (2023).

[9] Жюльен Гакон, Яннес Нис, Риккардо Росси, Стефан Вернер и Джузеппе Карлео, «Вариационная квантовая эволюция времени без квантового геометрического тензора», Arxiv: 2303.12839, (2023).

[10] Джан Джентинетта, Дэвид Саттер, Криста Зуфал, Брайс Фуллер и Стефан Вернер, «Квантовое выравнивание ядра со стохастическим градиентным спуском», Arxiv: 2304.09899, (2023).

[11] Филиппа Дакетт, Габриэль Фачини, Марцин Ястржебски, Сара Малик, Себастьен Ретти и Тим Скэнлон, «Реконструкция сегментов трека заряженных частиц с помощью квантово-усовершенствованной машины опорных векторов», Arxiv: 2212.07279, (2022).

[12] Трэвис Л. Шолтен, Деррик Перри, Джозеф Вашингтон, Дженнифер Р. Глик и Томас Уорд, «Модель времени выполнения схемы и ее последствия для квантовых ядер при практических размерах наборов данных», Arxiv: 2307.04980, (2023).

[13] Саманта В. Бэррон, Дэниел Дж. Эггер, Элайджа Пелофске, Андреас Берчи, Стефан Эйденбенц, Маттис Лемкюлер и Стефан Вернер, «Доказуемые границы для свободных от шума значений ожидания, вычисленных на основе зашумленных выборок», Arxiv: 2312.00733, (2023).

[14] М. Эмре Сахин, Бенджамин К. Б. Саймонс, Пушпак Пати, Файяз Минхас, Деклан Миллар, Мария Габрани, Ян Лукас Робертус и Стефано Менса, «Эффективная оптимизация параметров для квантового выравнивания ядра: подход с подвыборкой в ​​вариационном обучении» , Arxiv: 2401.02879, (2024).

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

On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2024-01-12 02:12:21).

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

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

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