Złożoność kwantowych maszyn wektorów nośnych

Złożoność kwantowych maszyn wektorów nośnych

Znacznik czasu: 11 stycznia 2024 9:08
Węzeł źródłowy: 3057476

Gian Gentinetta1,2, Arne Thomsena3,2, Dawid Sutter2i Stefana Woernera2

1Instytut Fizyki, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – Zurych
3Wydział Fizyki, ETH Zurich

Czy ten artykuł jest interesujący czy chcesz dyskutować? Napisz lub zostaw komentarz do SciRate.

Abstrakcyjny

Kwantowe maszyny wektorów nośnych wykorzystują obwody kwantowe do definiowania funkcji jądra. Wykazano, że to podejście zapewnia możliwe do udowodnienia wykładnicze przyspieszenie w porównaniu z dowolnym znanym klasycznym algorytmem dla niektórych zbiorów danych. Uczenie takich modeli odpowiada rozwiązaniu problemu optymalizacji wypukłej poprzez jego pierwotne lub dualne sformułowanie. Ze względu na probabilistyczny charakter mechaniki kwantowej, algorytmy uczące obarczone są niepewnością statystyczną, co ma istotny wpływ na ich złożoność. Pokazujemy, że problem podwójny można rozwiązać w ocenach obwodu kwantowego $O(M^{4.67}/varepsilon^2)$, gdzie $M$ oznacza rozmiar zbioru danych, a $varepsilon$ dokładność rozwiązania w porównaniu z ideałem wynikają z dokładnych wartości oczekiwanych, które można uzyskać jedynie w teorii. Dowodzimy, przy założeniu motywowanym empirycznie, że pierwotny problem z jądrem można alternatywnie rozwiązać w ocenach $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ poprzez uogólnienie znanego klasycznego algorytm o nazwie Pegasos. Towarzyszące wyniki empiryczne pokazują, że te analityczne złożoności są zasadniczo ograniczone. Ponadto badamy wariacyjne przybliżenie maszyn kwantowych wektorów nośnych i pokazujemy, że ich szkolenie heurystyczne zapewnia znacznie lepsze skalowanie w naszych eksperymentach.

Wyróżniony obraz: Oszacowanie wartości jądra $k(mathbf{x}_i, mathbf{x}_j)$, gdzie $mathcal{E}(mathbf{x}_i)$ oznacza jednostkę sparametryzowaną przez dane $mathbf{x }_i$. Liczba strzałów jest określona przez $R$, który kontroluje dokładność oszacowania jądra.

Popularne podsumowanie

Kwantowe maszyny wektorów nośnych są kandydatami do wykazania w najbliższej przyszłości przewagi kwantowej w przypadku problemów klasyfikacyjnych. Pomysł jest taki, że (miejmy nadzieję, użyteczną) funkcję jądra zapewnia wydajny obwód kwantowy, który jest klasycznie trudny do oceny. Ze względu na probabilistyczny charakter mechaniki kwantowej na takie funkcje jądra wpływa niepewność statystyczna. W tej pracy rygorystycznie analizujemy, w jaki sposób ta niepewność (zwana także szumem strzałowym) wpływa na ogólną złożoność obliczeniową rozwiązania problemu klasyfikacji.

► Dane BibTeX

► Referencje

[1] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe i S. Lloyd. Kwantowe uczenie maszynowe. Nature, 549(7671):195–202, 2017. DOI: 10.1038/​nature23474.
https: / / doi.org/ 10.1038 / nature23474

[2] V. Havlíček, AD Córcoles, K. Temme, AW Harrow, A. Kandala, JM Chow i JM Gambetta. Uczenie się nadzorowane z przestrzeniami cech wzmocnionymi kwantowo. Nature, 567(7747):209–212, 2019. DOI: 10.1038/​s41586-019-0980-2.
https:/​/​doi.org/​10.1038/​s41586-019-0980-2

[3] A. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli i S. Woerner. Siła kwantowych sieci neuronowych. Nature Computational Science, 1 (czerwiec), 2020. DOI: 10.1038/​s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] Y. Liu, S. Arunachalam i K. Temme. Rygorystyczne i solidne przyspieszenie kwantowe w nadzorowanym uczeniu maszynowym. Fizyka Przyrody, 2021. DOI: 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

[5] S. Aaronsona. Przeczytaj drobny druk. Nature Physics, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https: / / doi.org/ 10.1038 / nphys3272

[6] E. Tang. Klasyczny algorytm inspirowany technologią kwantową dla systemów rekomendacyjnych. W materiałach z 51. dorocznego sympozjum ACM SIGACT na temat teorii informatyki, STOC 2019, s. 217–228, Nowy Jork, NY, USA, 2019. Association for Computing Machinery. DOI: 10.1145/​3313276.3316310.
https: / / doi.org/ 10.1145 / 3313276.3316310

[7] N.-H. Chia, A. Gilyén, T. Li, H.-H. Lin, E. Tang i C. Wang. Oparta na próbkowaniu subliniowa macierz arytmetyczna niskiego rzędu do dekwantyzacji kwantowego uczenia maszynowego, strony 387–400. Association for Computing Machinery, Nowy Jork, NY, USA, 2020. Dostępne online: https://​/​doi.org/​10.1145/​3357713.3384314.
https: / / doi.org/ 10.1145 / 3357713.3384314

[8] T. Li, S. Chakrabarti i X. Wu. Subliniowe algorytmy kwantowe do uczenia klasyfikatorów liniowych i jądrowych. W Międzynarodowej konferencji na temat uczenia maszynowego, strony 3815–3824. PMLR, 2019.

[9] S. Thanasilp, S. Wang, M. Cerezo i Z. Holmes. Wykładnicza koncentracja i niemożność trenowania w metodach jądra kwantowego, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

[10] S. Shalev-Shwartz i N. Srebro. Optymalizacja SVM: Odwrotna zależność od rozmiaru zestawu treningowego. Materiały z 25. Międzynarodowej Konferencji na temat uczenia maszynowego, strony 928–935, 2008.

[11] A. Thomsena. Porównanie kwantowych sieci neuronowych i kwantowych maszyn wektorów nośnych. Praca magisterska, ETH Zurich, 2021-09-06. DOI: 20.500.11850/​527559.

[12] BE Boser, IM Guyon i VN Vapnik. Algorytm szkoleniowy dla klasyfikatorów optymalnej marży. W Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, strony 144–152, Nowy Jork, NY, USA, 1992. Association for Computing Machinery. DOI: 10.1145/​130385.130401.
https: / / doi.org/ 10.1145 / 130385.130401

[13] C. Cortesa i V. Vapnika. Sieci wektorów nośnych. W uczeniu maszynowym, strony 273–297, 1995.

[14] VN Vapnik. Natura statystycznej teorii uczenia się. Springer Science+Business Media, LLC, 2000.

[15] F. Pedregosa i in. Scikit-learn: Uczenie maszynowe w Pythonie. Journal of Machine Learning Research, 12(85):2825–2830, 2011. Dostępne w Internecie: http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

[16] S. Boyda i L. Vandenberghe. Optymalizacja wypukła. Cambridge University Press, 2004.

[17] S. Shalev-Shwartz, Y. Singer, N. Srebro i A. Cotter. Pegasos: Pierwotny szacowany moduł rozwiązywania podgradientów dla SVM. Programowanie matematyczne, 127(1):3–30, 2011. DOI: 10.1007/​s10107-010-0420-4.
https:/​/​doi.org/​10.1007/​s10107-010-0420-4

[18] MDS Anis i in. Qiskit: An Open Source Framework for Quantum Computing, 2021. DOI: 10.5281/​zenodo.2573505.
https: / / doi.org/ 10.5281 / zenodo.2573505

[19] P. Rebentrost, M. Mohseni i S. Lloyd. Kwantowa maszyna wektorów nośnych do klasyfikacji dużych zbiorów danych. Physical Review Letters, 113(3):1–5, 2014. DOI: 10.1103/​PhysRevLett.113.130503.
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503

[20] J. Kübler, S. Buchholz i B. Schölkopf. Indukcyjne odchylenie jąder kwantowych. W: M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang i JW Vaughan, redaktorzy, Advances in Neural Information Processing Systems, tom 34, strony 12661–12673. Curran Associates, Inc., 2021. Dostępne w internecie: 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] V. Heyraud, Z. Li, Z. Denis, A. Le Boité i C. Ciuti. Hałaśliwe maszyny z jądrem kwantowym. Fiz. Rev. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

[22] CJC Burges i CJC Burges. Samouczek na temat maszyn wektorów nośnych do rozpoznawania wzorów. Data Mining and Knowledge Discovery, 2:121–167, 1998. Dostępne w Internecie: https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -maszyny-do-rozpoznawania-wzorów/​.
https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector-machines-for-pattern-recognition/​

[23] M. Cerezo, A. Sone, T. Volkoff, L. Cincio i PJ Coles. Jałowe plateau zależne od funkcji kosztu w płytkich sparametryzowanych obwodach kwantowych. Nature Communications, 12(1):1791, 2021. DOI: 10.1038/​s41467-021-21728-w.
https: / / doi.org/ 10.1038 / s41467-021-21728-w

[24] Belis, Vasilis, González-Castillo, Samuel, Reissel, Christina, Vallecorsa, Sofia, Combarro, Elías F., Dissertori, Günther i Reiter, Florentin. Analiza Higgsa z wykorzystaniem klasyfikatorów kwantowych. EPJ Web Conf., 251:03070, 2021. DOI: 10.1051/​epjconf/​202125103070.
https://​/​doi.org/​10.1051/​epjconf/​202125103070

[25] M. Cerezo, A. Arrasmith, R. Babbush, SC Benjamin, S. Endo, K. Fujii, JR McClean, K. Mitarai, X. Yuan, L. Cincio i PJ Coles. Wariacyjne algorytmy kwantowe. 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] R. McGibborn i in. quadprog: Solver programowania kwadratowego (python). https://​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

[27] Y. Niestierow. Wykłady wprowadzające na temat optymalizacji wypukłej: kurs podstawowy. Zastosowana optymalizacja. Springer, 2004. DOI: 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] J. Spall. Przegląd metody równoczesnych zaburzeń w celu efektywnej optymalizacji. Przegląd techniczny Johna Hopkinsa APL, 19 (4), strony 482–492, 1998.

[29] G. Gentinetta, A. Thomsen, D. Sutter i S. Woerner. Kod manuskryptu „Złożoność kwantowych maszyn wektorów nośnych”. 2022. DOI: https://​/​doi.org/​10.5281/​zenodo.6303725.
https: / / doi.org/ 10.5281 / zenodo.6303725

[30] T. Hubregtsen, D. Wierichs, E. Gil-Fuster, P.-JHS Derks, PK Faehrmann i JJ Meyer. Trenowanie jąder osadzania kwantowego na krótkoterminowych komputerach kwantowych. Fiz. Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] R. Latała. Niektóre szacunki norm macierzy losowych. 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] R. Wierszynin. Wprowadzenie do nieasymptotycznej analizy macierzy losowych. Compressed Sensing: Theory and Applications, strony 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

[33] T. Hofmann, B. Schölkopf i AJ Smola. Metody jądra w uczeniu maszynowym. Annals of Statistics, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / 009053607000000677

[34] J.W. Daniela. Stabilność rozwiązania określonych programów kwadratowych. Programowanie matematyczne, 5(1):41–53, 1973. DOI: 10.1007/​BF01580110.
https: / / doi.org/ 10.1007 / BF01580110

Cytowany przez

[1] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemysław Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang i Fernando GSL Brandão, „Algorytmy kwantowe: przegląd aplikacji i kompleksowych złożoności”, arXiv: 2310.03011, (2023).

[2] Maria Schuld i Nathan Killoran, „Czy przewaga kwantowa jest właściwym celem kwantowego uczenia maszynowego?”, PRX Quantum 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik i Ofer Lahav, „A quantum-enhanced support Vector Machine for galaxyclassification”, „Wzmocniona kwantowo maszyna wektorów nośnych do klasyfikacji galaktyk”, Techniki i instrumenty RAS 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung i 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 i Zoë Holmes, „Wykładnicza koncentracja i nietreningowość w metodach jądra kwantowego”, arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka i Naoki Yamamoto, „Kwantowo-klasyczne hybrydowe sieci neuronowe w reżimie jądra stycznego neuronowego”, Nauka i technologia kwantowa 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo i Rudy Raymond, „Kwantowe uczenie maszynowe na krótkoterminowych urządzeniach kwantowych: aktualny stan technik nadzorowanych i nienadzorowanych w zastosowaniach w świecie rzeczywistym”, arXiv: 2307.00908, (2023).

[8] Raoul Heese, Thore Gerlach, Sascha Mücke, Sabine Müller, Matthias Jakobs i Nico Piątkowski, „Wyjaśnienie obwodów kwantowych za pomocą wartości Shapleya: w stronę wyjaśnialnego uczenia maszynowego kwantowego”, arXiv: 2301.09138, (2023).

[9] Julien Gacon, Jannes Nys, Riccardo Rossi, Stefan Woerner i Giuseppe Carleo, „Variational Quantum Time Evolution Without the Quantum Geometric Tensor”, arXiv: 2303.12839, (2023).

[10] Gian Gentinetta, David Sutter, Christa Zoufal, Bryce Fuller i Stefan Woerner, „Quantum Kernel Alignment with Stochastic Gradient Descent”, arXiv: 2304.09899, (2023).

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie i Tim Scanlon, „Rekonstrukcja segmentów ścieżek cząstek naładowanych za pomocą maszyny wektorów nośnych o wzmocnionej kwantowości”, arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick i Thomas Ward, „Model czasu wykonania obwodu i jego implikacje dla jąder kwantowych w praktycznych rozmiarach zbioru danych”, arXiv: 2307.04980, (2023).

[13] Samantha V. Barron, Daniel J. Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler i Stefan Woerner, „Udowodnione granice wartości oczekiwanych bez szumów obliczonych na podstawie zaszumionych próbek”, arXiv: 2312.00733, (2023).

[14] M. Emre Sahin, Benjamin CB Symons, Pushpak Pati, Fayyaz Minhas, Declan Millar, Maria Gabrani, Jan Lukas Robertus i Stefano Mensa, „Efficient Parameter Optimization for Quantum Kernel Alignment: A Sub-sampling Approach in Variational Training” , arXiv: 2401.02879, (2024).

Powyższe cytaty pochodzą z Reklamy SAO / NASA (ostatnia aktualizacja pomyślnie 2024-01-12 02:12:22). Lista może być niekompletna, ponieważ nie wszyscy wydawcy podają odpowiednie i pełne dane cytowania.

On Serwis cytowany przez Crossref nie znaleziono danych na temat cytowania prac (ostatnia próba 2024-01-12 02:12:21).

Niniejszy artykuł opublikowano w Quantum pod Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0) licencja. Prawa autorskie należą do pierwotnych właścicieli praw autorskich, takich jak autorzy lub ich instytucje.

Znak czasu:

Więcej z Dziennik kwantowy