Introducción
El algoritmo de Grover es un algoritmo cuántico para los llamados problemas de búsqueda no estructurada, que ofrece una mejora cuadrática sobre los algoritmos clásicos. Esto significa que el algoritmo de Grover requiere un número de operaciones del orden de la raíz cuadrada del número de operaciones necesarias para resolver una búsqueda no estructurada clásicamente, lo cual es equivalente a que los algoritmos clásicos para la búsqueda no estructurada deben tener un costo de al menos el orden del cuadrado del costo del algoritmo de Grover.
El algoritmo de Grover, sus extensiones y la metodología subyacente resultan ampliamente aplicables, ofreciendo una ventaja cuadrática en muchas tareas computacionales interesantes que, a primera vista, no parecen problemas de búsqueda no estructurada.
Aunque la amplia aplicabilidad de la técnica de búsqueda de Grover es convincente, al comienzo de esta lección debe reconocerse que la ventaja cuadrática sobre las computadoras clásicas probablemente no proporcionará beneficios prácticos en un futuro previsible. El hardware de computación clásica es muy superior al hardware de computación cuántica, y la ventaja cuántica cuadrática que ofrece el algoritmo de Grover se ve compensada, para cualquier problema de búsqueda no estructurada que pueda ser factible en un futuro previsible, por las enormes velocidades de reloj de las computadoras clásicas modernas.
Sin embargo, con el avance de la tecnología de computación cuántica, el algoritmo de Grover podría desarrollar su potencial. De hecho, algunos de los algoritmos clásicos más importantes e influyentes de todos los tiempos — incluyendo la transformada rápida de Fourier y los algoritmos de ordenamiento rápido (por ejemplo, Quicksort y Mergesort) — ofrecen una ventaja algo menor que cuadrática sobre los enfoques ingenuos para los problemas que resuelven. La diferencia clave, por supuesto, es que para el algoritmo de Grover se requiere una tecnología completamente nueva (es decir, la computación cuántica). Aunque esta tecnología está todavía en sus inicios en comparación con la computación clásica, no debemos subestimar el potencial de los avances tecnológicos — avances que algún día podrían permitir que una ventaja cuántica cuadrática ofrezca beneficios prácticos tangibles.
Video de la lección
En el siguiente video, John Watrous recorre el contenido de esta lección sobre el algoritmo de Grover. Alternativamente, puedes abrir el video de YouTube de esta lección en una ventana separada. Descargar diapositivas de esta lección.