Partitioned-Constraint QAOA (PC-QAOA): Structural State Preparation and Penalty Enforcement for Quantum Optimization

ملخص تقني: خوارزمية QAOA ذات القيود المجزأة (PC-QAOA)

بيان المشكلة
لا تزال مشكلات التحسين التوافقي المقيدة (COPs) تشكل تحديًا كبيرًا للخوارزميات الكمومية، لا سيما خوارزمية التقريب الكمومي للتحسين (QAOA). يعتمد النهج القياسي للتعامل مع القيود على تحويل المشكلات المقيدة إلى مشكلات تحسين ثنائي تربيعي غير مقيد (QUBO) عبر إضافة حدود جزاء (penalty terms) إلى هاميلتوني التكلفة. هذا الأسلوب، المعروف باسم PenaltyQAOA، يفرض عدة صعوبات: فهو غالبًا ما يتطلب متغيرات مساعدة (slack variables)، ويزيد من كثافة الـ QUBO الناتج، ويستلزم ضبطًا دقيقًا لمعاملات الجزاء. يمكن للجزاءات الكبيرة أن تشوه مشهد الطاقة، مما يخلق حواجز شديدة تمنع الحساسية تجاه تحسينات الهدف أو تؤدي إلى مشاهد تحسين عالية التذبذب. ومن ناحية أخرى، فإن النهج الهيكلي الكامل (مثل QAOA+ أو Grover-Mixer QAOA) الذي يحصر البحث داخل الفضاء الفرعي الممكن عبر خلاطات (mixers) وتجهيز حالات خاصة بالمشكلة، غالبًا ما يتطلب تصميمات دوائر معقدة خاصة بالمشكلة، والتي يصعب تجهيزها وقد تعاني من مشكلات "السهول الضحلة" (barren plateaus) أو محدودية الاتصال.

المنهجية: إطار عمل PC-QAOA
يقدم المؤلفون إطار عمل (PC-QAOA)، وهو إطار هجين يتوسط بين فرض القيود القائم على الجزاء بالكامل والفرض الهيكلي بالكامل. الفكرة الجوهرية هي تقسيم مجموعة القيود $C$ إلى مجموعتين منفصلتين:

1. القيود الهيكلية ($C_{str}$): يتم فرضها عبر عمليات تجهيز الحالة والخلاط التي تحافظ على الإمكانية (feasibility).
2. قيود الجزاء ($C_{pen}$): يتم فرضها عبر حدود جزاء طاقية في هاميلتوني التكلفة.

تسير الخوارزمية وفق الخطوات التالية:

• تقسيم القيود: تقوم خوارزمية جشعة مكونة من مرحلتين بتعيين القيود إلى $C_{str}$ إذا كانت تسمح بتجهيز حالة فعال ولها دعم منفصل عن القيود الهيكلية المختارة مسبقًا. أما القيود المتبقية، فتُعين إلى $C_{pen}$.
• الفرض الهيكلي: بالنسبة للقيود في $C_{str}$، تقوم الخوارزمية بتجهيز حالة أولية $|F_{str}\rangle$ تكون عبارة عن تراكب للتعيينات الممكنة.
  • بالنسبة لعائلات محددة (العدد، التعيين، حفظ التدفق)، تُستخدم دوائر دقيقة (مثل تجهيز حالات Dicke).
  • بالنسبة للقيود العامة ذات الدعم المنخفض التي تفتقر إلى بناءات دقيقة، يقدم المؤلفون أدوات القيود التباينية (VCGs). وهي دوائر كمومية معلمية يتم تدريبها خارج الخط (offline) باستخدام إجراء QAOA متعدد الزوايا لتقريب التراكب المنتظم لمجموعة الحلول الممكنة لقيد واحد.
• الخلط (Mixing): يتم بناء مؤثر الخلط بحيث يحافظ على الفضاء الفرعي الممكن المحدد بواسطة $C_{str}$. بالنسبة للأدوات الدقيقة، تُستخدم خلاطات محددة (مثل XY-mixers للعدد، وGrover mixers لـ VCGs). أما الكيوبتات (qubits) التي لا تغطيها الأدوات الهيكلية، فتستخدم خلاطات X القياسية.
• الفرض الطاقي: يتضمن هاميلتوني التكلفة دالة الهدف الأصلية بالإضافة إلى حدود الجزاء فقط للقيود المتبقية في $C_{pen}$. نظرًا لأن البحث مقيد في $F_{str}$، يمكن أن تكون معاملات الجزاء المطلوبة أصغر، حيث أن نطاق دالة الهدف عبر الفضاء الممكن المختزل عادة ما يكون أصغر مما هو عليه عبر الفضاء الثنائي الكامل.

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

1. التعامل الهجين مع القيود: يقترح البحث إطار عمل جديد يوازن بين تعقيد الدائرة وتقليص فضاء البحث من خلال ترميز هيكل القيود انتقائيًا في الحالة الأولية والديناميكيات، مع الاحتفاظ بالجزاءات للقيود المعقدة أو المتداخلة.
2. أدوات القيود التباينية (VCGs): يقدم المؤلفون طريقة لبناء تجهيزات حالة ممكنة تقريبية للقيود arbitrary ذات الدعم المنخفض. يتم تدريب هذه الأدوات خارج الخط لتقليل هاميلتوني خاص بالقيد، ويمكن إعادة استخدامها عبر نماذج المشكلات المختلفة، مما يوفر بديلًا مرنًا عند عدم توفر بناءات دقيقة.
3. الضمانات النظرية حول التركيب: يثبت البحث (الافتراض IV.1) أن أدوات القيود ذات الدعم المنفصل زوجيًا تتشكل بدقة دون تداخل، مما يسمح بتجهيز التراكب الممكن المشترك بالتوازي. ويوضح الاستنتاج IV.2 أن تراكم الخطأ في الاحتمالية الممكنة المشتركة محدود بمجموع أخطاء الأدوات الفردية، مما يضمن إمكانية عالية حتى مع الأدوات التقريبية.
4. بناء حفظ التدفق: تم تقديم بناء دائرة دقيقة جديد لقيود حفظ التدفق، باستخدام تجهيزات حالات Dicke مترابطة لفرض وزن هامينج متساوٍ عبر مجموعات المتغيرات.

النتائج
قيم المؤلفون PC-QAOA على 413 حالة مكتملة تمتد عبر سبع عائلات من القيود (بما في ذلك العدد، التعيين، حفظ التدفق، الحقيبة، والحقيبة التربيعية) مع أحجام مشكلات $n \in \{3, \dots, 8\}$.

• الإمكانية وجودة الحل: تفوق PC-QAOA بشكل كبير على PenaltyQAOA. عند العمق الضحل ($p=1$)، حقق PC-QAOA متوسط نسبة تقريب ممكنة ($AR_{feas}$) قدره 0.588 مقارنة بـ 0.21� لـ PenaltyQAOA. وعند $p=5$، اتسعت الفجوة لتصل إلى 0.783 مقابل 0.305.
• احتمالية الإمكانية: حافظ PC-QAOA على احتمالية عالية لأخذ حل ممكن ($P(feas) \approx 0.912$ عند $p=1$)، بينما تدهورت نتيجة PenaltyQAOA بشكل ملحوظ ($P(feas) \approx 0.420$ عند $p=1$).
• احتمالية الحل الأمثل: أظهر PC-QAOA تحسنًا نسبيًا بنسبة 215% في احتمالية أخذ الحل الأمثل ($P(opt)$) عند$p=1$ مقارنة بـ PenaltyQAOA.
• كفاءة الموارد: تطلب PC-QAOA عددًا أقل من الكيوبتات (لا توجد متغيرات مساعدة للقيود الهيكلية) وأقل عدد من بوابات الكيوبت الثنائية. عند $p=1$، تطلب 1.35 ضعفًا أقل من بوابات الكيوبت الثنائية مقارنة بـ PenaltyQAOA. وعند $p=5$، نمت هذه الميزة لتصل إلى 1.45 ضعفًا.
• أداء VCG: حققت أدوات VCG المدربة احتمالية إمكانية $P_{Fk} = 1$ ومتوسط إنتروبيا ممكنة معيارية ($S_{norm}$) قدره 0.9186، مما يشير إلى تغطية شبه منتظمة للفضاء الممكن.

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