An unsorted database contains N records, of which just one satisfies a particular property. The problem is to identify that one record. Any classical algorithm, deterministic or probabilistic, will clearly take O(N) steps since on the average it will have to examine a large fraction of the N records. Quantum mechanical systems can do several operations simultaneously due to their wave like properties. This paper gives an O(JN) step quantum mechanical algorithm for identifying that record. It is within a constant factor of the fastest possible quantum mechanical algorithm.
Notas/Comentarios de José A. Delgado-Penín:
El algoritmo de Grover es un algoritmo de búsqueda en bases de datos basado en mecánica cuántica. Según los expertos es muy rápido en su ejecución. A diferencia de otros algoritmos clásicos este algoritmo facilita búsquedas no estructuradas, 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. Este algoritmo forma parte del grupo más importante de esta algorítmica y que está constituido por los algoritmos cuánticos de: 1) Shor, 2) Grover y 3) el conocido como "del temple cuántico" (quantum annealing).
El algoritmo de Grover es un algoritmo de búsqueda en bases de datos basado en mecánica cuántica. Según los expertos es muy rápido en su ejecución. A diferencia de otros algoritmos clásicos este algoritmo facilita búsquedas no estructuradas, 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. Este algoritmo forma parte del grupo más importante de esta algorítmica y que está constituido por los algoritmos cuánticos de: 1) Shor, 2) Grover y 3) el conocido como "del temple cuántico" (quantum annealing).
Especificaciones
- Autor/es: Lov K. Grover.
- Fecha: 1996-07
- Publicado en: STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing Pages 212-219. Published: July 1996.
- Idioma: Inglés
- Formato: PDF
- Contribución: José Antonio Delgado-Penín.
- Palabras clave: Inteligencia computacional y artificial, Matemáticas, Ordenadores y tratamiento de la información, Tecnologías cuánticas
