⚛️ quantum physics

Digitized Counter-Diabatic Quantum Optimization for Bin Packing Problem

تُثبت هذه الورقة أن خوارزمية كمومية رقمية مضادة للدياباتي، وتحديداً باستخدام نموذج مزج (CD-mixer) مضاد للديابات، تحل مشكلة تعبئة الصناديق أحادية البعد بفعالية على الأجهزة الكمومية المتاحة حالياً من خلال التفوق على خوارزمية (QAOA) التقليدية في الدقة والمتانة مع تقليل المتطلبات الموردية.

المؤلفون الأصليون: Ruoqian Xu, Sebastián V. Romero, Jialiang Tang, Yue Ban, Xi Chen

نُشر 2026-04-28

📖 4 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Ruoqian Xu, Sebastián V. Romero, Jialiang Tang, Yue Ban, Xi Chen

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

الصورة الكبيرة: حزم حقيبة سفر بمساعدة صديق سحري

تخيل أن لديك كومة ضخمة من الأمتعة بمختلف الأحجام والأشكال، وعليك حزمها في أقل عدد ممكن من حقائب السفر. هذه هي "مسألة تعبئة الصناديق" (Bin Packing Problem). إنها لغز كلاسيكي يصعب على الحواسيب حلّه بشكل مثالي، خاصة عندما يكون لديك مئات العناصر.

يتساءل مؤلفو هذه الورقة البحثية: هل يمكن لحاسوب كمي (نوع متطور للغاية من الحواسيب) أن يحل لغز التعبئة هذا بشكل أفضل من الحاسوب العادي؟

يقولون "نعم"، ولكن مع لمسة خاصة. لم يستخدموا مجرد طريقة كمية قياسية؛ بل أضافوا "تعزيزاً توربينياً" خاصاً يسمى "القيادة المضادة للدياباتي" (Counter-Diabatic driving). فكر في الأمر كأنك تعطي الحاسوب الكمي خريطة وبوصلة حتى لا يضل طريقه أثناء البحث عن الترتيب الأمثل للحزم.

المشكلة: تحدي "حقيبة السفر"

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

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

الحل: استراتيجية كمية جديدة

اختبر الفريق ثلاث "استراتيجيات" مختلفة (تسمى ansatzes) على حاسوب كمي لمعرفة أي منها يجد أفضل حل للحزم بأسرعة.

الطريقة القديمة (QAOA القياسي): تشبه محاولة إيجاد أفضل ترتيب للحزم عبر التخمين العشوائي ثم التحسين التدريجي لتخمينك. إنها تعمل، لكنها بطيئة وغالباً ما تتعثر في حلول "محلية" (جيدة، ولكن ليست الأفضل).
طريقة "المستوحاة من الـ CD": تستخدم "التعزيز التوربيني" (مصطلحات CD) لتسريع عملية البحث، لكنها تحذف بعض الخطوات القياسية. إنها أسرع ولكنها قد تفقد الحل المثالي أحياناً.
طريقة "CD-Mixer" (الفائزة): هي نجمة هذه الورقة البحثية. فهي تجمع بين الخطوات القياسية و"التعزيز التوربيني" بطريقة محددة.
- التشبيه: تخيل أنك تتنزه للوصول إلى قمة جبل (الحل المثثل).
  - الطريقة القياسية هي المشي ببطء، وفحص كل مسار، والشعور بالتعب.
  - طريقة CD-Mixer تشبه امتلاك مروحية (هليكوبتر) يمكنها التحليق فوق الوديان الضبابية (الحلول السيئة) وإنزالك بالقرب من القمة مباشرة. إنها تجد المسار الأفضل بسرعة أكبر وبخطوات أقل.

ما الذي وجدوه؟

أجرى الباحثون عمليات محاكاة ثم اختبروا أفضل استراتيجية لديهم على حاسوب كمي حقيقي من إنتاج شركة IBM (يسمى ibm_strasbourg).

السرعة والدقة: كانت استراتيجية CD-Mixer هي الفائزة بوضوح. فقد وجدت عدد الصناديق الصحيح المطلوب في معظم الأحيان بنسبة تقارب 100% في اختباراتهم، بينما نجحت الطريقة القياسية في الوصول للنتيجة الصحيحة بنسبة 75% فقط تقريباً.
الكفاءة: احتاجت طريقة CD-Mixer إلى عدد أقل من "الخطوات" (طبقات الدائرة الكمية) للوصول إلى إجابة جيدة. وفي الحوسبة الكمية، تعني الخطوات الأقل فرصة أقل لحدوث الأخطاء، وهو أمر بالغ الأهمية لأن الحواسيب الكمية الحالية لا تزال "صاخبة" (مليئة بالضجيج والأخطاء).
الاختبار في العالم الحقيقي: حتى عندما جربوا ذلك على آلة IBM الكمية الفعلية (التي لها قيود وأخطاء)، لا تزال طريقة CD-Mixer تعمل بشكل جيد جداً، مما يثبت فعاليتها خارج بيئة المحاكاة الحاسوبية.

"السر الخفي": كيف يعمل الأمر؟

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

الخطوة 1: استخدام الحاسوب الكمي لإيجاد جميع الطرق الصالحة لملء صندوق واحد دون أن يكون ثقيلاً جداً.
الخطوة 2: استخدام حاسوب تقليدي (كلاسيكي) لأخذ تلك الحلول الصالحة لـ "الصندوق الواحد" ودمجها لحزم الشحنة بأكملها.

يعمل جزء "الـ Counter-Diabatic" كدرابزين توجيهي. فعندما يحاول الحاسوب الكمي التطور من حالة عشوائية إلى الحل، فإنه غالباً ما يريد الخروج عن المسار. تعمل مصطلحات الـ CD كيد لطيفة تدفعه للعودة إلى المسار الصحيح، مما يضمن وصوله إلى الحل دون إضاعة الوقت أو الطاقة.

الخلاصة

تظهر هذه الورقة البحثية أنه من خلال إضافة "موجه" محدد (القيادة المضادة للدياباتي) إلى الخوارزميات الكمية، يمكننا حل مشكلات التعبئة المعقدة بفعالية أكبر من ذي قبل. وتعد نهج CD-Mixer الأداة الأكثر واعدة لحواسيبنا الكمية الحالية، حيث توفر طريقة للحصول على إجابات عالية الجودة حتى مع الأجهزة المحدودة التي نمتلكها الآن.

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

إليك ملخص تقني مفصل لورقة البحث بعنوان: "التحسين الكمي المتقابل مع التغيير الرقمي لمسألة تعبئة الصناديق" (Digitized Counter-Diabatic Quantum Optimization for Bin Packing Problem).

1. بيان المسألة

تتناول الورقة البحثية مسألة تعبئة الصناديق أحادية البعد (1dBPP)، وهي مسألة كلاسيكية من نوع المسائل التوافقية ذات التعقيد الحسابي غير المحدد (NP-hard). الهدف هو تعبئة $n$ من العناصر ذات الأوزان المتفاوتة في أقل عدد ممكن من الصناديق، بحيث يكون لكل صندوق سعة ثابتة $C$ ، دون تجاوز سعة أي صندوق.

التحديات: تتسم الطرق التقليدية القائمة على البحث الشامل (Brute-force) بتعقيد زمني أسي ( $m^n$ )، مما يجعلها غير عملية للمسائل الكبيرة. وتوفر النهج الاستدلالية الكلاسيكية والتعلم الآلي الكفاءة، لكنها غالباً ما تضحي بدقة الحل.
السياق الكمي: على الرغم من تطبيق التلدين الكمي (Quantum Annealing) وخوارزمية التقريب الكمي الأمثل (QAOA) في التحسين، إلا أنها تواجه قيوداً في القدرة على التوسع، وعمق الدارة، وسرعة التقارب على الأجهزة الكمية الحالية ذات المقياس المتوسط المشوب بالضجيج (NISQ). وتحديداً، يعد تشفير قيود السعة الصارمة لمسألة 1dBPP في "هاميلتوني" (Hamiltonian) أمراً معقداً ومستهلكاً للموارد.

2. المنهجية

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

أ. صياغة المسألة وبناء الهاميلتوني

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

التركيز على الصندوق الواحد: يتم تفكيك المسألة إلى إيجاد "حلول جزئية قابلة للتنفيذ" (FPS)—وهي مجموعات فرعية من العناصر التي تتناسب داخل صندوق واحد.
هاميلتوني التكلفة ( $H_c$ ): يتم بناء هاميلتوني تربيعي يعمل على معاقبة مجموع الأوزان التي تتجاوز السعة $C$ . يتم ضبط الهاميلتوني عبر المعاملات $A$ و $B$ لتحديد جميع مجموعات الأوزان القابلة للتنفيذ حتى السعة $C$ .
أخذ العينات التدريجي: يُستخدم معامل $k$ (حجم الخطوة) للتنقل عبر مجموعات أوزان مختلفة، مما يولد مجموعة من المجموعات المرشحة.

ب. الخوارزميات الكمية (مخططات الـ Ansatz)

يكمن الابتكار الأساسي في مقارنة أربعة هياكل مختلفة للدارات الكمية المتغيرة لإيجاد الحالة الأرضية لهاميلتوني التكلفة:

QAOA القياسية: تتناوب بين هاميلتوني التكلفة ( $H_c$ ) وهاميلتوني المزج ( $H_m = \sum \sigma_x$ ).
DC-QAOA: توسع خوارزمية QAOA بإضافة حدود المتقابلة مع التغيير (Counter-Diabatic - CD) ( $H_{CD}$ $H_{C D}$ ) إلى مؤثر التطور. تعمل هذه الحدود على كبح الانتقالات غير الأديباتية (non-adiabatic transitions)، مما يسمح بتقارب أسرع نحو الحالة الأرضية بعدد أقل من الطبقات.
- حد الـ CD: يتم تقريبه باستخدام نهج المبدل المتداخل (Nested Commutator - NC)، مما ينتج عنه هاميلتوني يتضمن تفاعلات $\sigma_y \sigma_z$ و $\sigma_y$ .
الـ Ansatz المستوحى من CD: دارة مبسطة تستخدم فقط حدود الـ CD ( $e^{-i\gamma H_{CD}}$ )، مع إزالة التناوب القياسي بين التكلفة والمزج لتقليل عمق الدارة.
الـ Ansatz الخاص بمزج الـ CD (CD-Mixer): نهج هجين يجمع بين مزج بسيط ( $H_m$ ) وحدود الـ CD ( $e^{-i\beta H_m} e^{-i\gamma H_{CD}}$ ). يهدف هذا إلى موازنة قدرة البحث للمزج مع تسريع عملية القيادة بواسطة الـ CD.

ج. المعالجة الكلاسيكية اللاحقة

التصفية: تُخرج الدارة الكمية سلاسل بتات (bitstrings) تمثل مجموعات فرعية من العناصر. يقوم فحص كلاسيكي بتصفية "الحلول الجزئية غير القابلة للتنفيذ" (IPS) حيث يتجاوز مجموع الوزن السعة $C$ .
إعادة البناء: يتم دمج الـ FPS المتبقية باستخدام خوارزمية كلاسيكية لتعبئة جميع العناصر في أقل عدد ممكن من الصناديق.

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

أول تطبيق لـ DC-QAOA على مسألة 1dBPP: تقدم الورقة أول استكشاف متعمق لبروتوكولات الـ CD الرقمية لمسألة تعبئة الصناديق.
التحليل المقارن للمتغيرات: تقوم الورقة بتقييم منهجي لثلاثة متغيرات من DC-QAOA (الأصلية، والمستوحاة من CD، ومزج CD) مقابل QAOA القياسية، مع تحليل متانتها عبر عدد التكرارات، وعمق الطبقات، وحجم خطوة الهاميلتوني ( $k$ ).
التحقق من الأجهزة: تتضمن الدراسة تنفيذاً واقعياً على جهاز IBM Quantum "ibm_strasbourg" (بـ 127 كيوبت)، مع تحسين ترجمة الدارة (transpilation) للبوابات الأصلية (ECR, RZ, SX, X).
تبسيط الهاميلتوني: من خلال التركيز على تعبئة الصندوق الواحد واستخدام نهج هجين، نجح المؤلفون في التخفيف من قيود اتصال الكيوبتات وزمن التماسك في الأجهزة الحالية.

4. النتائج

تم تقييم الأداء باستخدام مقاييس مثل نسبة القابلية للتنفيذ (FR) (نسبة الحلول الصالحة التي تم العثور عليها) وعدد الحلول النهائية المتولدة.

نتائج المحاكاة:
- تفوق CD-Mixer: أظهر نموذج CD-mixer ansatz الأداء الأكثر متانة. فقد حافظ على نسبة قابلية تنفيذ عالية (قريبة من 1.0) حتى مع أحجام خطوات كبيرة ( $k=4$ ) وعدد أقل من التكرارات، بينما عانت QAOA القياسية من انخفاض كبير في الأداء تحت نفس الظروف.
- التقارب: حققت DC-QAOA ومتغيراتها تقارباً أسرع وتطلبت طبقات دارة أقل لإيجاد الحلول المثلى مقارنة بـ QAOA القياسية.
- كفاءة البوابات: تطلب نموذج CD-mixer عدداً أقل من بوابات CNOT والبوابات ذات المعاملات لكل طبقة مقارنة بـ DC-QAOA القياسية، مما يجعله أكثر ملاءمة لأجهزة NISQ.
النتائج التجريبية (IBM Quantum):
- في حالة W3 10 (10 عناصر، 3 صناديق مثالية)، حقق نموذج CD-mixer تطابقاً بنسبة ~100% مع الحلول الدقيقة لتعبئة الصندوق الواحد.
- حققت QAOA القياسية دقة 75% فقط على نفس الجهاز.
- نجح نموذج CD-mixer في تحديد العدد الأمثل للصناديق ( $M=3$ ) وولد عدداً أكبر من الحلول النهائية الصالحة مقارنة بالطرق الأخرى، رغم الضجيج المتأصل في الأجهزة الحقيقية.

5. الأهمية والخاتمة

التغلب على قيود NISQ: تثبت الدراسة أن دمج القيادة المتقابلة مع التغيير (Counter-Diabatic driving) يعد استراتيجية قابلة للتطبيق لتقليل عمق الدارة وتحسين جودة الحل في الأجهزة الكمية الحالية، مما يعالج مشكلات "الهضبة القاحلة" (barren plateau) والتقارب الشائعة في خوارزميات التحسين المتغيرة (VQAs).
القابلية للتطبيق العملي: يؤكد التنفيذ الناجح على أجهزة IBM إمكانات الخوارزميات الكمية لمشاكل اللوجستيات وسلاسل التوريد في العالم الحقيقي.
الاتجاهات المستقبلية: يشير المؤلفون إلى إمكانية توسيع استراتيجية تبسيط الهاميلتوني (تفكيك القيود المعقدة إلى مسائل الصندوق الواحد) لتشمل متغيرات أكثر تعقيداً مثل تعبئة الصناديق ثنائية وثلاثية الأبعاد. علاوة على ذلك، يمثل نموذج CD-mixer نموذجاً واعداً لمهام التحسين التوافقية الأخرى حيث يكون التقارب السريع وعمق الدارة المنخفض أمرين حاسمين.

باخت-صار، يرسخ هذا العمل DC-QAOA، ولا سيما متغير CD-mixer، كإطار عمل قوي وفعال لحل المسائل التوافقية ذات التعقيد العالي (NP-hard) على الأجهزة الكمية القريبة من العصر الحالي، متفوقاً على QAOA التقليدية في كل من المحاكاة وتجارب الأجهزة الحقيقية.