¿Qué es el Algoritmo de Grover y Por Qué Amenaza a AES-128?

Para entender qué es el algoritmo de Grover, debemos situarnos en 1996, año en que fue propuesto por Lov Grover. Su cometido parece engañosamente simple: encontrar un elemento concreto dentro de una base de datos desordenada a una velocidad inalcanzable para cualquier ordenador clásico.

La clave está en las cifras comparativas: un ordenador tradicional que busque entre N entradas desordenadas necesita, de media, N/2 intentos. En cambio, el algoritmo de Grover requiere aproximadamente √N operaciones. Hablamos de una aceleración cuadrática: no llega a ser exponencial, pero a gran escala resulta determinante.

Imagina la siguiente situación: alguien baraja un millón de cartas boca abajo y te pide encontrar el as de picas. Con la computación clásica tendrías que levantarlas una a una; de media, revisarías unas 500.000 cartas antes de dar con él. ¿Con el algoritmo de Grover? Apenas necesitarías unas 785 operaciones. Es la diferencia palpable entre dedicar media vida a voltear naipes o resolverlo antes de que se enfríe el café.

A continuación analizamos por qué este desarrollo es crucial, cómo funciona entre bastidores y dónde termina la teoría para dar paso a la realidad técnica.

El problema que resuelve: el cuello de botella de la fuerza bruta clásica

Buscar en un espacio no ordenado puede parecer trivial, hasta que descubres cuántos problemas computacionales de máxima dificultad se reducen, en esencia, a esta misma premisa.

¿Revertir el hash de una contraseña? Implica explorar todas las entradas posibles hasta hallar la que genera una salida concreta. ¿Resolver un problema de satisfacibilidad booleana (SAT)? Consiste en comprobar todas las combinaciones de variables hasta dar con la que hace verdadera la fórmula. ¿Invertir una función criptográfica? La estructura es idéntica: rastrear un espacio inmenso en busca de una aguja que cumpla una condición específica.

El enfoque clásico recurre sin remedio a la fuerza bruta: pruebas una opción, luego la siguiente y así sucesivamente. No existen atajos cuando los datos carecen de orden, estructura o índices. Hay que examinar cada posibilidad de forma individual, con un coste computacional que escala de forma lineal: O(N).

Para un valor reducido de N, no supone un inconveniente. Sin embargo, para N = 2¹²⁸ (el espacio de claves de AES-128), una escala lineal significa que la muerte térmica del universo llegaría antes de concluir la búsqueda. Por esta razón exacta la criptografía simétrica se ha considerado invulnerable durante décadas. El algoritmo de Grover no suprime la búsqueda: la comprime radicalmente.

La ventaja cuántica: comprender la aceleración cuadrática

Para visualizar la magnitud de esta aceleración, la siguiente tabla contrasta el promedio de pasos en un ordenador clásico frente a las iteraciones óptimas de Grover según el tamaño del conjunto de datos:

Hay un aspecto revelador: la ventaja se amplifica conforme crece N. En volúmenes reducidos de datos, el algoritmo de Grover apenas marca diferencias; no obstante, en espacios astronómicos —como los presentes en criptografía y optimización combinatoria— el salto de rendimiento resulta abrumador.

Conviene recalcar un matiz técnico esencial: la aceleración cuadrática es demostrablemente óptima. En 1997, Bennett, Brassard y colaboradores demostraron que ningún algoritmo cuántico puede examinar una base de datos no estructurada con una complejidad inferior a O(√N). Grover no solo diseñó un método eficaz: alcanzó el límite teórico absoluto que permite la mecánica cuántica para este tipo de problemas.

Cómo funciona el algoritmo de Grover paso a paso

Al margen de las matrices unitarias, el algoritmo se apoya en cuatro etapas conceptuales sustentadas en principios físicos intuitivos:

Paso 1: Superposición uniforme (disponer todas las respuestas al unísono)

El algoritmo comienza situando las N respuestas potenciales en un estado equiprobable de superposición cuántica. Es análogo a colocar todas las cartas boca arriba sobre una mesa infinita, asignando a cada una la misma amplitud de probabilidad. Ninguna carta parte con ventaja. El procesador cuántico abarca todos los candidatos a la vez, cada uno con una amplitud de 1/√N.

Este paso por sí solo no resuelve el problema, ya que una medición instantánea arrojaría un resultado completamente al azar. La verdadera mecánica diferencial tiene lugar en la siguiente fase.

Paso 2: El oráculo (marcado del objetivo mediante inversión de fase)

El oráculo opera como una función de caja negra capaz de validar la respuesta correcta. En el momento en que identifica el elemento buscado, invierte su fase en 180 grados. Siguiendo el ejemplo de las cartas, sería equivalente a marcar el reverso del as de picas con una tinta ultravioleta invisible: a simple vista se percibe idéntico al resto, pero su amplitud contiene ahora un signo negativo oculto.

El oráculo no desvela la ubicación del elemento; se limita a señalarlo. Esta distinción computacional es determinante.

Paso 3: Amplificación de amplitud (inversión respecto a la media)

Aquí interviene el principio físico central. El algoritmo calcula el promedio de amplitud de todos los estados y refleja cada valor respecto a dicha media. El elemento marcado (que se situaba por debajo del promedio debido a su fase negativa) sale proyectado con fuerza por encima de la media. Paralelamente, los elementos no marcados ven reducida su amplitud.

Al repetir los pasos 2 y 3 de manera cíclica, la amplitud del elemento objetivo aumenta en cada iteración mientras las demás decrecen. Se trata de interferencia constructiva y destructiva aplicada directamente a la probabilidad cuántica.

Paso 4: Medición (colapso en la respuesta definitiva)

Una vez completado el número preciso de iteraciones, se efectúa la medición del estado cuántico. La probabilidad de obtener el elemento marcado roza ya prácticamente el 100 %. El as de picas ha sido localizado.

¿Por qué exactamente π/4 · √N iteraciones? (El riesgo de la sobrerrotación)

La amplitud del estado objetivo describe una función sinusoidal a lo largo de las iteraciones: asciende gradualmente, alcanza un pico máximo y desciende de nuevo. El momento idóneo para detener el proceso se sitúa en torno a (π/4)√N iteraciones. Si se sobrepasa ese umbral, la probabilidad empieza a caer; es lo que en física cuántica se conoce como sobrerrotación (over-rotation).

Es exactamente igual que empujar a un niño en un columpio: si aplicas la fuerza en el instante exacto, gana altura; si continúas empujando fuera de compás cuando ya superó el punto más alto, frenarás su trayectoria. En el algoritmo de Grover la precisión rítmica es innegociable: excederse en las iteraciones empeora el resultado.

Una analogía física para visualizar el proceso

Pensemos en unos auriculares con cancelación activa de ruido. Su micrófono registra el sonido ambiental, el procesador interno genera una onda desfasada inversa y ambas señales interfieren destructivamente: el silencio neutraliza el barullo exterior.

La amplificación de amplitud de Grover aplica una lógica idéntica sobre las amplitudes de probabilidad. El «ruido» equivale al conjunto de respuestas erróneas. El algoritmo genera una versión reflejada de esa señal global y la superpone, anulando los candidatos incorrectos por interferencia destructiva. Por el contrario, la respuesta correcta —al conservar su fase invertida por el oráculo— experimenta una interferencia constructiva que refuerza su presencia tras cada ciclo.

Otra perspectiva visual consiste en arrojar una piedra a un estanque en reposo y lanzar de inmediato una segunda piedra con la cadencia y distancia exactas. Allí donde coinciden dos crestas, el agua se eleva pronunciadamente (interferencia constructiva); donde choca una cresta con un valle, la superficie queda lisa (interferencia destructiva). El algoritmo de Grover traslada este principio a la escala cuántica: hace que las opciones falsas se anulen entre sí y que la solución correcta emerja con la máxima amplitud.

Impacto real: qué cambia y qué no con este algoritmo

La seguridad de la criptografía simétrica se reduce a la mitad. Es su consecuencia más tangible en ciberseguridad. AES-128 ofrece un espacio de claves de 2¹²⁸. Un ataque clásico por fuerza bruta exigiría unas 2¹²⁷ operaciones. El algoritmo de Grover rebaja esa exigencia a unas 2⁶⁴, una cota asumible para un ordenador cuántico maduro. ¿La contramedida? Migrar a AES-256, cuya seguridad efectiva frente a Grover se sitúa en 2¹²⁸ bits, un estándar plenamente robusto.

NO vulnera RSA ni la criptografía de curvas elípticas. Ese cometido atañe al algoritmo de Shor. Grover ofrece una aceleración cuadrática, mientras que Shor aporta una ventaja exponencial frente a la factorización de enteros y logaritmos discretos. Confundir ambos métodos es uno de los equívocos más extendidos en la divulgación de la computación cuántica.

Optimización combinatoria. Retos como el problema del viajante, el coloreado de grafos o la resolución de problemas SAT pueden plantearse como búsquedas dentro de un espacio de soluciones. Grover aporta una reducción cuadrática en esa fase exploratoria, una propiedad valiosa cuando se integra en marcos algorítmicos híbridos más complejos.

Mitos comunes y el cuello de botella de la QRAM

Surge a menudo la misma pregunta: «Si el algoritmo de Grover acelera las búsquedas en bases de datos, ¿por qué no se implementa para optimizar Google o agilizar consultas en SQL?»

La respuesta reside en el cuello de botella de la QRAM (memoria cuántica de acceso aleatorio).

Grover asume como condición previa que la base de datos ya se encuentra cargada en superposición cuántica. Sin embargo, transferir una base de datos clásica de N registros a una memoria accesible por el procesador cuántico (QRAM) conlleva por sí solo un tiempo de O(N). Habrías invertido el mismo tiempo en cargar los registros que el que tardaría un ordenador clásico en escanearlos de principio a fin. La aceleración cuadrática se disipa por completo antes de ejecutar la primera iteración.

En la actualidad no existe hardware de QRAM capaz de trasladar datos clásicos a estados cuánticos de forma eficiente a escala, y los obstáculos de ingeniería para lograrlo son monumentales. No es un reto que se resuelva en un lustro; representa una barrera arquitectónica estructural.

Por ello, el algoritmo de Grover muestra su potencial cuando la «base de datos» se genera sobre la marcha mediante un circuito cuántico —como al computar una función hash o validar una restricción lógica— en lugar de leerse desde un disco duro convencional. Su territorio natural es la criptografía y la optimización, no los motores de indexación web.

A esto se suma el contexto actual de la era NISQ: los procesadores cuánticos disponibles disponen de entre unos pocos cientos y alrededor de un millar de cúbits ruidosos con tiempos de coherencia breves. Ejecutar Grover en espacios de búsqueda críticos (como 2¹²⁸) exigirá miles de cúbits lógicos corregidos y tolerantes a fallos.

Preguntas frecuentes sobre el algoritmo de Grover

¿El algoritmo de Grover proporciona una aceleración exponencial o cuadrática?

Es cuadrática. Reduce la complejidad temporal de O(N) a O(√N). Supone una aceleración de tipo polinómico, no exponencial. Posee un gran valor computacional, pero se diferencia estructuralmente del algoritmo de Shor, cuya aceleración sí es exponencial en la factorización de números enteros.

¿Por qué no es viable aplicar Grover en motores de búsqueda web?

Por tres motivos principales: (1) el tiempo de carga en la QRAM anula la ganancia teórica, (2) los buscadores web trabajan con índices invertidos estructurados y criterios heurísticos de clasificación, no con fuerza bruta no ordenada, y (3) la tecnología cuántica actual no dispone de interfaces escalables para comunicarse con bases de datos clásicas masivas. Grover da respuesta a un problema computacional distinto al funcionamiento de un motor de búsqueda.

¿Qué ocurre si el algoritmo de Grover ejecuta más iteraciones de las debidas?

La probabilidad de éxito decae notablemente. La amplitud del estado diana evoluciona de forma sinusoidal: asciende hasta rozar su punto óptimo en torno a (π/4)√N iteraciones y luego retrocede. La sobrerrotación provocada por un exceso de ciclos incrementa drásticamente las opciones de medir un resultado incorrecto. La exactitud en el número de iteraciones forma parte indisociable de la formulación del algoritmo.