Algoritmo de Deutsch-Jozsa

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 problema es determinar cómo es la función (constante o balanceada) aplicando entradas a la caja negra y observando su salida., es decir, la función que devuelve el resto de dividir la entrada entre dos.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.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.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:, que atraviesa dos puestas Hardamard (véase la figura) obteniéndoseAl atravesar la última puerta de Hadamard se obtiene:Este es el resultado final: midiendo el primer qúbit de la ecuación se obtieneEsta es la versión general del algoritmo para funciones f(x) de n entradas.A continuación de las puertas Hadamard se obtiene:A la salida del bloque Uf se tiene:La última puerta Hadamard produce la siguiente salidaY por último, realizando la medición, se obtiene z. En el caso en que la función f(x) sea balanceda, las contribuciones parase cancelan y la medida de z debe dar una combinación distinta.Por el contrario, si f(x) es constante se obtieneen 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.Recorreremos cada parte del código paso a paso para mostrar cómo se traduce la teoría en un circuito cuántico funcional.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 hastaveces— 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.