Exhaustive and feasible parametrisation with applications to the travelling salesperson problem

ملخص تقني: التوصيف الشامل والقابل للتنفيذ للتحسين التوافقي

1. بيان المشكلة

تتناول الورقة البحثية قيداً جوهرياً في أطر خوارزمية التقريب الكمي للتحسين (QAOA) الحالية، لا سيما فيما يتعلق بـ مشكلات التحسين التوافقي المقيدة مثل مسألة البائع المتجول (TSP).

في خوارزمية QAOA القياسية، يتم تصميم الدائرة الكمية لاستكشاف فضاء الحالة، لكنها غالباً ما تعاني من مشكلات الوصول (reachability issues): حيث قد لا تتضمن مجموعة الحالات التي يمكن الوصول إليها بواسطة الدائرة الموصوفة بالمعلمات (parametrised circuit) الحل الأمثل، أو قد تصل إليه فقط بشكل تقاربي (عندما يؤول عدد المعلمات $p \to \infty$). علاوة على ذلك، عند التعامل مع "القيود الصارمة" (حيث تكون بعض الحلول ممنوعة تماماً)، تعتمد الطرق التقليدية غالباً على حدود الجزاء (penalty terms) في الهاملتوني (Hamiltonian)، مما قد يجعل مشهد التحسين صعب التوجيه.

2. المنهجية: المسار التجريدي

يقترح المؤلفون مفهوماً جديداً: الدوائر الكمية الشاملة الموصوفة والمحترمة للجدوى.

• شاملة (Exhaustive): تضمن الدائرة الوصول إلى كل حل ممكن (بما في ذلك الحل الأمثل) بدقة، باستخدام قيم محددة للمعلمات، عبر عدد محدود من المعلمات.
• محترمة للجدوى (Feasibility-Respecting): الدائرة مقيدة رياضياً بالفضاء الجزئي الممكن، مما يعني أنها لا تنتج أبداً حالات غير ممكنة، وبالتالي تتجنب الحاجة إلى حدود الجزاء.

لبناء هذه الدوائر، يقدم المؤلفون مساراً تجريدياً يعتمد على نظرية الزمر (Group Theory):

1. الفعل الزمروي المتعدي (Transitive Group Action): تحديد زمرة $G$ تعمل بشكل متعدٍ على المجموعة الممكنة للمسألة $F$. يضمن التعدي إمكانية رسم أي حالة ممكنة إلى أي حالة أخرى عبر عناصر الزمرة.
2. تسلسل توليدي من العناصر الارتدادية (Generating Sequence of Involutions): بدلاً من المولدات العشوائية، يستخدم المؤلفون "تسلسلاً توليدياً" — وهو قائمة مرتبة وثابتة من عناصر الزمرة التي، عند تطبيقها، يمكنها إعادة بناء أي عنصر في الزمرة. ومن الأهمية بمكان أن تكون هذه العناصر ارتدادية (involutions) (عناصر هي نفسها معكوس لنفسها، $h^2 = id$).
3. التنفيذ الكمي: من خلال تمثيل هذه العناصر الزمرية كعوامل وحدوية متعددة الكيوبتات ($H_i$) وأسّها بمعلمات حقيقية ($\theta_i$)، يمكن للدائرة "توجيه" الحالة الابتدائية إلى أي حالة ممكنة مرغوبة.

3. المساهمات الرئيسية والتطبيقات على مسألة البائع المتجول (TSP)

يطبق المؤلفون هذا المسار على مسألة البائع المتجول (TSP)، باستخدام الزمرة المتناظرة $S_n$ (زمرة جميع التباديل) كبنية أساسية. وقد استخلصوا بناءين متميزين للدائرة:

• تسلسل ترتيب الفقاعات (Bubble Sort Sequence): مستوحى من خوارزمية ترتيب الفقاعات الكلاسيكية، يستخدم هذا البناء تسلسلاً من $O(n^2)$ من عمليات التبديل المتجاورة (تبديل المدن المتجاورة). وهو سهل التنفيذ ولكنه يتطلب عدداً أكبر من المعلمات.
• تسلسل الإدراج الثنائي (Binary Insertion Sequence): بناء أكثر تعقيداً من الناحية الرياضية يستخدم نهجاً تكرارياً لبناء تسلسل توليدي. ينتج عن ذلك دائرة أكثر كفاءة بكثير تحتوي على $O(n \log n)$ من المعلمات فقط.

4. النتائج والبرهان العددي على المبدأ

أجرى المؤلفون محاكاة عددية لمثال مسألة البائع المتجول لـ 9 مدن (باستخدام 24 كيوبت) لمقارنة أساليبهم مع خلاطات QAOA الراسخة (Hadfield et al).

• الأداء: تفوقت كلا البناءين الجديدين على خوارزمية QAOA القياسية. حقق بناء الإدراج الثنائي (Binary Insertion) أعلى نسبة تقريب ($\approx 0.91$)، وهي أفضل بكثير من QAOA القياسية ($\approx 0.62$).
• الكفاءة: كان متغير الإدراج الثنائي أفضل من متغير ترتيب الفقاعات لأن فضاء المعلمات منخفض الأبعاد سمح للمُحسِّن الكلاسيكي (COBYLA) بالتنقل في المشهد بشكل أكثر فعالية.
• تنبيه حول القابلية للتدريب (Trainability): رغم أن الدوائر مضمونة نظرياً للوص-إلى الحل الأمثل (الوصول/reachability)، إلا أن النتائج العددية تظهر أن المُحسِّنات الكلاسيكية لا تزال تواجه صعوبة في إيجاد المعلمات المثلى بالضبط. وهذا يسلط الضوء على التمييز بين الوصول (reachability) (وجود الحل ضمن نطاق الدائرة) وبين القابلية للتدريب (trainability) (القدرة على إيجاد ذلك الحل).

5. الأهمية

تنقل هذه الورقة التركيز في تصميم الخوارزميات الكمية من "التقارب التقاربي" إلى "التغطية المضمونة". ومن خلال تتبع التعبيرية للدوائر الكمية وصولاً إلى نظرية الزمر الأساسية، يوفر المؤلفون إطاراً هندسياً صارماً لتصميم أجهزة/برمجيات كمية متخصصة للمسائل المقيدة.

هذه المنهجية قابلة للتعميم: أي مسألة توافقية تمتلك فعلاً زمروياً متعدياً متعدياً وتسلسلاً توليدياً من العناصر الارتدادية (مثل بعض مسائل الجدولة أو التوجيه) يمكنها الاستفضاء من هذا النهج "الشامل". وهذا يوفر خارطة طريق لتطوير خوارزميات كمية أكثر موثوقية لمهام التحسين ذات القيود الصارمة.