تعقيد آلات ناقلات الدعم الكمومي

تعقيد آلات ناقلات الدعم الكمومي

الطابع الزمني: 11 كانون الثاني (يناير) 2024 ، الساعة 9:08 صباحًا
عقدة المصدر: 3057476

جيان جينتينيتا1,2, آرني تومسن3,2, ديفيد سوتر2، وستيفان فورنر2

1معهد الفيزياء، مدرسة البوليتكنيك الفيدرالية في لوزان
2IBM Quantum ، IBM Research Europe - زيورخ
3قسم الفيزياء، ETH زيورخ

تجد هذه الورقة مثيرة للاهتمام أو ترغب في مناقشة؟ Scite أو ترك تعليق على 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$ الذي يتحكم في دقة تقدير kernel.

ملخص شعبي

تعد آلات ناقلات الدعم الكمي مرشحة لإظهار ميزة كمية في المستقبل القريب لمشكلات التصنيف. الفكرة هي أن وظيفة النواة (التي نأمل أن تكون مفيدة) يتم الحصول عليها من خلال دائرة كمومية فعالة يصعب تقييمها بشكل كلاسيكي. نظرًا للطبيعة الاحتمالية لميكانيكا الكم، تتأثر وظائف النواة هذه بعدم اليقين الإحصائي. في هذا العمل، نقوم بتحليل دقيق لكيفية تأثير حالة عدم اليقين هذه (وتسمى أيضًا ضوضاء الطلقة) على التعقيد الحسابي الشامل لحل مشكلة التصنيف.

► بيانات BibTeX

ferences المراجع

[1] J. Biamonte، P. Wittek، N. Pancotti، P. Rebentrost، N. Wiebe، and S. Lloyd. التعلم الآلي الكمي. طبيعة، 549 (7671): 195-202، 2017. DOI: 10.1038 / Nature23474.
الشبكي: / / doi.org/ 10.1038 / nature23474

[2] V. Havlíček، A. D. Córcoles، K. Temme، A. W. Harrow، A. Kandala، J. M. Chow، and J. M. Gambetta. التعلم الخاضع للإشراف مع مساحات الميزات المحسنة الكم. طبيعة، 567 (7747): 209-212، 2019. DOI: 10.1038/s41586-019-0980-2.
https:/​/​doi.org/​10.1038/​s41586-019-0980-2

[3] أ. عباس، د. سوتر، ج. زوفال، أ. لوتشي، أ. فيجالي، وس. وورنر. قوة الشبكات العصبية الكمومية. علوم الطبيعة الحسابية، 1 (يونيو)، 2020. DOI: 10.1038/​s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] Y. ليو، S. أروناتشالام، وك. تيمي. تسريع كمي صارم وقوي في التعلم الآلي الخاضع للإشراف. فيزياء الطبيعة، 2021. DOI: 10.1038/s41567-021-01287-z.
الشبكي: / / doi.org/ 10.1038 / s41567-021-01287 زي

[5] إس آرونسون. قراءة المطبوعة الجميلة. فيزياء الطبيعة، 11(4):291-293، 2015. DOI: 10.1038/nphys3272.
الشبكي: / / doi.org/ 10.1038 / nphys3272

[6] إي تانغ. خوارزمية كلاسيكية مستوحاة من الكم لأنظمة التوصية. في وقائع ندوة ACM SIGACT السنوية الحادية والخمسين حول نظرية الحوسبة، STOC 51، الصفحة 2019-217، نيويورك، نيويورك، الولايات المتحدة الأمريكية، 228. جمعية آلات الحوسبة. دوى: 2019/10.1145.
الشبكي: / / doi.org/ 10.1145 / 3313276.3316310

[7] ن.-ح. شيا، أ. جيلين، ت. لي، ه.-ه. لين، إي تانغ، وسي وانغ. الإطار الحسابي للمصفوفة الخطية المنخفضة الرتبة القائم على أخذ العينات من أجل تقليص تعلم الآلة الكمي، الصفحة 387-400. جمعية آلات الحوسبة، نيويورك، نيويورك، الولايات المتحدة الأمريكية، 2020. متاح عبر الإنترنت: https://​/​doi.org/​10.1145/3357713.3384314.
الشبكي: / / doi.org/ 10.1145 / 3357713.3384314

[8] T. لي، S. تشاكرابارتي، وX. وو. خوارزميات الكم الخطية لتدريب المصنفات الخطية والمعتمدة على النواة. في المؤتمر الدولي للتعلم الآلي، الصفحات 3815-3824. بي إم إل آر، 2019.

[9] S. ثاناسيلب، S. وانغ، M. سيريزو، وZ. هولمز. التركيز الأسي وعدم القدرة على التدريب في أساليب النواة الكمومية، 2022. DOI: 10.48550/ARXIV.2208.11060.
https: / / doi.org/10.48550 / ARXIV.2208.11060

[10] S. شاليف شوارتز ون. سريبرو. تحسين SVM: الاعتماد العكسي على حجم مجموعة التدريب. وقائع المؤتمر الدولي الخامس والعشرون للتعلم الآلي، الصفحات 25-928، 935.

[11] أ. تومسن. مقارنة الشبكات العصبية الكمومية وآلات ناقلات الدعم الكمومي. رسالة ماجستير، ETH زيورخ، 2021-09-06. دوى: 20.500.11850/527559.

[12] B. E. Boser، وI. M. Guyon، وV. N. Vapnik. خوارزمية تدريب لمصنفات الهامش الأمثل. في وقائع ورشة العمل السنوية الخامسة حول نظرية التعلم الحسابي، COLT '92، الصفحات 144-152، نيويورك، نيويورك، الولايات المتحدة الأمريكية، 1992. جمعية آلات الحوسبة. دوى: 10.1145/130385.130401.
الشبكي: / / doi.org/ 10.1145 / 130385.130401

[13] جيم كورتيس وف. فابنيك. شبكات ناقلات الدعم. في التعلم الآلي، الصفحات 273-297، 1995.

[14] في إن فابنيك. طبيعة نظرية التعليم الإحصائى. سبرينغر ساينس+بيزنس ميديا، ذ.م.م، 2000.

[15] واو بيدريجوسا وآخرون. Scikit-Learn: التعلم الآلي في بايثون. مجلة أبحاث التعلم الآلي، 12(85):2825-2830، 2011. متاحة على الإنترنت: http://​/jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/jmlr.org/​papers/​v12/​pedregosa11a.html

[16] S. بويد وL. فاندينبيرج. تحسين محدب. مطبعة جامعة كامبريدج، 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] إم دي إس أنيس وآخرون. Qiskit: إطار عمل مفتوح المصدر للحوسبة الكمومية، 2021. DOI: 10.5281/​zenodo.2573505.
https: / / doi.org/ 10.5281 / zenodo.2573505

[19] ب. ريبينتروست، م. محسني، و س. لويد. آلة ناقلات الدعم الكمي لتصنيف البيانات الكبيرة. رسائل المراجعة البدنية، 113(3):1-5، 2014. DOI: 10.1103/​PhysRevLett.113.130503.
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.113.130503

[20] جي كوبلر، س. بوخهولز، وبي شولكوبف. التحيز الاستقرائي للنواة الكمومية. في M. Ranzato، A. Beygelzimer، Y. Dauphin، P. Liang، and J. W. Vaughan، المحررون، التقدم في أنظمة معالجة المعلومات العصبية، المجلد 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é، and C. Ciuti. آلات نواة الكم صاخبة. فيز. القس أ، 106:052421، 2022. DOI: 10.1103/​PhysRevA.106.052421.
الشبكي: / / doi.org/ 10.1103 / PhysRevA.106.052421

[22] سي جي سي بورجس وسي جي سي بورجس. وهناك أمثلة توضيحية على الأجهزة ناقلات دعم التعرف على الأنماط. استخراج البيانات واكتشاف المعرفة، 2: 121–167، 1998. متاح على الإنترنت: https://​/​www.microsoft.com/​en-us/​research/​publication/a-tutorial-on-support-vector -آلات-التعرف على الأنماط/​.
https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector-machines-for-pattern-recognition/​

[23] إم سيريزو، إيه سون، تي فولكوف، إل سينسيو، وبي جيه كولز. الهضاب القاحلة التي تعتمد على دالة التكلفة في الدوائر الكمومية الضحلة. اتصالات الطبيعة, 12(1):1791, 2021. DOI: 10.1038/s41467-021-21728-w.
https: / / doi.org/ 10.1038 / s41467-021-21728-ث

[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، and P. J. Coles. خوارزميات الكم المتغيرة. مراجعات الطبيعة فيزياء، 3 (9): 625-644، 2021. DOI: 10.1038/s42254-021-00348-9.
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[26] ر. ماكجيببورن وآخرون. Quadprog: حل البرمجة التربيعية (بيثون). https://​/github.com/quadprog/quadprog، 2022.
https://​/github.com/quadprog/quadprog

[27] يو نيستيروف. محاضرات تمهيدية حول التحسين المحدب: دورة أساسية. التحسين التطبيقي. سبرينغر، 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، and 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. إتش إس ديركس، بي كيه فايرمان، وجي جي ماير. تدريب نواة التضمين الكمي على أجهزة الكمبيوتر الكمومية على المدى القريب. فيز. القس أ، 106:042431، 2022. DOI: 10.1103/​PhysRevA.106.042431.
الشبكي: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] ر. لاتالا. بعض التقديرات لمعايير المصفوفات العشوائية. وقائع الجمعية الرياضية الأمريكية، 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.
الشبكي: / / doi.org/ 10.1017 / CBO9780511794308.006

[33] T. هوفمان، B. شولكوبف، وA. J. سمولا. طرق النواة في التعلم الآلي. حوليات الإحصاء، 36(3):1171-1220، 2008. DOI: 10.1214/009053607000000677.
الشبكي: / / doi.org/ 10.1214 / 009053607000000677

[34] جي دبليو دانيال. ثبات حل البرامج التربيعية المحددة. البرمجة الرياضية، 5(1):41-53، 1973. DOI: 10.1007/BF01580110.
الشبكي: / / doi.org/ 10.1007 / BF01580110

دليلنا يستخدم من قبل

[1] ألكساندر إم. دالزيل، سام مكاردل، ماريو بيرتا، برزيميسلاف بينياس، تشي-فانغ تشين، أندراس جيلين، كونور تي. هان، مايكل جيه. كاستوريانو، إميل تي. خبيبولين، ألكسندر كوبيكا، جرانت سالتون، سامسون وانغ، و فرناندو جي إس إل برانداو، "خوارزميات الكم: دراسة استقصائية للتطبيقات والتعقيدات الشاملة"، أرخايف: 2310.03011, (2023).

[2] ماريا شولد وناثان كيلوران، "هل الميزة الكمية هي الهدف الصحيح لتعلم الآلة الكمومية؟"، PRX كوانتوم 3 3 ، 030101 (2022).

[3] محمد حسن حسن شاهي، مارسين جاسترزيبسكي، سارة مالك، وعوفر لاهاف، "آلة متجهة داعمة معززة كميًا لتصنيف المجرات"، تقنيات وأدوات RAS 2 1، 752 (2023).

[4] كوان-تشينغ تشين، شياوتيان شو، هنري ماخانوف، هوي-هسوان تشونغ، وتشن-يو ليو، "آلة ناقل الدعم المعززة الكم لتصنيف النجوم على نطاق واسع مع تسريع وحدة معالجة الرسومات"، أرخايف: 2311.12328, (2023).

[5] سوبانوت ثاناسيلب ، سامسون وانج ، إم سيريزو ، وزوي هولمز ، "التركيز الأسي وعدم القدرة على التدريب في طرق النواة الكمومية" ، أرخايف: 2208.11060, (2022).

[6] كوهي ناكاجي وهيرويوكي تيزوكا وناوكي ياماموتو، "الشبكات العصبية الهجينة الكمومية الكلاسيكية في نظام النواة العصبية المماسية"، علوم وتكنولوجيا الكم 9 1، 015022 (2024).

[7] ياسويثا جوجو، وأتسوشي ماتسو، ورودي ريموند، "تعلم الآلة الكمومية على الأجهزة الكمومية قريبة المدى: الحالة الحالية للتقنيات الخاضعة للإشراف وغير الخاضعة للإشراف لتطبيقات العالم الحقيقي"، أرخايف: 2307.00908, (2023).

[8] راؤول هيسي، ثور جيرلاخ، ساشا موكي، سابين مولر، ماتياس جاكوبس، ونيكو بياتكوفسكي، "شرح الدوائر الكمومية بقيم شابلي: نحو تعلم الآلة الكمومية القابلة للتفسير"، أرخايف: 2301.09138, (2023).

[9] جوليان جاكون، جانيس نيس، ريكاردو روسي، ستيفان وورنر، وجوزيبي كارليو، "تطور الزمن الكمي المتغير بدون الموتر الهندسي الكمي"، أرخايف: 2303.12839, (2023).

[10] جيان جينتينيتا، ديفيد سوتر، كريستا زوفال، برايس فولر، وستيفان وورنر، "محاذاة النواة الكمومية مع نزول التدرج العشوائي"، أرخايف: 2304.09899, (2023).

[11] فيليبا داكيت، غابرييل فاسيني، مارسين جاسترزيبسكي، سارة مالك، سيباستيان ريتي، وتيم سكانلون، "إعادة بناء مقاطع مسار الجسيمات المشحونة باستخدام آلة متجهة داعمة معززة كميًا"، أرخايف: 2212.07279, (2022).

[12] ترافيس ل. شولتن، ديريك بيري، جوزيف واشنطن، جينيفر ر. جليك، وتوماس وارد، "نموذج لوقت تشغيل تنفيذ الدائرة وآثاره على النواة الكمومية في أحجام مجموعة البيانات العملية"، أرخايف: 2307.04980, (2023).

[13] سامانثا ف. بارون، دانييل ج. إيجر، إيليا بيلوفسكي، أندرياس بارتشي، ستيفان إيدنبينز، ماتيس ليمكوهلر، وستيفان فورنر، "الحدود الممكن إثباتها لقيم التوقع الخالية من الضوضاء المحسوبة من عينات صاخبة"، أرخايف: 2312.00733, (2023).

[14] إمري شاهين، بنجامين سي. بي سيمونز، بوشباك باتي، فاياز مينهاس، ديكلان ميلار، ماريا جابراني، جان لوكاس روبرتوس، وستيفانو مينسا، "التحسين الفعال للمعلمات لمحاذاة النواة الكمومية: نهج أخذ العينات الفرعية في التدريب المتغير" , أرخايف: 2401.02879, (2024).

الاستشهادات المذكورة أعلاه من إعلانات ساو / ناسا (تم آخر تحديث بنجاح 2024-01-12 02:12:22). قد تكون القائمة غير كاملة نظرًا لأن جميع الناشرين لا يقدمون بيانات اقتباس مناسبة وكاملة.

On خدمة Crossref's cited-by service لم يتم العثور على بيانات حول الاستشهاد بالأعمال (المحاولة الأخيرة 2024-01-12 02:12:21).

نشرت هذه الورقة في الكم تحت نسبة المشاع الإبداعي 4.0 الدولية (CC BY 4.0) رخصة. يظل حقوق الطبع والنشر مع مالكي حقوق الطبع والنشر الأصليين مثل المؤلفين أو مؤسساتهم.

الطابع الزمني:

اكثر من مجلة الكم