A kvantumtámogató vektorgépek összetettsége

A kvantumtámogató vektorgépek összetettsége

Időbélyeg: 11. január 2024. 9:08
Forrás csomópont: 3057476

Gian Gentinetta1,2, Arne Thomsen3,2, David Sutter2és Stefan Woerner2

1Physics Institute, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – Zürich
3Fizikai Tanszék, ETH Zürich

Érdekesnek találja ezt a cikket, vagy szeretne megvitatni? Scite vagy hagyjon megjegyzést a SciRate-en.

Absztrakt

A kvantumtámogató vektorgépek kvantumáramköröket alkalmaznak a kernelfüggvény meghatározására. Kimutatták, hogy ez a megközelítés bizonyíthatóan exponenciális gyorsulást tesz lehetővé bármely ismert klasszikus algoritmushoz képest bizonyos adatkészletek esetében. Az ilyen modellek betanítása egy konvex optimalizálási probléma megoldásának felel meg akár primális, akár duális megfogalmazásán keresztül. A kvantummechanika valószínűségi természetéből adódóan a betanító algoritmusokat statisztikai bizonytalanság érinti, ami nagyban befolyásolja azok összetettségét. Megmutatjuk, hogy a kettős probléma megoldható $O(M^{4.67}/varepszilon^2)$ kvantumáramkör kiértékelésekkel, ahol $M$ az adathalmaz méretét, $varepszilon$ pedig a megoldási pontosságot az ideálishoz képest. pontos elvárási értékekből erednek, ami csak elméletben érhető el. Empirikusan motivált feltevés mellett bebizonyítjuk, hogy a magba foglalt primál probléma alternatív módon megoldható $O(min { M^2/varepszilon^6, , 1/varepszilon^{10} })$ kiértékelésekben egy ismert klasszikus általánosítás alkalmazásával. Pegasos nevű algoritmus. A kísérő empirikus eredmények azt mutatják, hogy ezek az elemzési bonyolultságok alapvetően szűkek. Ezen túlmenően megvizsgálunk egy variációs közelítést a kvantumtartó vektor gépekre, és megmutatjuk, hogy a heurisztikus képzésük lényegesen jobb skálázást ér el kísérleteinkben.

Kiemelt kép: A $k(mathbf{x}_i, mathbf{x}_j)$ kernelérték becslése, ahol a $mathcal{E}(mathbf{x}_i)$ a $mathbf{x adatok által paraméterezett egységes egység. }_i$. A lövések számát a $R$ adja meg, amely a kernelbecslés pontosságát szabályozza.

Népszerű összefoglaló

A kvantumtámogató vektorgépek alkalmasak arra, hogy a közeljövőben kvantumelőnyöket demonstráljanak osztályozási problémák esetén. Az ötlet az, hogy egy (remélhetőleg hasznos) kernelfüggvényt egy hatékony kvantumáramkör ad, amelyet klasszikusan nehéz kiértékelni. A kvantummechanika valószínűségi jellege miatt az ilyen kernelfüggvényeket statisztikai bizonytalanság érinti. Ebben a munkában alaposan elemezzük, hogy ez a bizonytalanság (más néven lövészaj) hogyan befolyásolja az osztályozási probléma megoldásának általános számítási bonyolultságát.

► BibTeX adatok

► Referenciák

[1] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe és S. Lloyd. Kvantumgépi tanulás. 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 és J. M. Gambetta. Felügyelt tanulás kvantum-bővített funkcióterekkel. 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 és S. Woerner. A kvantumneurális hálózatok ereje. Nature Computational Science, 1 (június), 2020. DOI: 10.1038/​s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] Y. Liu, S. Arunachalam és K. Temme. Szigorú és robusztus kvantumgyorsítás a felügyelt gépi tanulásban. Nature Physics, 2021. DOI: 10.1038/​s41567-021-01287-z.
https://​/​doi.org/​10.1038/​s41567-021-01287-z

[5] S. Aaronson. Olvassa el az apró betűs részt. Nature Physics, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https://​/​doi.org/​10.1038/​nphys3272

[6] E. Tang. Kvantum-ihlette klasszikus algoritmus ajánlórendszerekhez. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, 217–228. oldal, 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 és C. Wang. Mintavételen alapuló szublineáris alacsony rangú mátrix aritmetikai keretrendszer a kvantumgépi tanulás dekvantálásához, 387–400. Association for Computing Machinery, New York, NY, USA, 2020. Elérhető online: https://​/​doi.org/​10.1145/​3357713.3384314.
https://​/​doi.org/​10.1145/​3357713.3384314

[8] T. Li, S. Chakrabarti és X. Wu. Szublineáris kvantum algoritmusok lineáris és kernel alapú osztályozók betanításához. In International Conference on Machine Learning, 3815–3824. oldal. PMLR, 2019.

[9] S. Thanasilp, S. Wang, M. Cerezo és Z. Holmes. Exponenciális koncentráció és betaníthatatlanság kvantummag-módszerekben, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

[10] S. Shalev-Shwartz és N. Srebro. SVM optimalizálás: fordított függés a képzési készlet méretétől. Proceedings of the 25th International Conference on Machine Learning, 928–935. oldal, 2008.

[11] A. Thomsen. Kvantum neurális hálózatok és kvantum támogató vektor gépek összehasonlítása. Mesterdolgozat, ETH Zürich, 2021-09-06. DOI: 20.500.11850/​527559.

[12] B. E. Boser, I. M. Guyon és V. N. Vapnik. Oktatási algoritmus az optimális árrés-osztályozókhoz. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT ’92, 144–152. oldal, New York, NY, USA, 1992. Association for Computing Machinery. DOI: 10.1145/​130385.130401.
https://​/​doi.org/​10.1145/​130385.130401

[13] C. Cortes és V. Vapnik. Támogató-vektor hálózatok. In Machine Learning, 273–297. oldal, 1995.

[14] V. N. Vapnik. A statisztikai tanuláselmélet természete. Springer Science+Business Media, LLC, 2000.

[15] F. Pedregosa és mtsai. Scikit-learn: gépi tanulás Pythonban. Journal of Machine Learning Research, 12(85):2825–2830, 2011. Online elérhető: http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

[16] S. Boyd és L. Vandenberghe. Konvex optimalizálás. Cambridge University Press, 2004.

[17] S. Shalev-Shwartz, Y. Singer, N. Srebro és A. Cotter. Pegasos: Elsődleges becsült al-gradiens megoldó az SVM-hez. Matematikai programozás, 127(1):3–30, 2011. DOI: 10.1007/​s10107-010-0420-4.
https:/​/​doi.org/​10.1007/​s10107-010-0420-4

[18] M. D. S. Anis et al. Qiskit: Nyílt forráskódú keretrendszer a kvantumszámításhoz, 2021. DOI: 10.5281/zenodo.2573505.
https://​/​doi.org/​10.5281/​zenodo.2573505

[19] P. Rebentrost, M. Mohseni és S. Lloyd. Kvantum támogató vektorgép nagy adatosztályozáshoz. 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 és B. Schölkopf. A kvantummagok induktív torzítása. M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang és J. W. Vaughan szerkesztők, Advances in Neural Information Processing Systems, 34. kötet, 12661–12673. oldal. Curran Associates, Inc., 2021. Elérhető 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

[21] V. Heyraud, Z. Li, Z. Denis, A. Le Boité és C. Ciuti. Zajos kvantum kernel gépek. Phys. Rev. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https://​/​doi.org/​10.1103/​PhysRevA.106.052421

[22] C. J. C. Burges és C. J. C. Burges. Oktatóanyag a mintafelismerést támogató vektorgépekről. Data Mining and Knowledge Discovery, 2:121–167, 1998. Elérhető online: https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -machines-for-minta-felismerés/​.
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 és P. J. Coles. Költségfüggvénytől függő kopár platók sekély parametrizált kvantumáramkörökben. 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 és Reiter, Florentin. Higgs-analízis kvantumosztályozókkal. 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 és P. J. Coles. Variációs kvantum algoritmusok. 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: Kvadratikus programozási megoldó (python). https://​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

[27] Y. Neszterov. Bevezető előadások a konvex optimalizálásról: alaptanfolyam. Alkalmazott optimalizálás. Springer, 2004. DOI: 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] J. Spall. A hatékony optimalizálás szimultán perturbációs módszerének áttekintése. John Hopkins APL Technical Digest, 19(4), 482–492. oldal, 1998.

[29] G. Gentinetta, A. Thomsen, D. Sutter és S. Woerner. A „Kvantum támogató vektorgépek összetettsége” kézirat kódja. 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 és J. J. Meyer. Kvantumbeágyazó rendszermagok képzése rövid távú kvantumszámítógépeken. Phys. Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https://​/​doi.org/​10.1103/​PhysRevA.106.042431

[31] R. Latała. A véletlen mátrixok normáinak néhány becslése. 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. Versinyin. Bevezetés a véletlen mátrixok nem aszimptotikus elemzésébe. Compressed Sensing: Theory and Applications, 210–268. oldal, 2009. DOI: 10.1017/​CBO9780511794308.006.
https://​/​doi.org/​10.1017/​CBO9780511794308.006

[33] T. Hofmann, B. Schölkopf és A. J. Smola. Kernel módszerek a gépi tanulásban. Annals of Statistics, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https://​/​doi.org/​10.1214/​009053607000000677

[34] J. W. Daniel. Határozott másodfokú programok megoldásának stabilitása. Matematikai programozás, 5(1):41–53, 1973. DOI: 10.1007/BF01580110.
https://​/​doi.org/​10.1007/​BF01580110

Idézi

[1] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, Gilyén András, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang és Fernando GSL Brandão, „Kvantum algoritmusok: Az alkalmazások és a végpontok közötti bonyolultságok felmérése”, arXiv: 2310.03011, (2023).

[2] Maria Schuld és Nathan Killoran, „A Quantum Advantage a megfelelő cél a kvantumgépi tanuláshoz?”, PRX Quantum 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik és Ofer Lahav, „Kvantum-bővített támogató vektorgép galaxisosztályozáshoz”, RAS Techniques and Instruments 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung és 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 és Zoë Holmes, „Exponenciális koncentráció és betaníthatatlanság kvantummag-módszerekben”, arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka és Naoki Yamamoto, „Kvantum-klasszikus hibrid neurális hálózatok a neurális tangens kernelrendszerben”, Kvantumtudomány és Technológia 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo és Rudy Raymond, „Kvantumgépi tanulás közeli távú kvantumeszközökön: A felügyelt és nem felügyelt technikák jelenlegi állapota valós alkalmazásokhoz”, arXiv: 2307.00908, (2023).

[8] Raoul Heese, Thore Gerlach, Sascha Mücke, Sabine Müller, Matthias Jakobs és 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 és Giuseppe Carleo, „Variational Quantum Time Evolution without the Quantum Geometric Tensor”, arXiv: 2303.12839, (2023).

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

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie és Tim Scanlon, „Töltött részecskék nyomvonal-szegmenseinek rekonstrukciója kvantum-javított hordozóvektor géppel”, arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick és Thomas Ward, „A Model for Circuit Execution Runtime and It Implikations 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 és Stefan Woerner, „Provable bounds for noise-free várakozási értékek zajos mintákból számítva”, arXiv: 2312.00733, (2023).

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

A fenti idézetek innen származnak SAO/NASA HIRDETÉSEK (utolsó sikeres frissítés: 2024-01-12 02:12:22). Előfordulhat, hogy a lista hiányos, mivel nem minden kiadó ad megfelelő és teljes hivatkozási adatokat.

On Crossref által idézett szolgáltatás művekre hivatkozó adat nem található (utolsó próbálkozás 2024-01-12 02:12:21).

Ez a tanulmány a Quantumban jelent meg Creative Commons Nevezd meg 4.0 International (CC BY 4.0) engedély. A szerzői jog az eredeti szerzői jog tulajdonosainál marad, például a szerzőknél vagy intézményeiknél.

Időbélyeg:

Még több Quantum Journal