Komplexiteten hos kvantstödvektormaskiner

Komplexiteten hos kvantstödvektormaskiner

Tidsstämpel: 11 januari 2024 9:08
Källnod: 3057476

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

1Institutet för fysik, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – Zürich
3Institutionen för fysik, ETH Zürich

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Kvantstödsvektormaskiner använder kvantkretsar för att definiera kärnfunktionen. Det har visat sig att detta tillvägagångssätt erbjuder en bevisbar exponentiell hastighet jämfört med vilken känd klassisk algoritm som helst för vissa datamängder. Träningen av sådana modeller motsvarar att lösa ett konvext optimeringsproblem antingen via dess primära eller dubbla formulering. På grund av kvantmekanikens probabilistiska natur påverkas träningsalgoritmerna av statistisk osäkerhet, vilket har stor inverkan på deras komplexitet. Vi visar att det dubbla problemet kan lösas i $O(M^{4.67}/varepsilon^2)$ kvantkretsutvärderingar, där $M$ anger storleken på datamängden och $varepsilon$ lösningsnoggrannheten jämfört med den ideala resultat från exakta förväntningsvärden, som endast är att få i teorin. Vi bevisar under ett empiriskt motiverat antagande att det kärniserade primala problemet alternativt kan lösas i $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ utvärderingar genom att använda en generalisering av en känd klassisk algoritm som heter Pegasos. Medföljande empiriska resultat visar att dessa analytiska komplexiteter är i huvudsak snäva. Dessutom undersöker vi en variationsmässig approximation till kvantstödvektormaskiner och visar att deras heuristiska träning uppnår avsevärt bättre skalning i våra experiment.

Utvald bild: Uppskattning av kärnvärdet $k(mathbf{x}_i, mathbf{x}_j)$, där $mathcal{E}(mathbf{x}_i)$ anger en enhetlig parametriserad av datan $mathbf{x }_i$. Antalet skott ges av $R$ som styr noggrannheten i kärnuppskattningen.

Populär sammanfattning

Kvantstödsvektormaskiner är kandidater för att demonstrera en kvantfördel i en nära framtid för klassificeringsproblem. Tanken är att en (förhoppningsvis användbar) kärnfunktion ges av en effektiv kvantkrets som är klassiskt svår att utvärdera. På grund av kvantmekanikens probabilistiska natur påverkas sådana kärnfunktioner av statistisk osäkerhet. I detta arbete analyserar vi noggrant hur denna osäkerhet (även kallad skottbrus) påverkar den övergripande beräkningskomplexiteten för att lösa klassificeringsproblemet.

► BibTeX-data

► Referenser

[1] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe och S. Lloyd. Kvantmaskininlärning. 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 och JM Gambetta. Övervakat lärande med kvantförbättrade funktionsutrymmen. 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 och S. Woerner. Kraften i kvantneurala nätverk. Nature Computational Science, 1 (juni), 2020. DOI: 10.1038/​s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] Y. Liu, S. Arunachalam och K. Temme. En rigorös och robust kvanthastighet inom övervakad maskininlärning. Nature Physics, 2021. DOI: 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

[5] S. Aaronson. Läs det finstilta. Nature Physics, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https: / / doi.org/ 10.1038 / nphys3272

[6] E. Tang. En kvantinspirerad klassisk algoritm för rekommendationssystem. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, sid 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 och C. Wang. Samplingsbaserad sublinjär aritmetisk matrisram med låg rangordning för avkvantisering av kvantmaskininlärning, sid 387–400. Association for Computing Machinery, New York, NY, USA, 2020. Tillgänglig online: https://​/​doi.org/​10.1145/​3357713.3384314.
https: / / doi.org/ 10.1145 / 3357713.3384314

[8] T. Li, S. Chakrabarti och X. Wu. Sublinjära kvantalgoritmer för träning av linjära och kärnbaserade klassificerare. I International Conference on Machine Learning, sidorna 3815–3824. PMLR, 2019.

[9] S. Thanasilp, S. Wang, M. Cerezo och Z. Holmes. Exponentiell koncentration och oträningsförmåga i kvantkärnmetoder, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

[10] S. Shalev-Shwartz och N. Srebro. SVM-optimering: Omvänt beroende av träningsuppsättningens storlek. Proceedings of the 25th International Conference on Machine Learning, sidorna 928–935, 2008.

[11] A. Thomsen. Jämföra kvantneurala nätverk och kvantstödvektormaskiner. Magisteruppsats, ETH Zürich, 2021-09-06. DOI: 20.500.11850/​527559.

[12] BE Boser, IM Guyon och VN Vapnik. En träningsalgoritm för Optimal Margin Classifiers. I Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, sidorna 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 och V. Vapnik. Stöd-vektor nätverk. I Machine Learning, sidorna 273–297, 1995.

[14] VN Vapnik. Naturen för statistisk lärandeteori. Springer Science+Business Media, LLC, 2000.

[15] F. Pedregosa et al. Scikit-learn: Machine Learning i Python. Journal of Machine Learning Research, 12(85):2825–2830, 2011. Tillgänglig online: http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

[16] S. Boyd och L. Vandenberghe. Konvex optimering. Cambridge University Press, 2004.

[17] S. Shalev-Shwartz, Y. Singer, N. Srebro och A. Cotter. Pegasos: Primal uppskattad subgradientlösare för SVM. Mathematical Programmering, 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 och S. Lloyd. Quantum support vektor maskin för big data klassificering. 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 och B. Schölkopf. Den induktiva förspänningen hos kvantkärnor. I M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang och JW Vaughan, redaktörer, Advances in Neural Information Processing Systems, volym 34, sidorna 12661–12673. Curran Associates, Inc., 2021. Tillgänglig 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é och C. Ciuti. Bullriga kvantkärnmaskiner. Phys. Rev. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

[22] CJC Burges och CJC Burges. En handledning om stöd för vektormaskiner för mönsterigenkänning. Data Mining and Knowledge Discovery, 2:121–167, 1998. Tillgänglig online: https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -maskiner-för-mönsterigenkänning/​.
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 och PJ Coles. Kostnadsfunktionsberoende karga platåer i grunda parametriserade kvantkretsar. 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 och Reiter, Florentin. Higgs-analys med kvantklassificerare. 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 och PJ Coles. Varierande kvantalgoritmer. 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: Kvadratisk programmeringslösare (python). https://​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

[27] Y. Nesterov. Inledande föreläsningar om konvex optimering: en grundkurs. Tillämpad optimering. Springer, 2004. DOI: 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] J. Spall. En översikt över metoden för samtidig störning för effektiv optimering. John Hopkins APL Technical Digest, 19(4), sidorna 482–492, 1998.

[29] G. Gentinetta, A. Thomsen, D. Sutter och S. Woerner. Kod för manuskript "Komplexiteten hos kvantstödsvektormaskiner". 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 och JJ Meyer. Utbildning av kvantinbäddningskärnor på kvantdatorer på kort sikt. Phys. Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] R. Latała. Några uppskattningar av normer för slumpmässiga matriser. 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. Introduktion till icke-asymptotisk analys av slumpmässiga matriser. Compressed Sensing: Theory and Applications, sidorna 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

[33] T. Hofmann, B. Schölkopf och AJ Smola. Kärnmetoder inom maskininlärning. Annals of Statistics, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / 009053607000000677

[34] JW Daniel. Stabilitet för lösningen av bestämda kvadratiska program. Mathematical Programmering, 5(1):41–53, 1973. DOI: 10.1007/​BF01580110.
https: / / doi.org/ 10.1007 / BF01580110

Citerad av

[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 och Fernando GSL Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv: 2310.03011, (2023).

[2] Maria Schuld och Nathan Killoran, "Är Quantum Advantage det rätta målet för Quantum Machine Learning?", PRX Quantum 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik och Ofer Lahav, "En kvantförstärkt stödvektormaskin för galaxklassificering", RAS-tekniker och instrument 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung och 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, och Zoë Holmes, "Exponentiell koncentration och untrainability in quantum kernel methods", arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka och Naoki Yamamoto, "Kvantklassiska hybridneurala nätverk i den neurala tangentkärnregimen", Kvantvetenskap och teknik 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo och 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 och 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 och Giuseppe Carleo, "Variational Quantum Time Evolution without the Quantum Geometric Tensor", arXiv: 2303.12839, (2023).

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

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie och Tim Scanlon, "Rekonstruera laddade partikelspårsegment med en kvantförstärkt stödvektormaskin", arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick och Thomas Ward, "A Model for Circuit Execution Runtime And Its 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 och Stefan Woerner, "Provable bounds for noise-free expectations values ​​computed from noisy samples", arXiv: 2312.00733, (2023).

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

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2024-01-12 02:12:22). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2024-01-12 02:12:21).

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal