Deutsch-Jozsa: El Primer Algoritmo Cuántico de la Historia

📅 Articulo actualizado en dos mil veintiseis

📑 Índice de contenidos

📅 Articulo actualizado en dos mil veintiseis

📑 Índice de contenidos

📅 Última actualización: marzo de 2026. Contenido revisado y verificado.

1985: David Deutsch y la pregunta que lo empezó todo

En 1985, David Deutsch, físico de la Universidad de Oxford y uno de los padres de la computación cuántica, publicó un artículo que planteó una pregunta aparentemente simple pero con consecuencias revolucionarias: ¿puede un ordenador cuántico resolver un problema más rápido que cualquier ordenador clásico?

Deutsch propuso el caso más simple posible. Imagina que tienes acceso a una caja negra, un oráculo, que implementa una función f que toma un bit de entrada y produce un bit de salida. La función solo puede ser de cuatro tipos: f(0)=0, f(1)=0 (constante cero); f(0)=1, f(1)=1 (constante uno); f(0)=0, f(1)=1 (identidad); o f(0)=1, f(1)=0 (negación). Las dos primeras son constantes y las dos últimas son balanceadas.

La pregunta es: ¿puedes determinar si la función es constante o balanceada? Clásicamente, necesitas dos consultas al oráculo para saberlo: evalúas f(0) y f(1) y comparas. Deutsch demostró que un ordenador cuántico puede responder la pregunta con una sola consulta, evaluando f en superposición.

El resultado fue más conceptual que práctico: ahorrar una consulta no es impresionante. Pero demostró el principio: la mecánica cuántica permite extraer información de formas imposibles clásicamente. La puerta estaba abierta.

El problema: constante o balanceada, esa es la cuestión

En 1992, Deutsch se unió a Richard Jozsa para generalizar el resultado a funciones de N bits. El problema de Deutsch-Jozsa es: dada una función f que toma N bits de entrada y produce un bit de salida, prometiendo que f es constante (devuelve el mismo valor para todas las entradas) o balanceada (devuelve cero para exactamente la mitad de las entradas y uno para la otra mitad), determinar cuál es el caso.

Este es un problema de decisión con promesa: no necesitas saber qué función es exactamente, solo si pertenece a la categoría constante o balanceada. La promesa de que la función es una de las dos cosas, y no algo intermedio, es esencial para que el algoritmo funcione.

El espacio de entradas tiene 2^N elementos. Para N=10, son 1.024 entradas posibles. Para N=50, son más de un billón. Para N=100, más que átomos en el universo. La pregunta es cuántas veces necesitas evaluar f para distinguir constante de balanceada.

Por qué un ordenador clásico necesita tantas consultas

Clásicamente, en el peor caso determinista, necesitas evaluar f en 2^(N-1)+1 entradas diferentes para estar seguro. La razón es que si las primeras 2^(N-1) evaluaciones dan todas el mismo resultado, la función podría ser constante o balanceada: una función balanceada podría dar el mismo valor en exactamente la mitad de las entradas, y has sido desafortunado evaluando solo entradas de un mismo lado. Solo al evaluar una entrada más y obtener un resultado diferente, o confirmar que todas son iguales tras superar la mitad, puedes estar seguro.

Con aleatorización, un algoritmo probabilístico clásico puede hacerlo mejor: evaluando k entradas al azar, si todas dan el mismo resultado, la probabilidad de que la función sea balanceada es menor que 2^(1-k). Con k=20 consultas aleatorias, la probabilidad de error es menor que una en un millón. Esto es mucho más eficiente pero no determinista: siempre hay una probabilidad, por pequeña que sea, de equivocarse.

El algoritmo de Deutsch-Jozsa da la respuesta correcta con certeza absoluta en una sola consulta cuántica, independientemente de N. Una consulta frente a más de la mitad de 2^N en el caso determinista: esa es la separación exponencial.

El truco cuántico: superposición, oráculo e interferencia

El algoritmo utiliza tres ingredientes fundamentales de la computación cuántica. Primero, la superposición para evaluar f en todas las 2^N entradas simultáneamente con una sola consulta al oráculo. Segundo, el oráculo cuántico, que aplica f de forma reversible manteniendo la coherencia cuántica. Tercero, la interferencia, que hace que las amplitudes se sumen constructiva o destructivamente de forma que el resultado de la medición contenga exactamente la información deseada.

La clave está en que el oráculo no solo evalúa f en una superposición de entradas, sino que codifica el resultado de cada evaluación como una fase en la amplitud del estado correspondiente. Las entradas donde f vale cero mantienen su fase intacta, y las entradas donde f vale uno ven su fase invertida. Después, las puertas Hadamard finales crean interferencia entre todas estas fases.

Si f es constante, todas las fases son iguales y la interferencia constructiva dirige toda la amplitud al estado cero. Si f es balanceada, las fases positivas y negativas se cancelan exactamente para el estado cero, y la amplitud se distribuye entre otros estados. Medir cero en todos los qubits indica función constante; cualquier resultado diferente de todo ceros indica función balanceada.

El circuito paso a paso con ejemplo de 3 qubits

Para ilustrar el algoritmo con un ejemplo concreto, consideremos una función de tres bits con un oráculo específico. El circuito tiene cuatro registros: tres qubits de entrada y un qubit auxiliar.

Paso uno: preparar los qubits de entrada en el estado cero y el qubit auxiliar en el estado uno. Paso dos: aplicar puertas Hadamard a todos los qubits, creando una superposición uniforme de las ocho entradas posibles en los qubits de entrada, y colocando el qubit auxiliar en el estado menos, la superposición con fase negativa que convierte la evaluación de f en un kickback de fase.

Paso tres: aplicar el oráculo cuántico. Este paso evalúa f simultáneamente en las ocho entradas. Las entradas donde f vale uno ven su amplitud multiplicada por menos uno. Las entradas donde f vale cero no se modifican. El qubit auxiliar facilita este mecanismo de kickback de fase.

Paso cuatro: aplicar puertas Hadamard a los tres qubits de entrada. Este paso transforma las fases relativas en amplitudes medibles. Si f es constante, toda la amplitud se concentra en el estado 000. Si f es balanceada, la amplitud de 000 es exactamente cero y se distribuye entre otros estados.

Paso cinco: medir los qubits de entrada. Si el resultado es 000, la función es constante. Cualquier otro resultado indica función balanceada. No hay probabilidad de error: el resultado es determinista.

Tabla: comparativa consultas clásicas vs cuánticas

Por qué funciona: la interferencia como clave de la ventaja

La interferencia cuántica es el mecanismo fundamental que hace posible el algoritmo. Cuando se aplican las puertas Hadamard finales, cada qubit de entrada se transforma de una superposición de valores de f en una superposición de patrones de interferencia. La amplitud del estado todo-ceros es proporcional a la suma de las fases de todas las entradas.

Si f es constante, todas las fases son iguales, ya sea todas positivas si f es siempre cero, o todas negativas si f es siempre uno. La suma de 2^N fases iguales da una amplitud de magnitud uno para el estado todo-ceros. La probabilidad de medir todo-ceros es exactamente uno.

Si f es balanceada, exactamente la mitad de las fases son positivas y la otra mitad negativas. La suma de 2^N fases con la mitad positivas y la mitad negativas es exactamente cero. La probabilidad de medir todo-ceros es exactamente cero, y toda la amplitud se distribuye entre otros estados.

Este cancelamiento perfecto entre las contribuciones positivas y negativas es una propiedad exclusivamente cuántica que no tiene análogo clásico. Un ordenador clásico no puede crear fases negativas ni interferencia destructiva, y por eso necesita evaluar f muchas veces para determinar si las evaluaciones positivas y negativas se equilibran.

Del algoritmo de Deutsch a Deutsch-Jozsa: la generalización

El camino desde el algoritmo de Deutsch de 1985 hasta Deutsch-Jozsa de 1992 ilustra cómo las ideas en computación cuántica maduraron gradualmente. El algoritmo original de Deutsch para un bit era correcto pero no completamente limpio: tenía una probabilidad de éxito del setenta y cinco por ciento en su formulación original, y requirió refinamientos posteriores.

La versión moderna del algoritmo de Deutsch, y la generalización de Deutsch-Jozsa, se beneficiaron enormemente del trabajo de Cleve, Ekert, Macchiavello y Mosca en 1998, que simplificaron el circuito usando el truco del qubit auxiliar en el estado menos. Este truco, ahora estándar, convierte la evaluación del oráculo en un kickback de fase sin necesidad de medir el qubit auxiliar.

La simplificación fue pedagógicamente crucial: el algoritmo pasó de ser una curiosidad técnica a un ejemplo elegante y comprensible que captura la esencia de la ventaja cuántica en unas pocas líneas de circuito. Es esta versión simplificada la que se enseña hoy en todos los cursos y libros de texto.

El legado: de Deutsch-Jozsa a Shor y Grover

El impacto de Deutsch-Jozsa fue más inspiracional que práctico. Demostró que la computación cuántica no era solo una curiosidad teórica sino una forma genuinamente diferente y potencialmente superior de procesar información. Esta demostración motivó a otros investigadores a buscar problemas donde la ventaja cuántica tuviera consecuencias prácticas.

Daniel Simon, en 1994, generalizó la idea a un problema más estructurado, el problema de Simon, demostrando una separación exponencial incluso frente a algoritmos probabilísticos clásicos. El problema de Simon fue la inspiración directa para que Peter Shor desarrollara su famoso algoritmo de factorización ese mismo año, el resultado que puso a la computación cuántica en el mapa mundial al demostrar que podía romper la criptografía RSA.

Lov Grover, en 1996, demostró una aceleración cuadrática para la búsqueda no estructurada, completando el trío de algoritmos cuánticos fundamentales. Todos estos desarrollos son descendientes intelectuales de la pregunta original de Deutsch: ¿puede un ordenador cuántico ser más rápido que uno clásico?

Implementación en Qiskit y ejecución en IBM Quantum

Deutsch-Jozsa es el ejercicio perfecto para quienes empiezan a programar en Qiskit. Para una función de dos bits, el circuito completo tiene solo cuatro qubits y unas diez puertas, ejecutable en cualquier simulador o procesador real.

La estructura del código es: crear un circuito de N+1 qubits, aplicar X al qubit auxiliar para ponerlo en estado uno, aplicar Hadamard a todos los qubits, implementar el oráculo como una secuencia de puertas CNOT que depende de la función elegida, aplicar Hadamard a los N qubits de entrada, medir, y verificar si el resultado es todo ceros o no.

En hardware real de IBM Quantum, el algoritmo funciona correctamente para N pequeño incluso con el ruido del procesador, ya que el circuito es lo suficientemente corto para que los errores no corrompan el resultado. Para N mayor de cinco o seis, los errores acumulados empiezan a difuminar la distinción entre constante y balanceada, ilustrando perfectamente las limitaciones de la era NISQ.

Preguntas frecuentes

¿Qué es el algoritmo de Deutsch-Jozsa?

El primer algoritmo cuántico con separación exponencial respecto al clásico determinista. Con una consulta determina si una función es constante o balanceada, frente a 2^(N-1)+1 clásicas.

¿Por qué importa si no es práctico?

Demostró que la ventaja cuántica existe y abrió el camino a Shor y Grover. Es el fundamento conceptual de toda la computación cuántica.

¿Cómo funciona?

Superposición para evaluar todas las entradas a la vez, el oráculo codifica los resultados como fases, y la interferencia cuántica final revela si las fases son uniformes (constante) o equilibradas (balanceada).

¿Se puede ejecutar en hardware real?

Sí. Para 2-3 qubits funciona perfectamente en IBM Quantum. Es el primer algoritmo que todo estudiante ejecuta.

¿Cuál es su legado?

Inspiró directamente el problema de Simon, que inspiró el algoritmo de Shor, que demostró que la computación cuántica puede romper la criptografía. Sin Deutsch-Jozsa, la historia habría sido diferente.

Continúa con nuestras guías sobre qué es la IA cuántica, programar con Qiskit y la historia de la computación cuántica.

<\!-- wp:html -->

<\!-- /wp:html -->

De Deutsch-Jozsa a los algoritmos modernos

Si Deutsch-Jozsa es el primer algoritmo, estos son sus descendientes con aplicaciones reales en 2026:

• Algoritmo de Shor — la culminación de la lógica de oráculos en factorización.
• Grover — el otro algoritmo histórico de búsqueda no estructurada.
• Computación cuántica: guía completa.