Η πολυπλοκότητα των μηχανών διανυσμάτων κβαντικής υποστήριξης

Η πολυπλοκότητα των μηχανών διανυσμάτων κβαντικής υποστήριξης

Χρονική σήμανση: 11 Ιανουαρίου 2024 9:08 π.μ.
Κόμβος πηγής: 3057476

Τζιαν Τζεντινέτα1,2, Άρνε Τόμσεν3,2, Ντέιβιντ Σάτερ2και ο Stefan Woerner2

1Ινστιτούτο Φυσικής, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – Ζυρίχη
3Τμήμα Φυσικής, ETH Ζυρίχης

Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.

Περίληψη

Οι μηχανές διανυσμάτων κβαντικής υποστήριξης χρησιμοποιούν κβαντικά κυκλώματα για να ορίσουν τη λειτουργία του πυρήνα. Έχει αποδειχθεί ότι αυτή η προσέγγιση προσφέρει μια αποδείξιμη εκθετική επιτάχυνση σε σύγκριση με οποιονδήποτε γνωστό κλασικό αλγόριθμο για ορισμένα σύνολα δεδομένων. Η εκπαίδευση τέτοιων μοντέλων αντιστοιχεί στην επίλυση ενός κυρτού προβλήματος βελτιστοποίησης είτε μέσω της αρχικής είτε της διπλής διατύπωσής του. Λόγω της πιθανολογικής φύσης της κβαντικής μηχανικής, οι αλγόριθμοι εκπαίδευσης επηρεάζονται από στατιστική αβεβαιότητα, η οποία έχει σημαντικό αντίκτυπο στην πολυπλοκότητά τους. Δείχνουμε ότι το διπλό πρόβλημα μπορεί να λυθεί σε αξιολογήσεις κβαντικού κυκλώματος $O(M^{4.67}/varepsilon^2)$, όπου το $M$ υποδηλώνει το μέγεθος του συνόλου δεδομένων και το $varepsilon$ την ακρίβεια της λύσης σε σύγκριση με το ιδανικό προκύπτουν από ακριβείς τιμές προσδοκίας, οι οποίες μπορούν να ληφθούν μόνο στη θεωρία. Αποδεικνύουμε με μια εμπειρικά υποκινούμενη υπόθεση ότι το πυρηνοποιημένο πρωταρχικό πρόβλημα μπορεί εναλλακτικά να λυθεί σε αξιολογήσεις $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ χρησιμοποιώντας μια γενίκευση μιας γνωστής κλασικής αλγόριθμος που ονομάζεται Pegasos. Τα συνοδευτικά εμπειρικά αποτελέσματα δείχνουν ότι αυτές οι αναλυτικές πολυπλοκότητες είναι ουσιαστικά περιορισμένες. Επιπλέον, διερευνούμε μια μεταβλητή προσέγγιση σε μηχανές κβαντικών διανυσμάτων υποστήριξης και δείχνουμε ότι η ευρετική τους εκπαίδευση επιτυγχάνει σημαντικά καλύτερη κλίμακα στα πειράματά μας.

Επιλεγμένη εικόνα: Εκτίμηση της τιμής του πυρήνα $k(mathbf{x}_i, mathbf{x}_j)$, όπου το $mathcal{E}(mathbf{x}_i)$ υποδηλώνει μια ενιαία παραμετροποίηση από τα δεδομένα $mathbf{x }_i$. Ο αριθμός των βολών δίνεται από το $R$ που ελέγχει την ακρίβεια της εκτίμησης του πυρήνα.

Δημοφιλή περίληψη

Οι μηχανές διανυσμάτων κβαντικής υποστήριξης είναι υποψήφιες για να επιδείξουν ένα κβαντικό πλεονέκτημα στο εγγύς μέλλον για προβλήματα ταξινόμησης. Η ιδέα είναι ότι μια (ελπίζουμε χρήσιμη) συνάρτηση πυρήνα δίνεται από ένα αποδοτικό κβαντικό κύκλωμα που είναι κλασικά δύσκολο να αξιολογηθεί. Λόγω της πιθανολογικής φύσης της κβαντικής μηχανικής, τέτοιες συναρτήσεις πυρήνα επηρεάζονται από στατιστική αβεβαιότητα. Σε αυτήν την εργασία, αναλύουμε αυστηρά πώς αυτή η αβεβαιότητα (που ονομάζεται επίσης θόρυβος βολής) επηρεάζει τη συνολική υπολογιστική πολυπλοκότητα για την επίλυση του προβλήματος ταξινόμησης.

► Δεδομένα BibTeX

► Αναφορές

[1] J. Biamonte, Ρ. Wittek, Ν. Pancotti, Ρ. Rebentrost, Ν. Wiebe, and S. Lloyd. Κβαντική μηχανική μάθηση. 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 και J. M. Gambetta. Εποπτευόμενη μάθηση με κβαντικά ενισχυμένους χώρους χαρακτηριστικών. Nature, 567(7747):209–212, 2019. DOI: 10.1038/​s41586-019-0980-2.
https:/​/​doi.org/​10.1038/​s41586-019-0980-2

[3] Α. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli και S. Woerner. Η δύναμη των κβαντικών νευρωνικών δικτύων. Nature Computational Science, 1 (Ιούνιος), 2020. DOI: 10.1038/​s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] Y. Liu, S. Arunachalam, and K. Temme. Μια αυστηρή και ισχυρή κβαντική επιτάχυνση στην εποπτευόμενη μηχανική εκμάθηση. Nature Physics, 2021. DOI: 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

[5] S. Aaronson. Διαβάστε τα ψιλά γράμματα. Nature Physics, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https: / / doi.org/ 10.1038 / nphys3272

[6] Ε. Τανγκ. Ένας κβαντικός κλασικός αλγόριθμος για συστήματα συστάσεων. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 217–228, New York, NY, USA, 2019. Association for Computing Machinery. DOI: 10.1145/​3313276.3316310.
https: / / doi.org/ 10.1145 / 3313276.3316310

[7] Ν.-Η. Chia, A. Gilyén, T. Li, H.-H. Lin, Ε. Tang και C. Wang. Βασισμένο σε δειγματοληψία Υπογραμμικό Αριθμητικό Πλαίσιο Πίνακα Χαμηλής Κατάταξης για Αποκβαντική Εκμάθηση Κβαντικής Μηχανής, σελίδα 387–400. Association for Computing Machinery, Νέα Υόρκη, Νέα Υόρκη, ΗΠΑ, 2020. Διαθέσιμο στο διαδίκτυο: https://doi.org/​10.1145/​3357713.3384314.
https: / / doi.org/ 10.1145 / 3357713.3384314

[8] T. Li, S. Chakrabarti, and X. Wu. Υπογραμμικοί κβαντικοί αλγόριθμοι για εκπαίδευση γραμμικών και βασισμένων σε πυρήνα ταξινομητών. Στο International Conference on Machine Learning, σελίδες 3815–3824. PMLR, 2019.

[9] S. Thanasilp, S. Wang, M. Cerezo και Z. Holmes. Εκθετική συγκέντρωση και ανεκπαίδευση σε μεθόδους κβαντικού πυρήνα, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://doi.org/​10.48550/​ARXIV.2208.11060

[10] S. Shalev-Shwartz και N. Srebro. Βελτιστοποίηση SVM: Αντίστροφη εξάρτηση από το μέγεθος του συνόλου εκπαίδευσης. Πρακτικά του 25ου Διεθνούς Συνεδρίου για τη Μηχανική Μάθηση, σελίδες 928–935, 2008.

[11] Α. Τόμσεν. Σύγκριση κβαντικών νευρωνικών δικτύων και μηχανών διανυσμάτων κβαντικής υποστήριξης. Μεταπτυχιακή διατριβή, ETH Zurich, 2021-09-06. DOI: 20.500.11850/​527559.

[12] B. E. Boser, I. M. Guyon και V. N. Vapnik. Ένας αλγόριθμος εκπαίδευσης για ταξινομητές βέλτιστων περιθωρίων. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT ’92, pages 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 και V. Vapnik. Υποστήριξη-διανυσματικά δίκτυα. Στο Machine Learning, σελίδες 273–297, 1995.

[14] V. N. Vapnik. Η Φύση της Στατιστικής Θεωρίας Μάθησης. Springer Science+Business Media, LLC, 2000.

[15] Οι F. Pedregosa et al. Scikit-learn: Machine Learning σε Python. Journal of Machine Learning Research, 12(85):2825–2830, 2011. Διαθέσιμο στο διαδίκτυο: http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​jmlr.org/​papers/​v12/​pedregosa11a.html

[16] S. Boyd και L. Vandenberghe. Κυρτή Βελτιστοποίηση. Cambridge University Press, 2004.

[17] S. Shalev-Shwartz, Y. Singer, N. Srebro, and A. Cotter. Pegasos: Πρωτεύων εκτιμώμενος επιλύτης υποδιαβάθμισης για 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, and S. Lloyd. Κβαντική διανυσματική μηχανή υποστήριξης για ταξινόμηση μεγάλων δεδομένων. 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, and B. Schölkopf. Η επαγωγική προκατάληψη των κβαντικών πυρήνων. Στο M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, εκδότες, Advances in Neural Information Processing Systems, τόμος 34, σελίδες 12661–12673. Curran Associates, Inc., 2021. Διαθέσιμο στο διαδίκτυο: 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é και C. Ciuti. Θορυβώδεις μηχανές κβαντικού πυρήνα. Phys. Αναθ. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

[22] C. J. C. Burges και C. J. C. Burges. Ένα σεμινάριο σχετικά με τις μηχανές υποστήριξης διανυσμάτων για την αναγνώριση προτύπων. Data Mining and Knowledge Discovery, 2:121–167, 1998. Διαθέσιμο στο διαδίκτυο: https://www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -μηχανές-για-αναγνώριση προτύπων/​.
https://www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector-machines-for-pattern-cognition/​

[23] M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles. Άγονα οροπέδια εξαρτώμενα από τη συνάρτηση κόστους σε ρηχά παραμετροποιημένα κβαντικά κυκλώματα. 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 και Reiter, Florentin. Ανάλυση Higgs με κβαντικούς ταξινομητές. 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 και P. J. Coles. Μεταβλητοί κβαντικοί αλγόριθμοι. 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: Τετραγωνικός λύτης προγραμματισμού (python). https://github.com/​quadprog/​quadprog, 2022.
https://github.com/​quadprog/​quadprog

[27] Y. Nesterov. Εισαγωγικές Διαλέξεις για το Convex Optimization: A Basic Course. Εφαρμοσμένη Βελτιστοποίηση. Springer, 2004. DOI: 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] J. Spall. Μια επισκόπηση της μεθόδου ταυτόχρονης διαταραχής για αποτελεσματική βελτιστοποίηση. John Hopkins APL Technical Digest, 19(4), σελίδες 482–492, 1998.

[29] G. Gentinetta, A. Thomsen, D. Sutter και S. Woerner. Κώδικας για το χειρόγραφο «Η πολυπλοκότητα των μηχανών διανυσμάτων κβαντικής υποστήριξης». 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, and J. J. Meyer. Εκπαίδευση πυρήνων κβαντικής ενσωμάτωσης σε βραχυπρόθεσμους κβαντικούς υπολογιστές. Phys. Αναθ. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] R. Latała. Μερικές εκτιμήσεις κανόνων τυχαίων πινάκων. 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. Εισαγωγή στη μη ασυμπτωτική ανάλυση τυχαίων πινάκων. Compressed Sensing: Theory and Applications, σελίδες 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

[33] T. Hofmann, B. Schölkopf, and A. J. Smola. Μέθοδοι πυρήνα στη μηχανική μάθηση. Annals of Statistics, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / 009053607000000677

[34] J. W. Daniel. Σταθερότητα επίλυσης ορισμένων τετραγωνικών προγραμμάτων. Mathematical Programming, 5(1):41–53, 1973. DOI: 10.1007/​BF01580110.
https: / / doi.org/ 10.1007 / BF01580110

Αναφέρεται από

[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 και Fernando GSL Brandão, «Κβαντικοί αλγόριθμοι: Έρευνα εφαρμογών και πολυπλοκοτήτων από άκρο σε άκρο», arXiv: 2310.03011, (2023).

[2] Maria Schuld και Nathan Killoran, «Είναι το Quantum Advantage ο σωστός στόχος για την κβαντική μηχανική μάθηση;», PRX Quantum 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik και Ofer Lahav, «A quantum-enhanced support vector machine for galaxy classification». RAS Techniques and Instruments 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung και Chen-Yu Liu, «Μηχανή διανυσμάτων υποστήριξης κβαντικής βελτιωμένης για μεγάλης κλίμακας αστρική ταξινόμηση με επιτάχυνση GPU», arXiv: 2311.12328, (2023).

[5] Supanut Thanasilp, Samson Wang, M. Cerezo και Zoë Holmes, «Εκθετική συγκέντρωση και ανεκπαίδευση σε μεθόδους κβαντικού πυρήνα». arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka και Naoki Yamamoto, «Κβαντικά-κλασικά υβριδικά νευρωνικά δίκτυα στο καθεστώς του νευρικού εφαπτομενικού πυρήνα», Κβαντική επιστήμη και τεχνολογία 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo και 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 και Nico Piatkowski, «Εξήγηση κβαντικών κυκλωμάτων με τιμές Shapley: Towards Explainable Quantum Machine Learning», arXiv: 2301.09138, (2023).

[9] Julien Gacon, Jannes Nys, Riccardo Rossi, Stefan Woerner και Giuseppe Carleo, «Variational Quantum Time Evolution without the Quantum Geometric Tensor», arXiv: 2303.12839, (2023).

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

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie και Tim Scanlon, «Ανακατασκευή τμημάτων τροχιάς φορτισμένων σωματιδίων με μια μηχανή διανυσμάτων υποστήριξης με κβαντική ενίσχυση». arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick και Thomas Ward, “A Model for Circuit Execution Runtime And Its Implications 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 και Stefan Woerner, «Αποδείξιμα όρια για τιμές προσδοκίας χωρίς θόρυβο που υπολογίζονται από θορυβώδη δείγματα». arXiv: 2312.00733, (2023).

[14] M. Emre Sahin, Benjamin C. B. Symons, Pushpak Pati, Fayyaz Minhas, Declan Millar, Maria Gabrani, Jan Lukas Robertus και Stefano Mensa, “Efficient Parameter Optimization for Quantum Kernel Alignment: A Sub-sampling Approach in Variational Training” , arXiv: 2401.02879, (2024).

Οι παραπάνω αναφορές είναι από SAO / NASA ADS (τελευταία ενημέρωση επιτυχώς 2024-01-12 02:12:22). Η λίστα μπορεί να είναι ελλιπής, καθώς δεν παρέχουν όλοι οι εκδότες τα κατάλληλα και πλήρη στοιχεία αναφοράς.

On Η υπηρεσία παραπομπής του Crossref δεν βρέθηκαν δεδομένα σχετικά με την αναφορά έργων (τελευταία προσπάθεια 2024-01-12 02:12:21).

Αυτό το Βιβλίο δημοσιεύεται στο Quantum στο πλαίσιο του Creative Commons Attribution 4.0 Διεθνής (CC BY 4.0) άδεια. Τα πνευματικά δικαιώματα παραμένουν στους κατόχους των πρωτότυπων δικαιωμάτων πνευματικής ιδιοκτησίας όπως οι δημιουργοί ή τα ιδρύματά τους

Σφραγίδα ώρας:

Περισσότερα από Quantum Journal