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 respecto a los algoritmos clásicos. Lo que esto significa es 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 la búsqueda no estructurada de forma clásica, lo que equivale a decir que los algoritmos clásicos de búsqueda no estructurada deben tener un coste al menos del orden del cuadrado del coste del algoritmo de Grover.

El algoritmo de Grover, junto con sus extensiones y la metodología subyacente, resulta ser ampliamente aplicable, lo que lleva a una ventaja cuadrática para muchas tareas computacionales interesantes que pueden no parecer inicialmente problemas de búsqueda no estructurados en la superficie.

Aunque la amplia aplicabilidad de la técnica de búsqueda de Grover es convincente, hay que reconocer aquí al principio de la lección que la ventaja cuadrática que ofrece parece poco probable que conduzca a una ventaja práctica de la computación cuántica sobre la clásica a corto plazo. El hardware de computación clásica es mucho más avanzado que el hardware de computación cuántica, y la ventaja cuántica cuadrática sobre la clásica que ofrece el algoritmo de Grover seguramente se verá anulada por las asombrosas velocidades de reloj de los ordenadores clásicos modernos para cualquier problema de búsqueda no estructurado que pueda ejecutarse en un futuro próximo.

Sin embargo, a medida que avanza la tecnología de computación cuántica, el algoritmo de Grover podría tener potencial. De hecho, algunos de los algoritmos clásicos más importantes e impactantes jamás descubiertos, como la transformada rápida de Fourier y la ordenación rápida (por ejemplo, quicksort y merge sort), ofrecen algo menos que una ventaja cuadrática sobre las aproximaciones ingenuas a los problemas que resuelven. La diferencia clave aquí, por supuesto, es que se requiere una tecnología completamente nueva (es decir, computación cuántica) para ejecutar el algoritmo de Grover. Aunque esta tecnología está aún muy en pañales en comparación con la computación clásica, no deberíamos subestimar tan rápidamente el potencial de los avances tecnológicos que podrían permitir que la ventaja cuadrática de la computación cuántica sobre la clásica ofrezca algún día ventajas prácticas tangibles.

Vídeo de la lección

En el siguiente vídeo, John Watrous le guía a través del contenido de esta lección sobre el algoritmo de Grover. También puede abrir el vídeo YouTube de esta lección en una ventana aparte. Descargue las diapositivas de esta lección.