يمكن تعلم PAC بشكل صحيح لدارات Clifford إذا وفقط إذا كان $ textf {RP} = textf {NP} $

يمكن تعلم PAC بشكل صحيح لدارات Clifford إذا وفقط إذا كان $ textf {RP} = textf {NP} $

الطابع الزمني: 7 حزيران (يونيو) 2023 ، الساعة 6:07 صباحًا
عقدة المصدر: 2706854

دانيال ليانغ

قسم علوم الكمبيوتر ، جامعة تكساس في أوستن

تجد هذه الورقة مثيرة للاهتمام أو ترغب في مناقشة؟ Scite أو ترك تعليق على SciRate.

ملخص

بالنظر إلى مجموعة بيانات لحالات الإدخال والقياسات والاحتمالات ، هل من الممكن التنبؤ بكفاءة باحتمالات القياس المرتبطة بدائرة الكم؟ الأعمال الأخيرة لكارو وداتا [19] درس مشكلة تعلم الدوائر الكمومية PAC بالمعنى النظري للمعلومات ، تاركًا أسئلة مفتوحة حول الكفاءة الحسابية. على وجه الخصوص ، فئة واحدة من الدوائر المرشحة التي قد يكون المتعلم الكفء ممكنًا لها هي تلك الخاصة بدارات كليفورد ، نظرًا لأن مجموعة الحالات المقابلة التي تم إنشاؤها بواسطة هذه الدوائر ، والتي تسمى حالات التثبيت ، معروفة بأنها قابلة للتعلم بكفاءة PAC [44]. نقدم هنا نتيجة سلبية ، توضح أن التعلم الصحيح لدارات CNOT مع خطأ 1 / poly ($ n $) يصعب على المتعلمين الكلاسيكيين ما لم يكن $ textf {RP = NP} $ ، مما يستبعد إمكانية وجود متعلمين أقوياء في ظل نظرية التعقيد القياسي الافتراضات. نظرًا لكونه المجموعة التناظرية والفرعية الكلاسيكية لدارات كليفورد ، فإن هذا يؤدي بطبيعة الحال إلى نتيجة صلابة لدارات كليفورد أيضًا. بالإضافة إلى ذلك ، نوضح أنه إذا كان $ textf {RP = NP} $ سيكون هناك خوارزميات تعليمية مناسبة وفعالة لدارات CNOT و Clifford. من خلال الحجج المماثلة ، نجد أيضًا وجود متعلم كم مناسب فعال لمثل هذه الدوائر إذا وفقط إذا كان $ textf {NP ⊆ RQP} $. نترك مشكلة الصلابة للتعلم غير السليم أو $ mathcal {O (1)} $ error للعمل في المستقبل.

► بيانات BibTeX

ferences المراجع

[1] سكوت آرونسون. قابلية تعلم الحالات الكمومية. وقائع الجمعية الملكية أ: العلوم الرياضية والفيزيائية والهندسية ، 463 (2088): 3089 - 3114 ، 2007. 10.1098 / rspa.2007.0113.
الشبكي: / / doi.org/ 10.1098 / rspa.2007.0113

[2] سكوت آرونسون. تصوير الظل المقطعي للحالات الكمومية. في وقائع الندوة السنوية الخمسين لـ ACM SIGACT حول نظرية الحوسبة ، STOC 50 ، الصفحة 2018-325 ، نيويورك ، نيويورك ، الولايات المتحدة الأمريكية ، 338. Association for Computing Machinery. ردمك 2018 / 9781450355599.
الشبكي: / / doi.org/ 10.1145 / 3188745.3188802

[3] سكوت آرونسون ودانييل جوتسمان. محاكاة محسنة لدارات التثبيت. مراجعة البدنية أ ، 70 (5): 052328 ، 2004. 10.1103 / physreva.70.052328.
الشبكي: / / doi.org/ 10.1103 / physreva.70.052328

[4] J. B. Altepeter، D. Branning، E. Jeffrey، T. C. Wei، P. G. Kwiat، R. T. Thew، J. L. O'Brien، M. A. Nielsen، and A. G. White. التصوير المقطعي للعملية الكمومية بمساعدة Ancilla. فيز. القس ليت، 90: 193601، مايو 2003. 10.1103/​PhysRevLett.90.193601.
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.90.193601

[5] مارتن أنتوني وبيتر إل بارتليت. وظيفة التعلم من الاستيفاء. التوافقية والاحتمالية والحوسبة ، 9 (3): 213-225 ، 2000. 10.1017 / S0963548300004247.
الشبكي: / / doi.org/ 10.1017 / S0963548300004247

[6] سرينيفاسان أروناتشالام ورونالد دي وولف. عمود الضيف: مسح لنظرية التعلم الكمي. أخبار ACM SIGACT ، 48 (2): 41-67 ، 2017. 10.1145 / 3106700.3106710.
الشبكي: / / doi.org/ 10.1145 / 3106700.3106710

[7] سرينيفاسان أروناتشالام ورونالد دي وولف. تعقيد العينة الكمية الأمثل لخوارزميات التعلم. في ريان أودونيل، محرر، مؤتمر التعقيد الحسابي الثاني والثلاثون (CCC 32)، المجلد 2017 من Leibniz International Proceedings in Informatics (LIPIcs)، الصفحات 79:25–1:25، داغستوهل، ألمانيا، 31. Schloss Dagstuhl–Leibniz-Zentrum مزيد من المعلوماتية. ردمك 2017-978-3-95977-040. 8/LIPIcs.CCC.10.4230.
الشبكي: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.25

[8] سرينيفاسان أروناشالام وأليكس ب جريلو وهنري يوين. تعلم الاستعلام الإحصائي الكمي. تمهيدي arXiv arXiv: 2002.08240 ، 2020. https: / / doi.org/ 10.48550 / arXiv.2002.08240.
https: / / doi.org/10.48550 / arXiv.2002.08240
أرخايف: 2002.08240

[9] سرينيفاسان أروناشالام وأليكس بريداريول غريلو وآرثي سوندارام. الصلابة الكمية لتعلم الدوائر الكلاسيكية الضحلة. مجلة SIAM للحوسبة ، 50 (3): 972-1013 ، 2021. 10.1137 / 20M1344202.
الشبكي: / / doi.org/ 10.1137 / 20M1344202

[10] تشارلز إتش بينيت وجيل براسارد. التشفير الكمي: توزيع المفتاح العام ورمي العملات المعدنية. علوم الكمبيوتر النظرية ، 560: 7-11 ، ديسمبر 2014. ISSN 0304-3975. 10.1016 / j.tcs.2014.05.025.
الشبكي: / / doi.org/ 10.1016 / j.tcs.2014.05.025

[11] تشارلز إتش بينيت وستيفن جيه وايزنر. الاتصال عبر مشغلي الجسيم الواحد والثاني في حالات أينشتاين-بودولسكي-روزن. فيز. القس ليت ، 69: 2881-2884 ، نوفمبر 1992. 10.1103 / PhysRevLett.69.2881.
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.69.2881

[12] بينيت ، وجيل براسار ، وكلود كريبو ، وريتشارد جوزسا ، وآشر بيريز ، وويليام ك. ووترز. النقل الآني لحالة كمومية غير معروفة عبر قنوات ثنائية كلاسيكية وقنوات آينشتاين-بودولسكي-روزن. فيز. القس ليت. ، 70: 1895-1899 ، مارس 1993. 10.1103 / PhysRevLett.70.1895.
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.70.1895

[13] إيثان برنشتاين وأوميش فازيراني. نظرية التعقيد الكمومي. مجلة SIAM للحوسبة ، 26 (5): 1411-1473 ، 1997. 10.1137 / S0097539796300921.
الشبكي: / / doi.org/ 10.1137 / S0097539796300921

[14] أفريم بلوم. الصلابة الحسابية في التعلم. http: / / www.cs.cmu.edu/ avrim / ML07 / lect1007.pdf ، 2015. URL http: / / www.cs.cmu.edu/ avrim / ML07 / lect1007 .بي دي إف. ملاحظات محاضرة لـ CS 10-806 أسس التعلم الآلي وعلوم البيانات.
http: / / www.cs.cmu.edu/ ~ avrim / ML07 / lect1007.pdf

[15] أفريم إل بلوم ورونالد إل ريفست. تدريب شبكة عصبية ثلاثية العقد مكتمل np. الشبكات العصبية ، 3 (5): 1-117 ، 127. ISSN 1992-0893. https: / / doi.org/ 6080 / S10.1016-0893 (6080) 05-80010.
https:/​/​doi.org/​10.1016/​S0893-6080(05)80010-3

[16] أنسلم بلومر ، أ. إهرنفخت ، ديفيد هوسلر ، ومانفريد ك.ورموث. قابلية التعلم والبعد vapnik-chervonenkis. J. ACM، 36 (4): 929-965 ، أكتوبر 1989. ISSN 0004-5411. 10.1145 / 76359.76371.
الشبكي: / / doi.org/ 10.1145 / 76359.76371

[17] جوناثان إف بوس ، جودموند فراندسن ، وجيفري أو شاليت. التعقيد الحسابي لبعض مسائل الجبر الخطي. مجلة علوم الحاسب والنظم ، 58 (3): 572-596 ، 1999. ISSN 0022-0000. https: / / doi.org/ 10.1006 / jcss.1998.1608.
https: / / doi.org/ 10.1006 / jcss.1998.1608

[18] ماتياس سي كارو. التصنيف الثنائي مع الأمثلة الكلاسيكية والتسميات الكمومية. ذكاء آلة الكم ، 3 (1) ، مايو 2021. 10.1007 / s42484-021-00043-z.
الشبكي: / / doi.org/ 10.1007 / s42484-021-00043 زي

[19] ماتياس سي كارو وإيشون داتا. البعد الزائف للدوائر الكمومية. ذكاء آلة الكم ، 2 (2) ، نوفمبر 2020. ISSN 2524-4914. 10.1007 / s42484-020-00027-5.
https:/​/​doi.org/​10.1007/​s42484-020-00027-5

[20] هاو-تشونج تشينج ، ومين-هسيو هسيه ، وبينج-تشينج يه. معرفة القياسات الكمومية غير المعروفة. معلومات الكم. الكمبيوتر ، 16 (7-8): 615-656 ، مايو 2016. ISSN 1533-7146. 10.26421 / QIC16.7-8-4.
https: / / doi.org/ 10.26421 / QIC16.7-8-4

[21] إسحاق إل تشوانج وما أ. نيلسن. وصفة طبية لتحديد ديناميكيات الصندوق الأسود الكمومي تجريبيًا. مجلة البصريات الحديثة ، 44 (11-12): 2455-2467 ، 1997. 10.1080 / 09500349708231894.
الشبكي: / / doi.org/ 10.1080 / 09500349708231894

[22] كاي مين تشونغ وهان هسوان لين. عينة من الخوارزميات الفعالة لتعلم القنوات الكمية في نموذج PAC ومشكلة تمييز الدولة التقريبية. في Min-Hsiu Hsieh ، محرر ، المؤتمر السادس عشر حول نظرية الحساب الكمي والتواصل والتشفير (TQC 16) ، المجلد 2021 من Leibniz International Proceedings in Informatics (LIPIcs) ، الصفحات 197: 3–1: 3 ، Dagstuhl ، ألمانيا ، 22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. ردمك 2021-978-3-95977-198. 6 / LIPIcs.TQC.10.4230.
الشبكي: / / doi.org/ 10.4230 / LIPIcs.TQC.2021.3

[23] أميت دانييلي وشاي شاليف شوارتز. القيود النظرية للتعقيد على تعلم DNF. في فيتالي فيلدمان، وألكسندر راخلين، وأوهاد شامير، المحررون، المؤتمر السنوي التاسع والعشرون حول نظرية التعلم، المجلد 29 من وقائع أبحاث التعلم الآلي، الصفحات 49-815، جامعة كولومبيا، نيويورك، نيويورك، الولايات المتحدة الأمريكية، 830-23 يونيو 26 .بي إم إل آر. عنوان URL https://proceedings.mlr.press/v2016/daniely49.html.
https: / / Actions.mlr.press/ v49 / daniely16.html

[24] ستيفن تي فلاميا ، ديفيد جروس ، يي كاي ليو ، وجينز إيسرت. التصوير المقطعي الكمي عن طريق الاستشعار المضغوط: حدود الخطأ وتعقيد العينة والمقدرات الفعالة. المجلة الجديدة للفيزياء ، 14 (9): 095022 ، سبتمبر 2012. 10.1088 / 1367-2630 / 14/9/095022.
https:/​/​doi.org/​10.1088/​1367-2630/​14/​9/​095022

[25] بول دبليو غولدبرغ ومارك آر جيروم. إحاطة بُعد vapnik-chervonenkis لفئات المفاهيم المحددة بواسطة أرقام حقيقية. تعلم الآلة ، 18: 131-148 ، 1995. 10.1007 / BF00993408.
الشبكي: / / doi.org/ 10.1007 / BF00993408

[26] دانيال جوتسمان. رموز المثبت وتصحيح الخطأ الكمي ، 1997.

[27] دانيال جوتسمان. تمثيل هايزنبرغ لأجهزة الكمبيوتر الكمومية ، 1998.

[28] فينكاتيسان جورسوامي وبراساد راغافيندرا. صلابة تعلم مسافات نصفية مع ضوضاء. مجلة SIAM للحوسبة ، 39 (2): 742-765 ، 2009. 10.1137 / 070685798.
الشبكي: / / doi.org/ 10.1137 / 070685798

[29] Jeongwan Haah و Aram W. Harrow و Zhengfeng Ji و Xiaodi Wu و Nengkun Yu. عينة التصوير المقطعي الأمثل للحالات الكمومية. معاملات IEEE على نظرية المعلومات ، الصفحات 1–1 ، 2017. ISSN 1557-9654. 10.1109 / tit.2017.2719044.
https: / / doi.org/ 10.1109 / tit.2017.2719044

[30] نيكا حتطلب. المحاضرة التاسعة : صعوبات التعلم. https://​/​www.cs.cornell.edu/​courses/​cs9/​6781sp/​lectures/​2020-hardness09.pdf, 1. URL https://​/​www.cs.cornell.edu/ ​دورات/cs2020/​6781sp/​محاضرات/​2020-hardness09.pdf. ملاحظات محاضرة لـ CS1 - الأسس النظرية للتعلم الآلي.
https: / / www.cs.cornell.edu/ course / cs6781 / 2020sp / lectures / 09-hardness1.pdf

[31] هسين يوان هوانغ وريتشارد كوينج وجون بريسكيل. توقع العديد من خصائص النظام الكمي من خلال قياسات قليلة جدًا. فيزياء الطبيعة ، أكتوبر 2020. 10.1038 / s41567-020-0932-7.
https:/​/​doi.org/​10.1038/​s41567-020-0932-7

[32] جوناثان كاتز. ملاحظات حول محاضرة نظرية التعقيد 3. https: / / www.cs.umd.edu/ jkatz / complexity / f11 / lecture3.pdf، 2011. URL https: / / www.cs.umd. edu / jkatz / complexity / f11 / lecture3.pdf. ملاحظات محاضرة لـ CS 652 - نظرية التعقيد.
https: / / www.cs.umd.edu/ ~ jkatz / complexity / f11 / lecture3.pdf

[33] مايكل خاريتونوف. صلابة التشفير للتعلم الخاص بالتوزيع. في وقائع ندوة ACM السنوية الخامسة والعشرين حول نظرية الحوسبة، STOC '93، الصفحة 372-381، نيويورك، نيويورك، الولايات المتحدة الأمريكية، 1993. جمعية آلات الحوسبة. ردمك 0897915917/10.1145.
الشبكي: / / doi.org/ 10.1145 / 167088.167197

[34] J. Kleinberg و E. Tardos. تصميم الخوارزمية. Pearson Education ، 2022. ISBN 9780132131087. URL https: / / books.google.com/ books؟ id = GORecgAACAAJ.
https: / / books.google.com/ books؟ id = GORecgAACAAJ

[35] آدم كليفانز. نموذج التعلم PAC. https: / / www.cs.utexas.edu/ klivans / f06lec2.pdf ، 2005. URL https: / / www.cs.utexas.edu/ klivans / f06lec2.pdf. ملاحظات محاضرة لنظرية التعلم الحاسوبي CS 395T.
https: / / www.cs.utexas.edu/ ~ klivans / f06lec2.pdf

[36] روبرت كونيغ وجون أ.سمولين. كيفية تحديد عنصر مجموعة clifford التعسفي بكفاءة. مجلة الفيزياء الرياضية ، 55 (12): 122202 ، ديسمبر 2014. ISSN 1089-7658. 10.1063 / 1.4903507.
الشبكي: / / doi.org/ 10.1063 / 1.4903507

[37] ريتشارد كينج وديفيد جروس. حالات استقرار Qubit هي تصميمات إسقاطية معقدة 3 ، 2015.

[38] تشينغ يي لاي وهاو تشونغ تشنغ. تعلم الدوائر الكمومية لبعض البوابات. معاملات IEEE على نظرية المعلومات ، الصفحات 1–1 ، 2022. 10.1109 / TIT.2022.3151760.
الشبكي: / / doi.org/ 10.1109 / TIT.2022.3151760

[39] ريتشارد أ.لو. تعلم واختبار الخوارزميات لمجموعة كليفورد. فيز. القس أ ، 80: 052314 ، نوفمبر 2009. 10.1103 / PhysRevA.80.052314.
الشبكي: / / doi.org/ 10.1103 / PhysRevA.80.052314

[40] اشلي مونتانارو. حالات استقرار التعلم بواسطة عينات بيل ، 2017.

[41] ريان أودونيل وجون رايت. التصوير المقطعي الكمي الفعال. في وقائع ندوة ACM السنوية الثامنة والأربعين حول نظرية الحوسبة، STOC '16، الصفحة 899-912، نيويورك، نيويورك، الولايات المتحدة الأمريكية، 2016. جمعية آلات الحوسبة. ردمك 9781450341325/10.1145.
الشبكي: / / doi.org/ 10.1145 / 2897518.2897544

[42] ريان أودونيل وجون رايت. التصوير المقطعي الكمي الفعال ii. في وقائع ندوة ACM SIGACT السنوية التاسعة والأربعين حول نظرية الحوسبة، STOC 49، الصفحة 2017-962، نيويورك، نيويورك، الولايات المتحدة الأمريكية، 974. جمعية آلات الحوسبة. ردمك 2017/9781450345286.
الشبكي: / / doi.org/ 10.1145 / 3055399.3055454

[43] يهوي كويك ، سرينيفاسان أروناتشالام ، وجون أ سمولين. التعلم الخاص يعني الاستقرار الكمي. في M. Ranzato ، A. Beygelzimer ، Y. Dauphin ، PS Liang ، و J. Wortman Vaughan ، محررون ، التطورات في أنظمة معالجة المعلومات العصبية ، المجلد 34 ، الصفحات 20503-20515. Curran Associates، Inc.، 2021. URL https: / / events.neurips.cc/ paper / 2021 / file / abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2021/​file/​abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf

[44] أندريا روتشيتو. حالات المثبت يمكن تعلمها بكفاءة PAC. معلومات الكم والحساب ، 18 (7-8): 541-552 ، 2018. 10.26421 / qic18.7-8-1.
https: / / doi.org/ 10.26421 / qic18.7-8-1

[45] بيتر دبليو شور. خوارزميات متعددة الحدود للعوامل الأولية واللوغاريتمات المنفصلة على جهاز كمبيوتر كمي. مراجعة SIAM، 41 (2): 303-332، 1999. 10.1137 / S0036144598347011.
الشبكي: / / doi.org/ 10.1137 / S0036144598347011

[46] دانيال ر. سايمون. على قوة الحساب الكمي. مجلة SIAM للحوسبة ، 26 (5): 1474–1483 ، 1997. 10.1137 / S0097539796298637.
الشبكي: / / doi.org/ 10.1137 / S0097539796298637

[47] ليزلي جي فاليانت. ونظرية قابلة للتعلم. اتصالات من ACM ، 27 (11): 1134-1142 ، 1984. 10.1145 / 1968.1972.
الشبكي: / / doi.org/ 10.1145 / 1968.1972

[48] إيووت فان دن بيرج. طريقة بسيطة لأخذ عينات عشوائية من مشغلي كليفورد. في عام 2021 مؤتمر IEEE الدولي للحوسبة الكمية والهندسة (QCE) ، الصفحات 54-59 ، 2021. 10.1109 / QCE52317.2021.00021.
https: / / doi.org/10.1109 / QCE52317.2021.00021

[49] ميثونا يوجاناثان. حالة تنطوي بموجبها المحاكاة الكلاسيكية على قابلية تعلم فعالة للحالة ، 2019.

[50] Huangjun Zhu. مجموعات كليفورد Multiqubit هي تصاميم أحادية 3. فيز. القس أ ، 96: 062336 ، ديسمبر 2017. 10.1103 / PhysRevA.96.062336.
الشبكي: / / doi.org/ 10.1103 / PhysRevA.96.062336

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

[1] لورينزو ليون، سلفاتوري إف إي أوليفيرو، سيث لويد، وأليوشيا هاما، "تعلم أجهزة فك التشفير الفعالة لأجهزة التشويش الكمومية شبه الفوضوية"، أرخايف: 2212.11338, 2022.

[2] سرينيفاسان أروناتشالام، سيرجي برافي، أركوبال دوت، وثيودور ج. يودر، "الخوارزميات المثالية لتعلم حالات الطور الكمي"، أرخايف: 2208.07851, 2022.

[3] أنوراغ أنشو وسرينيفاسان أروناتشالام، "دراسة استقصائية حول مدى تعقيد تعلم الحالات الكمومية"، أرخايف: 2305.20069, 2023.

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

On خدمة Crossref المستشهد بها لم يتم العثور على بيانات حول الاستشهاد بالأعمال (المحاولة الأخيرة 2023-06-07 22:21:40).

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

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

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