حدود لتقريب Max $ k $ XOR باستخدام الخوارزميات الكمومية والمحلية الكلاسيكية

أعاد نشره أفلاطون

المتابعون: 0

كونال مروحة^1,2,3,4 و ستيوارت هادفيلد^1,2

¹مختبر الذكاء الاصطناعي الكمومي (QuAIL) ، مركز أبحاث ناسا أميس ، موفيت فيلد ، كاليفورنيا
²معهد أبحاث USRA لعلوم الكمبيوتر المتقدمة (RIACS) ، ماونتن فيو ، كاليفورنيا
³مركز بيركلي للمعلومات والحساب الكمي ، جامعة كاليفورنيا ، بيركلي ، كاليفورنيا
⁴قسم علوم الكمبيوتر ، جامعة شيكاغو ، شيكاغو ، إلينوي

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

ملخص

نحن نأخذ في الاعتبار قوة الخوارزميات المحلية لحل Max $ k $ XOR تقريبًا ، وهو تعميم لمشكلتين لرضا القيد تمت دراستهما سابقًا باستخدام الخوارزميات الكلاسيكية والكمية (MaxCut و Max E3LIN2). في Max $ k $ XOR ، يكون كل قيد هو XOR لمتغيرات $ k $ بالضبط وبت تماثل. في الحالات التي تحتوي على علامات عشوائية (تماثلات) أو بدون عبارات متداخلة وعبارات $ D + 1 $ لكل متغير ، نحسب الجزء المُرضي المتوقع من عمق 1 QAOA من Farhi et al [arXiv: 1411.4028] ونقارن مع تعميم لـ خوارزمية العتبة المحلية من Hirvonen et al [arXiv: 1402.2543]. والجدير بالذكر أن الخوارزمية الكمومية تتفوق على خوارزمية العتبة لـ $ k $$ gt $$ 4 $.

من ناحية أخرى ، نسلط الضوء على الصعوبات المحتملة التي تواجهها هيئة ضمان وضمان الجودة لتحقيق ميزة حسابية كمومية بشأن هذه المشكلة. نحسب أولاً حدًا علويًا ضيقًا على الحد الأقصى للكسر المُرضي لجميع مثيلات Max $ k $ XOR العادية الكبيرة تقريبًا عن طريق حساب كثافة طاقة الحالة الأرضية $ P (k) $ لحقل متوسط $ k $ - spin glass [ arXiv: 1606.02365]. ينمو الحد الأعلى بمقدار $ k $ أسرع بكثير من أداء كل من الخوارزميات المحلية. نحدد أيضًا نتيجة عائق جديدة للدوائر الكمومية منخفضة العمق (بما في ذلك QAOA) عندما $ k = 3 $ ، مع تعميم نتيجة Bravyi et al [arXiv: 1910.08980] عندما $ k = 2 $. نعتقد أن هناك عائقًا مشابهًا لكل $ k $.

الصورة المميزة: مقارنة الكسر المرضي (الأداء) من خوارزمية العتبة وعمق 1 QAOA لـ Max kXOR على نطاق واسع $ D $ (و $ D gg k $). ينمو الثابت $ C_k $ لـ QAOA بسرعة أكبر باستخدام $ k $ مقارنة بخوارزمية العتبة. على الرغم من أن خوارزمية العتبة تتفوق على عمق 1 QAOA لـ $ k في {2,3,4،XNUMX،XNUMX} $ ، إلا أن خوارزمية QAOA هي أفضل خوارزمية.

[المحتوى جزءا لا يتجزأ]

► بيانات BibTeX

article {Marwaha2022boundsapproximating ، دوى = {10.22331 / q-2022-07-07-757} ، url = {https://doi.org/10.22331/q-2022-07-07-757} ، العنوان = {حدود تقريب {M} ax {$ k $} {XOR} بالخوارزميات المحلية الكمومية والكلاسيكية} ، المؤلف = {مروحة ، كونال وهادفيلد ، ستيوارت} ، مجلة = {{الكم}} ، رقم الإصدار = {2521-327X} ، الناشر = {{Verein zur F {“{o}} rderung des Open Access Publizierens in den Quantenwissenschaften}} ، الحجم = {6} ، الصفحات = {757} ، الشهر = يوليو ، السنة = {2022} }

ferences المراجع

[1] A. Auffinger و W.-K. تشين. على خصائص التدابير الباريسية. arXiv: 1303.3573 ، دوى: 10.1007 / s00440-014-0563-y.
الشبكي: / / doi.org/ 10.1007 / s00440-014-0563 ذ
أرخايف: 1303.3573

[2] A. Auffinger و W.-K. تشين. تحتوي صيغة Parisi على أداة تصغير فريدة. الاتصالات في الفيزياء الرياضية ، 335 (3): 1429-1444 ، نوفمبر 2014. arXiv: 1402.5132 ، دوى: 10.1007 / s00220-014-2254-z.
الشبكي: / / doi.org/ 10.1007 / s00220-014-2254 زي
أرخايف: 1402.5132

[3] A. Auffinger و W.-K. تشين. صيغة باريسي لطاقة الحالة الأرضية في نموذج p-spin المختلط. arXiv: 1606.05335 ، دوى: 10.1214 / 16-aop1173.
https: / / doi.org/10.1214 / 16-aop1173
أرخايف: 1606.05335

[4] عبد اللطيف علوي و أ. مونتاناري. عتبات الخوارزمية في متوسط زجاج الدوران. arXiv: 2009.11481.
أرخايف: 2009.11481

[5] عبد اللطيف العلوي ، أ. مونتاناري ، وم. تحسين نظارات الدوران ذات المجال المتوسط. arXiv: 2001.00904 ، دوى: 10.1214 / 21-aop1519.
https: / / doi.org/10.1214 / 21-aop1519
أرخايف: 2001.00904

[6] S. Bravyi و A. Kliesch و R. Koenig و E. Tang. العقبات التي تحول دون إعداد الحالة والتحسين المتغير من حماية التماثل. الإصدار التمهيدي لـ arXiv ، 2019. arXiv: 1910.08980.
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.125.260505
أرخايف: 1910.08980

[7] براك براك وخليل مروحة. الخوارزميات الكلاسيكية والقيود الكمومية لأقصى قطع على الرسوم البيانية عالية المقاس. arXiv: 2106.05900 ، دوى: 10.4230 / LIPIcs.ITCS.2022.14.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2022.14
أرخايف: 2106.05900

[8] باراك ، أ.مويترا ، ر. أودونيل ، وآخرون. التغلب على التخصيص العشوائي في مسائل الرضا القيد للدرجة المقيدة. arXiv: 1505.03424.
أرخايف: 1505.03424

[9] دبليو- ك. تشن ، د. جامارنيك ، د. بانشينكو ، و محمد رحمن. Suboptimality للخوارزميات المحلية لفئة من مشاكل الحد الأقصى. سجلات الاحتمالات ، 47 (3) ، مايو 2019. arXiv: 1707.05386 ، دوى: 10.1214 / 18-aop1291.
https: / / doi.org/10.1214 / 18-aop1291
أرخايف: 1707.05386

[10] C.-N. Chou و PJ Love و JS Sandhu و J. Shi. حدود خوارزميات الكم المحلية على Random Max-k-XOR وما بعدها. arXiv: 2108.06049.
أرخايف: 2108.06049

[11] A. Crisanti و T. Rizzo. تحليل حل كسر التناظر المتماثل $ infty لنموذج Sherrington-Kirkpatrick. مراجعة فيزيائية E، 65 (4)، أبريل 2002. arXiv: cond-mat / 0111037، doi: 10.1103 / physreve.65.046137.
https: / / doi.org/ 10.1103 / physreve.65.046137
arXiv: كوند مات / 0111037

[12] ب. دريدا. نموذج الطاقة العشوائية: نموذج قابل للحل تمامًا للأنظمة المضطربة. فيز. القس ب ، 24: 2613-2626 ، سبتمبر 1981. دوى: 10.1103 / PhysRevB.24.2613.
الشبكي: / / doi.org/ 10.1103 / PhysRevB.24.2613

[13] أ. ديمبو ، أ. مونتاناري ، وسين. قطع متطرفة من الرسوم البيانية العشوائية المتفرقة. سجلات الاحتمالات ، 45 (2): 1190-1217 ، 2017. arXiv: 1503.03923 ، دوى: 10.1214 / 15-aop1084.
https: / / doi.org/10.1214 / 15-aop1084
أرخايف: 1503.03923

[14] إلدار و أ. سكان هاميلتونيون المحليون الذين يصعب تقريب حالاتهم الأرضية. ندوة 2017 IEEE 58th السنوية حول أسس علوم الكمبيوتر (FOCS) ، أكتوبر 2017. arXiv: 1510.02082 ، دوى: 10.1109 / focs.2017.46.
الشبكي: / / doi.org/ 10.1109 / focs.2017.46
أرخايف: 1510.02082

[15] فارحي ، ج. غولدستون ، وس. جوتمان. خوارزمية التحسين الكمي التقريبي. arXiv: 1411.4028.
أرخايف: 1411.4028

[16] فارحي ، ج. غولدستون ، وس. جوتمان. خوارزمية التحسين الكمي التقريبية المطبقة على مشكلة قيود الحدوث المحدود. arXiv: 1412.6062.
أرخايف: 1412.6062

[17] فارحي ود. جامارنيك وس. جوتمان. تحتاج خوارزمية التحسين الكمي التقريبية إلى رؤية الرسم البياني بأكمله: حالة نموذجية. arXiv: 2004.09002.
أرخايف: 2004.09002

[18] فريدمان. دليل على تخمين القيمة الذاتية الثاني لألون والمشكلات ذات الصلة. arXiv: cs / 0405020 ، دوى: 10.1090 / مذكرة / 0910.
https: / / doi.org/10.1090 / memo / 0910
arXiv: CS / 0405020

[19] S. هادفيلد. خوارزميات الكم للحوسبة العلمية والتحسين التقريبي. جامعة كولومبيا ، 2018 ، arXiv: 1805.03265.
أرخايف: 1805.03265

[20] J. Håstad. بعض النتائج المثلى لعدم التقريب. مجلة ACM (JACM) ، 48 (4): 798-859 ، 2001. doi: 10.1145 / 258533.258536 ، URL http: / / www.cs.umd.edu/ gasarch / BLOGPAPERS / max3satl. بي دي إف.
الشبكي: / / doi.org/ 10.1145 / 258533.258536
http: / / www.cs.umd.edu/ ~ gasarch / BLOGPAPERS / max3satl.pdf

[21] MB هاستينغز. حالات الطاقة المنخفضة التافهة للانتقال إلى سكان هاميلتون ، وتخمين PCP الكمي. معلومات الكم والحساب ، 13 ، 2013. arXiv: 1201.3387 ، دوى: 10.26421 / qic13.5-6-3.
https: / / doi.org/ 10.26421 / qic13.5-6-3
أرخايف: 1201.3387

[22] MB هاستينغز. خوارزميات تقريب العمق التقليدية والكمية. arXiv: 1905.07047 ، دوى: 10.26421 / qic19.13-14-3.
https: / / doi.org/ 10.26421 / qic19.13-14-3
أرخايف: 1905.07047

[23] WW Ho و TH Hsieh. محاكاة متغيرة فعالة للحالات الكمية غير التافهة. arXiv: 1803.00026 ، دوى: 10.21468 / scipostphys.6.3.029.
https: / / doi.org/ 10.21468 / scipostphys.6.3.029
أرخايف: 1803.00026

[24] ج. هيرفونين ، ج. ريبيكي ، إس شميد ، وجيه. سوميلا. تخفيضات كبيرة باستخدام الخوارزميات المحلية على الرسوم البيانية الخالية من المثلثات. المجلة الإلكترونية للجمعيات ، الصفحات P4–21 ، 2017. arXiv: 1402.2543 ، دوى: 10.37236 / 6862.
الشبكي: / / doi.org/ 10.37236 / 6862
أرخايف: 1402.2543

[25] CY-Y. لين و Y. تشو. أداء QAOA في الحالات النموذجية لمشكلات الرضا عن القيود مع الدرجة المقيدة. arXiv: 1601.01744.
أرخايف: 1601.01744

[26] ك.مروة. تتفوق خوارزمية MAX-CUT الكلاسيكية المحلية في الأداء على $ p = 2 $ QAOA على الرسوم البيانية العادية عالية الجودة. الكم ، 5: 437 ، أبريل 2021. arXiv: 2101.05513 ، دوى: 10.22331 / q-2021-04-20-437.
https://doi.org/10.22331/q-2021-04-20-437
أرخايف: 2101.05513

[27] أ. مونتاناري. تحسين أداء Sherrington – Kirkpatrick Hamiltonian. arXiv: 1812.10897 ، دوى: 10.1109 / focs.2019.00087.
الشبكي: / / doi.org/ 10.1109 / focs.2019.00087
أرخايف: 1812.10897

[28] P. Obszarski و A. Jastrzȩbski. تلوين الحواف لـ 3 رسومات تخطيطية موحدة. الرياضيات التطبيقية المتقطعة ، 217: 48-52 ، 2017 ، التحسين التوافقي: النظرية والحساب والتطبيقات. دوى: 10.1016 / j.dam.2016.06.009.
https: / / doi.org/ 10.1016 / j.dam.2016.06.009

[29] د. بانتشينكو. مقدمة عن نموذج SK. arXiv: 1412.0170 ، دوى: 10.4310 / cdm.2014.v2014.n1.a4.
https://doi.org/10.4310/cdm.2014.v2014.n1.a4
أرخايف: 1412.0170

[30] د. بانتشينكو. على نموذج $ k $ -sat مع عدد كبير من الجمل. arXiv: 1608.06256 ، دوى: 10.1002 / rsa.20748.
الشبكي: / / doi.org/ 10.1002 / rsa.20748
أرخايف: 1608.06256

[31] G. باريزي. سلسلة من الحلول التقريبية لنموذج SK لزجاج الدوران. مجلة الفيزياء أ: الرياضيات والعامة ، 13 (4): L115-L121 ، أبريل 1980. دوى: 10.1088 / 0305-4470 / 13/4/009.
https://doi.org/10.1088/0305-4470/13/4/009

[32] S. Sen. التحسين على الرسوم البيانية العشوائية المتناثرة والنظارات الدوارة. arXiv: 1606.02365 ، دوى: 10.1002 / rsa.20774.
الشبكي: / / doi.org/ 10.1002 / rsa.20774
أرخايف: 1606.02365

[33] R. Shaydulin ، S. Hadfield ، T. Hogg ، و I. Safro. التناظرات الكلاسيكية وخوارزمية التحسين الكمي التقريبية. معالجة المعلومات الكمية ، 20 (11): 1–28 ، 2021. arXiv: 2012.04713 ، دوى: 10.1007 / s11128-021-03298-4.
https://doi.org/10.1007/s11128-021-03298-4
أرخايف: 2012.04713

[34] م تالاغراند. صيغة باريزي. حوليات الرياضيات ، 163: 221-263 ، 2006. doi: 10.4007 / Annals.2006.163.221 ، URL https: / / annals.math.princeton.edu/ wp-content / uploads / annals-v163 -n1-p04.pdf.
https: / / doi.org/10.4007 / annals.2006.163.221
https: / / annals.math.princeton.edu/ wp-content / uploads / annals-v163-n1-p04.pdf

[35] Z. Wang و S. Hadfield و Z. Jiang و EG Rieffel. خوارزمية التحسين الكمي التقريبي لـ maxcut: عرض فرميوني. فيز. القس أ ، 97: 022304 ، فبراير 2018. arXiv: 1706.02998 ، دوى: 10.1103 / PhysRevA.97.022304.
الشبكي: / / doi.org/ 10.1103 / PhysRevA.97.022304
أرخايف: 1706.02998

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

[1] جواو باسو ، إدوارد فارهي ، كونال مروها ، بنجامين فيلالونجا ، وليو زو ، "خوارزمية التحسين الكمي التقريبي في العمق العالي لـ MaxCut على الرسوم البيانية المنتظمة الكبيرة الحجم ونموذج شيرينغتون-كيركباتريك" ، أرخايف: 2110.14206.

[2] نيكولاس بي دي ساوايا ، وألبرت شميتز ، وستيوارت هادفيلد ، "ترميز المقايضات ومجموعات أدوات التصميم في الخوارزميات الكمومية لتحسين منفصل: التلوين ، والتوجيه ، والجدولة ، ومشاكل أخرى" ، أرخايف: 2203.14432.

[3] ياش ج.باتيل ، سفيان جربي ، توماس باك ، وفيدران دونجكو ، "تعزيز التعلم بمساعدة QAOA" ، أرخايف: 2207.06294.

الاستشهادات المذكورة أعلاه من إعلانات ساو / ناسا (تم آخر تحديث بنجاح 2022-07-26 13:36:03). قد تكون القائمة غير كاملة نظرًا لأن جميع الناشرين لا يقدمون بيانات اقتباس مناسبة وكاملة.

On خدمة Crossref's cited-by service لم يتم العثور على بيانات حول الاستشهاد بالأعمال (المحاولة الأخيرة 2022-07-26 13:36:00).

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