A Multilevel Framework for Partitioning Quantum Circuits

ملخص تقني: إطار عمل متعدد المستويات لتقسيم الدوائر الكمومية

بيان المشكلة
يوفر الحوسبة الكمومية الموزعة (DQC) مساراً للأنظمة الكمومية القابلة للتوسع من خلال ربط وحدات معالجة كمومية (QPUs) متعددة عبر التشابك. ومع ذلك، فإن تنفيذ الخوارزميات الكمومية عبر هذه العقد الموزعة يؤدي إلى أعباء إضافية كبيرة. يؤدي التعيين الساذج للدوائر إلى وحدات المعالجة الكمومية (QPUs) إلى تكاليف اتصال عالية، وتحديداً استهلاك أزواج التشابك (e-bits)، وزيادة وقت التنفيذ، وارتفاع الضجيج. يكمن التحدي الجوهري في التعيين الأمثل للكيوبتات المنطقية إلى وحدات المعالجة الكمومية (QPUs) وتحديد الطريقة الأكثر كفاءة لتغطية العمليات غير المحلية (البوابات التي تعمل على كيوبتات موجودة في وحدات معالجة مختلفة). وبينما تعالج الطرق الحالية هذه المسألة، إلا أنها غالباً ما تفشل في استيعاب الطيف الكامل لإمكانيات الانتقال الآني (teleportation) أو تعاني من الطبيعة المعقدة (NP-hard) لمشكلة التحسين، لا سيما مع زيادة أحجام الدوائر ونطاق الشبكات.

المنهجية
يقترح المؤلفون إطار عمل شاملاً متعدد المستويات يصيغ تقسيم الدائرة الكمومية كمسألة تقسيم للمخططات الفائقة (hypergraph partitioning). يتكون سير العمل من عدة مراحل متميزة:

1. بناء المخطط وتجميع البوابات:

   • يتم تحويل الدوائر إلى مجموعة بوابات محددة ($U(\theta, \phi, \lambda)$ و $CP(\theta)$) وتحويلها إلى مخطط ممتد زمنياً حيث تمثل العقد الكيوبتات في خطوات زمنية محددة.
   • يتم تعميم هذا المخطط إلى مخطط فائق عن طريق تجميع البوابات بناءً على "التوافق" لعمليات الانتقال الآني للبوابات المتعددة. يتم تشكيل المجموعة إذا كانت البوابات ثنائية الكيوبت تشترك في كيوبت تحكم مشترك، وكانت متجاورة، ولم تقاطعها بوابات أحادية الكيوبت غير قطرية على كيوبت التحكم.
   • يقدم إطار العمل الانتقال الآني للحالة المتداخل (nested state teleportation)، وهو بروتوكول مبتكر حيث يتم اختزال إجراءات انتقال البوابات جزئياً إلى انتقال الحالة آنياً. يسمح هذا للنظام بالاختيار الديناميكي بين انتقال الحالة وانتقال البوابة عن طريق إعادة توجيه "عملية الإنهاء" لإجراء انتقال بوابة متعددة.

2. دالة الهدف:

   • تم تصميم دالة تكلفة فريدة لتقليل عدد أزواج التشابك (e-bits) المطلوبة. يتم تعريف تكلفة الحافة الفائقة بعدد التقسيمات التي يشملها طقم المستقبل والتي لا يتم حسابها بواسطة طقم الجذر (مما يحصي القطوع التي تتطلب موارد تشابك جديدة فعلياً).
   • الهدف هو تقليل مجموع هذه التكاليف عبر جميع الحواف: $\min_{\Phi} \sum_{e \in E} c_e(\Phi)$.

3. خوارزمية التقسيم (المكيفة من FM):

   • تم تكييف خوارزمية فيدوتشيا-ماثيز (Fiduccia-Mattheyses - FM) الشهيرة للتعامل مع الهيكل الزمني للمخطط الفائق وقيود التوازن المحددة (سعة الكيوبت لكل وحدة معالجة كمومية في كل خطوة زمنية).
   • لضمان الكفاءة، يقوم المؤلفون بحساب التكاليف مسبقاً لجميع تكوينات الحواف الفائقة الممكنة ويستخدمون هياكل بيانات مساعدة (تعدادات الجذر/المستقبل) لحساب "مكاسب دلتا" في وقت ثابت.
   • لضمان الهروب من النهايات الصغرى المحلية المتأصلة في التعيينات الأولية الثابتة، قدم المؤلفون تمريرات استكشافية لا تتراجع إلى أفضل مكسب تراكمي، مما يسمح للخوارزمية بعبور تسلسلات من التحركات التي تزيد التكلفة مؤقتاً للوصول إلى حلول مثلى عالمية أفضل.

4. إطار العمل متعدد المستويات:

   • مستوحى من أدوات تقسيم المخططات المتطورة (مثل METIS و KaHyPar)، يستخدم إطار العمل التقسيم الخشن الزمني (temporal coarsening). بدلاً من دمج العقد عشوائياً، يتم دمج الخطوات الزمنية (نافذة، كتلة، أو تقشير متكرر).
   • تتضمن العملية:
     • التقشير (Coarsening): تقليل الدقة الزمنية لإنشاء مخطط فائق أصغر وأكثر خشونة.
     • التقسيم (Partitioning): حل مسألة التقسيم على المخطط الأكثر خشونة.
     • إلغاء التقشير والتحسين (Uncoarsening and Refinement): استعادة الدقة الزمنية تدريجياً، باستخدام الحل من المستوى السابق كنقطة انطلاق، وتطبيق تحسين FM في كل مستوى.
   • تم تحديد استراتيجية التقشير المتكرر (دمج الخطوات الزمنية المتجاورة) كالأكثر فعالية، حيث توفر توسعاً لوغاريتمياً في عدد المستويات.

5. استخراج الدائرة:

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

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

• صياغة الانتقال الآني للحالة المتداخلة: يقدم البحث رؤية موحدة حيث تُعامل عمليات انتقال الحالة والبوابة كاختلافات لنفس الإجراء، والذي يتم تحديده من خلال اتجاه عملية الإنهاء. وهذا يوسع نطاق التصميم لتحسين تكاليف التشابك.
• التقسيم الزمني متعدد المستويات: تكييف تقنيات متعددة المستويات خصيصاً للهيكل الزمني للدوائر الكمومية، مما يسمح بحل المسألة عند مستويات دقة متفاوتة لتحسين جودة الحل ووقت التشغيل على حد سواء.
• خوارزمية FM المعدلة: خوارزمية فيدوتشيا-ماثيز معدلة تتعامل بكفاءة مع دالة التكلفة المحددة وقيود التوازن للحوسبة الكمومية الموزعة، بما في ذلك آليات لتجنب النهايات الصغرى المحلية من خلال التمريرات الاستكشافية.
• التنفيذ مفتوح المصدر: تم تنفيذ إطار العمل في مستودع disqco ، مما يوفر أداة قابلة لإعادة الإنتاج لتجميع الدوائر الكمومية الموزعة.

النتائج
تم اختبار إطار العمل مقابل أساليب متطورة، بما في ذلك Pytket-DQC (باستخدام مسارات Partition و PartitionEmbed و EmbedSteinerDetached) وطريقة التقسيم دقيق التفاصيل (FGP-rOEE).

• تقليل التشابك: عبر مجموعة واسعة من أنواع الدوائر (CP-fraction, QFT, QAOA, Quantum Volume, و QASM benchmarks)، حقق إطار العمل متعدد المستويات المقترح (تحديداً النسخة المتكررة، MLFM-R) أدنى تكاليف للتشابك في معظم الحالات.
• التحسن الكمي: قلل الإطار في المتوسط من متطلبات التشابك بنسبة 35% مقارلة بالطريقة التالية في الأداء.
• القابلية للتوسع: قلل النهج متعدد المستويات من وقت التشغيل بشكل كبير مقارنة بخوارزمية FM القياسية، وسمح بتقسيم دوائر أكبر بكثير (مئات الكيوبتات) من الطرق المنافسة، بشرط ألا يكون عدد التقسيمات كبيراً بشكل مفرط.
• المقايضات: أدى استخدام تجميع البوابات (الانتقال الآني للبوابات المتعددة) إلى تقليل عمق الدائرة بشكل كبير ولكنه زاد من الطلب على كيوبتات الاتصال. يسمح إطار العمل للمستخدمين بضبط هذه المقايضة بناءً على موارد الأجهزة المتاحة.

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

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