Algoritmo de Deutsch-Jozsa

El algoritmo de Deutsch-Jozsa generaliza el algoritmo de Deutsch (1985),[1] que resuelve el problema planteado para el caso n=1. En el año 1992 Deutsch y Jozsa encontraron la solución al problema para un número arbitrario de bits de entrada.

El de Deutsch-Jozsa es un ejemplo claro de problema que resulta sencillo de resolver para un ordenador cuántico pero muy complejo para un ordenador clásico,[2] que en el peor de los casos necesita ${\displaystyle 2^{n-1}+1}$ iteraciones para determinar si la función es constante o balanceada.

Es importante remarcar que, pese a la importancia de encontrar un problema donde un ordenador cuántico arroja un mejor resultado que uno clásico, no se han encontrado hasta la fecha aplicaciones prácticas reales de este algoritmo.^{[cita requerida]}

Circuito cuántico que implementa el algoritmo de Deutsch.

Esta es la versión del algoritmo para una función f(x) de una sola entrada. Se utilizan dos cúbits auxiliares en los cálculos. El algoritmo se ilustra en la figura de la derecha.

El bloque H es una puerta Hadamard cuya operación es la siguiente:

${\displaystyle H(|0\rangle )={\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )}$

${\displaystyle H(|1\rangle )={\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )}$

El bloque U_f denota el oráculo y realiza la operación siguiente:

${\displaystyle U_{f}(|0\rangle |0\rangle )=|0\rangle |0\oplus f(0)\rangle =|0\rangle |f(0)\rangle }$

${\displaystyle U_{f}(|0\rangle |1\rangle )=|0\rangle |1\oplus f(0)\rangle =|0\rangle |{\overline {f(0)}}\rangle }$

${\displaystyle U_{f}(|1\rangle |0\rangle )=|1\rangle |0\oplus f(1)\rangle =|1\rangle |f(1)\rangle }$

${\displaystyle U_{f}(|1\rangle |1\rangle )=|1\rangle |1\oplus f(1)\rangle =|1\rangle |{\overline {f(1)}}\rangle }$

Además,

${\displaystyle U_{f}(|0\rangle (|0\rangle -|1\rangle ))=|0\rangle |f(0)-{\overline {f(0)}}\rangle =|0\rangle |(-1)^{f(0)}(|0\rangle -|1\rangle )}$

${\displaystyle U_{f}(|1\rangle (|0\rangle -|1\rangle ))=|1\rangle |f(1)-{\overline {f(1)}}\rangle =|1\rangle |(-1)^{f(1)}(|0\rangle -|1\rangle )}$

${\displaystyle U_{f}(|x\rangle (|0\rangle -|1\rangle ))=|x\rangle |(-1)^{f(x)}(|0\rangle -|1\rangle )}$

La entrada al circuito es: ${\displaystyle |a\rangle =|0\rangle |1\rangle }$, que atraviesa dos puestas Hardamard (véase la figura) obteniéndose ${\displaystyle |b\rangle =(1/2)(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )}$. Esto atraviesa el bloque U_f obteniéndose

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

Esta expresión puede escribirse:

${\displaystyle |c\rangle =\left\{{\begin{array}{ll}\pm (1/2)(|0\rangle +|1\rangle )|(|0\rangle -|1\rangle )&{\mbox{si }}~f(0)=f(1)\\\pm (1/2)(|0\rangle -|1\rangle )|(|0\rangle -|1\rangle )&{\mbox{si }}~f(0)\neq f(1)\end{array}}\right.}$

Al atravesar la última puerta de Hadamard se obtiene:

${\displaystyle |d\rangle =\left\{{\begin{array}{ll}\pm {\frac {1}{\sqrt {2}}}|0\rangle (|0\rangle -|1\rangle )&{\mbox{si }}~f(0)=f(1)\\\pm {\frac {1}{\sqrt {2}}}|1\rangle (|0\rangle -|1\rangle )&{\mbox{si }}~f(0)\neq f(1)\end{array}}\right.}$

Puesto que si ${\displaystyle f(0)=f(1),f(0)\oplus f(1)=0}$ y si ${\displaystyle f(0)\neq f(1),f(0)\oplus f(1)=1}$, podemos escribir

${\displaystyle \pm {\frac {1}{\sqrt {2}}}|f(0)\oplus f(1)\rangle (|0\rangle -|1\rangle )}$

Este es el resultado final: midiendo el primer qúbit de la ecuación se obtiene ${\displaystyle f(0)\oplus f(1)}$. Si resulta el valor 0, entonces la función f(x) es constante, mientras que si resulta 1, la función es balanceada.

Circuito cuántico que implementa el algoritmo de Deutsch-Jozsa.

Esta es la versión general del algoritmo para funciones f(x) de n entradas.

En este caso, la entrada al circuito es:

${\displaystyle |a\rangle =|0\rangle ^{\otimes n}|1\rangle }$

A continuación de las puertas Hadamard se obtiene:

${\displaystyle |b\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}$

A la salida del bloque U_f se tiene:

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

La última puerta Hadamard produce la siguiente salida

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

Y por último, realizando la medición, se obtiene z. En el caso en que la función f(x) sea balanceda, las contribuciones para ${\displaystyle (0,\ldots ,0)}$ se cancelan y la medida de z debe dar una combinación distinta. Por el contrario, si f(x) es constante se obtiene ${\displaystyle (0,\ldots ,0)}$ en la medida, pues el resto de las contribuciones se cancelan en este caso. Por consiguiente, comprobando si z es cero o distinto de cero se sabe que la función es, respectivamente, constante o balanceada.

• Algoritmo de Bernstein–Vazirani

1. Deutsch, David; Jozsa, Richard (1992). «Rapid solutions of problems by quantum computation». Proceedings of the Royal Society of London A. 439 (1907): 553–558. Bibcode:1992RSPSA.439..553D. doi:10.1098/rspa.1992.0167.
2. Johansson, N.; Larsson, JÅ. (2017). «Efficient classical simulation of the Deutsch–Jozsa and Simon's algorithms». Quantum Inf Process (2017) 16: 233. Bibcode:2017QuIP...16..233J. doi:10.1007/s11128-017-1679-7.

• Michael A. Nielsen e Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Reino Unido, 2000, ISBN 0-521-63503-9.
• Alberto Galindo y Miguel Ángel Martin-Delgado (2002). Information and computation: classical and quantum aspects. Reviews of Modern Physics, 74(2), 347

• https://qiskit.org/textbook/ch-algorithms/deutsch-jozsa.html