La complessità delle macchine vettoriali a supporto quantistico

La complessità delle macchine vettoriali a supporto quantistico

Timestamp: 11 gennaio 2024 9:08
Nodo di origine: 3057476

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

1Istituto di fisica, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – Zurigo
3Dipartimento di Fisica, ETH Zurigo

Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.

Astratto

Le macchine vettoriali a supporto quantistico utilizzano circuiti quantistici per definire la funzione del kernel. È stato dimostrato che questo approccio offre una velocità esponenziale dimostrabile rispetto a qualsiasi algoritmo classico noto per determinati set di dati. L'addestramento di tali modelli corrisponde alla risoluzione di un problema di ottimizzazione convessa tramite la sua formulazione primale o duale. A causa della natura probabilistica della meccanica quantistica, gli algoritmi di addestramento sono affetti da incertezza statistica, che ha un impatto notevole sulla loro complessità. Mostriamo che il doppio problema può essere risolto nelle valutazioni di circuiti quantistici $O(M^{4.67}/varepsilon^2)$, dove $M$ indica la dimensione del set di dati e $varepsilon$ l'accuratezza della soluzione rispetto all'ideale derivano da valori attesi esatti, ottenibili solo in teoria. Dimostriamo, sotto un'ipotesi motivata empiricamente, che il problema primale kernelizzato può alternativamente essere risolto in valutazioni $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ impiegando una generalizzazione di un modello classico noto algoritmo chiamato Pegasos. I risultati empirici di accompagnamento dimostrano che queste complessità analitiche sono essenzialmente strette. Inoltre, investighiamo un'approssimazione variazionale alle macchine vettoriali a supporto quantistico e mostriamo che il loro addestramento euristico raggiunge un ridimensionamento considerevolmente migliore nei nostri esperimenti.

Immagine in primo piano: Stima del valore del kernel $k(mathbf{x}_i, mathbf{x}_j)$, dove $mathcal{E}(mathbf{x}_i)$ denota un unitario parametrizzato dai dati $mathbf{x }_i$. Il numero di colpi è dato da $R$ che controlla l'accuratezza della stima del kernel.

Riepilogo popolare

Le macchine vettoriali a supporto quantistico sono candidate a dimostrare un vantaggio quantistico nel prossimo futuro per i problemi di classificazione. L'idea è che una funzione kernel (si spera utile) sia data da un circuito quantistico efficiente che è classicamente difficile da valutare. A causa della natura probabilistica della meccanica quantistica, tali funzioni del nucleo sono influenzate dall'incertezza statistica. In questo lavoro, analizziamo rigorosamente come questa incertezza (chiamata anche rumore di sparo) influisce sulla complessità computazionale complessiva per risolvere il problema di classificazione.

► dati BibTeX

► Riferimenti

, J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe e S. Lloyd. Apprendimento automatico quantistico. Natura, 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 e JM Gambetta. Apprendimento supervisionato con spazi di funzionalità potenziati dal punto di vista quantistico. Natura, 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 e S. Woerner. Il potere delle reti neurali quantistiche. Nature Computational Science, 1 (giugno), 2020. DOI: 10.1038/​s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

, Y. Liu, S. Arunachalam e K. Temme. Un’accelerazione quantistica rigorosa e robusta nell’apprendimento automatico supervisionato. Fisica della natura, 2021. DOI: 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

, S. Aaronson. Leggi le clausole scritte in piccolo. Nature Physics, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https: / / doi.org/ 10.1038 / nphys3272

, E. Tang. Un algoritmo classico di ispirazione quantistica per sistemi di raccomandazione. In Atti del 51° Simposio annuale ACM SIGACT sulla teoria dell'informatica, STOC 2019, pagine 217–228, New York, NY, USA, 2019. Association for Computing Machinery. DOI: 10.1145/​3313276.3316310.
https: / / doi.org/ 10.1145 / 3313276.3316310 mila

, N.-H. Chia, A. Gilyén, T. Li, H.-H. Lin, E. Tang e C. Wang. Quadro aritmetico della matrice sublineare di basso rango basato sul campionamento per la dequantizzazione dell'apprendimento automatico quantistico, pagina 387–400. Association for Computing Machinery, New York, NY, USA, 2020. Disponibile online: https://​/​doi.org/​10.1145/​3357713.3384314.
https: / / doi.org/ 10.1145 / 3357713.3384314 mila

, T. Li, S. Chakrabarti e X. Wu. Algoritmi quantistici sublineari per l'addestramento di classificatori lineari e basati su kernel. Nella conferenza internazionale sull'apprendimento automatico, pagine 3815–3824. PMLR, 2019.

, S. Thanasilp, S. Wang, M. Cerezo e Z. Holmes. Concentrazione esponenziale e non addestrabilità nei metodi del kernel quantistico, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

, S. Shalev-Shwartz e N. Srebro. Ottimizzazione SVM: dipendenza inversa dalla dimensione del set di addestramento. Atti della 25a conferenza internazionale sull'apprendimento automatico, pagine 928–935, 2008.

, A. Thomsen. Confronto tra reti neurali quantistiche e macchine vettoriali a supporto quantistico. Tesi di master, ETH Zurigo, 2021-09-06. DOI: 20.500.11850/​527559.

, BE Boser, IM Guyon e VN Vapnik. Un algoritmo di addestramento per classificatori di margine ottimali. In Atti del quinto seminario annuale sulla teoria dell'apprendimento computazionale, COLT '92, pagine 144–152, New York, NY, USA, 1992. Association for Computing Machinery. DOI: 10.1145/​130385.130401.
https: / / doi.org/ 10.1145 / 130385.130401 mila

, C. Cortes e V. Vapnik. Reti di vettori di supporto. In Machine Learning, pagine 273–297, 1995.

, VN Vapnik. La natura della teoria dell'apprendimento statistico. Springer Science+Business Media, LLC, 2000.

, F. Pedregosa et al. Scikit-learn: apprendimento automatico in Python. Journal of Machine Learning Research, 12(85):2825–2830, 2011. Disponibile online: http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

, S. Boyd e L. Vandenberghe. Ottimizzazione convessa. Stampa dell'Università di Cambridge, 2004.

, S. Shalev-Shwartz, Y. Singer, N. Srebro e A. Cotter. Pegasos: risolutore sub-gradiente stimato primordiale per SVM. Programmazione matematica, 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: An Open-source Framework for Quantum Computing, 2021. DOI: 10.5281/​zenodo.2573505.
https: / / doi.org/ 10.5281 / zenodo.2573505

, P. Rebentrost, M. Mohseni e S. Lloyd. Macchina vettoriale di supporto quantistico per la classificazione dei big data. Physical Review Letters, 113(3):1–5, 2014. DOI: 10.1103/​PhysRevLett.113.130503.
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503

, J. Kübler, S. Buchholz e B. Schölkopf. La polarizzazione induttiva dei nuclei quantistici. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang e JW Vaughan, editori, Advances in Neural Information Processing Systems, volume 34, pagine 12661–12673. Curran Associates, Inc., 2021. Disponibile 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

, V. Heyraud, Z. Li, Z. Denis, A. Le Boité e C. Ciuti. Macchine rumorose con kernel quantistico. Fis. Rev. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

, CJC Burges e CJC Burges. Un tutorial sulle macchine vettoriali di supporto per il riconoscimento di pattern. Data Mining and Knowledge Discovery, 2:121–167, 1998. Disponibile online: https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -macchine-per-il-riconoscimento-di-modelli/​.
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 e PJ Coles. Altopiani sterili dipendenti dalla funzione di costo in circuiti quantistici parametrizzati poco profondi. 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, and Reiter, Florentin. Analisi di Higgs con classificatori quantistici. EPJ Web Conf., 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 e PJ Coles. Algoritmi quantistici variazionali. 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 al. quadprog: risolutore di programmazione quadratica (python). https://​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

, Y. Nesterov. Lezioni introduttive sull'ottimizzazione convessa: un corso base. Ottimizzazione applicata. Springer, 2004. DOI: 10.1007/978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

, J. Spall. Una panoramica del metodo delle perturbazioni simultanee per un'ottimizzazione efficiente. John Hopkins APL Technical Digest, 19(4), pagine 482–492, 1998.

, G. Gentinetta, A. Thomsen, D. Sutter e S. Woerner. Codice per il manoscritto “La complessità delle macchine vettoriali a supporto quantistico”. 2022. DOI: https://​/​doi.org/​10.5281/​zenodo.6303725.
https: / / doi.org/ 10.5281 / zenodo.6303725

, T. Hubregtsen, D. Wierichs, E. Gil-Fuster, P.-JHS Derks, PK Faehrmann e JJ Meyer. Addestramento di kernel di incorporamento quantistico su computer quantistici a breve termine. Fis. Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

, R. Latala. Alcune stime di norme di matrici casuali. Atti dell'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. Vershinin. Introduzione all'analisi non asintotica di matrici casuali. Compressed Sensing: Theory and Applications, pagine 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

, T. Hofmann, B. Schölkopf e AJ Smola. Metodi kernel nell'apprendimento automatico. Annals of Statistics, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / 009053607000000677 mila

, JW Daniele. Stabilità della soluzione di programmi quadratici definiti. Programmazione matematica, 5(1):41–53, 1973. DOI: 10.1007/​BF01580110.
https: / / doi.org/ 10.1007 / BF01580110

Citato da

[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 e Fernando GSL Brandão, “Algoritmi quantistici: un'indagine sulle applicazioni e sulle complessità end-to-end”, arXiv: 2310.03011, (2023).

[2] Maria Schuld e Nathan Killoran, "Il vantaggio quantistico è l'obiettivo giusto per l'apprendimento automatico quantistico?", PRX Quantico 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik e Ofer Lahav, "Una macchina vettoriale di supporto potenziata quantistica per la classificazione delle galassie", Tecniche e Strumenti RAS 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung e Chen-Yu Liu, "Macchina vettoriale di supporto potenziata quantistica per classificazione stellare su larga scala con accelerazione GPU", arXiv: 2311.12328, (2023).

[5] Supanut Thanasilp, Samson Wang, M. Cerezo e Zoë Holmes, "Concentrazione esponenziale e non addestrabile nei metodi del kernel quantistico", arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka e Naoki Yamamoto, "Reti neurali ibride quantistiche-classiche nel regime del kernel tangente neurale", Scienza e tecnologia quantistica 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo e Rudy Raymond, "Apprendimento automatico quantistico su dispositivi quantistici a breve termine: stato attuale delle tecniche supervisionate e non supervisionate per applicazioni nel mondo reale", arXiv: 2307.00908, (2023).

[8] Raoul Heese, Thore Gerlach, Sascha Mücke, Sabine Müller, Matthias Jakobs e Nico Piatkowski, "Spiegare i circuiti quantistici con i valori di Shapley: verso l'apprendimento automatico quantistico spiegabile", arXiv: 2301.09138, (2023).

[9] Julien Gacon, Jannes Nys, Riccardo Rossi, Stefan Woerner e Giuseppe Carleo, "Evoluzione temporale quantistica variazionale senza il tensore geometrico quantistico", arXiv: 2303.12839, (2023).

[10] Gian Gentinetta, David Sutter, Christa Zoufal, Bryce Fuller e Stefan Woerner, "Allineamento del kernel quantistico con discesa del gradiente stocastico", arXiv: 2304.09899, (2023).

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie e Tim Scanlon, "Ricostruzione di segmenti di tracce di particelle cariche con una macchina vettoriale di supporto potenziata quantistica", arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick e Thomas Ward, "Un modello per il runtime di esecuzione di circuiti e le sue implicazioni per i kernel quantistici a dimensioni pratiche di set di dati", arXiv: 2307.04980, (2023).

[13] Samantha V. Barron, Daniel J. Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler e Stefan Woerner, "Limiti dimostrabili per valori di aspettativa privi di rumore calcolati da campioni rumorosi", arXiv: 2312.00733, (2023).

[14] M. Emre Sahin, Benjamin CB Symons, Pushpak Pati, Fayyaz Minhas, Declan Millar, Maria Gabrani, Jan Lukas Robertus e Stefano Mensa, "Ottimizzazione efficiente dei parametri per l'allineamento del kernel quantistico: un approccio di sottocampionamento nell'allenamento variazionale" , arXiv: 2401.02879, (2024).

Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2024-01-12 02:12:22). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.

On Il servizio citato da Crossref non sono stati trovati dati su citazioni (ultimo tentativo 2024-01-12 02:12:21).

Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.

Timestamp:

Di più da Diario quantistico