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

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

Мітка часу: 11 січня 2024 р., 9:08 ранку
Вихідний вузол: 3057476

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

1Інститут фізики, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – Цюріх
3Факультет фізики, ETH Zurich

Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на 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] Ю. Лю, С. Аруначалам і К. Темме. Суворе та надійне квантове прискорення керованого машинного навчання. Nature Physics, 2021. DOI: 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

[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] Т. Лі, С. Чакрабарті та X. Ву. Сублінійні квантові алгоритми для навчання лінійних і ядерних класифікаторів. У Міжнародній конференції з машинного навчання, сторінки 3815–3824. PMLR, 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-06. DOI: 20.500.11850/​527559.

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

[13] К. Кортес і В. Вапник. Опорно-векторні мережі. У Machine Learning, сторінки 273–297, 1995.

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

[15] F. Pedregosa та ін. Scikit-learn: машинне навчання на Python. Journal of Machine Learning Research, 12(85):2825–2830, 2011. Доступно онлайн: http:/​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

[16] С. Бойд і Л. Ванденберге. Конвексна оптимізація. Cambridge University Press, 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 та ін. 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] Й. Кюблер, С. Бухгольц і Б. Шелькопф. Індуктивне зміщення квантових ядер. У M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang і J. W. Vaughan, редактори, Досягнення в системах обробки нейронної інформації, том 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] C. J. C. Берджес і C. J. C. Берджес. Підручник із опорних векторних машин для розпізнавання образів. Data Mining and Knowledge Discovery, 2:121–167, 1998. Доступно онлайн: https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -machines-for-pattern-recognition/​.
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-w

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

[25] М. Серезо, А. Аррасміт, Р. Беббуш, С. К. Бенджамін, С. Ендо, К. Фуджі, Дж. Р. Макклін, К. Мітараї, X. Юань, Л. Сінчіо та П. Дж. Коулз. Варіаційні квантові алгоритми. 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] Дж. Сполл. Огляд методу одночасного збурення для ефективної оптимізації. John Hopkins APL Technical Digest, 19(4), сторінки 482–492, 1998.

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

[30] Т. Губрегтсен, Д. Віріхс, Е. Гіл-Фустер, П.-Ж. H. S. Derks, P. K. Faehrmann і J. J. Meyer. Навчання ядрам квантового вбудовування на квантових комп’ютерах короткого періоду. фіз. Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] Р. Латала. Деякі оцінки норм випадкових матриць. Праці Американського математичного товариства, 133(5):1273–1282, 2005. DOI: 10.1090/​s0002-9939-04-07800-1.
https:/​/​doi.org/​10.1090/​s0002-9939-04-07800-1

[32] Р. Вершиніна. Введення в неасимптотичний аналіз випадкових матриць. Compressed Sensing: Theory and Applications, сторінки 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https://​/​doi.org/​10.1017/​CBO9780511794308.006

[33] Т. Хофманн, Б. Шелькопф, А. Й. Смола. Методи ядра в машинному навчанні. Annals of Statistics, 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] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung, and Chen-Yu Liu, “Quantum-Enhanced Support Vector Machine for Large-Scale Stellar Classification with GPU Acceleration”, arXiv: 2311.12328, (2023).

[5] Supanut Thanasilp, Samson Wang, M. Cerezo та Zoë Holmes, «Експоненціальна концентрація та неможливість навчання в методах квантового ядра», arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka та Naoki Yamamoto, “Квантово-класичні гібридні нейронні мережі в режимі нейронного дотичного ядра”, Квантова наука і техніка 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo та Rudy Raymond, «Quantum Machine Learning on Near-Term Quantum Devices: Current State of Supervised and Unsupervised Techniques for Real-World Applications», 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] M. Emre Sahin, Benjamin C. B. Symons, Pushpak Pati, Fayyaz Minhas, Declan Millar, Maria Gabrani, Jan Lukas Robertus і Stefano Mensa, «Efficient Parameter Optimization for Quantum Kernel Alignment: A Sub-sampling Approach in Variation Training» , arXiv: 2401.02879, (2024).

Вищезазначені цитати від SAO / NASA ADS (останнє оновлення успішно 2024-01-12 02:12:22). Список може бути неповним, оскільки не всі видавці надають відповідні та повні дані про цитування.

On Служба, на яку посилається Crossref даних про цитування робіт не знайдено (остання спроба 2024-01-12 02:12:21).

Ця стаття опублікована в Quantum під Creative Commons Attribution 4.0 International (CC на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.

Часова мітка:

Більше від Квантовий журнал