Simulated Bifurcation Quantum Annealing

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

تعد مشكلات التحسين التوليفي، التي غالبًا ما تُصاغ في شكل إيجاد الحالة الأرضية لهاملتونياني (Hamiltonian) لنموذج "إيزينج" للسبين الزجاجي (Ising spin-glass)، منتشرة في كل مكان في العلوم والصناعة. وبينما توفر التلدين الكمومي (Quantum Annealing - QA) نهجًا قائمًا على الأجهزة باستخدام النفق الكمومي والتراكب، تواجه الأجهزة الحالية قيودًا مثل محدودية اتصال الكيوبتات، والضجيج، وأوقات التماسك المحدودة، مما يمنع تقديم إثبات قاطع للتسارع الكمومي.

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

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

2. المنهجية: التلدين الكمومي بالتفرع المحاكي (SBQA)

يقدم المؤلفون SBQA، وهي خوارটি خوارزمية تحسين مستوحاة من الكم، توسع نظام SBM القياسي عن طريق دمج التفاعلات بين النسخ المتعددة (inter-replica interactions).

• الأساس النظري:

  • أساس SBM: تعمل SBM القياسية على تطوير نظام من $N$ من الجسيمات التي يحكمها هاملتونياني يعتمد على الزمن. وهي تستخدم الديناميكيات الفوضوية والتفرعات لاستكشاف سطح الطاقة.
  • الإلهام الكمومي: يستمد المؤلفون أفكارهم من التلدين الكمومي المحاكي في الزمن المنفصل (DTSQA)، والمستمد من صياغة مونت كارلو لمسار نموذج "إيزينج" للمجال المستعرض. في DTSQA، يتم رسم خريطة لنظام كمومي إلى نظام كلاسيكي ذي $d+1$ من الأبعاد عبر تفكيك سوزوكي-تروتر (Suzuki–Trotter decomposition)، حيث يمثل البعد الإضافي الزمن التخيلي (النسخ).
  • الابتكار الرئيسي: تقدم SBQA اقترانًا فعالًا بين النسخ المستقلة (المسارات) لنظام SBM. يعمل هذا الاقتران كبديل كلاسيكي لـ النفق الكمومي، مما يسمح للنظام بالهروب من النهايات الصغرى المحلية بشكل أكثر فعالية من SBM القياسية.

• الصياغة الرياضية:

  • يتضمن هاملتونياني SBQA لـ $N$ من الجسيمات و $R$ من النسخ حد اقتران بين النسخ $J_\perp(t)$:
    $$H = \sum_{i=1}^N \sum_{k=1}^R \left[ \frac{a_0}{2R} p_{i,k}^2 + \frac{a_0 - a(t)}{2R} q_{i,k}^2 - \frac{c_0}{R} \left( h_i q_{i,k} + \frac{1}{2} \sum_{j=1}^N J_{ij} q_{i,k} q_{j,k} \right) - J_\perp(t) q_{i,k} q_{i,k+1} \right]$$
  • قوة الاقتران $J_\perp(t)$ تعتمد على الزمن ومستمدة من المجال المستعرض $\Gamma_x(t)$ ودرجة الحرارة العكسية $\beta$:
    $$J_\perp(t) = -\frac{1}{2\beta} \ln \tanh \left( \frac{\beta \Gamma_x(t)}{R} \right)$$
  • يتطور النظام وفقًا لمعادلات حركة معدلة حيث يتضمن تحديث الزخم حدًا يربط النسخ المتجاورة ($q_{i,k-1} + q_{i,k+1}$).

• المعلمات الفائقة والضبط:

  • تم تقديم معلمتين فائقتين جديدتين: $\beta$ (درجة الحرارة العكسية، التي تتحكم في قوة الاقتران) و $\alpha$ (أس جدول التلدين).
  • يقترح المؤلفون استراتيجية ضبط تلقائي خفيفة الوزن: بدلاً من التحسين المكلف الخاص بكل حالة، يقومون بتشغيل تكرارات متعددة بالتوازي (وهو أمر ممكن على وحدات معالجة الرسومات الحديثة)، مع أخذ عينات عشوائية لـ $\beta \in [0.5, 1.5]$ و $\alpha \in [0.5, 1.0]$، واختيار أفضل حل. يضمن هذا الاستقرار دون عبء إضافي كبير.

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

1. اشتقاق الخوارزمية: اشتقاق معادلات الحركة لـ SBQA، مما يوضح أن إضافة الاقتران بين النسخ يؤدي إلى حد أدنى من العبء على الأداء ولكنه يغير الديناميكيات بشكل كبير.
2. استراتيجية الضبط التلقائي: طريقة عملية ومنخفضة التكلفة لاختيار المعلمات الفائقة تتجنب الحاجة إلى ضبط دقيق خاص بكل حالة، مما يجعل الخوارزمية قوية وسهلة النشر.
3. التقييم المرجعي الشامل: تقييم صارم عبر فئتين متميزتين:
   • التحجيم التقاربي واسع النطاق: الاختبار على مشكلات تصل فيها المتغيرات إلى $N \approx 7.2 \times 10^5$ (رسوم Zephyr، ورسوم QAC المنطقية، وزرع البلاطات/tile-planting).
   • الحالات ذات الصلة بالأجهزة: الاختبار على مشكلات أصلية لتوبولوجيا الأجهزة الكمومية الحالية (D-Wave Pegasus، و IBM Heavy-Hex).

4. النتائج

تستخدم الدراسة مقياس الوقت للوصول إلى إبسيلون ($TT_\epsilon$)، والذي يقيس الوقت المطلوب لإيجاد حل ضمن فجوة مثالية محددة ($\epsilon$) مع احتمال مستهدف (عادة 99%).

• التحجيم التقاربي (المشكلات واسعة النطاق):

  • رسوم Zephyr: تتفوق SBQA بشكل منهجي على SBM في رسوم Zephyr المتفرقة والكبيرة جدًا ($N > 10^4$). وتتسع فجوة الأداء مع زيادة حجم المشكلة وانخفاض كثافتها. تظهر SBQA أسًا تقاربيًا ($\gamma$) أفضل من SBM.
  • تصحيح التلدين الكمومي (QAC): في رسوم QAC المنطقية (حالات Sidon28)، تتفوق SBQA على SBM في أحجام الأنظمة الكبيرة ($L \ge 80$)، خاصة بالنسبة لأهداف المثالية الصارمة. يشير هذا إلى أن SBQA ترفع سقف المعايير الكلاسيكية مقابل التلدين الكمومي المعزز بـ QAC.
  • زرع البلاطات (2D/3D):
    • 2D (شبكة مربعة): تظهر SBQA ميزة هائلة على SBM، التي تعاني بشكل كبير في هذه الحالات المتفرقة والوعرة. تحافظ SBQA على تحجيم حدودي (polynomial) بينما تقترب SBM من التحجيم الأسي (exponential).
    • 3D (شبكة مكعبة): تؤدي كلتا الخوارزميتين بشكل جيد، لكن SBQA لا تزال تقدم أسًا تقاربيًا أفضل قليلاً.

• الاختبارات المرجعية ذات الصلة بالأجهزة:

  • السبينات الزجاجية ثلاثية الأبعاد (D-Wave Pegasus): تضاهي SBQA أو تتفوق على SBM عبر مختلف أحجام الشبكات. وهي تتفوق بشكل كبير على DTSQA (وهي محلل مستوحى من الكم متخصص) في معظم الحالات، باستثناء أكبر الحالات ذات الأهداف الأكثر صرامة، حيث تنجح DTSQA ولكن بتكلفة زمن تشغيل أعلى بكثير. كما تتفوق SBQA أيضًا على ملدن D-Wave Advantage 4.1 في هذه الحالات الوعرة المحددة.
  • التحسين الثنائي عالي الرتبة (HUBO على IBM Heavy-Hex): في التوبولوجيات المعقدة المستمدة من معالجات IBM، تحافظ SBQA على تعدد استخداماتها. فهي تضاهي SBM في الأهداف "السهلة" وتتفوق عليها بشكل كبير في الأهداف "الصعبة" للأحجام الكبيرة. ومن الجدير بالذكر أن DTSQA تفشل في حل الأهداف الأصعب على هذه التوبولوجيات المعقدة.

5. الأهمية والخاتمة

• خوارزمية استدلالية عملية مستوحاة من الكم: توفر SBQA أداة تحسين كلاسيكية قوية تكون فعالة بشكل خاص في الأنظمة المتفرقة والوعرة حيث تفشل SBM القياسية. فهي تحتفظ بالتوازي والكفاءة الخاص بـ SBM مع إضافة قدرة "النفق" عبر اقتران النسخ.
• رفع المعيار الكلاسيكي: تشير النتائج إلى أن التحسينات الخوارزمية المتواضعة (بضع في المائة في الأداء) يمكن أن تكون حاسمة. تضع SBQA معيارًا كلاسيكيًا أقوى لتقييم التفوق الكمومي. في الأنظمة التي تعتمد فيها المقارنات بين الكم والكلاسيك على هوامش ضيقة، تثبت SBQA أن الطرق الكلاسيكية يمكنها سد الفجوة أو حتى تجاوز أداء الأجهزة الكمومية الحالية في فئات مشكلات معينة.
• تعدد الاستخدامات: على عكس الحلول المتخصصة التي قد يتدهور أداؤها في توبولوجيات معينة (مثل DTSQA في رسوم heavy-hex)، تظل SBQA فعالة عبر مجموعات متنوعة من المشكلات، من الشبكات المتفرقة إلى التوبولوجيات المعقدة المرتبطة بالأجهزة.

باختصار، تثبت الورقة أن دمج التفاعلات بين النسخ المستوحاة من الكم في ديناميكيات التفرع الكلاسيكية يخلق خوارزمية تحسين متفوقة للمشكلات التوليفية الصعبة، مما يوفر بديلًا عمليًا للأجهزة الكمومية الحالية ومعيارًا صارمًا للمقارنات المستقبلية بين الكم والكلاسيك.