خوارزمية غروفر: البحث الكمي
الدرس 11 من 23 في دورة «الكم». مجاني، مع رسوم متحركة واختبار.
مسألة الصناديق
أمامك N صندوقًا مغلقًا والهدية في واحد منها. بلا تلميحات: تفتح وتنظر وتغلق. في المتوسط ستفتح نصف الصناديق، وفي أسوأ الأحوال كلها. النسخة الكمية: لدينا «عرّاف»، أي دارة تجيب هل هذا هو الصندوق الصحيح. عام 1996 أظهر لوف غروفر من مختبرات بيل كيف تجد الهدية في نحو √N سؤالًا. لمليون صندوق هذا نحو 800 سؤال بدل نصف مليون.
كيف تعمل: وسم ثم انعكاس
أولًا تعطي بوابات H كل الصناديق السعة نفسها. الخطوة 1: يضع العرّاف إشارة سالبة لسعة الصندوق الصحيح، وهي خطوة الوسم من وصفتنا. الخطوة 2: «الانعكاس حول المتوسط». انخفض المتوسط قليلًا بسبب السالب، فتُقلب كل سعة حوله. الصناديق العادية تنخفض قليلًا، أما السالبة فتقفز عاليًا. كرر «وسم + انعكاس» فيكبر الصندوق الصحيح في كل مرة.
المهم أن تتوقف في الوقت المناسب
تفصيل غير بديهي: غروفر ليس «كلما طال كان أفضل». سعة الصندوق الصحيح تكبر مثل سهم يدور. مع 64 صندوقًا يصبح الاحتمال قرابة 100% بعد نحو 6 خطوات، وإن واصلت تجاوز السهم الهدف وبدأ الاحتمال ينخفض. لذلك يُحسب عدد الخطوات مسبقًا: نحو π/4 · √N. وإن لم تعرف عدد الهدايا فهناك صيغ ذكية للخوارزمية، لكن هذه تفاصيل.
غروفر والتشفير
تخمين مفتاح الشيفرة هو بالضبط البحث عن صندوق واحد بين عدد هائل. في AES-128 هناك 2 أس 128 خيارًا. يأخذ غروفر الجذر فتبقى 2 أس 64 خطوة، أي تصبح حماية «128 بت» «64 بت». عمليًا حتى هذا كثير جدًا: خطوات غروفر تسير واحدة تلو الأخرى بصرامة، ولا يمكن توزيعها على آلاف الأجهزة بسهولة التجريب العادي. لكن العلاج بسيط ومستخدم الآن: يبقى AES-256 بقوة 128 بت بعد غروفر.
حد السرعة
هل يبتكر أحد بحثًا أسرع؟ لا: عام 1997 أثبت أربعة باحثين، بينيت وبرنشتاين وبراسار وفازيراني، أن √N هو الحد للبحث «الأعمى» على أي حاسوب كمي. ومن هنا استنتاج مهم: كثير من المسائل الصعبة، مثل أفضل مسار توصيل، يرجع في جوهره إلى التجريب. الحاسوب الكمي يسرّعها إلى الجذر على الأكثر ولا يجعلها فورية. ولم يجد أحد تسريعًا أُسّيًا لمثل هذه المسائل.
أين تفيد غروفر فعلًا
تبدو كأنها «غوغل كمي»، لكن للبحث في قاعدة بيانات عادية تكاد غروفر لا تفيد. لكي تسأل العرّاف يجب أولًا تحميل البيانات في ذاكرة كمية، وهذا وحده يستغرق نحو N خطوة ويلتهم المكسب كله. الفائدة الحقيقية حيث لا تُخزّن «الصناديق» بل تُحسب بصيغة: تخمين المفاتيح والتحقق من الحلول وكروتين فرعي داخل خوارزميات أعقد. وكل ذلك يتطلب حواسيب كبيرة مصححة الأخطاء.
اختبر نفسك
- كم خطوة غروفر تقريبًا لـ10,000 خيار؟
الإجابة الصحيحة: نحو 80. √10,000 = 100، وπ/4 · 100 ≈ 79. تسريع تربيعي لا فوري. - كرر صديقك خطوات غروفر ثلاثة أضعاف اللازم «للاحتياط». ماذا يحدث؟
الإجابة الصحيحة: ينخفض الاحتمال: يتجاوز السهم الجواب. غروفر دوران. بعد النقطة المثلى تعود سعة الصندوق الصحيح إلى الانخفاض. - هل يجب استبدال AES-256 عاجلًا بسبب غروفر؟
الإجابة الصحيحة: لا: تبقى له 128 بت حماية بعد غروفر. غروفر يقسم «عدد البتات» على اثنين، و128 بت تعد آمنة. لذا يُنصح بـAES-256 للمدى الطويل.