علماء الكمبيوتر توسيع نطاق اختبار المعرفة

نما الكون المهام فحص الكمبيوتر. بفضل العنصر السري الذي حدث هذا؟ بسبب التشابك الكم.

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

هذه هي المشكلة الرئيسية لعلوم الكمبيوتر. يصعب حل بعض المهام في فترة زمنية معقولة. لكن قراراتهم سهلة التحقق. في ضوء ذلك ، يريد علماء الكمبيوتر معرفة: ما مدى تعقيد المهمة ، وما زال يمكن التحقق من حلها؟

اتضح أن الإجابة على هذا السؤال هي: معقدة بشكل لا يمكن تصوره.

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

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

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

إلى نهاية الكون

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



مهمة ثلاثة ألوان من الصعب حلها. في الحالة العامة ، يزيد الوقت المطلوب للبحث عن تلوين القمم (أو تحديد عدم وجود مثل هذا التلوين) بشكل كبير مع زيادة حجم الرسم البياني. على سبيل المثال ، إذا كان البحث عن حل للرسم البياني ذي 20 رأسًا يستغرق 3 ثوانٍ ، أي بضع ثوانٍ ، فإن الرسم البياني ذو 60 رأسًا سيستغرق 3 ⁶⁰ ثانية ، وهو 100 مرة من عمر الكون الحالي.

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

وقال جون رايت ، عالم فيزياء بمعهد ماساتشوستس للتكنولوجيا ، الذي كتب هذا العمل مع أناند ناتاراجان من معهد كاليفورنيا للتقنية "مع اللون المناسب بثلاثة ألوان ، من السهل اختبار أدائه".

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

الأسئلة الصحيحة

قبل عمل ناتاراجان ورايت ، زادت قوة عمليات التفتيش في قفزتين كبيرتين.

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

ومع ذلك ، يُسمح لك بطرح أسئلة إثبات هذا الشخص. لنفترض أن الموصل يخبرك أن المكعبات لها ألوان مختلفة. يمكنك استدعاء واحد منهم "المكعب A" والآخر "المكعب B". ثم تقوم بإخفائها خلف ظهرك ، وتقوم بمبادلة الأماكن بينها عن طريق الخطأ. ثم تفتح المكعبات وتطلب من prover العثور على يموت A.

إذا كانت المكعبات بألوان مختلفة ، فهذا سؤال بسيط للغاية. سوف يتعرف prover على Cube A ، إذا كان هذا ، على سبيل المثال ، مكعب أحمر ، وسيحدده بشكل صحيح في كل مرة.

ومع ذلك ، إذا كانت المكعبات من نفس اللون - وكان الخطأ قد أخطأ في وصفها بأنها مختلفة - لا يمكن للمهندس أن يخمن أي منهما هو الآخر. لذلك ، سيكون قادرًا على تحديد المكعب A بشكل صحيح في 50٪ فقط من الحالات. من خلال استجواب المطرب باستمرار حول قراره ، يمكنك تأكيد ما إذا كان صحيحًا.


أناند ناتاراجان وجون رايت

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

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

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

وقال رايت: "لن يتمكن المشتبه بهما من إنشاء قصة ثابتة موزعة ، لأنهما لا يعرفان الإجابات الأخرى".

في عام 1988 ، أثبت أربعة علماء كمبيوتر أنه إذا طلبت من جهازي كمبيوتر حل نفس المشكلة بشكل منفصل ثم استجوابهما بشكل منفصل ، فيمكنك تأكيد فئة من المشكلات أكبر من IP: فئة MIP ، دليل تفاعلي مع الكثير من الأدلة.

باستخدام هذا النهج ، من الممكن ، على سبيل المثال ، تأكيد صحة تلوين رسم بياني بثلاثة ألوان لتسلسل الرسوم البيانية التي تزيد في حجمها أسرع بكثير من الرسوم البيانية من NP. في NP ، تزداد أحجام الرسم البياني خطيًا - يمكن أن يزيد عدد القمم من 1 إلى 2 ، إلى 3 ، إلى 4 ، وهكذا - بحيث لا يكون حجم الرسم البياني أكبر بشكل غير متناسب من مقدار الوقت المطلوب للتحقق من التلوين. لكن في MIP ، يزداد عدد رؤوس الرسم البياني أضعافا مضاعفة من 2 ¹ إلى 2 ² ، 2 ³ ، 2 ⁴ ، وهكذا.

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

في MIP ، يمتلك المختبر ذاكرة كافية لتشغيل برنامج يسمح لنا بتحديد ما إذا كان رأسان الرسم البياني متصلان بواسطة حافة - ويمكنه التحقق من إجابات المختبرين للتأكد من صحة التلوين.

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

العمل الجديد لناتراجان ورايت لديه إجابة على هذا السؤال.

الحيل الكمومية

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

في عملهم الجديد ، يفكر ناتاراجان ورايت في سيناريو يتضمن جهازي كمبيوتر كوانتين مختلفين ، مع تشويش الكبتات الخاصة بأحد الكبتات الأخرى.

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

في الواقع ، عندما تم الكشف عن السيناريو مع جهازي كمبيوتر كمومية متشابكة لأول مرة في عام 2003 ، اقترح علماء الكمبيوتر أن التشابك من شأنه أن يقلل من إمكانية التحقق. وقال فيديك: "كان رد فعل الجميع الواضح ، بما في ذلك أنا ، هو أن المتسابقين في هذه القضية لديهم المزيد من الفرص". "يمكنهم استخدام الارتباك لربط إجاباتهم".

لكن على الرغم من التشاؤم المبدئي ، أمضى فيديك عدة سنوات في محاولة لإثبات العكس. في عام 2012 ، أثبت هو و Tsuyoshi Ito أن القدرة على اختبار جميع المهام في MIP باستخدام أجهزة الكمبيوتر الكم المتشابكة موجودة.

الآن ، أثبت كل من ناتاراجان ورايت أن الوضع أفضل: فبفضل التعقيد ، يمكن للمرء أن يثبت وجود فئة أكبر من المشاكل أكثر من عدمه. من الممكن عكس الاتصال بين أجهزة الكمبيوتر الكمومية المتشابكة لصالح المدقق.

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

في فئة المشكلات التي نظر فيها Natarajan و Wright - والمعروفة باسم NEEXP ، وهو زمن غير متضاعف مرتين - يزداد حجم الرسوم البيانية بشكل أسرع من MIP. الرسوم البيانية في NEEXP تنمو بمعدل مضاعف. بدلاً من النمو كدرجات من 2 - 2 ¹ ، 2 ² ، 2 ³ ، 2 ⁴ ، وهكذا - ينمو عدد الرؤوس في الرسوم البيانية مع تزايد درجات اثنين - 2 ^{2 1} ، 2 ^{2 2} ، 2 ^{2 3} ، 2 ^{2 4} ، وهلم جرا. نتيجة لذلك ، اتضح أن الرسوم البيانية بسرعة كبيرة لدرجة أن المفتش لم يعد قادرًا على العثور على زوج من الرؤوس المتصلة.

وقال ناتاراجان: "لتحديد قمة الرأس ، هناك حاجة إلى ^عدد 2 بتات ، وهو أكبر بكثير من المدقق الموجود في الذاكرة". ومع ذلك ، أثبت ناتاراجان ورايت أنه من الممكن التحقق من تلوين رسم بياني مزدوج الأسي بثلاثة ألوان ، حتى بدون القدرة على تحديد الرؤوس التي يجب طلبها للحصول على أدلة. الحقيقة هي أنه يمكنك أن تجعل المتسابقين أنفسهم يختارون الأسئلة الصحيحة.

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

وقال رايت "الدول المتشابكة هي موارد مشتركة". "بروتوكولنا بالكامل هو فهم كيفية استخدام هذا المورد المشترك لإنشاء مشكلات مترابطة."

إذا تم خلط الحواسيب الكمومية ، فإن اختيار الرؤوس سوف يرتبط ، ويعطي مجموعة الأسئلة المناسبة لفحص التلوين بثلاثة ألوان فقط.

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

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

وقال فيديك: "نحتاج إلى أن ننسى المراقبون ، وهذا هو الشيء الرئيسي الذي فعله ناتاراجان ورايت في عملهما". "إنهم يجبرون القائد على محو المعلومات من خلال القياس."

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

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