Symmetry-based quantum algorithms for open-shop scheduling with hard constraints

ملخص تقني: خوارزميات الكم القائمة على التماثل لجدولة المتجر المفتوح مع القيود الصارمة

بيان المشكلة
تتناول الورقة مشكلة جدولة المتجر المفتوح (OSSP)، وهي مشكلة تحسين توافقي حيث يجب توزيع $J$ من المهام عبر $M$ من الآلات مع $T$ من الفترات الزمنية لكل منها. تتطلب القيود أن يتم تنفيذ كل مهمة بالضبط مرة واحدة، وألا يتم تعيين أكثر من مهمة واحدة لكل آلة-فترة زمنية. هذه المشكلة هي تعميم لمشكلة البائع المتجول (TSP)، حيث $TSP = OSSP(1, T, T)$.

يكمن التحدي الجوهري في ترميز هذه "القيود الصارمة" في الخوارزميات الكمومية التباينية (VQAs). وخلافاً للمشكلات غير المقيدة (مثل MAX-CUT) أو تلك التي تحتوي على قيود "مرمزة برفق" (حيث يتم فرض عقوبة على عدم الصلاحية في دالة الهدف)، تتطلب مشكلة OSSP أن يظل التحسين حصرياً داخل الفضاء الجزئي الصالح. غالباً ما تؤدي الترميز الرقيق إلى مساحات تحسين فرعية غير مثالية أو مشكلات في الصلاحية. وبينما توفر خوارزمية QAOA إطاراً للقيود الصارمة عبر "خلاطات" (mixers) تحافظ على الصلاحية، فإن البناءات الحالية لمشكلات الجدولة كانت غالباً تجريبية، وتفشل في استغلال هياكل التماثل الكامنة في المشكلة بشكل كامل.

المنهجية
يستخدم المؤلفون نهجاً صارماً يعتمد على نظرية المجموعات ونظرية المخططات لتحليل هيكل الصلاحية لـ OSSP:

1. نموذج مخطط القيود: يتم رسم المشكلة كـ مخطط قيود $G=(V, E)$ حيث تمثل الرؤوس عمليات تعيين المهام المحتملة (البتات) وتمثل الحواف القيود التي تمنع التعيين المتزامن. وتتوافق الحلول مع المجموعات المستقلة (cocliques) ذات الحجم $J$.
2. المجموعة الحافظة للصلاحية ($F$): يحدد المؤلفون المجموعة $F$ من تبديلات قيم البتات التي تنقل الحلول الصالحة إلى حلول صالحة أخرى. وقد أثبتوا أن هذه المجموعة متماثلة مع مجموعة التماثل للمخطط $G$، أي $\text{Aut}(G)$.
   • في حالة "الازدحام" ($MT = J$)، يتضمن هيكل المجموعة "الضرب الالتفافي" (wreath product) للمجموعات المتماثلة.
   • والأهم من ذلك، أثبتوا أن $F$ تعمل بشكل متعدٍ (transitively) على مجموعة كافة الحلول الصالحة. وهذا يعني أنه يمكن تحويل أي حل صالح إلى أي حل آخر عبر سلسلة من التبديلات في $F$.
3. تصميم الخوارزمية:
   • توسيع QAOA: قاموا بتحسين إطار عمل QAOA عبر بناء خلاطات مستمدة مباشرة من مولدات $F$. وبما أن $F$ تعمل بشكل متعدٍ، فإن الخلاطات المشتقة من عناصرها تضمن إمكانية الوصول إلى كامل الفضاء الجزئي الصالح.
   • خوارزمية VQA جديدة (تحسين المجموعات الكمومية): بالنسبة لحالات OSSP المزدحمة، يقترح المؤلفون خوارزمية جديدة تتجاوز فاصل الطور القياسي. ومن خلال تفكيك التبديلات في المجموعة المتماثلة $S_J$ (التي تمثل فضاء الحل لـ OSSP المزدحم) إلى حاصل ضرب التبديلات (transpositions)، قاموا ببناء دائرة معلمية باستخدام بوابات SWAP.
   • التمثيل بالمعلمات (Parameterization): تستخدم الخوارمة تفكيكاً محدداً للتبديلات إلى $J(J-1)/2$ من التبديلات، حيث يتم تنفيذ كل تبديل كحاصل ضرب بوابات SWAP منفصلة عبر كتل المهام.

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

• التوصيف النظري: تقدم الورقة توصيفاً كاملاً لمجموعة الحفاظ على الصلاحية لـ OSSP، حيث تثبت تماثلها مع مجموعة التماثل لمخطط القيود وتثبت عملها المتعدي على مجموعة الحلول.
• الوصول المضمون: خلافاً لـ QAOA العام، حيث لا يُضمن الوصول إلى الحل الأمثل إلا في حد لانهائي من عمق الدائرة ($p \to \infty$)، تقدم الـ VQA المقترحة حداً علوياً صارماً للمعلمات. لقد أثبت المؤلفون أن عدد معلمات قدره $O(J^3)$ (تحديداً $J(J-1)/2$) كافٍ للوصول إلى أي حل صالح، بما في ذلك الحل الأمثل العالمي، بيقين تام.
• تنفيذ القيود الصارمة: يوضح العمل طريقة منهجية لبناء خلاطات تحافظ بدقة على الفضاء الجزئي الصالح، متجنبة عيوب الترميز الرقيق للقيود.
• التنفيذ على الأجهزة: طبق المؤلفون الخوارزمية على جهاز كمي حقيقي (IBM Q System One) لحالة $OSSP(1, 3, 3)$ (المكافئة لمشكلة TSP لـ 3 مدن) وأجروا محاكاة خالية من الضجيج لحالة $OSSP(2, 2, 4)$.

النتائج

• المحاكاة الخالية من الضجيج ($OSSP(2, 2, 4)$): نجحت الـ VQA المقترحة ذات القيود المرمزة برفق في الوصول إلى الحد الأدنى العالمي (نسبة تقريب 100%) خلال ست تكرارات (بتحسين 12 معلمة). وفي المقابل، فشلت خوارزمية QAOA القياسية ذات القيود المرمزة برفق في تجاوز نسبة تقريب 30%، حتى مع الوصول إلى جميع المعلمات الـ 18، وذلك بسبب صعوبة تركيز السعة في الفضاء الجزئي الصغير.
• الأجهزة الحقيقية ($OSSP(1, 3, 3)$): على جهاز IBM Q System One، أظهرت الخوارزمية القدرة على مغادرة الحالة الأولية وزيادة التداخل مع الحل الأمثل المحلي. ومع ذلك، أشار المؤلفون إلى أن ضجيج الأجهزة قد طمس بشكل كبير التقارب نحو الحل الأمثل العالمي، حيث هيمنت الخلفية الضوضائية على الإشارة. أظهرت المحاكاة الكلاسيكية للضجيج تقارباً أفضل، مما يشير إلى أن قيود الأجهزة الحالية (زمن التماسك، ودقة البوابة) هي العوائق الأساسية بدلاً من التصميم الخوارزمي.

الأهمية والادعاءات
يدعي المؤلفون أن الأهمية الرئيسية لعملهم تكمن في توفير إطار عمل منهجي قائم على التماثل لترميز القيود الصارمة في VQAs، والانتقال إلى ما وراء التصميم التجريبي للخلاطات. ومن خلال ربط هيكل صلاحية المشكلة بتماثلات المخطط، استنتج المؤلفون خوارزمية ذات ضمان نظري بأن عدداً حدودياً من المعلمات ($O(J^3)$) كافٍ لاستكشاف فضاء الحل بالكامل.

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