¿Qué es el algoritmo de Grover?

Una de las muchas ventajas que tiene un ordenador cuántico sobre uno clásico es su velocidad superior a la hora de buscar en bases de datos. El algoritmo de Grover ejemplifica esta capacidad.

Lov Grover, informático estadounidense de origen indio, publicó en 1996 un artículo que le dio fama en el campo de la informática cuántica. En su investigación, había trabajado en la optimización de problemas de búsqueda no estructurados.

Grover sugiere aplicar un truco en cuántica conocido como Amplificación de Amplitud para reducir significativamente el tiempo que se tarda en encontrar el ganador w en una base de datos no estructurada. Grover tuvo varias inspiraciones al escribir su artículo. Según Grover, los sistemas cuánticos "se mueven" hacia puntos con bajo potencial. El sistema busca el punto con el potencial más bajo para que el estado acumule más amplitud de probabilidad.

En segundo lugar, había utilizado la ecuación de Schrodinger (que predice el comportamiento futuro de un sistema dinámico. La ecuación se basa en la función de onda y predice sucesos o resultados de forma analítica y precisa). Además, encuentra versiones unitarias de sus matrices de evolución discretizadas. La selección de una fase y la posterior difusión de un estado cuántico inicial o de prueba son los dos elementos esenciales del algoritmo de Grover. Grover utiliza la métrica basada en el estado marcado de naturaleza markoviana pero no unitaria (Una matriz de Markov, también conocida como matriz estocástica, se utiliza para representar los pasos de una cadena de Markov. Cada entrada de la matriz de Markov representa la probabilidad de un resultado).

Según Grover, una operación de búsqueda puede presentarse utilizando una función f(x) que trabaja sobre el elemento x, si resuelve la búsqueda como exitosa entonces f(x)=1. Si el elemento x no se encuentra entonces f(x)=1. Si el elemento x no se encuentra entonces f(x)=0 . La computación cuántica se puede utilizar para resolver el problema de búsqueda no estructurada en O√N que es muy eficiente en comparación con los algoritmos de búsqueda clásicos.

Un ejemplo simplificado del algoritmo de Grover:
Supongamos que se quiere encontrar una determinada llave de entre N llaves colocadas aleatoriamente en una caja.
Para encontrar la llave concreta que busca, tendrá que buscar en la caja una media de N/2 veces, en el peor de los casos N veces. La tecnología cuántica permite acelerar este proceso hasta √N veces.
En una caja de 100 claves, esto significaría probar 10 claves en lugar de 50-100 claves.

Otra ventaja del algoritmo de Grover es que funciona en sólo O(√N log N) puertas. Grover utiliza el concepto de Oráculo, que es como una operación de caja negra que toma una entrada binaria de n bits y genera m bits. Asimismo sus operadores de difusión dan una inversión sobre la media de forma que los pequeños pasos a escala infinita se vuelven medibles.

Aplicaciones del algoritmo de Grover

El algoritmo de Grover puede resolver problemas relacionados con la eliminación de la media y la mediana de una colección de números. También puede resolver problemas de colisión:

• Puede resolver problemas NP completos utilizando la búsqueda exhaustiva para encontrar posibles soluciones
• El algoritmo ayuda a acelerar los problemas de búsqueda no estructurada en tiempo de ejecución de orden cuadrático para una variedad de otros algoritmos.
• Utiliza interferencia de fase y superposición además de amplificación de amplitud para localizar el elemento a buscar.

Utimaco proporciona soluciones resistentes a la cuántica que permiten a las empresas defender sus sistemas contra asaltos basados en ordenadores cuánticos y la ejecución del algoritmo de Grover para encontrar claves criptográficas. Nuestras importantes inversiones de tiempo y talento en criptografía post-cuántica dieron lugar a algoritmos PQC aprobados por el NIST y el BSI que ya se pueden implementar hoy en día en nuestras soluciones de ciberseguridad.