Algoritmo de 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 poca utilidad práctica, es uno de los primeros ejemplos de un algoritmo cuántico que es exponencialmente más rápido que cualquier algoritmo clásico determinista posible. ^[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 error, mientras que una computadora clásica determinista necesitaría una cantidad exponencial de consultas a la caja negra para resolver el problema. Más formalmente, produce un oráculo en relación con el cual EQP , la clase de problemas que pueden ser resueltos 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 oracular con BPP , la clase de problemas que se pueden resolver con un 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 oracular 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}\rightarrow \{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 esos valores. Se nos promete que la función es constante (0 en todas las entradas o 1 en todas las entradas) o equilibrada (1 para exactamente la mitad del dominio de entrada y 0 para la otra mitad). ^[1] La tarea entonces es determinar si es constante o equilibrada utilizando el oráculo.${\estilo de visualización f}$

Para un algoritmo determinista convencional donde 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 encontrar que sus salidas son idénticas (porque se garantiza que la función está equilibrada o es constante, no algo intermedio). El mejor caso ocurre cuando la función está equilibrada y los dos primeros valores de salida son diferentes. Para un algoritmo aleatorio convencional , una constante de evaluaciones de la función es suficiente para producir la respuesta correcta con una alta probabilidad (fallando con probabilidad con ). Sin embargo, 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 única evaluación de .${\estilo de visualización n}$$Estilo de visualización 2^{n-1}+1$${\estilo de visualización f}$${\estilo de visualización f}$${\estilo de visualización k}$${\displaystyle \epsilon \leq 1/2^{k}}$${\displaystyle k\geq 1}$$estilo de visualización k=2^{n-1}+1}$${\estilo de visualización f}$

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

El algoritmo, tal como lo había propuesto originalmente Deutsch, no era determinista. El algoritmo tenía éxito con una probabilidad de la mitad. En 1992, Deutsch y Jozsa produjeron un algoritmo determinista que se generalizó a una función que toma bits como entrada. A diferencia del algoritmo de Deutsch, este algoritmo requería dos evaluaciones de la función en lugar de una sola.${\estilo de visualización n}$

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

Para que funcione el algoritmo Deutsch–Jozsa, el oráculo que calcula a partir de debe ser un oráculo cuántico que no descohere . Tampoco debe hacer una copia de , porque eso violaría el teorema de no clonación .${\estilo de visualización f(x)}$${\estilo de visualización x}$ ${\estilo de visualización x}$${\estilo de visualización x}$

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

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

donde se ejecuta sobre todas las cadenas de bits. Hemos implementado la función como un oráculo cuántico. El oráculo asigna su estado de entrada a , donde denota adición módulo 2. Al aplicar el oráculo cuántico se obtiene:${\estilo de visualización x}$${\estilo de visualización n}$${\estilo de visualización f}$${\displaystyle |x\rangle |y\rangle}$${\displaystyle |x\rangle |y\omás f(x)\rangle }$${\displaystyle \oplus}$

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

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

${\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 se puede ignorar el último qubit y queda lo siguiente:${\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}$

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

A continuación, haremos que el qubit pase por una puerta Hadamard.

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

( es la suma del producto bit a bit, donde es la adición módulo 2) sobre el primer registro para obtener${\displaystyle j\cdot k=j_{0}k_{0}\oplus j_{1}k_{1}\oplus \cdots \oplus j_{n-1}k_{n-1}}$${\displaystyle \oplus }$

${\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}(-1)^{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 }$

De esto, podemos ver que la probabilidad de que se mida un estado es${\displaystyle k}$

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

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

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

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

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

Comenzamos con el estado de dos cúbits y aplicamos una puerta de Hadamard a cada cúbit. Esto produce${\displaystyle |0\rangle |1\rangle }$

${\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).}$

Se nos da una implementación cuántica de la función que corresponde a . Al aplicar esta función a nuestro estado actual, obtenemos${\displaystyle f}$${\displaystyle |x\rangle |y\rangle }$${\displaystyle |x\rangle |f(x)\oplus y\rangle }$

${\displaystyle {\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 ))}$

${\displaystyle ={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))}$

${\displaystyle =(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle ).}$

Ignoramos el último 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 {\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )}$

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

${\displaystyle f(0)\oplus f(1)=0}$si y solo si medimos y si y solo si medimos . Así que con certeza sabemos si es constante o está en equilibrio.${\displaystyle |0\rangle }$${\displaystyle f(0)\oplus f(1)=1}$${\displaystyle |1\rangle }$${\displaystyle f(x)}$

• Algoritmo de Bernstein-Vazirani

• Conferencia de Deutsch sobre el algoritmo Deutsch-Jozsa