Feedback-based quantum optimization and its classical counterpart: quantum advantage and the power of classical algorithms

ملخص تقني: التحسين الكمي القائم على التغذية الراجعة ونظيره الكلاسيكي

بيان المشكلة
تُصنف مشكلات التحسين التوليفي، المنتشرة في مجالات اللوجستيات وعلوم المواد والتمويل، عموماً كمسائل صعبة حسابياً من فئة (NP-hard)، مما يتطلب تكاليف حوسبة أسية لحلها بدقة. وبينما توجد خوارزميات كمية وكلاسيكية متنوعة، بما في ذلك الملدنات الكمية والخوارزميات الكمية المتغيرة، تبرز الحاجة إلى مقارنة منهجية بين النهج الكمية ونظائرها الكلاسيكية لتقييم إمكانية التفوق الكمي. وتحديداً، تستخدم خوارزمية (FALQON) - وهي الخوارزمية القائمة على التغذية الراجعة للتحسين الكمي - نظرية التحكم بـ "ليابونوف" (Lyapunov control theory) لتقليل دالة التكلفة بشكل تكراري دون الحاجة إلى حلقات تحسين كلاسيكية. ومع ذلك، فإن التكلفة الحسابية للتغذية الراجعة التكرارية في الأنظمة الكمية تعتبر باهظة. وفي المقابل، تقدم الخوارزميات الكلاسيكية المستوحاة من (FALQON)، مثل (CACAO) - وهي الخوارزمية الكلاسيكية للمساعدة في التحسين عبر مضادات التباين (Counterdiabaticity) - سرعة تقارب أكبر، ولكنها قد تفتقر إلى جودة الحل. علاوة على ذلك، غالباً ما يتم حل مشكلات التحسين الثنائي غير المقيد من الرتب العليا (HUBO) بشكل غير فعال عبر اختزالها إلى صيغ التحسين الثنائي غير المقيد التربيعي (QUBO)، مما يؤدي إلى زيادة حجم المشكلة. وهناك فجوة في فهم النظراء الكلاسيكيين الدقيقين لخوارزميات التحسين الكمي القائمة على التغذية الراجعة وقدرتهم على التعامل مع مشكلات (HUBO) بشكل مباشر.

المنهجية
يضع المؤلفون إطاراً نظرياً قائماً على التناظر الكمي-الكلاسيكي لأنظمة الغزل (spin systems). ومن خلال استبدال مصفوفات باولي $\{\hat{X}_i, \hat{Y}_i, \hat{Z}_i\}$ بمتجهات غزل كلاسيكية وحدة $\{m^X_i, m^Y_i, m^Z_i\}$ واستخدام المعادلات الكانونية للحركة، قاموا باشتقاق نظراء كلاسيكيين دقيقين لخوارزميات التحسين الكمي القائمة على التغذية الراجعة.

1. الاشتقاق النظري:

   • الجانب الكمي: تستعرض الورقة خوارزمية (FALQON) ومتغيرها غير المتجانس (iFALQON)، حيث يتم تحديد معاملات التحكم من خلال القيمة المتوقعة للمبدلات (commutators) بين هاملتوني المشكلة وحزم القيادة.
   • الجانب الكلاسيكي: اشتق المؤلفون (CC-FALQON) و(CC-iFALQON) كنظراء كلاسيكيين دقيقين. وخلافاً للنسخة الكمية، لا تتطلب هذه الخوارزميات الكلاسيكية حلقة تغذية راجعة تكرارية؛ حيث تُحسب معاملات التحكم مباشرة من الحالة اللحظية للغزل الكلاسيكي.
   • التوسع في الرتب العليا: تم توسيع الإطار لتطوير (HOT-CACAO) - وهي خوارما (CACAO) ذات الرتب العليا - والتي تقدم حدوداً ثانوية من مضادات التباين (second-order counterdiabatic terms)، و(HOT-CACAO+) التي تدمج كلاً من هاملتوني المشكلة وجميع حدود مضادات التباين التي تمت مناقشتها (من الدرجة الأولى والثانية).

2. الاختبار المعياري:

   • النطاق الصغير: أجرى المؤلفون اختبارات معيارية على نماذج $N=12$ لمشكلة (2-SAT) (المصاغة كـ QUBO) لمقارنة جودة الحل وسرعة التقارب للخوارزميات الكمية (FALQON, iFALQON) مقابل نظائرها الكلاسيكية (CC-FALQON, CC-iFALQEM) والمتغيرات الكلاسيكية الأخرى (CACAO, HOT-CACAO, HOT-CACAO+).
   • النطاق الكبير: تقيم الدراسة قابلية التوسع للخوارزميات الكلاسيكية على نماذج $N=10,000$ لمشكلة (3-SAT) (المصاغة مباشرة كـ HUBO). وتشمل الخوارزميات المختبرة (CC-iFALQON, CACAO, HOT-CACAO, HOT-CACAO+).
   • تحليل الديناميكيات: تحلل الورقة قوة معاملات التحكم وديناميكيات الطاقة لفهم سلوك التقارب ودور اللا-محلية (nonlocality) مقابل المحلية (locality).

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

• النظراء الكلاسيكيون الدقيقون: تقدم الورقة (CC-FALQON) و(CC-iFALQON)، مما يوفر أول صياغات كلاسيكية دقيقة لخوارزميات التحسين الكمي القائمة على التغذية الراجعة والمشتقة من تناظر أنظمة الغزل.
• النظرية الكلاسيكية ذات الرتب العليا: طورت (HOT-CACAO) و(HOT-CACAO+)، مما وسع خوارزمية (CACAO) بحدود مضادات التباية من الرتب العليا والدمج الصريح لهاملتوني المشكلة.
• الحل المباشر لـ HUBO: أثبتت الخوارزميات الكلاسيكية المقترحة قدرتها على حل مشكلات (HUBO) مباشرة دون الحاجة إلى طرق تقليل الرتب (التي عادة ما تزيد من عدد المتغيرات المساعدة وتضعف الأداء).
• الديناميكيات الكمية مقابل الكلاسيكية: توضح الدراسة السلوكيات المتباينة للديناميكيات الكمية والكلاسيكية فيما يتعلق بالقيادة غير المتجانسة، وتعزو الاختلافات إلى الطبيعة العالمية للديناميكيات الكمية مقابل الطبيعة المحلية للتحديثات الكلاسيكية.

النتائج

• جودة الحل مقابل سرعة التقارب:
  • التفوق الكمي في الجودة: تظهر (FALQON) جودة حل فائقة (كثافة طاقة نهائية أقل) مقارنة بنظيرها الكلاسيكي (CC-FALQON) والخوارزميات الكلاسيكية الأخرى، مما يشير إلى تفوق كمي محتمل في استكشاف مشهد التحسين العالمي.
  • التفوق الكلاسيكي في السرعة: تُظهر الخوارزميات الكلاسيكية عموماً سرعة تقارب أكبر بكثير من الخوارزميات الكمية. ومن الجدير بالذكر أن (CC-FALQON) تظهر تقارباً بطيئاً جداً، بينما تتقارب (HOT-CACAO) و(HOT-CACAO+) بسرعة.
• تأثيرات عدم التجانس:
  • في الإعداد الكمي، تتفوق القيادة المتجانسة (FALQON) على القيادة غير المتجانسة (iFALQON).
  • في الإعداد الكلاسيكي، ينعكس الاتجاه: تحقق القيادة غير المتجانسة (CC-iFALQON) كثافة طاقة أقل من القيادة المتجانسة (CC-FALQON). ويُعزى ذلك إلى عدم التطابق بين الديناميكيات الكمية العالمية والمعاملات المحلية، مقابل التوافق بين القيادة غير المتجانسة والتحديثات الكلاسيكية المحلية.
• القابلية للتوسع وأداء HUBO:
  • في نماذج (3-SAT) واسعة النطاق ($N=10,000$)، تحقق (HOT-CACAO+) أدنى كثافة طاقة نهائية بين جميع الطرق المختبرة.
  • بينما تتقارب (HOT-CACAO+) بشكل أبطأ من (HOT-C_A_C_O)، إلا أنها تصل إلى حالات طاقة أدنى، مما يشير إلى وجود مقايضة بين سرعة التقارب وجودة الحل.
  • يكشف تحليل القابلية للتوسع أن (HOT-CACAO+) هي الطريقة الوحيدة التي تحسن كثافة الطاقة باستمرار مع زيادة حجم النظام، بينما تستقر الطرق الأخرى. وهذا يسلط الضوء على ضرورة الجمع بين حدود مضادات التباين من الرتب العليا وهاملتوني المشكلة للتحسين عالي الرتب واسع النطاق.

الأهمية والادعاءات
تدعي الورقة أن نتائجها تسلط الضوء على الأدوار المتميزة لـ "الكمية" (quantumness) والنهج الكلاسيكي. إذ تُظهر خوارزمية (FALQON) - وهي خوارزمية تحسين كمي قائمة على التغذية الراجعة - إمكانية تحقيق حلول أعلى جودة من خلال الاستفادة من الارتباطات العالمية، بينما توفر الخوارزميات الكلاسيكية، لا سيما المعززة بحدود مضادات التباين من الرتب العليا (HOT-CACAO+)، تقارباً سريعاً وقابلية توسع فائقة لمشكلات (HUBO).

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