Kvanttitukivektorikoneiden monimutkaisuus

Kvanttitukivektorikoneiden monimutkaisuus

Aikaleima: 11. tammikuuta 2024 9
Lähdesolmu: 3057476

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

1Institute of Physics, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – Zürich
3Fysiikan laitos, ETH Zurich

Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.

Abstrakti

Kvanttitukivektorikoneet käyttävät kvanttipiirejä ytimen funktion määrittämiseen. On osoitettu, että tämä lähestymistapa tarjoaa todistettavasti eksponentiaalisen nopeuden verrattuna mihin tahansa tunnettuun klassiseen algoritmiin tietyille tietojoukoille. Tällaisten mallien koulutus vastaa konveksin optimointitehtävän ratkaisemista joko sen primaalisen tai kaksoisformuloinnin kautta. Kvanttimekaniikan todennäköisyyden vuoksi harjoitusalgoritmeihin vaikuttaa tilastollinen epävarmuus, jolla on suuri vaikutus niiden monimutkaisuuteen. Osoitamme, että kaksoisongelma voidaan ratkaista $O(M^{4.67}/varepsilon^2)$ kvanttipiirin arvioinneissa, joissa $M$ tarkoittaa tietojoukon kokoa ja $varepsilon$ ratkaisutarkkuutta ideaaliin verrattuna. tulosta tarkoista odotusarvoista, jotka ovat saatavissa vain teoriassa. Osoitamme empiirisesti motivoidulla oletuksella, että ydinongelma voidaan vaihtoehtoisesti ratkaista $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ arvioinneilla käyttämällä tunnetun klassisen yleistyksen Algoritmi nimeltä Pegasos. Mukana olevat empiiriset tulokset osoittavat, että nämä analyyttiset kompleksit ovat olennaisesti tiukkoja. Lisäksi tutkimme variaatioapproksimaatiota kvanttitukivektorikoneisiin ja osoitamme, että niiden heuristinen harjoittelu saavuttaa huomattavasti paremman skaalauksen kokeissamme.

Suositeltu kuva: Arvio ytimen arvosta $k(mathbf{x}_i, mathbf{x}_j)$, jossa $mathcal{E}(mathbf{x}_i)$ tarkoittaa yhtenäistä parametria, joka on parametroitu datalla $mathbf{x }_i$. Laukausten lukumäärän antaa $R$, joka ohjaa ytimen arvioinnin tarkkuutta.

Suosittu yhteenveto

Kvanttitukivektorikoneet ovat ehdokkaita osoittamaan kvanttietua lähitulevaisuudessa luokitteluongelmissa. Ajatuksena on, että (toivottavasti hyödyllinen) ydinfunktio saadaan tehokkaalla kvanttipiirillä, jota on klassisen vaikea arvioida. Kvanttimekaniikan todennäköisyyden vuoksi tällaisiin ytimen toimintoihin vaikuttaa tilastollinen epävarmuus. Tässä työssä analysoimme tarkasti, kuinka tämä epävarmuus (kutsutaan myös laukauskohinaksi) vaikuttaa yleiseen laskennalliseen monimutkaisuuteen luokitteluongelman ratkaisemiseksi.

► BibTeX-tiedot

► Viitteet

[1] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe ja S. Lloyd. Kvanttikoneoppiminen. 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 ja JM Gambetta. Valvottua oppimista kvanttitehostetuilla ominaisuustiloilla. 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 ja S. Woerner. Kvanttihermoverkkojen voima. Nature Computational Science, 1. (kesäkuu), 2020. DOI: 10.1038/​s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] Y. Liu, S. Arunachalam ja K. Temme. Tiukka ja vankka kvanttivahvistus valvotussa koneoppimisessa. Nature Physics, 2021. DOI: 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

[5] S. Aaronson. Lue pieni teksti. Nature Physics, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https: / / doi.org/ 10.1038 / nphys3272

[6] E. Tang. Kvanttivaikutteinen klassinen algoritmi suositusjärjestelmille. Julkaisussa Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, sivu 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 ja C. Wang. Otantapohjainen sublineaarinen matalan asteen matriisiaritmeettinen viitekehys kvanttikoneoppimisen dekvantisoimiseksi, sivut 387–400. Association for Computing Machinery, New York, NY, USA, 2020. Saatavilla verkossa: https://​/​doi.org/​10.1145/​3357713.3384314.
https: / / doi.org/ 10.1145 / +3357713.3384314

[8] T. Li, S. Chakrabarti ja X. Wu. Sublineaariset kvanttialgoritmit lineaaristen ja ydinpohjaisten luokittimien koulutukseen. International Conference on Machine Learning, sivut 3815–3824. PMLR, 2019.

[9] S. Thanasilp, S. Wang, M. Cerezo ja Z. Holmes. Eksponentiaalinen keskittyminen ja kouluttamattomuus kvanttiydinmenetelmissä, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

[10] S. Shalev-Shwartz ja N. Srebro. SVM-optimointi: Käänteinen riippuvuus harjoitussarjan koosta. Proceedings of the 25th International Conference on Machine Learning, sivut 928–935, 2008.

[11] A. Thomsen. Kvanttihermoverkkojen ja kvanttitukivektorikoneiden vertailu. Diplomityö, ETH Zurich, 2021-09-06. DOI: 20.500.11850/​527559.

[12] BE Boser, IM Guyon ja VN Vapnik. Harjoitusalgoritmi optimaalisille marginaaliluokittelijoille. Julkaisussa Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, sivut 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 ja V. Vapnik. Tukivektoriverkot. Teoksessa Machine Learning, sivut 273–297, 1995.

[14] VN Vapnik. Tilastollisen oppimisteorian luonne. Springer Science+Business Media, LLC, 2000.

[15] F. Pedregosa et ai. Scikit-learn: koneoppiminen Pythonissa. Journal of Machine Learning Research, 12(85):2825–2830, 2011. Saatavilla verkossa: http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

[16] S. Boyd ja L. Vandenberghe. Kupera optimointi. Cambridge University Press, 2004.

[17] S. Shalev-Shwartz, Y. Singer, N. Srebro ja A. Cotter. Pegasos: Ensisijainen arvioitu aligradientin ratkaisija SVM:lle. 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 ai. 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 ja S. Lloyd. Kvanttitukivektorikone ison datan luokitteluun. 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 ja B. Schölkopf. Kvanttiytimien induktiivinen bias. Julkaisussa M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang ja JW Vaughan, toimittajat, Advances in Neural Information Processing Systems, osa 34, sivut 12661–12673. Curran Associates, Inc., 2021. Saatavilla verkossa: 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é ja C. Ciuti. Meluiset kvanttiydinkoneet. Phys. Rev. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

[22] CJC Burges ja CJC Burges. Opetusohjelma kuvioiden tunnistusta tukevista vektorikoneista. Data Mining and Knowledge Discovery, 2:121–167, 1998. Saatavilla verkossa: https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -koneet-kuviontunnistusta varten/.
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 ja PJ Coles. Kustannusfunktiosta riippuvaiset karut tasangot matalissa parametroiduissa kvanttipiireissä. 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 ja Reiter, Florentin. Higgs-analyysi kvanttiluokittimilla. 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 ja PJ Coles. Variaatiokvanttialgoritmit. 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 ai. quadprog: Quadratic ohjelmoinnin ratkaisija (python). https://​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

[27] Y. Nesterov. Johdatusluennot kuperasta optimoinnista: peruskurssi. Sovellettu optimointi. Springer, 2004. DOI: 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] J. Spall. Yleiskatsaus tehokkaan optimoinnin samanaikaisen häiriön menetelmästä. John Hopkins APL Technical Digest, 19(4), sivut 482–492, 1998.

[29] G. Gentinetta, A. Thomsen, D. Sutter ja S. Woerner. Koodi käsikirjoitukselle "Kvanttitukivektorikoneiden monimutkaisuus". 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 ja JJ Meyer. Kvanttiupotusytimien koulutus lähiajan kvanttitietokoneissa. Phys. Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] R. Latała. Joitakin arvioita satunnaismatriisien normeista. 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. Johdatus satunnaismatriisien ei-asymptoottiseen analyysiin. Compressed Sensing: Theory and Applications, sivut 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

[33] T. Hofmann, B. Schölkopf ja AJ Smola. Ytimen menetelmät koneoppimisessa. Annals of Statistics, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / +009053607000000677

[34] JW Daniel. Määrättyjen toisen asteen ohjelmien ratkaisun stabiilius. Mathematical Programming, 5(1):41–53, 1973. DOI: 10.1007/BF01580110.
https: / / doi.org/ 10.1007 / BF01580110

Viitattu

[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 ja Fernando GSL Brandão, "Kvanttialgoritmit: Tutkimus sovelluksista ja päästä päähän -monimutkaisuuteen", arXiv: 2310.03011, (2023).

[2] Maria Schuld ja Nathan Killoran, "Onko kvanttietu oikea tavoite kvanttikoneoppimiseen?", PRX Quantum 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik ja Ofer Lahav, "Kvanttiparannettu tukivektorikone galaksien luokitteluun". RAS Techniques and Instruments 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung ja 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 ja Zoë Holmes, "Exponentiaalinen keskittyminen ja kouluttamattomuus kvanttiydinmenetelmissä", arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka ja Naoki Yamamoto, "Kvanttiklassiset hybridihermoverkot hermotangenttiytimen järjestelmässä", Kvanttitiede 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo ja Rudy Raymond, "Quantum Machine Learning on Near-Term Quantum Devices: Current State of Supervised and Unvalvised Techniques for Real-World Applications", arXiv: 2307.00908, (2023).

[8] Raoul Heese, Thore Gerlach, Sascha Mücke, Sabine Müller, Matthias Jakobs ja Nico Piatkowski, "Splaining Quantum Circuits with Shapley Values: Towards Explainable Quantum Machine Learning" arXiv: 2301.09138, (2023).

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

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

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie ja Tim Scanlon, "Varattujen hiukkasten radan segmenttien rekonstruointi kvanttitehostetulla tukivektorikoneella", arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick ja Thomas Ward, "A Model for Circuit Execution Runtime and Its Implics 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 ja Stefan Woerner, "Todistettavat rajat meluttomille odotusarvoille, jotka on laskettu meluisista näytteistä". arXiv: 2312.00733, (2023).

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

Yllä olevat sitaatit ovat peräisin SAO: n ja NASA: n mainokset (viimeksi päivitetty onnistuneesti 2024-01-12 02:12:22). Lista voi olla puutteellinen, koska kaikki julkaisijat eivät tarjoa sopivia ja täydellisiä viittaustietoja.

On Crossrefin siteerattu palvelu tietoja teosten viittaamisesta ei löytynyt (viimeinen yritys 2024-01-12 02:12:21).

Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.

Aikaleima:

Lisää aiheesta Quantum Journal