شعار زيفيرنت

الخوارزميات الكلاسيكية والكمية لتحليل المكوّن الرئيسي

التاريخ:

ماثيو ب. هاستينغز

محطة Q ، Microsoft Research ، سانتا باربرا ، كاليفورنيا 93106-6105 ، الولايات المتحدة الأمريكية
Microsoft Quantum و Microsoft Research، Redmond، WA 98052، USA

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

ملخص

نقدم الخوارزميات الكلاسيكية والكمية المستندة إلى الطرق الطيفية لمشكلة في تحليل المكوّن الأساسي للموتر. تحقق الخوارزمية الكمية تسريعًا $ quartic $ أثناء استخدام مساحة أصغر بشكل أسرع من الخوارزمية الطيفية الأسرع ، وتسريع متعدد الحدود فائق فوق الخوارزميات الكلاسيكية التي تستخدم مساحة متعددة الحدود فقط. ترتبط الخوارزميات الكلاسيكية التي نقدمها ، ولكنها تختلف قليلاً عن تلك التي قدمت مؤخرًا في المرجع. [1]. على وجه الخصوص ، لدينا عتبة مُحسَّنة للاسترداد ، والخوارزميات التي نقدمها تعمل مع كل من التينرزات الفردية والزوجية. هذه النتائج تشير إلى أن مشاكل الاستدلال واسعة النطاق هي تطبيق واعد في المستقبل لأجهزة الكمبيوتر الكم.

► بيانات BibTeX

ferences المراجع

[1] ألكساندر وين ، أحمد العلوي ، وكريستوفر مور. و kikuchi التسلسل الهرمي وتنسور pca. 2019. arXiv: 1904.03858.
أرخايف: 1904.03858

[2] أندريا مونتاناري وإميل ريتشارد. نموذج إحصائي لتنسور pca. في التقدم في نظم معالجة المعلومات العصبية ، الصفحات 2897-2905 ، 2014.

[3] Thibault Lesieur و Leo Miolane و Marc Lelarge و Florent Krzakala و Lenka Zdeborova. التحولات المرحلة الإحصائية والحسابية في تقدير الموتر ارتفعت. في عام 2017 ، ندوة IEEE الدولية لنظرية المعلومات (ISIT). IEEE ، يونيو 2017. دوي: 10.1109 / isit.2017.8006580.
الشبكي: / / doi.org/ 10.1109 / isit.2017.8006580

[4] صموئيل هوبكنز ، جوناثان شي ، وديفيد شتايرر. تحليل عنصر الموتر الرئيسي عبر مجموعة من البراهين. في مؤتمر حول نظرية التعلم ، الصفحات 956–1006 ، 2015.

[5] صموئيل بي هوبكنز ، وتسيلل شرام ، وجوناثان شي ، وديفيد ستورر. خوارزميات طيفية سريعة من براهين مجموع المربعات: تحلل الموتر وناقلات متفرقة مزروعة. في وقائع ندوة ACM SIGACT السنوية الثامنة والأربعين حول نظرية الحوسبة - STOC 48. ACM Press ، 2016. doi: 2016 / 10.1145.
الشبكي: / / doi.org/ 10.1145 / 2897518.2897529

[6] Vijay VSP Bhattiprolu و Mrinalkanti Ghosh و Euiwoong Lee و Venkatesan Guruswami و Madhur Tulsiani. تقريبية مضاعفة لتحسين كثير الحدود على وحدة المجال. CoRR ، abs / 1611.05998 ، 2016. URL: http: / / arxiv.org/ abs / 1611.05998 ، arXiv: 1611.05998.
أرخايف: 1611.05998

[7] فيجاي بهاتبرولو ، ومرينالكانتي غوش ، وفينكاتيسان غوروسوامي ، وإويونج لي ، ومادور تولسياني. فك الارتباط ضعيف ، طيات متعدد الحدود والتحسين التقريبي على الكرة. في عام 2017 ، عقدت الندوة السنوية الثامنة والخمسون لمعهد IEEE حول أسس علوم الحاسوب (FOCS). IEEE ، أكتوبر 58. دوي: 2017 / focs.10.1109.
الشبكي: / / doi.org/ 10.1109 / focs.2017.97

[8] الترددات اللاسلكية ويرنر. انحرافات كبيرة وأنظمة الكم المتوسطة المجال. في احتمال الكم والمواضيع ذات الصلة ، الصفحات 349-381. عالم العلوم ، يوليو 1992. دوي: 10.1142 / 9789814354783_0024.
الشبكي: / / doi.org/ 10.1142 / 9789814354783_0024

[9] كريستينا ف. كراوس ، ماسيج لوينشتاين ، وج. اجناسيو شيراك. حالات الأرض من hamiltonians شعرية fermionic مع التماثل التقليب. Physical Review A، 88 (2)، aug 2013. doi: 10.1103 / physreva.88.022335.
الشبكي: / / doi.org/ 10.1103 / physreva.88.022335

[10] فرناندو جي إس إل برانداو وأرام دبليو هارو. تقريب حالة المنتج إلى الحالات الكمية. الاتصالات في الفيزياء الرياضية ، 342 (1): 47-80 ، يناير 2016. doi: 10.1007 / s00220-016-2575-1.
https:/​/​doi.org/​10.1007/​s00220-016-2575-1

[11] سكوت آرونسون وليجي تشن. الأسس النظرية للتجارب التفوق الكمومية. في مؤتمر التعقيد الحسابي الثاني والثلاثين (CCC 32). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik، 2017. arXiv: 2017.
أرخايف: 1612.05903

[12] مادان لال ميهتا. مصفوفات عشوائية ، المجلد 142. إلسفير ، 2004.

[13] جيمس ديميل ، إيوانا دوميتريو ، وأولغا هولتز. الجبر الخطي السريع مستقر. Numerische Mathematik ، 108 (1): 59–91 ، أكتوبر 2007. doi: 10.1007 / s00211-007-0114-x.
الشبكي: / / doi.org/ 10.1007 / s00211-007-0114-X

[14] غوانغ هاو لو وإسحاق تشوانغ. محاكاة هاميلتون الأمثل من خلال معالجة الإشارات الكمومية. فيز. Rev. Lett. ، 118: 010501 ، 2017. arXiv: 1606.02685v2 ، doi: 10.1103 / PhysRevLett.118.010501.
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.118.010501
أرخايف: 1606.02685v2

[15] غوانغ هاو لو وإسحاق تشوانغ. محاكاة هاميلتون عن طريق qubitization. 2016. arXiv: 1610.06546 https: / / doi.org/ 10.22331 / q-2019-07-12-163.
https:/​/​doi.org/​10.22331/​q-2019-07-12-163
أرخايف: 1610.06546

[16] دومينيك دبليو بيري ، أندرو م. تشايلدز ، ريتشارد كليف ، روبن كوثاري ، ورولاندو سوما. تحسن كبير في الدقة لمحاكاة هاميلتونيس متناثر. الصفحات 283–292 ، 2014. arXiv: 1312.1414 ، doi: 10.1145 / 2591796.2591854.
الشبكي: / / doi.org/ 10.1145 / 2591796.2591854
أرخايف: 1312.1414

[17] دومينيك دبليو بيري ، أندرو م. تشايلدز ، ريتشارد كليف ، روبن كوثاري ، ورولاندو سوما. محاكاة ديناميكيات هاميلتون مع سلسلة تايلور مقطوعة. فيز. Rev. Lett. ، 114: 090502 ، 2015. arXiv: 1412.4687 ، doi: 10.1103 / PhysRevLett.114.090502.
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.114.090502
أرخايف: 1412.4687

[18] DW Berry، AM Childs، and R. Kothari. محاكاة هاميلتون مع الاعتماد الأمثل تقريبا على جميع المعلمات. في عام 2015 ، عقدت الندوة السنوية IEEE 56 حول أسس علوم الحاسب ، الصفحات 792-809 ، أكتوبر 2015. arXiv: 1501.01715 ، doi: 10.1109 / FOCS.2015.54.
الشبكي: / / doi.org/ 10.1109 / FOCS.2015.54
أرخايف: 1501.01715

[19] أليكسي يو كيتيف ، ألكساندر شين ، وميخائيل ن فيالي. الحوسبة الكلاسيكية والكمية ، المجلد 47. الجمعية الرياضية الأمريكية بروفيدنس ، 2002. دوي: 10.1090 / gsm / 047.
الشبكي: / / doi.org/ 10.1090 / جي إس إم / 047

[20] جيل براسارد ، وبيتر هوير ، وميشيل موسكا ، وآلان تاب. تضخيم السعة الكمومية وتقديرها. الرياضيات المعاصرة ، 305: 53–74 ، 2002. doi: 10.1090 / conm / 305.
الشبكي: / / doi.org/ 10.1090 / conm / 305

[21] أنتوني كاربيري وجيمس رايت. عدم المساواة في التوزيع و $ {L ^ q} $ للعديد من الحدود على الهيئات المحدبة في $ {R ^ n} $. رسائل الأبحاث الرياضية ، 8 (3): 233-248 ، 2001. doi: 10.4310 / mrl.2001.v8.n3.a1.
https:/​/​doi.org/​10.4310/​mrl.2001.v8.n3.a1

[22] ديف ويكر ، ماثيو بي هاستينغز ، ناثان ويبي ، براين ك. كلارك ، تشيتان ناياك ، وماثياس ترويير. حل نماذج الإلكترون المرتبطة بقوة على جهاز كمبيوتر الكم. Physical Review A، 92 (6)، December 2015. doi: 10.1103 / physreva.92.062318.
الشبكي: / / doi.org/ 10.1103 / physreva.92.062318

<p class = "break">[23] ماثيو ب. هاستينغز. التقارب في الكم دقيقة التدفق الحد الأدنى. الاتصالات في الفيزياء الرياضية ، 351 (1): 387-418 ، نوفمبر 2016. doi: 10.1007 / s00220-016-2791-8.
https:/​/​doi.org/​10.1007/​s00220-016-2791-8

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

[1] ألكسندر س. وين ، أحمد العلوي ، وكريستوفر مور ، "تسلسل كيكوتشي وتنسور بي سي إيه" ، أرخايف: 1904.03858.

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

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

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

بقعة_صورة

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

بقعة_صورة

الدردشة معنا

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