كتب الذكاء الاصطناعيمشاريع الذكاء الاصطناعيمقالات الذكاء الاصطناعيمعجم الذكاء الاصطناعياسئلة واجوبة في الذكاء الاصطناعيأكاديمية الذكاء الاصطناعي للأطفالأكاديمية الذكاء الاصطناعيمدرسة رياضيات الذكاء الاصطناعيمختبر الذكاء الاصطناعيمختبر الخوارزميات المستوحاة من الطبيعةأطلس نماذج الذكاء الاصطناعيموسوعة تطبيقات الذكاء الاصطناعيمستكشف مجموعات البيانات للذكاء الاصطناعياختبارات الذكاء الاصطناعيالفايب كودينغدليل البرمجة بالذكاء الاصطناعيمولّد مشاريع الذكاء الاصطناعيمرصد الذكاء الاصطناعيدليل أدوات الذكاء الاصطناعي البحث والنشر الأكاديميمكتبة البرومبتات الأكاديميةمستودع الرسائل والأطاريح في الذكاء الاصطناعيحاسبة الترقية العلميةأكاديمية الوكلاء الذكيينمختبر أخلاقيات الذكاء الاصطناعي والعدالةساحة ألعاب الذكاء الاصطناعيعبقري الذكاء الاصطناعيمختبر التنبؤ بالسلاسل الزمنيةمتحف الذكاء الاصطناعيمختبر الرؤية الحاسوبيةموسوعة شبكات التعلم العميق الحديثةمختبر الشبكات العصبية البيانيةمختبر تحليل الصور الطبيةمختبر معالجة اللغة الطبيعيةمختبر الحوسبة الكمّيةخرائط طريق الذكاء الاصطناعيأكاديمية ماتلاب والذكاء الاصطناعيمصمم الشبكات العصبيةأكاديمية الذكاء الاصطناعي بدون برمجةمختبر الذكاء الاصطناعي الكمّي
تجربةمتوسطمفهوم راسخ تعمل في المتصفح

التحسين التوافقي بـ QAOA

QAOA for Max-Cut

حل مسألة القطع الأعظمي على رسوم صغيرة بـ QAOA في المتصفح، مع منظر الطاقة للعمق p=1، ومقارنة بالحل الشامل وبخوارزمية كلاسيكية بسيطة.

خطوات التجربة

  1. اختر الرسم البياني (مربع، خماسي موزون، حلقة…).
  2. اختر العمق p.
  3. نفّذ التحسين واقرأ نسبة التقريب واحتمال القطع الأمثل.
  4. قارن بالحل الشامل وبالبحث المحلي الكلاسيكي.
جارٍ تحميل المحاكي…
ما تتنبأ به النظرية وما تلاحظه

زيادة p تحسّن نسبة التقريب عادةً، لكن الحل الشامل أسرع لهذه الأحجام. لا يوجد اليوم دليل على تفوق QAOA العملي على أفضل الخوارزميات الكلاسيكية.

سيناريوهات جاهزة

كل سيناريو يفتح المحاكي بإعدادات محددة؛ يُحمَّل المحاكي عند فتح السيناريو فقط.

QAOA بعمق 1 على المربع

على المربع (4 عقد، 4 حواف) يبلغ أفضل $\langle C\rangle$ لـ QAOA بعمق 1 القيمة 3 من أصل الحل الأمثل 4، أي نسبة تقريب $0.75$.

الهدف: تشغيل QAOA على أبسط رسم وقراءة نسبة التقريب.

  1. اختر الرسم square و$p=1$.
  2. شاهد منظر $\langle C\rangle(\gamma,\beta)$.
  3. اقرأ القيمة المثلى ونسبة التقريب.
  4. زد العمق إلى $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$.

الهدف: مقارنة العمقين على مسألة موزونة.

  1. اختر weighted5 و$p=1$ ودوّن النسبة.
  2. غيّر إلى $p=2$.
  3. قارن احتمال الحلول المثلى.
  4. اقرأ قيم $\gamma$ و$\beta$ المثلى.
جارٍ تحميل المحاكي…

تتوقع النظرية قطعاً أمثل 12 (الحلان 01101 و10010)، ومتوسطاً عشوائياً 6.5، وأن تكون نسبة $p=2$ أكبر من نسبة $p=1$ أو مساوية لها. في تشغيل المحرك بلغت النسبة نحو $0.81$ عند $p=1$ ونحو $0.89$ عند $p=2$ (تعتمد على المحسّن).

مقارنة مع الطرق الكلاسيكية

يحل المختبر Max-Cut للرسم الموزون بالبحث الشامل والبحث المحلي الجشع والتلدين المحاكى؛ جميعها تجد القطع الأمثل 12 لهذا الرسم الصغير.

الهدف: وضع QAOA في سياقه بمقارنته بخوارزميات كلاسيكية معيارية.

  1. اختر weighted5 ووضع classical.
  2. اقرأ نتيجة البحث الشامل وعدد التقييمات.
  3. قارن بالبحث المحلي والتلدين.
  4. عد إلى وضع qaoa وقارن.
جارٍ تحميل المحاكي…

تتوقع النظرية أن يعطي البحث الشامل 12 بعد تقييم 16 تقسيماً، وأن يجد البحث المحلي والتلدين المحاكى القيمة 12 أيضاً في هذا الرسم (تحقق المحرك من ذلك بالبذور الافتراضية).

صياغة إيزنغ للقطع الأعظمي

بتعيين $s_i=\pm1$ لكل عقدة يصبح القطع $\mathrm{cut}=(W-E)/2$ حيث $E=\sum w_{ij}s_is_j$ طاقة نموذج إيزنغ؛ تعظيم القطع يكافئ تصغير الطاقة.

الهدف: ربط مسألة رسومية بهاملتوني فيزيائي.

  1. اختر square ووضع ising.
  2. اختر تقسيماً واقرأ $E$ والقطع.
  3. تحقق من $\mathrm{cut}=(W-E)/2$.
  4. ابحث عن حالة الطاقة الدنيا.
جارٍ تحميل المحاكي…

تتوقع النظرية للمربع: $E=-4$ والقطع 4 للتقسيمين 0101 و1010، و$E=+4$ والقطع 0 لـ 0000 و1111، و$E=0$ والقطع 2 لتقسيم مثل 0011.

المفاهيم التي تشرحها التجربة

المراجع

  1. Edward Farhi; Jeffrey Goldstone; Sam Gutmann (2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 doi:10.48550/arXiv.1411.4028
  2. 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
  3. Andrew Lucas (2014). Ising formulations of many NP problems. Frontiers in Physics 2:5 doi:10.3389/fphy.2014.00005

نتائج التجارب المحلية ناتجة عن محاكاة كلاسيكية دقيقة لمتجه الحالة تعمل في متصفحك، ونتائج الخادم الحسابي ناتجة عن محاكيات Qiskit وPennyLane؛ ولا يعادل أيٌّ منهما التشغيل على حاسوب كمّي حقيقي. تتضاعف الذاكرة مع كل كيوبت ($2^n$ سعة)، لذلك يُحدّد عدد الكيوبتات بـ 16 في المتصفح.