La complexité des machines à vecteurs de support quantiques

La complexité des machines à vecteurs de support quantiques

Horodatage: 11 janvier 2024 9:08 AM
Nœud source: 3057476

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

1Institut de Physique, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – Zurich
3Département de physique, ETH Zurich

Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.

Abstract

Les machines à vecteurs de support quantiques utilisent des circuits quantiques pour définir la fonction du noyau. Il a été démontré que cette approche offre une accélération exponentielle prouvable par rapport à tout algorithme classique connu pour certains ensembles de données. L'apprentissage de tels modèles correspond à la résolution d'un problème d'optimisation convexe soit via sa formulation primale, soit via sa formulation dual. En raison de la nature probabiliste de la mécanique quantique, les algorithmes d’entraînement sont affectés par une incertitude statistique, ce qui a un impact majeur sur leur complexité. Nous montrons que le double problème peut être résolu dans les évaluations de circuits quantiques $O(M^{4.67}/varepsilon^2)$, où $M$ désigne la taille de l'ensemble de données et $varepsilon$ la précision de la solution par rapport à l'idéal. résultent de valeurs attendues exactes, qui ne peuvent être obtenues qu’en théorie. Nous prouvons sous une hypothèse motivée empiriquement que le problème primal kernelisé peut alternativement être résolu dans des évaluations $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ en employant une généralisation d'un classique connu algorithme appelé Pegasos. Les résultats empiriques qui les accompagnent démontrent que ces complexités analytiques sont fondamentalement étroites. De plus, nous étudions une approximation variationnelle des machines à vecteurs de support quantiques et montrons que leur formation heuristique permet d'obtenir une mise à l'échelle considérablement meilleure dans nos expériences.

Image présentée : Estimation de la valeur du noyau $k(mathbf{x}_i, mathbf{x}_j)$, où $mathcal{E}(mathbf{x}_i)$ désigne un unitaire paramétré par les données $mathbf{x }_i$. Le nombre de tirs est donné par $R$ qui contrôle la précision de l'estimation du noyau.

Résumé populaire

Les machines à vecteurs de support quantiques sont candidates pour démontrer un avantage quantique dans un avenir proche pour les problèmes de classification. L’idée est qu’une fonction de noyau (espérons-le utile) est donnée par un circuit quantique efficace qui est classiquement difficile à évaluer. En raison de la nature probabiliste de la mécanique quantique, ces fonctions du noyau sont affectées par une incertitude statistique. Dans ce travail, nous analysons rigoureusement l'impact de cette incertitude (également appelée bruit de tir) sur la complexité informatique globale pour résoudre le problème de classification.

► Données BibTeX

► Références

J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe et S. Lloyd. Apprentissage automatique quantique. Nature, 549(7671) :195-202, 2017. DOI : 10.1038/​nature23474.
https: / / doi.org/ 10.1038 / nature23474

V. Havlíček, AD Córcoles, K. Temme, AW Harrow, A. Kandala, JM Chow et JM Gambetta. Apprentissage supervisé avec des espaces de fonctionnalités améliorés quantiquement. Nature, 567(7747):209-212, 2019. DOI : 10.1038/​s41586-019-0980-2.
https:/​/​doi.org/​10.1038/​s41586-019-0980-2

A. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli et S. Woerner. La puissance des réseaux de neurones quantiques. Nature Computational Science, 1 (juin), 2020. DOI : 10.1038/​s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

Y. Liu, S. Arunachalam et K. Temme. Une accélération quantique rigoureuse et robuste dans l’apprentissage automatique supervisé. Physique de la nature, 2021. DOI : 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

S. Aaronson. Lisez les petits caractères. Physique de la nature, 11(4):291-293, 2015. DOI : 10.1038/​nphys3272.
https: / / doi.org/ 10.1038 / nphys3272

E.Tang. Un algorithme classique d'inspiration quantique pour les systèmes de recommandation. Dans Actes du 51e Symposium annuel ACM SIGACT sur la théorie de l'informatique, STOC 2019, pages 217-228, New York, NY, États-Unis, 2019. Association for Computing Machinery. DOI : 10.1145/​3313276.3316310.
https: / / doi.org/ 10.1145 / 3313276.3316310

N.-H. Chia, A. Gilyén, T. Li, H.-H. Lin, E. Tang et C. Wang. Cadre arithmétique matriciel sublinéaire de bas rang basé sur l'échantillonnage pour déquantifier l'apprentissage automatique quantique, pages 387 à 400. Association for Computing Machinery, New York, NY, États-Unis, 2020. Disponible en ligne : https:/​/​doi.org/​10.1145/​3357713.3384314.
https: / / doi.org/ 10.1145 / 3357713.3384314

T. Li, S. Chakrabarti et X. Wu. Algorithmes quantiques sublinéaires pour la formation de classificateurs linéaires et basés sur le noyau. Dans Conférence internationale sur l'apprentissage automatique, pages 3815 à 3824. PMLR, 2019.

S. Thanasilp, S. Wang, M. Cerezo et Z. Holmes. Concentration exponentielle et non-entraînement dans les méthodes du noyau quantique, 2022. DOI : 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

S. Shalev-Shwartz et N. Srebro. Optimisation SVM : dépendance inverse de la taille de l'ensemble d'entraînement. Actes de la 25e Conférence internationale sur l'apprentissage automatique, pages 928-935, 2008.

A. Thomsen. Comparaison des réseaux de neurones quantiques et des machines à vecteurs de support quantiques. Mémoire de master, ETH Zurich, 2021-09-06. DOI : 20.500.11850/​527559.

B.E. Boser, I.M. Guyon et V.N. Vapnik. Un algorithme de formation pour les classificateurs de marge optimale. Dans Actes du cinquième atelier annuel sur la théorie de l'apprentissage informatique, COLT '92, pages 144-152, New York, NY, États-Unis, 1992. Association for Computing Machinery. DOI : 10.1145/​130385.130401.
https: / / doi.org/ 10.1145 / 130385.130401

C. Cortés et V. Vapnik. Réseaux de vecteurs de support. Dans Apprentissage automatique, pages 273 à 297, 1995.

V.N. Vapnik. La nature de la théorie de l'apprentissage statistique. Springer Science+Business Media, LLC, 2000.

F. Pedregosa et al. Scikit-learn : apprentissage automatique en Python. Journal of Machine Learning Research, 12(85):2825–2830, 2011. Disponible en ligne : http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

S. Boyd et L. Vandenberghe. Optimisation convexe. La Presse de l'Universite de Cambridge, 2004.

S. Shalev-Shwartz, Y. Singer, N. Srebro et A. Cotter. Pegasos : solveur de sous-gradient estimé primordial pour SVM. Programmation mathématique, 127(1):3–30, 2011. DOI : 10.1007/​s10107-010-0420-4.
https:/​/​doi.org/​10.1007/​s10107-010-0420-4

MDS Anis et al. Qiskit : Un framework open source pour l'informatique quantique, 2021. DOI : 10.5281/​zenodo.2573505.
https: / / doi.org/ 10.5281 / zenodo.2573505

P. Rebentrost, M. Mohseni et S. Lloyd. Machine vectorielle de support quantique pour la classification des mégadonnées. Lettres d'examen physique, 113(3):1–5, 2014. DOI : 10.1103/​PhysRevLett.113.130503.
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503

J. Kübler, S. Buchholz et B. Schölkopf. Le biais inductif des noyaux quantiques. Dans M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang et J. W. Vaughan, éditeurs, Advances in Neural Information Processing Systems, volume 34, pages 12661-12673. Curran Associates, Inc., 2021. Disponible en ligne : https:/​/​proceedings.neurips.cc/​paper_files/​paper/​2021/​file/​69adc1e107f7f7d035d7baf04342e1ca-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper_files/​paper/​2021/​file/​69adc1e107f7f7d035d7baf04342e1ca-Paper.pdf

V. Heyraud, Z. Li, Z. Denis, A. Le Boité et C. Ciuti. Machines à noyau quantique bruyantes. Phys. Rév. A, 106 :052421, 2022. DOI : 10.1103/​PhysRevA.106.052421.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

CJC Burges et CJC Burges. Un didacticiel sur les machines à vecteurs de support pour la reconnaissance de formes. Data Mining and Knowledge Discovery, 2:121–167, 1998. Disponible en ligne : https:/​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -machines-pour-la-reconnaissance-de-formes/​.
https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector-machines-for-pattern-recognition/​

M. Cerezo, A. Sone, T. Volkoff, L. Cincio et P. J. Coles. Plateaux stériles dépendant de la fonction de coût dans des circuits quantiques paramétrés peu profonds. Nature Communications, 12(1):1791, 2021. DOI : 10.1038/​s41467-021-21728-w.
https: / / doi.org/ 10.1038 / s41467-021-21728-w

Belis, Vasilis, González-Castillo, Samuel, Reissel, Christina, Vallecorsa, Sofia, Combarro, Elías F., Dissertori, Günther et Reiter, Florentin. Analyse de Higgs avec classificateurs quantiques. Conférence Web EPJ, 251:03070, 2021. DOI : 10.1051/​epjconf/​202125103070.
https://​/​doi.org/​10.1051/​epjconf/​202125103070

M. Cerezo, A. Arrasmith, R. Babbush, SC Benjamin, S. Endo, K. Fujii, JR McClean, K. Mitarai, X. Yuan, L. Cincio et PJ Coles. Algorithmes quantiques variationnels. Nature Reviews Physics, 3(9):625-644, 2021. DOI : 10.1038/​s42254-021-00348-9.
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

R. McGibborn et coll. quadprog : Solveur de programmation quadratique (python). https://​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

Y. Nesterov. Cours d'introduction à l'optimisation convexe : un cours de base. Optimisation appliquée. Springer, 2004. DOI : 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

J. Spall. Un aperçu de la méthode de perturbation simultanée pour une optimisation efficace. John Hopkins APL Technical Digest, 19(4), pages 482-492, 1998.

G. Gentinetta, A. Thomsen, D. Sutter et S. Woerner. Code du manuscrit « La complexité des machines à vecteurs de support quantiques ». 2022. DOI : https://​/​doi.org/​10.5281/​zenodo.6303725.
https: / / doi.org/ 10.5281 / zenodo.6303725

T. Hubregtsen, D. Wierichs, E. Gil-Fuster, P.-J. HS Derks, PK Faehrmann et JJ Meyer. Formation de noyaux d'intégration quantique sur des ordinateurs quantiques à court terme. Phys. Rév. A, 106:042431, 2022. DOI : 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

R. Latala. Quelques estimations de normes de matrices aléatoires. Actes de l'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

R. Vershynine. Introduction à l'analyse non asymptotique de matrices aléatoires. Détection compressée : théorie et applications, pages 210 à 268, 2009. DOI : 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

T. Hofmann, B. Schölkopf et A. J. Smola. Méthodes du noyau dans l'apprentissage automatique. Annales de statistique, 36(3):1171-1220, 2008. DOI : 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / 009053607000000677

J.W. Daniel. Stabilité de la solution de programmes quadratiques définis. Programmation mathématique, 5(1):41-53, 1973. DOI : 10.1007/​BF01580110.
https: / / doi.org/ 10.1007 / BF01580110

Cité par

[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 et Fernando GSL Brandão, « Algorithmes quantiques : une étude des applications et des complexités de bout en bout », arXiv: 2310.03011, (2023).

[2] Maria Schuld et Nathan Killoran, « L'avantage quantique est-il le bon objectif pour l'apprentissage automatique quantique ? », PRX Quantique 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik et Ofer Lahav, « Une machine à vecteurs de support améliorés quantiquement pour la classification des galaxies », Techniques et instruments RAS 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung et Chen-Yu Liu, « Machine à vecteurs de support améliorés quantiquement pour la classification stellaire à grande échelle avec accélération GPU », arXiv: 2311.12328, (2023).

[5] Supanut Thanasilp, Samson Wang, M. Cerezo et Zoë Holmes, « Concentration exponentielle et non entraînement dans les méthodes du noyau quantique », arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka et Naoki Yamamoto, « Réseaux de neurones hybrides quantiques-classiques dans le régime du noyau tangent neuronal », Science et technologie quantiques 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo et Rudy Raymond, « Apprentissage automatique quantique sur les appareils quantiques à court terme : état actuel des techniques supervisées et non supervisées pour les applications du monde réel », arXiv: 2307.00908, (2023).

[8] Raoul Heese, Thore Gerlach, Sascha Mücke, Sabine Müller, Matthias Jakobs et Nico Piatkowski, « Expliquer les circuits quantiques avec les valeurs Shapley : vers un apprentissage automatique quantique explicable », arXiv: 2301.09138, (2023).

[9] Julien Gacon, Jannes Nys, Riccardo Rossi, Stefan Woerner et Giuseppe Carleo, « Evolution temporelle quantique variationnelle sans le tenseur géométrique quantique », arXiv: 2303.12839, (2023).

[10] Gian Gentinetta, David Sutter, Christa Zoufal, Bryce Fuller et Stefan Woerner, « Alignement du noyau quantique avec descente de gradient stochastique », arXiv: 2304.09899, (2023).

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sébastien Rettie et Tim Scanlon, « Reconstruction de segments de traces de particules chargées avec une machine à vecteurs de support améliorée quantique », arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick et Thomas Ward, « Un modèle pour l'exécution de circuits et ses implications pour les noyaux quantiques à des tailles d'ensembles de données pratiques », arXiv: 2307.04980, (2023).

[13] Samantha V. Barron, Daniel J. Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler et Stefan Woerner, « Limites prouvables pour les valeurs d'espérance sans bruit calculées à partir d'échantillons bruyants », arXiv: 2312.00733, (2023).

[14] M. Emre Sahin, Benjamin C. B. Symons, Pushpak Pati, Fayyaz Minhas, Declan Millar, Maria Gabrani, Jan Lukas Robertus et Stefano Mensa, « Optimisation efficace des paramètres pour l'alignement du noyau quantique : une approche de sous-échantillonnage dans la formation variationnelle » , arXiv: 2401.02879, (2024).

Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2024-01-12 02:12:22). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.

On Le service cité par Crossref aucune donnée sur la citation des œuvres n'a été trouvée (dernière tentative 2024-01-12 02:12:21).

Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.

Horodatage:

Plus de Journal quantique