في الممارسة العملية ، لا يمكن تشغيل العديد من البرامج المصممة لأجهزة الكمبيوتر التقليدية على أجهزة الكمبيوتر الكمومية لأنها لا تستطيع نسيان المعلومات بشكل انتقائي. تُظهر خوارزمية الضرب الجديدة كيفية التغلب على هذه المشكلة.
البتات الكلاسيكية بالأبيض والأسود ، والبتات الكم أكثر تعقيدًا قليلاًعندما كان عمري 9 ، اشترى والدي جهاز كمبيوتر جديد. في جميع النواحي تقريبًا ، كان أفضل من القديم ، باستثناء واحد: لم تبدأ السباقات المفضلة لدي. أتذكر كيف فكرت - لماذا أحتاج إلى كمبيوتر جديد إذا لم يبدأ تشغيل برنامجي المفضل؟
أجهزة الكمبيوتر الكم لديها نفس المشكلة. من الناحية النظرية ، فإنهم قادرون على كل ما هو كلاسيكي قادر. في الممارسة العملية ، تجعل طبيعتها الكمية من المستحيل تقريبًا تشغيل بعض الخوارزميات الكلاسيكية الأكثر أهمية.
هذا هو السبب في أن
العمل ، الذي نشر في 15 أبريل ، يحتوي على أخبار سارة.
يصف كريج غيدني ، عالم الكمبيوتر في Google AI Quantum في سانتا باربارا ، كاليفورنيا ، نسخة الكم من الخوارزمية الكلاسيكية لضرب أعداد كبيرة بسرعة كبيرة. على أجهزة الكمبيوتر الكلاسيكية ، تم تشغيل هذه الخوارزمية لبعض الوقت. ولكن قبل عمل جيدني ، لم يكن من الواضح ما إذا كان من الممكن تكييفه مع الآلات الكمومية.
الأهم من ذلك ، تنتمي خوارزمية الضرب إلى فئة خوارزميات علوم الكمبيوتر في كل مكان. يعتقد غيدني أن أسلوبه الجديد سيسمح لأجهزة الكمبيوتر الكمومية بتنفيذ فئة كاملة من هذه الخوارزميات ، والتي تعتبر حتى الآن مرهقة للغاية لاستخدامها في آلة الكم.
تستفيد خوارزمية الضرب من هذا الاكتشاف ، الذي كان أول طفرة في الضرب التي تمت على مدار عدة آلاف من السنين. تتطلب طريقة الضرب التقليدية بالمدرسة n
2 خطوات ، حيث n هو عدد الأحرف بالأرقام المضروبة. لعدة آلاف من السنين ، يعتقد علماء الرياضيات أن نهج أكثر كفاءة لم يكن موجودا.
ولكن ، كما أوضحنا مؤخرًا في مقال "
اكتشف علماء الرياضيات الطريقة المثلى لمضاعفة الأرقام "
، في عام 1960 ، اكتشف عالم الرياضيات السوفيتي أناتولي كاراتسوبا طريقة أسرع. كانت طريقته تقسيم الأعداد الطويلة إلى أرقام أقصر. لمضاعفة رقمين مكونين من ثمانية أرقام ، على سبيل المثال ، يجب عليك أولاً تقسيمها إلى رقمين مكونين من أربعة أرقام ، ثم تقسيم كل واحد منهم إلى رقمين. ثم تحتاج إلى تنفيذ العديد من العمليات بأرقام من رقمين واستعادة نتيجة الضرب النهائي. لمضاعفة أعداد كبيرة للغاية ، تأخذ طريقة Karatsuba خطوات أقل بكثير من طريقة المدرسة.
عندما يعمل كمبيوتر كلاسيكي على خوارزمية Karatsuba ، فإنه يحذف المعلومات في هذه العملية. على سبيل المثال ، استعادة الأرقام المكونة من رقمين إلى أربعة أرقام ، فإنه ينسى الأرقام المكونة من رقمين. الآن هو مهتم فقط بأرقام من أربعة أرقام. يشبه الإصدار الكلاسيكي للخوارزمية متسلقًا يطرد معداته أثناء صعوده - يمكنه التحرك بشكل أسرع إذا لم يحمل معه كل الأشياء غير الهامة معه.
لكن أجهزة الكمبيوتر الكمومية لا يمكنها تجاهل المعلومات.
تقوم الحواسب الكمومية بإجراء عمليات حسابية من خلال التلاعب بالبتات الكمومية أو "البتات". تتشابك مع بعضها البعض ، أو مشوشة. يمنح هذا الارتباك أجهزة الكمبيوتر الكمومية فرصًا هائلة - بدلاً من تخزين المعلومات في أجزاء منفصلة ، تستخدم أجهزة الكمبيوتر الكمومية تفاعلات معقدة لكل وحدات البت. نتيجة لذلك ، بالنسبة لبعض المهام ، تستطيع أجهزة الكمبيوتر الكمومية إظهار قدرة حسابية أكبر بشكل كبير مقارنة بتلك التقليدية.
ومع ذلك ، فإن نفس الخاصية التي تجعل أجهزة الكمبيوتر الكمومية قوية جدًا تجعلها أيضًا هشة. نظرًا لأن البتات مشتبكة ، فمن المستحيل تغيير بعضها دون التأثير على أي شخص آخر. هذا يجعل من المستحيل بشكل انتقائي حذف المعلومات المتاحة لأجهزة الكمبيوتر الكلاسيكية. إن ضرب البتات الخلفية يشبه قطع أجزاء من الويب - حتى القطع الواحدة يمكن أن تدمر الويب بالكامل.
هذا الشرط للحفاظ على المعلومات يعقد إنشاء إصدارات كمية من الخوارزميات العودية - وهذا هو ، والتحول إلى أنفسهم. في علوم الكمبيوتر ، تُستخدم الخوارزميات العودية على نطاق واسع جدًا ، ولكن لكي تعمل بأفضل طريقة ، فإنها تحتاج إلى الكمبيوتر لتجاهل المعلومات في كل خطوة. بدون هذا ، سوف تصبح الحوسبة غير عملية بسرعة. وقال
آشلي مونتانارو ، متخصص المعلومات الكمومية في جامعة بريستول: "إذا قمت بحفظ المعلومات في كل مرة تقوم فيها بإجراء عملية ، فإن المساحة التي تحتلها ستزداد بعدد العمليات". أي جهاز عملي سوف ينفد من الذاكرة بسرعة.
في عمل جديد ، يصف غيدني طريقة كمومية لتنفيذ عملية الضرب Karatsuba ، والتي لا تتطلب استهلاكًا كبيرًا للذاكرة. بدلاً من إنشاء قيم وسيطة للحصول على النتيجة النهائية ، تستخدم طريقة "
تحسين العودية الذيل " لتحويل المدخلات مباشرة إلى مخرجات. يسمح هذا للخوارزمية بتجنب إنشاء معلومات وسيطة يتعذر على الكمبيوتر الكمي تجاهلها. وقال
توماس فون ، متخصص المعلومات الكمومية في جامعة كريتون: "لقد تخلص من مشكلة البتات الإضافية دون توليد البتات الإضافية".
يعتقد غيدني أن طريقته ستعمل على تكييف العديد من الخوارزميات العودية الكلاسيكية لأجهزة الكمبيوتر الكمومية. حتى الآن ، أصبحت أجهزة الكمبيوتر الكمومية في مهدها بحيث لا يمكنها بالكاد التعامل مع تكاثر الأرقام المفردة. ومع ذلك ، فإن الخوارزمية جاهزة ، وعندما يتم تحسين مخططاتها ، ستصبح أكثر قدرة.