Algoritmo Cuántico de Grover: Un algoritmo de búsqueda optimizado por superposición cuántica

Todos somos conscientes de la importancia de optimizar los algoritmos de búsqueda. Vivimos en una era tecnológica donde la información crece a un ritmo imparable, y encontrar un dato concreto en medio de este océano de datos se ha convertido en un desafío cada vez más complejo. Hoy en día, los algoritmos clásicos resuelven este problema con rapidez cuando el volumen de información es pequeño. Pero a medida que los datos aumentan y menos estructurados se encuentran, la tarea se parece cada vez más a ”encontrar una aguja en un pajar”, como bien dice el refrán.

Figura 1: Algoritmo Cuántico de Grover

Un algoritmo de búsqueda optimizado por superposición cuántica 

Entonces, surge la pregunta: ¿hemos llegado al límite de lo que pueden hacer los algoritmos de búsqueda? ¿Realmente no podemos buscar más rápido? Evidentemente no. Hace un par de años vimos cómo AlphaDev era capaz de optimizar los algoritmos de ordenación, que tienen un impacto en los algoritmos de búsqueda, pero es que además, la respuesta a un Search más óptimo podría llegar con la inminente revolución de los ordenadores cuánticos.

La tecnología cuántica hoy en día

Los ordenadores cuánticos están en boca de todos, y para quienes aún no lo sepan, estas máquinas utilizan principios de la Mecánica Cuántica para resolver ciertos problemas de forma mucho más rápida y eficiente que los ordenadores convencionales. Y de ellos se ha hablado por este blog en algunos artículos que tienes aquí.

• Quantum Computing Cybersecurity Preparedness Act: Comienza la era de Ciberseguridad Post-Quantum en Estados Unidos
• Hamming Quasi-Cyclic (HQC-KEM): Nuevo Key-Encapsulation Mechanism en Post-Quantum Cryptography
• FrodoKEM: Un Key-Encapsulation Mechanism Quantum-Safe (PQC) que recibe su nombre por "El señor de los Anillos"
• La Gran Búsqueda de Números Primos de Mersenne en Internet para superar el mayor Número Primo conocido hasta la fecha
• Cómo acelerar los algoritmos de Inteligencia Artificial con Computadores Analógicos Ópticos (AOC)
• Premio Nobel en Física 2025: El trabajo del "Efecto Tunel" que trajo la cuántica a nuestro mundo y abrió la puerta a los ordenadores cuánticos
• Un Reloj Atómico Óptico del MIT con Optimización Cuántica para medir el Tiempo del Futuro
• Quantum Cryptography: Una comunicación con cifrado cuántico
• Factorización de RSA con un Optimizador de Quantum Computing (y Classic Computing)
• Cuánto del tráfico en Internet funciona con Post-Quantum Cryptography

Como siempre explicamos, no se trata de un reemplazo de tecnología, sino de una herramienta complementaria, especialmente útil para tareas muy específicas. Un ejemplo es el famoso algoritmo de Shor, que amenaza los sistemas criptográficos actuales, y que ha obligado a trabajar en los Algoritmos de Criptografía Post-Cuántica de los que hablamos en nuestro libro de Quantum Security.

Figura 2: Quatum Security: Tecnología Cuántica & Ciberseguridad.

Criptográfica Cuántica y Post-Cuántica. 

Nuestro nuevo libro en 0xWord escrito por: Chema Alonso,

Pablo González, Fran Ramírez, Carmen Torrano, Daniel Romero,

Javier Álvarez, Mario Piattini, Iker Pastor, Pablo García Bringas

Pero hoy nos centraremos en otro de los grandes hitos de los algoritmos cuánticos que ya ha pasado al historia con el nombre de: El algoritmo de Grover.

Algoritmo de Grover

El Algoritmo de Grover está diseñado para encontrar una solución dentro de un conjunto desordenado de datos, lo que se conoce como ”problema de búsqueda”. En términos sencillos, este algoritmo aprovecha las propiedades cuánticas para localizar lo que buscamos de forma mucho más eficiente que los métodos clásicos. Pongamos un ejemplo fácil de visualizar: el Sorteo de Navidad. 

Figura 3: Representación del Algoritmo de Grover en un Circuito Cuántico

Imaginemos que queremos encontrar la bola ganadora del premio gordo entre miles de opciones. No tenemos ninguna característica que nos haga afinar la búsqueda, descartar grupos, o optimizar un proceso basado en alguna característica de la bola. Todas son iguales y hay que revisarlas. Con un método clásico, tendríamos que revisar una por una hasta dar con la correcta. Si hay 1000 bolas, en promedio necesitaríamos alrededor de 500 intentos.  En cambio, el algoritmo de Grover permite analizar todas las posibilidades de manera simultánea gracias a la Superposición Cuántica, reduciendo drásticamente el número de operaciones necesarias.

Figura 4: Ejemplo de un sorteo: mientras un método clásico revisa las bolas

una a una, el algoritmo de Grover evalúa todas las posibilidades a la vez.

Esosí,como casi todo en el mundo cuántico, el algoritmo de Grover tiene sus limitaciones. En primer lugar, es probabilístico: no garantiza un resultado correcto al 100%, sino que ofrece una solución con una cierta probabilidad de éxito. Para maximizar esta probabilidad, es necesario aplicar el algoritmo un número específico de veces, como se muestra en la siguiente gráfica. Además, es recomendable verificar rápidamente si el resultado obtenido es el correcto.

Figura 5: Ejemplo de probabilidad de éxito del algoritmo de Grover

en función del número de iteraciones.

Otra limitación importante es que, para conjuntos pequeños de datos, el Algoritmo de Grover no es más rápido que los métodos clásicos. De hecho, su ventaja se hace evidente sólo cuando el número de posibilidades es muy grande.

% comparacion_grover.m
% Comparación f(x) = 2^(log2(x)) y
%           g(x) = 2^(log2(x)/2) * (56*log2(x) - 112) + 1
% Ejecutar en MATLAB o Octave.

clear; close all; clc;

% ---------------------------
% Parámetros y dominio
% ---------------------------
x_min = 4;           % evitar log2(x) problemático y que g sea razonable
x1_max = 1200;       % rango pequeño
x2_max = 1e7;       % rango grande
 

% Dominios (vectorizados)
x1 = linspace(x_min, x1_max, 2000);

% para rango grande usamos espaciado logarítmico
x2 = linspace(x_min, x2_max, 10000);

% ---------------------------
% Definición de funciones
% ---------------------------
% f(x) = 2^(log2(x)) = x (pero usamos la forma pedida)
f = @(x) 2.^(log2(x));

% g(x) = 2^(log2(x)/2) * (56*log2(x) - 112) + 1
g = @(x) (2.^(log2(x) ./ 2)) .* (56 .* log2(x) - 112) + 1;

% Evaluaciones
y1_f = f(x1);
y1_g = g(x1);

y2_f = f(x2);
y2_g = g(x2);

% ---------------------------
% Impresión de comprobación numérica
% ---------------------------
x_test = 1024;
fprintf('Comprobación en x = %g:\n', x_test);
fprintf('  f(%g) = %g\n', x_test, f(x_test));
fprintf('  g(%g) = %g\n', x_test, g(x_test));
% Esperado: f(1024)=1024, g(1024)=14337 (según cálculo manual)

% ---------------------------
% Figura 1: rango pequeño (lineal)
% ---------------------------
figure('Name','Comparación Grover - Rango Pequeño','NumberTitle','off','Color','w');
plot(x1, y1_f, 'r-', 'LineWidth', 2); hold on;
plot(x1, y1_g, 'b-', 'LineWidth', 2);
xlabel('Número de datos (N)');
ylabel('Número de operaciones');
title('Comparación: Rango Pequeño (0 – 1200)');
legend('Clásico: 2^{log_2(x)}','Grover', 'Location','northwest');
grid on;
xlim([0 x1_max]);
% ajustar ylim para que se vea bien (se adapta al máximo entre ambas curvas)
ylim([0, max(max(y1_f), max(y1_g)) * 1.05]);
set(gca,'FontSize',12);

% ---------------------------
% Figura 2: rango grande (log-log)
% ---------------------------
figure('Name','Comparación Grover - Rango Grande','NumberTitle','off','Color','w');
plot(x2, y2_f, 'r-', 'LineWidth', 2); hold on;
plot(x2, y2_g, 'b-', 'LineWidth', 2);
xlabel('Número de datos (N)');
ylabel('Número de operaciones');
title('Comparación: Rango Grande (hasta 10^{10})');
legend('Clásico: 2^{log_2(x)}','Grover', 'Location','northwest');
ylim([0, 13e6]);
grid on;
set(gca,'FontSize',12);


% ---------------------------
% Opcional: guardar figuras (descomentar si quieres)
% ---------------------------
% saveas(figure(1), 'grover_rango_pequeno.png');
% saveas(figure(2), 'grover_rango_grande_loglog.png');

% ---------------------------
% Mensaje de fin
% ---------------------------
disp('Gráficas generadas. Revisa la ventana de figuras.');

Esto se puede analizar teóricamente estudiando el número de operaciones (puertas lógicas) que requiere cada enfoque. Tienes el código anterior para MATLAB u Octave, por si lo quieres probar.

Figura 6: Número de operaciones necesarias según el tamaño

del conjunto de datos: Grover (azul) vs. clásico (rojo)

Pero esto no es un problema real, ya que la ventaja del Algoritmo de Grover se vuelve abrumadora cuando trabajamos con millones de posibilidades o más. De hecho, esta escala se alcanza rápidamente. Por ejemplo, con sólo 20 qubits, ya tenemos más de un millón de combinaciones posibles.

Figura 7: La misma gráfica anterior, pero para un rango mayor de datos.

Se observa cómo Grover supera claramente a los métodos clásicos.

Todo esto, lo explica muy bien en el siguiente vídeo Ket.G, un canal de Computación Cuántica, más que recomendable para aprender de este mundo.

Figura 8: ¿Es el Algoritmo de Grover más lento? Contemos operaciones en Ket.G

En resumen, el Algoritmo de Grover es especialmente útil cuando necesitamos buscar una o varias soluciones dentro de un conjunto enorme y desordenado de datos. Sus aplicaciones son muy prometedoras en áreas como :

Criptoanálisis: reduciendo drásticamente el tiempo necesario para romper sistemas criptográficos simétricos.

Optimización: encontrando soluciones rápidas en problemas matemáticos complejos.

Big Data: realizando búsquedas exhaustivas en grandes volúmenes de datos de manera eficiente.

Los ordenadores cuánticos están en camino, y con ellos, algoritmos como el de Grover que prometen revolucionar nuestra forma de procesar la información. La pregunta es: ¿estamos preparados para esta revolución?

Figura 9: Foro Público de Quantum Security de

la Universidad de Deusto en MyPublicInbox

Si quieres, puedes participar, comentar y aprender más sobre estos temas en el Foro de Quantum Security al que puedes conectarte con tu cuenta de MyPublicInbox. Primero inicia sesión con tu cuenta de MyPublicInbox, y luego visita este enlace para poder entrar en el foro.

Saludos,

Autor: Daniel Romero Ruiz

Contactar con Daniel Romero Ruiz