El algoritmo de Simon resuelve un problema de «periodo oculto» de forma exponencialmente más rápida que cualquier método clásico. Presentado en 1994, tiene un lugar de honor en la historia: fue la chispa que llevó a Peter Shor a idear su célebre algoritmo de factorización. Es el primer ejemplo de una ventaja cuántica exponencial demostrable, y el puente conceptual entre los algoritmos de juguete y los que amenazan la criptografía real.
📋 Resumen rápido: imagina una función que empareja los números de dos en dos según un patrón secreto: dos entradas dan el mismo resultado solo si se diferencian en una cadena oculta s. Encontrar s con un ordenador clásico exige un número gigantesco de pruebas —crece exponencialmente con el tamaño del problema—. El algoritmo de Simon lo consigue con apenas unas pocas consultas cuánticas, del orden del número de bits. La diferencia entre «exponencial» y «lineal» es justo lo que hace fascinante a este algoritmo.
Última actualización: julio de 2026.
El problema de Simon
El escenario vuelve a ser el de un oráculo o caja negra, pero con una estructura especial. La función esconde una cadena secreta s de n bits, y cumple una promesa: dos números cualesquiera producen el mismo resultado si y solo si se diferencian exactamente en s (en el sentido de la suma bit a bit). Dicho de otro modo, la función es «dos a uno»: cada valor de salida corresponde a exactamente dos entradas, y esas dos entradas siempre están separadas por la misma distancia secreta s. El objetivo es descubrir s.
Es un problema de «periodicidad» en un sentido abstracto: s es el periodo que hace que la función se repita. Y aunque suene artificial, esa idea de buscar un periodo oculto es exactamente la que, generalizada, permite factorizar números y romper el cifrado RSA. Simon capturó la esencia del problema en su forma más limpia.
Una analogía: dos llaves para la misma cerradura
Piensa en un enorme llavero donde cada cerradura se abre exactamente con dos llaves distintas, y donde el «salto» entre esas dos llaves es siempre el mismo número secreto. Si pruebas llaves al azar, tendrás que acumular muchísimas antes de dar por casualidad con dos que abran la misma cerradura y así deducir el salto secreto. Ese es el trabajo clásico: buscar una coincidencia a ciegas. El algoritmo cuántico, en cambio, no busca coincidencias una a una: interroga todas las llaves a la vez y, mediante interferencia, extrae directamente pistas sobre el salto secreto en cada consulta.
La versión clásica: por qué es exponencial
Para un ordenador clásico, la única estrategia es buscar una «colisión»: dos entradas distintas que den el mismo resultado. En cuanto encuentras una pareja así, la cadena secreta s es simplemente la diferencia entre ambas, y el problema está resuelto. El obstáculo es cuántas pruebas hacen falta para topar con esa pareja.
Aquí interviene un razonamiento parecido al de la «paradoja del cumpleaños». Para tener una probabilidad razonable de encontrar una colisión por azar, hay que consultar del orden de la raíz cuadrada del número total de entradas posibles. Y como el número de entradas es 2 elevado a n, eso significa alrededor de 2 elevado a n medios consultas: una cantidad que se dispara exponencialmente. Para n = 100, hablamos de un número astronómico de pruebas, fuera del alcance de cualquier superordenador. No es que el algoritmo clásico sea torpe: se puede demostrar que ninguna estrategia clásica lo hace sustancialmente mejor.
La versión cuántica: exponencialmente más rápida
El algoritmo de Simon encuentra s con un número de consultas que crece solo linealmente con n: bastan del orden de n llamadas al oráculo, más un cálculo clásico sencillo al final. Frente a las 2 elevado a n medios consultas clásicas, es un salto descomunal. Para dar magnitud: donde un método clásico necesitaría billones de billones de pruebas, el cuántico necesita unas decenas. Esta es la primera vez, en la historia de la computación cuántica, que se demostró una ventaja exponencial —no solo cuadrática— para un problema bien definido. Ese detalle lo convirtió en un antes y un después.
Paso a paso: cómo funciona
El algoritmo combina una parte cuántica y una parte clásica. La parte cuántica usa dos registros de qubits:
- Superposición: se aplica la puerta de Hadamard al primer registro, poniéndolo en superposición de todos los números a la vez.
- Consulta al oráculo: la caja negra calcula la función y guarda el resultado en el segundo registro. Por la estructura «dos a uno», el primer registro queda en una superposición de exactamente dos números: uno cualquiera y ese mismo más s.
- Segunda transformada de Hadamard: se aplica Hadamard otra vez al primer registro. La interferencia hace que solo sobrevivan ciertos resultados.
- Medición: al medir, se obtiene un número y con una propiedad clave: su producto escalar con la cadena secreta s es cero (módulo 2). Es decir, cada medición entrega una «ecuación» que s debe cumplir.
Una sola medición no basta para conocer s: solo da una ecuación, y hay muchas cadenas que la cumplen. Pero repitiendo la parte cuántica unas cuantas veces se acumulan varias ecuaciones independientes.
El post-procesado clásico: resolver el sistema
Aquí entra la parte clásica, y es sorprendentemente sencilla. Cada ejecución del circuito cuántico aporta una ecuación lineal que la cadena secreta debe satisfacer. Repitiendo el proceso del orden de n veces, se reúnen suficientes ecuaciones independientes como para formar un sistema que tiene una única solución no trivial: precisamente s. Resolver ese sistema de ecuaciones lineales módulo 2 es una tarea rutinaria para un ordenador clásico, del tipo que se hace con eliminación gaussiana en un instante.
Este reparto de trabajo —el ordenador cuántico genera las pistas, el clásico las combina— es una característica que reaparece en muchos algoritmos cuánticos posteriores, incluido el de Shor. La máquina cuántica hace solo la parte que ninguna clásica sabe hacer rápido; el resto se delega en hardware convencional.
Un ejemplo concreto
Tomemos un caso pequeño con cadena secreta s = 11 (dos bits). La función empareja las entradas de forma que 00 y 11 dan el mismo resultado, y 01 y 10 dan otro resultado común: cada pareja está separada exactamente por s = 11. Un ordenador clásico tendría que ir probando entradas hasta topar con una de esas parejas. El algoritmo de Simon, con un par de ejecuciones cuánticas, obtiene ecuaciones como «el producto de y con s es cero», y al combinarlas deduce que s = 11. Con dos bits el ahorro es modesto, pero la ventaja crece explosivamente con el tamaño: con veinte bits, el clásico necesitaría del orden de un millón de pruebas y el cuántico apenas una veintena de consultas.
El eslabón que llevó a Shor
Esta es la parte más importante de la historia. Cuando Daniel Simon presentó su algoritmo en 1994, demostró algo que hasta entonces solo se intuía: que un ordenador cuántico podía resolver un problema estructurado de forma exponencialmente más rápida que uno clásico. Peter Shor conocía ese trabajo, y fue precisamente la estructura del algoritmo de Simon —buscar un periodo oculto mediante interferencia— la que le hizo ver que la factorización de números podía atacarse de la misma manera. Factorizar se reduce a encontrar el periodo de una función, y encontrar periodos es justo lo que la técnica de Simon sabía hacer.
Pocos meses después, Shor publicó su algoritmo de factorización, sustituyendo la sencilla transformada de Hadamard de Simon por la más potente transformada de Fourier cuántica, capaz de detectar periodos numéricos y no solo binarios. Sin el algoritmo de Simon como inspiración directa, la historia de la computación cuántica —y la urgencia actual por migrar a criptografía postcuántica— probablemente habría sido muy distinta. Simon abrió la puerta; Shor la cruzó.
Simon y el problema del subgrupo oculto
Con el tiempo se entendió que el algoritmo de Simon, el de Bernstein-Vazirani y el de Shor son casos particulares de un mismo marco abstracto: el problema del subgrupo oculto. Todos consisten en descubrir una estructura escondida (un periodo, una cadena, un subgrupo) aprovechando que la interferencia cuántica revela esa estructura de golpe, mientras que un ordenador clásico tiene que reconstruirla pieza a pieza. La estimación de fase y la transformada de Fourier cuántica son las herramientas que hacen ese trabajo en los casos más generales. El algoritmo de Simon es la versión más limpia y didáctica de ese patrón profundo.
La familia de algoritmos de oráculo
El algoritmo de Simon pertenece a un pequeño club de algoritmos que demuestran ventaja cuántica sobre cajas negras, cada uno con su matiz:
- Deutsch-Jozsa: decide si una función es constante o equilibrada; ventaja exponencial pero para un problema con respuesta binaria.
- Bernstein-Vazirani: reconstruye una cadena secreta con una sola consulta; ventaja lineal y determinista.
- Simon: encuentra un periodo oculto con ventaja exponencial y un problema genuinamente más rico.
La progresión no es casual: cada uno prepara el terreno para el siguiente, y todos comparten el esqueleto de superposición, oráculo e interferencia mediante transformadas. Simon es el más ambicioso de los tres y el que más cerca está, en espíritu, del algoritmo de Shor.
Un algoritmo genuinamente híbrido
Vale la pena subrayar una lección que el algoritmo de Simon enseña con claridad: los algoritmos cuánticos rara vez son «todo cuántico». El de Simon reparte el trabajo entre una fase cuántica que genera ecuaciones y una fase clásica que las resuelve. Esta filosofía híbrida —usar el ordenador cuántico solo para el paso que ofrece ventaja y dejar el resto a los clásicos— es la que domina hoy el diseño de algoritmos, desde la química cuántica hasta la optimización. Simon lo mostró tres décadas antes de que se convirtiera en la norma.
Importancia y limitaciones
Como sus hermanos de oráculo, el algoritmo de Simon no resuelve un problema práctico directo: la función «dos a uno con periodo oculto» es una construcción teórica. Su valor es doble. Por un lado, histórico y conceptual: demostró la primera ventaja exponencial y engendró el algoritmo de Shor. Por otro, pedagógico: ilustra a la perfección cómo la interferencia cuántica extrae estructura global escondida, y cómo se combinan las partes cuántica y clásica. También sirve, como Bernstein-Vazirani, para poner a prueba hardware cuántico real con circuitos de tamaño moderado. Lo que no debe esperarse de él es una aplicación comercial: su descendiente Shor es quien lleva la técnica al terreno práctico —y temido— de la criptografía.
Implementar el algoritmo en Qiskit
El circuito para un caso pequeño puede escribirse a mano y ejecutarse en un simulador. El esquema general es:
from qiskit import QuantumCircuit
n = 2 # bits de entrada
qc = QuantumCircuit(2*n, n) # dos registros de n qubits
qc.h(range(n)) # superposicion del primer registro
# --- oraculo con periodo oculto s (se construye segun s) ---
# copiar/entrelazar el primer registro en el segundo segun la funcion
qc.barrier()
qc.h(range(n)) # segunda transformada de Hadamard
qc.measure(range(n), range(n))
# Cada ejecucion da una y con y . s = 0 (mod 2).
# Repetir ~n veces y resolver el sistema lineal mod 2 en el ordenador clasico.
La clave del ejercicio está en construir el oráculo que codifica un periodo s concreto, ejecutar el circuito varias veces para recoger ecuaciones y, finalmente, resolver el sistema con álgebra lineal módulo 2 en Python. Ver cómo unas pocas ejecuciones bastan para deducir un periodo que un método clásico tardaría una eternidad en encontrar es la mejor demostración práctica de la potencia del algoritmo.
Por qué la interferencia hace el trabajo
El motor silencioso del algoritmo es la interferencia. Tras consultar el oráculo, el primer registro contiene dos números a la vez —los dos que comparten resultado—, y al aplicar la segunda transformada de Hadamard esos dos «caminos» se combinan. La clave es que interfieren de forma constructiva solo para aquellos valores y compatibles con el periodo secreto, y de forma destructiva para el resto, que se cancelan y nunca aparecen al medir. Es el mismo principio que hace funcionar a todos los grandes algoritmos cuánticos: no se trata de «probar todas las opciones y elegir», sino de disponer las amplitudes para que las respuestas incorrectas se anulen entre sí y solo sobrevivan las útiles. En el algoritmo de Simon, esa cancelación es lo que garantiza que cada medición aporte una ecuación válida sobre la cadena secreta.
Simon en el hardware real
A diferencia de Shor, que necesita miles de qubits corregidos para atacar claves reales, el algoritmo de Simon puede ejecutarse en instancias pequeñas con los procesadores actuales, precisamente porque su circuito es poco profundo para tamaños modestos. Se han realizado demostraciones con unos pocos qubits que recuperan correctamente el periodo secreto, sirviendo como banco de pruebas de la interferencia y de la fidelidad de las puertas de dos qubits. No es una aplicación útil —el problema sigue siendo artificial—, pero sí una validación tangible de que los principios funcionan en silicio y no solo sobre el papel. Para tamaños grandes, en cambio, el ruido acaba borrando la interferencia, igual que ocurre con el resto de algoritmos: el reto de fondo sigue siendo la corrección de errores.
Preguntas frecuentes
¿Qué hace el algoritmo de Simon?
Encuentra una cadena secreta (un «periodo oculto») escondida en una función dos a uno, de forma exponencialmente más rápida que cualquier algoritmo clásico.
¿Por qué es históricamente importante?
Fue la primera demostración de una ventaja cuántica exponencial para un problema bien definido, y su estructura inspiró directamente el algoritmo de factorización de Shor.
¿Cuánto más rápido es que un método clásico?
Un ordenador clásico necesita del orden de 2 elevado a n medios consultas; el algoritmo de Simon, solo del orden de n. La diferencia es exponencial.
¿Es un algoritmo totalmente cuántico?
No: es híbrido. La parte cuántica genera ecuaciones que la cadena secreta debe cumplir, y una parte clásica sencilla las resuelve con álgebra lineal.
¿Qué relación tiene con el algoritmo de Shor?
Shor generalizó la idea de Simon —buscar un periodo oculto— sustituyendo la transformada de Hadamard por la transformada de Fourier cuántica, lo que le permitió factorizar números y amenazar el cifrado RSA.
¿Tiene aplicaciones prácticas?
No de forma directa: su función es una construcción teórica. Su valor es histórico, conceptual y pedagógico, además de servir para probar hardware cuántico.
⚠️ Aviso: contenido divulgativo con fines educativos. Para implementaciones consulta la documentación oficial de tu SDK cuántico.