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]
Planteamiento del problema
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 equilibrado mediante el uso del oráculo.
Motivación
El problema Deutsch-Jozsa está diseñado específicamente para que sea 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 pueden resolverse 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 .
Solución clásica
Para un algoritmo determinista convencional donde n es el número de bits, evaluaciones de será necesario en el peor de los casos. Para probar esoes constante, un poco más de la mitad del conjunto de entradas debe evaluarse y sus salidas deben ser 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 constante evaluaciones de la función es suficiente para producir la respuesta correcta con una alta probabilidad (fallando con probabilidad con ). Sin emabargo,Todavía se requieren evaluaciones si queremos una respuesta que sea siempre correcta. El algoritmo cuántico de Deutsch-Jozsa produce una respuesta que siempre es correcta con una única evaluación de.
Historia
El algoritmo Deutsch-Jozsa generaliza el trabajo anterior (1985) de David Deutsch, que proporcionó una solución para el caso simple en el que .
Específicamente, se nos dio una función booleana cuya entrada es de 1 bit,y preguntó si es constante. [6]
El algoritmo que Deutsch había propuesto originalmente no era, de hecho, determinista. El algoritmo tuvo éxito con una probabilidad de la mitad. En 1992, Deutsch y Jozsa produjeron un algoritmo determinista que se generalizó a una función que tomabits para su entrada. A diferencia del algoritmo de Deutsch, este algoritmo requería dos evaluaciones de funciones en lugar de solo una.
Cleve et al. [2] realizaron más mejoras en el algoritmo Deutsch – Jozsa, lo que resultó en un algoritmo que es determinista y requiere solo una única consulta de. Este algoritmo todavía se conoce como algoritmo Deutsch-Jozsa en honor a las técnicas innovadoras que emplearon. [2]
Algoritmo
Para que funcione el algoritmo Deutsch – Jozsa, la computación oracle de tiene que ser un oráculo cuántico que no decohere . Tampoco debe dejar ninguna copia de tumbado al final de la llamada al oráculo.
El algoritmo comienza con el estado de bits . Es decir, los primeros n bits están cada uno en el estado y la parte final es . Se aplica una transformada de Hadamard a cada bit para obtener el estado
- .
Tenemos la funcion implementado como un oráculo cuántico. El oráculo mapea el estado a , dónde es la adición módulo 2 (ver más abajo para detalles de implementación). La aplicación del oráculo cuántico da
- .
Para cada es 0 o 1. Al probar estas dos posibilidades, vemos que el estado anterior es igual a
- .
En este punto el último qubit puede ignorarse y, por lo tanto, se mantiene a continuación:
- .
Aplicamos una transformada de Hadamard a cada qubit para obtener
dónde es la suma del producto bit a bit (donde es el módulo de adición 2).
Finalmente examinamos la probabilidad de medir ,
que se evalúa a 1 si es constante ( interferencia constructiva ) y 0 siestá equilibrado ( interferencia destructiva ). En otras palabras, la medida final será (es decir, todos ceros) si es constante y producirá algunos otros estados si está equilibrado.
Algoritmo de Deutsch
El algoritmo de Deutsch es un caso especial del algoritmo general de Deutsch – Jozsa. Necesitamos verificar la condición. Es equivalente a comprobar (dónde es módulo de adición 2, que también se puede ver como una puerta XOR cuántica implementada como una puerta NO controlada ), si es cero, entonces es constante, de lo contrario no es constante.
Comenzamos con el estado de dos qubit y aplique una transformada de Hadamard a cada qubit. Esto produce
Se nos da una implementación cuántica de la función que mapas a . Aplicando esta función a nuestro estado actual obtenemos
Ignoramos el último bit y la fase global y, por lo tanto, tenemos el estado
Aplicando una transformación de Hadamard a este estado tenemos
si y solo si medimos y si y solo si medimos . Entonces, con certeza sabemos si es constante o equilibrado.
Ver también
Referencias
- ^ David Deutsch y Richard Jozsa (1992). "Soluciones rápidas de problemas por computación cuántica". Actas de la Royal Society de Londres Una . 439 (1907): 553–558. Código bibliográfico : 1992RSPSA.439..553D . CiteSeerX 10.1.1.655.5997 . doi : 10.1098 / rspa.1992.0167 .
- ^ a b c R. Cleve; A. Ekert; C. Macchiavello; M. Mosca (1998). "Algoritmos cuánticos revisitados". Actas de la Royal Society de Londres Una . 454 (1969): 339–354. arXiv : quant-ph / 9708016 . Código bibliográfico : 1998RSPSA.454..339C . doi : 10.1098 / rspa.1998.0164 .
- ^ Simon, Daniel (noviembre de 1994). "Sobre el poder de la computación cuántica" . 94 Actas del 35º Simposio anual sobre fundamentos de la informática : 116–123.
- ^ "Certeza de la incertidumbre" . Archivado desde el original el 6 de abril de 2011 . Consultado el 13 de febrero de 2011 .[ fuente no confiable? ]
- ^ Johansson, N .; Larsson, JÅ. (2017). "Simulación clásica eficiente de los algoritmos de Deutsch-Jozsa y Simon". Proceso Quantum Inf (2017) . 16 (9): 233. arXiv : 1508.05027 . doi : 10.1007 / s11128-017-1679-7 .
- ^ David Deutsch (1985). "Teoría cuántica, el principio de Church-Turing y la computadora cuántica universal" (PDF) . Actas de la Royal Society de Londres Una . 400 (1818): 97-117. Código Bibliográfico : 1985RSPSA.400 ... 97D . CiteSeerX 10.1.1.41.2382 . doi : 10.1098 / rspa.1985.0070 .[ enlace muerto permanente ]
enlaces externos
- Conferencia de Deutsch sobre el algoritmo Deutsch-Jozsa