Neural-powered unit disk graph embedding: qubits connectivity for some QUBO problems

ملخص تقني: التضمين الرسومي لوحدات القرص عبر الشبكات العصبية لمشكلات QUBO

بيان المشكلة
تتناول هذه الورقة التحدي الحرج المتمثل في إسقاط مشكلات التحسين التربيعي الثنائي غير المقيد (QUBO) على محاكيات الكم القائمة على الذرات المتعادلة، وتحديداً تلك التي تستخدم ذرات ريدبرج (مثل نموذج Pasqal Chadoq2 الأولي). وخلافاً للحواسيب الكمومية القائمة على البوابات أو أجهزة التلدين ذات الطوبولوجيا الثابتة (مثل D-Wave)، تسمح أجهزة الذرات المتعادلة بوضع الكيوبتات في أماكن عشوائية في فضاء ثنائي أو ثلاثي الأبعاد. ومع ذلك، فإن التفاعلات الفيزيائية بين هذه الكيوبتات تخضع لتأثير حظر ريدبرج (Rydberg blockade): حيث لا يمكن استثارة الكيوبتات المتباعدة بمسافة أقل من "نصف قطر الحظر" ($r_b$) في آن واحد، مما يخلق نمط تجاور مكافئ لـ "رسم بياني لوحدة القرص" (Unit Disk Graph).

يكمن الصعوبة الجوهرية في مشكلة تضمين رسم وحدة القرص: إيجاد مجموعة من الإحداثيات الفيزيائية للكيوبتات بحيث:

1. تكون الكيوبتات المتجاورة في رسم QUBO المستهدف ضمن نصف قطر الحظر ($d_{ij} \leq \tilde{r}_b$).
2. الكيوبتات غير المتجاورة تكون خارج نصف قطر الحظر ($d_{hk} > \tilde{r}_b$).
3. تتسع جميع الكيوبتات ضمن قيود السجل الفيزيائي (على سبيل المثال، نطاق دائري بنصف قطر 50 ميكرومتر) وتحترم حدود الفصل الدنيا (على سبيل المثال، 4 ميكرومتر) لتجنب التداخل.

يشير المؤلفون إلى أنه بينما يعد حساب التجاور من الإحداثيات أمراً بسيطاً، فإن المسألة العكسية — وهي إيجاد إحداثيات تحقق مصفوفة تجاور معينة — هي مسألة صعبة (NP-hard). وغالباً ما تفشل الحلول الكلاسيكية في إيجاد تضمينات قابلة للتنفيذ للرسوم البيانية المعقدة أو واسعة النطاق ضمن أطر زمنية معقولة.

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

• البنية:
  • المدخلات/المخرجات: تأخذ الشبكة الإحداثيات الأولية (2D أو 3D) لـ $n$ من الكيوبتات $(x_i, y_i, z_i)$ وتخرج الإحداثيات المحولة $(x'_i, y'_i, z'_i)$.
  • مكون التشفير التلقائي (Autoencoder): تقوم شبكة متناظرة كاملة الاتصال (مدخل $\leftarrow$ طبقات خفية $\leftarrow$ مخرج) بتحويل الإحداثيات. تستخدم طبقة المخرجات دالة تنشيط tanh مُدرجة لتناسب النطاق الفيزيائي ($\pm 50$ ميكرومتر).
  • طبقة المسافة القابلة للتفاضل: تقوم طبقة متخصصة غير قابلة للتدريب (sparse layer) بحساب المسافة الإقليدية بين جميع أزواج الكيوبتات بناءً على الإحداثيات المحولة. وهذا يسمح للشبكة "برؤية" القيود الهندسية أثناء التدريب.
• دالة الخسارة (Loss Function): هدف التدريب ليس تقليل خطأ التنبؤ، بل تحقيق أربعة قيود فيزيائية في وقت واحد. دالة الخسارة هي مجموع أربعة حدود جزائية:
  1. الحدود العالمية: تعاقب الأزواج التي تتجاوز نصف قطر السجل الأقصى (100 ميكرومتر).
  2. الحد الأدنى للفصل: تعاقب الأزواج الأقرب من المسافة الفيزيائية الدنيا (4 ميكرومتر).
  3. قيد التجاور: تعاقب الكيوبتات المتجاورة التي تكون بعيدة جداً ($> \tilde{r}_b$).
  4. قيد عدم التجاور: تعاقب الكيوبتات غير المتجاورة التي تكون قريبة جداً ($\leq \tilde{r}_b + \epsilon$).
• التحسين: يتم تدريب النموذج باستخدام محسن AdamW. تتكون مجموعة التدريب من عينة واحدة (حالة QUBO محددة)، وتقوم الشبكة بالتكرار لإيجاد مجموعة إحداثيات تقلل الخسارة، مما يحل فعلياً مشكلة التضمين لذلك الرسم البياني المحدد.

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

1. استدلال عصبي لتضمين NP-hard: تقدم الورقة تطبيقاً جديداً للمشفرات التلقائية لحل مشكلة تضمين رسم وحدة القرص المقيد، متجاوزةً بذلك قيود الحلول الكلاسيكية الدقيقة للرسوم البيانية الأكبر أو الأكثر تعقيداً.
2. دمج القيود الفيزيائية: تدمج المنهجية بشكل صريح القيود الفيزيائية لأجهزة الذرات المتعادلة (نصف قطر الحظر، الحد الأدنى للفصل، وحجم السجل) مباشرة في دالة الخسارة وبنية الشبكة العصبية.
3. المرونة في الأبعاد: تم اختبار النهج في كل من 2D و3D. يوضح المؤلفون أن توسيع الشبكة إلى 3D يسمح بتضمين رسوم بيانية ذات اتصال أعلى (cliques ودرجات أكبر) والتي يستحيل تضمينها في 2D بسبب قيود التعبئة الهندسية.
4. الحدود النظرية: تحدد الورقة الشروط الضرورية للقابلية للتضمين في 2D بناءً على نظرية "ثيوه" (Thue's Theorem) المتعلقة بتعبئة الدوائر، مما يحدد أن الحد الأقصى لحجم الـ clique هو 7 والدرجة القصوى هي 18 في ظل معايير الآلة المحددة ($\tilde{r}_b \approx 10.26$ ميكرومتر).

النتائج
قيم المؤلفون GEAN مقابل حل Gurobi (وهو محلل تربيعي كلاسيكي متطور) على ثلاثة أنواع من حالات QUBO:

• QUBO MIS Antennas: بيانات واقعية من مواقع الهوائيات في تورينو. نجح GEAN في تضمين المكونات المتصلة (حتى 87 كيوبت في 3D) حيث فشل Gurobi في إيجاد حل قابل للتنفيذ خلال مهلة الدقيقتين.
• طي البروتين (Protein Folding): حالات نموذجية لمشكلات المجموعة المستقلة القصوى (Maximum Independent Set). وجد GEAN تضمينات قابلة للتنفيذ لجميع الحالات المختبرة، بينما فشل Guroi في حالة $G_{17,7}$.
• تلوين الرسم البياني (Graph Coloring): مشكلة تلوين ثلاثي لـ 21 كيوبت. وجد GEAN تضميناً ثلاثي الأبعاد في 767 حقبة (epoch)، بينما فشل Gurobi في التقارب.

مقاييس الأداء:

• السرعة: وجد GEAN باستمرار حلولاً في غضون دقيقتين على أجهزة استهلاكية قياسية، حتى لأكثر الحالات تعقيداً (87 كيوبت في 3D).
• القابلية للتنفيذ: في الحالات التي فشل فيها Gurobi في إيجاد أي تضمين قابل للتنفيذ ضمن المهلة الزمنية، نجح GEA في ذلك.
• الجودة: حققت الإحداثيات المحولة جميع القيود الفيزيائية (المسافة الدنيا، المسافة القصوى، وفصل نصف قطر الحظر)، مما حول التكوينات الأولية "غير القابلة للتنفيذ" (التي غالباً ما تُستمد من تخطيطات Fruchterman-Reingold) إلى تخطيطات صالحة للاستخدام في الأجهزة.

الأهمية والادعاءات
تدعي الورقة أن GEAN يوفر جسراً عملياً بين صياغات QUBO النظرية والواقع الفيزيائي لأجهزة الكم الكمي القائمة على الذرات المتعادلة. ومن خلال الاستفادة من الشبكات العصبية لتحسين وضع الكيوبتات، تساهم المنهجية في:

• التغلب على القيود الكلاسيكية: تفوق GEAN على الحلول الدقيقة التقليدية (مثل Gurobi) في إيجاد تضمينات قابلة للتنفيذ للرسوم البيانية المعقدة ضمن أطر زمنية عملية.
• تقليل الهدر في الموارد: بخلاف النهج التي تتطلب ذرات "أسلاك" إضافية أو هياكل شبكية ثابتة، يستخدم GEAN المرونة الكاملة للسجل، مما يتطلب الحد الأدنى من الكيوبتات الفيزيائية اللازمة للمشكلة.
• تمكين القابلية للتوسع: إن القدرة على حل مشكلات التضمين هذه بسرعة تسمح للباحثين باختبار مشكلات QUBO غير بديهية على الأجهزة الحالية ذات عدد الكيوبتات المحدود، دون أن يعيقهم عملية التضمين.

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