Generative Quantum Search for Combinatorial Optimization: Learning Shallow Quantum Samplers for Classically Refined Solution Subspaces

ملخص تقني: البحث الكمي التوليدي للتحسين التوليفي

بيان المشكلة
يتقصى هذا البحث ما إذا كان بإمكان أجهزة أخذ العينات الكمية الضحلة (shallow quantum samplers) التفوق على أجهزة أخذ العينات الكلاسيكية في التحسين التوليفي (combinatorial optimization) من خلال وضع كتلة احتمالية أعلى داخل "حوض الاسترداد الكلاسيكي" (classical recovery basin). تكيّف الدراسة بنية خوارزمية (GQE+QSCI) -المطورة أصلاً للكيمياء الكمية- لتناسب مجال تحسين الرسوم البيانية (تحديداً مسألة المجموعة المستقلة ذات الوزن الأقصى، MWIS). وتتمثل الفرضية الجوهرية في أن جهاز أخذ عينات كمي يمكنه توليد توزيع من الحلول المرشحة التي، عند صقلها بواسطة خوارزمية إصلاح وتوسيع كلاسيكية، تعطي معدل نجاح أعلى من أجهزة أخذ العينات الكلاسيكية.

المنهجية
يقترح المؤلف إطار عمل GQO+QSS (التحسين الكمي التوليدي + البحث المختار كمياً)، والذي يتبع مساراً من أربع مراحل:

1. السياسة التوليدية (Generative Policy): نموذج تعلم آلي (سياسة مشروطة بالرسم البياني) يولد برامج دوائر كمية (مثل معاملات QAOA).
2. أخذ العينات الكمي (Quantum Sampling): يتم تنفيذ الدوائر على محاكي أو وحدة معالجة كمية (Piast-Q) لإنتاج سلاسل بتات (حلول مرشحة).
3. الاسترداد الكلاسيكي (Classical Recovery): تقوم دالة إصلاح خاصة بالمسألة بتصحيح الحلول غير الصالحة، يتبعها توسيع محلي (مثل جوار $r$-flip) لإنشاء فضاء بحث مقيد.
4. المحلل المقيد (Restricted Solver): يجد محلل كلاسيكي دقيق الحل الأمثل ضمن هذا الفضاء المقيد.

الصياغة النظرية الرئيسية
تصيغ الورقة مسألة "الفائدة الكمية" باستخدام كتلة حوض الاسترداد ($p_r$):
$$p_r(q_\theta, G) = \Pr_{x \sim q_\theta} [x \in A_r(G)]$$
حيث $A_r(G)$ هي مجموعة الحالات التي تحتوي، بعد الإصلاح وتوسيع $r$-flip، على الحل الأمثل العالمي. احتمال النجاح مع عدد $B$ من الطلبات (shots) هو $P_{success} = 1 - (1 - p_r)^B$. وتفترض الدراسة أن المقياس الحاسم ليس حجم الفضاء الذي تم أخذ العينات منه بالنسبة لإجمالي الفضاء ($|S_Q|/2^n$)، بل كتلة الاحتمال $p_r$ التي يضعها جهاز أخذ العينات في الحوض القابل للاسترداد.

بروتوكول التجربة

• مجموعات البيانات: 150 حالة من حالات MWIS تم التحقق من حقائقها الأرضية (ground truths) عبر CBC والتحقق بالقوة الغاشمة (brute-force).
• النماذج المرجعية (Baselines): تمت مقارنة تسعة أجهزة لأخذ العينات، بما في ذلك العشوائي المنتظم، والبحث الجشع (greedy)، والتلدين المحاكى (SA)، والبحث التابو (tabu search)، والبحث المحلي متعدد البدايات، ومتروبوليس، وQAOA ذو البداية الدافئة (warm-start)، وQAOA المعتمد على الأوراكل (أفضل 50 تكويناً)، وسياسة كلاسيكية متعلمة مطابقة.
• القيود: بروتوكول مجمد ومسجل مسبقاً بميزانية ثابتة قدرها 200 طلب لكل جهاز أخذ عينات.
• الأجهزة: شملت التجارب عمليات محاكاة وتنفيذاً على معالج Piast-Q ذي الأيونات المحاصرة (20 كيوبت).

النتائج الرئيسية

1. الهيمنة الكلاسيكية: تفوق بحث "التابو" (Tabu search) والتلدين المحاكى (SA) بشكل كبير على جميع أجهزة أخذ العينات الكمية والمتعلمة الكلاسيكية عبر جميع أحجام المسائل المختبرة ($n=16$ إلى $n=28$). حقق بحث التابو كتلة حوض استرداد ($p_r$) تتراوح بين 0.822 عند $n=16$ و0.944 عند $n=18$، وقيم 0.878 عند $n=20$، و0.943 عند $n=24$، و0.901 عند $n=28$. بينما تراوح SA بين 0.088 و0.428 عبر هذه الأحجام.
2. ضعف الأداء الكمي: خسرت جميع أجهزة أخذ العينات الكمية (warm-start QAOA، وoracle QAOA، والسياسات التوليدية) أمام كل من SA وبحث التابو في كل حجم مسألة تحت البروتوكول العادل والمسجل مسبقاً.
3. أثر "الأوراكل" (The Oracle Artifact): تم تحديد النتائج الإيجابية السابقة التي أظهرت تفوق QAOA على SA كآثار ناتجة عن اختيار التكوين لكل حالة (أعلى حد "أوراكل" لا يمكن نشره). عند التقييم باستخدام تكوينات عشوائية (وهي طريقة قابلة للنشر)، حقق oracle QAOA قيمة $p_r = 0.014$ عند $n=28$، وهو أقل بكثير من SA البالغ 0.088.
4. التكافؤ الكلاسيكي المتعلم: حققت سياسة كلاسيكية متعلمة (140 ألف معلمة) أداءً مماثلاً لـ oracle QAOA ($p_r = 0.005–0.101$ مقابل $0.014–0.113$)، مما يشير إلى أن الدائرة الكمية لا تقدم أي ميزة هيكلية فوق النموذج الكلاسيكي المطابق في هذا السياق.
5. متانة الأجهزة: أظهرت التجارب على Piast-Q اتساقاً بنسبة 93.4% في الاسترداد بين عينات QPU والمحاكي، مما يؤكد متانة الأجهزة ولكنه كشف عن عدم وجود ميزة كمية في جودة التحسين.
6. انتقال الاسترداد: رسمت الدراسة "انتقال استرداد" حيث يكون الاسترداد الكلاسيكي كافياً لـ $n \le 16$ ولكنه يبدأ في الفشل لـ $n \ge 20$ مع توسيع 2-flip. ومع ذلك، حتى في نظام الانتقال هذا، حافظت النماذج الكلاسيكية القوية (SA، Tabu) على أداء متفوق.

الأهمية والادعاءات
تقدم هذه الورقة نفسها كـ دراسة تفنيد (falsification study). ادعاؤها الأساسي هو أنه تحت تقييم صارم ومسجل مسبقاً مع نماذج أساسية متعلمة مطابقة، فإن توزيعات الاقتراح المشتقة من QAOAs الضحلة لا تتفوق على نماذج الاقتراح الكلاسيكية المطابقة في التقاط أحواض الاسترداد الكلاسيكية في مسألة MWIS.

• لا توجد ميزة كمية: يدعي المؤلف صراحةً عدم وجود ميزة كمية لبنية GQO+QSS في الأنظمة المختبرة.
• تفنيد الادعاءات السابقة: تعزو الدراسة النتائج الإيجابية السابقة إلى تأثير "الأوراكل" المتمثل في اختيار أفضل تكوين لكل حالة، وهي طريقة غير قابلة للنشر.
• تصحيح المقياس: تجادل الورقة بأن "كسر الفضاء الجزئي" ($|S_Q|/2^n$) هو مقياس تحصيل حاصل في ظل ميزانيات الطلبات الثابتة، وأن كتلة حوض الاسترداد ($p_r$) هي الكمية الدقيقة علمياً للقياس.
• الاتجاه المستقبلي: يقترح المؤلف أنه لكي يوفر أخذ العينات الكمي قيمة، يجب أن يضع باستمرار كتلة أكبر في حوض الاسترداد من النماذج الكلاسيكية القوية (مثل SA) في الأنظمة التي يفشل فيها الاسترداد الكلاسي (عند $n \ge 55$)، وهو تحدٍ لم تلبه الدوائر الضحلة الحالية بعد.

تخلص الدراسة إلى أنه بينما تعد بنية GQO+QSS إطار عمل صالح للتحسين الهجين، فإن أجهزة أخذ العينات الكمية الضحلة الحالية لا توفر ميزة هيكلية فوق طرق البحث العشوائي الكلاسيكية القوية في المهمة المحددة المتمثلة في التقاط حوض استرداد MW.