ملخص تقني: خوارزمية هجينة للتقسية الكلاسيكية-الكمومية لمسألة البائع المتجول (TSP)

بيان المشكلة

تعد مسألة البائع المتجول (TSP) مسألة تحسين أساسية من فئة المسائل الصعبة حاسوبياً (NP-hard)، وتتطلب تحديد أقصر دورة هاميلتونية في رسم بياني كامل الأوزان. وبينما يمكن للمحللات الكلاسيكية الدقيقة (مثل Concorde) التعامل مع الحالات الكبيرة، إلا أنها غالباً ما تواجه صعوبات في التوسع ضمن زمن حدودي. وفي المقابل، تقدم النهج الكمومية، وخاصة التقسية الكمومية (QA)، بديلاً واعداً لآلية الضجيج الحراري للهروب من النهايات الصغرى المحلية. ومع ذلك، تواجه الأجهزة الحالية ذات المقياس المتوسط المشوبة بالضجيج (NISQ)، مثل أجهزة D-Wave annealers، قيوداً فيزيائية شديدة تتعلق بعدد الكيوبتات والاتصال الطوبولوجي. تمنع هذه القيود النمذجة المباشرة لحالات TSP واسعة النطاق، والتي تتطلب اتصالاً كثيفاً، على وحدات المعالجة الكمومية (QPUs) الحالية.

المنهجية

يقترح المؤلفون خوارزمية هجينة كلاسيكية-كمومية تسد الفجوة بين حالات TSP واسعة النطاق وقدرات الأجهزة الكمومية الحالية. يدمج هذا النهج بين منهجيتين تأسيسيتين: محاكاة مونت كارلو بالتكامل المساري (PIMC) للتقسية الكمومية، واستراتيجية استخراج subQUBO.

1. انكماش الرسم البياني عبر تردد الحواف

الابتكار الجوهية هو تقنية انكماش الرسم البياني التي تقلل من أبعاد المسألة الأصلية.

• توليد المجمع (Pool Generation): تبدأ الخوارهازمية بتوليد مجمع من الحلول المرشحة ($P$) باستخدام تبديلات عشوائية يتم تنقيحها بواسطة التقسية المحاكية (SA) مع حركات 2-opt.
• تحديد العمود الفقري الواثق: بدلاً من تحليل المجمع بأكمله، تقوم الخوارزمية بأخذ عينة من مجموعة فرعية ($S$) لحساب تكرار الحواف التي تظهر عبر الحلول. تُحدد الحواف التي تظهر بتردد أعلى من عتبة الثقة ($\tau$) كـ "عمود فقري واثق".
• الانكماش: يتم تثبيت هذه الحواف عالية التردد، ويتم دمج العقد المتصلة في "عقد فائقة" (super-nodes). يحول هذا الرسم البياني الأصلي $G$ إلى حالة فرعية أصغر بكثير من مسألة TSP ($G_{sub}$). يتم إعادة حساب مصفوفة المسافات للمسألة الفرعية لمراعاة الدمج المنطقي للمسارات (رأس وذيل العقد الفائقة).

2. حلقة التحسين الهجينة

تعمل الخوارزمية في حلقة تكرارية:

1. التنقيح: تقوم الاستدلالات الكلاسيكية بتنقيح مجمع الحلول لتحسين موثوقية تردد الحواف.
2. أخذ العينات والانكماش: يتم أخذ عينة من الحلول لتحديد الحواف الثابتة وانكماش الرسم البيائي.
3. الحل الكمومي: يتم حل مسألة TSP الفرعية المختزلة باستخدام محلل كمومي. في تجارب الورقة، تم تنفيذ ذلك عبر:
   • المحاكاة الكلاسيكية: محاكاة مونت كارلو بالتكامل المساري (PIMC) بناءً على مخطط Martoňák et al.، والذي يربط TSP بنظام يشبه نموذج Ising مقيد باستخدام حركات 2-opt كعوامل طاقة حركية.
   • التنفيذ على الأجهزة: التنفيذ المباشر على نظام D-Wave Advantage_system 4.1 QPU.
4. التوسيع والتحديث: يتم توسيع الحل من المسألة الفرعية وإعادته إلى الرسم البياني الأصلي عن طريق إعادة إدراج الحواف الثابتة. تُضاف الدورة الجديدة إلى المجمع، ويتم تحديث أفضل دورة عالمية إذا تم العثốt على تحسن.
5. الإنهاء: تتكرر العملية حتى تؤدي $K$ من التكرارات المتتالية إلى عدم وجود تحسن.

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

• إطار عمل هجين قابل للتوسع: تقدم الورقة طريقة لتجاوز قيود الكيوبت والاتصال لأجهزة NISQ من خلال تقليل حالات TSP الكبيرة إلى أحجام يمكن إدارتها بواسطة الأجهزة الحالية (على سبيل المثال، تقليل حالة تضم 1,002 مدينة إلى حوالي 185 عقدة).
• الدمج بين PIMC و SubQUBO: يجمع العمل بين الوعد النظري لنفق PIMC الكمومي (الفعال في التنقل عبر مشاهد الطاقة المعقدة) والضرورة العملية لاستخراج subQUBO (تقسيم المسألة التكراري).
• التحقق التجريبي على الأجهزة: نجح المؤلفون في اختبار الخوارزمية على جهاز D-Wave كمومي، مما أظهر أن استراتيجية الانكماش تسمح بالدمج المباشر لمسائل TSP الفرعية التي كانت ستكون غير قابلة للحل لولا ذلك.

النتائج التجريبية

تم تقييم الخوارزمية على حالات TSPLIB تتراوح من 14 إلى 11,849 مدينة.

• حساسية المعلمات:
  • العتبة ($\tau$): يؤدي خفض $\tau$ إلى زيادة الضغط (تقليل حجم المسألة) ولكنه يخاطر بتثبيت حواف دون المستوى الأمثل، مما يزيد من فجوة الأمثلية. قدمت العتبة $\tau=0.75$ توازناً ملائماً للحالات المتوسطة.
  • حجم المجمع ($N_I$) وحجم العينة ($N_S$): حقق مجمع بحجم 500 مع حجم عينة 250 (50%) أفضل النتائج للحالات المتوسطة إلى الكبيرة، مما يشير إلى أن أخذ العينات العشوائي يمنع اختيار الحواف من أن يصبح حتمياً بشكل مفرط.
• الأداء مقابل المراجع الكلاسيكية:
  • بالنسبة للحالات الصغيرة (مثل burma14، ulysses22)، وجدت الخوارزمية الحل الأمثل العالمي (فجوة 0%).
  • بالنسبة للحالات الكبيرة (مثل pr2392)، حافظت الخوارزمية على متوسط فجوة أمثلية أقل من 4%، متفوقة على Google's OR-Tools في عدة حالات (على سبيل المثال، حققت rl11849 فجوة قدرها 7.36% مقابل 14.58% لـ OR-Tools).
• نتائج أجهزة D-Wave:
  • عند تشغيلها على جهاز D-Wave QPU، حقق النهج الهجين فجوات أمثلية أفضل بكثير من محلل BQM الهجين الخاص بـ D-Wave. على سبيل المثال، في حالة ulysses22، حققت الطريقة المقترحة فجوة قدرها 2.57% مقارلة بـ 16.88% للمحلل الهجين، وذلك من خلال حل مسائل فرعية تتكون من حوالي 5 عقد فقط.
• الاختناقات:
  • تم تحديد مرحلة محاكاة PIMC كعائق حسابي رئيسي في المحاكاة الكلاسيكية.
  • بالنسبة للحالات الكبيرة جداً (مثل rl11849)، أصبح العبء الكلاسيكي (تهيئة المجمع والتنقيح) مهيمناً، حيث شكل حوالي 70% من وقت التشغيل، مما يشير إلى أن فوائد التسريع الكمومي يتم تحييدها حالياً بالتكاليف المسبقة الكلاسيكية في المقاييس القصوى.

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

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

1. الجدوى: يمكن تقليص حالات TSP الكبيرة إلى مقياس مناسب للدمج في أجهزة التقسية NISQ دون فقدان السلامة الهيكلية المطلوبة للحلول عالية الجودة.
2. إمكانية التفوق الكمومي: بينما محاكاة PIMC الحالية هي كلاسيكية، فإن الإطار مصمم ليكون قابلاً للتكيف مباشرة مع الأجهزة الكمومية. تشير النتائج إلى أنه إذا تم تنفيذ خطوة PIMC على محلل كمومي، فيمكن تقليل التكلفة الحسابية بشكل كبير، مما قد يوفر تسارعاً أسياً لعملية التحسين.
3. المتانة: الطريقة متينة عبر أحجام الحالات المتفاوتة، حيث تحقق حلولاً دقيقة للمسائل الصغيرة وتحافظ على فجوات أمثلية منخفضة للمسائل واسعة النطاق حيث تعاني الاستدلالات الكلاسيكية.

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