En 1996 Lov Grover, en Bell Labs, presenta 'A fast quantum mechanical algorithm for database search' en STOC 1996: un algoritmo cuántico que busca un elemento específico en una base de datos no estructurada de N elementos en O(√N) operaciones, frente a las O(N) que necesita cualquier algoritmo clásico. La aceleración es cuadrática —no exponencial como la de Shor—, pero se ha demostrado que es óptima: ningún algoritmo cuántico puede hacerlo mejor para búsqueda no estructurada. El mecanismo central es la amplificación de amplitud: el algoritmo amplifica iterativamente la probabilidad cuántica del estado solución mientras suprime las de los demás estados, convergiendo al resultado correcto en √N pasos. El algoritmo de Grover tiene implicaciones directas en criptografía simétrica: reduce a la mitad la seguridad efectiva en bits de algoritmos como AES, lo que explica por qué los estándares post-cuánticos recomiendan doblar las longitudes de clave. Junto con el algoritmo de Shor, Grover establece que la computación cuántica ofrece ventajas algorítmicas reales y medibles sobre la computación clásica en problemas concretos.