Algoritmo de Deutsch-Jozsa

El algoritmo de Deutsch-Jozsa, publicado en 1992, fue el primer algoritmo cuántico en demostrar una aceleración exponencial frente a cualquier algoritmo clásico posible, aunque solo para un problema construido deliberadamente. Dada una función oculta que se garantiza que es o bien constante (devuelve la misma salida para cada entrada) o bien equilibrada (devuelve 0 para exactamente la mitad de todas las entradas y 1 para la otra mitad), un algoritmo clásico necesita hasta 2^(n-1) + 1 consultas en el peor caso para determinar cuál es, mientras que el algoritmo de Deutsch-Jozsa determina la respuesta con una sola consulta poniendo el registro de entrada en superposición, aplicando la función como un oráculo cuántico y usando interferencia para que solo las funciones constantes o solo las equilibradas produzcan un resultado de medición específico. El algoritmo no tiene aplicación práctica conocida. Su importancia es histórica y pedagógica: demostró el mecanismo central, consultas a un oráculo más interferencia, sobre el que se construyen después algoritmos genuinamente útiles como los de Grover y Shor, y suele enseñarse junto con los algoritmos relacionados de Bernstein-Vazirani y Simon como introducción estándar a la complejidad de consulta cuántica antes de pasar a la búsqueda de Grover.