شعار زيفيرنت

تقريب ديناميات هاميلتون مع طريقة نيستروم

التاريخ:

اليساندرو رودي1ليونارد فوسنيج2,3كارلو سيليبيرتو2أندريا روتشيتو2,4,5ماسيميليانو بونتيل6، وسيمون سيفيريني2

1INRIA - فريق مشروع سييرا ، باريس ، فرنسا
2قسم علوم الحاسوب ، كلية لندن الجامعية ، لندن ، المملكة المتحدة
3Rahko Ltd. ، لندن ، المملكة المتحدة
4قسم علوم الكمبيوتر ، جامعة تكساس في أوستن ، أوستن ، الولايات المتحدة
5قسم علوم الحاسوب ، جامعة أكسفورد ، أكسفورد ، المملكة المتحدة
6الإحصاء الحسابي والتعلم الآلي ، IIT ، جنوة ، إيطاليا

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

ملخص

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

► بيانات BibTeX

ferences المراجع

[1] أهارونوف وتا شما "إجراءات توليد الدولة الكمومية والمعرفة الصفرية الإحصائية" لندوة ACM السنوية الخامسة والثلاثين حول نظرية الحوسبة 20-29 (2003).
الشبكي: / / doi.org/ 10.1145 / 780542.780546

[2] ألكسندروف و Peller "وظائف المشغل Lipschitz" المسوحات الرياضية الروسية 71 ، 605 (2016).
الشبكي: / / doi.org/ 10.1070 / RM9729

[3] Belabbas and Wolfe "تقريب سريع منخفض الدرجة لمصفوفات التغاير" ورشة العمل الدولية الثانية IEEE حول التقدم الحسابي في المعالجة التكيفية متعددة أجهزة الاستشعار ، 2. 2007-293 (296).
الشبكي: / / doi.org/ 10.1109 / CAMSAP.2007.4498023

[4] Belabbas و Wolfe "في تمثيلات متفرقة للعوامل الخطية وتقريب منتجات المصفوفة" المؤتمر السنوي الثاني والأربعون لعلوم ونظم المعلومات 42-258 (263).
الشبكي: / / doi.org/ 10.1109 / CISS.2008.4558532

[5] بيري ، تشايلدز وكوثاري ، "محاكاة هاميلتونية مع اعتماد مثالي تقريبًا على جميع المعلمات" الندوة السنوية 56 IEEE على أسس علوم الكمبيوتر (FOCS) 792-809 (2015).
الشبكي: / / doi.org/ 10.1109 / FOCS.2015.54

[6] Biamonte و Wittek و Pancotti و Rebentrost و Wiebe و Lloyd ، "تعلم الآلة الكمومي" Nature 549، 195 (2017).
الشبكي: / / doi.org/ 10.1038 / nature23474

[7] Bravyi و Browne و Calpin و Campbell و Gosset و Howard ، "محاكاة الدوائر الكمومية من خلال تحليلات التثبيت منخفضة الرتبة" arXiv preprint arXiv: 1808.00128 (2018).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[8] شيا ، جيلين ، لي ، لين ، تانغ ، ووانغ ، "إطار حسابي مصفوفة رتبية فرعية منخفضة الخط قائم على أخذ العينات لتمييز التعلم الآلي الكمومي" arXiv preprint arXiv: 1910.06151 (2019).

[9] تشايلدز وكوثاري "محاكاة هاميلتونيين متناثرات مع تحلل النجوم" وقائع المؤتمر الخامس لنظرية حساب الكم والاتصال والتشفير 5-94 (103).
https:/​/​doi.org/​10.1007/​978-3-642-18073-6_8

[10] تشايلدز وويبي "محاكاة هاميلتونية باستخدام تركيبات خطية من العمليات الوحدوية". احسب. 12 ، 901-924 (2012).
الشبكي: / / doi.org/ 10.5555 / 2481569.2481570

[11] تشايلدز ، كليف ، ديوتو ، فرحي ، غوتمان ، وسبيلمان ، "تسريع الخوارزميات الأسي بواسطة المشي الكمومي" وقائع الندوة السنوية الخامسة والثلاثين لـ ACM حول نظرية الحوسبة 59-68 (2003).
الشبكي: / / doi.org/ 10.1145 / 780542.780552

[12] Ciliberto و Herbster و Ialongo و Pontil و Rocchetto و Severini و Wossnig ، "التعلم الآلي الكمومي: منظور كلاسيكي" Proc. R. Soc. أ 474 ، 20170551 (2018).
الشبكي: / / doi.org/ 10.1098 / rspa.2017.0551

[13] Drineas و Kannan و Mahoney ، "خوارزميات مونت كارلو السريعة للمصفوفات I: تقريب ضرب المصفوفة" SIAM Journal on Computing 36، 132-157 (2006).
الشبكي: / / doi.org/ 10.1137 / S0097539704442684

[14] Drineas و Kannan و Mahoney ، "خوارزميات مونت كارلو السريعة للمصفوفات II: حساب تقريب منخفض الرتبة إلى مصفوفة" SIAM Journal على الحوسبة 36 ، 158-183 (2006).
الشبكي: / / doi.org/ 10.1137 / S0097539704442696

[15] Drineas and Mahoney "على طريقة نيستروم لتقريب مصفوفة غرام لتحسين التعلم القائم على النواة" J. Mach. تعلم. الدقة. 6 ، 2153-2175 (2005).
الشبكي: / / doi.org/ 10.5555 / 1046920.1194916

[16] Drineas and Mahoney "محاضرات حول الجبر الخطي العددي العشوائي" رياضيات البيانات 25 ، 1 (2018).

[17] Drineas و Mahoney و Muthukrishnan و Sarlós ، "تقريب أسرع المربعات الصغرى" Numer. الرياضيات. 117 ، 219-249 (2011).
https:/​/​doi.org/​10.1007/​s00211-010-0331-6

[18] Fowlkes و Belongie و Chung و Malik ، "التجميع الطيفي باستخدام طريقة Nyström" IEEE Trans. نمط الشرج. ماخ. انتل. 26 ، 214-225 (2004).
الشبكي: / / doi.org/ 10.1109 / TPAMI.2004.1262185

[19] Frieze، Kannan، and Vempala، "Fast Monte-Carlo Algorithms for Finding Approxations Low-Rank Rations" J. ACM 51، 1025-1041 (2004).
الشبكي: / / doi.org/ 10.1145 / 1039488.1039494

[20] Haegeman و Cirac و Osborne و Pižorn و Verschelde و Verstraete ، "مبدأ التباين المعتمد على الوقت للشبكات الكمومية" رسائل المراجعة البدنية 107 ، 070601 (2011).
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.107.070601

[21] Higham "طريقة المقياس والتربيع لمراجعة المصفوفة الأسية" SIAM J. Matrix Anal. تطبيق 26 ، 1179-1193 (2005).
الشبكي: / / doi.org/ 10.1137 / 04061101X

[22] هيغام "طريقة التحجيم والتربيع لمراجعة المصفوفة الأسية" SIAM Rev. 51، 747-764 (2009).
الشبكي: / / doi.org/ 10.1137 / 090768539

[23] Hsu "أخذ العينات المرجحة للمنتجات الخارجية" arXiv preprint arXiv: 1410.4429 (2014).

[24] هوانغ ، نيومان ، وسيجيدي ، "حدود سفلية صريحة على محاكاة كمومية قوية" arXiv preprint arXiv: 1804.10368 (2018).

[25] Jónsson و Bauer و Carleo ، "حالات الشبكة العصبية للمحاكاة الكلاسيكية للحوسبة الكمومية" arXiv preprint arXiv: 1808.05232 (2018).

[26] كيرينيديس وبراكاش "أنظمة التوصية الكمية" arXiv preprint arXiv: 1603.08675 (2016).

[27] Kimmel ، Lin ، Low ، Ozols ، و Yoder ، "محاكاة هاميلتونية مع تعقيد العينة الأمثل" npj Quantum Information 3، 13 (2017).
https:/​/​doi.org/​10.1038/​s41534-017-0013-7

[28] كومار ، مهري ، وتالوالكار ، "حول التحلل الطيفي التقريبي المستند إلى أخذ العينات" وقائع
المؤتمر الدولي السنوي السادس والعشرون للتعلم الآلي 26-553 (560).
الشبكي: / / doi.org/ 10.1145 / 1553374.1553446

[29] كومار ، موهري ، وتالوالكار ، "طرق أخذ العينات لطريقة نيستروم" مجلة بحوث التعلم الآلي 13 ، 981-1006 (2012).
الشبكي: / / doi.org/ 10.5555 / 2188385.2343678

[30] لي ، كووك ، ولو ، "جعل تقريب نيستروم واسع النطاق ممكنًا" وقائع المؤتمر الدولي السابع والعشرين حول المؤتمر الدولي حول التعلم الآلي 27-631 (638).
الشبكي: / / doi.org/ 10.5555 / 3104322.3104403

[31] Lloyd "Universal Quantum Simulators" Science 273، 1073-1078 (1996).
الشبكي: / / doi.org/ 10.1126 / science.273.5278.1073

[32] لويد ، محسني ، وريبنتروست ، "تحليل المكون الرئيسي الكمومي" فيزياء الطبيعة 10 ، 631 (2014).
الشبكي: / / doi.org/ 10.1038 / nphys3029

[33] Lowand Chuang "محاكاة هاميلتونية بواسطة التضخيم الطيفي الموحد" arXiv preprint arXiv: 1707.05391 (2017).

[34] Mackey ، Talwalkar ، و Jordan ، "Divide-and-Conquer Matrixization" وقائع المؤتمر الدولي الرابع والعشرين حول أنظمة معالجة المعلومات العصبية 24-1134 (1142).
الشبكي: / / doi.org/ 10.5555 / 2986459.2986586

[35] ماهوني "خوارزميات عشوائية للمصفوفات والبيانات" Foundations and Trends® 3 ، 123-224 (2011).
الشبكي: / / doi.org/ 10.1561 / 2200000035

[36] Mathias "تقريب الوظائف ذات القيمة المصفوفة" مجلة SIAM على تحليل المصفوفة والتطبيقات 14 ، 1061-1063 (1993).
الشبكي: / / doi.org/ 10.1137 / 0614070

[37] Al-Mohyand Higham "خوارزمية جديدة للمقياس والتربيع لمصفوفة الأسي" مجلة SIAM حول تحليل وتطبيقات المصفوفة 31 ، 970-989 (2009).
الشبكي: / / doi.org/ 10.1137 / 09074721X

[38] المحي الدين هيغام "حساب عمل المصفوفة الأسية ، مع تطبيق على التكامل الأسي" مجلة SIAM عن الحوسبة العلمية 33 ، 488-511 (2011).
الشبكي: / / doi.org/ 10.1137 / 100788860

[39] ناكاموتو "عدم مساواة معياري لمشغلي الهرميتين" الأمريكية الرياضية الشهرية 110 ، 238 (2003).
الشبكي: / / doi.org/ 10.1080 / 00029890.2003.11919961

[40] نيستروم "dieber die praktische Auflösung von Integralgleichungen mit Anwendungen auf Randwertaufgaben" Acta Mathematica 54، 185-204 (1930).
الشبكي: / / doi.org/ 10.1007 / BF02547521

[41] Orecchia و Sachdeva و Vishnoi ، "تقريب الأسي وطريقة Lanczos وخوارزمية طيفية زمنية للفاصل المتوازن" للندوة السنوية الرابعة والأربعين لـ ACM حول نظرية الحوسبة 1141-1160 (2012).
الشبكي: / / doi.org/ 10.1145 / 2213977.2214080

[42] أورس "مقدمة عملية لشبكات الموتر: حالات منتج ماتريكس وحالات الزوج المتشابكة المتوقعة" حوليات الفيزياء 349 ، 117-158 (2014).
الشبكي: / / doi.org/ 10.1016 / j.aop.2014.06.013

[43] ريبنتروست ، محسني ، ولويد ، "آلة ناقلات الدعم الكمومي لتصنيف البيانات الضخمة" رسائل المراجعة البدنية 113 ، 130503 (2014).
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.113.130503

[44] Rebentrost و Schuld و Wossnig و Petruccione و Lloyd ، "منحدر التدرج الكمومي وطريقة نيوتن لتحسين كثير الحدود المقيدة" New Journal of Physics 21 ، 073023 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab2a9e

[45] رودي وكاموريانو وروزاسكو ، "الأقل هو أكثر: Nyström Computational Regulation" وقائع المؤتمر الدولي الثامن والعشرين حول أنظمة معالجة المعلومات العصبية - المجلد 28 1-1657 (1665).
الشبكي: / / doi.org/ 10.5555 / 2969239.2969424

[46] رودي وكاموريانو وروزاسكو ، "الأقل هو أكثر: Nyström Computational Regulation" arXiv preprint arXiv: 1507.04717 (2015).

[47] Schuld ، Sinayskiy ، و Petruccione ، "التنبؤ من خلال الانحدار الخطي على الكمبيوتر الكمومي" المراجعة الفيزيائية A 94 ، 022342 (2016).
الشبكي: / / doi.org/ 10.1103 / PhysRevA.94.022342

[48] شوارز ونيست "محاكاة الدوائر الكمية مع توزيعات خرج متفرقة" arXiv preprint arXiv: 1310.6749 (2013).

[49] Spielman and Teng "خوارزميات الوقت الخطية تقريبًا لتقسيم الرسم البياني ، وتوزيع الرسم البياني ، وحل الأنظمة الخطية" وقائع الندوة السنوية السادسة والثلاثين لـ ACM حول نظرية الحوسبة 81-90 (2004).
الشبكي: / / doi.org/ 10.1145 / 1007352.1007372

[50] Spielman and Teng "Spectral sparsification of والرسوم البيانية" مجلة SIAM على الحوسبة 40 ، 981-1025 (2011).
الشبكي: / / doi.org/ 10.1137 / 08074489X

[51] سوزوكي "معادلة تروتر المعممة وتقريبها المنهجي للعوامل الأسية والمشتقات الداخلية مع تطبيقات لمشاكل العديد من الجسم" الاتصالات في الفيزياء الرياضية 51 ، 183-190 (1976).
الشبكي: / / doi.org/ 10.1007 / BF01609348

[52] تالوالكار ، كومار ، ورولي ، "التعلم المتعدد على نطاق واسع" مؤتمر IEEE حول رؤية الكمبيوتر والتعرف على الأنماط 1-8 (2008).
الشبكي: / / doi.org/ 10.1109 / CVPR.2008.4587670

[53] تانغ "خوارزمية كلاسيكية مستوحاة من الكم لأنظمة التوصية" وقائع الندوة السنوية الحادية والخمسين ACM SIGACT حول نظرية الحوسبة 51-217 (228).
الشبكي: / / doi.org/ 10.1145 / 3313276.3316310

[54] تم العثور على تروب "حدود ذيل سهلة الاستخدام لمجموع المصفوفات العشوائية". احسب. الرياضيات. 12 ، 389-434 (2012).
الشبكي: / / doi.org/ 10.1007 / s10208-011-9099 زي

[55] Trotter "على منتج شبه مجموعات من المشغلين" وقائع الجمعية الرياضية الأمريكية 10 ، 545-551 (1959).
https:/​/​doi.org/​10.1090/​S0002-9939-1959-0108732-6

[56] Van Den Nest "المحاكاة الكلاسيكية للحساب الكمي ، Gottesman" معلومات الكم والحساب 10 ، 258-271 (2010).
الشبكي: / / doi.org/ 10.5555 / 2011350.2011356

[57] Verstraete و Garcia-Ripoll و Cirac ، "مشغلي كثافة منتجات Matrix: محاكاة أنظمة درجة الحرارة المحدودة والتبديد" رسائل المراجعة الفيزيائية 93 ، 207204 (2004).
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.93.207204

[58] Verstraete ، Murg ، و Cirac ، "حالات منتج Matrix ، حالات الزوج المتشابكة المتوقعة ، وطرق مجموعة إعادة التباين المتغيرة لأنظمة دوران الكم". التقدم في الفيزياء 57 ، 143-224 (2008).
الشبكي: / / doi.org/ 10.1063 / 1.5026985

[59] فيدال "المحاكاة الفعالة لأنظمة أجسام الجسم الكمية أحادية البعد" Phys. القس ليت. 93 ، 040502 (2004).
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.93.040502

[60] ويليامز وسيجر "استخدام طريقة نيستروم لتسريع أجهزة نواة" التقدم في أنظمة معالجة المعلومات العصبية 13 682-688 (2001).
الشبكي: / / doi.org/ 10.5555 / 3008751.3008847

[61] ويليامز ، راسموسن ، شوايغوفر ، وتريسب ، تقرير "ملاحظات على طريقة نيستروم لتنبؤ عملية غاوس" (2002).

[62] Woodruff "رسم كأداة للجبر الخطي العددي" أسس وتريندز 10 ، 1-157 (2014).
الشبكي: / / doi.org/ 10.1561 / 0400000060

[63] Zhang و Kwok "طريقة Nyström المجمعة للتعلم متعدد الأبعاد على نطاق واسع وتقليل الأبعاد" معاملات IEEE على الشبكات العصبية 21 ، 1576-1587 (2010).
الشبكي: / / doi.org/ 10.1109 / TNN.2010.2064786

[64] Zhang ، Tsang ، و Kwok ، "إجراءات Nyström المحسنة لتقدير منخفض الرتبة وتحليل الأخطاء" وقائع المؤتمر الدولي الخامس والعشرين حول التعلم الآلي 25-1232 (1239).
الشبكي: / / doi.org/ 10.1145 / 1390156.1390311

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

[1] Ewin Tang ، "خوارزميات كلاسيكية مستوحاة من الكم لتحليل المكونات الرئيسية والتكتلات الخاضعة للإشراف" ، أرخايف: 1811.00414.

[2] خوان أسيبرون ، "طريقة مونت كارلو لحساب عمل مصفوفة أسية على ناقل" ، أرخايف: 1904.12759.

[3] Nai-Hui Chia و András Gilyén و Tongyang Li و Han-Hsuan Lin و Ewin Tang و Chunhao Wang ، "إطار حسابي مصفوفة رتبية منخفضة الخط يعتمد على أخذ العينات من أجل تكثيف تعلم الآلة الكمومية" ، أرخايف: 1910.06151.

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

لا يمكن أن تجلب استشهد تبادل البيانات أثناء آخر محاولة 2020-02-20 15:40:34: لا يمكن جلب البيانات المستشهد بها من 10.22331 / q-2020-02-20-234 من Crossref. هذا أمر طبيعي إذا تم تسجيل DOI مؤخرًا.

المصدر: https://quantum-journal.org/papers/q-2020-02-20-234/

بقعة_صورة

أحدث المعلومات الاستخباراتية

بقعة_صورة

الدردشة معنا

أهلاً! كيف يمكنني مساعدك؟