QAOA Inside ADMM: Subproblem Wins Do Not Become Decomposition Wins at Matched Budgets
تقوم هذه الورقة البحثية بتقييم خوارزمية التحسين التقريبي الكمي (QAOA) كحل لمسائل فرعية ضمن إطار عمل "خوارزمية تعظيم دالة التقارب والجزاء" (ADMM) للمسائل المختلطة الثنائية، حيث وجدت أنه بينما يمكن لـ QAOA أن تتفوق على الخوارزميات المحلية الكلاسيكية في المحاكاة الخالية من الضجيج تحت معايير تقييم محددة، إلا أنها تفشل في النهاية في تقديم حلول إجمالية متفوقة مقارنة بأفضل الحلول الكلاسيكية عبر عائلات المسائل التي تم اختبارها.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلف ولم يصادق عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
في عالم اتخاذ القرارات المعقدة، غالبًا ما تواجه الحواسيب مشكلات تحتوي على ملايين الإجابات الممكنة، حيث يكون العثور على الإجابة الأفضل الوحيدة أشبه بالبحث عن إبرة في كومة قش يتغير شكلها باستمرار. ولمواجهة ذلك، يستخدم العلماء استراتيجية تسمى التفكيك (decomposition)، والتي تقوم بتجزئة مشكلة ضخمة ومتشابكة إلى قطع أصغر يمكن إدارتها وحلها بشكل منفصل. وتعد طريقة "تغيير اتجاه المضاعفات" (ADMM) إحدى الطرق الشائعة للقيام بذلك؛ إذ تعمل على التناوب بين حل الأجزاء المستمرة من المشكلة والأجزاء المنفصلة (التي تعتمد على وجود أو عدم وجود شيء)، مع تمرير المعلومات ذهابًا وإيابًا حتى تتطابق القطع مع بعضها البعض. لسنوات طويلة، تساءل الباحثون عما إذا كانت الحواسيب الكمومية، التي تعمل وفق القواعد الغريبة لميكانيكا الكم، قادرة على حل هذه الأجزاء المنفصلة بشكل أسرع من الحواسيب الكلاسيكية. والمرشح الأبرز لهذه المهمة هو خوارزمية تُعرف باسم "خوارزمية التحسين التقريبي الكمومي" (QAOA)، المصممة لإيجاد حلول جيدة من خلال استكشاف العديد من الاحتمالات في وقت واحد. وكان السؤال الكبير هو ما إذا كان هذا النهج الكمومي يستحق حقًا التكلفة والجهد مقارنة بالأسالرح الكلاسيكية القوية جداً التي نمتلكها بالفعل.
لقد وضع فريق من الباحثين نصب أعينهم الإجابة على هذا السؤال من خلال وضع الخوارزمية الكمومية تحت اختبار صارم داخل إطار عمل ADMM. لم يكتفوا بمجرد تشغيل الحاسوب الكمومي وتمني الأفضل، بل بنوا مقارنة عادلة حيث مُنح كل من الحلّالين (solvers) الكمومي والكلاسيكي نفس القدر من الجهد الحسابي، أو "الميزانية"، لحل القطع الأصغر من اللغز. ركزت الدراسة على نوع محدد من المشكلات حيث تكون المتغيرات ثنائية، مما يعني أنها يمكن أن تكون صفرًا أو واحدًا فقط. أجرى الباحثون عمليات محاكاة على نسخة مثالية وخالية من الضجيج من حاسوب كمومي مكون من اثني عشر كيوبت (qubit) لمعرفة كيفية أداء الحلّال الكمومي مقابل مجموعة من الحلّال الكلاسيكيين، بما في ذلك البحث العشوائي، والتلدين المحاكي (simulated annealing)، وتقنيات أكثر تقدمًا مثل بحث "تابو" (tabu search). واختبروا النظام على نوعين مختلفين من عائلات المشكلات: إحداهما سلسة وسهلة نسبيًا، والأخرى وعرة وصعبة، صُممت لمحاكة المناظر الطبيعية المعقدة الموجودة في التطبيقات الواقعية.
جاء الاكتشاف الأكثر إثارة للدهشة من كيفية حساب النتائج. ففي عالم الحوسبة الكمومية، تنتج عملية تشغيل واحدة للخوارزمية تدفقًا من الإجابات المحتملة، أو السلاسل الثنائية (bitstrings)، وتقضي الخوارزمية معظم وقتها في ضبط إعداداتها الداخلية لتحسين هذه الإجابات. ووجد الباحثون أن الحكم النهائي يعتمد كليًا على الإجابة التي يتم اختيارها لتمثيل عملية التشغيل. فإذا اعتبر الباحثون الحاسوب الكمومي بناءً على آخر مجموعة من الإجابات فقط، كما هو شائع في بعض الدروس التعليمية للبرمجيات القياسية، فإن الحلّال الكمومي كان يؤدي بشكل أسوأ من مجرد البحث العشوائي؛ فقد فشل في إيجاد الحل الأفضل في كثير من الأحيان مقارنة بحاسوب يقوم بالتخمين العشوائي فقط. ومع ذلك، عندما نسب الباحثون الفضل للحلّال الكمومي في أفضل إجابة واحدة وجدها خلال كامل عملية التشغيل، انقلت القصة تمامًا. فبموجب نظام تسجيل "أفضل عينة" (best-sample)، تفوق الحلّال الكمومي على البحث العشوائي، بل وهزم عدة طرق كلاسيكية متطورة في المشكلات الصعبة والوعرة على مستوى المشكلة الفرعية. وقد كشف هذا أن الفشل المتصور للنهج الكمومي كان في كثير من الأحيان نتاجًا لكيفية تسجيل البيانات، وليس فشلًا في الفيزياء نفسها.
وعندما نظر الباحثون بعمق في أداء نسخة محددة من الخوارزمية الكمومية التي تستخدم إعدادات مدربة مسبقًا، والمعروفة باسم "الزوايا المنقولة" (transferred angles)، وجدوا أنها تستطيع حل المشكلات الفرعية الصعبة بدقة ملحوظة. ففي عائلة المشكلات الوعرة، وجدت هذه الطريقة الكمومية الحل الأفضل بدقة أكبر من طرق البحث المحلي المضبوطة (97.3% مقابل 67.4% لأقوى الاستدلالات المحلية)، رغم أنها لم تتفوق على تقنية كلاسيكية تعتمد على البرمجة شبه المحددة (SDP+LS). ومع ذلك، لم ينتقل هذا التفوق إلى النتيجة النهائية للمشكلة الكلية. ووجدت الدراسة أنه لا توجد عائلة من المشكلات منحت QAOA نتيجة نهائية أفضل من أفضل حلّال كلاسيكي ومعامل جزاء (penalty). كما حسب الباحثون أن النهج الكمومي استغرق حوالي خمسين ضعف الوقت بالثواني مقارنة بطريقة كلاسيكية تسمى بحث "تابو" لنفس حجم المشكلة. علاوة على ذلك، لم يكن أداء الطريقة الكمومية يتوسع بنفس كفاءة الطرق الكلاسيكية؛ فمع زيادة حجم المشكلات، اختفت ميزة الحلّال الكمومي في عدد المحاولات، وتراجع خلف تقنية كلاسيكية تعتمد على البرمجة شبه المحددة.
كما كشفت الدراسة عن خلل دقيق ولكن حاسم في كيفية عمل طريقة التفكيك نفسها. اكتشف الباحثون أنه بالنسبة لأنواع معينة من المشكلات، يعتمد أسلوب إعادة تجميع القطع بشكل كبير على معامل يُسمى "الجزاء" (penalty). فعندما تم ضبط هذا الجزاء على قيمة معينة، قامت طريقة التفكيك فعليًا بحل المشكلة بأكملة مباشرة، مما جعل جودة الحلّال الفرعي غير ذات صلة. ولكن عندما كان الجزاء أعلى، كانت الطريقة تتعثر أحيانًا في حل غير مثالي، وترفض المضي قدمًا حتى لو كان هناك حل أفضل موجود. وفي هذه الحالات، ساعدت الطبيعة "المزعجة" (noisy) للحلّال الكمومي، التي كانت تغير إجاباتها باستمرار، النظام على الهروب من هذه الأفخاخ وإيجاد حل أفضل إجمالي مما كان سيحققه حلّال دقيق ومثالي قد يعلق في مكان ما. وقد أشار هذا إلى أن نجاح الحلّال الكمومي لم يكن دائمًا بسبب طبيعته الكمومية، بل أحيانًا لأنه تصرف مثل البحث العشوائي، وهو وسيلة معروفة للهروب من الأفخاخ المحلية في مناظر التحسين الصعبة.
في النهاية، خلصت الورقة البحثية إلى أنه بينما تُظهر الخوارزميات الكمومية وعدًا في حل مشكلات فرعية محددة بدقة عالية، إلا أنها لم تثبت بعد تفوقًا واضحًا على أفضل الطرق الكلاسيكية عند النظر إلى النظام بأكمله. لم يقدم الحلّال الكمومي نتيجة نهائية أفضل للمشكلة الكلية مما يمكن لأفضل حلّال كلاسيدي تحقيقه مع الإعدادات الصحيحة. وتؤكد الدراسة أن الحوسبة الكمومية لكي تكون مفيدة حقًا في هذه الأنظمة الهجينة، يجب ألا تكتفي بإيجاد إجابات جيدة فحسب، بل يجب أن تفعل ذلك في وقت أقل وبقدرة أكبر على التوسع مقارنة بالبدائل الكلاسيكية. ووجد الباحثون أنه بينما استطاع النهج الكمومي مضاهاة الحلّال الكلاسيكيين في الدقة تحت ظروف معينة، إلا أنه كان أبطأ بكثير ولم يتوسع بنفس الكفاءة. ويعمل هذا العمل كعملية مراجعة ضرورية للواقع، تظهر أن الطريق نحو التفوق الكمومي لا يقتصر فقط على بناء أجهزة كمومية أفضل، بل يتعلق أيضًا بتصميم دقيق لكيفية استخدام هذه الآلات ضمن أطر عمل كلاسيكية أكبر.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.