خوارزمية غروفر

خوارزمية غروفر ويُطلق عليها أيضًا خوارزمية البحث الكمومي، هي خوارزمية كمومية ابتكرها عالم الحاسوب الأمريكي من أصل هندي لوف غروفر عام 1996، وتُستخدم في الحوسبة الكمومية للبحث غير المنظم، إذ يُمكنها أن تُحدد باحتمالية عالية المدخلات الفريدة لدالة الصندوق الأسود التي تُنتج قيمة مخرجات محددة، باستخدام تقييمات  للدالة فقط، حيث 𝑁 هو حجم مجال الدالة. تتسم المسألة المماثلة في الحوسبة الكلاسيكية بتعقيد استعلام مقداره 𝑂 (𝑁) (أي أنه يجب تقييم الدالة لعدد 𝑂 (𝑁) مرات) لا يوجد نهج أفضل من تجربة جميع قيم المدخلات واحدة تلو الأخرى، وهو ما يستغرق في المتوسط ما يساوي 𝑁/2 من الخطوات.

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

على عكس الخوارزميات الكمومية الأخرى، والتي قد تُوفّر تسريعًا أُسيًا مقارنةً بنظيراتها الكلاسيكية، فإن خوارزمية غروفر تُوفّر تسريعًا تربيعيًا فقط. ومع ذلك، فحتى التسريع التربيعي يكون ملحوظًا عندما تكون قيمة 𝑁 كبيرة، ويمكن تطبيق خوارزمية غروفر لتسريع فئات واسعة من الخوارزميات. في هجمات البحث الشامل، تستطيع خوارزمية غروفر التوصل إلى مفتاح تشفير متماثل بطول 128 بت بعد حوالي 264 تكرارًا، ويُمكنها اكتشاف مفتاح تشفير بطول 256 بت بعد حوالي 2128 تكرارًا. وعلى الرغم من ذلك، فإن خوارزمية غروفر قد لا تُشكل خطرًا متزايدًا بشكل ملحوظ على التشفير مقارنةً بالخوارزميات الكلاسيكية الحالية.

 مراجع 



تصنيف:خوارزميات الكم
تصنيف:خوارزميات بحث
تصنيف:علم الحاسوب