پیچیدگی ماشین های بردار پشتیبان کوانتومی

پیچیدگی ماشین های بردار پشتیبان کوانتومی

تمبر زمان: 11 ژانویه 2024، 9:08 صبح
گره منبع: 3057476

جیان جنتینتا1,2, آرنه تامسن3,2, دیوید ساتر2و استفان وورنر2

1موسسه فیزیک، École Polytechnique Fédérale de Lozanne
2IBM Quantum، IBM Research Europe – زوریخ
3گروه فیزیک، ETH زوریخ

این مقاله را جالب می دانید یا می خواهید بحث کنید؟ SciRate را ذکر کنید یا در SciRate نظر بدهید.

چکیده

ماشین‌های بردار پشتیبان کوانتومی از مدارهای کوانتومی برای تعریف عملکرد هسته استفاده می‌کنند. نشان داده شده است که این رویکرد یک سرعت نمایی قابل اثبات در مقایسه با هر الگوریتم کلاسیک شناخته شده برای مجموعه داده های خاص ارائه می دهد. آموزش چنین مدل‌هایی با حل یک مسئله بهینه‌سازی محدب از طریق فرمول‌بندی اولیه یا دوگانه آن مطابقت دارد. با توجه به ماهیت احتمالی مکانیک کوانتومی، الگوریتم های آموزشی تحت تأثیر عدم قطعیت آماری هستند که تأثیر عمده ای بر پیچیدگی آنها دارد. ما نشان می‌دهیم که مشکل دوگانه را می‌توان در ارزیابی مدار کوانتومی $O(M^{4.67}/varepsilon^2)$ حل کرد، که در آن $M$ نشان‌دهنده اندازه مجموعه داده‌ها و $varepsilon$ دقت راه‌حل در مقایسه با ایده‌آل است. حاصل از مقادیر دقیق انتظارات است که فقط در تئوری قابل حصول است. ما تحت یک فرض با انگیزه تجربی ثابت می‌کنیم که مشکل اولیه هسته‌ای را می‌توان در ارزیابی‌های $O(min {M^2/varepsilon^6, , 1/varepsilon^{10}})$ با استفاده از تعمیم یک کلاسیک شناخته‌شده حل کرد. الگوریتمی به نام پگاسوس. نتایج تجربی همراه نشان می‌دهد که این پیچیدگی‌های تحلیلی اساساً تنگ هستند. علاوه بر این، ما یک تقریب متغیر را برای ماشین‌های بردار پشتیبان کوانتومی بررسی می‌کنیم و نشان می‌دهیم که آموزش اکتشافی آنها در آزمایش‌های ما به مقیاس بهتری دست می‌یابد.

تصویر ویژه: تخمین مقدار هسته $k(mathbf{x}_i، mathbf{x}_j)$، که در آن $mathcal{E}(mathbf{x}_i)$ یک پارامتر واحد را با داده‌های $mathbf{x نشان می‌دهد. }_i$. تعداد شات ها توسط $R$ داده می شود که دقت تخمین هسته را کنترل می کند.

خلاصه محبوب

ماشین‌های بردار پشتیبان کوانتومی کاندیدایی برای نشان دادن مزیت کوانتومی در آینده نزدیک برای مسائل طبقه‌بندی هستند. ایده این است که یک تابع هسته (امیدواریم مفید) توسط یک مدار کوانتومی کارآمد ارائه شود که ارزیابی کلاسیک آن دشوار است. با توجه به ماهیت احتمالی مکانیک کوانتومی، چنین توابع هسته تحت تأثیر عدم قطعیت آماری قرار می گیرند. در این کار، ما به شدت تجزیه و تحلیل می کنیم که چگونه این عدم قطعیت (همچنین نویز شات نامیده می شود) بر پیچیدگی محاسباتی کلی برای حل مشکل طبقه بندی تأثیر می گذارد.

► داده های BibTeX

◄ مراجع

[1] J. Biamonte، P. Wittek، N. Pancotti، P. Rebentrost، N. Wiebe، و 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] A. عباس، D. Sutter، C. Zoufal، A. Lucchi، A. Figalli، و S. Woerner. قدرت شبکه های عصبی کوانتومی علوم محاسباتی طبیعت، 1 (ژوئن)، 2020. DOI: 10.1038/s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] Y. Liu، S. Arunachalam و K. Temme. یک افزایش سرعت کوانتومی دقیق و قوی در یادگیری ماشینی نظارت شده. Nature Physics، 2021. DOI: 10.1038/​s41567-021-01287-z.
https://doi.org/​10.1038/​s41567-021-01287-z

[5] اس. آرونسون. چاپ ریز را بخوانید. Nature Physics، 11 (4): 291-293، 2015. DOI: 10.1038/​nphys3272.
https://doi.org/​10.1038/​nphys3272

[6] ای تانگ. یک الگوریتم کلاسیک با الهام از کوانتوم برای سیستم های توصیه در مجموعه مقالات پنجاه و یکمین سمپوزیوم سالانه ACM SIGACT در تئوری محاسبات، STOC 51، صفحه 2019–217، نیویورک، نیویورک، ایالات متحده آمریکا، 228. انجمن ماشین های محاسباتی. DOI: 2019/​10.1145.
https://doi.org/​10.1145/​3313276.3316310

[7] N.-H. چیا، A. Gilyén، T. Li، H.-H. لین، ای تانگ و سی وانگ. چارچوب محاسباتی ماتریس رتبه پایین زیرخطی مبتنی بر نمونه برداری برای یادگیری ماشین کوانتومی کوانتومی، صفحه 387-400. انجمن ماشین‌های محاسباتی، نیویورک، نیویورک، ایالات متحده آمریکا، 2020. در دسترس آنلاین: https://doi.org/​10.1145/​3357713.3384314.
https://doi.org/​10.1145/​3357713.3384314

[8] T. Li، S. Chakrabarti و X. Wu. الگوریتم‌های کوانتومی زیرخطی برای آموزش طبقه‌بندی‌کننده‌های خطی و مبتنی بر هسته. در کنفرانس بین المللی یادگیری ماشین، صفحات 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.

[11] A. تامسن. مقایسه شبکه‌های عصبی کوانتومی و ماشین‌های بردار پشتیبان کوانتومی پایان نامه کارشناسی ارشد، ETH زوریخ، 2021-09-06. DOI: 20.500.11850/​527559.

[12] B. E. Boser، I. M. Guyon و V. N. Vapnik. الگوریتم آموزشی برای طبقه‌بندی‌کننده‌های حاشیه بهینه. در مجموعه مقالات پنجمین کارگاه سالانه نظریه یادگیری محاسباتی، COLT '92، صفحات 144-152، نیویورک، نیویورک، ایالات متحده آمریکا، 1992. انجمن ماشین های محاسباتی. DOI: 10.1145/130385.130401.
https://doi.org/​10.1145/​130385.130401

[13] C. Cortes و V. Vapnik. شبکه های بردار پشتیبانی در یادگیری ماشین، صفحات 273-297، 1995.

[14] V. N. Vapnik. ماهیت نظریه یادگیری مبتنی بر آمار. Springer Science+Business Media، LLC، 2000.

[15] F. Pedregosa و همکاران. Scikit-Learn: یادگیری ماشینی در پایتون. مجله تحقیقات یادگیری ماشین، 12 (85): 2825–2830، 2011. در دسترس آنلاین: http://jmlr.org/​papers/​v12/​pedregosa11a.html.
http://jmlr.org/​papers/​v12/​pedregosa11a.html

[16] S. Boyd و L. Vandenberghe. بهینه سازی محدب انتشارات دانشگاه کمبریج، 2004.

[17] S. Shalev-Shwartz، Y. Singer، N. Srebro و A. Cotter. Pegasos: حلگر زیر گرادیان برآورد شده اولیه برای SVM. برنامه ریزی ریاضی، 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 و همکاران Qiskit: یک چارچوب منبع باز برای محاسبات کوانتومی، 2021. DOI: 10.5281/​zenodo.2573505.
https://doi.org/​10.5281/​zenodo.2573505

[19] P. Rebentrost، M. محسنی و 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 و 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. ماشین های هسته کوانتومی پر سر و صدا. فیزیک Rev. 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. آموزش ماشین‌های بردار پشتیبانی برای تشخیص الگو. داده کاوی و کشف دانش، 2:121–167، 1998. موجود به صورت آنلاین: https://www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -machines-for-pattern-recognition/.
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، و 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] بلیس، واسیلیس، گونزالس-کاستیلو، ساموئل، ریسل، کریستینا، والکورسا، صوفیا، کومبارو، الیاس اف.، دیسرتوری، گونتر، و رایتر، فلورنتین. تجزیه و تحلیل هیگز با طبقه بندی کننده های کوانتومی 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 و همکاران. quadprog: حل کننده برنامه نویسی درجه دوم (پایتون). https://github.com/​quadprog/​quadprog، 2022.
https://github.com/​quadprog/​quadprog

[27] Y. Nesterov. سخنرانی های مقدماتی در مورد بهینه سازی محدب: یک دوره پایه. بهینه سازی کاربردی Springer، 2004. DOI: 10.1007/978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] جی. اسپال. مروری بر روش اغتشاش همزمان برای بهینه سازی کارآمد. خلاصه فنی جان هاپکینز APL، 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، و J. J. Meyer. آموزش هسته های جاسازی کوانتومی در کامپیوترهای کوانتومی کوتاه مدت فیزیک Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https://doi.org/​10.1103/​PhysRevA.106.042431

[31] R. Latała. برخی از برآوردهای هنجارهای ماتریس های تصادفی. مجموعه مقالات انجمن ریاضی آمریکا، 133 (5): 1273-1282، 2005. DOI: 10.1090/​s0002-9939-04-07800-1.
https:/​/​doi.org/​10.1090/​s0002-9939-04-07800-1

[32] آر. ورشینین. مقدمه ای بر تحلیل غیر مجانبی ماتریس های تصادفی. سنجش فشرده: نظریه و کاربردها، صفحات 210-268، 2009. DOI: 10.1017/​CBO9780511794308.006.
https://doi.org/​10.1017/​CBO9780511794308.006

[33] T. Hofmann، B. Schölkopf و A. J. Smola. روش های هسته در یادگیری ماشین Annals of Statistics, 36 (3): 1171-1220, 2008. DOI: 10.1214/​009053607000000677.
https://doi.org/​10.1214/​009053607000000677

[34] جی دبلیو دانیل. پایداری حل برنامه های درجه دوم قطعی. Mathematical Programming, 5(1):41-53, 1973. DOI: 10.1007/​BF01580110.
https://doi.org/​10.1007/​BF01580110

ذکر شده توسط

[1] الکساندر ام. دالزل، سام مک آردل، ماریو برتا، پرزمیسلاو بینیاس، چی فانگ چن، آندراس گیلین، کانر تی هان، مایکل جی. کاستوریانو، امیل تی. خابیبولین، الکساندر کوبیکا، گرانت سالتون، سامسون وانگ، و فرناندو جی‌اس‌ال برنداو، «الگوریتم‌های کوانتومی: بررسی برنامه‌ها و پیچیدگی‌های سرتاسری» arXiv: 2310.03011, (2023).

[2] ماریا شولد و ناتان کیلوران، "آیا مزیت کوانتومی هدف درستی برای یادگیری ماشین کوانتومی است؟" PRX Quantum 3 3, 030101 (2022).

[3] محمدحسن حسنشاهی، مارسین جاسترزبسکی، سارا مالیک و اوفر لهاو، «ماشین بردار پشتیبان تقویت‌شده کوانتومی برای طبقه‌بندی کهکشان‌ها» 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، "یادگیری ماشین کوانتومی در دستگاه‌های کوانتومی نزدیک‌مدت: وضعیت فعلی تکنیک‌های نظارت شده و بدون نظارت برای برنامه‌های کاربردی در دنیای واقعی". arXiv: 2307.00908, (2023).

[8] رائول هیز، ثور گرلاخ، ساشا موکه، سابین مولر، ماتیاس یاکوبز و نیکو پیاتکوفسکی، "تبیین مدارهای کوانتومی با مقادیر شیپلی: به سوی یادگیری ماشین کوانتومی قابل توضیح"، arXiv: 2301.09138, (2023).

[9] جولین گاکن، یان نایس، ریکاردو روسی، استفان وورنر و جوزپه کارلئو، "تکامل زمان کوانتومی متغیر بدون تانسور هندسی کوانتومی"، arXiv: 2303.12839, (2023).

[10] جیان جنتینتا، دیوید ساتر، کریستا زوفال، برایس فولر و استفان وورنر، "همترازی هسته کوانتومی با نزول گرادیان تصادفی"، arXiv: 2304.09899, (2023).

[11] فیلیپا داکت، گابریل فاچینی، مارسین جاسترزبسکی، سارا مالیک، سباستین رتی و تیم اسکنلون، "بازسازی بخش‌های مسیر ذرات باردار با یک ماشین بردار پشتیبان تقویت‌شده با کوانتومی". arXiv: 2212.07279, (2022).

[12] تراویس ال. شولتن، دریک پری، جوزف واشنگتن، جنیفر آر. گلیک، و توماس وارد، "مدلی برای زمان اجرای مدار و پیامدهای آن برای هسته های کوانتومی در اندازه های مجموعه داده های عملی"، 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، "بهینه سازی پارامتر کارآمد برای تراز کوانتومی هسته: یک رویکرد نمونه گیری فرعی در آموزش متغیر" ، 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 International (CC BY 4.0) مجوز. حق چاپ نزد دارندگان حق چاپ اصلی مانند نویسندگان یا مؤسسات آنها باقی می ماند.

تمبر زمان:

بیشتر از مجله کوانتومی