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. Aunque de poca importancia Para su uso práctico, 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.

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. Es un problema de caja negra que una computadora cuántica puede resolver eficientemente sin errores, mientras que una computadora clásica determinista necesitaría un número exponencial de consultas a la caja negra para resolver el problema. Más formalmente, produce un oráculo respecto del cual EQP, la clase de problemas que se puede resolver exactamente en tiempo polinomial en una computadora cuántica, y P son diferentes.

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

Declaración del problema

En el problema de Deutsch-Jozsa, se nos proporciona una computadora cuántica de caja negra conocida como oráculo que implementa alguna función:

f:: {}0,1}n→ → {}0,1}{displaystyle fcolon {0,1}n}rightarrow {0,1}

La función toma valores binarios n-bit como entrada y produce un 0 o un 1 como salida para cada valor. Se nos promete que la función es constante (0 en todas las entradas o 1 en todas las entradas) o equilibrado (1 para exactamente la mitad del dominio de entrada y 0 para la otra mitad). La tarea entonces es determinar si f{displaystyle f} es constante o equilibrada usando el oráculo.

Solución clásica

Para un algoritmo determinista convencional donde n{displaystyle n} es el número de bits, 2n− − 1+1{displaystyle 2^{n-1}+1} evaluaciones de f{displaystyle f} será necesario en el peor caso. Para demostrarlo f{displaystyle f} es constante, apenas más de la mitad del conjunto de entradas debe ser evaluado y sus salidas se encuentran idénticas (porque la función está garantizada a ser equilibrada o constante, no en algún lugar entre). El mejor caso ocurre cuando la función es equilibrada y los dos primeros valores de salida son diferentes. Para un algoritmo convencional aleatorizado, una constante k{displaystyle k} las evaluaciones de la función bastan para producir la respuesta correcta con una alta probabilidad (con probabilidad ε ε ≤ ≤ 1/2k{displaystyle epsilon leq 1/2^{k} con k≥ ≥ 1{displaystyle kgeq 1}). Sin embargo, k=2n− − 1+1{displaystyle k=2^{n-1}+1} las evaluaciones todavía son necesarias si queremos una respuesta que no tiene posibilidad de error. El algoritmo cuántico Deutsch-Jozsa produce una respuesta siempre correcta con una sola evaluación de f{displaystyle f}.

Historia

El algoritmo Deutsch–Jozsa generaliza antes (1985) trabajo de David Deutsch, que proporcionó una solución para el caso simple donde n=1{displaystyle n=1}.
Específicamente, dada una función booleana cuya entrada es un poco, f:{}0,1}→ → {}0,1}{displaystyle f:{0,1}rightarrow {0,1}¿Es constante?

El algoritmo, como Deutsch lo había propuesto originalmente, no era determinista. El algoritmo tuvo éxito con una probabilidad de una mitad. En 1992, Deutsch y Jozsa produjeron un algoritmo determinista que se generalizó a una función que toma n{displaystyle n} bits para su entrada. A diferencia del algoritmo de Deutsch, este algoritmo requería dos evaluaciones de funciones en lugar de sólo una.

Otras mejoras en el algoritmo de Deutsch–Jozsa fueron hechas por Cleve et al., resultando en un algoritmo que es determinista y requiere sólo una sola consulta de f{displaystyle f}. Este algoritmo todavía se conoce como algoritmo Deutsch–Jozsa en honor de las técnicas innovadoras que emplearon.

Algoritmo

Para el algoritmo de Deutsch–Jozsa para trabajar, la computación del oráculo f()x){displaystyle f(x)} desde x{displaystyle x} debe ser un oráculo cuántico que no decohere x{displaystyle x}. Tampoco debe hacer una copia x{displaystyle x}Porque eso violaría el teorema de no clonar.

El algoritmo comienza con el n+1{displaystyle n+1} estado Silencio0.. ⊗ ⊗ nSilencio1.. {displaystyle TENIDO0rangle. Es decir, las primeras n bits son cada uno en el estado Silencio0.. {displaystyle Silencioso y la parte final es Silencio1.. {displaystyle ← }. Una transformación Hadamard se aplica a cada bit para obtener el estado

12n+1.. x=02n− − 1Silenciox.. ()Silencio0.. − − Silencio1.. ){displaystyle {frac {1} {sqrt {2^{n+1}}sum}} {f} {fn}} {fn}}}} {fn}}} {fn}}}} {fn}}}} {fn}}}}} {fn}}}}}}}} {f}}}}}}}}}}}}}}}}}}}}}}}}} { - ¿Por qué?,

Donde x{displaystyle x} sobre todo n{displaystyle n}- cuerdas bit. Tenemos la función f{displaystyle f} implementado como un oráculo cuántico. El oráculo mapea su estado de entrada Silenciox.. SilencioSí... {displaystyle.. a Silenciox.. SilencioSí.⊕ ⊕ f()x).. {displaystyle tenciónxrangle Silenciosooplus f(x)rangle }, donde ⊕ ⊕ {displaystyle oplus } denotes addition modulo 2. Aplicar el oráculo cuántico da;

12n+1.. x=02n− − 1Silenciox.. ()Silencio0⊕ ⊕ f()x).. − − Silencio1⊕ ⊕ f()x).. ){displaystyle {frac {1} {sqrt {2^{n+1}}}sum _{x=0}^{2^{n}-1}rangle (present0oplus f(x)rangle - perpetua1oplus f(x)rangle)}}.

Para cada uno x,f()x){displaystyle x,f(x)} es 0 o 1. Probando estas dos posibilidades, vemos que el estado anterior es igual a

12n+1.. x=02n− − 1()− − 1)f()x)Silenciox.. ()Silencio0.. − − Silencio1.. ){displaystyle {frac {1} {sqrt {2^{n+1}}sum _{x=0}^{2^{n}-1}(-1)^{f(x)} sobrevivirxrangle.

En este punto el último codo Silencio0.. − − Silencio1.. 2{displaystyle {frac {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}} {f}}} {fnK}}}}}} puede ser ignorado y los siguientes restos:

12n.. x=02n− − 1()− − 1)f()x)Silenciox.. [displaystyle {frac {1} {sqrt {2^{n}}sum _{x=0}^{2^{n}-1}(-1)^{f(x)}.

A continuación, aplicaremos la transformada de Hadamard.

H⊗ ⊗ nSilenciok.. =12n.. j=02n− − 1()− − 1)k⋅ ⋅ jSilencioj.. {displaystyle H^{otimes n}}sum _{j=0}{2^{n} {1} {fn}}sum _{j=0}}{2^{n}-1} {kcdot j}

()j⋅ ⋅ k=j0k0⊕ ⊕ j1k1⊕ ⊕ ⋯ ⋯ ⊕ ⊕ jn− − 1kn− − 1{displaystyle jcdot k=j_{0}k_{0}oplus j_{1}k_{1}oplus cdots oplus J_{n-1}k_{n-1} es la suma del producto bitwise, donde ⊕ ⊕ {displaystyle oplus } modulo adicional 2) en el primer registro para obtener

12n.. x=02n− − 1()− − 1)f()x)[12n.. Sí.=02n− − 1()− − 1)x⋅ ⋅ Sí.SilencioSí... ]=.. Sí.=02n− − 1[12n.. x=02n− − 1()− − 1)f()x)()− − 1)x⋅ ⋅ Sí.]SilencioSí... {displaystyle {frac {1}{sqrt {2}}}sum}} {fn}} {fn}}} {fn}}} {fn}}} {fn}}}}}} {fn}}} {fn}}}}} {fn}}}}}} {fn}}}}}}}}}}}}}}}}}}}}}}} {f}}} {f}}}} {f}}}}}}}}}}}}}}}}}}}}} {f}}}}}}}}}}}}}} {f}}}}}} {f}}}}} {f}}}}} {f}}}}} {f}}}}}}}} {f}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} ¿Por qué? ################################################################################################################################################################################################################################################################ ¿Por qué?

De esto podemos ver que la probabilidad de un estado k{displaystyle k} que se mide

Silencio12n.. x=02n− − 1()− − 1)f()x)()− − 1)x⋅ ⋅ kSilencio2{displaystyle left WordPress{1}{2^{n}}sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{xcdot k}right^{2}}} {f}}} {f}}}} {f}}{2}}}}}}}} {f}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {

La probabilidad de medición k=0{displaystyle k=0}, correspondiente a Silencio0.. ⊗ ⊗ n{displaystyle Silencio0rangle ^{otimes No., es

Silencio12n.. x=02n− − 1()− − 1)f()x)Silencio2{displaystyle {bigg Н}{2}}sum _{x=0}{2^{n}-1}(-1)^{f(x)}{bigg

que evalúa a 1 si f()x){displaystyle f(x)} es constante (intromisión constructiva) y 0 si f()x){displaystyle f(x)} es equilibrado (intromisión destructiva). En otras palabras, la medición final será Silencio0.. ⊗ ⊗ n{displaystyle Silencio0rangle ^{otimes No. (todos ceros) si y sólo si f()x){displaystyle f(x)} es constante y producirá algún otro estado si f()x){displaystyle f(x)} está equilibrado.

Algoritmo de Deutsch

El algoritmo de Deutsch es un caso especial del algoritmo general Deutsch–Jozsa donde n = 1 en f:: {}0,1}n→ → {}0,1}{displaystyle fcolon {0,1}n}rightarrow {0,1}. Tenemos que comprobar la condición f()0)=f()1){displaystyle f(0)=f(1)}. Es equivalente al cheque f()0)⊕ ⊕ f()1){displaystyle f(0)oplus f(1)} (donde) ⊕ ⊕ {displaystyle oplus } es el modulo de adición 2, que también se puede ver como una puerta XOR cuántica implementada como una puerta NO Controlada), si cero, entonces f{displaystyle f} es constante, de lo contrario f{displaystyle f} no es constante.

Comenzamos con el estado de dos codos Silencio0.. Silencio1.. {displaystyle ← } y aplicar una transformación Hadamard a cada cuarto. Este rendimiento

12()Silencio0.. +Silencio1.. )()Silencio0.. − − Silencio1.. ).{displaystyle {frac {1}{2} {rangle + endure1rangle)(Sobrevivir0rangle - sobrevivir1rangle). }

Se nos da una implementación cuántica de la función f{displaystyle f} que mapas Silenciox.. SilencioSí... {displaystyle.. a Silenciox.. Silenciof()x)⊕ ⊕ Sí... {displaystyle tenciónxrangle. Aplicando esta función a nuestro estado actual obtenemos

12()Silencio0.. ()Silenciof()0)⊕ ⊕ 0.. − − Silenciof()0)⊕ ⊕ 1.. )+Silencio1.. ()Silenciof()1)⊕ ⊕ 0.. − − Silenciof()1)⊕ ⊕ 1.. )){displaystyle {frac {1}{2} {rangle (rest0(0)oplus 0rangle - habitf(0)oplus 1rangle)+Sobrevivir1rangle (Principio 0oplus 0rangle - perpetuaf(1)oplus 1rangle)}}}

=12()()− − 1)f()0)Silencio0.. ()Silencio0.. − − Silencio1.. )+()− − 1)f()1)Silencio1.. ()Silencio0.. − − Silencio1.. )){displaystyle ={frac {1}{2}(-1)^{f(0)} sobrevivir0rangle (pretensión0rangle - perpetua1rangle)+(-1)^{f(1)} sobrevivir1rangle (pres0rangle - perpetua1rangle)}}

=()− − 1)f()0)12()Silencio0.. +()− − 1)f()0)⊕ ⊕ f()1)Silencio1.. )()Silencio0.. − − Silencio1.. ).{displaystyle =(-1)^{f(0)}{frac {1}{2}left(tener0rangle +(-1)^{f(0)oplus f(1)}Sobrevivir1rangle right)(Prince0rangle - perpetua1rangle). }

Ignoramos el último bit y la fase global y por lo tanto tenemos el estado

12()Silencio0.. +()− − 1)f()0)⊕ ⊕ f()1)Silencio1.. ).{displaystyle {frac {1}{sqrt {2}} {rangle +(-1)^{f(0)oplus f(1)}Sobrevivir1rangle). }

Aplicando una transformada de Hadamard a este estado tenemos

12()Silencio0.. +Silencio1.. +()− − 1)f()0)⊕ ⊕ f()1)Silencio0.. − − ()− − 1)f()0)⊕ ⊕ f()1)Silencio1.. ){displaystyle {frac {1}{2}} {rangle +(-1)^{f(0)oplus f(1)}Sobrevivir0rangle -(-1)^{f(0)oplus f(1)}

=12()()1+()− − 1)f()0)⊕ ⊕ f()1))Silencio0.. +()1− − ()− − 1)f()0)⊕ ⊕ f()1))Silencio1.. ).{displaystyle ={frac {1}{2}}(1+(-1)^{f(0)oplus f(1)} eterna0rangle +(1-(-1)^{f(0)oplus f(1)}) perpetua1rangle). }

f()0)⊕ ⊕ f()1)=0{displaystyle f(0)oplus f(1)=0} si y sólo si mide Silencio0.. {displaystyle Silencioso y f()0)⊕ ⊕ f()1)=1{displaystyle f(0)oplus f(1)=1} si y sólo si mide Silencio1.. {displaystyle ← }. Así que con certeza sabemos si f()x){displaystyle f(x)} es constante o equilibrada.