Fuente verificadaNivel 3
Algoritmo de Grover
El algoritmo de Grover ofrece aceleracion cuadratica para busqueda no estructurada con O(√N) consultas.
Qué significa
Usa oraculo de fase y difusion de Grover iterativamente.Optimo para busqueda no estructurada.Analogía cotidiana
Como un efecto de resonancia.
Como ecolocacion cuantica.
Errores comunes
- Aceleracion cuadratica, no exponencial.
- Demasiadas iteraciones reducen probabilidad de exito.
Puntos clave
- O(√N) consultas.
- Oraculo de fase + amplificacion de amplitud.
- Probado optimo.
Comprueba tu comprensión
¿Complejidad de Grover?
- A.O(N)
- B.O(log N)
- C.O(√N)
- D.O(N²)
Ver la respuesta
Respuesta: C. O(√N)
Por qué: O(√N) consultas oraculo.
Se apoya en
Fuente primaria: Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79, 325 (1997), doi:10.1103/PhysRevLett.79.325
Apréndelo con la práctica
Este concepto forma parte de un plan de 46 niveles, con un simulador interactivo y Lumen, un tutor cuyas respuestas se verifican antes de mostrarse. Los niveles 1–5 son gratuitos.