Adaptive Differential Evolution and Multistart Search for Noisy QAOA Optimization
تقيم هذه الورقة عشرة من المحسنات الكلاسيكية لتحسين خوارزمية QAOA في ظل وجود ضجيج عند ، كاشفةً أنه بينما تتفوق طرق تعدد البدايات (multistart) مع الأهداف الدقيقة، تصبح الخوارزميات التكيفية القائمة على المجموعات (population-based) تنافسية في ظل وجود الضجيج، وإن كان الاختيار الأمثل يعتمد في النهاية على مستوى الضجيج المحدد، ومقياس الأداء، ونموذج المسألة.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
في مجال الحوسبة الكمومية الناشئ، يحاول العلماء حل ألغاز معقدة تفوق قدرة الحواسيب القياسية الحالية. وتعد إحدى أكثر الأدوات واعدة لهذه المهمة طريقة تسمى "خوارزمية التحسين التقريبي الكمومي". فكر في هذه الخوارزمية كأنها ملاح متطور يحاول العثور على أدنى نقطة في مشهد طبيعي شاسع يلفه الضباب. يمثل هذا المشهد جميع الحلول الممكنة لمشكلة ما، والهدف هو العثور على القاع المطلق، والذي يمثل الإجابة الأفضل. ومع ذلك، لا يستطيع الملاح رؤية الخريطة بأكملها دفعة واحدة؛ بل يجب عليه اتخاذ خطوات، وقياس الارتفاع عند كل نقطة، واستخدام تلك المعلومات لتقرير وجهته التالية. تعتمد هذه العملية على شراكة بين الآلة الكمومية، التي تستكشف المشهد، والحاسوب التقليدي، الذي يعمل كدليل، حيث يقوم بتعديل الخطوات بناءً على ما يتعلمه.
التحدي يكمن في أن المشهد غالباً ما يكون مليئاً بالفخاخ، والمنحدرات الشديدة، والضباب المربك. وفي العالم الحقيقي، ينتج هذا "الضباب" عن الطبيعة غير المثالية للأجهزة الكمومية الحالية، والتي تُدخل أخطاء عشوائية في القياسات. وهذا الضجيج يجعل من الصعب للغاية على الدليل التقليدي معرفة ما إذا كان يتحرك نحو حل أفضل أم أنه يتخبط في الظلام فحسب. وقد تناظر الباحثون طويلاً حول أي نوع من الأدلاء هو الأنسب لهذه المهمة الصعبة. فبعض الأدلاء يعتمدون على حسابات دقيقة وسلسة تعمل جيداً عندما يكون الجو صافياً، بينما يستخدم آخرون استراتيجيات تعتمد على التجربة والخطأ تكون أكثر قوة عندما تكون البيئة فوضوية. إن فهم أي دليل يعمل بشكل أفضل وتحت أي ظروف هو أمر بالغ الأهمية لتحويل هذه الآلات الكمومية من مجرد فضول تجريبي إلى أدوات عملية.
وضع فريق من الباحثين حداً لهذا النقاش عبر إخضاع عشرة أنواع مختلفة من الأدلاء لسلسلة صارمة من الاختبارات. لقد قاموا بمحاكاة إعداد كمومي محدد بـ اثني عشر بتًا كموميًا، وعمق ثلاث طبقات، وستة إعدادات قابلة للتعديل، مما خلق بيئة محكومة لرؤية كيفية أداء كل دليل. كما اختبروا هؤلاء الأدلاء على أربعة أنواع متميزة من مشاهد المشكلات، تتراوح من الشبكات المنتظمة البسيطة إلى الشبكات المتشابكة والمعقدة من التفاعلات. ولجعل الاختبار واقعياً، أجروا التجارب مرتين: مرة بقياسات مثالية خالية من الضجيج، ومرة أخرى بمستويين مختلفين من التشويش المحاكى، مما يمثل الأخطاء الموجودة في الأجهزة الكمومية الحقيقية. وقد منحوا كل دليل ميزانية تصل إلى ثلاثين ألف محاولة لإيجاد الحل الأفضل، مع تتبع ليس فقط جودة الحل الذي وجدوه، بل أيضاً مدى قدرتهم على تحديد الحل الأفضل من البيانات المشوشة التي تلقوها.
كشفت النتائج عن تحول واضح ومفاجئ في الاستراتيجية اعتماداً على الظروف. فعندما كانت القياسات مثالية والمشهد واضحاً، كانت الأدلاء الأكثر فعالية هي تلك التي يمكنها إعادة بدء بحثها من الصفر عدة مرات. هذه الأساليب، والتي تشمل تنويعات من تقنية تُعرف باسم (BFCS)، كانت تستكشف منطقة ما، وتجد نقطة منخفضة محلية، ثم تقفز إلى منطقة جديدة تماماً لتبدأ من جديد. سمح هذا النهج لها باستكشاف المشهد بدقة وتغطية الوديان العميقة بدقة عالية. وفي هذه الظروف الهادئة، كانت الأدلاء التي اعتمدت على مجموعات كبيرة من المرشحين أو نماذج إحصائية معقدة أقل كفاءة، حيث كانت غالباً ما تتعثر أو تتحرك ببطء شديد بحيث لا تصل إلى الإجابة الأفضل الممكنة ضمن المهلة الزمنية.
ومع ذلك، في اللحظة التي أدخل فيها الباحثون الضجيج، تغيرت قواعد اللعبة تماماً. فالأدلاء الذين اعتمدوا على إعادة البدء من الصفر بدأوا في المعاناة، حيث جعلت الأخطاء العشوائية من الصعب التأكد مما إذا كانت نقطة البداية الجديدة هي بالفعل نقطة أفضل أم أنها مج-رد ضربة حظ. وفي هذه البيئة الضبابية، تصدرت الأدلاء التي استخدمت نهجاً قائماً على المجموعات (Population-based approach)، وتحديداً عائلة من الأساليب المعروفة باسم "التطور التفاضلي التكيفي". يعمل هؤلاء الأدلاء من خلال الحفاظ على مجموعة من الحلول المحتملة التي تتطور وتتكيف بمرور الوقت، وتتبادل المعلومات للتنقل عبر حالة عدم اليقين. ووجدت الدراسة أن النوع المحدد من الدليل التكيفي الذي يؤدي بشكل أفضل يعتمد بشدة على نوع الضجيج وهيكل المشكلة. فعلى سبيل المثال، برع أحد المتغيرات عندما كان الضجيج منخفضاً، بينما أصبح متغير آخر، أكثر متانة، هو الفائز الواضح عندما كان الضجيض مرتفعاً.
ولعل الاكتشاف الأكثر أهمية هو التمييز بين إيجاد حل جيد وبين النجاح في اختياره من وسط الضجيج. فحتى عندما يتمكن دليل ما من زيارة أفضل نقطة في المشهد أثناء بحثه، فإن الخطوة النهائية المتمثلة في تحديد النقطة التي سيتم الإبلاغ عنها كإجابة يمكن أن تفسدها التشوهات. فقد اكتشف الباحثون أن الفجوة بين أفضل نقطة تمت زيارتها والنقطة التي تم اختيارها بالفعل يمكن أن تكون كبيرة في ظل وجود ضجيج عالٍ. ووجدوا أن تخصيص جزء صغير من الميزانية الحسابية لإعادة قياس أفضل المرشحين في النهاية قد حسن بشكل كبير جودة الإجابة النهائية عبر جميع الأساليب. وهذا يشير إلى أنه في عالم مليء بالضجيج، فإن القدرة على إعادة فحص طرف خيط واعد لا تقل أهمية عن القدرة على إيجاده.
كما استكشف البحث ما إذا كان استخدام معلومات من نسخ أبسط للمشكلة يمكن أن يساعد. فقد اقترح بعض الباحثين استخدام طريقة "البحث في الشجرة"، حيث تُستخدم الحلول التي تم العثور عليها في عمق ضحل لتقييد البحث في مستوى أعمق. ومع ذلك، أظهرت النتال أن استراتيجية البحث في الشجرة المعقدة هذه كانت أقل فعالية من مجرد صقل البحث المستمر باستخدام دليل محلي. وظل النهج الأكثر نجاحاً هو مزيج من بحث تكيفي واسع النطاق للتنقل عبر الضجيج، يليه صقل محلي مركز للوصول إلى الإجابة بدقة.
في نهاية المطاف، يثبت هذا البحث أنه لا يوجد دليل واحد "أفضل" للتحسين الكمومي. فالاختيار بين الاستراتيجية الصحيحة يعتمد على توازن دقيق بين شكل المشكلة، ومستوى الضجيج في القياسات، والموارد المتاحة. فبالنسب لالمشكلات الواضحة والمنضبطة، تعتبر الطريقة التي تعيد البدء بشكل متكرر هي الأفضل. أما بالنسبة للواقع الفوضوي والمليء بالضجيج للأجهزة الكمومية الحالية، فإن أساليب المجموعات التكيفية التي يمكنها التعلم من مجموعة من المرشحين هي الأكثر فعالية بكثير. يوفر هذا العمل خارطة طريق عملية للعلماء والمهندسين، موضحاً أنه للحصول على أقصى استفادة من هذه الآلات القوية، يجب مواءمة أداة الملاحة بعناية مع التضاريس وحالة الطقس.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.