Polynomial-Space Quantum Algorithms from Classical Branching: Colouring, Domination and Monotone Local Search

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

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

يركز البحث على ثلاثة أنواع رئيسية من المسائل التي تظهر بشكل متكرر في علوم الحاسوب والرياضيات. الأول هو تلوين الرسم البياني (graph coloring)، والذي يسأل عما إذا كان يمكن تلوين خريطة بعدد محدود من الألوان بحيث لا يتشارك أي منطقتين متجاورتين نفس اللون. والثاني يتعلق بمسائل الهيمنة (domination problems)، والتي تسأل عن أصغر مجموعة من النقاط في شبكة يمكنها "مراقبة" أو الاتصال بكل نقطة أخرى. وتتضمن الفئة الثالثة المسائل التي يجب عليك فيها إزالة عناصر محددة لكسر الدورات أو إصلاح المشكلات الهيكلية، مثل إيجاد الحد الأدنى من الرؤوس التي يجب حذفها لإلغاء جميع الحلقات في شبكة. لكل من هذه المسائل، أخذ الباحثون أفضل الخوارزميات الكلاسيكية المعروفة، وهي خوارزميات سريعة بالفعل ولكنها لا تزال تتطلب وقتاً أسياً، وقاموا بتكييفها للحواسيب الكمومية. فعلوا ذلك من خلال إثبات أن المنطق خطوة بخطوة لهذه الخوارزميات الكلاسيكية يشكل نوعاً معيناً من الهياكل الشجرية. هذا الهيكل يسمح للحاسوب الكمومي باستخدام "المشي الكمومي" (quantum walk) للعثور على الحل في زمن يعادل تقريباً الجذر التربيعي للوقت الذي قد يستغرقه الحاسوب الكلاسيكي.

تعد النتائج بمثابة تقليل كبير في الوقت المطلوب لحل هذه المسائل. بالنسبة لمسألة التلوين الرباعي الكلاسيكية، يمكن للخوارزمية الكمومية الجديدة إيجاد حل في زمن يتناسب مع الرقم 1.3032 مرفوعاً لأس عدد الرؤوس. وهذا يمثل تحسناً ملموساً عن أفضل تقدير كمومي سابق وهو 1.3231. وبالنسبة للمسائل التي تتطلب ألواناً أكثر، مثل خمسة أو ما يصل إلى ثمانية عشر لوناً، فإن الطريقة الجديدة تتفوق باستمرار على الحدود القديمة، حيث ينمو الوقت المطلوب ببطء أكبر مع زيادة عدد الألوان. أما بالنسبة لمسائل الهيمنة، فإن التحسينات أكثر إثارة للإعجاب؛ إذ ينخفض الوقت اللازم لإيجاد مجموعة مهيمنة من حوالي 1.4969 (في أفضل تقدير سابق) إلى 1.2235، وبالنسبة لإيجاد مجموعة مهيمنة مستقلة، ينخفض إلى 1.1583. قد تبدو هذه الأرقام مجردة، ولكن في عالم النمو الأسي، يترجم أي انخفاض بسيط في الرقم الأساسي إلى توفير هائل في وقت الحوسبة الفعلي للشبكات الكبيرة.

كما طبق الباحثون هذا المنطق على تقنية تسمى "البحث المحلي الرتيب" (monotone local search)، والتي تُستخدم للمسائل التي تبدأ فيها بحل جزئي وتحاول توسيعه ليصل إلى حل كامل. ومن خلال دمج هذه التقنية مع البحث الكمومي، أنشأوا طريقة جديدة تحل مسائل مثل إيجاد الحد الأدنى من الرؤوس التي يجب حذفها لكسر جميع الدورات في رسم بياني. بالنسبة لهذه المسألة تحديداً، فإن الوقت الكمومي الجديد هو تقريباً 1.3081 مرفوعاً لأس عدد الرؤوس، مما يمثل أول حد كمومي معروف لهذا النهج، حيث لم يتم ذكر أي شكل سابق للبحث المحلي الرتيب الكمومي. ولعل الأمر الأكثر إثارة للاهتمام هو أن الفريق أظهر أن هذا النهج لا يعمل فقط لإيجاد الحل المثالي الدقيق، بل أيضاً لإيجاد حلول "جيدة بما يكفي" (approximations). فعلى سبيل المثال، أظهروا طريقة لإيجاد حل لمسألة "الغطاء الرأسي" (vertex cover) يكون أكبر بنسبة 10 بالمائة فقط من الإجابة المثالية، ولكن يمكن إيجاده في زمن يتناسب مع 1.0555 مرفوعاً لأس عدد الرؤوس. وهذا أسرع من إيجاد الحل الدقيق، مما يوفر مقايضة عملية للتطبيقات الواقعية حيث تكون الإجابة القريبة من المثالية كافية في كثير من الأحيان.

وثمة جانب حاسم في هذا العمل وهو القيد الصارم على الذاكرة. فقد صُممت الخوارزميات لتعمل بـ "مساحة حدودية"، مما يعني أن كمية الذاكرة التي تحتاجها تنمو بمعدل يمكن التحكم فيه مع كبر حجم المسألة. وهذا قيد حيوي لأن الحواسيب الكمومية الحالية والقريبة المستقبلية لن تمتلك سعة الذاكرة الضخمة المطلوبة من قبل خوارزميات كمومية نظرية أخرى تعتمد على "ذاكرة الوصول العشوائي الكمومية" (quantum random access memory). ومن خلال تجنب هذا المتطلب، خلق الباحثون مساراً أكثر واقعية للأجهزة التي ستوجد بالفعل. وقد تحققوا من نتائجهم باستخدام مزيج من البراهين الرياضية والمحاكاة الحاسوبية، للتأكد من أن الخوارزميات تعمل بشكل صحيح على الرسوم البيانية العشوائية وأن تقديرات الوقت تصمد أمام التدقيق. لا يدعي العمل أنه حل هذه المسائل بطريقة تجعلها سهلة لأي حاسوب، بل إنه دفع حدود الممكن، موضحاً أن الآلات الكمومية يمكنها معالجة هذه الألغاز الصعبة ذات الوقت الأسي بمستوى من الكفاءة كان يُعتقد سابقاً أنه يتطلب ذاكرة أكثر مما هو ممكن.

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