أخيرًا ، كانت هناك مشكلة لا يمكن حلها سوى أجهزة الكمبيوتر الكمومية

لسنوات ، كان علماء الكمبيوتر يبحثون عن مهام من نوع معين لن يتمكن سوى الكمبيوتر الكمومي من حلها ، ولكن ليس الكمبيوتر الكلاسيكي ، حتى من الأجيال القادمة. ووجدوا أحدهم.

في المراحل الأولى من دراسة أجهزة الكمبيوتر الكمومية ، سأل علماء الكمبيوتر سؤالًا ، كان الجواب ، في رأيهم ، يكشف عن بعض الحقيقة العميقة حول قدرات هذه الآلات المستقبلية. بعد 25 سنة ، تم العثور على إجابة عليه. في ورقة نشرت في مايو 2018 ، قدم علماء الكمبيوتر Ren Rez و Avishai Tal أدلة دامغة على أن قوة الحوسبة لأجهزة الكمبيوتر الكمومية تفوق أي شيء يمكن أن تحققه أجهزة الكمبيوتر الكلاسيكية.

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

منذ ذلك الحين ، كانوا يأملون في مقارنة فئة مهام BQP المعروفة باسم PH ، والتي تتضمن جميع المهام التي يمكن إجراؤها على أي كمبيوتر كلاسيكي ، حتى تلك المتقدمة بشكل لا يصدق التي طورتها بعض حضارات المستقبل. تعتمد إمكانية مثل هذا التباين على إيجاد مشكلة تنتمي إلى فئة BQP ، ولكن ليس لفئة PH. والآن قام بها ريز وتال.

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

فئات الكم

المهمة الأساسية للمعلوماتية النظرية هي تقسيم المهام إلى فئات معقدة. تحتوي فئة التعقيد على جميع المهام التي يمكن حلها بمورد معين ، مثل الوقت أو الذاكرة.

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

فئتان صعوبة مشهورتان هما P و NP. P هي جميع المهام التي يمكن للكمبيوتر الكلاسيكي حلها بسرعة. (المشكلة هي "الرقم الأولي؟" ينتمي إلى P). يتضمن NP جميع المهام التي لا يحلها الكمبيوتر الكلاسيكي بالضرورة بسرعة ، ولكن صحة الحل الحالي ، والذي يمكن التحقق منه بسرعة. ("ما هي العوامل الرئيسية للرقم؟" ينتمي إلى NP). يعتقد العلماء أن الفئتين P و NP مختلفتان ، لكن مهمة إثبات هذا الاختلاف هي أصعب وأهم المشكلات المفتوحة في هذا المجال.


يحتوي PH على NP يحتوي على P. هل BQP فئة منفصلة عن PH؟

في عام 1993 ، حدد علماء الكمبيوتر إيثان بيرنشتاين وأوميش وزيراني فئة جديدة من التعقيد ، أطلقوا عليها BQP ، أو "الوقت متعدد الحدود الكمية مع الحد من احتمال الخطأ". عرّفوا الفصل على أنه يحتوي على جميع مهام صنع القرار - المهام ذات الإجابة "نعم" أو "لا" - التي تستطيع أجهزة الكمبيوتر الكمومية حلها بفعالية. في نفس الوقت تقريبًا ، أثبتوا أن أجهزة الكمبيوتر الكمومية قادرة على حل جميع المهام التي يمكن للحواسيب الكلاسيكية القيام بها. أي أن BQP يحتوي على جميع المهام الواردة في P.

مثال آخر على فئات المهام الفردية. تسأل مشكلة البائع إذا كان المسار الذي يمر عبر مدن معينة أقصر من مسافة معينة. هذه المهمة في NP. تسأل مهمة أكثر صعوبة ما إذا كانت هذه المسافة هي أقصر مسار عبر هذه المدن. مثل هذه المهمة في PH.

ومع ذلك ، لم يتمكنوا من تحديد ما إذا كان BQP يحتوي على مهام ليست في فئة مهمة أخرى من المهام ، والمعروفة باسم PH أو "التسلسل الهرمي متعدد الحدود". PH هو تعميم NP. يحتوي على جميع المهام التي يمكن الحصول عليها من خلال البدء بمهمة من NP ، وتعقيدها ، وإضافة عبارات توضيحية مثل "سواء" و "للجميع". لا تزال أجهزة الكمبيوتر الكلاسيكية لا تستطيع حل معظم المشكلات من PH ، ولكن يمكن اعتبار هذا الفصل فئة من المشاكل التي يمكن أن تحلها أجهزة الكمبيوتر الكلاسيكية إذا اتضح أن P تعادل NP. وبعبارة أخرى ، لمقارنة BQP و PH ، من الضروري تحديد ما إذا كانت أجهزة الكمبيوتر الكمومية لها ميزة على أجهزة الكمبيوتر الكلاسيكية ، والتي ستبقى حتى إذا تعلمت أجهزة الكمبيوتر الكلاسيكية فجأة حل مشاكل أكثر بكثير مما يمكنها حلها اليوم.

قال سكوت أرونسون ، أخصائي تكنولوجيا المعلومات في جامعة تكساس في أوستن: "إن PH هو أحد أبسط فئات التعقيد الموجودة". "لذا نريد نوعًا ما معرفة مكان الحوسبة الكمومية في عالم من التعقيد الكلاسيكي."

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

وقال آرونسون: للعثور على مهمة تنتمي إلى BQP ، ولكن ليس إلى PH ، تحتاج إلى تحديد شيء "لا يمكن للكمبيوتر الكلاسيكي ، بحكم تعريفه ، التحقق من الإجابة بشكل فعال ، ناهيك عن العثور عليها". "هذا يلغي العديد من المهام التي نعمل معها في علوم الكمبيوتر."

اسأل أوراكل

التحدي. لنفترض أن لدينا اثنين من مولدات الأرقام العشوائية ، ينتج كل منها سلسلة من الأرقام. سؤال للكمبيوتر: هل هذان التسلسلان مستقلان تمامًا عن بعضهما البعض ، أم أنهما مرتبطان بشكل غير محسوس (على سبيل المثال ، هل حصل أحد التسلسل بواسطة تحويل فورييه للآخر)؟ قدم آرونسون مهمة "furrelation" في عام 2009 وأثبت أنه ينتمي إلى BQP. تبقى الخطوة الثانية الأكثر صعوبة - لإثبات أن النخر غير مدرج في PH.


ران ريز

هذا هو بالضبط ما فعله Resu و Talu. عملهم يفصل بين BQP و PH بمساعدة ما يسمى ب " أوراكل " أو "الصندوق الأسود". هذه نتيجة شائعة في علوم الكمبيوتر ، والتي لجأ إليها الباحثون عندما لا يتم منحهم ما يريدون إثباته بأي شكل من الأشكال.

أفضل طريقة لفصل فئتي التعقيد في درجة BQ و PH هي قياس الوقت الحسابي المطلوب لحل المشاكل من كل فئة. لكن هنري يون ، عالم الكمبيوتر في جامعة تورونتو ، قال إن علوم الكمبيوتر ليس لديها "فهم عميق لوقت الحوسبة الحقيقي أو القدرة على قياسه".

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

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

"بمعنى ما ، نحن نفهم هذا النموذج بشكل أفضل. قالت تال إنها تتحدث عن المعلومات أكثر مما تتحدث عن الحوسبة.


أفيشاي تال

يثبت العمل الجديد لـ Reza and Tal أن الكمبيوتر الكمومي سيحتاج إلى عدد أقل بكثير من القرائن لحل مشكلة النشوة من المشكلة الكلاسيكية. علاوة على ذلك ، يحتاج الكمبيوتر الكمومي إلى تلميح واحد فقط ، على الرغم من حقيقة أن PH ليس لديه خوارزمية لحل هذه المشكلة ، حتى مع عدد غير محدود من التلميحات. قال ريز: "هذا يعني أن هناك خوارزمية كمية فعالة للغاية تحل مثل هذه المشكلة". "ولكن إذا أخذنا في الاعتبار الخوارزميات الكلاسيكية فقط ، فعندئذ حتى لو وصلنا إلى أعلى فئات الخوارزميات الكلاسيكية ، فلن يتمكنوا من التأقلم معها". هذا يثبت أنه مع أوراكل ، يشير التحريك إلى المهام التي تنتمي إلى BQP ، ولكن ليس إلى PH.

توصل Rez و Tal تقريبًا إلى هذه النتيجة قبل حوالي أربع سنوات ، لكنهما لم يتمكنا من اتخاذ خطوة واحدة في الدليل المستقبلي. وبعد ذلك ، قبل شهر واحد فقط من النشر ، سمع تال عن عمل جديد حول مولدات الأرقام العشوائية الزائفة ، وأدرك أن التقنيات من هذا المقال تعطي ما يحتاجه هو وريز لإنهاء عملهما. قال تال "لقد كانت قطعة مفقودة".

انتشرت أخبار فصل فئتي BQP و PH بسرعة. كتب لانس فورتناو ، أخصائي تكنولوجيا المعلومات في جامعة جورجيا للتكنولوجيا بعد يوم واحد من نشر العمل ، "عالم التعقيد الكمي صاخب".

يمنح العمل ثقة حديدية بوجود أجهزة كمبيوتر كمومية في عالم حوسبي منفصل عن العالم الحاسوبي الكلاسيكي (على الأقل من خلال التعريف مع أوراكل). حتى في عالم حيث P تعادل NP - حيث يكون حل مشكلة البائع المتجول أمرًا بسيطًا مثل العثور على الخط الأكثر ملاءمة في جدول البيانات - يوضح الدليل من قبل رضا وتال أن هناك مشاكل لا يمكن إلا للكمبيوتر الكمومي حلها.

قال فورتناو: "حتى لو كانت P تعادل NP ، حتى مع وجود مثل هذا الافتراض القوي ، فلن تستمر أجهزة الكمبيوتر الكمومية في اللحاق بالركب".