Kompleksiteten til kvantestøttevektormaskiner

Kompleksiteten til kvantestøttevektormaskiner

Tidsstempel: 11. januar 2024 9:08
Kilde node: 3057476

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

1Institutt for fysikk, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – Zürich
3Institutt for fysikk, ETH Zürich

Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.

Abstrakt

Kvantestøttevektormaskiner bruker kvantekretser for å definere kjernefunksjonen. Det har vist seg at denne tilnærmingen tilbyr en påviselig eksponentiell hastighetsøkning sammenlignet med en hvilken som helst kjent klassisk algoritme for visse datasett. Trening av slike modeller tilsvarer å løse et konveks optimaliseringsproblem enten via dens primære eller doble formulering. På grunn av kvantemekanikkens sannsynlige natur, påvirkes treningsalgoritmene av statistisk usikkerhet, noe som har stor innvirkning på kompleksiteten deres. Vi viser at det doble problemet kan løses i $O(M^{4.67}/varepsilon^2)$ kvantekretsevalueringer, der $M$ angir størrelsen på datasettet og $varepsilon$ løsningsnøyaktigheten sammenlignet med den ideelle resultat fra eksakte forventningsverdier, som kun er oppnåelig i teorien. Vi beviser under en empirisk motivert antakelse at det kerneliserte primalproblemet alternativt kan løses i $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$-evalueringer ved å bruke en generalisering av en kjent klassisk algoritme kalt Pegasos. Medfølgende empiriske resultater viser at disse analytiske kompleksitetene i hovedsak er stramme. I tillegg undersøker vi en variasjonstilnærming til kvantestøttevektormaskiner og viser at deres heuristiske trening oppnår betydelig bedre skalering i våre eksperimenter.

Utvalgt bilde: Estimering av kjerneverdien $k(mathbf{x}_i, mathbf{x}_j)$, der $mathcal{E}(mathbf{x}_i)$ angir en enhetlig parametrisert av dataene $mathbf{x }_i$. Antall skudd er gitt av $R$ som kontrollerer nøyaktigheten av kjerneestimering.

Populært sammendrag

Kvantestøttevektormaskiner er kandidater for å demonstrere en kvantefordel i nær fremtid for klassifiseringsproblemer. Tanken er at en (forhåpentligvis nyttig) kjernefunksjon er gitt av en effektiv kvantekrets som er klassisk vanskelig å evaluere. På grunn av kvantemekanikkens sannsynlige natur påvirkes slike kjernefunksjoner av statistisk usikkerhet. I dette arbeidet analyserer vi grundig hvordan denne usikkerheten (også kalt skuddstøy) påvirker den generelle beregningskompleksiteten for å løse klassifiseringsproblemet.

► BibTeX-data

► Referanser

[1] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe og S. Lloyd. Kvantemaskinlæring. 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 og JM Gambetta. Overvåket læring med kvanteforbedrede funksjonsrom. 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 og S. Woerner. Kraften til kvantenevrale nettverk. 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 og K. Temme. En streng og robust kvantehastighet innen overvåket maskinlæring. Nature Physics, 2021. DOI: 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

[5] S. Aaronson. Les den fine skriften. Nature Physics, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https: / / doi.org/ 10.1038 / nphys3272

[6] E. Tang. En kvanteinspirert klassisk algoritme for anbefalingssystemer. I Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, side 217–228, New York, 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 og C. Wang. Sampling-basert sublineær lavrangert matrisearitmetisk rammeverk for avkvantisering av kvantemaskinlæring, side 387–400. Association for Computing Machinery, New York, NY, USA, 2020. Tilgjengelig på nettet: https://​/​doi.org/​10.1145/​3357713.3384314.
https: / / doi.org/ 10.1145 / 3357713.3384314

[8] T. Li, S. Chakrabarti og X. Wu. Sublineære kvantealgoritmer for trening av lineære og kjernebaserte klassifikatoren. I International Conference on Machine Learning, side 3815–3824. PMLR, 2019.

[9] S. Thanasilp, S. Wang, M. Cerezo og Z. Holmes. Eksponentiell konsentrasjon og utrening i kvantekjernemetoder, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

[10] S. Shalev-Shwartz og N. Srebro. SVM-optimalisering: Invers avhengighet av treningssettstørrelse. Proceedings of the 25th International Conference on Machine Learning, side 928–935, 2008.

[11] A. Thomsen. Sammenligning av kvantenevrale nettverk og kvantestøttevektormaskiner. Masteroppgave, ETH Zürich, 2021-09-06. DOI: 20.500.11850/​527559.

[12] BE Boser, IM Guyon og VN Vapnik. En treningsalgoritme for Optimal Margin Classifiers. I Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, side 144–152, New York, NY, USA, 1992. Association for Computing Machinery. DOI: 10.1145/​130385.130401.
https: / / doi.org/ 10.1145 / 130385.130401

[13] C. Cortes og V. Vapnik. Støtte-vektor nettverk. I Machine Learning, side 273–297, 1995.

[14] VN Vapnik. Naturen til statistisk læringsteori. Springer Science+Business Media, LLC, 2000.

[15] F. Pedregosa et al. Scikit-learn: Maskinlæring i Python. Journal of Machine Learning Research, 12(85):2825–2830, 2011. Tilgjengelig på nettet: http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

[16] S. Boyd og L. Vandenberghe. Konveks optimalisering. Cambridge University Press, 2004.

[17] S. Shalev-Shwartz, Y. Singer, N. Srebro og A. Cotter. Pegasos: Primal estimert subgradientløser for SVM. Matematisk programmering, 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: 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 og S. Lloyd. Kvantestøtte vektormaskin for stordataklassifisering. 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 og B. Schölkopf. Den induktive skjevheten til kvantekjerner. I M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang og JW Vaughan, redaktører, Advances in Neural Information Processing Systems, bind 34, side 12661–12673. Curran Associates, Inc., 2021. Tilgjengelig på nettet: 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é og C. Ciuti. Støyende kvantekjernemaskiner. Phys. Rev. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

[22] CJC Burges og CJC Burges. En veiledning om støtte for vektormaskiner for mønstergjenkjenning. Data Mining and Knowledge Discovery, 2:121–167, 1998. Tilgjengelig på nettet: https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -maskiner-for-mønstergjenkjenning/​.
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 og PJ Coles. Kostnadsfunksjonsavhengige golde platåer i grunne parametriserte kvantekretser. 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 og Reiter, Florentin. Higgs-analyse med kvanteklassifiserere. 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 og PJ Coles. Varierende kvantealgoritmer. 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: Kvadratisk programmeringsløser (python). https://​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

[27] Y. Nesterov. Innledende forelesninger om konveks optimalisering: Et grunnkurs. Anvendt optimalisering. Springer, 2004. DOI: 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] J. Spall. En oversikt over metoden for samtidig forstyrrelse for effektiv optimalisering. John Hopkins APL Technical Digest, 19(4), side 482–492, 1998.

[29] G. Gentinetta, A. Thomsen, D. Sutter og S. Woerner. Kode for manuskript "Kompleksiteten til kvantestøttevektormaskiner". 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 og JJ Meyer. Trening av kvanteinnbyggingskjerner på kortsiktige kvantedatamaskiner. Phys. Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] R. Latała. Noen estimater av normer for tilfeldige matriser. 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. Introduksjon til ikke-asymptotisk analyse av tilfeldige matriser. Compressed Sensing: Theory and Applications, side 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

[33] T. Hofmann, B. Schölkopf og AJ Smola. Kjernemetoder i maskinlæring. Annals of Statistics, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / 009053607000000677

[34] JW Daniel. Stabilitet av løsningen av bestemte kvadratiske programmer. Mathematical Programmering, 5(1):41–53, 1973. DOI: 10.1007/​BF01580110.
https: / / doi.org/ 10.1007 / BF01580110

Sitert av

[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 og Fernando GSL Brandão, "Kvantealgoritmer: En undersøkelse av applikasjoner og ende-til-ende kompleksitet", arxiv: 2310.03011, (2023).

[2] Maria Schuld og Nathan Killoran, "Er Quantum Advantage det riktige målet for kvantemaskinlæring?", PRX Quantum 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik og Ofer Lahav, "En kvanteforbedret støttevektormaskin for galakseklassifisering", RAS-teknikker og -instrumenter 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung og 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 og Zoë Holmes, "Eksponentiell konsentrasjon og utrening i kvantekjernemetoder", arxiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka og Naoki Yamamoto, "Kvanteklassiske hybride nevrale nettverk i det nevrale tangentkjerneregimet", Kvantevitenskap og teknologi 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo og Rudy Raymond, "Quante Machine Learning on Near-Term Quantum Devices: Current State of Supervised and Unsupervised Techniques for Real-World Applications", arxiv: 2307.00908, (2023).

[8] Raoul Heese, Thore Gerlach, Sascha Mücke, Sabine Müller, Matthias Jakobs og Nico Piatkowski, "Explaining Quantum Circuits with Shapley Values: Towards Explainable Quantum Machine Learning", arxiv: 2301.09138, (2023).

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

[10] Gian Gentinetta, David Sutter, Christa Zoufal, Bryce Fuller og Stefan Woerner, "Quantum Kernel Alignment with Stokastic Gradient Descent", arxiv: 2304.09899, (2023).

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie og Tim Scanlon, "Rekonstruere ladede partikkelsporsegmenter med en kvanteforsterket støttevektormaskin", arxiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick og Thomas Ward, "A Model for Circuit Execution Runtime And Its Impplications for Quantum Kernels at Practical Data Set Sizes", arxiv: 2307.04980, (2023).

[13] Samantha V. Barron, Daniel J. Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler og Stefan Woerner, "Provable bounds for noise-free expectations values ​​computed from noisy samples", arxiv: 2312.00733, (2023).

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

Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2024-01-12 02:12:22). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.

On Crossrefs siterte tjeneste ingen data om sitering av verk ble funnet (siste forsøk 2024-01-12 02:12:21).

Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.

Tidstempel:

Mer fra Kvantejournal