ملخص تقني: أخذ العينات البديلة المستنيرة كموميًا (QISS) للتحسين التوافقي

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

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

هناك قيد جوهري في خوارزمية QAOA الضحلة وهو المحلية (locality): بالنسبة للرسوم البيانية المتفرقة (sparse graphs)، يكون "المخروط الضوئي" (light cone) للدائرة محدودًا بالعمق $p$ وليس بحجم المشكلة $N$. وبناءً على ذلك، غالبًا ما تفشل خوارزمية QAOA ذات العمق الثابت ($p$) في استغلال الهياكل العالمية للمشكلة، وترث قيودًا مشابهة للخوارزميات الكلاسيكية المحلية. علاوة على ذلك، فإن توزيع المخرجات الكامل لحالة كمومية يكون عمومًا غير قابل للاستخراج كلاسيكيًا بشكل مباشر، ولا يمكن للجهاز الكمومي إنتاج حلول عالية الجودة مباشرة عندما يكون مقيدًا بأعماق ضحلة.

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

2. المنهجية: أخذ العينات البديلة المستنيرة كموميًا (QISS)

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

سير العمل الأساسي

1. التقدير الكمومي: يتم تنفيذ دائرة QAOA ضحلة (العمق $p$) على جهاز كمومي (أو محاكاة) لتقدير مجموعة مختارة من قيم التوقع (الارتباطات) منخفضة الوزن $\mu_{S_\alpha}$:
   $$\mu_{S_\alpha} = \langle \psi_p(\gamma, \beta) | \prod_{i \in S_\alpha} Z_i | \psi_p(\gamma, \beta) \rangle$$
   تركز الورقة على الأوزان $|S_\alpha| \in \{1, 2\}$. هذه القيم يمكن الوصول إليها عبر القياسات المتكررة وهي مهيأة لتخفيف الخطأ.

2. بناء التوزيع البديل: يتم بناء توزيع عامل كلاسيكي $P(z)$ على فضاء الحلول $\{-1, +1\}^N$ باستخدام هذه الارتباطات المقاسة كمعاملات:
   $$P(z) \propto \prod_{S_\alpha \in \mathcal{S}} \left( 1 + \mu_{S_\alpha} \chi_{S_\alpha}(z) \right)$$
   حيث $\chi_{S_\alpha}(z) = \prod_{i \in S_\alpha} z_i$ هي دالة التكافؤ (parity function). هذا التوزيع يكافئ توزيع غيبس (Gibbs distribution) لهاملتوني-إيزينغ فعال $H'$ مع روابط $J_{S_\alpha} = -\text{arctanh}(\mu_{S_\alpha})$.

3. أخذ العينات الكلاسيكي: يتم سحب الحلول المرشحة من $P(z)$ باستخدام مونت كارلو عبر سلاسل ماركوف (MCMC). تستخدم عملية أخذ العينات تحديثات شرطية أحادية الموقع، وهي فعالة لأن الاحتمال الشرطي لقلب السبين (spin flip) يعتمد فقط على العوامل المحلية التي تشمل ذلك السبين. ولا يتطلب الأمر معرفة ثابت التطبيع (partition function) أبدًا.

4. اختيار الارتباطات: تميز الورقة بين مجموعتين من الارتباطات:

   • مجموعة الحواف ($\mathcal{S} = E \cup V$): تشمل فقط الحواف المباشرة لرسم المشكلة البياني. في الرسوم البيانية التي تشبه الأشجار محليًا، تعيد هذه المجموعة لحظات QAOA دون تحسين.
   • المجموعة الموسعة ($\mathcal{S}' = E' \cup V$): تتضمن جميع الأزواج $(i, j)$ ضمن مسافة المخروط الضوئي $d_G(i, j) \le 2p$. هذا يخلق رسمًا عاملاً كثيفًا وغير شبيه بالأشجار، مما يسمح للبديل بالتقاط ارتباطات رتب عليا بشكل ضمني وتوليد حلول تتفوق على مخرجات QAOA الخام.

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

• خالٍ من التدريب: تستخدم الطريقة زوايا QA-optimal ثابتة (من المرجع [61])، مما لا يتطلب أي تحسين متغير للبديل.

• نمطي (Modularity): خطوة أخذ العينات مستقلة عن دالة التكلفة؛ فهي تتطلب فقط الارتباطات.

• مقاومة الضجيج: عملية الربط من الارتباطات إلى الروابط ($\text{arctanh}$) سلسة، مما يجعل البديل قويًا تجاه الضجيج في الإحصائيات المقاسة.

3. المساهمات والنتائج الرئيسية

أ. القطع الأقصى (MaxCut) على الرسوم البيانية ثلاثية الانتظام

• الأداء مقابل Vanilla QAOA: عند استخدام مجموعة الارتباطات الموسعة (جميع الأزواج ضمن المسافة $2p$)، تتفوق QISS بشكل كبير على Vanilla QAosa. وتحديدًا، تحقق QISS باستخدام ارتباطات من دائرة QAOA بعمق $p=3$ أو $p=4$ متوسط نسب قطع يتجاوز Vanilla QAOA عند العمق $p=17$ (أكبر عمق تُعرف له زوايا مثالية شجرية).
• تكامل البداية الدافئة (Warm-Start Integration): تم دمج الطريقة مع Regularized Warm-Start QAOA (RWS-QAOA). حتى عند الأعماق الضحلة ($p=1, 2$)، أدت المعالجة اللاحقة لـ QISS إلى تحسين جودة الحل، مما دفع نسبة التقريب لتكون قريبة من الحد الأمثل.
• التحقق من الأجهزة: أُجريت التجارب على وحدة معالجة كمومية IQM Emerald QPU بـ 54 كيوبت. أظهرت النتائج أن QISS مقاومة جدًا للضجيج. كانت نسب التقريب التي تم الحصول عليها من ارتباطات QPU الصاخبة الخام تكاد لا تختلف عن تلك التي تم الحصول عليها من المحاكاة الخالية من الضجيج. لقد تم "غسل" ضجيج الجهاز فعليًا بواسطة المعالجة اللاحقة، مما جعل تخفيف الخطأ غير ذي صلة إلى حد كبير بجودة الحل النهائي في هذا النطاق.
• القابلية للتوسع: حافظت الطريقة على أدائها حتى $N=140$ (محدودة بعدد الكيوبتات المتاحة بعد تجميد المتغيرات)، مع بقاء نسب التقريب مستقرة وفوق ضمانات SDP القياسية.

ب. المجموعة المستقلة القصوى (MIS)

• التعامل مع القيود: على عكس MaxCut، تعد MIS مشكلة مقيدة. قد تحتوي عينات QISS على تعارضات (عقد متجاورة مختارة معًا). قدم المؤلفون إجراء تقليم (pruning) بسيطًا للمعالجة اللاحقة لحل التعارضات وإضافة العقد الصالحة بشكل جشع (greedily).
• الأداء: بالنسبة لـ MIS، أدى استخدام ارتباطات الحواف فقط إلى أداء أسوأ من Vanilla QAOA بسبب غياب تناظر $Z_2$ وتداخل العوامل. ومع ذلك، سمح استخدام مجموعة الارتباطات الموسعة مع إجراء التقليم لـ QISS بالتفوق على QAOA المستقل ومنافسة الخوارزميات الكلاسيكية المتطورة (مثل البحث ذو الأولوية الخطية والخوارزميات الجشعة المعززة كموميًا).

ج. المقارنة مع الحلول الكلاسيكية

تم اختبار QISS مقابل Simulated Annealing (SA) وتخفيف Burer–Monteiro (BM) من الرتبة الثانية لـ Goemans–Williamson SDP.

• أنتجت QISS المدمجة مع RWS-QAOA نتائج تنافسية مع حل BM.
• على عكس أخذ العينات الكلاسيكية التي يتدهور أداؤها مع زيادة حجم النظام تحت ميزانية زمنية ثابتة، تستفيد QISS من محلية ارتباطات QAOA، والتي تظل مستقرة مع $N$.

4. الأهمية والادعاءات

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

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

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