El algoritmo de Bernstein-Vazirani resuelve un reto muy concreto: descubrir una cadena secreta de bits escondida dentro de una función, y hacerlo con una sola consulta donde un ordenador clásico necesitaría tantas como bits tenga la cadena. Propuesto en 1993, es una de las demostraciones más limpias de que un ordenador cuántico puede batir a uno clásico de forma segura y sin margen de error.
📋 Resumen rápido: imagina una caja negra que, dado un número, responde con un único bit calculado a partir de una clave secreta s. Un ordenador clásico tiene que interrogar la caja una vez por cada bit de s para reconstruirla. El algoritmo de Bernstein-Vazirani lo consigue con una única pregunta cuántica, gracias a dos ingredientes: la puerta de Hadamard aplicada en paralelo y un truco llamado retroceso de fase. El resultado es exacto: la respuesta sale bien siempre, no con alta probabilidad.
Última actualización: julio de 2026.
Qué problema resuelve
El escenario es el de un «oráculo»: una función que actúa como caja negra. Dentro esconde una cadena secreta de n bits, que llamaremos s. Cuando le entregas un número x (también de n bits), la caja calcula el producto escalar de x y s bit a bit, suma esos productos y te devuelve el resultado módulo 2, es decir, un único bit: 0 o 1. En términos llanos: multiplica tu número por la clave secreta de una forma binaria muy sencilla y te da la paridad del resultado.
El objetivo es reconstruir s por completo haciendo el menor número posible de preguntas a la caja. Es un problema artificial, pensado para aislar y medir la ventaja cuántica, más que una tarea de la vida real. Pero precisamente por su pureza se ha convertido en uno de los ejemplos didácticos más citados de toda la disciplina.
La versión clásica: una pregunta por cada bit
Con un ordenador clásico, la estrategia óptima es transparente. Para averiguar el primer bit de s, le preguntas a la caja por el número 1000…0 (un 1 en la primera posición, ceros en el resto): la respuesta es exactamente el primer bit de s, porque el producto escalar solo «activa» esa posición. Para el segundo bit, preguntas por 0100…0, y así sucesivamente. Cada pregunta revela un bit, ni más ni menos.
La consecuencia es clara: reconstruir una clave de n bits exige n preguntas. No hay forma clásica de hacerlo mejor; cada consulta solo puede devolver un bit de información y hay n bits que averiguar. Para una clave de 100 bits, cien preguntas. Aquí está el listón que el algoritmo cuántico va a pulverizar.
La versión cuántica: una sola pregunta
El algoritmo de Bernstein-Vazirani reconstruye la cadena completa con una única consulta a la caja, sea cual sea el número de bits. Cien bits, una pregunta. Mil bits, una pregunta. Es una ventaja lineal —de n a 1— y, lo que es más notable, es determinista: el algoritmo devuelve la respuesta correcta con certeza absoluta, no con una probabilidad alta que haya que confirmar repitiendo. Esta combinación de aceleración garantizada y exactitud perfecta es lo que hace del algoritmo un ejemplo tan valioso.
El truco: el retroceso de fase
El corazón del algoritmo es un mecanismo llamado retroceso de fase (en inglés, phase kickback), que reaparece en muchos algoritmos cuánticos, incluido el de Grover. La idea es preparar un qubit auxiliar en un estado especial (la superposición |0⟩ menos |1⟩). Cuando la caja negra escribe su resultado en ese qubit auxiliar, en lugar de cambiar su valor lo que hace es imprimir un signo —una fase— sobre el registro principal.
Dicho de otro modo: el resultado del cálculo, en vez de aparecer como un bit que hay que leer, se «cuela hacia atrás» convertido en un patrón de signos sobre la superposición de entrada. Ese patrón de signos codifica exactamente la información de la clave secreta. El retroceso de fase es el puente que convierte una respuesta numérica difícil de aprovechar en una estructura de fases que sí podemos manipular con interferencia.
El papel de la transformada de Hadamard
El segundo ingrediente es la puerta de Hadamard aplicada a todos los qubits a la vez, lo que se conoce como transformada de Hadamard. Al principio, sirve para poner el registro en superposición de todos los números posibles simultáneamente, de modo que la única consulta a la caja los «prueba» todos a la vez.
Pero la magia está en aplicarla otra vez al final. Resulta que el patrón de signos que el retroceso de fase ha dejado sobre la superposición es, matemáticamente, la transformada de Hadamard del propio número secreto s. Y como la transformada de Hadamard es su propia inversa, aplicarla una segunda vez deshace la codificación y deja el registro exactamente en el estado s. Al medir, sale s directamente, sin ambigüedad. Es una coreografía perfecta: superponer, dejar que la caja imprima los signos, y volver a transformar para revelar la respuesta.
Paso a paso del circuito
- Inicio: un registro de n qubits en |0⟩ y un qubit auxiliar preparado en el estado |0⟩ menos |1⟩.
- Superposición: se aplica Hadamard a los n qubits, creando una superposición uniforme de todos los números.
- Consulta al oráculo: la caja negra actúa una vez; por retroceso de fase, imprime el patrón de signos correspondiente a s.
- Segunda transformada de Hadamard: deshace la codificación y concentra todo en el estado s.
- Medición: se leen los n qubits y se obtiene s con certeza.
Un ejemplo concreto
Supongamos una clave secreta de tres bits, s = 101. Un ordenador clásico haría tres preguntas: por 100 (devuelve 1), por 010 (devuelve 0) y por 001 (devuelve 1), reconstruyendo 101. El algoritmo cuántico, en cambio, prepara los tres qubits en superposición, deja que la caja imprima los signos en una sola pasada, aplica la transformada de Hadamard de nuevo y mide: los tres qubits salen 1, 0, 1. Una sola consulta frente a tres. Con una clave de treinta bits, sería una consulta frente a treinta; con trescientos, una frente a trescientas. La ventaja crece con el tamaño del problema.
Bernstein-Vazirani frente a Deutsch-Jozsa
El algoritmo pertenece a una familia estrechamente emparentada. Su hermano mayor es el algoritmo de Deutsch-Jozsa, que responde a una pregunta distinta (si una función es constante o «equilibrada») también con una sola consulta frente a las muchas que necesita un clásico. Ambos comparten esqueleto: Hadamard, oráculo con retroceso de fase, Hadamard, medición. La diferencia está en qué información extrae cada uno de ese patrón de fases. Bernstein-Vazirani va un paso más allá: no se limita a una respuesta binaria, sino que reconstruye una cadena completa de bits. Por eso se considera un puente entre el problema de juguete de Deutsch-Jozsa y algoritmos más ambiciosos.
Su lugar en la historia
Bernstein-Vazirani es una pieza clave de la genealogía que culminó en los grandes algoritmos cuánticos. La secuencia histórica —Deutsch, Deutsch-Jozsa, Bernstein-Vazirani, Simon y finalmente el algoritmo de Shor— muestra una escalada: cada algoritmo demostró una ventaja cuántica un poco más contundente que el anterior, y cada uno aportó una técnica que el siguiente reaprovechó. Bernstein-Vazirani, en concreto, refinó el uso de la transformada de Hadamard como herramienta para extraer información global escondida en una función, una idea que desemboca directamente en el uso de la transformada de Fourier cuántica en algoritmos posteriores.
La versión recursiva y la teoría de la complejidad
Más allá de su versión básica, Bernstein y Vazirani propusieron una variante recursiva del problema —apilar el esquema sobre sí mismo varias veces— que demuestra una separación aún mayor entre lo cuántico y lo clásico: no ya lineal, sino superpolinómica. Este resultado tuvo un peso enorme en la teoría de la complejidad computacional, porque fue una de las primeras pruebas rigurosas de que los ordenadores cuánticos pueden ser dramáticamente más eficientes que los clásicos en ciertos problemas, dentro del modelo de oráculos. Sentó bases formales sobre las que se construyó buena parte de la teoría posterior de la computación cuántica.
Importancia práctica y limitaciones
Conviene ser honesto sobre su alcance. Bernstein-Vazirani no resuelve un problema útil de la vida real: la «clave secreta» es un artificio y el oráculo es una construcción teórica. Su valor no es aplicado, sino conceptual y pedagógico. Sirve para tres cosas: demostrar de forma limpia y verificable que existe ventaja cuántica, enseñar mecanismos —retroceso de fase, transformada de Hadamard— que sí aparecen en algoritmos útiles, y ofrecer un banco de pruebas sencillo para validar hardware cuántico real, porque su circuito es corto y su resultado, predecible. Muchos equipos lo ejecutan en sus procesadores como test de calidad: si el chip devuelve la cadena secreta correcta, es señal de que las puertas funcionan con fidelidad razonable.
Implementar el algoritmo en Qiskit
El circuito es lo bastante sencillo como para escribirlo a mano y es un ejercicio recomendable:
from qiskit import QuantumCircuit
s = "101" # cadena secreta a descubrir
n = len(s)
qc = QuantumCircuit(n + 1, n)
qc.x(n); qc.h(n) # qubit auxiliar en |0>-|1>
qc.h(range(n)) # superposicion del registro principal
# oraculo f(x) = s . x (mod 2): una CNOT por cada bit 1 de s
for i, bit in enumerate(reversed(s)):
if bit == "1":
qc.cx(i, n)
qc.h(range(n)) # segunda transformada de Hadamard
qc.measure(range(n), range(n))
Al ejecutarlo, la medición devuelve la cadena secreta con probabilidad prácticamente 1 (en un simulador ideal, exactamente 1). Cambiar s y comprobar que el algoritmo la recupera siempre en una sola consulta es la mejor forma de convencerse de que funciona.
El modelo de oráculos: ¿es hacer trampa?
Una objeción habitual y legítima: si el algoritmo depende de una «caja negra» que calcula la función secreta, ¿no estamos escondiendo la dificultad dentro de esa caja? Es una crítica que merece respuesta. En el modelo de oráculos, tanto el ordenador clásico como el cuántico tienen acceso a la misma caja, en igualdad de condiciones; lo que se compara es cuántas veces necesita cada uno consultarla. Que el cuántico lo logre con una sola consulta y el clásico necesite n es una diferencia real y demostrable, no un truco contable. La caja no favorece a nadie: simplemente, la máquina cuántica sabe extraer más información de cada llamada gracias a la superposición y la interferencia. Dicho esto, es cierto que una ventaja en el modelo de oráculos no garantiza automáticamente una ventaja en problemas reales, donde no hay ninguna caja mágica. Por eso los algoritmos de oráculo se ven como pruebas de concepto y peldaños teóricos, no como soluciones prácticas por sí mismas. Su papel es demostrar qué es posible y aislar los mecanismos que luego hay que trasladar, con mucho más trabajo, a problemas del mundo real.
Muestreo de Fourier: la idea que generaliza
Visto con perspectiva, Bernstein-Vazirani es un caso particular de una técnica más general llamada muestreo de Fourier: preparar una superposición, dejar que un oráculo imprima información en las fases, y aplicar una transformada que convierte esas fases en una respuesta medible. En Bernstein-Vazirani la transformada es la de Hadamard, la más simple. En algoritmos más potentes —como el de Shor— esa transformada se sustituye por la transformada de Fourier cuántica completa, capaz de detectar periodicidades mucho más ricas. Y todos ellos son ejemplos del llamado problema del subgrupo oculto, el marco abstracto que unifica la factorización, el logaritmo discreto y este tipo de búsquedas de estructura escondida. Entender Bernstein-Vazirani es, por tanto, entender en su forma más desnuda el patrón que, elaborado, pone en jaque a la criptografía moderna. Lo que en este algoritmo es un juguete, en el de Shor es una amenaza real; pero la idea de fondo es la misma.
Por qué se enseña de los primeros
De todos los algoritmos cuánticos de oráculo, Bernstein-Vazirani suele ser de los primeros que se enseñan, y hay una razón: reúne, en un circuito cortísimo y un resultado que se lee de un vistazo, casi todas las ideas centrales de la computación cuántica. Superposición para explorar en paralelo, retroceso de fase para codificar información en signos, interferencia mediante Hadamard para revelar la respuesta, y una ventaja sobre lo clásico que se puede enunciar en una frase. Quien entiende de verdad este algoritmo tiene ya en la mano los conceptos que reaparecerán, más sofisticados, en Grover, en Simon y en Shor. No es casualidad que aparezca en prácticamente todos los cursos introductorios y en los primeros tutoriales de los kits de programación cuántica: funciona como el «hola mundo» de los algoritmos con ventaja demostrable. Por eso, aunque no resuelva nada útil, es uno de los mejores puntos de entrada al pensamiento cuántico.
Preguntas frecuentes
¿Qué hace el algoritmo de Bernstein-Vazirani?
Descubre una cadena secreta de bits escondida en una función, con una sola consulta cuántica frente a las n que necesita un ordenador clásico (una por bit).
¿Por qué es más rápido que un algoritmo clásico?
Porque pone todos los números en superposición y usa el retroceso de fase para que una única consulta imprima toda la información de la clave, que luego la transformada de Hadamard revela de golpe.
¿El resultado es seguro o probabilístico?
Es determinista: en un circuito ideal, el algoritmo devuelve la cadena correcta con certeza, no con alta probabilidad.
¿En qué se diferencia de Deutsch-Jozsa?
Comparten estructura, pero Deutsch-Jozsa solo responde si una función es constante o equilibrada, mientras que Bernstein-Vazirani reconstruye una cadena completa de bits.
¿Tiene aplicaciones prácticas?
No resuelve un problema real: su valor es didáctico y como test de hardware. Enseña mecanismos que sí usan algoritmos útiles y sirve para comprobar la fidelidad de un procesador cuántico.
¿Qué relación tiene con el algoritmo de Shor?
Forma parte de la genealogía que culminó en Shor. Refinó el uso de transformadas para extraer información global de una función, idea que desemboca en la transformada de Fourier cuántica de los grandes algoritmos.
⚠️ Aviso: contenido divulgativo con fines educativos. Para implementaciones consulta la documentación oficial de tu SDK cuántico.