Congestion-free routing on quantum chips

إليك ملخص تقني مفصل لورقة البحث بعنوان "التوجيه الخالي من الازدحام في الرقائق الكمومية" (Congestion-free routing on quantum chips) للباحث كومار وآخرون.

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

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

• الإضافات في العمق (Depth Overhead): يتطلب نقل حالة عبر مسار طوله $L$ عمليات SWAP بعدد $L$. وبما أن بوابة SWAP تتفكك إلى 3 بوابات CNOT، فإن تكلفة النقل هي $3L$ من الطبقات، مما يزيد بشكل كبير من عمق الدائرة وفقدان الترابط (decoherence).
• ازدحام المسارات (Path Congestion): مع توسع المعالجات، غالبًا ما تتنافس عمليات غير محلية متعددة على نفس المسارات الفيزيائية. وفي بنيات الكيوبت القياسية، يجب تسلسل المسارات المتداخلة (تنفيذها واحد تلو الآخر)، مما يزيد من العمق ومعدلات الخطأ.
• محدودية الكيوبتات المساعدة (Ancilla Limitations): تعتمد الحلول الحالية غالبًا على إضافة كيوبتات "مساعدة" إضافية لتسهيل التوجيه، مما يزيد من الأعباء الهاردويرية والتعقيد.

2. المنهجية: إطار التوجيه الطيفي

يقترح المؤلفون إطار توجيه خالٍ من الـ SWAP يستفيد من الكيوديتات (qudits) (الأنظمة متعددة المستويات، حيث $d > 2$) بدلاً من الكيوبتات الثنائية. الابتكار الجوهري هو معاملة مستويات الطاقة الأعلى لنفس الكيوديت الفيزيائي كـ حافلات طيفية متعامدة (orthogonal spectral buses).

المفاهيم الأساسية:

• تقسيم فضاء الحالة: يتم تقسيم كل كيوديت فيزيائي إلى:
  • الفضاء الحسابي ($H_C$): المستويان $|0\rangle$ و $|1\rangle$ يخزنان الكيوبت المنطقي المقيم.
  • فضاء التوجيه ($H_R$): المستويات من $|2\rangle$ إلى $|d-1\rangle$ تعمل كقنوات لإشارات التحكم الموجهة.
• ترميز الحافلة الثنائي (Binary Bus Encoding): تُرمز إشارات التحكم الموجهة كإزاحات $\Delta_k = 2^k$. يمكن للكيوديت أن يحمل في آن واحد بتًا منطقيًا محليًا ($x_0$) وعدة تسميات حافلة موجهة ($x_k$) في قيمة عدد صحيح واحدة:
  $$r = x_0 + \sum_{k=1}^K x_k 2^k$$
  يسمح هذا لعدة إشارات تحكم متميزة بالمرور عبر نفس العقدة الفيزيائية دون تداخل، بشرجع أن يكون البعد المحلي $d$ كبيرًا بما يكفي ($d \ge 2^{K+1}$).
• عمليات التوجيه الأولية: يستخدم البروتوكول ثلاث عمليات وحدوية (unitary) مثالية:
  1. تحميل الحافلة المتحكم به (Controlled-Bus-Load - CBL): يرفع إشارة التحكم من كيوبت مصدر إلى مستوى حافلة محدد في الجار.
  2. الانتشار المتحكم به بالحافلة (Bus-Controlled Propagation - BCP): ينشر تسمية الحافلة على طول المسار. إذا كانت العقدة السابقة تحمل الحافلة $k$، يتم استثارة العقدة التالية لحملها.
  3. الهدف المتحكم به بالتوجيه (Routing-Controlled Target - CUR): يطبق بوابة منطقية (مثل CNOT) على الفضاء الحسابي للهدف مشروطًا بوجود تسمية حافلة محددة، مع ترك تسمية التوجيه كما هي.
• التنظيف (Cleanup): يتضمن البروتوكول مرحلة عكسية باستخدام عمليات عكسية لإزالة تسمات التوجيه من العقد الوسيطة، واستعادة حالاتها المنطقية الأصلية دون نقل البيانات.

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

أ. تقليل تعقيد النقل

بالنسبة لبوابة غير محلية عبر مسار طوله $L$:

• خط الأساس لـ SWAP: يتطلب $3L$ من طبقات ما يعادل CNOT.
• التوجيه الطيفي: يتطلب $2L + 1$ من العمليات التوجيهية المنطقية.
  هذا يقلل من ثابت النقل الرئيسي بنسبة تقارب 33%.

ب. تخفيف الازدحام عبر تعدد الإرسال الطيفي (Spectral Multiplexing)

يحول هذا الإطار الازدحام المكاني إلى مشكلة تعدد إرسال طيفي.

• التوازي: يمكن لعمليات غير محلية متعددة عبور نفس العقدة الفيزيائية في وقت واحد إذا تم تخصيص تسميات حافلة متميزة لها.
• تلوين الرسم البياني (Graph Coloring): يتم تحديد عدد جولات التوجيه المطلوبة لطبقة من العمليات من خلال الرقم الكروماتي ($\chi(\Gamma)$) لرسم بيوت التعارض في المسارات مقسومًا على عدد الحافلات المتاحة ($K$):
  $$R_K(\Gamma) = \lceil \chi(\Gamma) / K \rceil$$
• الحد الأدنى النظري: يثبت المؤلفون أن التوجيه الذي يتطلب تداخلًا تامًا في نفس العقدة (مع الحفاظ على البيانات المقيمة ومع حامل $K$ من البتات الموجهة) يتطلب بُعدًا لـ هيلبرت المحلي لا يقل عن $d \ge 2^{K+1}$. الكيوبت الواحد ($d=2$) لا يمكنه دعم حتى بت تحكم موجه واحد بجانب الحالة المقيمة دون كيوبتات مساعدة.

ج. امتداد التجميع المنطقي (Boolean Fan-In)

يمتد الإطار ليشمل العمليات متعددة التحكم. يمكن لعدة ضوابط موجهة تصل إلى هدف مشترك عبر حافلات متميزة أن تفعل وحدة (unitary) محلية بناءً على دالة بولية (Boolean function) اختيارية $g(x_1, \dots, x_K)$.

• العمق: يصبح العمق الإجمالي $2L + D_g + O(1)$، حيث $D_g$ هي التكلفة المحلية لتخليق الدالة البولية. هذا يفصل تكاليف النقل غير المحلي عن تكاليف التجميع المحلي.

4. النتائج والتحقق

نتائج المحاكاة

• المحاكاة المثالية (Cirq): أكدت أن بروتوكول التوجيه ينفذ بشكل صحيح بوابات CNOT غير محلية والتجميع البولي (Boolean fan-in) مع صفر تداخل (zero crosstalk) بين المسارات المتداخلة. وقد تم استعادة الحالات الأصلية للعقد الوسيطة بدقة تامة.
• اختبارات المترجم (Compiler Benchmarks): تم الاختبار على دوائر QFT و QAOA و Mirror-interaction.
  • تقليل النقل: كان النقل الموجه باستمرار بمعدل 0.75–0.89 من خط أساس SWAP (على سبيل المثال، QFT على خط: 15.08 مقابل 19.38 SWAPs).
  • جولات الازدحام: باستخدام حافلتين طيفيتين فقط ($K=2$)، انخفض عدد جولات التوجيد لأعباء العمل المزدحمة (مثل دوائر Mirror) من 4 إلى 2.
• المحاكاة الضوضائية (QuTiP):
  • تحت افتراضات الأجهزة الحالية (محدودية ترابط المستويات العليا)، يمتلك بروتوكول التوجيه حاليًا دقة (fidelity) أقل من توجيه SWAP بسبب التسرب (leakage) وفقدان الطور (dephasing) في مستويات الطاقة العليا.
  • تحليل العتبة: تحدد الدراسة "منطقة الربح" (win region). إذا تم تحسين أوقات الترابط للمستويات العليا بمعامل 2–5 (اعتمادًا على سرعة البوابة)، فإن تقليل العمق في التوجيه الطيفي سيؤدي في النهاية إلى تحقيق دقة إجمالية أعلى من توجيه SWAP.

5. الأهمية والآثار المترتبة

• تحول معماري: تقترح الورقة تحولًا جوهريًا من "نقل البيانات" (SWAP) إلى "نقل المعلومات" (الحافلات الطيفية). إنها تعامل الكيوديت الفيزيائي كعقدة متعددة الإرسال قادرة على تخزين البيانات وتوجيه الإشارات في آن واحد.
• الاستقلالية عن الأجهزة: بينما النظرية عامة، إلا أنها ذات صلة خاصة بمنصات مثل الترانزمونات فائقة التوصيل (التي تمتلك طبيعيًا مستويات متعددة يمكن الوصول إليها) والأيونات المحاصرة.
• القابلية للتوسع: من خلال حل مشكلة الازدحام عبر التوسع الطيفي المحلي بدلاً من التكرار المكاني (إضافة المزيد من الكيوبتات)، يوفر هذا النهج مسارًا لتوسيع الدوائر الكمومية على أجهزة الجيران الأقرب دون الأعباء الهائلة للكيوبتات المساعدة.
• النظرة المستقبلية: يعد هذا العمل بمثابة مخطط معماري. فهو يسلط الضوء على أن العائق الرئيسي أمام الاعتماد ليس نظريًا بل هندسيًا: وهو تحسين زمن الترابط ودقة التحكم لمستويات الكيوديت العليا ($|2\rangle, |3\rangle, \dots$) لجعل ميزة العمق النظرية تترجم إلى مكاسب عملية في الدقة.

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