¿Qué es Grover y cuánta aceleración da realmente?

Estado a: agosto 2026. El algoritmo de Grover es el segundo algoritmo cuántico más famoso y probablemente el peor citado. Lo que da es preciso y está probado: para búsqueda no estructurada, del orden de √N llamadas a un oráculo en vez de N — una aceleración cuadrática, en el modelo de consultas. Lo que suele venderse — una forma de buscar en tu base de datos, una fuerza bruta en paralelo, una amenaza cercana para AES — no lo es. El techo también es un teorema: nada cuántico baja de √N en esta tarea. Y la corrida de Grover mejor-que-clásica más grande publicada hasta hoy usó 5 qubits, un espacio de búsqueda de 32 ítems.

¿Qué hace Grover de verdad?

Tomá una función que marca exactamente uno de N candidatos, sin estructura que explotar. Clásicamente evaluás candidatos hasta dar con el marcado — del orden de N/2 intentos en promedio. Grover (1996) prepara una superposición sobre los N candidatos y aplica aproximadamente (π/4)·√N iteraciones; cada iteración llama a la función como circuito cuántico — el oráculo — y rota amplitud hacia el estado marcado. Es coreografía por interferencia, no prueba en paralelo: medí antes de tiempo y obtenés un candidato al azar (cómo computa de verdad un qubit).

Dos propiedades vuelven a esta clase inusualmente honesta. La aceleración está probada — sin conjetura asintótica, sin heurística. Y el límite también: Bennett, Bernstein, Brassard y Vazirani (1997) demostraron que ningún algoritmo cuántico resuelve búsqueda no estructurada en menos del orden de √N consultas. Grover es óptimo. En un campo donde la mayoría de los claims vive de estimaciones, este es uno de los pocos rincones acotado por teoremas en ambas direcciones (la lista corta de ventaja probada).

¿Grover acelera buscar en mi base de datos?

No — y esta es la mala lectura más común. El oráculo no es una consulta a memoria; es una computación. Grover asume que podés evaluar la función que marca sobre una superposición de candidatos. Si tus N ítems son datos almacenados, sin estructura, algo tiene que cargarlos primero en ese circuito, y cargar N ítems cuesta del orden de N operaciones — la ventaja se evapora antes de que el algoritmo arranque (Aaronson, Nature Physics 2015). Es la misma letra chica que la dequantización explotó para tumbar una generación de claims de machine learning cuántico (el veredicto de QML).

Donde Grover sí aplica legítimamente es en espacios de búsqueda definidos por una función y no guardados en memoria: asignaciones que satisfacen una fórmula, preimágenes de un hash, claves criptográficas. Ahí el candidato se computa, no se busca en disco, y el conteo √N se sostiene. El núcleo de Grover además se generaliza en la amplificación de amplitud (Brassard, Høyer, Mosca & Tapp, 2002) — una subrutina que mejora cuadráticamente la probabilidad de éxito de otros algoritmos cuánticos, donde vive la mayor parte de su uso serio.

¿Cuánta aceleración es "cuadrática" en la práctica?

Cuadrática significa raíz cuadrada del número de consultas — no del tiempo de reloj. Para buscar la clave de AES-128, 2^128 intentos clásicos se vuelven del orden de 2^64 consultas de Grover, y cada consulta corre el circuito completo de AES de forma coherente. El costeo estándar (Grassl, Langenberg, Roetteler & Steinwandt, PQCrypto 2016) pone el ataque en 2.953 qubits lógicos y una profundidad total de circuito de ≈1,16·2^81, con ≈1,19·2^86 compuertas T. Trabajo posterior refinó las estimaciones a la baja (Jaques et al., EUROCRYPT 2020 — revisado una vez por bugs de herramientas; la aritmética se mueve, la conclusión no).

La profundidad es lo que mata, porque Zalka (1999) probó que las iteraciones deben correr en serie para obtener la aceleración completa. Nuestra aritmética sobre la profundidad citada: 1,16·2^81 son ≈2,8×10^24 pasos lógicos secuenciales. A un reloj lógico de 1 GHz — que ningún roadmap promete; los ciclos lógicos de hoy corren en el orden de microsegundos — eso da aproximadamente 89 millones de años. Paralelizar no lo rescata: la cota de Zalka dice que S máquinas compran solo un factor √S, así que bajar 89 millones de años a un año pediría del orden de 8×10^15 computadores cuánticos completos. Por eso "AES-128 cae a seguridad de 64 bits bajo Grover" es cierto solo en el modelo de consultas, y por eso el propio FAQ de NIST (accedido en agosto 2026) concluye que "es bastante probable que el algoritmo de Grover aporte poca o ninguna ventaja para atacar AES, y AES-128 seguirá siendo seguro por décadas" (traducción propia; NIST PQC FAQ).

La versión general de esta aritmética ya está en el registro: las aceleraciones cuadráticas, como clase, no rinden ventaja en las primeras máquinas tolerantes a fallos una vez que se paga el sobrecosto de corrección de errores (Babbush et al., PRX Quantum 2021 — de dónde sale un punto de cruce). Grover es el miembro canónico de esa clase.

¿Qué se ha corrido en hardware?

Demos chicas, cuidadosas y honestas. El récord de probabilidad de éxito mejor-que-clásica en Grover es de 5 qubits — un espacio de 32 ítems — en dispositivos IBM de 7 qubits, usando detección de errores y desacople dinámico (Pokharel & Lidar, npj Quantum Information 2024). En las máquinas actuales de IBM de más de 100 qubits, una instancia de Grover de 3 qubits acierta el 51–64% de las veces contra un piso de 25% de adivinanza aleatoria, y los intentos publicados de 8 qubits no habían superado a la adivinanza clásica (AbuGhanem, Scientific Reports 2025). La corrida chica de mayor fidelidad es de 3 qubits de espín nuclear en silicio con 93,5% de éxito sin corrección de errores (Nature Nanotechnology 2024; SQC, feb 2025) — un resultado de fidelidad genuino que sus propios autores presentan como prueba de concepto a escala chica, no como claim de ventaja. Nada de esto es una crítica: esos papers declaran su alcance con claridad. Cada uno de esos disparos, además, se factura por tarea y por disparo en hardware rentado (lo que cuesta de verdad una corrida).

Ventaja end-to-end medida de Grover en un problema útil, en cualquier hardware: cero, a agosto 2026 (el marcador).

Los claims sobre Grover, uno por uno

Qué sabemos / qué no sabemos

Qué sabemos. El conteo √N de consultas está probado, y BBBV probó que ningún algoritmo cuántico lo mejora — para búsqueda no estructurada pura, el techo es un teorema, así que ninguna astucia futura lo sube en el modelo de consultas. Los costeos tolerantes a fallos publicados ponen a Grover-sobre-AES en profundidad serial astronómica, y la posición pública de NIST lo refleja. El récord de hardware con éxito mejor-que-clásico es de 5 qubits.

Qué no sabemos. Si fábricas de estados mágicos más baratas y mejor síntesis de oráculos doblan las constantes lo suficiente como para importar algún día — las estimaciones se han revisado más de una vez, hasta ahora siempre astronómicas. Si Grover-como-subrutina dentro de algoritmos tolerantes a fallos más grandes llega a rendir valor end-to-end medido en una instancia útil — nada medido hasta hoy. Dónde quedaría el tamaño de cruce N* en hardware tolerante a fallos real — no existe esa máquina para medirlo. Rosetta Q no tiene corridas selladas en esta clase: nuestras series selladas son experimentos chicos de optimización y quantum walks donde el baseline clásico sigue invicto — no tenemos mediciones propias de Grover y no reclamamos ninguna.

Rosetta Q publica veredictos con datos crudos reproducibles. Esto es contenido educativo, no un claim de producto.