Kompleksnost kvantnih podpornih vektorskih strojev

Kompleksnost kvantnih podpornih vektorskih strojev

Časovni žig: 11. januar 2024 9
Izvorno vozlišče: 3057476

Gian Gentinetta1,2, Arne Thomsen3,2, David Sutter2in Stefan Woerner2

1Inštitut za fiziko, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – Zürich
3Oddelek za fiziko, ETH Zürich

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

Kvantni podporni vektorski stroji uporabljajo kvantna vezja za definiranje funkcije jedra. Pokazalo se je, da ta pristop ponuja dokazljivo eksponentno pospešitev v primerjavi s katerim koli znanim klasičnim algoritmom za določene nize podatkov. Usposabljanje takšnih modelov ustreza reševanju problema konveksne optimizacije bodisi prek njegove primarne ali dvojne formulacije. Zaradi verjetnostne narave kvantne mehanike na učne algoritme vpliva statistična negotovost, ki močno vpliva na njihovo kompleksnost. Pokažemo, da je dvojni problem mogoče rešiti v vrednotenjih kvantnega vezja $O(M^{4.67}/varepsilon^2)$, kjer $M$ označuje velikost nabora podatkov, $varepsilon$ pa natančnost rešitve v primerjavi z idealno rezultat natančnih pričakovanih vrednosti, ki jih je mogoče dobiti samo v teoriji. Pod empirično motivirano predpostavko dokažemo, da je jedrnati primarni problem mogoče alternativno rešiti v vrednotenjih $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ z uporabo posplošitve znane klasične algoritem, imenovan Pegasos. Priloženi empirični rezultati kažejo, da so te analitične kompleksnosti v bistvu tesne. Poleg tega raziskujemo variacijski približek kvantnim podpornim vektorskim strojem in pokažemo, da njihovo hevristično usposabljanje dosega bistveno boljše skaliranje v naših poskusih.

Predstavljena slika: Ocena vrednosti jedra $k(mathbf{x}_i, mathbf{x}_j)$, kjer $mathcal{E}(mathbf{x}_i)$ označuje enoto, parametrizirano s podatki $mathbf{x }_i$. Število strelov je podano z $R$, ki nadzira natančnost ocene jedra.

Priljubljen povzetek

Kvantni podporni vektorski stroji so kandidati za prikaz kvantne prednosti v bližnji prihodnosti pri težavah s klasifikacijo. Ideja je, da je (upajmo uporabna) funkcija jedra podana z učinkovitim kvantnim vezjem, ki ga je klasično težko ovrednotiti. Zaradi verjetnostne narave kvantne mehanike na takšne funkcije jedra vpliva statistična negotovost. V tem delu natančno analiziramo, kako ta negotovost (imenovana tudi strelni šum) vpliva na celotno računsko kompleksnost za reševanje problema klasifikacije.

► BibTeX podatki

► Reference

[1] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe in S. Lloyd. Kvantno strojno učenje. Narava, 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 in JM Gambetta. Nadzorovano učenje s kvantno izboljšanimi prostori funkcij. Narava, 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 in S. Woerner. Moč kvantnih nevronskih mrež. Nature Computational Science, 1 (junij), 2020. DOI: 10.1038/​s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] Y. Liu, S. Arunachalam in K. Temme. Strogo in robustno kvantno pospeševanje v nadzorovanem strojnem učenju. Fizika narave, 2021. DOI: 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

[5] S. Aaronson. Preberite drobni tisk. Nature Physics, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https: / / doi.org/ 10.1038 / nphys3272

[6] E. Tang. Kvantno navdihnjen klasični algoritem za sisteme priporočil. V zborniku 51. letnega simpozija ACM SIGACT o teoriji računalništva, STOC 2019, stran 217–228, New York, NY, ZDA, 2019. Združenje za računalniške stroje. 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 in C. Wang. Na vzorčenju temelječe sublinearno matrično aritmetično ogrodje nizkega ranga za dekvantiziranje kvantnega strojnega učenja, stran 387–400. Association for Computing Machinery, New York, NY, ZDA, 2020. Dostopno na spletu: https://​/​doi.org/​10.1145/​3357713.3384314.
https: / / doi.org/ 10.1145 / 3357713.3384314

[8] T. Li, S. Chakrabarti in X. Wu. Sublinearni kvantni algoritmi za usposabljanje linearnih in jedrnih klasifikatorjev. Na mednarodni konferenci o strojnem učenju, strani 3815–3824. PMLR, 2019.

[9] S. Thanasilp, S. Wang, M. Cerezo in Z. Holmes. Eksponentna koncentracija in neusposobljivost v metodah kvantnega jedra, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

[10] S. Shalev-Shwartz in N. Srebro. Optimizacija SVM: obratna odvisnost od velikosti vadbenega niza. Zbornik 25. mednarodne konference o strojnem učenju, strani 928–935, 2008.

[11] A. Thomsen. Primerjava kvantnih nevronskih mrež in kvantnih podpornih vektorskih strojev. Magistrsko delo, ETH Zurich, 2021. 09. 06. DOI: 20.500.11850/527559.

[12] BE Boser, IM Guyon in VN Vapnik. Algoritem za usposabljanje za klasifikatorje optimalnih marž. V zborniku pete letne delavnice o teoriji računalniškega učenja, COLT '92, strani 144–152, New York, NY, ZDA, 1992. Association for Computing Machinery. DOI: 10.1145/​130385.130401.
https: / / doi.org/ 10.1145 / 130385.130401

[13] C. Cortes in V. Vapnik. Podporno-vektorska omrežja. V Machine Learning, strani 273–297, 1995.

[14] VN Vapnik. Narava statistične teorije učenja. Springer Science+Business Media, LLC, 2000.

[15] F. Pedregosa et al. Scikit-learn: Strojno učenje v Pythonu. Journal of Machine Learning Research, 12(85):2825–2830, 2011. Dostopno na spletu: http:/​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

[16] S. Boyd in L. Vandenberghe. Konveksna optimizacija. Cambridge University Press, 2004.

[17] S. Shalev-Shwartz, Y. Singer, N. Srebro in A. Cotter. Pegasos: prvotni ocenjeni podgradientni reševalec za SVM. Matematično programiranje, 127(1):3–30, 2011. DOI: 10.1007/​s10107-010-0420-4.
https:/​/​doi.org/​10.1007/​s10107-010-0420-4

[18] MDS Anis et al. Qiskit: Odprtokodni okvir za kvantno računalništvo, 2021. DOI: 10.5281/​zenodo.2573505.
https: / / doi.org/ 10.5281 / zenodo.2573505

[19] P. Rebentrost, M. Mohseni in S. Lloyd. Kvantni podporni vektorski stroj za klasifikacijo velikih podatkov. 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 in B. Schölkopf. Induktivna pristranskost kvantnih jeder. V M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang in JW Vaughan, uredniki, Advances in Neural Information Processing Systems, zvezek 34, strani 12661–12673. Curran Associates, Inc., 2021. Dostopno na spletu: 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é in C. Ciuti. Hrupni stroji s kvantnim jedrom. Phys. Rev. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

[22] CJC Burges in CJC Burges. Vadnica o podpornih vektorskih strojih za prepoznavanje vzorcev. Data Mining and Knowledge Discovery, 2:121–167, 1998. Dostopno na spletu: https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -stroji-za-prepoznavanje-vzorcev/​.
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 in PJ Coles. Od stroškovne funkcije odvisni goli platoji v plitvih parametriziranih kvantnih vezjih. 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 in Reiter, Florentin. Higgsova analiza s kvantnimi klasifikatorji. Spletna konferenca EPJ, 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 in PJ Coles. Variacijski kvantni algoritmi. 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 et al. quadprog: Reševalec kvadratnega programiranja (python). https://​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

[27] Y. Nesterov. Uvodna predavanja o konveksni optimizaciji: osnovni tečaj. Uporabljena optimizacija. Springer, 2004. DOI: 10.1007/978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] J. Spall. Pregled metode simultanih motenj za učinkovito optimizacijo. John Hopkins APL Technical Digest, 19(4), strani 482–492, 1998.

[29] G. Gentinetta, A. Thomsen, D. Sutter in S. Woerner. Koda za rokopis "Kompleksnost kvantnih podpornih vektorskih strojev". 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 in JJ Meyer. Usposabljanje jeder za kvantno vgrajevanje na kvantnih računalnikih v bližnji prihodnosti. Phys. Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] R. Latała. Nekaj ​​ocen norm naključnih matrik. 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. Veršinin. Uvod v neasimptotično analizo naključnih matrik. Stisnjeno zaznavanje: teorija in aplikacije, strani 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

[33] T. Hofmann, B. Schölkopf in AJ Smola. Metode jedra v strojnem učenju. Annals of Statistics, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / 009053607000000677

[34] JW Daniel. Stabilnost rešitve določenih kvadratnih programov. Matematično programiranje, 5(1):41–53, 1973. DOI: 10.1007/​BF01580110.
https: / / doi.org/ 10.1007 / BF01580110

Navedel

[1] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang in Fernando GSL Brandão, "Kvantni algoritmi: pregled aplikacij in kompleksnosti od konca do konca", arXiv: 2310.03011, (2023).

[2] Maria Schuld in Nathan Killoran, »Ali je kvantna prednost pravi cilj za kvantno strojno učenje?«, PRX Quantum 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik in Ofer Lahav, "Kvantno izboljšan podporni vektorski stroj za klasifikacijo galaksij", Tehnike in instrumenti RAS 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung in Chen-Yu Liu, »Kvantno izboljšan podporni vektorski stroj za obsežno zvezdno klasifikacijo s pospeškom GPU«, arXiv: 2311.12328, (2023).

[5] Supanut Thanasilp, Samson Wang, M. Cerezo in Zoë Holmes, "Eksponentna koncentracija in nezmožnost usposabljanja v metodah kvantnega jedra", arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka in Naoki Yamamoto, "Kvantno-klasične hibridne nevronske mreže v režimu nevronskega tangentnega jedra", Kvantna znanost in tehnologija 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo in Rudy Raymond, »Kvantno strojno učenje na skorajšnjih kvantnih napravah: trenutno stanje nadzorovanih in nenadzorovanih tehnik za aplikacije v resničnem svetu« arXiv: 2307.00908, (2023).

[8] Raoul Heese, Thore Gerlach, Sascha Mücke, Sabine Müller, Matthias Jakobs in Nico Piatkowski, »Razlaga kvantnih vezij s Shapleyjevimi vrednostmi: na poti k razložljivemu kvantnemu strojnemu učenju«, arXiv: 2301.09138, (2023).

[9] Julien Gacon, Jannes Nys, Riccardo Rossi, Stefan Woerner in Giuseppe Carleo, »Variational Quantum Time Evolution without the Quantum Geometric Tensor«, arXiv: 2303.12839, (2023).

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

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie in Tim Scanlon, "Rekonstrukcija segmentov sledi nabitih delcev s kvantno izboljšanim podpornim vektorskim strojem", arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick in Thomas Ward, »Model izvajalnega časa vezja in njegove posledice za kvantna jedra pri praktičnih velikostih nabora podatkov«, arXiv: 2307.04980, (2023).

[13] Samantha V. Barron, Daniel J. Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler in Stefan Woerner, »Dokazljive meje za brezšumne pričakovane vrednosti, izračunane iz šumnih vzorcev«, arXiv: 2312.00733, (2023).

[14] M. Emre Sahin, Benjamin CB Symons, Pushpak Pati, Fayyaz Minhas, Declan Millar, Maria Gabrani, Jan Lukas Robertus in Stefano Mensa, »Učinkovita optimizacija parametrov za kvantno poravnavo jedra: pristop podvzorčenja pri variacijskem treningu« , arXiv: 2401.02879, (2024).

Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2024-01-12 02:12:22). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.

On Crossref je navedel storitev ni bilo najdenih podatkov o navajanju del (zadnji poskus 2024-01-12 02:12:21).

Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.

Časovni žig:

Več od Quantum Journal