Hybrid quantum-classical end-to-end pipeline for solving MILPs: a vehicle routing case study

ملخص تقني: مسار هجين (كمي-كلاسيكي) متكامل لحل مسائل البرمجة الخطية بالأعداد الصحيحة المختلطة (MILPs)

بيان المشكلة
تعد مسائل البرمجة الخطية بالأعداد الصحيحة المختلطة (MILP) مركزية في اتخاذ القرارات عالية التأثير في صناعات مثل اللوجستيات وإدارة سلاسل التوريد، ولكنها تمثل تحدياً حوسبياً نظراً لطبيعتها التوافقية. وبينما تُستخدم تقنيات التفكيك مثل "تفكيك بندرز" (Benders Decomposition - BD) على نطاق واسع لحل مسائل MILP واسعة النطاق عبر فصلها إلى مسألة رئيسية (Master Problem) ومسائل فرعية (Subproblems)، إلا أنها غالباً ما تعاني من بطء التقارب. ويعتمد هذا التقارب بشكل حاسم على اختيار "القطع" (Cuts) أو القيود الأكثر إفادة لإضافتها إلى المسألة الرئيسية. وقد اقترح العمل السابق لـ "باتيراكيس" [1] استخدام التلدين الكمي (Quantum Annealing) لحل خطوة اختيار القطع — والتي صيغت كمسألة "تغطية المجموعات الدنيا" (Minimum Set Cover) — لتسريع هذه العملية. ومع ذلك، يتطلب التلدين الكمي إجراءات "تضمين ثانوي" (Minor-embedding) مكلفة تفرض عبئاً إضافياً كبيراً عند التوسع في الحجم.

المنهجية
تقدم هذه الورقة إطار عمل هجين (كمي-كلاسيكي) متكامل لتحسين العمليات، يوسع نهج تفكيك بندرز المعروف بـ "القطع المتعددة عبر الحلول المتعددة" (MCMS). والابتكار الجوهري هنا هو استبدال خطوة التلدين الكمي بتطبيقات خوارزمية التقريب الكمي الأمثل (QAOA) القائمة على البوابات المنطقية.

يعمل إطار العمل كما يلي:

1. تفكيك بندرز (MCMS): تقوم الخوارزمية بتوليد حلول مرشحة متعددة في كل تكرار، عبر حل مسائل فرعية متعددة بالتوازي لإنتاج مجموعة من القطع المرشحة.
2. اختيار القطع كمسألة QUBO: لمنع المسألة الرئيسية من أن تصبح مكلفة حوسبياً بسبب العدد المفرط من القطوع، يتم اختيار مجموعة فرعية من القطوع الأكثر إفادة. وتُصاغ هذه العملية كمسألة "تغطية المجموعات الدنيا"، والتي يتم بعد ذلك تحويلها إلى نموذج "التحسين التربيعي غير المقيد الثنائي" (QUBO).
3. تكامل خوارزمية QAOA: على عكس نهج التلدين السابق، يستخدم هذا الإطار خوارزمية QAOA لحل الـ QUBO. ويتصل المسار بثلاثة محركات حل متميزة:
   • Ava من Fermioniq: وهو محاكي دوائر الشبكة الموترية (Tensor Network).
   • MPS-JuliQAOA: وهو محاكي "متجه حالة مصفوفة المنتج" (MPS) مفتوح المصدر مبني بلغة جوليا (Julia).
   • IBM Quantum: التنفيذ المباشر على أجهزة الكم الكمي فائقة التوصيل (معالج IBM Eagle).
4. دراسة الحالة: يتم تقييم إطار العمل على "مسألة توجيه المركبات" (VRP)، وهي مسألة لوجستية نموذجية. تستخدم الدراسة معياراً قياسياً من QOptLib (20 عميلاً، 4 مركبات) ونماذج تجريبية عشوائية (5 عملاء) لاختبار جدوى المسار.

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

• التوسع القائم على البوابات: توسع الورقة إطار عمل HQC-MCMS من التلدين الكمي إلى الحوسبة الكمية القائمة على البوابات، مما يسمح بالتنفيذ على كل من محاكيات الشبكة الموترية والمعالجات الكمية فائقة التوصيل.
• التنفيذ المتكامل: نجح المؤلفون في إثبات وجود مسار وظيفي كامل يدمج عمليات QAOA الفرعية داخل حلقة تفكيك بندرز الكلاسيكية.
• القياس التجريبي: توفر الدراسة تحليلاً مقارناً لأداء المسار عبر محركات حل مختلفة (Cbc الكلاسيكي، MPS-JuliQAOA، Fermioniq، وIBM Quantum) على نماذج VRP.

النتائج
تقدم النتائج التجريبية عدة رؤى نقدية فيما يتعلق بالجدوى الحالية للتفوق الكمي في هذا السياق المحدد:

• الأداء الكلاسيكي: في الإعداد الكلاسيكي الكامل (باستخدام Cbc لاختيار القطع)، نجح المسار في إيجاد حلول ممكنة لنموذج VRP ذي الـ 20 عميلاً، مع انخفاض فجوة المثالية عبر التكرارات. ويؤدي نهج "القطع المتعددة" (باستخدام مسائل فرعية أكثر) إلى الوصول لنتائج ممكنة في عدد أقل من التكرارات.
• اختناقات وقت التشغيل: يكشف تحليل المسار الكلاسيكي أن خطوة اختيار القطع تستهلك جزءاً صغيراً فقط من إجمالي وقت التكرار؛ حيث يُستهلك معظم الوقت في حل المسألة الرئيسية.
• الأداء الكمي: عند استبدال خطوة اختيار القطع بخوارزمية QAOA (باستخدام MPS-JuliQAOA) في مسألة تجريبية صغيرة، يزدัง وقت التشغيل الإجمالي بشكل كبير مقارنة بالنهج الكلاسيكي. وتشير الدراسة إلى أن MPS-JuliQAOA أقل كفاءة بكثير من المحلل الكلاسيكي Cbc بالنسبة لمسألة "تغطية المجموعات الدنيا" بهذا الحجم.
• مخرجات QAOA: تظهر التجارب على الأجهزة الكمية والمحاكيات أنه بالنسبة للإعدادات المختبرة، تؤدي غالبية عينات QAOA إلى حلول غير ممكنة (أي أنها لا تشكل تغطية صحيحة للمجموعات). ورغم أن الدوائر الأعمق ($p=3$) أعطت عينات ذات تكلفة أمثل أكثر من الدوائر الأقل عمقاً ($p=1$)، إلا أن الأداء العام لم يتجاوز الطرق الكلاسيكية.

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

1. خطوة اختيار القطع، وهي الهدف من التسريع الكمي، ليست عائقاً حوسبياً في مسار MCMS الكلاسيكي الحالي؛ إذ تهيمن عملية حل المسألة الرئيسية على وقت التشغيل.
2. المحلل الكلاسيكي (Cbc) يتفوق بمراحل على تطبيقات QAOA بالنسبة لمسائل "تغطية المجموعات الدنيا" المحددة في هذا النطاق.

ويؤكد المؤلفون أنه بينما يعد المسار فعالاً من الناحية التقنية ويثبت خطوة قابلة للتكرار نحو التحسين المعزز كمياً، فإن تحويل مسألة "تغطية المجموعات" إلى نموذج QUBO يضيف أعباءً حسابية كبيرة. ويرون أن الأبحاث المستقبلية يجب أن تركز على اختبارات قياسية ذات نطاق أكبر حيث قد تصبح خطوة اختيار القطع عائقاً أكثر أهمية، وحيث يمكن لوحدات المعالجة الكمية (QPUs) الأكثر قوة أن تقدم قيمة مضافة. وتعمل هذه الدراسة كتحليل تجريبي تحذيري، يسلط الضوء على أن الطرق الكمية الحالية لا توفر بعد سرعة فائقة لهذا النوع المحدد من خطوات التفكيك في النماذج العملية ذات النطاق الصغير إلى المتوسط.