Minimum Bisection Problem: Machine Learning-Based Penalty Parameter Tuning for Optimization on Quantum Annealers

ملخص تقني: ضبط معامل العقوبة القائم على تعلم الآلة لتقسيم الحد الأدنى (Minimum Bisection) على الملدنات الكمومية

تعريف المشكلة
تعد مشكلة التقسيم الأدنى (Minimum Bisection Problem - MBP) مسألة تقسيم رسوم بيانية أساسية من نوع NP-hard، تتطلب تقسيم عقد الرسم البياني إلى مجموعتين متساويتي الحجم مع تقليل عدد الحواف التي تربط بينهما إلى أدنى حد. وبينما تبرز تطبيقات مشكلة MBP في الحوسبة المتوازية وتصميم الشبكات، فإن حلها عبر التلدين الكمومي يتطلب صياغتها كنموذج تحسين ثنائي تربيعي غير مقيد (QUBO). ويتمثل التحدي الحرج في هذه الصياغة في اختيار معامل العقوبة ($\lambda$)، الذي يفرض قيد التوازن (تساوي أحجام المجموعات). فإذا كان $\lambda$ صغيراً جداً، سيعيد الحلّال حلولاً غير صالحة تنتهك قيد التوازن؛ وإذا كان كبيراً جداً، فسوف يهيمن حد العقوبة على دالة الهدف، مما يحجب هدف تقليل القطع (cut-minimization). وتعتمد الطرق الحالية على الضبط اليدوي أو الاستدلالات الثابتة، والتي غالباً ما تكون مرتبطة بنوع محدد من المسائل وغير موثوقة عبر هياكل الرسوم البيانية المتغيرة.

المنهجية
يقترح المؤلفون إطار عمل يعتمد على البيانات لأتمتة اختيار $\lambda$ خصيصاً لمشكلة MBP على الملدنات الكمومية. يمر هذا النهج عبر أربع مراحل:

1. الحدود النظرية والتقدير الأولي:
   استنتج المؤلفون تقديراً أولياً يعتمد على الرسم البياني ($\lambda_{est}$) من خلال تحليل مشهد الطاقة (energy landscape). وقد وضعوا حداً أدنى نظرياً ($\lambda \ge 1$) وحداً أقصى عملياً بناءً على أقصى درجة للعقدة وحجم الرسم البياني ($\lambda \le \min(\Delta(G), n/2 - 1)$). تم تعيين التقدير الأولي ليكون منتصف هذه الفترة. تعتمد هذه الطريقة حصرياً على خصائص الرسم البياني القابلة للقياس ($n$ و $\Delta(G)$) بدلاً من المعاملات المولدة للرسم البياني، مما يضمن قابليتها للتطبيق على الرسوم البيانية المدخلة العشوائية.

2. القياس التجريبي والمعايرة:
   كشفت التجارب الأولية أن المنتصف النظري غالباً ما يتطلب مزيداً من القياس، لا سيما للرسوم البيانية الأكبر حجماً. أجرى المؤلفون مرحلة معايرة باستخدام 607 من رسوم إردوش-ريني البيانية ($G(n, p)$) بأحجام تصل إلى 4000 عقدة. واختبروا مضاعفات مختلفة ($\lambda_{mult}$) طُبقت على $\lambda_{est}$ لتحديد نطاقات القيم التي أسفرت عن تقسيمات متوازنة صالحة مع أقل قيم قطع باستخدام الحل الهجين الكمي-الكلاسيكي (QA HS) من D-Wave.

3. تنبؤ تعلم الآلة:
   لإلغاء الحاجة إلى البحث اليدوي المكلف عبر المضاعفات المرشحة، درب المؤلفون نموذجين من نماذج "منظم تعزيز التدرج" (Gradient Boosting Regressor - GBR).

• المدخلات: تأخذ النماذج ثلاث ميزات: عدد العقد ($n$)، وكثافة الرسم البياني المحققة ($\rho$)، والتقدير الأولي للعقوبة ($\lambda_{est}$).
• المخرجات: يتنبأ أحد النماذج بالحد الأدنى ($\lambda_{min}$) والآخر يتنبأ بالحد الأقصى ($\lambda_{max}$) لنطاق المضاعف الفعال.
• الحساب النهائي: يتم حساب معامل العقوبة النهائي كالتالي: $\lambda = \lambda_{est} \times \frac{\lambda_{min} + \lambda_{max}}{2}$.

4. التقييم التجريبي:
   تم تقييم النماذج المدربة على 126 من رسوم إردوش-ريني البيانية المستقلة (حتى 4000 عقدة) ومقارنتها بالنماذج الكلاسيكية المرجعية: Metis (التقسيم متعدد المستويات) وKernighan–Lin (التحسين المحلي). كما أُجريت تجارب مباشرة على وحدة المعالجة الكمومية (QPU) على رسوم بيانية أصغر ($n \le 100$) لتقييم الأداء الخاص بالعتاد.

المساهمات الرئيسية

• إطار عمل خاص بـ MBP: يقدم البحث إطار عمل يجمع بين تقدير تحليلي يعتمد على الرسم البياني وتعلم الآلة للتنبؤ بنطاق المضاعف الفعال، متجاوزاً بذلك الضبط العام للعقوبة.
• مجموعة بيانات المعايرة: أنتج المؤلفون واستخدموا مجموعة بيانات مكونة من 607 من رسوم إردوش-ريني البيانية لتدريب النماذج، وقيموا النتائج على 126 حالة غير مرئية، تغطي نطاقاً واسعاً من الأحجام (حتى 4000 عقدة) والكثافات.
• التحقق من الأداء: أظهرت الدراسة أن اختيار العقوبة المتعلم يُمكّن الحل الهجين من إيجاد تقسيمات متوازنة صالحة لـ 100% من حالات التقييم، وهو تحسن ملحوظ عن التقديرات الاستدلالية الأولية.

النتائج

• الصلاحية: في ظل الإعداد التجريبي المعتمد، سمحت معاملات العقوبة المتوقعة من نموذج GBR للمحلل الهجين من D-Wave بإرجاع تقسيمات متوازنة لجميع حالات التقييم الـ 126.
• جودة الحل: حقق الحل الهجين باستخدام العقوبات المتوقعة قيم قطع أقل (حواف قطع أقل) من Metis في 100% من الحالات التي تم تقييمها. وأكد التحليل الإحصائي باستخدام اختبار ويلكوكسون (Wilcoxon signed-rank test) أن هذه الاختلافات كانت جوهرية ($p < 0.001$).
• أداء QPU المباشر: بالنسبة للرسوم البيانية الصغيرة ($n \le 100$)، تفوقت QPU على Metis في غالبية الحالات عندما كانت $n \ge 80$، وإن كان الأداء مختلطاً للرسوم الأصغر، ويرجع ذلك على الأرجح إلى تدريب النموذج أساساً على حالات أكبر حجماً.
• دقة النموذج: حقق نموذج GBR للحد الأقصى ($\lambda_{max}$) درجة $R^2$ عالية بلغت 0.9028. أما نموذج الحد الأدنى ($\lambda_{min}$) فقد سجل $R^2$ أقل (0.4489) بسبب انخفاض التباين في القيم المستهدفة، لكنه حافظ على خطأ مطلق منخفض (MAE 0.0124).

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

تضع هذه الدراسة نفسها كخطوة نحو جعل صياغات QUBO أكثر قوة للعتاد الكمومي. ويشير المؤلفون صراحةً إلى أن نتائجهم خاصة بتوزيع رسوم إردوش-ريني وتكوين الحل الهجين من D-Wave المستخدم. وهم لا يدعون التفوق العالمي على جميع الخوارزميات الكلاسيكية (على سبيل المثال، يقرون بأن Metis أسرع بكثير من حيث وقت التشغيل الخام)، لكنهم يجادلون بأن الضبط المقترح يجعل النهج الكمومي منافساً في جودة الحل مع ضمان الصلاحية. وقد تم تحديد العمل المستقبلي في توسيع الإطار ليشمل عائلات رسوم بيانية أخرى، ومعايير واقعية، ومشكلات التقسيم $k$.