Comparing Qubit and Qudit Encodings for EV Charging and Trip Assignment Problems

ملخص تقني: مقارنة بين ترميز الكيوبت (Qubit) والكيوديت (Qudit) لمهام شحن المركبات الكهربائية وتعيين الرحلات

بيان المشكلة
تتناول الورقة البحثية مشكلة التحسين المقيد لإدارة أسطول من المركبات الكهربائية (EVs). يتضمن ذلك عمليتين قرار مترابطتين: جدولة الشحن ثنائي الاتجاه (أو أحادي الاتجاه) لعدد $N_{EV}$ من المركبات عبر أفق زمني منفصل $T$، وتعيين هذه المركبات لعدد $R$ من طلبات رحلات العملاء. الهدف هو تقليل تكاليف الشحن مع تلبية القيود التشغيلية الصارمة، بما في ذلك حدود حالة شحن البطارية (SOC)، وتداخل الرحلات، وحدود قدرة الشبكة، وشرط عدم قدرة المركبة على الشحن أثناء تنفيذ رحلة.

يكمن التحدي الجوهري الذي تمت دراسته في كيفية تأثير اختيار الترميز لمتغيرات تعيين الرحلات على متطلبات الموارد وسلوك التحسين في الخوارزميات الكمومية التباينية (VQAs)، وتحديداً خوارزمية التقريب الكمي للتحسين (QAOA). يقارن المؤلفون بين تمثيلين متميزين:

1. الترميز الثنائي (الكيوبت - Qubit): يستخدم متغيرًا ثنائيًا واحدًا ($r_{n,i} \in \{0,1\}$) لكل زوج (مركبة-رحلة). يتطلب هذا الترميز قيودًا صريحة لضمان خدمة كل رحلة بواسطة مركبة واحدة على الأكثر، وأن الرحلات المتداخلة لا تُسند إلى نفس المركبة.
2. الترميز الصحيح (الكيوديت - Qudit): يستخدم متغيرًا صحيحًا واحدًا ($q_i \in \{0, \dots, N_{EV}\}$) لكل رحلة، حيث يحدد القيمة للمركبة المعينة مباشرة (أو حالة عدم الخدمة). يلبي هذا الترميز بطبيعته قيد "مركبة واحدة لكل رحلة"، مما يلغي الحاجة إلى قيود ثنائية صريحة على التعيين.

المنهجية
صاغ المؤلفون المشكلة باستخدام QAOA. يستخدم كلا الترميزين متغيرات الكيوديت لمستويات طاقة الشحن ($l_{n,t}$)، لكنهما يختلفان في القاعدة الحسابية لتعيينات الرحلات.

• بناء الهاملتوني (Hamiltonian Construction): يتم ترقية دالات التكلفة الكلاسيكية والقيود إلى مؤثرات قطرية في القاعدة الحسابية. يتم فرض القيود (مثل حدود SOC، وعدم الشحن أثناء الرحلات) عبر حدود عقابية غير خطية تُضاف إلى هاملتوني التكلفة.
• المحاكاة: تستخدم الدراسة محاكاة دقيقة لمتجه الحالة (state-vector) لتقييم الخوارزميات. لمحاكاة قيود الأجهزة الواقعية، يتم تقدير القيم المتوقعة لدالة التكلفة باستخدام عدد محدود من عمليات القياس (shots) ($M=256$) بدلاً من الحساب الدقيق.
• التحسين: يقوم مُحسن كلاسيكي (طريقة Powell) بتقليل دالة التكلفة عن طريق تغيير معاملات QAOA ($\gamma, \beta$). تجري الدراسة 10 عمليات تشغيل عشوائية لكل فئة من المشكلات، مع 10 عمليات تحسين لكل حالة، باستخدام ميزانية ثابتة قدرها 200 تكرار للمُحسن الداخلي.
• حالات الاختبار: تم تحليل فئتين من المشكلات:
  • الشحن ثنائي الاتجاه: 3 مركبات كهربائية، خطوتان زمنيتان، رحلتان، و3 مستويات شحن ($d=3$).
  • الشحن أحادي الاتجاه: مركبتان كهربائيتان، 3 خطوات زمنية، عدد متغير من الرحلات ($R=2,3,4$)، ومستويان للشحن ($d=2$).

المساهمات الرئيسية والنتائج
تقدم الورقة تحليلاً مقارناً بين الترميزين عبر عدة مقاييس:

1. تقليص فضاء هيلبرت (Hilbert Space Reduction): يقلل ترميز الكيوديت (الصحيح) أبعاد فضاء هيلبرت بشكل أسي مقارنة بترميز الكيوبت (الثنائي). تُعطى نسبة التكوينات بالمعادلة $N_{int}/N_{bin} \approx 2^{-R N_{EV} + R \log_2(N_{EV}+1)}$. بالنسبة للحالات المختبرة، يؤدي هذا إلى تقليص مساحة البحث من عشرات الآلاف إلى بضعة آلاف من الحالات.
2. أداء التحسين:
   • فجوة الطاقة المتوسطة (Mean Energy Gap): يحقق ترميز الكيوديت باستمرار فجوة طاقة متوسطة مماثلة أو أفضل قليلاً من ترميز الكيوبت.
   • التباين: تظهر نتائج الكيوديت تباينًا أقل بكثير في فجوات الطاقة عبر عمليات التشغيل المختلفة.
   • احتمالية النجاح: تكون نسبة عمليات التشغيل التي تجد الحل الأمثل العالمي ونسبة الحالات الممكنة التي يتم أخذ عينات منها أعلى أو أكثر استقرارًا في ترميز الكيوديت.
3. وقت التشغيل والتقارب:
   • وقت محاكاة التشغيل: نظرًا لصغر فضاء هيلبرت، يتطلب ترميز الكيوديت أوقات محاكاة أقصر بكثير (خطية في عمق الدائرة ولكن بمعامل أصغر بكثير).
   • سلوك عمق الطبقة: مع زيادة عمق QAOA ($L$)، يتدهور أداء ترميز الكيوبت بشكل أكبر من ترميز الكيوديت. يعزو المؤلفون ذلك إلى زيادة عدد المعلمات المتغيرة مما يجعل مشهد التحسين أصعب في الملاحة ضمن ميزانية تكرار ثابتة. ترميز الكيوديت أكثر قوة تجاه الإنهاء المبكر للمُحسن الكلاسيكي.
4. مشهد التكلفة: تظهر مشاهد التكلفة لترميز الكيوبت مقياس طاقة أكبر وترددات تذبذب أعلى بسبب العدد الأكبر من الحالات غير الممكنة (التي تتحمل تكاليف عقابية عالية) مقارنة بترميز الكيوديت.

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

• توفير أسي في الموارد في أبعاد فضاء هيلبرت.
• تقليل العبء الحسابي الإضافي في المحاكاة الكلاسيكية (كوكيل لتعقيد التمثيل).
• تحسين القوة في عملية التحسين، خاصة في الأنظمة شديدة القيود حيث تكون الحلول الممكنة نادرة.

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