Algoritmo de Deutsch – Jozsa

El algoritmo Deutsch-Jozsa es un algoritmo cuántico determinista propuesto por David Deutsch y Richard Jozsa en 1992 con mejoras de Richard Cleve , Artur Ekert , Chiara Macchiavello y Michele Mosca en 1998. ^{[1] [2]} Aunque de poco uso práctico actual, es uno de los primeros ejemplos de un algoritmo cuántico que es exponencialmente más rápido que cualquier posible algoritmo clásico determinista. ^[3]

En el problema Deutsch-Jozsa, se nos da una computadora cuántica de caja negra conocida como oráculo que implementa alguna función . La función toma valores binarios de n dígitos como entrada y produce un 0 o un 1 como salida para cada uno de esos valores. Se nos promete que la función es constante (0 en todas las salidas o 1 en todas las salidas) o balanceada (devuelve 1 para la mitad del dominio de entrada y 0 para la otra mitad). ^[4] La tarea entonces es determinar si es constante o balanceada usando el oráculo.${\ Displaystyle f \ colon \ {0,1 \} ^ {n} \ rightarrow \ {0,1 \}}$${\ Displaystyle f}$

El problema de Deutsch-Jozsa está diseñado específicamente para ser fácil para un algoritmo cuántico y difícil para cualquier algoritmo clásico determinista. La motivación es mostrar un problema de caja negra que puede ser resuelto de manera eficiente por una computadora cuántica sin errores, mientras que una computadora clásica determinista necesitaría una gran cantidad de consultas a la caja negra para resolver el problema. Más formalmente, produce un oráculo relativo al cual EQP , la clase de problemas que se pueden resolver exactamente en tiempo polinomial en una computadora cuántica, y P son diferentes. ^[5]

Dado que el problema es fácil de resolver en una computadora clásica probabilística, no produce una separación de oráculo con BPP , la clase de problemas que se pueden resolver con error acotado en el tiempo polinomial en una computadora clásica probabilística. El problema de Simon es un ejemplo de un problema que produce una separación de oráculo entre BQP y BPP .

Para un algoritmo determinista convencional donde n es el número de bits, se requerirán evaluaciones de en el peor de los casos. Para demostrar que es constante, se debe evaluar un poco más de la mitad del conjunto de entradas y se debe determinar que sus salidas son idénticas (recordando que se garantiza que la función es equilibrada o constante, no en algún punto intermedio). El mejor caso ocurre cuando la función está equilibrada y los dos primeros valores de salida que se seleccionan son diferentes. Para un algoritmo aleatorio convencional , una evaluación constante de la función es suficiente para producir la respuesta correcta con una alta probabilidad (fallando con probabilidad con ). Sin embargo,${\ Displaystyle 2 ^ {n-1} +1}$${\ Displaystyle f}$${\ Displaystyle f}$${\ Displaystyle k}$${\ Displaystyle \ epsilon \ leq 1/2 ^ {k}}$${\ Displaystyle k \ geq 1}$${\ Displaystyle k = 2 ^ {n-1} +1}$Las evaluaciones siguen siendo necesarias si queremos una respuesta siempre correcta. El algoritmo cuántico de Deutsch-Jozsa produce una respuesta que siempre es correcta con una sola evaluación de .${\ Displaystyle f}$

Circuito cuántico del algoritmo Deutsch-Jozsa