تفوق كمي

خوارزمية شور لتحليل الأعداد الصحيحة

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

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

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

نقد الاسم

انظر كذلك

جيوتشانغ

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

أخذ عينات البوزون

ومن جهة أخرى، تتطلب أفضل خوارزمية معروفة لمحاكاة دائرة كمية عشوائية تعسفية مقدارًا من الوقت يتناسب بدرجة كبيرة مع عدد البتات الكمومية، مما دفع إحدى المجموعات إلى تقدير أن نحو 50 بتًا كموميًا قد تكون كافية لإثبات التفوق الكمومي. في سنة 2018، قدم بولاند، وفيفرمان، ونيركي، وفازيراني أدلة نظرية على أن محاكاة دائرة كمية عشوائية بكفاءة تتطلب انهيار التسلسل الهرمي متعدد الحدود الحسابي. أعلنت شركة جوجل عن نيتها إظهار التفوق الكمي بحلول نهاية عام 2017 من خلال بناء وتشغيل شريحة مكونة من 49 كيوبت والتي ستكون قادرة على أخذ عينات من التوزيعات التي لا يمكن الوصول إليها بواسطة أي أجهزة كمبيوتر كلاسيكية حالية في فترة زمنية معقولة. كان أكبر جهاز محاكاة للدوائر الكمية العالمية يعمل على أجهزة الكمبيوتر العملاقة الكلاسيكية في ذلك الوقت قادرًا على محاكاة 48 كيوبت. ولكن بالنسبة لأنواع معينة من الدوائر، فمن الممكن إجراء محاكاة لدوائر كمية أكبر تحتوي على 56 كيوبت. قد يتطلب هذا زيادة عدد البتات الكمومية لإثبات التفوق الكمي. في 23 أكتوبر 2019، نشرت جوجل نتائج تجربة التفوق الكمي هذه في مقالة نيتشر، «التفوق الكمي باستخدام معالج فائق التوصيل قابل للبرمجة»، حيث طوروا معالجًا جديدًا مكونًا من 53 كيوبت، يُدعى «سيكامور»، وهو قادر على إنشاء بوابات منطقية كمية سريعة وعالية الدقة، من أجل إجراء اختبار معياري. تزعم شركة جوجل أن جهازها أجرى عملية الحساب المستهدفة في 200 ثانية، وتقدر أن خوارزميتها الكلاسيكية ستستغرق 10000 عام في أسرع حاسوب عملاق في العالم لحل نفس المشكلة. رفضت شركة آي بي إم هذا الادعاء، قائلة إن الخوارزمية الكلاسيكية المحسنة يجب أن تكون قادرة على حل هذه المشكلة في يومين ونصف على نفس الحاسوب العملاق.

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

الانتقادات

أخذ عينات من توزيع مخرجات الدوائر الكمومية العشوائية

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

قابلية الخطأ

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

التجارب المقترحة

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

التعقيد الحسابي

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

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

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

التقدم في القرن الحادي والعشرين

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

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

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

إضافةً إلى ذلك، في 18 يونيو 2019، اقترحت أن التفوق الكمي قد يحدث في عام 2019، بحسب قانون نيفن. في 20 سبتمبر 2019، ذكرت صحيفة فاينانشال تايمز أن «جوجل تدعي أنها وصلت إلى التفوق الكمي بمجموعة من 54 كيوبت، منها 53 كيوبت وظيفية، والتي تم استخدامها لإجراء سلسلة من العمليات في 200 ثانية والتي قد يستغرق حاسوب عملاق قرابة 10000 عام لإكمالها». في 23 أكتوبر، أكدت جوجل هذه الادعاءات رسميًا. وردت شركة آي بي إم على ذلك باقتراح أن بعض هذه الادعاءات مبالغ فيها، واقترحت أن الأمر قد يستغرق يومين ونصف اليوم بدلاً من عشرة آلاف عام، مع ذكر التقنيات التي قد يستعملها الحاسوب العملاق الكلاسيكي لتعظيم سرعة الحوسبة. كانت استجابة شركة آي بي إم ذات صلة حيث أن أقوى حاسوب عملاق في ذلك الوقت، Summit، تم تصنيعه بواسطة شركة آي بي إم. لقد طور الباحثون منذ ذلك الحين خوارزميات أفضل لمشكلة أخذ العينات المستعملة في المطالبة بالتفوق الكمي، مما أدى إلى انخفاض كبير في الفجوة بين معالج وأجهزة الكمبيوتر العملاقة الكلاسيكية وحتى التغلب عليها.

من جهة ثانية، أعلنت شركة جوجل عن خططها لإثبات التفوق الكمي قبل نهاية عام 2017 باستخدام مجموعة مكونة من 49 كيوبت فائق التوصيل. في أوائل يناير 2018، أعلنت شركة إنتل عن برنامج أجهزة مماثل. في أكتوبر 2017، قامت شركة آي بي إم بمحاكاة 56 كيوبت على حاسوب عملاق كلاسيكي، مما أدى إلى زيادة القوة الحسابية اللازمة لإثبات التفوق الكمي. في نوفمبر 2018، أعلنت جوجل عن شراكة مع ناسا تهدف إلى «تحليل نتائج الدوائر الكمومية المُشغّلة على معالجات جوجل الكمومية، وتوفير مقارنات مع المحاكاة الكلاسيكية لدعم جوجل في التحقق من صحة أجهزتها، ووضع خط أساس للتفوق الكمومي». أشارت الأعمال النظرية المنشورة في عام 2018 إلى أنه من الممكن تحقيق التفوق الكمومي باستخدام «شبكة ثنائية الأبعاد من 7×7 كيوبت وقرابة 40 دورة ساعة» إذا أمكن خفض معدلات الخطأ إلى مستوى منخفض بما يكفي. كان المخطط الذي تمت مناقشته عبارة عن متغير من مخطط أخذ العينات العشوائية الكمومية حيث تخضع البتات الكمومية لدوائر كمية عشوائية تتميز ببوابات كمية مرسومة من مجموعة بوابات عالمية، تليها قياسات على أساس حسابي.

من جانب آخر، في يونيو 2022، أبلغ زانادو عن تجربة أخذ عينات من البوزون تتوافق مع تلك التي أجرتها جوجل وجامعة العلوم والتكنولوجيا في الصين. استعمل إعدادهم حلقات من الألياف الضوئية والإرسال المتعدد لاستبدال شبكة مقسمات الشعاع بشبكة واحدة مما جعل إعادة تكوينها أكثر سهولة. وقد اكتشفوا متوسطًا يتراوح بين 125 إلى 219 فوتونًا من 216 وضعًا مضغوطًا (يتبع الضوء المضغوط توزيعًا لعدد الفوتونات بحيث يمكن أن يحتوي على أكثر من فوتون واحد لكل وضع) ويزعمون أنهم حصلوا على تسريع أكبر بـ 50 مليون مرة من التجارب السابقة.

وفي هذا السياق، في أكتوبر 2021، أعلنت فرق من جامعة جنوب كاليفورنيا للتكنولوجيا مرة أخرى عن أسبقية الكم من خلال بناء حاسوبين عملاقين يسميان جيوتشانغ 2.0 وزوشنزي. نفذ جهاز جيوتشانغ 2.0 المعتمد على الضوء أخذ عينات من البوزونات الغاوسية لاكتشاف 113 فوتونًا من مقياس تداخل بصري بـ 144 وضعًا وتسريع معدل أخذ العينات بمقدار 1024 - وهو فرق يبلغ 37 فوتونًا و10 أوامر من حيث الحجم مقارنة بجهاز جيوتشانغ السابق. زوشنزي هو حاسوب كمي فائق التوصيل قابل للبرمجة ويجب الحفاظ عليه في درجات حرارة منخفضة للغاية للعمل بكفاءة ويستعمل أخذ عينات عشوائية من الدوائر للحصول على 56 كيوبت من بنية اقتران قابلة للضبط مكونة من 66 إرسالًا—وهو تحسن عن إنجاز جوجل سيكامور 2019 بمقدار 3 كيوبت، مما يعني تكلفة حسابية أكبر للمحاكاة الكلاسيكية من 2 إلى 3 أوامر من حيث الحجم. أشارت دراسة ثالثة إلى أن زوشنزي 2.1 أكمل مهمة أخذ عينات «أكثر صعوبة بنحو 6 أوامر من حيث الحجم من مهمة سيكامور» «في المحاكاة الكلاسيكية».

التفوق الكمي في القرن العشرين

كذلك، في سنة 1994، تم تحقيق المزيد من التقدم نحو التفوق الكمي عندما صاغ بيتر شور خوارزمية شور، والتي قامت بتبسيط طريقة تحليل الأعداد الصحيحة في زمن متعدد الحدود. في عام 1995، نشر كريستوفر مونرو وديفيد وينلاند ورقتهما البحثية «عرض بوابة منطقية كمية أساسية»، والتي كانت بمثابة العرض الأول لبوابة منطقية كمية، وتحديدًا بوابة «نوت» ذات البتتين. في عام 1996، بدأ في الاهتمام بتصنيع حاسوب كمي بعد نشر خوارزميته، خوارزمية جروفر، في ورقته البحثية «خوارزمية ميكانيكية كمية سريعة للبحث في قواعد البيانات». في سنة 1998، نشر جوناثان أ. جونز «تنفيذ خوارزمية كمية لحل مشكلة دويتش على جهاز كمبيوتر الكم بالرنين المغناطيسي النووي»، مما يمثل أول عرض لخوارزمية كمية.

وفي السياق ذاته، في سنة 1936، نشر آلان تورينج ورقته البحثية «حول الأرقام القابلة للحساب»، ردًا على مشاكل هيلبرت عام 1900. وصفت ورقة تورينج ما أسماه «آلة الحوسبة العالمية»، والتي عُرفت فيما بعد باسم آلة تورينج. في عام 1980، استعمل ورقة تورينج لاقتراح إمكانية تطبيق الحوسبة الكمومية من الناحية النظرية. كانت ورقته البحثية «الحاسوب كنظام فيزيائي: نموذج هاملتوني ميكانيكي كمومي مجهري لأجهزة الكمبيوتر كما تمثلها آلات تورينج»، أول من أثبت أنه من الممكن إظهار الطبيعة العكسية للحوسبة الكمومية طالما أن الطاقة المبددة صغيرة بشكل تعسفي. في عام 1981، أظهر ريتشارد فاينمان أنه لا يمكن محاكاة ميكانيكا الكم بكفاءة على الأجهزة الكلاسيكية. خلال محاضرة، ألقى الاقتباس الشهير، «الطبيعة ليست كلاسيكية، اللعنة، وإذا كنت تريد إجراء محاكاة للطبيعة، فمن الأفضل أن تجعلها ميكانيكية كمية، وبالله إنها مشكلة رائعة، لأنها لا تبدو سهلة للغاية.» فيما بعد بوقت قصير، أنتج ديفيد دويتش وصفًا لآلة تورينج الكمومية وصمم خوارزمية تم إنشاؤها للتشغيل على جهاز كمبيوتر كمي.