Polynomial Time Quantum Approximation Schemes for Constrained Optimization
تثبت هذه الورقة أن خط معالجة كمي-كلاسيكي مشوب بالضجيج، يعتمد على خوارزمية التحسين التقريبي الكمي المعززة بالقيود (Constraint-Enhanced QAOA)، والمدعومة بتضخيم اللقطات والإصلاح الحتمي، يشكل مخطط تقريب عشوائي كامل متعدد الحدود (FPRAS) ومخطط تقريب كمي متعدد الحدود في زمن (-PTQAS) للتحسين المقيد، مما يبرهن على ميزة كمية مثبتة على أجهزة أخذ العينات الكلاسيكية ويتحقق من صحة النهج على أجهزة بقدر 127 كيوبت.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي لبحث مسبق لم يخضع لمراجعة الأقران. وهو ليس نصيحة طبية. لا تتخذ أي قرارات تتعلق بصحتك بناءً على هذا المحتوى. اقرأ إخلاء المسؤولية الكامل
في عالم الحوسبة، هناك مشكلات ليست صعبة فحسب، بل هي من نوع خاص من المستحيلات التي لا تستطيع الآلات التقليدية حلها بسرعة. تُعرف هذه المشكلات بمسائل التحسين المقيدة. تخيل التخطيط لمسار توصيل لأسطول من الشاحنات؛ يجب عليك زيارة كل عميل مرة واحدة بالضبط، والبقاء ضمن حدود الوزن، والانتهاء في أسرع وقت ممكن. إن عدد المسارات الممكنة هائل لدرجة أن أقوى الحواسيب الفائقة ستستغرق وقتاً أطول من عمر الكون للتحقق منها جميعاً واحداً تلو الآخر. لعقود من الزمن، أمل العلماء أن تتمكن الحواسيب الكمومية، التي تستخدم القواعد الغريبة للجسيمات دون الذرية لمعالجة المعلومات، من اختراق هذا التعقيد. ومع ذلك، فإن الأجهزة الكمومية الحالية صاخبة وعرضة للخطأ؛ فهي غالباً ما تنتج إجابات مستحيلة رياضياً، مثل مسار يزور نفس المدينة مرتين أو يتخطى محطة بالكامل. وكان السؤال الكبير هو ما إذا كانت هذه الآلات غير المثالية لا تزال قادرة على أن تكون جزءاً من نظام موثوق يضمن حلاً جيداً في وقت معقول.
لقد أجاب فريق من الباحثين الآن على هذا السؤال من خلال بناء خط معالجة كامل يجمع بين حاسوب كمومي صاخب وحاسب كلاسيكي لحل هذه المشكلات الصعبة. لقد ركزوا على نوع محدد من الخوارزميات الكمومية يسمى (Constraint-Enhanced QAOA)، وهو مصمم لاحترام قواعد المشكلة أثناء البحث عن أفضل إجابة. وتظهر أعمالهم أنه حتى عندما ترتكب الآلة الكمومية أخطاء بسبب الضجيج، يمكن لبرنامج حاسوبي كلاسيكي ذكي أن يصلح تلك الأخطاء فوراً. ومن خلال فحص المخرجات الكمومية، وإصلاح أي مسارات مكسورة، وتقييم النت actually، يمكن للنظام العثور على الحل الأمثل بثقة عالية. وقد أثبت الباحثون رياضياً أن هذا النهج الهجين يعمل في وقت حدودي (polynomial time)، مما يعني أن الوقت الذي يستغرقه حل المشكلة ينمو بمعدل يمكن التحكم فيه مع زيادة حجم المشكلة، بدلاً من الانفجار إلى ما لا نهاية.
يكمن جوهر اكتشافهم في كيفية عمل الجزأين الكمومي والكلاسيكي معاً. يعمل الحاسوب الكمومي كأداة لأخذ العينات، حيث يولد عدداً هائلاً من الحلول المحتملة. وبسبب الضجيج في الآلة، تكون العديد من هذه العينات معيبة؛ فقد تنتهك قواعد المشكلة، مثل تخصيص شاحنتين لنفس الطريق أو ترك مدينة دون زيارة. في الماضي، ربما كان العلماء ببساال رمي هذه العينات السيئة، لكن ذلك من شأنه أن يهدر جهد الحاسوب الكمومي. بدلاً من ذلك، طور الباحثون طريقة يعمل فيها الحاسوب الكلاسيكي كورشة إصلاح؛ حيث يأخذ كل عينة، حتى المكسورة منها، ويستخدم تقنية رياضية معروفة لإصلاحها. فإذا كان المسار يفتقد مدينة أو يحتوي على تكرار، يقوم الحاسوب الكلاسيكي بإعادة ترتيب المسار لجعله صالحاً مرة أخرى، مما يضمن زيارة كل مدينة مرة واحدة بالضبط. عملية الإصلاح هذه سريعة وحتمية، مما يعني أنها تنتج دائماً نتيجة صالحة.
بمجرد إصلاح العينات، يقوم النظام بتقييمها لمعرفة أيها الأفضل. وقد أظهر الببحاث أن الحاسوب الكمومي، إذا تم ضبطه بشكل صحيح، ينتج طبيعياً عدداً أكبر من الحلول الجيدة مقارنة بالسيئة، حتى في بيئة صاخبة. وقد أثبتوا أنه من خلال تشغيل الدائرة الكمومية لمرات كافية، يضمن النظام العثور على الحل المثالي. كما أثبتوا أن عدد المرات التي تحتاج فيها الآلة للعمل للعثور على الإجابة ينمو بطريقة يمكن التنبؤ بها مع زيادة حجم المشكلة. وهذا يعني أن الطريقة ليست مجرد تخمين محظوظ، بل هي خوارزمية صارمة ذات ضمانات أداء. ويسمي الفريق هذا "مخطط تقريب عشوائي حدودي كامل"، وهو تعبير تقني يعني أنها طريقة موثوقة وسريعة لإيجاد إجابات شبه مثالية للمشكلات الصعبة.
لاختبار نظريتهم، أخذ الباحثون خوارزميتهم إلى أجهزة حقيقية. استخدموا معالجاً كمومياً بقدرة 127 كيوبت من شركة IBM، وهو جهاز متاح حالياً ولكنه لا يزال يعاني من ضجيج كبير. طبقوا نظامهم على مجموعة من مشكلات "البائع المتجول"، حيث الهدف هو إيجاد أقصر مسار يزور عدداً معيناً من المدن. تراوحت المشكلات من نماذج صغيرة مكونة من 16 متغيراً منطقياً إلى نماذج أكبر تضم 100 متغير. وعلى الرغم من البيئة الصاخبة، نجح النظام. فقد ولد الحاسوب الكمومي تدفقاً من البيانات الخام، وكان معظمها غير صالح. ثم قامت خطوة الإصلاح الكلاسيكية بإصلاح كل مسار من هذه المسارات غير الصالحة. كانت النتائج النهائية مبهرة: بالنسبة للمشكلات الأصغر، طابق النظام أفضل الحلول المعروفة تماماً. أما بالنسبة للمشكلات الأكبر والأكثر صعوبة، فقد وجد النظام مسارات أفضل من الحلول المرجعية المنشورة سابقاً.
استكشف الباحثون أيضاً كيفية جعل هذه العملية أسرع. لقد أدركوا أن الحاسوب الكمومي يميل إلى إنتاج عدد قليل من الإجابات الشائعة جداً والعديد من الإجابات النادرة. وبدلاً من فحص كل مسار تم إصلاحه، طوروا طريقة تصفية تركز فقط على المرشحين الأكثر تكراراً. هذا النهج المسمى "Heavy-hitter" قلل بشكل كبير من العمل الذي يتعين على الحاسوب الكلاسيكي القيام به، مما قلل من الوقت اللازم لمعالجة النتائج دون فقدان الضمان بالعثور على أفضل إجابة. هذا التحسين يجعل خط المعالجة بأكمله أكثر كفاءة، مما يشير إلى إمكانية توسيعه لمشكلات أكبر في المستقبل.
كان جزء حاسم من عملهم هو إثبات أن هذه الميزة تأتي من الحاسوب الكمومي نفسه، وليس فقط من خطوة الإصلاح الكلاسيكية. لقد أظهروا أنه إذا حاول حاسوب كلاسيكي بحت القيام بنفس المهمة — توليد مسارات عشوائية ثم إصلاحها — فإنه سيفشل في العثور على الحل الأمثل بكفاءة. إن قدرة الحاسوب الكمومي على تركيز احتماليته على أفضل الحلول هي ما يصنع الفرق. فبدون هذا الانحياز الكمومي، ستكون عملية الإصلاح الكلاسيكية بمثابة البحث عن إبرة في كومة قش. وتوضح الدراسة أن الآلة الكمومية توفر البداية القوية الضرورية، بينما يضمن الحاسوب الكلاسيكي أن تكون النتيجة قابلة للاستخدام.
تشير النتائج إلى طريقة جديدة للتفكير في الحوسبة الكمومية. فبدلاً من انتظار آلات مثالية وخالية من الأخطاء قد يستغرق ظهورها عقوداً، تظهر هذه الأعمال أنه يمكننا بناء أدوات قوية اليوم عبر دمج عينات كمومية صاخبة مع إصلاح كلاسيكي قوي. لا يتطلب النظام أن تكون الآلة الكمومية مثالية؛ بل يحتاج فقط لأن تكون منحازة نحو الإجابة الصحيحة. ومن خلال قبول الضجيج وبناء نظام يمكنه التعامل معه، خلق الباحثون مساراً عملياً لحل بعض أصعب مشكلات التحسين في العلوم والهندسة. وتعد دراستهم على معالج IBM Eagle-r3 دليلاً ملموساً على أن هذا النهج الهجين ليس مجرد نظرية، بل هو واقع وظيفي يمكنه بالفعل التفوق على المعايير الحالية في مشكلات العالم الحقيقي.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.