خوارزمية جديدة تغلق نافذة التفوق الكمي
في أي حالات محددة تتفوق الحواسيب الكمومية على نظيراتها التقليدية؟ هذا سؤال يصعب الإجابة عليه ، ويرجع ذلك جزئيًا إلى أن أجهزة الكمبيوتر الكمومية اليوم هي أشياء صعبة ، مليئة بالأخطاء التي يمكن أن تتراكم وتفسد حساباتها.
وفقًا لمقياس واحد ، بالطبع ، لقد فعلوا ذلك بالفعل. في عام 2019 ، أعلن الفيزيائيون في Google أنهم استخدموا آلة ذات 53 كيلوبت لتحقيق التفوق الكمي ، وهو معلم رمزي يشير إلى النقطة التي يقوم فيها الكمبيوتر الكمومي بشيء بعيد عن متناول أي خوارزمية كلاسيكية عملية. وسرعان ما تبعت عروض مماثلة قام بها علماء فيزياء في جامعة العلوم والتكنولوجيا في الصين.
ولكن بدلاً من التركيز على نتيجة تجريبية لجهاز معين ، يريد علماء الكمبيوتر معرفة ما إذا كانت الخوارزميات الكلاسيكية ستكون قادرة على مواكبة أجهزة الكمبيوتر الكمومية. قال سكوت آرونسون ، عالم الكمبيوتر في جامعة تكساس ، أوستن: “الأمل هو أن الجانب الكمومي في النهاية يبتعد تمامًا حتى تختفي المنافسة بعد الآن”.
لا يزال من الصعب الإجابة على هذا السؤال العام ، ويرجع ذلك جزئيًا مرة أخرى إلى تلك الأخطاء المزعجة. (ستعوض الآلات الكمومية المستقبلية عيوبها باستخدام تقنية تسمى تصحيح الخطأ الكمومي ، لكن هذه القدرة لا تزال بعيدة المنال). هل من الممكن الحصول على الميزة الكمومية المأمولة حتى مع وجود أخطاء غير مصححة؟
اشتبه معظم الباحثين في أن الإجابة كانت لا ، لكنهم لم يتمكنوا من إثبات ذلك في جميع الحالات. الآن ، في ورقة تم نشرها على خادم ما قبل الطباعة arxiv.org ، اتخذ فريق من علماء الكمبيوتر خطوة كبيرة نحو دليل شامل على أن تصحيح الخطأ ضروري لميزة كمومية دائمة في أخذ عينات الدائرة العشوائية – وهي المشكلة المفصلة التي استخدمتها Google إظهار السيادة الكمومية. لقد فعلوا ذلك من خلال تطوير خوارزمية كلاسيكية يمكنها محاكاة تجارب عينات الدوائر العشوائية عند وجود أخطاء.
قال آرونسون: “إنها نتيجة نظرية جميلة” ، مشددًا على أن الخوارزمية الجديدة ليست مفيدة عمليًا لمحاكاة تجارب حقيقية مثل تجارب Google.
في تجارب أخذ عينات الدائرة العشوائية ، يبدأ الباحثون بمجموعة من الكيوبتات ، أو بتات الكم. ثم يتلاعبون بشكل عشوائي بهذه الكيوبتات من خلال عمليات تسمى البوابات الكمومية. تتسبب بعض البوابات في تشابك أزواج الكيوبتات ، مما يعني أنها تشترك في حالة كمية ولا يمكن وصفها بشكل منفصل. تؤدي الطبقات المتكررة من البوابات إلى جعل الكيوبتات في حالة تشابك أكثر تعقيدًا.
لمعرفة المزيد عن هذه الحالة الكمومية ، يقيس الباحثون بعد ذلك جميع الكيوبتات في المصفوفة. يؤدي هذا إلى انهيار الحالة الكمومية الجماعية الخاصة بهم إلى سلسلة عشوائية من البتات العادية – 0 و 1. عدد النتائج المحتملة ينمو بسرعة مع عدد الكيوبتات في المصفوفة: مع 53 كيوبت ، كما في تجربة جوجل ، يقارب 10 كوادريليون. ولا تتساوى احتمالية حدوث كل السلاسل. أخذ العينات من دائرة عشوائية يعني تكرار مثل هذه القياسات عدة مرات لبناء صورة لتوزيع الاحتمالات الكامن وراء النتائج.
سؤال الميزة الكمومية هو ببساطة: هل من الصعب محاكاة توزيع الاحتمالات هذا بخوارزمية كلاسيكية لا تستخدم أي تشابك؟
في عام 2019 ، أثبت الباحثون أن الإجابة هي نعم للدارات الكمومية الخالية من الأخطاء: من الصعب بالفعل محاكاة تجربة أخذ عينات الدوائر العشوائية عند عدم وجود أخطاء. عمل الباحثون في إطار نظرية التعقيد الحسابي ، والتي تصنف الصعوبة النسبية للمشكلات المختلفة. في هذا المجال ، لا يتعامل الباحثون مع عدد الكيوبتات كرقم ثابت مثل 53. “فكر في الأمر على أنه نقال آرام هارو ، عالم فيزياء في معهد ماساتشوستس للتكنولوجيا ، “وهو رقم سيزداد”. “ثم تريد أن تسأل: هل نقوم بأشياء يكون فيها الجهد أسيًا ن أو كثير الحدود في ن؟ ” هذه هي الطريقة المفضلة لتصنيف وقت تشغيل الخوارزمية – متى ن تنمو بشكل كافٍ ، وهي خوارزمية أسية فيها ن يتخلف كثيرًا عن أي خوارزمية متعددة الحدود فيها ن. عندما يتحدث المنظرون عن مشكلة صعبة على أجهزة الكمبيوتر الكلاسيكية ولكنها سهلة لأجهزة الكمبيوتر الكمومية ، فإنهم يشيرون إلى هذا التمييز: أفضل خوارزمية كلاسيكية تستغرق وقتًا أسيًا ، بينما يمكن للكمبيوتر الكمومي حل المشكلة في وقت متعدد الحدود.
ومع ذلك ، تجاهلت ورقة عام 2019 آثار الأخطاء التي تسببها البوابات غير الكاملة. ترك هذا المجال مفتوحًا لميزة كمية لأخذ عينات الدائرة العشوائية دون تصحيح الخطأ.
إذا كنت تتخيل زيادة مستمرة في عدد الكيوبتات كما يفعل منظرو التعقيد ، وتريد أيضًا حساب الأخطاء ، فأنت بحاجة إلى تحديد ما إذا كنت ستستمر في إضافة المزيد من طبقات البوابات – زيادة عمق الدائرة ، كما يقول الباحثون. لنفترض أنك تحافظ على ثبات عمق الدائرة عند ثلاث طبقات ضحلة نسبيًا ، على سبيل المثال ، مع زيادة عدد البتات. لن تحصل على الكثير من التشابك ، وسيظل الإخراج قابلاً للمحاكاة الكلاسيكية. من ناحية أخرى ، إذا قمت بزيادة عمق الدائرة لمواكبة العدد المتزايد للكيوبتات ، فإن التأثيرات التراكمية لأخطاء البوابة ستزيل التشابك ، وسيصبح الناتج مرة أخرى سهل المحاكاة بشكل كلاسيكي.
ولكن في المنتصف تقع منطقة المعتدل. قبل الورقة البحثية الجديدة ، كان لا يزال من الممكن أن تستمر ميزة الكم هنا ، حتى مع زيادة عدد البتات الكمومية. في هذه الحالة ذات العمق المتوسط ، تقوم بزيادة عمق الدائرة ببطء شديد مع نمو عدد الكيوبتات: على الرغم من أن الناتج سيتدهور بثبات بسبب الأخطاء ، فقد لا يزال من الصعب محاكاته بشكل كلاسيكي في كل خطوة.
الورقة الجديدة تسد هذه الثغرة. اشتق المؤلفون خوارزمية كلاسيكية لمحاكاة أخذ عينات الدائرة العشوائية وأثبتوا أن وقت تشغيلها هو دالة متعددة الحدود للوقت المطلوب لتشغيل التجربة الكمية المقابلة. والنتيجة تشكل علاقة نظرية قوية بين سرعة المقاربات الكلاسيكية والكمية لأخذ عينات الدائرة العشوائية.
تعمل الخوارزمية الجديدة مع فئة رئيسية من دوائر العمق المتوسط ، لكن افتراضاتها الأساسية تنهار لبعض الدوائر الضحلة ، تاركة فجوة صغيرة حيث طرق المحاكاة الكلاسيكية الفعالة غير معروفة. لكن قلة من الباحثين يأملون في أن يكون من الصعب محاكاة عينات الدائرة العشوائية بشكل كلاسيكي في هذه النافذة الضئيلة المتبقية. قال بيل فيفرمان ، عالم الكمبيوتر في جامعة شيكاغو وأحد مؤلفي الورقة النظرية لعام 2019: “أعطيها احتمالات صغيرة جدًا”.
تشير النتيجة إلى أن أخذ عينات الدائرة العشوائية لن ينتج عنه ميزة كمية وفقًا للمعايير الصارمة لنظرية التعقيد الحسابي. في الوقت نفسه ، يوضح حقيقة أن الخوارزميات متعددة الحدود ، والتي يسميها منظرو التعقيد بشكل عشوائي كفاءة ، ليست بالضرورة سريعة في الممارسة. تصبح الخوارزمية الكلاسيكية الجديدة أبطأ بشكل تدريجي مع انخفاض معدل الخطأ ، وبمعدلات الخطأ المنخفضة التي تحققت في تجارب التفوق الكمي ، فهي بطيئة جدًا بحيث لا تكون عملية. مع عدم وجود أخطاء ، فإنه ينهار تمامًا ، لذا فإن هذه النتيجة لا تتعارض مع أي شيء يعرفه الباحثون حول مدى صعوبة محاكاة أخذ عينات الدائرة العشوائية في الحالة المثالية الخالية من الأخطاء. يقول سيرجيو بويكسو ، الفيزيائي الذي يقود أبحاث السيادة الكمية في Google ، إنه يعتبر الورقة “تأكيدًا رائعًا لأخذ عينات الدوائر العشوائية أكثر من أي شيء آخر.”
يتفق جميع الباحثين على نقطة واحدة: تؤكد الخوارزمية الجديدة مدى أهمية تصحيح الخطأ الكمومي في نجاح الحوسبة الكمومية على المدى الطويل. قال فيفرمان: “هذا هو الحل ، في نهاية المطاف”.
ملاحظة المحرر: سكوت آرونسون عضو في المجلس الاستشاري لمجلة كوانتا.
