← أحدث الأبحاث
⚛️ الفيزياء الكمومية

Proven optimality for LABS with quantum-classical branch and bound

تقدم هذه الورقة خوارزمية "الفرع والحد" (branch and bound) كمومية-كلاسيكية تستفيد من أخذ عينات خوارزمية التقدير الكمي للتحسين التقريبي (QAOA) بزاوية ثابتة لحل مشكلة تحسين المتواليات الثنائية ذات الارتباط الذاتي المنخفض (LABS)، حيث نجحت في إثبات الأمثلية العالمية لأطوال المتواليات التي تصل إلى 30، مع توفير حدود دنيا معتمدة ومقاييس تقارب دون الاعتماد على التسريع الكمي.

المؤلف الأصلي: András Czégel

نُشر 2026-11-20
📖 5 دقيقة قراءة🧠 قراءة متعمّقة

المؤلف الأصلي: András Czégel

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلف ولم يصادق عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

لقد أثبت باحث يدعى أندراس تشيجل (András Czégel) الآن طريقة لحل هذه المشكلة بيقين مطلق، باستخدام نهج هجين يمزج بين الحوسبة الكلاسيكية وأخذ العينات الكمومية. لا يدعي العمل أنه أسرع من الطرق التقليدية الأفضل؛ في الواقع، يصرح المؤلف صراحةً بأنه لا يوجد تسريع. بدلاً من ذلك، يكمن الإنجاز في البرهان. فمن خلال دمج خوارزمية كمومية داخل إطار بحث كلاسيكي صارم، أثبت الفريق الحلول المثلى للتسلسلات التي يتراوح طولها من 2 إلى 30. ويمثل هذا علامة فارقة لأن المحاولات الكمومية السابقة لهذه المشكلة لم تستطع سوى إيجاد تسلسلات جيدة، لكنها لم تستطع أبدًا ضمان أنها كانت الأفضل، كما لم تستطع قياس مدى بعد التخمين عن المثالية. توفر هذه الطة الجديدة شهادة على المثالية، وهي ضمان رياضي بأنه لا يوجد تسلسل أفضل، بالإضافة إلى قياس دقيق لكيفية تقارب البحث بمرور الوقت.

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

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

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

يمثل هذا العمل تحولًا في كيفية تقييم الخوارزميات الكمومية. فبدلاً من مجرد التسابق للعثور على إجابة جيدة بأسرع ما يمكن، ينصب التركيز هنا على تقديم إجابة موثقة ومعتمدة. سجل الباحثون عملية البحث بأكملها، وقاسوا الفجوة بين أفضل حل تم العثود عليه والحد الأدنى النظري في كل لحظة. يعمل هذا "التكامل الأولي-المزدوج" (primal-dual integral) كبطاقة تقييم لكفاءة الخوارزمية، حيث يوضح بدقة مدى سرعة تضييق الاحتمالات. تؤكد الدراسة أن أخذ العينات الكمومية يمكن دمجه في الخوارزميات الدقيقة لتوفير براهين على المثالية لمشكلات كانت تُحل سابقًا فقط بواسطة طرق تجريبية أو طرق كلاسيكية لا يمكن التحقق منها بوسائل كمومية. وبينما يظل نطاق المشكلات التي تم حلها حاليًا محدودًا بطول 30، وهو أقل بكثير من الـ 66 التي حققتها أفضل الطرق الكلاسيكية، فإن إثبات المفهوم واضح: يمكن للخوارزمية الكمومية الآن تقديم شهادة حقيقة، وليس مجرد تخمين.

غارق في أبحاث مجالك؟

تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.

جرّب Digest →