COMPUTACIÓN CUÁNTICA Puertas cuánticas Problema de Deutsch Modelo cuántico de computación...

COMPUTACIÓN CUÁNTICA

Puertas cuánticas

Problema de Deutsch

Modelo cuántico de computación

Teletransporte

Algoritmo de Shor

Ordenadores cuánticos

Puertas cuánticas

Puertas cuánticas de un qubit:

Negación: X

X|0 = |1X|1 = |0

Cambio de fase: Z

Z|0 = |0Z|1 = |1

Puertas cuánticas

Puertas cuánticas de un qubit:

Cambio de fase general: Rk

Rk |0 = |0Rk |1 = exp(2i/2k)|1

|0 + |1

2

Puerta de Hadamard: H

H|0 = H|1 =|0 |1

2

Puertas cuánticas

Puertas cuánticas de dos qubits:

Negación controlada: X

X|0x = |0xX|1x = |1 X|x

Intercambio de qubits: S

S|xy = |yx

Función booleana f: Uf

Uf|x,y = |x,xf(y)

Puertas cuánticas

Conjunto universal:

X + puertas de un qubit

Representación:

X

U

U

X

S

Uf

Uf

Problema de Deutsch

Determinar si una función booleana f(x)es constante o no

Para resolver el problema clásicamente hay que evaluar f(0) y f(1)

Para resolverlo cuánticamente sólo hay que evaluar Uf una vez

Problema de Deutsch

Modelo cuántico de computación

Puertas

cuánticas

Medidas

cuánticasout

in = |0

No es necesario que el estado inicial sea |0

Se pueden mezclar puertas y medidas

Teletransporte

Par EPR1 2

2

Teletransporte

(a|0+b|1) (|00+|11)=

Algoritmo de Shor

1. Elegir a aleatoriamente entre 0 y N-1.Si mcd(a,N) 1 fin.

3. Si T es impar ir al paso 1.

4. Si mcd(aT/2+1,N) N fin, en otro caso

ir al paso 1.

2. Determinar el periodo T de la función f(x) = ax mod N.

Algoritmo de Shor

1. Iniciar 0 = |0|01er reg: n qubits t.q. N2 Q < 2N2 con Q = 2n

2o reg: m qubits tal que N 2m < 2N

2. Aplicar la QFT al 1er reg:

F |0 |0 = |j |0 = 1j=0

Q-1

Q1

3. Calcular f en el 2o reg:

Uf 1 = |j |f(j) = 2j=0

Q-1

Q1

Algoritmo de Shor

6. Calcular el periodo T a partir de k.

4. Aplicar la QFT al 1er reg:

F 2 = jk |k |f(j) = 3j=0

Q-1

Q1

k=0

Q-1

3 = |k |A(k)Q1

k=0

Q-1

con |A(k) = jk |f(j)j=0

Q-1

5. Medir el 1er reg:

k {0,1, ... Q-1} con Prob(k) = || A(k) ||2

= exp(2i/2n)

Algoritmo de Shor

Algoritmo para la QFT

Algoritmo de Shor

Ejemplo de QFT

Algoritmo de Shor

Obtención del periodo T a partir de k

j/T es una convergente de lafracción continua de k/Q

Algoritmo de Shor

Simulación del algoritmo

shor(N);

tshor(N);

pshor(N);

Algoritmo de Shor

Probabilidad de éxito para N 255

Probabilidad de éxito: P Cte / loglog(N)

Ordenadores cuánticos