algoritmos cuanticos

1. 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óncuá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(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 esentonces 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 auxiliares en los cálculos. El algoritmo se ilustra en la figura de la derecha.
El bloque H esuna puerta Hadamard cuya operación es la siguiente:


El bloque Uf realiza la operación siguiente:




Además,



La entrada al circuito es: , que atraviesa dos puestas Hardamard (véase la figura) obteniéndose . Esto atraviesa el bloque obteniéndose

Esta expresión puede escribirse:

Al atravesar la última puerta de Hadamard obtenemos:

Puesto que sí   y si , podemos escribir

Estees el resultado final: midiendo el primer qubit de la ecuación obtenemos. 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 nentradas.
En este caso, la entrada al circuitoes:

A continuación de las puertas Hadamard se obtiene:

A la salida del bloque Uf se tiene:

La última puerta Hadamard produce la siguiente salida

Y por último, realizando la medición, se obtiene z. En el caso en que la función f(x) sea balanceada, las contribuciones para  se cancelan y la medida de z debe dar una combinación distinta. Por el contrario, si f(x) es constante se obtiene  enla 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.

2. 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 notación O). Fue inventado por Lov K. Grover en 1996.
En una búsqueda normal de un dato, si tenemos una secuencia desordenada se debe realizar una inspección lineal, que necesita un tiempo de O (N), por lo que el algoritmo de Grover es una mejora bastante sustancial, evitando, además, la necesidad de la ordenaciónprevia. La ganancia obtenida es "sólo" de la raíz cuadrada, lo que contrasta con otras mejoras de los algoritmos cuánticos que obtienen mejoras de orden exponencial sobre sus contrapartidas clásicas.
Al igual que otros algoritmos de naturaleza cuántica, el algoritmo de Grover es un algoritmo de carácter probabilístico, por lo que produce la respuesta correcta con una determinada probabilidad de error,que, no obstante, puede obtenerse tan baja como se desee por medio de iteraciones.
Aunque el propósito del algoritmo es, como ha sido indicado, la búsqueda en una secuencia, se podría describir de una manera más adecuada como la "inversión de una función". Así, si tenemos la función y=f (x), que puede ser evaluada en un computador cuántico, este algoritmo nos permite calcular el valor...