⚛️ quantum physics

QUACOD: Quantum Optimization via Coordinate Descent for Scalable Drone Scheduling

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

المؤلفون الأصليون: Van-Quang-Huy Nguyen, Hoang-Quan Nguyen, Samee U. Khan, Ilya Safro, Khoa Luu

نُشر 2026-05-15

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

CC BY 4.0

المؤلفون الأصليون: Van-Quang-Huy Nguyen, Hoang-Quan Nguyen, Samee U. Khan, Ilya Safro, Khoa Luu

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

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

هذه هي مشكلة جدولة الدرون (Drone Scheduling Problem). إنها تشبه محاولة تنظيم رقصة فوضوية حيث يمتلك الجميع خطوات مختلفة، وأنت تريد أن تتوقف الموسيقى بمجرد انتهاء آخر راقص.

المشكلة: راقصون كثر.. ومسرح صغير جداً

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

مؤخراً، اعتقد العلماء: "لنستخدم الحواسيب الكمومية (Quantum Computers)!"، وهي آلات مستقبلية يمكنها حل ألغاز معينة بسرعة أكبر بكثير من الحواسيب العادية. ومع ذلك، هناك عقبة؛ فالحواسيب الكمومية الحالية تشبه الآلات الموسيقية الصغيرة والهشة، فهي لا تمتلك سوى عدد قليل من "الكيوبتات" (وهي المعادل الكمومي للخلايا العصبية في الدماغ). محاولة حل مشكلة درونات ضخمة على هذه الحواسيب تشبه محاولة حشر أوركسترا كاملة داخل صندوق أحذية. الأجهزة الكمومية الحالية ببساطة ليست كبيرة بما يكفي لاستيعاب المشكلة بأكملها في وقت واحد.

الحل: QUACOD (استراتيجية "التقطيع")

ابتكر مؤلفو هذه الورقة البحثية، بقيادة "فان كوانج هوي نجوين" وزملائه، حلاً ذكياً يسمى QUACOD (التحسين الكمومي عبر الهبوط الإحداثي).

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

إليك كيف يعمل الأمر، باستخدام تشبيه بسيط:

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

من خلال تقسيم المشكلة الضخمة إلى "إحداثيات" صغيرة (مجموعات صغيرة من المتغيرات)، يسمح QUACOD لحاسوب كمومي صغير بحل مشكلة ضخمة لم يكن بإمكانه التعامل معها بمفرده.

النتائج: التفوق على المنافسين

اختبر الفريق تقنية QUACOD مقابل أفضل طريقة سابقة (تسمى QUADRO). وإليكم ما وجدوه:

السرعة والكفاءة: وجد QUACOD جداول زمنية تنتهي بشكل أسرع من الطريقة القديمة.
القابلية للتوسع (الفوز الكبير): كانت الطريقة القديمة (QUADRO) قادرة فقط على التعامل مع 11 طائرة درون تقريباً. أما QUACOD، وباستخدام نفس "صندوق الأحذية" الكمومي الصغير، فقد نجح في إدارة مشكلات تضم 55 طائرة درون (أي 5 أضعاف أكثر) و 1,000 مسار (أي 35 ضعفاً أكثر).
كفاءة الأجهزة: أثبتوا أنك لست بحاجة إلى حاسوب كمومي ضخم ومثالي؛ يمكنك استخدام حاسوب كمومي صغير و"مشوش" (مثل النوع الموجود لدينا اليوم) إذا استخدمت الاستراتيجية الصحيحة (مثل تصميم الدائرة "الفعالة من حيث الأجهزة" الخاص بهم).

الخلاصة

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

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

ملخص تقني: QUACOD – التحسين الكمي عبر التدرج الإحداثي لجدولة الطائرات بدون طيار القابلة للتوسع

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

تتناول الورقة البحثية مشكلة جدولة الطائرات بدون طيار (Drone Scheduling Problem)، وهي مكون حيوي في الخدمات اللوجستية للمرحلة الأخيرة (last-mile logistics)، حيث يتمثل الهدف في تعيين مسارات محددة مسبقاً لأسطول من الطائرات بدون طيار المتطابقة لتقليل أقصى وقت إنجاز ( $C_{max}$ ) للأسطول بأكಲೇ.

تشمل القيود والخصائص الرئيسية للمشكلة ما يلي:

قيود البطارية: يجب أن تشحن الطائرات بدون طيار نفسها بين المسارات المتتالية، مما يؤدي إلى إدخال وقت إعادة شحن ( $c$ ) غير مهمل يؤثر بشكل كبير على إجمالي وقت الإنجاز.
التعقيد التوليفي: المشكلة هي مسألة (NP-hard)، مرتبطة بمسألة البائع المتجول (Traveling Salesman Problem)، مع مساحة حل تنمو أسياً مع زيادة عدد المسارات ( $n$ ) والطائرات ( $q$ ).
القيود العتادية: يعيق التطبيق العملي محدودية أجهزة الحوسبة الكمية ذات الضجيج والمتوسطة المقياس (NISQ) الحالية، والتي تفتقر إلى عدد الكيوبتات (qubits) المطلوب لترميز مشكلات الجدولة واسعة النطاق مباشرة في التلدين الكمي (Quantum Annealing) أو الخوارزميات الكمية التباينية (VQA). النهج الكمي الحالي، مثل QUADRO، محدود بنماذج صغيرة جداً (على سبيل المثال، أقل من 11 طائرة بدون طيار).

2. المنهجية: QUACOD

يقترح المؤلفون QUACOD (التحسين الكمي عبر التدرج الإحداثي)، وهو إطار عمل هجين (كمي-كلاسيكي) مصمم لحل مشكلات الجدولة واسعة النطاق تحت قيود صارمة على عدد الكيوبتات.

أ. صياغة المشكلة وتحويلها إلى QUBO

يتم نمذجة مشكلة الجدولة في البداية كعملية تقليل لـ $C_{max}$ مع مراعاة قيود التعيين (كل مسار يتم تعيينه لطائرة واحدة بالضبط) وقيود السعة. ولجعلها متوافقة مع التحسين الكمي، قام المؤلفون بتحويل المشكلة إلى صيغة التحسين التربيعي غير المقيد بالمتغيرات الثنائية (QUBO):

معالجة القيود: تم تحويل قيود المساواة (تعيين المسارات) إلى حدود جزائية تُضاف إلى دالة الهدف.
تحويل الهدف: بدلاً من تقليل $C_{max}$ مباشرة، استخدم المؤلفون نموذجاً استدلالياً مشتقاً من ملاحظة أن تقليل مجموع مربعات الانحرافات لأوقات إنجاز الطائرات الفردية ( $T_j$ ) عن متوسط وقت الإنجاز ( $T/q$ ) يقلل فعلياً من $C_{max}$ . هذا يلغي قيود عدم المساواة المعقدة.
الهدف النهائي: تقوم دالة QUBO الناتجة بتقليل مجموع مربعات الانحرافات لـ $T_j$ بالإضافة إلى الجزاء الخاص بالمسارات غير المعينة.

ب. خوارزمية QUACOD

للتغلب على محدودية ندرة الكيوبتات، تكيّف QUACOD استراتيجية تحسين التدرج الإحداثي (Coordinate Descent):

التفكيك (Decomposition): بدلاً من تحسين جميع المتغيرات الثنائية $n \times q$ في وقت واحد، تختار الخوارزمية بشكل تكراري مجموعة فرعية صغيرة من المسارات ( $N$ ) والطائرات ( $Q$ ).
اختيار المتغيرات: يتم اختيار المجموعات الفرعية بحيث:
- لا يتجاوز عدد المتغيرات ( $|N| \times |Q|$ ) عدد الكيوبتات المتاحة ( $m$ ).
- تتضمن المجموعة الفرعية الطائرة ذات أعلى وقت إنجاز (عنق الزجاجة) والطائرة ذات أقل وقت إنجاز (الأقل حمولة) لتسهيل عملية إعادة التوزيع.
- يضمن الاختيار وجود حلول غير تافهة (على الأقل مسار واحد معين لكل طائرة مختارة).
الروتين الكمي الفرعي: يتم حل المشكلة الفرعية المختارة باستخدام خوارزمية الحل الطيفي الكمي التبايني (VQE) مع أنسات (ansatz) كفء للعتاد (طبقة واحدة من دورات $R_y$ وبوابات تشابك $CZ$ خطية).
التكرار: يتم تثبيت المتغيرات غير المختارة، وتتكرر العملية حتى التقارب.

ج. الأنسات الكفء للعتاد (Hardware-Efficient Ansatz)

تستخدم الورقة البحثية "أنسات" محدد لـ VQE يتكون من كتل دوران $R_y$ تفصل بينها سلسلة خطية من بوابات التشابك $CZ$ . تم اختيار هذا التصميم لتوافقه مع أجهزة NISQ وقدرته على إنتاج حلول عالية الجودة باستخدام طبقة واحدة، مما يتجنب الدوائر العميقة والتكاليف الحسابية العالية المرتبطة بخوارزمية QAOA.

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

خوارزمية مبتكرة: تقديم QUACOD، وهو نهج هجين يفكك جدولة الطائرات بدون طيار عالية التعقيد إلى مشكلات فرعية يمكن حلها بواسطة الأجهزة الكمية الحالية.
القابلية للتوسع: إثبات أن التدرج الإحداثي يمكن أن يسد الفجوة بين التفوق الكمي النظري والقيود العملية لأجهزة NISQ، مما يسمح بحل مشكلات أكبر بكثير مما تعاملت معه الطرق السابقة.
التحقق من الأداء: أدلة تجريبية تظهر تفوق QUACOD على أحدث ما توصل إليه العلم (QUADRO) في كل من جودة الحل (أوقات إنجاز أقل) والقابلية للتوسع.
كفاءة العتاد: التحقق من أن الدوائر الكفئة للعتاد فعالة للتحسين التوليفي، مما يدعم جدوى النشر الكمي في المدى القريب.

4. النتائج التجريبية

قيم المؤلفون QUACOD باستخدام عمليات محاكاة كلاسيكية للأجهزة الكمية (Qiskit) على مجموعتي بيانات:

المقارنة مع QUADRO (مجموعة بيانات Augerat):
- تم اختبار QUACOD على ست حالات بمتغيرات مختلفة من الطائرات والمسارات.
- النتائج: وجدت QUACOD باستمرار حلولاً بأوقات إنجاز قصوى أقل من كل من النهجين الهجين والكمي الصرف لـ QUADRO.
- القابلية للتوسع: بينما فشل QUADRO في جدولة الحالات التي تزيد عن 11 طائرة بدون طيار، نجح QUACOD في التعامل مع حالات تصل إلى 50 طائرة بدون طيار و1,000 مسار (5 أضعاف عدد الطائرات و35 ضعفاً لعدد المسارات مقارنة بحدود QUADRO).
الاختبار المرجعي واسع النطاق (مجموعة بيانات جدولة الآلات المتوازية):
- أُجريت التجارب على حالات تتراوح من 200 إلى 3,000 مسار ومن 5 إلى 100 طائرة بدون طيار.
- نجحت QUACOD في حل معظم الحالات واسعة النطاق باستخدام 20 كيوبت فقط لمحاكاة الكم.
- القيود: فشلت أكبر حالتين (3,000 مسار، 100 طائرة بدون طيار) بسبب قيود الذاكرة الكلاسيكية (RAM) المطلوبة لتخزين حدود $O(n^2q^2)$ لدالة QUBO، وليس بسبب قيود العتاد الكمي.

5. الأهمية والادعاءات

تدعي الورقة أن QUACOD يمثل خطوة مهمة نحو التطبيقات الكمية العملية في عصر NISK من خلال:

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

القيود المعترف بها

أشار المؤلفون بتواضع إلى عدة قيود:

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