Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem

ملخص تقني: خوارزميات استدلالية قابلة للتوسع تعتمد على المشي الكمي لوغاريتم الحد الأدنى من غطاء الرؤوس

بيان المشكلة
تعد مشكلة الحد الأدنى من غطاء الرؤوس (MVC) تحدياً جوهرياً من نوع NP-complete في مجال الأمثلة التوافقية، وتتطلب تحديد أصغر مجموعة فرعية من الرؤوس $C \subseteq V$ في رسم بياني $G=(V, E)$ بحيث يكون كل ضلع متصلاً بـرأس واحد على الأقل في $C$. وبينما توجد خوارزميات دقيقة، إلا أنها تتوسع بشكل أسي مع حجم الغطاء. توفر استراتيجيات التقريب الكلاسيكية، مثل المطابقة القصوى، نسبة $\le 2$، ولكن دينور وسافرا أثبتا أنه لا توجد خوارزمية ذات زمن حدودي يمكنها تحقيق نسبة أقل من $\approx 1.3606$ للرسوم البيانية ذات الدرجات العالية. يهدف المؤلفون إلى استكشاف ما إذا كان بإمكان المشي الكمي في الزمن المستمر (CTQWs) توفير معيار اختيار عالي الجودة ومنهجي لمشكلة MVC يتفوق على الاستدلالات الكلاسيكية مع الحفاظ على القابلية للتوسع.

المنهجية
تقترح الورقة خوارزمية استدلالية تعتمد على CTQW تعمل بشكل تكراري لبناء غطاء رؤوس. تتضمن المنهجية الأساسية ثلاثة مكونات رئيسية:

1. الصياغة الكمية:

   • الهاملتوني (Hamiltonian): يتم ترميز الرسم البياني في هاملتوني $H$ يعتمد على لابلاتشيان المتماثل الموحد: $H = I - D^{-1/2}AD^{-1/2}$، حيث $A$ هي مصفوفة التجاور و $D$ هي مصفوفة الدرجة. يضمن هذا التنميط ديناميكيات انتشار موحدة، مما يقلل من الانحياز نحو الرؤوس ذات الدرجات العالية.
   • التطور: يتطور النظام تحت $U(t) = e^{-iHt}$ لزمن قصير ومثالي $t_{opt}$. يستخدم المؤلفون مخطط ترميز ثنائي، يمثل $n = \lceil \log_2 V \rceil$ كيوبت للرؤوس $V$، مما يقلل بشكل كبير من متطلبات الكيوبتات مقارنة بترميزات "الواحد الساخن" (one-hot encodings).
   • معيار الاختيار: في كل تكرار، يتم اختيار الرأس $m$ الذي يمتلك أعلى احتمال انتقال $P(m \to \text{out}) = 1 - |[e^{i\Gamma t}]_{mm}|^2$ وإضافته إلى الغطاء. هنا، $\Gamma$ هي مصفوفة التجاور الموحدة.
   • آلية التجميد: لمنع إعادة الاختيار وعزل الرأس المختار، يتم تطبيق حد عقوبة الطاقة على الفضاء الجزئي للرأس المختار. هذا "العزل الطيفي" (أو التجميد) يزيح الحالة المختارة عن الرنين، مما يؤدي فعلياً إلى إخراجها من الديناميكيات النشطة للعمليات اللاحقة دون حذف الأضلاع فيزيائياً من مصفوفة الهاملتوني.

2. الاشتقاق الكلاسيكي (استدلال مستوحى من الكم):

   • من خلال توسيع قصير المدى لأس المصفوفة $e^{i\Gamma t}$، يشتق المؤلفون تحليلياً أن معيار الاختيار الكمي يتقلص إلى كمية طيفية كلاسيكية يمكن حسابها في زمن $O(|E|)$:
     $$s(m) = [\Gamma^2]_{mm} = \frac{1}{d_m} \sum_{j \in N(m)} \frac{1}{d_j}$$
   • تمثل هذه الكمية متوسط مقلوب درجة جيران الرأس، موازاةً بدرجة الرأس نفسه. وهي تلتقط معلومات هيكلية من خطوتين (two-hop)، مما يميزها عن النهج الجشع البسيط القائم على الدرجة.

3. التنفيذ:

   • الأجهزة الكمية: تم تنفيذ الخوارزمية على منصات ibm_marrakesh (القائمة على البوابات) و Bloqade (الذرات المحايدة) التابعة لشركة IBM. التنفيذ القائم على البوابات محدود بعمق الدائرة ($O(V^2)$ من بوابات الرأسين) للرسوم البيانية الصغيرة ($V \lesssim 16$)، بينما يستخدم نهج الذرات المحايدة ذرة واحدة لكل رأس.
   • المحاكاة الكلاسيكية: تمت مقارنة الخوارزمية الطيفية الجشعة (الخوارزمية 2) مع الحلول الدقيقة للبرمجة الخطية المختلطة (MILP) والاستدلالات الكلاسيكية (الدرجة الجشعة، FastVC، تقريب 2، المحاكاة التلدينية) عبر 14,680 حالة.

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

• الارتباط الفيزيائي: يربط هذا العمل بين ديناميكيات النقل الكمي ومشكلة MVC، موضحاً أن الرؤوس ذات احتمالات الانتقال العالية تتوافق طبيعياً مع عناصر الغطاء ذات الصلة الهيكلية.

• كفاءة الموارد: من خلال استخدام الترميز الثنائي، تتطلب الخوارزمية الكمية فقط $\lceil \log_2 V \rceil$ من الكيوبتات، وهو انخفاض كبير مقارنة بـ $V$ من الكيوبتات المطلوبة في صياغات QAOA القياسية.

• الخوارزمية الكلاسيكية المستوحاة من الكم: المساهمة الرئيسية هي اشتقاق استدلال كلاسيكي (الخوارزمية 2) يعيد إنتاج أداء الخوارزمية الكمية بتعقيد $O(|E|)$ لكل تكرار، مما يجعلها قابلة للتوسع للرسوم البيانية التي يصل فيها $V \sim 10^5$ إلى $10^5$ رأس.
• التقييم الشامل: قدمت الدراسة تحققاً واسع النطاق عبر مجموعات Erdős–Rényi، و Barabási–Albert، والرسوم البيانية المنتظمة، بالإضافة إلى الشبكات الواقعية من مستودع SNAP.

النتائج

• الأداء مقابل الاستدلالات الكلاسيكية: عبر 14,680 حالة اختبار ($N \in [4, 150]$)، حقق النهج القائم على CTQW (ومكافئه الطيفي الكلاسيكي) متوسط نسبة تقريب قدره 1.015، وهو ما يتفوق بشكل ملحوظ على الدرجة الجشعة (1.023) والمحاكاة التلدينية (1.027). كان التفوق أكثر وضوحاً في الرسوم البيانية المنتظمة (Regular graphs)، حيث نجح المعيار الطيفي في حل حالات التعادل التي حيرت الطرق القائمة على الدرجة.
• الحالات الصعبة: في العائلات الصعبة هيكلياً (رسوم Crown، ورسم Petersen، والرسوم البيانية العشوائية ثلاثية الانتظام)، كانت أسوأ نسبة هي 1.143، وهي أقل بكثير من عتبة عدم القابلية للتقريب النظرية البالغة $\approx 1.3606$.
• القابلية للتوسع: في المقاييس الكبيرة ($V \in [10^3, 10^5]$)، حققت الخوارزمية الجشعة الطيفية أفضل حجم غطاء (نسبة 1.000 بالنسبة لأفضل حل افتراضي) في 100% من 210 حالة. لقد تفوقت على الدرجة الجشعة (متوسط نسبة 1.047) والمحاكاة التلدينية (متوسط نسبة 1.072).
• التحقق من الأجهزة: على أجهزة IBM، أنتجت الخوارزمية حلولاً دقيقة لـ $V=4$ ولكنها عانت من أخطاء البوابات عند $V=32$ بسبب عمق الدوائر. ومع ذلك، أكدت النتائج أن الترميز الثنائي قابل للتطبيق لـ $V$ الصغيرة، وأن تحليل المشي الكمي يعمل كآلية اكتشاف للمعيار الكلاسيكي.
• الشبكات الواقعية: في ثماني شبكات واقعية (بما في ذلك شبكات الطرق وشبكات التعاون)، طابقت الطريقة الجشعة الطيفية أفضل حل افتراضي في جميع الحالات، محققة تحسناً بنسبة 5.3% عن الدرجة الجشعة في شبكة طرق بنسلفانيا.

الأهمية والادعاءات
تفترض الورقة أن تحليل المشي الكمي يعمل في المقام الأول كـ آلية اكتشاف. وبينما تعد المحاكاة الكمية الكاملة غير قابلة للتنفيذ للرسوم البيانية الكبيرة على أجهزة NISQ الحالية بسبب قيود عمق الدائرة، فإن المبدأ الهيكلي الذي تشفره—وهو الوزن الطيفي لخطوتين من لابلاتشيان الموحد—ينتقل بسلاسة إلى خوارزمية كلاسية فعالة.

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