في عام 1994 ، اكتشف عالم رياضيات كيفية جعل الكمبيوتر الكمومي يفعل شيئًا لا يستطيع أي كمبيوتر تقليدي عادي القيام به. كشف العمل أنه ، من حيث المبدأ ، يمكن لآلة تعتمد على قواعد ميكانيكا الكم أن تقسم بكفاءة عددًا كبيرًا إلى عواملها الأولية - وهي مهمة صعبة للغاية بالنسبة للحاسوب الكلاسيكي لدرجة أنها تشكل الأساس لمعظم أمن الإنترنت اليوم.
تلا ذلك موجة من التفاؤل. ربما اعتقد الباحثون أننا سنكون قادرين على ابتكار خوارزميات كمومية يمكنها حل مجموعة كبيرة من المشكلات المختلفة.
لكن التقدم توقف. قال: "لقد كان مسارًا مشؤومًا بعض الشيء" رايان أودونيل من جامعة كارنيجي ميلون. "كان الناس مثل ،" هذا مذهل ، أنا متأكد من أننا سنحصل على جميع أنواع الخوارزميات الرائعة الأخرى. " لا." اكتشف العلماء تسريعًا دراماتيكيًا فقط لفئة واحدة ضيقة من المشكلات من داخل مجموعة قياسية يسمى NP، مما يعني أن لديهم حلولًا يمكن التحقق منها بكفاءة - مثل العوملة.
كان هذا هو الحال لما يقرب من ثلاثة عقود. ثم في أبريل ، الباحثون اخترع نوع جديد جوهريًا من المشكلات التي يجب أن يكون الكمبيوتر الكمومي قادرًا على حلها بشكل أسي أسرع من الحل التقليدي. إنها تتضمن حساب المدخلات لعملية حسابية معقدة ، تعتمد فقط على مخرجاتها المختلطة. لم يتم بعد تحديد ما إذا كانت المشكلة قائمة بذاتها أو أنها الأولى في جبهة جديدة للعديد من المشكلات الأخرى.
قال "هناك شعور بالإثارة" فينود فايكونتاناثان، عالم كمبيوتر في معهد ماساتشوستس للتكنولوجيا. "يفكر الكثير من الناس في ما هو موجود أيضًا."
يحاول علماء الكمبيوتر فهم ما تفعله أجهزة الكمبيوتر الكمومية بشكل أفضل من خلال دراسة النماذج الرياضية التي تمثلها. في كثير من الأحيان ، يتخيلون نموذجًا لحاسوبًا كميًا أو كلاسيكيًا مقترنًا بآلة حساب مثالية تسمى أوراكل. تشبه Oracles وظائف رياضية بسيطة أو برامج كمبيوتر ، حيث تأخذ مدخلات وتبصق ناتجًا محددًا مسبقًا. قد يكون لديهم سلوك عشوائي ، حيث يتم إخراج "نعم" إذا كان الإدخال يقع ضمن نطاق عشوائي معين (على سبيل المثال ، من 12 إلى 67) و "لا" إذا لم يكن كذلك. أو قد تكون دورية ، بحيث يؤدي الإدخال بين 1 إلى 10 إلى "نعم" ، وإرجاع 11 إلى 20 "لا" ، وإرجاع 21 إلى 30 "نعم" مرة أخرى ، وهكذا.
لنفترض أن لديك واحدة من هذه الأوراكل الدورية ولا تعرف الفترة. كل ما يمكنك فعله هو إطعامها بالأرقام ومعرفة ما ستخرجه. مع هذه القيود ، ما مدى السرعة التي يمكن أن يجدها الكمبيوتر في هذه الفترة؟ في عام 1993 ، وجد دانيال سيمون ، الذي كان يعمل وقتها في جامعة مونتريال ، أن الخوارزمية الكمومية يمكنها حساب الإجابة على مشكلة وثيقة الصلة بشكل أسرع من أي خوارزمية كلاسيكية.
مكنت النتيجة سايمون من تحديد واحدة من أولى التلميحات إلى أين يمكن توقع التفوق الهائل لأجهزة الكمبيوتر الكمومية. لكن عندما قدم ورقته إلى مؤتمر قيادي ، تم رفضها. ومع ذلك ، فقد اهتمت الورقة بعضو صغير في لجنة برنامج المؤتمر - بيتر شور، الذي كان في ذلك الوقت في مختبرات بيل في نيوجيرسي. ذهب شور ليجد أنه يمكنه تكييف خوارزمية سيمون لحساب فترة أوراكل ، إذا كان لديه واحد. ثم أدرك أنه يمكنه تكييف الخوارزمية مرة أخرى ، لحل معادلة تتصرف بشكل مشابه للوراثة الدورية: المعادلة التي تصف التحليل ، وهي دورية.
كانت نتيجة شور تاريخية. يمكن للخوارزمية الكمومية التي اكتشفها أن تقلل بسرعة من الأرقام الضخمة إلى عواملها الأولية المكونة لها ، وهو أمر لا يمكن لأي خوارزمية كلاسيكية معروفة القيام به. في السنوات التي تلت ذلك ، اكتشف الباحثون خوارزميات كمومية أخرى فعالة. حتى أن بعضها ، مثل خوارزمية شور ، قدم ميزة أسية ، لكن لم يستطع أحد إثبات ميزة كمية كبيرة في أي مشكلة NP لم تكن دورية.
قادت ندرة التقدم اثنين من علماء الكمبيوتر ، سكوت هارونسون من جامعة تكساس ، أوستن ، و أندريس أمبينيس من جامعة لاتفيا ، لإبداء ملاحظة. بدت البراهين على الميزة الكمومية تعتمد دائمًا على الأوراكل التي لها نوع من البنية غير العشوائية ، مثل الدورية. في عام 2009 ، هم تكهنت أنه لا يمكن أن يكون هناك تسريع كبير في مشاكل NP التي كانت عشوائية أو غير منظمة. لا أحد يمكن أن يجد استثناء.
وضع تخمينهم قيودًا على قوى أجهزة الكمبيوتر الكمومية. لكنها قالت فقط أنه لا توجد تسريع دراماتيكي لنوع معين من مشاكل NP غير المنظمة - أولئك الذين لديهم إجابات بنعم أو لا. إذا كانت هناك مشكلة تتعلق باكتشاف إجابات كمية أكثر تحديدًا ، والتي تُعرف بمشكلة البحث ، فإن التخمين لا ينطبق.
مع وضع ذلك في الاعتبار ، الباحثين تاكاشي ياماكاوا NTT Social Informatics Laboratories and مارك زاندري من NTT Research وجامعة برينستون قررت تجربة مشكلة بحث محددة ، تم تقديمها في عام 2005 بواسطة عوديد ريجيف.
تخيل مجموعة من دوارات الطقس التي تشير جميعها في نفس الاتجاه. امنح كل منهم دفعة محسوبة ، ثم دع الرياح العاصفة تؤثر على اتجاههم. أراد ريغيف أن يحدد ، بناءً على اتجاهاتهم النهائية ، إلى أين أشاروا جميعًا في البداية. أصبحت مشاكل مثل هذه تسمى "التعلم بالأخطاء" ، لأن الريح والرياح تعمل كمصدر للخطأ العشوائي في الاتجاه الأصلي. هناك أدلة على أنه من الصعب حل كل من الخوارزميات الكلاسيكية والكمية.
قام Yamakawa و Zhandry بتعديل الإعداد. لقد قاموا بتعديل قوة تلك الدفعات البادئة ، مما جعلها أكثر قابلية للتنبؤ بها. لقد تسببوا أيضًا في تحديد الريح بواسطة أوراكل عشوائي بحيث تكون أكثر عشوائية في بعض الحالات ولكنها نائمة تمامًا في حالات أخرى.
مع هذه التعديلات ، اكتشف الباحثون أن الخوارزمية الكمومية يمكنها إيجاد الاتجاه الأولي بكفاءة. لقد أثبتوا أيضًا أن أي خوارزمية كلاسيكية يجب أن تكون أبطأ بعامل أسي. مثل شور ، قاموا بعد ذلك بتكييف الخوارزمية الخاصة بهم لحل نسخة حقيقية من المشكلة ، والتي تستبدل أوراكل بمعادلة رياضية فعلية.
لا يزال علماء الكمبيوتر يعملون على فهم المشكلة والبناء عليها. يقارنها Vaikuntanathan بأخرى مختلفة تنشأ عند ضغط البيانات: عندما يتم ضغط المعلومات ، يمكن ضغط بتتين بطريق الخطأ في نفس المكان ، والكتابة عليها. إن مشكلة التنبؤ بهذه الاصطدامات مقدمًا ، حتى تتمكن من تجنبها ، تحمل بعض التشابه. قال: "هذه فئة من المشاكل تبدو في الأساس هكذا". "ربما يمكن حل هذه المشاكل كمياً."
كانت هناك آمال في إمكانية حل مشكلة غير منظمة مثل المشكلة الجديدة حتى في الإصدارات الوليدة من أجهزة الكمبيوتر الكمومية ، وبالتالي توفير وسيلة لاختبارها. كان التفكير هو أن المشكلات غير المنظمة قد تتطلب موارد أقل للبرمجة ، أو تكون أقل حساسية للضوضاء ، لأنها عشوائية بالفعل. ولكن حتى الآن ، لا تزال المشكلة الجديدة تبدو متقدمة جدًا بحيث يتعذر على أجهزة الكمبيوتر الكمومية الموجودة حلها. إنها مشكلة غريبة. قال آرونسون "لم أفكر في تعريفه". "ولكن بالنظر إلى الماضي ، فإنه يحتوي على بعض الميزات الرائعة جدًا."
توفر النتيجة المثال الأول للميزة الكمية الهائلة في مشكلة NP غير المنظمة. هل يمكن أن يكون هناك العديد من المشكلات الأخرى التي يتغير بها العالم الكمي من غير قابل للحل عمليًا إلى قابل للحل؟ هناك الآن سبب آخر للاعتقاد بذلك.
قال أودونيل: "لقد قلبت إلى حد ما معتقداتنا حول أنواع المشاكل التي يمكن أن تكون الحواسيب الكمومية جيدة فيها".
