Quantum Superposition over Near Optimal Seeds for Maximum Independent Set on Dense Graphs
تقدم هذه الورقة خوارزمية كمومية تباينية تستفيد من التراكبات الموحدة للبذور القريبة من المثالية والاختيار اللاحق القائم على التداخل لحل مشكلات المجموعة المستقلة القصوى في الرسوم البيانية الكثيفة التي تصل إلى 400 عقدة، متفوقة بشكل كبير على خوارزميات VQE القياسية والاستدلالات الكلاسيكية في الحالات الصعبة حيث تتعثر الطرق السابقة.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
في عالم علوم الحاسوب، هناك فئة من المشكلات تُعرف باسم التحسين التوليفي (combinatorial optimization)، حيث يكون الهدف هو إيجاد أفضل ترتيب ممكن من بين عدد هائل من الخيارات. ومن أشهر هذه المشكلات هي مشكلة "المجموعة المستقلة القصوى" (Maximum Independent Set). تخيل مجموعة من الأشخاص في حفلة، حيث يعرف بعضهم بعضاً ولا يعرف الآخرون بعضهم البعض. التحديد يكمن في دعوة أكبر عدد ممكن من الضيوف إلى غرفة خاصة بحيث لا يعرف أي شخصان في الغرفة بعضهما البعض. إذا كان شخصان يعرفان بعضهما، فلا يمكن دعوتهما معاً. وبينما يبدو هذا الأمر بسيطاً لمجموعة صغيرة، فإن عدد التشكيلات الممكنة ينمو بسرعة انفجارية لدرجة أن أقوى الحواسيب الفائقة تجد صعوبة في إيجاد الإجابة المثالية المطلقة عندما تصل المجموعة إلى بضع مئات من الأشخاص. وتجعل هذه الصعوبة من المشكلة اختباراً قياسياً للتقنيات الحوسبية الجديدة، وخاصة الحواسيب الكمومية، التي تستخدم القواعد الغريبة لميكانيكا الكم لاستكشاف العديد من الاحتمالات في وقت واحد.
لقد طور فريق من الباحثين في "آي بي إم ريسيرش" (IBM Research) طريقة جديدة لمعالجة هذه المشكلة في الرسوم البيانية الكثيفة (dense graphs)، حيث يعرف الجميع تقريباً الجميع تقريباً. في هذه السيناريوهات المزدحمة، غالباً ما تقع طرق البحث التقليدية في فخ محلي، فتجد حلاً جيداً لكنها تفوت الحل المثالي لأن الطريق إلى الإجابة الأفضل يتطلب سلسلة من التغييرات المنسقة التي تبدو مستحيلة التنفيذ واحداً تلو الآخر. وجد الباحثون أنه من خلال استخدام حاسوب كمومي لإبقاء عدة حلول "شبه مثالية" في حالة من التراكب (superposition) — وهي حالة حيث ينظر الحاسوب إلى خيارات متعددة في آن واحد — يمكنهم كسر هذه الفخاخ. وقد أظهر عملهم، الذي تم اختباره على رسوم بيانية تصل إلى 400 عقدة، أن هذا النهج يمكنه إيجاد أكبر المجموعات الممكنة من الرؤوس غير المتجاورة، مما يحل حالات استعصت على الطرق القياسية. والأهم من ذلك، أنهم أظهروا أن هذا النجاح يعتمد على قدرة الحاسوب الكمومي على استكشاف مشهد الحلول بشكل متوازٍ، بدلاً من مجرد تحسين نقطة بداية واحدة.
بدأ الباحثون بالإقرار بوجود نقطة ضعف محددة في كيفية مقاربة الحواسيب الكمومية لهذه المشكلات عادةً. فالطرق القياسية غالباً ما تبدأ من لوحة فارغة، وتطلب من الآلة الكمومية البحث في الكون بأكره من الصفر. بالنسبة للرسوم البيانية الكثيفة، تكون الإجابة الصحيحة نادرة جداً لدرجة أنها تشبه البحث عن حبة رمل محددة وسط شاطئ؛ والبدء بلوحة فارغة يعني أن الحاسوب ليس لديه فرصة تذكر للعثور عليها بمحض الصدفة. وبدلاً من ذلك، قرر الفريق البدء بـ "دفعة للأمام". فقد استخدموا حواسيب كلاسيكية لإيجاد عدة حلول عالية الجودة، وإن لم تكن مثالية. كانت هذه هي "البذور" لعملية البحث الخاصة بهم. ثم قاموا بتشفير هذه البذور في الحاسوب الكمومي، ليس واحداً تلو الآخر، بل جميعاً في وقت واحد، مما خلق تراكباً منتظماً. في هذه الحالة، كان الحاسوب الكمومي، فعلياً، يحتفظ بكل هذه الحلول شبه المثالية في ذهنه في آن واحد، معاملاً إياها كنقطة بداية واحدة معقدة.
لضمان بقاء البحث على المسار الصحيح، استخدم الفريق نوعاً خاصاً من الدوائر الكمومية المصممة للحفاظ على عدد "الإثارة" (excitation). وفي لغة المشكلة، كان هذا يعني أن الدائرة ممنوعة تماماً من تغيير العدد الإجمالي للأشخاص المدعوين إلى الغرفة. فإذا بدأت البذور بـ 14 شخصاً، فإن التطور الكمومي يمكنه فقط تبديل هؤلاء الـ 14 شخصاً، عبر استبدال ضيف بآخر، لكنه لا يمكنه أبداً دعوة شخص 15 بالخطأ أو خفض العدد إلى 13. كان هذا القيد حيوياً؛ فقد أبقى البحث مركزاً على المنطقة الأكثر واعدة في مساحة الحلول، ومنع الحاسوب من إضاعة الوقت في استكشاف تكوينات مستحيلة أو أدنى مستوى بوضوح. ومن خلال تثبيت عدد الضيوف المدعوين، استطاعت الدائرة إجراء تمييز دقيق بين المجموعات المختلفة المكونة من 14 شخصاً، بحثاً عن الترتيب المحدد الذي يقترب من الإجابة المثالية.
اختبر الفريق هذا المسار على عدة رسوم بيانية صعبة، بما في ذلك حالة صعبة مكونة من 180 عقدة حيث يتضمن الحل المثالي 15 شخصاً. وعندما حاولوا حل هذه الحالة باستخدام بذرة واحدة، تعثر النظام باستمرار عند 14 شخصاً، عاجزاً عن إيجاد الطريق للوصول إلى الشخص الخامس عشر. ومع ذلك، عندما استخدموا تراكب أربع بذور مختلفة مكونة من 14 شخصاً، نجح النظام في الاختراق. لقد وجد الحاسوب الكمومي، من خلال تطوير البذور الأربع معاً تحت نفس القواعد، تكويناً لم تستطع أي من البذور الفردية الوصول إليه بمفردها. تضمنت الخطوة النهائية قيام حاسوب كلاسيكي بأخذ المخرج الكمومي وإجراء فحص سريع وذكي لمعرفة ما إذا كان يمكن توسيع المجموعة لتصبح 15 شخصاً. نجح هذا النهج الهجين في استعادة الحد الأقصى المعتمد المكون من 15 شخصاً، وهي نتيجة لم يستطع المعالجة اللاحقة الكلاسيكية ولا الطريقة الكمومية القياسية تحقيقها بمفردهما.
لفهم سبب نجاح ذلك، أجرى الباحثون سلسلة من الاختبارات لاستبعاد التفسيرات الأخرى. فقد اختبروا ما إذا كانت المعالجة اللاحقة الكلاسيكية وحدها يمكن أن تجد الإجابة إذا أُعطيت بذرة واحدة فقط، وفشلت في كل مرة. كما اختبروا ما إذا كانت بنية الدائرة الكمومية نفسها هي المكون السحري عبر تشغيلها على بذور فردية، لكنها تعثرت أيضاً. وكان السبيل الوحيد للهروب من الفخ المحلي هو جعل الحاسوب الكمومي يعمل على تحسين جميع البذور في وقت واحد. وقد أكد هذا أن القوة جاءت من البحث المتوازي: فقد وجد الحاسوب الكمومي مجموعة من المعايير التي تعمل على تحسين جميع نقاط البداية الأربع في آن واحد، مما مكنه فعلياً من عبور مسار كان غير مرئي لأي نقطة بداية فردية.
استكشف الباحثون أيضاً ما إذا كانت الفروع المختلفة للتراكب يمكن أن تتداخل مع بعضها البعض لتضخيم أفضل الإجابات، وهي ظاهرة حيث تندمج الموجات الكمومية لجعل الإشارة أقوى. وقد أضافوا طبقة محددة من العمليات المصممة لخلق هذا التداخل ثم قاموا بقياس النتائج. وبينما تمكنوا من اكتشاف وجود المصطلحات المتقاطعة الكمومية، إلا أن التأثير كان ضئيلاً في عمليات المحاكاة الحالية. وأشار الباحثون إلى أنه لكي يكون هذا التداخل أكثر قوة، يجب أن تكون الحلول المختلفة متشابهة جداً في بنيتها، أو يجب أن تكون الدائرة الكمومية أكثر عمقاً. وقد وجدوا أن عمق الدائرة التي يمكنهم محاكاتها كان محدوداً بتعقيد التشابك، مما يشير إلى الحاجة إلى أجهزة مستقبلية ذات عدد أكبر من الكيوبتات واستقرار أفضل للاستفادة الكاملة من تأثير التداخل هذا.
تحقق الفريق من نتائجهم على أجهزة كمومية حقيقية لرسوم بيانية أصغر، حيث قاموا بتشغيل خوارزمياتهم على معالج "آي بي إم" يحتوي على 156 كيوبت. وحتى مع وجود الضجيج والأخطاء المتأصلة في الأجهزة الحالية، نجحت الطريقة في استعادة الحلول المثلى للرسوم البيانية ذات 64 و99 و125 عقدة. وقد أثبت هذا أن المسار قوي بما يكفي للعمل على الأجهزة الحقيقية، وليس فقط في المحاكاة المثالية. وبالنسبة للرسوم البيانية الأكبر، مثل حالة الـ 400 عقدة، اعتمد الفريق على محاكاة عالية الدقة لأن حجم المشكلة تجاوز قدرة الأجهزة الكمومية الحالية. وفي هذه المحاكاة، وجدوا أن زيادة عمق الدائرة الكمومية سمحت لهم بإيجاد مجموعات مستقلة أكبر، حيث وصلوا إلى حجم 25 في رسم بياني تكون فيه الإجابة المثالية هي 27. وهذا يشير إلى أنه مع ازدياد قوة الحواسيب الكمومية، ستستمر هذه الطريقة في التوسع.
يسلط هذا العمل الضوء على تحول في كيفية تصميم الخوارزميات الكمومية للمشكلات الصعبة. فبدلاً من محاولة إيجاد الإجابة من الصفر، قد تكون الاستراتيجية الأكثر فعالية هي استخدام الحواسيب الكلاسيكية لإيجاد نقاط بداية جيدة، ثم استخدام الحواسيب الكمومية لاستكشاف المساحة الموجودة بينها. لقد أظهر الباحثون أنه من خلال الجمع بين نقاط القوة لكليهما — الاستدلالات الكلاسيكية لإيجاد البذور، والتراكب الكمومي لاستكشاف الروابط بينها — يمكنهم حل مشكلات كانت بعيدة المنال سابقاً. ورغم أنهم لم يدّعوا حل مشكلة "المجموعة المستقلة القصوى" لجميع الرسوم البيانية الممكنة، إلا أنهم قدموا مساراً واضحاً وقابلاً للتكرار لحل أصعب الحالات في الرسوم البيانية الكثيفة، مما يوفر مخططاً لكيفية مواجهة الحواسيب الكمومية المستقبلية للتحديات التوليفية المعقدة.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.