De complexiteit van kwantumondersteuningsvectormachines

De complexiteit van kwantumondersteuningsvectormachines

Tijdstempel: 11 januari 2024 9:08 uur
Bronknooppunt: 3057476

Gian Gentinetta1,2, Arne Thomsen3,2, David Sutter2, en Stefan Woerner2

1Instituut voor Natuurkunde, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – Zürich
3Afdeling Natuurkunde, ETH Zürich

Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.

Abstract

Kwantumondersteuningsvectormachines gebruiken kwantumcircuits om de kernelfunctie te definiëren. Er is aangetoond dat deze aanpak een aantoonbare exponentiële versnelling biedt in vergelijking met elk bekend klassiek algoritme voor bepaalde datasets. De training van dergelijke modellen komt overeen met het oplossen van een convex optimalisatieprobleem via de primaire of dubbele formulering ervan. Vanwege het probabilistische karakter van de kwantummechanica worden de trainingsalgoritmen beïnvloed door statistische onzekerheid, wat een grote impact heeft op hun complexiteit. We laten zien dat het dubbele probleem kan worden opgelost in $O(M^{4.67}/varepsilon^2)$ kwantumcircuitevaluaties, waarbij $M$ de omvang van de dataset aangeeft en $varepsilon$ de oplossingsnauwkeurigheid vergeleken met het ideale resulteren uit exacte verwachtingswaarden, die alleen in theorie verkrijgbaar zijn. We bewijzen onder een empirisch gemotiveerde aanname dat het kernelized primaire probleem als alternatief kan worden opgelost in $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ evaluaties door gebruik te maken van een generalisatie van een bekende klassieke algoritme genaamd Pegasos. Begeleidende empirische resultaten tonen aan dat deze analytische complexiteiten in wezen krap zijn. Daarnaast onderzoeken we een variatiebenadering van kwantumondersteuningsvectormachines en laten we zien dat hun heuristische training in onze experimenten een aanzienlijk betere schaalbaarheid bereikt.

Uitgelichte afbeelding: schatting van de kernelwaarde $k(mathbf{x}_i, mathbf{x}_j)$, waarbij $mathcal{E}(mathbf{x}_i)$ een unitair getal aanduidt, geparametriseerd door de gegevens $mathbf{x }_i$. Het aantal schoten wordt gegeven door $R$, wat de nauwkeurigheid van de kernelschatting bepaalt.

Populaire samenvatting

Kwantumondersteuningsvectormachines zijn kandidaten voor het aantonen van een kwantumvoordeel in de nabije toekomst voor classificatieproblemen. Het idee is dat een (hopelijk nuttige) kernelfunctie wordt gegeven door een efficiënt kwantumcircuit dat klassiek moeilijk te evalueren is. Vanwege de probabilistische aard van de kwantummechanica worden dergelijke kernelfuncties beïnvloed door statistische onzekerheid. In dit werk analyseren we rigoureus hoe deze onzekerheid (ook wel schotruis genoemd) de algehele computationele complexiteit voor het oplossen van het classificatieprobleem beïnvloedt.

► BibTeX-gegevens

► Referenties

[1] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe en S. Lloyd. Kwantummachine learning. 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 en JM Gambetta. Begeleid leren met kwantum-verbeterde functieruimten. 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 en S. Woerner. De kracht van kwantumneurale netwerken. Nature Computational Science, 1 (juni), 2020. DOI: 10.1038/​s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] Y. Liu, S. Arunachalam en K. Temme. Een rigoureuze en robuuste kwantumversnelling in begeleid machinaal leren. Natuurfysica, 2021. DOI: 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

[5] S. Aaronson. Lees de kleine lettertjes. Nature Physics, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https: / / doi.org/ 10.1038 / nphys3272

[6] E. Tang. Een kwantumgeïnspireerd klassiek algoritme voor aanbevelingssystemen. In Proceedings of the 51e jaarlijkse ACM SIGACT Symposium on Theory of Computing, STOC 2019, pagina 217–228, New York, NY, VS, 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 en C. Wang. Op steekproeven gebaseerd sublineair matrixrekenkundig raamwerk met lage rangorde voor het dekwantiseren van kwantummachine learning, pagina 387–400. Association for Computing Machinery, New York, NY, VS, 2020. Online beschikbaar: https://​/​doi.org/​10.1145/​3357713.3384314.
https: / / doi.org/ 10.1145 / 3357713.3384314

[8] T. Li, S. Chakrabarti en X. Wu. Sublineaire kwantumalgoritmen voor het trainen van lineaire en kernelgebaseerde classificatoren. In Internationale Conferentie over Machine Learning, pagina's 3815-3824. PMLR, 2019.

[9] S. Thanasilp, S. Wang, M. Cerezo en Z. Holmes. Exponentiële concentratie en ontrainbaarheid in kwantumkernelmethoden, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

[10] S. Shalev-Shwartz en N. Srebro. SVM-optimalisatie: omgekeerde afhankelijkheid van de grootte van de trainingsset. Proceedings of the 25th International Conference on Machine Learning, pagina's 928-935, 2008.

[11] A. Thomsen. Vergelijking van kwantumneurale netwerken en kwantumondersteuningsvectormachines. Masterscriptie, ETH Zürich, 2021-09-06. DOI: 20.500.11850/​527559.

[12] BE Boser, IM Guyon en VN Vapnik. Een trainingsalgoritme voor optimale margeclassificatoren. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, pagina's 144–152, New York, NY, VS, 1992. Association for Computing Machinery. DOI: 10.1145/​130385.130401.
https: / / doi.org/ 10.1145 / 130385.130401

[13] C. Cortes en V. Vapnik. Ondersteuningsvectornetwerken. In Machine Learning, pagina's 273–297, 1995.

[14] VN Vapnik. De aard van de statistische leertheorie. Springer Wetenschap + Zakelijke Media, LLC, 2000.

[15] F. Pedregosa et al. Scikit-learn: machinaal leren in Python. Journal of Machine Learning Research, 12(85):2825–2830, 2011. Online beschikbaar: http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

[16] S. Boyd en L. Vandenberghe. Convexe optimalisatie. Cambridge University Press, 2004.

[17] S. Shalev-Shwartz, Y. Singer, N. Srebro en A. Cotter. Pegasos: Primaire geschatte subgradiëntoplosser voor SVM. Wiskundig programmeren, 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: een opensourceframework voor kwantumcomputing, 2021. DOI: 10.5281/​zenodo.2573505.
https: / / doi.org/ 10.5281 / zenodo.2573505

[19] P. Rebentrost, M. Mohseni en S. Lloyd. Kwantumondersteuningsvectormachine voor big data-classificatie. 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 en B. Schölkopf. De inductieve bias van kwantumkernels. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang en JW Vaughan, redacteuren, Advances in Neural Information Processing Systems, deel 34, pagina's 12661–12673. Curran Associates, Inc., 2021. Online beschikbaar: 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é en C. Ciuti. Lawaaierige kwantumkernelmachines. Fys. Rev. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

[22] CJC Burges en CJC Burges. Een tutorial over ondersteunende vectormachines voor patroonherkenning. Data Mining and Knowledge Discovery, 2:121–167, 1998. Online beschikbaar: https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -machines-voor-patroonherkenning/​.
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 en PJ Coles. Kostenfunctie-afhankelijke kale plateaus in ondiepe geparametriseerde kwantumcircuits. 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 en Reiter, Florentin. Higgs-analyse met kwantumclassificatoren. 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 en PJ Coles. Variationele kwantumalgoritmen. 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: Kwadratische programmeeroplosser (python). https://​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

[27] Y. Nesterov. Inleidende lezingen over convexe optimalisatie: een basiscursus. Toegepaste optimalisatie. Springer, 2004. DOI: 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] J. Spall. Een overzicht van de gelijktijdige verstoringsmethode voor efficiënte optimalisatie. John Hopkins APL Technical Digest, 19(4), pagina's 482-492, 1998.

[29] G. Gentinetta, A. Thomsen, D. Sutter en S. Woerner. Code voor manuscript "De complexiteit van kwantumondersteuningsvectormachines". 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 en JJ Meyer. Het trainen van kwantuminbeddingskernels op kwantumcomputers voor de korte termijn. Fys. Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] R. Latała. Enkele schattingen van normen van willekeurige matrices. 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. Vershynin. Inleiding tot de niet-asymptotische analyse van willekeurige matrices. Compression Sensing: Theory and Applications, pagina's 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

[33] T. Hofmann, B. Schölkopf en AJ Smola. Kernelmethoden in machine learning. Annals of Statistics, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / 009053607000000677

[34] JW Daniël. Stabiliteit van de oplossing van bepaalde kwadratische programma's. Wiskundig programmeren, 5(1):41–53, 1973. DOI: 10.1007/​BF01580110.
https: / / doi.org/ 10.1007 / BF01580110

Geciteerd door

[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 en Fernando GSL Brandão, “Kwantumalgoritmen: een overzicht van applicaties en end-to-end complexiteiten”, arXiv: 2310.03011, (2023).

[2] Maria Schuld en Nathan Killoran, “Is Quantum Advantage het juiste doel voor Quantum Machine Learning?”, PRX Quantum 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik en Ofer Lahav, “Een kwantum-verbeterde ondersteuningsvectormachine voor de classificatie van sterrenstelsels”, RAS-technieken en instrumenten 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung en Chen-Yu Liu, "Quantum-Enhanced Support Vector Machine voor grootschalige sterrenclassificatie met GPU-versnelling", arXiv: 2311.12328, (2023).

[5] Supanut Thanasilp, Samson Wang, M. Cerezo en Zoë Holmes, "Exponentiële concentratie en niet-trainbaarheid in kwantumkernelmethoden", arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka en Naoki Yamamoto, "Kwantum-klassieke hybride neurale netwerken in het neurale tangens-kernregime", Quantum Science and Technology 9, 1 (015022).

[7] Yaswitha Gujju, Atsushi Matsuo en Rudy Raymond, “Quantum Machine Learning op Quantum Devices op korte termijn: huidige staat van technieken onder toezicht en zonder toezicht voor toepassingen in de echte wereld”, arXiv: 2307.00908, (2023).

[8] Raoul Heese, Thore Gerlach, Sascha Mücke, Sabine Müller, Matthias Jakobs en Nico Piatkowski, "Kwantumcircuits uitleggen met Shapley-waarden: op weg naar verklaarbaar kwantummachineleren", arXiv: 2301.09138, (2023).

[9] Julien Gacon, Jannes Nys, Riccardo Rossi, Stefan Woerner en Giuseppe Carleo, "Variationele kwantumtijdevolutie zonder de kwantumgeometrische tensor", arXiv: 2303.12839, (2023).

[10] Gian Gentinetta, David Sutter, Christa Zoufal, Bryce Fuller en Stefan Woerner, "Quantum Kernel Alignment met stochastische gradiëntafdaling", arXiv: 2304.09899, (2023).

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie en Tim Scanlon, "Reconstructie van spoorsegmenten van geladen deeltjes met een kwantumverbeterde ondersteuningsvectormachine", arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick en Thomas Ward, "Een model voor de runtime van circuituitvoering en de implicaties ervan voor kwantumkernels bij praktische datasetgroottes", arXiv: 2307.04980, (2023).

[13] Samantha V. Barron, Daniel J. Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler en Stefan Woerner, "Bewijsbare grenzen voor ruisvrije verwachtingswaarden berekend op basis van luidruchtige monsters", arXiv: 2312.00733, (2023).

[14] M. Emre Sahin, Benjamin CB Symons, Pushpak Pati, Fayyaz Minhas, Declan Millar, Maria Gabrani, Jan Lukas Robertus en Stefano Mensa, "Efficiënte parameteroptimalisatie voor Quantum Kernel Alignment: een sub-sampling-aanpak in variatietraining" , arXiv: 2401.02879, (2024).

Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2024-01-12 02:12:22). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.

On De door Crossref geciteerde service er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2024-01-12 02:12:21).

Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.

Tijdstempel:

Meer van Quantum Journaal