أثبت يوفين تان البالغ من العمر 18 عامًا أن أجهزة الكمبيوتر الكلاسيكية يمكنها حل "مشكلة التوصية" بنفس سرعة أجهزة الكمبيوتر الكمومية تقريبًا. هذه النتيجة تبطل أحد أفضل الأمثلة على التسارع الكمي للحسابات.
حاصر مراهقون من تكساس تطور الحوسبة الكمومية. في مقال نشر هذا الشهر على الإنترنت
، أثبت يوفين تان البالغ من العمر 18 عامًا أن أجهزة الكمبيوتر العادية يمكنها حل مشكلة حسابية مهمة بسرعة
يمكن مقارنتها بأجهزة الكمبيوتر الكمومية.
في شكلها الأكثر عملية ، تتعلق مشكلة التوصية بكيفية تحديد الخدمات مثل Amazon و Netflix للمنتجات التي قد ترغب فيها. اعتبرها علماء الكمبيوتر
من أفضل الأمثلة على المهام التي يمكن حلها بشكل أسرع بشكل كبير على أجهزة الكمبيوتر الكمومية - والتي أكدت على
القدرات المحتملة لهذه الآلات المستقبلية. والآن دحض تان هذا الرأي.
يقول تانغ ، الذي تخرج من جامعة تكساس في أوستن في الربيع ويبدأ دراساته لنيل درجة الدكتوراه في جامعة واشنطن: "لقد كان أحد الأمثلة المحددة لتسارع الكم - والآن اختفى".
في عام 2014 ، في سن الرابعة عشرة ، قفز تانغ خلال الصفوف 4 و 5 و 6 ، ودخل جامعة تكساس ، حيث تخرج في الرياضيات وعلوم الكمبيوتر. في ربيع عام 2017 ، أخذ تان دورة في المعلومات الكمية ، قام بتدريسها
سكوت آرونسون ، الباحث
الشهير في مجال الحوسبة الكمومية. تعرف آرونسون على طالب موهوب بشكل غير عادي في تان ودعاه ليصبح مستشارًا له في مشروع بحثي مستقل. أعطى آرونسون تان عدة مهام للاختيار من بينها ، بما في ذلك مسألة التوصيات. اختارها تان على مضض إلى حد ما.
قال تان "لقد ترددت لأنه بدا معقدًا إلى حد ما ، ولكنه كان أبسط المهام التي اقترحها علي".
الهدف من التوصيات هو تقديم توصيات حول المنتجات التي قد يحبها المستخدم. فكر في Netflix. إنه يعرف الأفلام التي شاهدتها. إنه يعرف ما شاهده الملايين من مستخدميه. مع هذه المعلومات ، هل من الممكن معرفة ما تريد البحث عنه أكثر؟
يمكن تمثيل هذه البيانات في شكل شبكة ضخمة ، أو مصفوفة ، على رأسها جميع الأفلام المدرجة ، على الجانب جميع المستخدمين ، وداخلها هناك قيم تقيس مدى إعجاب كل مستخدم بكل فيلم. ستنتج الخوارزمية الجيدة قائمة بالتوصيات ، وستكشف بسرعة ودقة أوجه التشابه بين الأفلام والمستخدمين ، وتملأ الخلايا الفارغة للمصفوفة.
في عام 2016 ، نشر علماء الكمبيوتر
Iordanis Kerenidis و
Anupam Prakash خوارزمية كمية حلت مشكلة التوصية بشكل أسرع من أي خوارزميات كلاسيكية معروفة. لقد تلقوا مثل هذا التسارع الكمي ، على وجه الخصوص ، بسبب تبسيط المشكلة. بدلاً من ملء المصفوفة بالكامل وتحديد أفضل منتج يمكن التوصية به ، توصلوا إلى طريقة لتقسيم المستخدمين إلى عدد صغير من الفئات - هل يحبون الأفلام الضخمة أم السينما المستقلة؟ - ومعالجة البيانات الموجودة بطريقة تعطي توصية تكون ببساطة جيدة للغاية.
في الوقت الذي ظهر فيه عمل كيرينيديس وبراكاش ، كانت هناك أمثلة قليلة جدًا على المشكلات التي كان من المفترض أن تحلها أجهزة الكمبيوتر الكمومية بشكل أسرع من تلك الكلاسيكية. بالنسبة للجزء الأكبر ، كانت هذه المهام متخصصة - مشاكل ضيقة مصممة خصيصًا للاستفادة من نقاط قوة أجهزة الكمبيوتر الكمومية (بما في ذلك مشكلة "
الارتباط " التي كتبنا عنها بالفعل). كان عمل كيرينيديس وبراكاش مثيرًا للاهتمام لأنه سلط الضوء على مشكلة حقيقية ، مهمة للناس ، حيث تجاوزت أجهزة الكمبيوتر الكمومية تلك الكلاسيكية.
قال كيرينيديس ، متخصص في: "من وجهة نظري ، كان هذا أحد الأمثلة الأولى للتعلم الآلي ومعالجة البيانات الضخمة ، حيث أظهرنا أن أجهزة الكمبيوتر الكمومية يمكنها القيام بشيء لا نعرف حتى الآن كيفية القيام به باستخدام الأساليب الكلاسيكية". علوم الكمبيوتر من معهد باريس لأبحاث علوم الكمبيوتر.
أثبت كيرينيديس وبراكاش أن الكمبيوتر الكمومي يمكن أن يحل مشكلة التوصيات بشكل أسرع من أي خوارزميات معروفة ، لكنهما لم يثبتا أنه لا توجد خوارزمية كلاسيكية سريعة. لذلك ، عندما بدأ آرونسون العمل مع تان في عام 2017 ، طرح مهمة من هذا القبيل - لإثبات عدم وجود خوارزمية كلاسيكية سريعة ، مما يؤكد التسارع الكمي ل Kerenidis و Prakash.
قال آرونسون ، الذي كان يعتقد في ذلك الوقت أنه لا توجد خوارزمية كلاسيكية سريعة: "يبدو لي أن هذه ستكون نقطة مهمة سنستكملها لإكمال هذه القصة".
بدأ تانغ العمل في خريف عام 2017 ، على أمل أن تكون مهمة التوصيات هي موضوع أطروحته. لعدة شهور ، حاول تان إثبات استحالة وجود خوارزمية كلاسيكية. مر الوقت ، وبدأ تان يعتقد أنه ربما توجد مثل هذه الخوارزمية.
قال تان: "بدأت أؤمن بوجود الخوارزمية الكلاسيكية ، لكنني لم أستطع أن أقنع نفسي بذلك ، لأن سكوت اعتقد أنه غير موجود ، وكان سلطة بالنسبة لي".
أخيرًا ، عندما كان الموعد النهائي للرسالة ينفد بالفعل ، كتب تان رسالة إلى آرونسون ، حيث اعترف بشكوكه المتزايدة. قال آرونسون: "لقد كتب لي تان بشكل أساسي ما يلي: أعتقد أن هناك خوارزمية كلاسيكية سريعة".
طوال فصل الربيع ، كتب تانغ النتائج وعمل مع آرونسون لتوضيح بعض خطوات الإثبات. تم اكتشاف الخوارزمية الكلاسيكية السريعة بواسطة تان ، وهي مستوحاة من خوارزمية الكم السريعة التي عثر عليها كيرينيديس وبراكاش قبل عامين. أظهر تان أن أخذ العينات الكمية المستخدمة في الخوارزمية الخاصة بهم يمكن إعادة إنتاجه في الظروف الكلاسيكية. تم تنفيذ خوارزمية Tan ، مثل خوارزمية Kerenidis و Prakash ، في وقت متعدد الخوارزميات - أي تم تقدير وقت الحساب بواسطة لوغاريتم معلمات مثل عدد المستخدمين والمنتجات - وكان أسرع بشكل كبير من أي خوارزميات كلاسيكية معروفة سابقًا.
بعد الانتهاء من تان الخوارزمية ، أراد آرونسون التأكد من صحتها قبل النشر. وقال آرونسون: "كنت ما زلت متوترة بشأن حقيقة أنه إذا تبين أن نشر تان العمل غير صحيح ، فإن أول مهمة كبيرة في مسيرة تان ستصبح زيلك".
خطط آرونسون لحضور ورشة عمل الحوسبة الكمومية في جامعة كاليفورنيا في بيركلي في يونيو. كان من المقرر أن يتجمع النجوم في هذه المنطقة ، بما في ذلك Kerenidis و Prakash. دعا آرونسون ثان معه إلى بيركلي من أجل تقديم خوارزميته بشكل غير رسمي بعد الجزء الرسمي من المؤتمر.
في صباح 18 وصباح 19 يونيو ، ألقى تان محاضرتين ، ردا على أسئلة الجمهور. بعد أربع ساعات ، تم التوصل إلى توافق في الآراء: تبدو خوارزمية تان الكلاسيكية مثل الخوارزمية الصحيحة. ما لم يفهمه العديد من الحاضرين هو كيف كان تان صغيرًا. "لم أكن أعلم أن يوفين كان يبلغ من العمر 18 عامًا ، وبالتأكيد لم يبدو لي ذلك من نتائج المحادثات. يبدو لي أن جوفين كان يجري محادثة كرجل كامل النمو ”، قال كيرينيديس. الآن سيكون لدى الخوارزمية مراجعة نظيرة رسمية قبل نشرها.
بالنسبة للحوسبة الكمومية ، تكون نتيجة Tan خطوة إلى الوراء. أم لا. أزال تانغ أحد أكثر الأمثلة المفهومة وأفضلية للميزة الكمية. في الوقت نفسه ، يعد عمل تان دليلاً آخر على وجود
تفاعل مثمر بين دراسات الخوارزميات الكلاسيكية والكمية.
"تانغ يزيل التسارع الكمي لكل من كيرينيديس وبراكاش ، ولكن بمعنى آخر ، يساهم تانغ في تحسن كبير ويستند إلى عملهم. قال آرونسون ، إن تانغ لم يكن ليخرج أبداً بخوارزميته الكلاسيكية إذا لم ينشر الكم.