El algoritmo de Grover: búsqueda cuántica
Lección 11 de 23 del curso «Cuántica». Gratis, con animaciones y un test.
El problema de las cajas
Tienes N cajas cerradas y un regalo en una. Sin pistas: abres, miras, cierras. De media abrirás la mitad, en el peor caso todas. La versión cuántica: tenemos un “oráculo”, un circuito que dice si una caja es la buena. En 1996 Lov Grover, de Bell Labs, mostró cómo encontrar el regalo en unas √N preguntas. Para un millón de cajas son unas 800 preguntas en lugar de medio millón.
Cómo funciona: marcar y reflejar
Primero, las puertas H dan a todas las cajas la misma amplitud. Paso 1: el oráculo pone un menos a la amplitud de la caja buena, el paso de marca de nuestra receta. Paso 2: “reflexión respecto a la media”. La media bajó un poco por el menos, y cada amplitud se voltea alrededor de ella. Las cajas normales bajan un poco y la negativa salta muy arriba. Repites “marca + reflejo” y la caja buena crece cada vez.
La clave es parar a tiempo
Un detalle no evidente: Grover no es “cuanto más, mejor”. La amplitud de la caja buena crece como una flecha que gira. Con 64 cajas, tras unos 6 pasos la probabilidad es casi 100%, y si sigues, la flecha se pasa y la probabilidad empieza a bajar. Por eso el número de pasos se calcula antes: unos π/4 · √N. Si no sabes cuántos regalos hay, existen variantes ingeniosas, pero eso ya es detalle.
Grover y el cifrado
Adivinar una clave de cifrado es justo buscar una caja entre muchísimas. AES-128 tiene 2 elevado a 128 opciones. Grover saca la raíz y quedan 2 elevado a 64 pasos, así que la seguridad de “128 bits” pasa a “64 bits”. En la práctica incluso eso es mucho: los pasos de Grover van estrictamente uno tras otro y no se reparten entre miles de máquinas tan fácil como la fuerza bruta normal. Pero la cura es simple y ya se usa: AES-256 sigue dando 128 bits tras Grover.
El límite de velocidad
¿Y si alguien inventa una búsqueda aún más rápida? No: en 1997 cuatro investigadores, Bennett, Bernstein, Brassard y Vazirani, demostraron que en búsqueda “a ciegas” √N es el límite para cualquier ordenador cuántico. De ahí una conclusión importante. Muchos problemas difíciles, como la ruta de reparto óptima, se reducen en el fondo a probar opciones. Un ordenador cuántico los acelera como mucho hasta la raíz, no los vuelve instantáneos. Nadie ha encontrado una aceleración exponencial para ellos.
Dónde Grover es útil de verdad
Suena a “Google cuántico”, pero para buscar en una base de datos normal Grover casi no sirve. Para preguntar al oráculo, primero hay que cargar los datos en memoria cuántica, y eso ya cuesta del orden de N pasos y se come la ventaja. El valor real está donde las “cajas” no se guardan, sino que se calculan con una fórmula: adivinar claves, comprobar soluciones, una subrutina dentro de algoritmos más complejos. Y todo eso requerirá grandes ordenadores con corrección de errores.
Ponte a prueba
- ¿Cuántos pasos de Grover hacen falta para 10 000 opciones?
Respuesta correcta: Unos 80. √10 000 = 100, y π/4 · 100 ≈ 79. Aceleración cuadrática, no instantánea. - Un amigo hizo el triple de pasos de Grover “por si acaso”. ¿Qué pasa?
Respuesta correcta: La probabilidad baja: la flecha se pasa de la respuesta. Grover es una rotación. Pasado el óptimo, la amplitud de la caja buena vuelve a bajar. - ¿Hay que cambiar AES-256 con urgencia por Grover?
Respuesta correcta: No: tras Grover le quedan 128 bits de seguridad. Grover reduce los bits a la mitad, y 128 bits se consideran seguros. Por eso se recomienda AES-256 a largo plazo.
← El mito de “lo prueba todo a la vez” El algoritmo de Shor y RSA →