التحسين التوافقي بـ QAOA
QAOA for Max-Cut
حل مسألة القطع الأعظمي على رسوم صغيرة بـ QAOA في المتصفح، مع منظر الطاقة للعمق p=1، ومقارنة بالحل الشامل وبخوارزمية كلاسيكية بسيطة.
خطوات التجربة
- اختر الرسم البياني (مربع، خماسي موزون، حلقة…).
- اختر العمق p.
- نفّذ التحسين واقرأ نسبة التقريب واحتمال القطع الأمثل.
- قارن بالحل الشامل وبالبحث المحلي الكلاسيكي.
زيادة p تحسّن نسبة التقريب عادةً، لكن الحل الشامل أسرع لهذه الأحجام. لا يوجد اليوم دليل على تفوق QAOA العملي على أفضل الخوارزميات الكلاسيكية.
سيناريوهات جاهزة
كل سيناريو يفتح المحاكي بإعدادات محددة؛ يُحمَّل المحاكي عند فتح السيناريو فقط.
QAOA بعمق 1 على المربع
على المربع (4 عقد، 4 حواف) يبلغ أفضل $\langle C\rangle$ لـ QAOA بعمق 1 القيمة 3 من أصل الحل الأمثل 4، أي نسبة تقريب $0.75$.
الهدف: تشغيل QAOA على أبسط رسم وقراءة نسبة التقريب.
- اختر الرسم square و$p=1$.
- شاهد منظر $\langle C\rangle(\gamma,\beta)$.
- اقرأ القيمة المثلى ونسبة التقريب.
- زد العمق إلى $p=2$.
تتوقع النظرية $\langle C\rangle_{\max}=3$ ونسبة $0.75$ عند $p=1$ (مقابل 2 للتخصيص العشوائي)، واحتمال الحلول المثلى نحو $0.53$؛ وعند $p=2$ تصل النسبة إلى 1 (يُقاس أحد الحلين 0101 أو 1010 دائماً).
QAOA بعمق 2 على رسم موزون
على الرسم الموزون بخمس عقد (القطع الأمثل 12 من وزن كلي 13) يرفع العمق $p=2$ نسبة التقريب مقارنة بـ $p=1$.
الهدف: مقارنة العمقين على مسألة موزونة.
- اختر weighted5 و$p=1$ ودوّن النسبة.
- غيّر إلى $p=2$.
- قارن احتمال الحلول المثلى.
- اقرأ قيم $\gamma$ و$\beta$ المثلى.
تتوقع النظرية قطعاً أمثل 12 (الحلان 01101 و10010)، ومتوسطاً عشوائياً 6.5، وأن تكون نسبة $p=2$ أكبر من نسبة $p=1$ أو مساوية لها. في تشغيل المحرك بلغت النسبة نحو $0.81$ عند $p=1$ ونحو $0.89$ عند $p=2$ (تعتمد على المحسّن).
مقارنة مع الطرق الكلاسيكية
يحل المختبر Max-Cut للرسم الموزون بالبحث الشامل والبحث المحلي الجشع والتلدين المحاكى؛ جميعها تجد القطع الأمثل 12 لهذا الرسم الصغير.
الهدف: وضع QAOA في سياقه بمقارنته بخوارزميات كلاسيكية معيارية.
- اختر weighted5 ووضع classical.
- اقرأ نتيجة البحث الشامل وعدد التقييمات.
- قارن بالبحث المحلي والتلدين.
- عد إلى وضع qaoa وقارن.
تتوقع النظرية أن يعطي البحث الشامل 12 بعد تقييم 16 تقسيماً، وأن يجد البحث المحلي والتلدين المحاكى القيمة 12 أيضاً في هذا الرسم (تحقق المحرك من ذلك بالبذور الافتراضية).
صياغة إيزنغ للقطع الأعظمي
بتعيين $s_i=\pm1$ لكل عقدة يصبح القطع $\mathrm{cut}=(W-E)/2$ حيث $E=\sum w_{ij}s_is_j$ طاقة نموذج إيزنغ؛ تعظيم القطع يكافئ تصغير الطاقة.
الهدف: ربط مسألة رسومية بهاملتوني فيزيائي.
- اختر square ووضع ising.
- اختر تقسيماً واقرأ $E$ والقطع.
- تحقق من $\mathrm{cut}=(W-E)/2$.
- ابحث عن حالة الطاقة الدنيا.
تتوقع النظرية للمربع: $E=-4$ والقطع 4 للتقسيمين 0101 و1010، و$E=+4$ والقطع 0 لـ 0000 و1111، و$E=0$ والقطع 2 لتقسيم مثل 0011.
المفاهيم التي تشرحها التجربة
المراجع
- Edward Farhi; Jeffrey Goldstone; Sam Gutmann (2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 doi:10.48550/arXiv.1411.4028
- Michel X. Goemans; David P. Williamson (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42(6):1115–1145 doi:10.1145/227683.227684
- Andrew Lucas (2014). Ising formulations of many NP problems. Frontiers in Physics 2:5 doi:10.3389/fphy.2014.00005
