En computación cuántica, el algoritmo de Deutsch-Jozsa es un algoritmo cuántico, propuesto por David Deutsch y Richard Jozsa en 1992.[1] Fue uno de los primeros algoritmos diseñados para ejecutar sobre un computador cuántico y que tiene el potencial de ser más eficiente que los algoritmos clásicos al aprovechar el paralelismo inherente de los estados de superposición cuánticos.
En el problema de Deutsch-Jozsa, se tiene una función (que puede considerarse como un oráculo o caja negra) f(x1, x2,..., xn) que toma n bits de entrada x1, x2,..., xn y devuelve un valor binario f(x1, x2,..., xn)= 0 ó 1. El objetivo es determinar si la función es constante (0 en todas las entradas o 1 en todas las entradas) o balanceada (devuelve 1 para la mitad de las entradas y 0 para la otra mitad). El problema es determinar cómo es la función (constante o balanceada) aplicando entradas a la caja negra y observando su salida. A modo de ejemplo, considérese la función , es decir, la función que devuelve el resto de dividir la entrada entre dos. Esta función devuelve 1 si el argumento es impar y 0 si el argumento es par, por lo que se trata de una función balanceada. La función del algoritmo sería la de llegar a esta misma conclusión con el menor número posible de iteraciones, algo que en el caso clásico requeriría la evaluación repetida de la función hasta alcanzar dos resultados diferentes, y por tanto el número de iteraciones dependería del orden en el que se escogieran las variables de entrada.
El algoritmo de Deutsch-Jozsa generaliza el algoritmo de Deutsch (1985),[1] que resuelve el problema planteado para el caso n=1. En el año 1992 Deutsch y Jozsa encontraron la solución al problema para un número arbitrario de bits de entrada.
El de Deutsch-Jozsa es un ejemplo claro de problema que resulta sencillo de resolver para un ordenador cuántico pero muy complejo para un ordenador clásico,[2] que en el peor de los casos necesita iteraciones para determinar si la función es constante o balanceada.
Es importante remarcar que, pese a la importancia de encontrar un problema donde un ordenador cuántico arroja un mejor resultado que uno clásico, no se han encontrado hasta la fecha aplicaciones prácticas reales de este algoritmo.[cita requerida]
Esta es la versión del algoritmo para una función f(x) de una sola entrada. Se utilizan dos cúbits auxiliares en los cálculos. El algoritmo se ilustra en la figura de la derecha.
El bloque H es una puerta Hadamard cuya operación es la siguiente:
El bloque Uf denota el oráculo y realiza la operación siguiente:
Además,
La entrada al circuito es: , que atraviesa dos puestas Hardamard (véase la figura) obteniéndose . Esto atraviesa el bloque Uf obteniéndose
Esta expresión puede escribirse:
Al atravesar la última puerta de Hadamard se obtiene:
Puesto que si y si , podemos escribir
Este es el resultado final: midiendo el primer qúbit de la ecuación se obtiene . Si resulta el valor 0, entonces la función f(x) es constante, mientras que si resulta 1, la función es balanceada.
Esta es la versión general del algoritmo para funciones f(x) de n entradas.
En este caso, la entrada al circuito es:
A continuación de las puertas Hadamard se obtiene:
A la salida del bloque Uf se tiene:
La última puerta Hadamard produce la siguiente salida
Y por último, realizando la medición, se obtiene z. En el caso en que la función f(x) sea balanceda, las contribuciones para se cancelan y la medida de z debe dar una combinación distinta. Por el contrario, si f(x) es constante se obtiene en la medida, pues el resto de las contribuciones se cancelan en este caso. Por consiguiente, comprobando si z es cero o distinto de cero se sabe que la función es, respectivamente, constante o balanceada.
A continuación, se muestra un ejemplo sencillo de cómo se puede implementar el algoritmo Deutsch–Jozsa en Python usando Qiskit, un entorno de desarrollo de software de computación cuántica de código abierto de IBM. Recorreremos cada parte del código paso a paso para mostrar cómo se traduce la teoría en un circuito cuántico funcional.
from qiskit import QuantumCircuit, transpile
from qiskit_aer import Aer
def create_constant_oracle(n_qubits, output):
"""
Crea un oráculo 'constante'.
Si `output` es 0, el oráculo siempre devuelve 0.
Si `output` es 1, el oráculo siempre devuelve 1.
Parámetros:
n_qubits (int): El número de qubits de entrada.
output (int): El valor de salida constante de la función (0 o 1).
Devuelve:
QuantumCircuit: Un circuito cuántico que implementa el oráculo constante.
"""
oracle = QuantumCircuit(n_qubits + 1)
# Si el oráculo debe devolver siempre 1, giramos ("flip") el qubit de salida
# usando una compuerta X (similar a una compuerta NOT en un qubit).
if output == 1:
oracle.x(n_qubits)
return oracle
def create_balanced_oracle(n_qubits):
"""
Crea un oráculo 'balanceado'.
La mitad de los patrones de bits de entrada generan 0,
y la otra mitad generan 1.
Para demostración, esta función implementa una función balanceada sencilla
usando compuertas X en el primer qubit de la entrada como control,
invirtiendo el qubit de salida para la mitad de las entradas.
Parámetros:
n_qubits (int): El número de qubits de entrada.
Devuelve:
QuantumCircuit: Un circuito cuántico que implementa el oráculo balanceado.
"""
oracle = QuantumCircuit(n_qubits + 1)
# Usaremos un patrón sencillo: si el primer qubit es 1, volteamos la salida.
# Esto significa que para la mitad de las posibles entradas, la salida cambia.
oracle.cx(0, n_qubits)
return oracle
def deutsch_jozsa_circuit(oracle, n_qubits):
"""
Construye el circuito completo de Deutsch–Jozsa.
El circuito realiza los siguientes pasos:
1. Inicia todos los qubits de 'entrada' en |0>.
2. Inicia el qubit de 'salida' en |1>.
3. Aplica compuertas de Hadamard a todos los qubits.
4. Aplica el oráculo.
5. Aplica de nuevo compuertas de Hadamard a los qubits de entrada.
6. Mide los qubits de entrada.
Parámetros:
oracle (QuantumCircuit): El circuito que codifica la función 'misteriosa' f(x).
n_qubits (int): El número de qubits de entrada.
Devuelve:
QuantumCircuit: El circuito completo de Deutsch–Jozsa listo para ejecutarse.
"""
# Total de n_qubits para la entrada, más 1 para el qubit de salida
dj_circuit = QuantumCircuit(n_qubits + 1, n_qubits)
# 1. Los qubits de entrada ya están en |0>.
# 2. Ponemos el qubit de salida en |1>. Para ello usamos una compuerta X.
dj_circuit.x(n_qubits)
# 3. Aplica compuertas de Hadamard a todos los qubits (entrada + salida).
for qubit in range(n_qubits + 1):
dj_circuit.h(qubit)
# 4. Anexa el circuito del oráculo.
dj_circuit.compose(oracle, inplace=True)
# 5. Aplica compuertas de Hadamard nuevamente, solo a los qubits de entrada.
for qubit in range(n_qubits):
dj_circuit.h(qubit)
# 6. Finalmente, mide los qubits de entrada.
for qubit in range(n_qubits):
dj_circuit.measure(qubit, qubit)
return dj_circuit
def run_deutsch_jozsa_test(n_qubits, oracle_type='constant', constant_output=0):
"""
Construye y ejecuta el circuito de Deutsch–Jozsa para un oráculo constante
o uno balanceado, luego imprime los resultados.
Parámetros:
n_qubits (int): Número de qubits de entrada.
oracle_type (str): Especifica el tipo de oráculo, 'constant' o 'balanced'.
constant_output (int): Si el oráculo es constante, determina si devuelve 0 o 1.
"""
# Crea el oráculo seleccionado
if oracle_type == 'constant':
oracle = create_constant_oracle(n_qubits, constant_output)
print(f"Using a CONSTANT oracle that always returns {constant_output}")
else:
oracle = create_balanced_oracle(n_qubits)
print("Using a BALANCED oracle.")
# Crea el circuito de Deutsch–Jozsa
dj_circ = deutsch_jozsa_circuit(oracle, n_qubits)
# Dibuja el circuito como referencia visual
display(dj_circ.draw())
# Usa el backend del simulador para ejecutar el circuito
simulator = Aer.get_backend('aer_simulator')
transpiled_circ = transpile(dj_circ, simulator)
job = simulator.run(transpiled_circ, shots=1)
result = job.result()
counts = result.get_counts(transpiled_circ)
print("Measurement outcomes:", counts)
# Interpreta la medición
# Si todos los bits medidos son 0 (por ejemplo, '000' para 3 qubits),
# entonces la función es constante. De lo contrario, es balanceada.
measured_result = max(counts, key=counts.get) # The most likely outcome
if measured_result == '0' * n_qubits:
print("Conclusion: f(x) is CONSTANT.")
else:
print("Conclusion: f(x) is BALANCED.")
# Test with 3 qubits
run_deutsch_jozsa_test(n_qubits=3, oracle_type='constant', constant_output=0)
print("\n" + "="*50 + "\n")
run_deutsch_jozsa_test(n_qubits=3, oracle_type='balanced')
Using a CONSTANT oracle that always returns 0 ┌───┐┌───┐┌─┐ q_0: ┤ H ├┤ H ├┤M├────── ├───┤├───┤└╥┘┌─┐ q_1: ┤ H ├┤ H ├─╫─┤M├─── ├───┤├───┤ ║ └╥┘┌─┐ q_2: ┤ H ├┤ H ├─╫──╫─┤M├ ├───┤├───┤ ║ ║ └╥┘ q_3: ┤ X ├┤ H ├─╫──╫──╫─ └───┘└───┘ ║ ║ ║ c: 3/═══════════╩══╩══╩═ 0 1 2 Measurement outcomes: {'000': 1} Conclusion: f(x) is CONSTANT. ================================================== Using a BALANCED oracle. ┌───┐ ┌───┐ ┌─┐ q_0: ┤ H ├───────■──┤ H ├───┤M├ ├───┤┌───┐ │ └┬─┬┘ └╥┘ q_1: ┤ H ├┤ H ├──┼───┤M├─────╫─ ├───┤├───┤ │ └╥┘ ┌─┐ ║ q_2: ┤ H ├┤ H ├──┼────╫──┤M├─╫─ ├───┤├───┤┌─┴─┐ ║ └╥┘ ║ q_3: ┤ X ├┤ H ├┤ X ├──╫───╫──╫─ └───┘└───┘└───┘ ║ ║ ║ c: 3/═════════════════╩═══╩══╩═ 1 2 0 Measurement outcomes: {'001': 1} Conclusion: f(x) is BALANCED.
Utilizamos los elementos principales de Qiskit:
QuantumCircuit
para construir circuitos cuánticosAer
, transpile
y run
para ejecutar nuestro circuito en un simulador clásicoCNOT
(cx
) para voltear el qubit de salida cuando el primer qubit de entrada es 1.dj_circuit.h(qubit)
) a todos los qubits. La compuerta Hadamard distribuye las amplitudes entre y , creando superposiciones.Ejecutamos el circuito usando el aer_simulator
integrado de Aer. Debido a que el algoritmo Deutsch–Jozsa solo necesita una ejecución (un conjunto de disparos) para distinguir entre constante y balanceada con un 100% de certeza, ejecutar múltiples disparos siempre dará el mismo resultado.
De forma clásica, se podría tener que “llamar” a la función (f) (nuestra “caja negra” misteriosa) muchas veces — potencialmente hasta veces— para estar absolutamente seguros de si es constante o balanceada. Sin embargo, la versión cuántica de este problema se puede resolver con una sola llamada al oráculo, más algunas compuertas cuánticas adicionales. Aunque Deutsch–Jozsa se considera más un “ejemplo didáctico” que una aplicación práctica, demuestra una de las ideas clave de los algoritmos cuánticos: aprovechar la superposición y la interferencia para reducir drásticamente el número de llamadas requeridas a la función.