قام طالب الدراسات العليا بحل مشكلة تأكيد الحوسبة الكمومية

أمضت أورميلا ماهاديف ثماني سنوات في القضاء بحثًا عن إجابة على أحد الأسئلة الأساسية للحوسبة الكمومية: كيف نعرف أن الكمبيوتر الكمومي قام بشيء على الأقل على المستوى الكمومي؟

في ربيع عام 2017 ، كانت Urmila Mahadev في وضع جيد ، من وجهة نظر معظم طلاب الدراسات العليا. لقد حلت للتو المشكلة الحاسمة للحوسبة الكمومية - مجال علوم الكمبيوتر ، مستمدة من قدراتها من القوانين الغريبة لفيزياء الكم. جنبا إلى جنب مع أعمالها السابقة ، نتيجة جديدة لمهاديف تصف ما يسمى قال سكوت أرونسون ، اختصاصي تكنولوجيا المعلومات في جامعة تكساس في أوستن: "لقد جعلت الحوسبة العمياء" من الواضح أنها نجمة صاعدة.

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

لكن مهاديف لم ينته من الدراسة في ذلك العام. حتى أنها لا تنظر في هذه المسألة. لم تنته بعد.

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

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

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

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

قال فازيراني: "الكمبيوتر الكمّي قوي لكنه غامض".

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

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

لكنها رفضت الاستسلام. أظهر مهاديف مثل هذا المستوى من العزم الثابت الذي لم يلتزم به وزيراني من قبل. وقال: "بهذا المعنى ، أورميلا استثنائية للغاية".



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

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

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

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

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

طريق طويل

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

قالت: "كان شيئًا غريبًا تمامًا لم يكن لدي أدنى فكرة عنه".

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

منحوتة في الحجر

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

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

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

"هذه فكرة رائعة! - كتب فيديك. "إنها تضربني في كل مرة تشرح لها أورميلا."

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

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

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

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

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

بقيت ماكهاديف ، بعد حل مشكلتها المفضلة ، في حالة مرتبكة إلى حد ما. تقول مهاديف إنها تود أن تفهم ما جعل هذه المشكلة مناسبة لها تمامًا. « - , ». , , , , , , .

« , , — . – ».