Unfair Sampling of Quantum Annealing in Weighted Graph Bipartitioning Problems

إليك ملخص تقني مفصل للورقة البحثية بعنوان "أخذ العينات غير العادل في التلدين الكمي في مسائل تقسيم المخططات الموزونة" من إعداد شونتا إيدي وشو تاناكا.

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

يعد التلدين الكمي (QA) نهجاً رائداً لحل مسائل الأمثلة التوافقية. ومع ذلك، لا تزال هناك مشكلة حرجة تُعرف باسم "أخذ العينات غير العادل" (Unfair Sampling): فحتى في الحد الأديباتي (عند أوقات تلدين كافية)، لا يتم أخذ الحالات الأرضية المتدهورة (الحلول المثلى المتعددة) باحتمالية متساوية. يعيق هذا الانحياز التطبيقات التي تتطلب تنوع الحلول، مثل العد التوافقي والتحسين القائم على التنوع.

تظهر هذه المشكلة بشكل خاص في المسائل التوافقية المقيدة، حيث يتم فرض القيود عادةً عبر طريقة الجزاء (Penalty Method). في هذه الطريقة، يتم إضافة حد جزاء ($H_{const}$) إلى هاميلتوني الهدف ($H_{obj}$) بمعامل $\mu$. وبينما يتم ضبط معامل الجزاء تقليدياً لضمان الجدوى (أي إيجاد حل صالح)، فإن تأثيره المحدد على عدالة أخذ العينات بين الحالات الأرضية المتدهورة لا يزال غير مفهوم بشكل جيد.

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

2. المنهجية

تستخدم الدراسة نهجاً متعدد الأوجه يجمع بين المحاكاة النظرية والتحقق التجريبي:

• صياغة الهاميلتوني:
  يتم تعيين المسألة لـ "هاميلتوني إيسينج" (Ising Hamiltonian). يُعرف هاميلتوني المسألة الإجمالي بـ:
  $$H_p = H_{obj} + \mu H_{const}$$
  حيث يمثل $H_{obj}$ وزن القطع، و $H_{const} = (\sum \sigma_i^z)^2$ يفرض قيد التقسيم المتساوي. يتم تفكيك معامل الجزاء إلى $\mu = \mu_{opt} + \mu_+$، حيث $\mu_{opt}$ هو الحد الأدنى المطلوب للجدوى، و $\mu_+$ هو الجزاء الإضافي.

• المحاكاة العددية:

  • تم حل معادلة شرودنجر المعتمدة على الزمن باستخدام QuTiP لمحاكاة ديناميكيات التلدين الكمي.
  • تحليل الحالة الواحدة: تم تحليل حالة محددة لـ 6 سبينات (spins) من مسألة GBP لتوصيف العلاقة بين وقت التلدين ($T$)، ومعامل الجزاء ($\mu_+$)، وتوزيع أخذ العينات.
  • تحليل القياس (Scaling Analysis): تم إنشاء 100 حالة عشوائية لأحجام أنظمة $N \in \{4, 6, 8, 10, 12\}$. استخدمت الدراسة معامل جزاء معيارياً $\lambda \in [0, 1]$ لتغطية النطاق الكامل لـ $\mu$.
  • المقياس: تم قياس عدالة أخذ العينات باستخدام إنتروبيا شانون ($S$) لتوزيع احتمالية الحالة الأرضية. تشير $S = \log_2 D$ (حيث $D$ هو درجة التدهور) إلى العدالة المثالية؛ بينما تشير القيم الأقل إلى وجود انحياز.

• التحقق التجريبي:

  • أُجريت التجارب على نظام D-Wave Advantage2 System 1.13.
  • شملت التقنيات المستخدمة التلدين المتوازي (باستخدام 400 تضمين متميز) وتحويل عكس السبين (SRT) (10 تحويلات غاوس) للتخفيف من ضوضاء الأجهزة والأخطاء المنهجية.
  • تم ضبط وقت التلدين عند 200 ميكروثانية (10 أضعاف الافتراضي) للاقتراب من النظام الأديباتي.

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

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

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

• سلوك الحالة الواحدة:

  • بالنسبة لحالة 6 سبينات ذات 4 حالات أرضية متدهورة، أدى زيادة $\mu_+$ إلى كبح انحياز أخذ العينات.
  • عند أوقات التلدين القصيرة ($T \lesssim 10^3$)، أدت زيادة $\mu_+$ إلى زيادة الإنتروبيا (العدالة) ولكنها قللت من الاحتمالية الإجمالية لإيجاد أي حالة أرضية ($P_{GS}$).
  • عند أوقات التلدين الطويلة ($T \approx 10^4$)، ظلت $P_{GS}$ قريبة من الوحدة لجميع قيم $\mu_+$، وأدت زيادة $\mu_+$ إلى زيادة الإنتروبيا بشكل رتيب، مما قضى فعلياً على المقايضة.

• نتائج أجهزة D-Wave:

  • لوحظ أخذ عينات غير عادل في نظام D-Wave، وإن كان بمقدار أقل مما هو موجود في المحاكاة (ربما بسبب الاسترخاء الحراري والضوضاء).
  • زادت الإنتروبيا في البداية قليلاً مع $\mu_+$، ثم انخفضت عند $\mu_+ \approx 0.4$، ثم زادت مرة أخرى. والأهم من ذلك، أن الحالات التي كانت منحازة في المحاكاة ظلت هي الحالات المنحازة في الأجهزة، مما يؤكد الطبيعة الهيكلية للانحياز.
  • مع زيادة $\mu_+$، أصبح توزيع أخذ العينات أقرب إلى التوزيع الموحد، حتى مع تناقص $P_{GS}$.

• تحليل القياس (N = 4 إلى 12):

  • بالنسبة لـ $N=4$، أظهرت جميع الحالات أخذ عينات عادلاً بغض النظر عن $\lambda$.
  • بالنسبة للقيم الأكبر من $N$، أصبح السلوك معقداً، حيث أظهرت بعض الحالات تغيرات غير رتيبة في الإنتروبيا.
  • معدل الزيادة الرتيبة: يوضح الجدول I نسبة الحالات التي زادت فيها الإنتروبيا بشكل رتيب مع معامل الجزاء:
    • $N=4$: 100%
    • $N=6$: 91%
    • $N=8$: 74%
    • $N=10$: 72%
    • $N=12$: 74%
  • يستقر المعدل حول 70-75% للأنظمة الأكبر، مما يشير إلى أن زيادة معامل الجزاء يحسن العدالة في معظم الحالات، حتى لو لم يكن ذلك عالمياً.

5. الأهمية والتوجهات المستقبلية

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

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