Algoritmo de Jozsa

Algoritmo cuántico determinista

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 .

Planteamiento del problema

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

Solución clásica

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 . ${\displaystyle n}$ ${\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}$ ${\displaystyle f}$

Historia

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] ${\displaystyle 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. ${\displaystyle 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] ${\displaystyle f}$

Algoritmo

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 . ${\displaystyle f(x)}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$

Circuito cuántico del algoritmo Deutsch-Jozsa

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 ${\displaystyle 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: ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle |x\rangle |y\rangle }$ ${\displaystyle |x\rangle |y\oplus f(x)\rangle }$ ${\displaystyle \oplus }$

${\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 uno es 0 o 1. Al probar estas dos posibilidades, vemos que el estado anterior es igual a ${\displaystyle 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)}$

Algoritmo de Deutsch

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)}$

Véase también

• Algoritmo de Bernstein-Vazirani

Referencias

1. David Deutsch y Richard Jozsa (1992). "Soluciones rápidas de problemas mediante computación cuántica". Actas de la Royal Society of London A . 439 (1907): 553–558. Bibcode :1992RSPSA.439..553D. CiteSeerX  10.1.1.655.5997 . doi :10.1098/rspa.1992.0167. S2CID  121702767.
2. R. Cleve; A. Ekert; C. Macchiavello; M. Mosca (1998). "Revisión de los algoritmos cuánticos". Actas de la Royal Society of London A . 454 (1969): 339–354. arXiv : quant-ph/9708016 . Código Bibliográfico :1998RSPSA.454..339C. doi :10.1098/rspa.1998.0164. S2CID  16128238.
3. Simon, Daniel (noviembre de 1994). "Sobre el poder de la computación cuántica". Actas del 35.º Simposio anual sobre fundamentos de la informática . pp. 116-123. doi :10.1109/SFCS.1994.365701. ISBN 0-8186-6580-7.S2CID 7457814  .
4. Johansson, N.; Larsson, JÅ. (2017). "Simulación clásica eficiente de los algoritmos de Deutsch–Jozsa y Simon". Quantum Inf Process (2017) . 16 (9): 233. arXiv : 1508.05027 . Bibcode :2017QuIP...16..233J. doi :10.1007/s11128-017-1679-7. S2CID  28670540.
5. David Deutsch (1985). "Teoría cuántica, el principio de Church-Turing y la computadora cuántica universal". Actas de la Royal Society of London A . 400 (1818): 97–117. Bibcode :1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382 . doi :10.1098/rspa.1985.0070. S2CID  1438116. 

Enlaces externos

• Conferencia de Deutsch sobre el algoritmo Deutsch-Jozsa