algoritmo de Grover

En computación cuántica, el algoritmo de Grover es un algoritmo cuántico para la búsqueda en una secuencia no ordenada de datos con N componentes en un tiempo O (N1/2), y con una necesidad adicional de espacio de almacenamiento de O(logN) (véase notación O). Fue inventado por Lov K. Grover en 1996. En una búsqueda normal de un dato, si tenemos una secuencia desordenada se debe realizar una inspección lineal, que necesita un tiempo de O (N), por lo que el algoritmo de Grover es una mejora bastante sustancial, evitando, además, la necesidad de la ordenación previa. La ganancia obtenida es cuadrática, lo que contrasta con otras mejoras de los algoritmos cuánticos que obtienen mejoras de orden exponencial sobre sus contrapartidas clásicas. Al igual que otros algoritmos de naturaleza cuántica, el algoritmo de Grover es un algoritmo de carácter probabilístico, por lo que produce la respuesta correcta con una determinada probabilidad de error, que, no obstante, puede obtenerse tan baja como se desee por medio de iteraciones.