A Spectral Gap Informed Parameter Schedule for QAOA

ملخص تقني: جدولة المعاملات المستندة إلى الفجوة الطيفية لخوارزمية QAOA

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

تعد خوارزمية التحسين التقريبي الكمي (QAOA) خوارزمية تباينية كمية رائدة لحل مشكلات التحسين التوليفي. ومع ذلك، يعتمد أداؤها بشكل كبير على اختيار المعاملات التباينية ($\beta, \gamma$). وغالباً ما يكون العثور على هذه المعاملات المثلى مهمة صعبة من فئة (NP-hard) بسبب وجود النهايات الصغرى المحلية والسهول المسطحة العقم (Barren Plateaus).

لقد قدمت المحاولات الحالية لـ "إلغاء التباين" في خوارزمية QAOA —أي تقليل الحاجة إلى التحسين— ما يسمى بـ خوارزمية QAOA ذات المنحدر الخطي (LR–QAOA). تستخدم LR–QAOA جداول زمنية خطية للمعاملات مستوحاة من الخوارزمية الكمية الأديباتيكية (QAA). ومع ذلك، من المعروف أن الجداول الخطية تكون غير مثالية للعديد من المشكلات (مثل بحث غروفر) لأنها لا تأخذ في الاعتبار الفجوة الطيفية —وهي الحد الأدنى لفرق الطاقة بين الحالة الأرضية وأول حالة مثارة. في التطور الأديباتيكي، يجب أن يتطور النظام ببطء أكبر عندما تكون الفجوة الطيفية صغيرة لتجنب الانتقالات الديباتيكية (الأخطاء).

2. المنهجية

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

• بناء الهاميلتوني الأديباتيكي: يحدد المؤلفون هاميلتونياً أديباتيكياً $H_{Ad} = (1-s)H_{mix} + sH_C$، حيث $H_{mix}$ هو هاميلتوني الخلاط (Mixer) الخاص بـ QAOA، و $H_C$ هو هاميلتوني التكلفة. وهذا يختلف عن QAA القياسية باستخدام الخلاط كنقطة انطلاق.
• اشتقاق الجدول الزمني: يتم حساب الجدول الزمني $f(s)$ باستخدام تكامل تراكمي موزون للفجوة الطيفية $g(s)$:
  $$f(s) = \frac{\int_{0}^{s} [g(s') - g_{min}]^\kappa ds'}{\int_{0}^{1} [g(s') - g_{min}]^\kappa ds'}$$
  حيث $\kappa$ هو أس قابل للضبط (تم ضبطه عند 2) يعمل على تركيز سرعة التطور حول الحد الأدنى للفجوة ($g_{min}$).
• القابلية للتوسع عبر الاستقراء: بما أن حساب الطيف الدقيق للأنظمة الكبيرة مكلف حاسوبياً، فقد طور المؤلفون تقنية استقراء. يقومون بحساب الفجوة لأحجام مشكلات صغيرة ويستخدمون تلك الاتجاهات لتقدير الجدول الزمني للأحجام الأكبر بكثير.
• مقاييس التقييم: يتم قياس الأداء عبر احتمالية الحل الأمثل ($P_s$) عند عمق ثابت $p$، و العمق المطلوب $p$ للوصج إلى عتبة نجاح محددة.

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

• تقديم SGIR–QAOA: طريقة جديدة لجدولة المعاملات تستخدم الخصائص الفيزيائية (الفجوة الطيفية) للمشكلة لتوجيه الخوارزمية.
• إثبات التفوق على LR–QAOA: إثبات أن الجداول الزمنية المستندة إلى الطيف تتفوق على المنحدرات الخطية في كل من احتمالية النجاح وكفاءة عمق الدائرة.
• إطار عمل القابلية للتوسع: توفير طريقة لتطبيق هذه الجداول الزمنية المستنيرة على مشكلات واسعة النطاق حيث يكون حساب الفجوة الدقيقة مستحيلاً.
• تحليل المتانة تجاه الضجيج: إظهار أن الطريقة تحافظ على مزاياها حتى في ظل وجود ضجيج إزالة الاستقطاب (Depolarizing noise).

4. النتائج

تحقق المؤلفون من صحة طريقتهم باستخدام معيارين أساسيين:

• مشكلة بحث غروفر (Grover’s Search Problem):
  • حققت SGIR–QAOA احتمالات أعلى للحل الأمثل ($P_s$) عند عمق ثابت مقارنة بـ LR–QAOA والتخمينات العشوائية للمعاملات.
  • والأهم من ذلك، تطلبت SGIR–QAOA عمق دائرة $p$ أقل بكثير للوصول إلى عتبة نجاح قدرها 0.1 مع زيادة حجم المشكلة $n$.
• مشكلة المجموعة المستقلة القصوى (Maximum Independent Set - MIS):
  • في الرسوم البيانية المتفرقة ثلاثية الانتظام، أظهرت SGIR–QAOA توسعاً أسياً متفوقاً لاحتمالية النجاح ($2^{-(0.41 \pm 0.02)n}$) مقارنة بـ LR–QAOA التي سجلت ($2^{-(0.56 \pm 0.02)n}$).
  • نجحت تقنية الاستقراء في الحفاظ على هذه الميزة للأحجام الأكبر من المشكلات حيث لا يمكن حساب الفجوة الدقيقة.
• أداء الضجيج: في ظل ضجيج إزالة الاستقطاب، وصلت SGIR–QAOA إلى احتمالات نجاح ذروية أعلى عند أعماق أقل من LR–QAOA الخالية من الضجيج، مما يشير إلى أنها أكثر عملية لأجهزة عصر الـ NISQ.

5. الأهمية

ينقل هذا العمل نموذج اختيار معاملات QAOA من التحسين التجريبي (Heuristic Optimization) إلى الجدولة المستندة إلى الفيزياء. من خلال دمج الفجوة الطيفية، تقلل SGIR–QAOA من خطر الانتقالات الديباتيكية، مما يسمح بمعدلات نجاح أعلى باستخدام دوائر أقل عمقاً. وهذا أمر بالغ الأهمية لعصر NISQ، حيث يكون عمق الدائرة محدوداً بشدة بسبب فك الترابط (Decoherence) والضجيج. إن القدرة على استقراء هذه الجداول الزمنية تجعل من هذه الطريقة مرشحاً قابلاً للتطبيق لتوسيع نطاق التحسين الكمي إلى مشكلات واقعية أكبر وأكثر تعقيداً.