تعمل خوارزمية كمية جديدة على تسريع حل فئة كبيرة من المشاكل

النسخة الأصلية ل هذه القصة ظهرت في مجلة Quanta.

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

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

ولكن في ورقة تم نشرها على موقع Arxiv.org العلمي في العام الماضي ، وصف الباحثون ما يبدو وكأنه تسريع الكم مقنع ومفيد. وصف الباحثون خوارزمية كمية جديدة تعمل بشكل أسرع من جميع تلك الكلاسيكية المعروفة في إيجاد حلول جيدة لفئة واسعة من مشاكل التحسين (التي تبحث عن أفضل حل ممكن بين عدد هائل من الخيارات).

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

وقال رونالد دي وولف ، عالم الكمبيوتر النظري في CWI ، المعهد الوطني للبحوث للرياضيات وعلوم الكمبيوتر في هولندا ، الذي لم يشارك في الخوارزمية الجديدة: “أنا متحمس لذلك”. ولكن في الوقت نفسه ، حذر من أنه لا يزال من الممكن أن يجد الباحثون في النهاية خوارزمية كلاسيكية تعمل أيضًا. وبسبب عدم وجود أجهزة الكم ، لا يزال هناك بعض الوقت قبل أن يتمكنوا من اختبار الخوارزمية الجديدة تجريبياً.

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

أفضل طريقة للمضي قدما؟

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

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

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