Die Komplexität von Quanten-Support-Vektor-Maschinen

Die Komplexität von Quanten-Support-Vektor-Maschinen

Zeitstempel: 11. Januar 2024, 9:08 Uhr
Quellknoten: 3057476

Gian Gentinetta1,2, Arne Thomsen3,2, David Sutter2, und Stefan Wörner2

1Institut für Physik, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – Zürich
3Departement Physik, ETH Zürich

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Quanten-Support-Vektor-Maschinen nutzen Quantenschaltkreise, um die Kernelfunktion zu definieren. Es hat sich gezeigt, dass dieser Ansatz im Vergleich zu allen bekannten klassischen Algorithmen für bestimmte Datensätze eine nachweisbare exponentielle Beschleunigung bietet. Das Training solcher Modelle entspricht der Lösung eines konvexen Optimierungsproblems entweder über seine primäre oder duale Formulierung. Aufgrund der probabilistischen Natur der Quantenmechanik unterliegen die Trainingsalgorithmen einer statistischen Unsicherheit, die einen großen Einfluss auf ihre Komplexität hat. Wir zeigen, dass das duale Problem in $O(M^{4.67}/varepsilon^2)$ Quantenschaltkreisauswertungen gelöst werden kann, wobei $M$ die Größe des Datensatzes und $varepsilon$ die Lösungsgenauigkeit im Vergleich zum Ideal bezeichnet ergeben sich aus exakten Erwartungswerten, die nur theoretisch erreichbar sind. Wir beweisen unter einer empirisch motivierten Annahme, dass das Kernel-Primalproblem alternativ in $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$-Auswertungen gelöst werden kann, indem eine Verallgemeinerung eines bekannten Klassikers verwendet wird Algorithmus namens Pegasos. Begleitende empirische Ergebnisse zeigen, dass diese analytischen Komplexitäten im Wesentlichen eng sind. Darüber hinaus untersuchen wir eine Variationsnäherung an Quanten-Support-Vektor-Maschinen und zeigen, dass deren heuristisches Training in unseren Experimenten eine deutlich bessere Skalierung erreicht.

Ausgewähltes Bild: Schätzung des Kernelwerts $k(mathbf{x}_i, mathbf{x}_j)$, wobei $mathcal{E}(mathbf{x}_i)$ eine durch die Daten $mathbf{x parametrisierte Einheitsgröße bezeichnet }_i$. Die Anzahl der Schüsse wird durch $R$ angegeben, was die Genauigkeit der Kernelschätzung steuert.

Populäre Zusammenfassung

Quanten-Support-Vektor-Maschinen sind Kandidaten, um in naher Zukunft einen Quantenvorteil bei Klassifizierungsproblemen zu demonstrieren. Die Idee ist, dass eine (hoffentlich nützliche) Kernelfunktion durch einen effizienten Quantenschaltkreis gegeben ist, der klassischerweise schwer zu bewerten ist. Aufgrund der probabilistischen Natur der Quantenmechanik sind solche Kernelfunktionen von statistischer Unsicherheit betroffen. In dieser Arbeit analysieren wir eingehend, wie sich diese Unsicherheit (auch Schrotrauschen genannt) auf die gesamte Rechenkomplexität zur Lösung des Klassifizierungsproblems auswirkt.

► BibTeX-Daten

► Referenzen

[1] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe und S. Lloyd. Quantenmaschinelles Lernen. 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 und JM Gambetta. Überwachtes Lernen mit quantenverstärkten Merkmalsräumen. 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 und S. Woerner. Die Kraft quanten neuronaler Netze. 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 und K. Temme. Eine rigorose und robuste Quantenbeschleunigung beim überwachten maschinellen Lernen. Nature Physics, 2021. DOI: 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

[5] S. Aaronson. Lesen Sie das Kleingedruckte. Nature Physics, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https: / / doi.org/ 10.1038 / nphys3272

[6] E. Tang. Ein quanteninspirierter klassischer Algorithmus für Empfehlungssysteme. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Seite 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 und C. Wang. Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning, Seite 387–400. Association for Computing Machinery, New York, NY, USA, 2020. Online verfügbar: https://​/​doi.org/​10.1145/​3357713.3384314.
https: / / doi.org/ 10.1145 / 3357713.3384314

[8] T. Li, S. Chakrabarti und X. Wu. Sublineare Quantenalgorithmen zum Training linearer und kernbasierter Klassifikatoren. In International Conference on Machine Learning, Seiten 3815–3824. PMLR, 2019.

[9] S. Thanasilp, S. Wang, M. Cerezo und Z. Holmes. Exponentielle Konzentration und Untrainierbarkeit in Quantenkernmethoden, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

[10] S. Shalev-Shwartz und N. Srebro. SVM-Optimierung: Inverse Abhängigkeit von der Trainingssatzgröße. Tagungsband der 25. Internationalen Konferenz zum maschinellen Lernen, Seiten 928–935, 2008.

[11] A. Thomsen. Vergleich von Quanten-Neuronalen Netzen und Quanten-Support-Vektor-Maschinen. Masterarbeit, ETH Zürich, 2021. DOI: 09/​06.

[12] BE Boser, IM Guyon und VN Vapnik. Ein Trainingsalgorithmus für optimale Margin-Klassifikatoren. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, Seiten 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 und V. Vapnik. Support-Vektor-Netzwerke. In Machine Learning, Seiten 273–297, 1995.

[14] VN Vapnik. Die Natur der statistischen Lerntheorie. Springer Science+Business Media, LLC, 2000.

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

[16] S. Boyd und L. Vandenberghe. Konvexe Optimierung. Cambridge University Press, 2004.

[17] S. Shalev-Shwartz, Y. Singer, N. Srebro und A. Cotter. Pegasos: Ursprünglich geschätzter Subgradientenlöser für SVM. Mathematical Programming, 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 und S. Lloyd. Quanten-Support-Vektor-Maschine für die Big-Data-Klassifizierung. 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 und B. Schölkopf. Die induktive Vorspannung von Quantenkernen. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang und JW Vaughan, Herausgeber, Advances in Neural Information Processing Systems, Band 34, Seiten 12661–12673. Curran Associates, Inc., 2021. Online verfügbar: 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é und C. Ciuti. Verrauschte Quantenkernmaschinen. Physik. Rev. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

[22] CJC Burges und CJC Burges. Ein Tutorial zu Support-Vektor-Maschinen zur Mustererkennung. Data Mining and Knowledge Discovery, 2:121–167, 1998. Online verfügbar: https://www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -Maschinen-zur-Mustererkennung/​.
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 und PJ Coles. Kostenfunktionsabhängige karge Plateaus in flach parametrisierten Quantenschaltkreisen. 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 und Reiter, Florentin. Higgs-Analyse mit Quantenklassifikatoren. 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 und PJ Coles. Variationale Quantenalgorithmen. 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: Quadratischer Programmierlöser (Python). https://​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

[27] Y. Nesterov. Einführungsvorlesungen zur konvexen Optimierung: Ein Grundkurs. Angewandte Optimierung. Springer, 2004. DOI: 10.1007/978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] J. Spall. Ein Überblick über die Simultanstörungsmethode zur effizienten Optimierung. John Hopkins APL Technical Digest, 19(4), Seiten 482–492, 1998.

[29] G. Gentinetta, A. Thomsen, D. Sutter und S. Woerner. Code für Manuskript „Die Komplexität von Quanten-Support-Vektor-Maschinen“. 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 und JJ Meyer. Training von Quanteneinbettungskernen auf kurzfristigen Quantencomputern. Physik. Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] R. Latała. Einige Schätzungen der Normen von Zufallsmatrizen. 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. Werschynin. Einführung in die nicht-asymptotische Analyse von Zufallsmatrizen. Compressed Sensing: Theory and Applications, Seiten 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

[33] T. Hofmann, B. Schölkopf und AJ Smola. Kernel-Methoden im maschinellen Lernen. Annals of Statistics, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / 009053607000000677

[34] JW Daniel. Stabilität der Lösung bestimmter quadratischer Programme. Mathematical Programming, 5(1):41–53, 1973. DOI: 10.1007/​BF01580110.
https: / / doi.org/ 10.1007 / BF01580110

Zitiert von

[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 und Fernando GSL Brandão, „Quantenalgorithmen: Eine Übersicht über Anwendungen und End-to-End-Komplexitäten“, arXiv: 2310.03011, (2023).

[2] Maria Schuld und Nathan Killoran, „Ist Quantum Advantage das richtige Ziel für Quantum Machine Learning?“, PRX-Quantum 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik und Ofer Lahav, „Eine quantenverstärkte Support-Vektor-Maschine für die Galaxienklassifizierung“, RAS Techniken und Instrumente 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung und 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 und Zoë Holmes, „Exponentielle Konzentration und Untrainierbarkeit bei Quantenkernmethoden“, arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka und Naoki Yamamoto, „Quantum-classical hybrid Neural Networks in the Neural Tangent Kernel Regime“, Quantenwissenschaft und -technologie 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo und 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 und 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 und Giuseppe Carleo, „Variative Quantenzeitentwicklung ohne den quantengeometrischen Tensor“, arXiv: 2303.12839, (2023).

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

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie und Tim Scanlon, „Rekonstruktion geladener Teilchenspursegmente mit einer quantenverstärkten Support-Vektor-Maschine“, arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick und Thomas Ward, „Ein Modell für die Laufzeit der Schaltungsausführung und ihre Auswirkungen auf Quantenkerne bei praktischen Datensatzgrößen“, arXiv: 2307.04980, (2023).

[13] Samantha V. Barron, Daniel J. Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler und Stefan Woerner, „Beweisbare Grenzen für rauschfreie Erwartungswerte, die aus verrauschten Proben berechnet wurden“, arXiv: 2312.00733, (2023).

[14] M. Emre Sahin, Benjamin CB Symons, Pushpak Pati, Fayyaz Minhas, Declan Millar, Maria Gabrani, Jan Lukas Robertus und Stefano Mensa, „Effiziente Parameteroptimierung für die Quantenkernausrichtung: Ein Unterabtastansatz im Variationstraining“ , arXiv: 2401.02879, (2024).

Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2024, 01:12:02 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.

On Der von Crossref zitierte Dienst Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2024-01-12 02:12:21).

Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.

Zeitstempel:

Mehr von Quantenjournal