مقدمة

خوارزمية Grover هي خوارزمية كمية لمسائل البحث غير المهيكل (unstructured search) توفر تحسينًا تربيعيًا مقارنةً بالخوارزميات الكلاسيكية. ما يعنيه ذلك هو أن خوارزمية Grover تحتاج إلى عدد من العمليات يساوي تقريبًا الجذر التربيعي لعدد العمليات المطلوبة لحل البحث غير المهيكل كلاسيكيًا — وهو ما يعادل القول بأن الخوارزميات الكلاسيكية للبحث غير المهيكل يجب أن يكون تكلفتها على الأقل بمقدار مربع تكلفة خوارزمية Grover.

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

وبينما يُعدّ النطاق الواسع لتطبيق تقنية بحث Grover أمرًا مقنعًا، لا بد من الإقرار هنا في بداية الدرس بأن الميزة التربيعية التي تقدمها تبدو مستبعدة أن تؤدي إلى ميزة عملية للحوسبة الكمية على الكلاسيكية في أي وقت قريب. أجهزة الحوسبة الكلاسيكية أكثر تقدمًا بكثير من أجهزة الحوسبة الكمية — وستطغى سرعات الساعة المذهلة للحواسيب الكلاسيكية الحديثة على الميزة التربيعية الكمية على الكلاسيكية التي توفرها خوارزمية Grover لأي مسألة بحث غير مهيكل يمكن تشغيلها فعليًا في أي وقت قريب.

غير أنه مع تقدم تكنولوجيا الحوسبة الكمية، قد يكون لخوارزمية Grover إمكانات كامنة. في الواقع، بعض من أهم الخوارزميات الكلاسيكية الأكثر تأثيرًا التي اكتُشفت على الإطلاق، بما فيها تحويل فورييه السريع والترتيب السريع (كخوارزمية quicksort وmerge sort مثلًا)، تقدم ميزة تقل قليلًا عن التربيعية مقارنة بالمناهج السذاجة للمسائل التي تحلها. الفارق الرئيسي هنا، بالطبع، هو أن تقنية جديدة كليًا (أي الحوسبة الكمية) مطلوبة لتشغيل خوارزمية Grover. وبينما لا تزال هذه التقنية في مهدها مقارنةً بالحوسبة الكلاسيكية، لا ينبغي لنا التسرع في الاستهانة بإمكانية التطورات التكنولوجية التي قد تسمح يومًا ما للميزة التربيعية الكمية على الكلاسيكية بتقديم فوائد عملية ملموسة.

فيديو الدرس

في الفيديو التالي، يأخذك John Watrous خطوةً بخطوة عبر محتوى هذا الدرس حول خوارزمية Grover. يمكنك أيضًا فتح فيديو YouTube الخاص بهذا الدرس في نافذة منفصلة. تنزيل الشرائح لهذا الدرس.