توسع هذه الورقة البحثية خوارزمية التقريب الكمي التكرارية للتحسين (Recursive Quantum Approximate Optimization Algorithm) لتشمل المسائل التوافقية المقيدة من خلال تحديد فئات أوسع من المسائل المغلقة تحت عملية حذف المتغيرات وبناء خلاطات فعالة تحافظ على الإمكانية، مما يتيح التحسين التكراري لمهام مثل مسألة الحقيبة التي تتفوق على النهج غير التكراري والنهج القائم على الجزاء.
في سعيها لحل أكثر الألغاز استعصاءً في العالم، توجه العلماء إلى نوع جديد من الآلات: الحاسوب الكمي. وخلافاً للأجهزة الموجودة في جيوبنا التي تعالج المعلومات كتدفق بسيط من الأصفار والآحاد، تستخدم هذه الآلات القوانين الغريبة للفيزياء للحفاظ على العديد من الاحتمالات في حالة من "التراكب" في آن واحد. وهذا يسمح لها باستكشاف مشهد شاسع من الحلول دفعة واحدة، مما يوفر اختصاراً محتملاً لمشكلات قد تستغرق الحواسيب التقليدية آلاف السنين لحلها. ومن بين الأدوات الواعدة لهذه الآلات خوارزمية تسمى "خوارزمية التحسين التقريبي الكمي". فكر فيها كعملية بحث موجهة حيث يقوم الحاسوب بإعداد حالة كمية، ويقيس مدى ملاءمتها للمشكلة، ثم يعدل إعداداته للوصول إلى أفضل إجابة. ومع ذلك، فإن مشكلات العالم الحقيقي نادراً ما تكون حرة في التجول؛ فهي مقيدة بقواعد صارمة، أو قيود. فشاحنة التوصيل لا يمكنها حمل وزن أكثر مما يسمح به محركها، وشبكة من الأصدقاء لا يمكن أن تتضمن شخصين يرفضان التحدث إلى بعضهما البعض. وعندما تكون هذه القواعد صعبة، فإن طرق البحث القياسية غالباً ما تفشل، فتتوه في بحر من الحلول المستحيلة أو تتطلب حلولاً بديلة ركيكة تضعف من قوتها.
لقد طور فريق من الباحثين الآن طريقة لجعل عمليات البحث الكمي هذه أكثر ذكاءً وانضباطاً، وتحديداً للمشكلات ذات القواعد الصارمة. لقد أخذوا استراتيجية موجودة تسمى "خوارزمية التحسين التقريبي الكمي التكرارية"، والتي تعمل عن طريق حل مشكلة كبيرة عبر تقسيمها بشكل متكرر إلى نسخ أصغر وأبسط من نفسها. في الماضي، كانت هذه الطريقة تعمل جيداً للمشكلات التي لا تحتوي على قواعد، لكنها تعثرت عندما واجهت قيوداً. ففي كل مرة تحاول فيها الخوارزمية تبسيط مشكلة ما عن طريق تثبيت متغير واحد، كان نسيج القواعد المعقد يتحول إلى شكل جديد غير قابل للتمييز لم تعد أدوات الحاسوب قادرة على التعامل معه. أدرك الباحثون أنه لضمان بقاء البحث على المسار الصحيح، كان عليهم التوقف عن محاولة إجبار كل مشكلة مبسطة على العودة إلى قالبها الأصلي. بدلاً من ذلك، بنوا إطار عمل جديداً وأكثر اتساعاً يقبل هذه الأشكال المتغيرة كخطوات طبيعية في العملية.
إن جوهر اكتشافهم هو مجموعة من التعليمات الجديدة التي تسمح للحاسوب الكمي بالتنقل في هذه المشاهد المتغيرة دون الخروج أبداً من نطاق الحلول الصالحة. لقد صمموا نظاماً حيث يقوم الحاسوب، عند كل خطوة من خطوات التبسيط، بإعداد نقطة انطلاق جديدة مضمونة الصلاحية، ويستخدم مجموعة خاصة من الحركات التي تكتفي فقط بالتنقل بين الخيارات الصالحة. وهذا يضمن عدم إضاعة الحاسوب لوقته في استكشاف سيناريوهات مستحيلة. اختبر الباحثون هذا النهج على نوعين صعبين من المشكلات: مشكلة "الحقيبة" (knapsack problem)، التي تتضمن اختيار عناصر لتعظيم القيمة دون تجاوز حد الوزن، ومتغير من مشكلة "تقسيم الرسم البياني" (graph partitioning) حيث يجب تقسيم العقد إلى مجموعتين متساويتين في الوزن. وفي تجاربهم، التي أجريت على حواسيب تقليدية لمحاكاة السلوك الكمي بشكل مثالي، تفوقت طريقتهم الجديدة باستمرار على التقنيات القديمة. فقد وجدت حلولاً أفضل من النهج غير التكراري القياسي، وتفوقت كثيراً على الطرق التي حاولت التعامل مع القواعد عن طريق إضافة جزاءات (penalties)، والتي غالباً ما تركت الحاسوب مرتبكاً بمزيج من الإجابات الصحيحة والخاطئة.
وما يجعل هذا العمل مهماً بشكل خاص هو كيفية تعامله مع التغييرات الحتمية التي تحدث عند تفكيك المشكلة. فعندما تقوم الخوارزمية بتثبيت متغير أو دمج متغيرين معاً، يتغير الهيكل الرياضي للقيود. على سبيل المثال، قد تتحول قاعدة بسيطة حول العدد الإجمالي للعناصر إلى قاعدة أكثر تعقيداً حول المجاميع الموزونة. حاولت الأساليب السابقة فرض هذه القواعد الجديدة للعودة إلى التنسيق القديم، وهو ما فشل غالداً. ومع ذلك، يحدد النهج الجديد فئة أوسع من القواعد التي تظل مستقرة بغض النظر عن كيفية تبسيط المشكلة. لقد أنشأوا برنامجاً ديناميكياً، وهو حساب كلاسيكي يعمل جنباً إلى جنب مع العملية الكمية، لرسم خريطة للحركات الصالحة للمشكلة الجديدة والمبسطة في كل خطوة. وتخبر هذه الخريطة الحاسوب الكمي بالضبط كيف ينتقل من حل صالح إلى آخر دون كسر القواعد، كما تحدد المتغيرات التي أصبحت بالفعل مجبرة على قيمة معينة، مما يسمح للحاسوب بتجاهلها وتركيز قوته على المجاهيل المتبقية.
أظهر الباحثون أن هذه الطريقة تعمل بكفاءة لمجموعة واسعة من القيود، بما في ذلك تلك الموجودة في مشكلة الحقيبة وفي المشكلات التي تتضمن مساواة وعدم مساواة. وأوضحوا أنه طالما أن الأرقام المشار إليها في القواعد ليست ضخمة بشكل فلكي، يمكن للحاسوب إنشاء هذه الخرائط بسرعة. ومع ذلك، فقد رسموا خطاً واضحاً في الرمال: إذا أصبحت القواعد معقدة للغاية أو الأرقام كبيرة جداً، فإن مهمة إيجاد نقطة انطلاق صالحة تصبح مستحيلة لأي حاسوب فعال، وهو قصور متجذر في الطبيعة الجوهرية لهذه المشكلات. أظهرت محاكاتهم، التي تضمنت مشكلات تصل إلى أربعة وعشرين متغيراً، أن الجمع بين هذا الالتزام الصارم بالقواعد واستراتيجية التفكيك التكراري يؤدي إلى نتائج متفوقة. لم يجد النهج الجديد حلولاً ذات جودة أعلى فحسب، بل فعل ذلك من خلال إبقاء الحالة الكمية مركزة تماماً في المنطقة الممكنة، متجنباً الانجراف نحو الحلول غير الصالحة الذي عانت منه الأساليب القائمة على الجزاءات.
يمثل هذا العمل تحولاً في كيفية تفكيرنا في حل المشكلات المقيدة على الأجهزة الكمية. فبدلاً من معاملة القيود كإزعاج يجب معالجته بوضع جزاءات، قام الباحثون بدمجها في صلب حركة الخوارزمية. ومن خلال قبول حقيقة أن المشكلة يتغير شكلها أثناء تبسيطها وبناء أدوات تتكيف مع تلك الأشكال الجديدة، فقد أنشأوا مساراً أكثر قوة نحو إيجاد الحلول المثلى. وتشير النتائج إلى أنه بالنسبة للمشكلات التي تكون فيها القواعد صارمة ومساحة البحث شاسعة، فإن هذا النهج التكراري المدرك للقيود يوفر ميزة واضحة. ورغم أن المحاكاة كانت مثالية وخالية من الضجيج، إلا أن الاتساق في التحسن عبر مختلف أنواع المشكلات وأحجامها يشير إلى قوة حقيقية في الطريقة. إنها تقدم مخططاً لكيفية تعامل الخوارزميات الكمية المستقبلية مع التحديات المعقدة والمقيدة بالقواعد في مجالات اللوجستيات، والجدولة، وتخصيص الموارد، محولةً القيود الصارمة للعالم الحقيقي من عائق إلى دليل.
بيان المشكلة أثبتت خوارزمية التحسين التقريبي الكمومي المتكررة (RQAOA) نجاحاً في حل مشكلات التحسين التوليفي (COPs) غير المقيدة من خلال التخلص المتكرر من المتغيرات بناءً على الارتباطات المقاسة في الحالات التباينية. ومع ذلك، فإن توسيع نطاق RQAOA ليشمل المشكلات المقيدة يمثل تحدياً جوهرياً: إذ إن عمليات الاستبدال القياسية في RQAOA (مثل تثبيت متغير عند 0 أو 1، أو مساواة متغير بآخر أو بنفيه) تغير هيكل الجدوى للمشكلة. وفي السياقات المقيدة، غالباً ما يفشل "المُزج" (Mixer) المصمم للحفاظ على الجدوى لفئة المشكلات الأصلية في الحفاظ عليها للمشكلات الفرعية الناتجة. وقد اعتمدت المحاولات السابقة لتوسيع RQAOA لتشمل المشكلات المقيدة (مثل مجموعة المستقل الأقصى، أو غطاء الرؤوس الأدنى) على قواعد اختزال مخصصة تُبقي كل مشكلة فرعية ضمن فئة المشكلة الأصلية نفسها. وهذا النهج غير كافٍ للمقيدات العامة، مثل مشكلة الحقيبة (Knapsack) أو مقيدات المساواة الخطية، حيث يمكن لعملية استبدال واحدة أن تحول المشكلة إلى فئة مختلفة (على سبيل المثال، تحويل قيد الوزن الهامينج إلى قيد مساواة خطي موزون).
المنهجية يقترح المؤلفون نهج الموثرات التبادلية الكمومية المتكرر (RQAOA) الذي يتعامل جوهرياً مع القيود الصعبة دون استخدام حدود الجزاء (Penalty terms). وتتكون المنهجية الأساسية من ثلاثة مكونات رئيسية:
معايير التصميم المعممة: بدلاً من اشتراط بقاء المشكلات الفرعية ضمن فئة المشكلة الجذرية المحددة، يحدد المؤلفون فئة أوسع من هياكل القيود التي تكون مغلقة تحت جميع عمليات استبدال RQA�A الأربعة (xi∈{0,1,xj,¬xj}). وبالنسبة لكل مشكلة فرعية يتم توليدها، يجب أن تكون الخوارزمية قادرة على تجميع حالة ابتدائية جديدة قابلة للتحقق ومُزج (Mixer) يحافظ على الجدوى بكفاءة.
آليات بناء المُزج والحالة:
القيود أحادية الاتجاه (Unate Constraints): بالنسبة لمسندات الجدوى التي تكون رتيبة (أحادية الاتجاه) في كل متغير (مثل المتراجحات الخطية المفردة مثل مشكلة الحقيبة)، يعمم المؤلفون مُزج "قلب البت المتحكم به" (Controlled bit flip). يتضمن هذا دورانًا للبت الواحد متحكماً به على جدوى قيمة البت "غير الآمنة". ويقوم هذا البناء بتعميم مولد الشجرة الكمومي (QTG) ويضمن الانتقال بين جميع الحلول الممكنة.
قيود المساواة الخطية: بالنسبة للقيود التي تأتي على شكل w⋅x=d (بما في ذلك الوزن الهامينج)، يقدم المؤلفون تبادلات كتل XY المعممة. تقوم هذه العمليات بتبادل كتل موحدة من الكيوبتات ذات الوزن الإجمالي المتساوي. ويضمن وجود "رسم بياني لليف" (Fibre graph) متصل (حيث تمثل الرؤوس الحلول الممكنة وتمثل الحواف عمليات التبادل الصالحة) قدرة المُزج على الانتقال بين أي زوج من الحالات الممكنة.
التصنيع الفعال: من الضروري أن يوضح المؤلفون أنه بالنسبة للقيود ذات الأوزان محدودة حدودياً، يمكن بناء عائلة من تبادلات الكتل المتصلة وحالة ابتدائية قابلة للتحقق في وقت حدودي باستخدام نهج البرمجة الديناميكية عبر مجموعات القيم الجزئية المتاحة. كما يحدد هذا البرنامج الديناميكي "المتغيرات القسرية" (المتغيرات التي تُثبت على قيمة محددة في جميع الحلول الممكنة) ليتم استبعادها كلاسيكياً قبل المعالجة الكمومية.
القيود المعقدة: يمتد الإطار ليشمل أنظمة المساواة الخطية المقترنة بمتراجحة خطية واحدة (مثل الحقيبة ذات القيد على عدد العناصر) عبر استخدام "نجمة" من الحركات المتحكم بها بين ألياف (Fibres) الجدوى، مما يضمن الاتصال دون الحاجة لأن تكون معاملات المتراجحة محدودة حدودياً.
الحلقة المتكررة: في كل خطوة، تقوم الخوارزمية بإعداد حالة تباينية، وتقدير الارتباطات، واختيار عملية استبدال، ثم تصنيع المُزج والحالة الابتدائية من جديد للمشكلة المختزلة باستخدام آليات البرمجة الديناميكية الكلاسيكية. وهذا يتجنب العبء الأسي الناتج عن استنتاج مُزجات المشكلات الفرعية من مُزج المشكلة الأم.
المساهمات الرئيسية
الإطار النظري: يؤسس البحث حساباً منهجياً لتزويد المخططات المتكررة بحالات ابتدائية قابلة للتحقق ودوائر تحافظ على الجدوى لجميع المشكلات الفرعية، متجاوزاً محدودية البقاء ضمن فئة واحدة للمشكلات.
ضمانات الكفاءة: يثبت المؤلفون أنه للفئات المحددة، يمكن بناء المُزجات والحالات الابتدائية اللازمة في وقت حدودي. وعلى العكس من ذلك، يوضحون أنه بالنسبة للأوزان العامة أو الأنظمة ذات القيود المتعددة، فإن البناء الفعال مستحيل ما لم يكن NP⊆BQP.
التنفيذ الخوارزمي: يفصل البحث خطوات المعالجة المسبقة الكلاسيكية (البرمجة الديناميكية لمجموعات القيم الجزئية) المطلوبة لتوليد الدوائر الكمومية لكل خطوة تكرارية، بما في ذلك اكتشاف المتغيرات القسرية.
النتائج أجرى المؤلفون محاكاة عددية دقيقة على فئتين من المشكلات:
مشكلة الحقيبة (0-1 Knapsack): حالات تحتوي على ما يصل إلى 24 متغيراً.
مشكلة الفصل الأقصى الموزون بالرؤوس (Vertex-Weighted Max-Bisection): حالات تحتوي على ما يصل إلى 24 متغيراً، حيث غالباً ما تخرج المشكلات الفرعية عن فئة المشكلة الأصلية (لتصبح قيود مساواة خطية عامة).
تمت مقارنة CRQAOA المقترح بـ:
CQAOA غير المتكرر (الخوارزمية المقيدة).
RQAOA و QAOA القائمين على نظام الجزاء (Penalty-based).
النتائج:
الأداء: حققت خوارزمية CRQAOAs باستمرار أعلى نسب تقريب عبر جميع الحالات، متفوقة على كل من النسخة المقيدة غير المتكررة والنهج القائم على الجزاء.
الجدوى: عانت الطرق القائمة على الجزاء بشكل كبير، خاصة في مشكلة "الفصل الأقصى"، حيث كانت الحالات النهائية ذات تداخل منخفض جداً مع الفضاء الجزئي الممكن (كما هو منخفض بنسبة 11-24% عندما n≥12). في المقابل، حافظت CRQAOA على جدوى بنسبة 100% من خلال التصميم.
تطور المشكلة الفرعية: في مشكلة "الفصل الأقصى"، ولدت الخطوات المتكررة مشكلات فرعية لم تعد تنتمي لفئة "الفصل الأقصى الموزون بالرؤوس"، لكنها ظلت ضمن الفئة الأوسع من قيود المساواة الخطية. وكانت القدرة على تصنيع مُزجات جديدة لهذه المشكلات "المتحولة" ضرورية للنجاح.
الأهمية والادعاءات يزعم البحث حل عقبة حرجة في تطبيق RQAOA على التحسين المقيد: وهي عدم القدرة على الحفاظ على ديناميكيات الحفاظ على الجدوى أثناء تغير هيكل المشكلة أثناء التكرار. ومن خلال تحديد فئات قيود أوسع ومغلقة، وتوفير قواعد تجميع كلاسيكية فعالة لمُزجاتها، تمكن المؤلفون من إنشاء مخطط متكرر:
يتعامل جوهرياً مع القيود الصعبة دون الحاجة لضبط الجزاء أو استخدام كيوبتات إضافية (Slack qubits).
يتفوق على الطرق القائمة على الجزاء عبر تجنب تركيز السعة في الفضاءات غير الممكنة.
يعمم التقنيات الموجودة (مثل QTG ومُزجات MIS) في إطار عمل موحد ومتكرر.
يظل المؤلفون متواضعين بشأن نطاق العمل، مشيرين إلى أن ضمانات الكفاءة لديهم تعتمد على الأوزان المحدودة حدودياً وعدد ثابت من القيود. كما يقرون بأن المشكلات التي ينمو فيها عدد القيود مع حجم المشكلة (مثل مشكلة البائع المتجول) تقع خارج هذه الضمانات. علاوة على على ذلك، يوضحون أنه بينما تم إثبات وجود إنشاءات فعالة، فإن عمق الدائرة الفعلي وعدد البوابات للمُزجات المقترحة (التي تتضمن عمليات متعددة التحكم) أعلى بكثير من المُزجات القياسية، وهو مقايضة تتطلب تحليلاً أكثر وعياً بالموارد. يُقدم هذا العمل كإثبات لمبدأ إمكانية تطبيق النهج في محاكاة دقيقة وخالية من الضجيج.