Algoritmo de Deutsch-Jozsa

Algoritmo de Deutsch-Jozsa

En computación cuántica, el algoritmo de Deutsch-Jozsa es un algoritmo cuántico, propuesto por David Deutsch y Richard Jozsa en 1992. Fue uno de los primeros algoritmos diseñados para ejecutar sobre un computador cuántico y que tiene el potencial de ser más eficiente que los algoritmos clásicos al aprovechar el paralelismo inherente de los estados de superposición cuánticos.

En el problema de Deutsch-Jozsa nos dan una función cuántica (que para nosotros es una caja negra) f(x1, x2,..., xn) que toma n bits de entrada x1, x2,..., xn y devuelve un valor binario f(x1, x2,..., xn). Sabemos que la función es constante (0 en todas las entradas o 1 en todas las entradas) o balanceada (devuelve 1 para la mitad de las entradas y 0 para la otra mitad); el problema es entonces determinar cómo es la función (constante o balanceada) aplicando entradas a la caja negra y observando su salida.

Algoritmo de Deutsch

Circuito cuántico que implementa el algoritmo de Deutsch.

Esta es una versión del algoritmo para una función f(x) de una sola entrada. Se utilizan dos qubits 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:

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

El bloque Uf realiza la operación siguiente:

U_f(|0\rangle |0\rangle )=|0\rangle |0\oplus f(0)\rangle =|0\rangle |f(0)\rangle
U_f(|0\rangle |1\rangle )=|0\rangle |1\oplus f(0)\rangle =|0\rangle |\overline{f(0)}\rangle
U_f(|1\rangle |0\rangle )=|1\rangle |0\oplus f(1)\rangle =|1\rangle |f(1)\rangle
U_f(|1\rangle |1\rangle )=|1\rangle |1\oplus f(1)\rangle =|1\rangle |\overline{f(1)}\rangle

Además,

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 )
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 )
U_f(|x\rangle (|0\rangle -|1\rangle ))=|x\rangle |(-1)^{f(x)}(|0\rangle -|1\rangle )

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

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

|c\rangle= \left\{\begin{array}{ll} \pm(|0\rangle +|1\rangle )|(|0\rangle -|1\rangle )& \mbox{si } ~ f(0)=f(1) \\ \pm(|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 obtenemos:

|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 f(0)=f(1), f(0)\oplus f(1)=0 y si f(0)\neq f(1), f(0)\oplus f(1)=1, podemos escribir

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

Este es el resultado final: midiendo el primer qubit de la ecuación obtenemos 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.

Algoritmo de Deutsch-Jozsa

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:

|a\rangle=|0\rangle^{\oplus n}|1\rangle

A continuación de las puertas Hadamard obtenemos:

|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 Uf se tiene:

|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

|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, obtenemos z. En el caso en que la función f(x) sea balanceda, las contribuciones para (0,\ldots,0) se cancelan y la medida de z debe dar una combinación distinta. Por el contrario, si f(x) es constante obtenemos (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 sabemos que la función es, respectivamente, constante o balanceada.

Referencias

  • Michael A. Nielsen e Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Reino Unido, 2000, ISBN:0-521-63503-9.

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Algoritmo cuántico — Transformada de Fourier cuántica sobre tres qubits, basada en la aplicación reiterada de la puerta cuántica de Hadamard y de puertas de cambio de fase. Un algoritmo cuántico es un algoritmo que se ejecuta en un modelo realista de computación… …   Wikipedia Español

  • Algoritmo de Grover — En computación cuántica, el algoritmo de Grover es un algoritmo cuántico para la búsqueda en una secuencia no ordenada de datos con N componentes en un tiempo O (N1/2), y con una necesidad adicional de espacio de almacenamiento de O(logN) (véase… …   Wikipedia Español

  • David Deutsch — Saltar a navegación, búsqueda David Elieser Deutsch (nacido en 1953 en Haifa, Israel) es un físico de la Universidad de Oxford, miembro de la Royal Society. Es profesor visitante en el Department of Atomic and Laser Physics del Centre for Quantum …   Wikipedia Español

  • Computación cuántica — La esfera de Bloch es una representación de un qubit, el bloque de construcción fundamental de los computadores cuánticos. La computación cuántica es un paradigma de computación distinto al de la computación clásica. Se basa en el uso de qubits… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”