Exact Spin Elimination for Quadratic and k-Local Ising Optimization

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

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

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

اختبر الباحثون هذه الطريقة على نوعين من المشكلات الصعبة. تضمن النوع الأول شبكات من المفاتيح حيث يتفاعل كل منها مع ثلاثة أخرى بالضبط، وهو إعداد يُعرف باسم "زجاج مغزلي متناثر" (sparse spin glass). وتضمن النوع الثاني تفاعلات بين مجموعات من ثلاثة مفاتيح في آن واحد. وفي هذه الاختبارات، قارن الباحثون النهج القياسي مقابل طريقة الحذف الجديدة باستخدام "محلل التلدين المحاكي" (simulated annealing solver)، وهو نوع من الخوارزميات يحاكي تبريد المعادن لإيجاد حالات مستقرة. أجروا آلاف المحاولات مع تحديد وقت ثابت لكل محاولة. وكانت النتائج مذهلة؛ فبالنسبة لمشكلات التفاعل الثلاثي، قفز معدل النجاح في إيجاد الحل الأفضل من حوالي 17 بالمائة إلى 87.5 بالمائة. أما بالنسبة لمشكلات التفاعل الثنائي الأبسط، فقد ارتفع معدل النجاح من حوالي 10 بالمائة إلى ما يقرب من 98 بالمائة. وقد ظل هذا التحسن قائمًا حتى بعد احتساب الوقت الذي قضاه الكمبيوتر في إعداد المشكلة المختصرة. وفي الواقع، انخفض الوقت المطلوب لإيجاد الحل بمعامل قدره حوالي 34 للمشكلات الأبسط و11 للمشكلات الأكثر تعقيدًا.

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

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

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

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