Kompleksiteten af ​​kvantestøttevektormaskiner

Kompleksiteten af ​​kvantestøttevektormaskiner

Tidsstempel: 11. januar 2024 kl. 9
Kildeknude: 3057476

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

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

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Kvantestøttevektormaskiner anvender kvantekredsløb til at definere kernefunktionen. Det har vist sig, at denne tilgang tilbyder en beviselig eksponentiel fremskyndelse sammenlignet med enhver kendt klassisk algoritme for visse datasæt. Træningen af ​​sådanne modeller svarer til at løse et konveks optimeringsproblem enten via dets primære eller dobbelte formulering. På grund af kvantemekanikkens probabilistiske karakter er træningsalgoritmerne påvirket af statistisk usikkerhed, hvilket har stor indflydelse på deres kompleksitet. Vi viser, at det dobbelte problem kan løses i $O(M^{4.67}/varepsilon^2)$ kvantekredsløbsevalueringer, hvor $M$ angiver størrelsen af ​​datasættet og $varepsilon$ løsningsnøjagtigheden sammenlignet med den ideelle resultat af nøjagtige forventningsværdier, som kun kan opnås i teorien. Vi beviser under en empirisk motiveret antagelse, at det kerneliserede primalproblem alternativt kan løses i $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ evalueringer ved at anvende en generalisering af en kendt klassisk algoritme kaldet Pegasos. Medfølgende empiriske resultater viser, at disse analytiske kompleksiteter i det væsentlige er stramme. Derudover undersøger vi en variationsmæssig tilnærmelse til kvantestøttevektormaskiner og viser, at deres heuristiske træning opnår betydeligt bedre skalering i vores eksperimenter.

Udvalgt billede: Estimering af kerneværdien $k(mathbf{x}_i, mathbf{x}_j)$, hvor $mathcal{E}(mathbf{x}_i)$ angiver en enhedsparametriseret af dataene $mathbf{x }_i$. Antallet af skud er givet af $R$, som styrer nøjagtigheden af ​​kerneestimeringen.

Populært resumé

Kvantestøttevektormaskiner er kandidater til at demonstrere en kvantefordel i den nærmeste fremtid for klassificeringsproblemer. Tanken er, at en (forhåbentlig nyttig) kernefunktion er givet af et effektivt kvantekredsløb, som er klassisk svært at evaluere. På grund af kvantemekanikkens probabilistiske karakter er sådanne kernefunktioner påvirket af statistisk usikkerhed. I dette arbejde analyserer vi nøje, hvordan denne usikkerhed (også kaldet skudstøj) påvirker den overordnede beregningsmæssige kompleksitet til løsning af klassifikationsproblemet.

► BibTeX-data

► Referencer

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

[2] V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow og J. M. Gambetta. Overvåget læring med kvanteforstærkede funktionsrum. 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 i kvanteneurale netværk. 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 kvantehastighed i overvåget maskinlæring. Nature Physics, 2021. DOI: 10.1038/​s41567-021-01287-z.
https://​/​doi.org/​10.1038/​s41567-021-01287-z

[5] S. Aaronson. Læs det med småt. Nature Physics, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https://doi.org/​10.1038/​nphys3272

[6] E. Tang. En kvanteinspireret klassisk algoritme til 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-baseret sublineær lav-rangs matrix aritmetisk ramme for afkvantisering af kvantemaskinelæring, side 387–400. Association for Computing Machinery, New York, NY, USA, 2020. Tilgængelig online: 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 til træning af lineære og kernebaserede klassifikatorer. I International Conference on Machine Learning, side 3815–3824. PMLR, 2019.

[9] S. Thanasilp, S. Wang, M. Cerezo og Z. Holmes. Eksponentiel koncentration og utrænerbarhed i kvantekernemetoder, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

[10] S. Shalev-Shwartz og N. Srebro. SVM-optimering: Omvendt afhængighed af træningssættets størrelse. Proceedings of the 25th International Conference on Machine Learning, side 928-935, 2008.

[11] A. Thomsen. Sammenligning af kvanteneurale netværk og kvantestøttevektormaskiner. Kandidatafhandling, ETH Zürich, 2021-09-06. DOI: 20.500.11850/​527559.

[12] BE Boser, IM Guyon og VN Vapnik. En træningsalgoritme 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. Support-vektor netværk. I Machine Learning, side 273-297, 1995.

[14] V. N. Vapnik. Naturen af ​​statistisk læringsteori. Springer Science+Business Media, LLC, 2000.

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

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

[17] S. Shalev-Shwartz, Y. Singer, N. Srebro og A. Cotter. Pegasos: Primal estimeret sub-gradient solver 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] M.D.S. 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. Quantum support vektor maskine til big data klassificering. 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 skævhed af kvantekerner. I M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang og J. W. Vaughan, redaktører, Advances in Neural Information Processing Systems, bind 34, side 12661-12673. Curran Associates, Inc., 2021. Tilgængelig online: 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øjende kvantekernemaskiner. Phys. Rev. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https://​/​doi.org/​10.1103/​PhysRevA.106.052421

[22] C. J. C. Burges og C. J. C. Burges. En vejledning om understøttelse af vektormaskiner til mønstergenkendelse. Data Mining and Knowledge Discovery, 2:121–167, 1998. Tilgængelig online: https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -maskiner-til-mønstergenkendelse/​.
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 P.J. Coles. Omkostningsfunktionsafhængige golde plateauer i lavvandede parametriserede kvantekredsløb. 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 kvanteklassifikatorer. 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, S.C. Benjamin, S. Endo, K. Fujii, J.R. McClean, K. Mitarai, X. Yuan, L. Cincio og P.J. Coles. Variationelle 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. Indledende forelæsninger om konveks optimering: Et grundkursus. Anvendt optimering. Springer, 2004. DOI: 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] J. Spall. En oversigt over den samtidige forstyrrelsesmetode til effektiv optimering. John Hopkins APL Technical Digest, 19(4), side 482-492, 1998.

[29] G. Gentinetta, A. Thomsen, D. Sutter og S. Woerner. Kode til manuskriptet "Kompleksiteten af ​​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.-J. H. S. Derks, P. K. Faehrmann og J. J. Meyer. Træning af kvanteindlejringskerner på kortsigtede kvantecomputere. Phys. Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https://​/​doi.org/​10.1103/​PhysRevA.106.042431

[31] R. Latała. Nogle estimater af normer for tilfældige matricer. 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. Introduktion til den ikke-asymptotiske analyse af tilfældige matricer. 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 A. J. Smola. Kernelmetoder i maskinlæring. Annals of Statistics, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https://​/​doi.org/​10.1214/​009053607000000677

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

Citeret af

[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, "Quantealgoritmer: En undersøgelse af applikationer og end-to-end kompleksiteter", arXiv: 2310.03011, (2023).

[2] Maria Schuld og Nathan Killoran, "Er Quantum Advantage det rigtige mål for Quantum Machine Learning?", PRX Quantum 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik og Ofer Lahav, "En kvanteforstærket støttevektormaskine til galakseklassificering", 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, "Eksponentiel koncentration og utrænelighed i kvantekernemetoder", arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka og Naoki Yamamoto, "Kvanteklassiske hybride neurale netværk i det neurale tangentkerneregime", Quantum Science and Technology 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo og 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] 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, "Rekonstruering af ladede partikelsporsegmenter med en kvanteforstærket støttevektormaskine", 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 Implikations 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).

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2024-01-12 02:12:22). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2024-01-12 02:12:21).

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.

Tidsstempel:

Mere fra Quantum Journal