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 realizadas por Richard Cleve , Artur Ekert , Chiara Macchiavello y Michele Mosca en 1998. ^{[ 1 ] [ 2 ]} Aunque de poca utilidad práctica, es uno de los primeros ejemplos de un algoritmo cuántico exponencialmente más rápido que cualquier posible algoritmo clásico determinista. ^{[ 3 ]}

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 puede ser resuelto eficientemente por una computadora cuántica 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. Formalmente, produce un oráculo con respecto al cual EQP , la clase de problemas que pueden resolverse exactamente en tiempo polinomial en una computadora cuántica, y P son diferentes. ^{[ 4 ]}

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 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 .

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

$${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$$

La función toma valores binarios de n bits como entrada y produce un 0 o un 1 como salida para cada uno de dichos valores. Se nos promete que la función es constante (0 en todas las entradas o 1 en todas las entradas) o balanceada (1 para exactamente la mitad del dominio de entrada y 0 para la otra mitad). ^{[ 1 ]} La tarea entonces es determinar si${\displaystyle f}$es constante o equilibrado mediante el uso del oráculo.

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

El algoritmo Deutsch-Jozsa generaliza el trabajo anterior (1985) de David Deutsch, que proporcionó una solución para el caso simple donde${\displaystyle n=1}$. Específicamente, averiguar si una función booleana dada cuya entrada es de un bit,${\displaystyle f:\{0,1\}\to \{0,1\}}$, es constante. ^{[ 5 ]}

El algoritmo, tal como Deutsch lo propuso originalmente, no era determinista. El algoritmo tenía éxito con una probabilidad de un medio. En 1992, Deutsch y Jozsa produjeron un algoritmo determinista que se generalizó a una función que toma${\displaystyle n}$bits para su entrada. A diferencia del algoritmo de Deutsch, este algoritmo requería dos evaluaciones de función en lugar de solo una.

Cleve et al. realizaron mejoras adicionales al algoritmo Deutsch-Jozsa, ^{[ 2 ]} dando como resultado un algoritmo que es determinista y requiere solo una única consulta de${\displaystyle f}$Este algoritmo aún se conoce como algoritmo de Deutsch-Jozsa en honor a las técnicas innovadoras que emplearon. ^{[ 2 ]}

Para que el algoritmo Deutsch-Jozsa funcione, se requiere la computación de oráculo.${\displaystyle f(x)}$de${\displaystyle x}$Debe ser un oráculo cuántico que no se decohere.${\displaystyle x}$. En su cálculo, no puede hacer una copia de${\displaystyle x}$, porque eso violaría el teorema de no clonación . El punto de vista del algoritmo de Deutsch-Jozsa de${\displaystyle f}$Que un oráculo actúe como tal significa que no importa lo que haga, ya que simplemente tiene que realizar la transformación prometida.

El algoritmo comienza con el${\displaystyle n+1}$estado de bits${\displaystyle |0\rangle ^{\otimes n}|1\rangle }$. Es decir, los primeros n bits están cada uno en el estado${\displaystyle |0\rangle }$y la parte final es${\displaystyle |1\rangle }$Se aplica una puerta Hadamard a cada bit para obtener el estado.

$${\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle ),}$$

dónde${\displaystyle x}$corre por todas partes${\displaystyle n}$cadenas de bits, cada una de las cuales puede estar representada por un número de${\displaystyle 0}$a${\displaystyle 2^{n}-1}$Tenemos la función${\displaystyle f}$implementado como un oráculo cuántico. El oráculo mapea su estado de entrada.${\displaystyle |x\rangle |y\rangle }$a${\displaystyle |x\rangle |y\oplus f(x)\rangle }$, dónde${\displaystyle \oplus }$denota la suma módulo 2. Aplicando el oráculo cuántico se obtiene:

$${\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\oplus f(x)\rangle -|1\oplus f(x)\rangle ).}$$

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

$${\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle ).}$$

En este punto el último cúbit${\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}$puede ignorarse y queda lo siguiente:

$${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle .}$$

A continuación, haremos que cada cúbit pase por una puerta de Hadamard . La transformación total sobre todos${\displaystyle n}$Los cúbits se pueden expresar con la siguiente identidad:

$${\displaystyle H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle }$$

(${\displaystyle j\cdot k=j_{0}k_{0}\oplus j_{1}k_{1}\oplus \cdots \oplus j_{n-1}k_{n-1}}$es la suma del producto bit a bit). Esto da como resultado

$${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{y=0}^{2^{n}-1}{\left(-1\right)}^{x\cdot y}|y\rangle \right]=\sum _{y=0}^{2^{n}-1}\left[{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle .}$$

A partir de esto, podemos ver que la probabilidad de un estado${\displaystyle k}$ser medido es

$${\displaystyle \left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}{\left(-1\right)}^{f(x)}{\left(-1\right)}^{x\cdot k}\right|^{2}}$$

La probabilidad de medir${\displaystyle k=0}$, correspondiente a${\displaystyle |0\rangle ^{\otimes n}}$, es

$${\displaystyle {\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}}$$

que se evalúa a 1 si${\displaystyle f(x)}$es constante ( interferencia constructiva ) y 0 si${\displaystyle f(x)}$está equilibrado ( interferencia destructiva ). En otras palabras, la medición final será${\displaystyle |0\rangle ^{\otimes n}}$(todo ceros) si y solo si${\displaystyle f(x)}$es constante y producirá algún otro estado si${\displaystyle f(x)}$está equilibrado.

El algoritmo de Deutsch es un caso especial del algoritmo general de Deutsch-Jozsa donde n = 1, de modo que${\displaystyle f\colon \{0,1\}\rightarrow \{0,1\}}$Necesitamos comprobar la condición${\displaystyle f(0)=f(1)}$Es equivalente a comprobar${\displaystyle f(0)\oplus f(1)}$(dónde${\displaystyle \oplus }$es la suma módulo 2, que también puede verse como una puerta XOR cuántica implementada como una puerta NOT controlada ), si es cero, entonces${\displaystyle f}$es constante, de lo contrario${\displaystyle f}$no es constante.

Comenzamos con el estado de dos cúbits${\displaystyle |0\rangle |1\rangle }$y aplicar una puerta Hadamard a cada cúbit. Esto produce $${\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).}$$

Se nos proporciona una implementación cuántica de la función.${\displaystyle f}$que mapas${\displaystyle |x\rangle |y\rangle }$a${\displaystyle |x\rangle |f(x)\oplus y\rangle }$Aplicando esta función a nuestro estado actual obtenemos $${\displaystyle {\begin{aligned}&{\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))\\&={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))\\&=(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle ).\end{aligned}}}$$

Ignoramos el segundo cúbit y la fase global y por lo tanto tenemos el estado $${\displaystyle {\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ).}$$

Aplicando una puerta Hadamard a este estado tenemos $${\displaystyle {\begin{aligned}&{\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )\\&={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).\end{aligned}}}$$

${\displaystyle f(0)\oplus f(1)=0}$si y solo si medimos${\displaystyle |0\rangle }$y${\displaystyle f(0)\oplus f(1)=1}$si y solo si medimos${\displaystyle |1\rangle }$. Entonces, con certeza sabemos si${\displaystyle f(x)}$es constante o equilibrado.

El circuito cuántico que se muestra aquí es un ejemplo sencillo de cómo se puede implementar el algoritmo de Deutsch-Jozsa en Python utilizando Qiskit , un marco de desarrollo de software de computación cuántica de código abierto de IBM.

• Algoritmo de Bernstein-Vazirani

• Conferencia de Deutsch sobre el algoritmo de Deutsch-Jozsa