مرجع
آخر الزيارات

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

281 كلمة•0 مشاهدة•🗒️ منذ 5 أيام
باختصار: خوارزمية غروفر ويُطلق عليها كذلك خوارزمية البحث الكمومي، هي خوارزمية كمومية ابتكرها عالم الحاسوب الأمريكي من أصل هندي لوف غروفر عام 1996، وتُستعمل في الحوسبة الكمومية للبحث غير المنظم، إذ يُمكنها أن تُحدد باحتمالية عالية المدخلات الفريدة….
خوارزمية غروفر

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

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

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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