parte 1 - aula 141aula141.cat/wp-content/uploads/2015/03/computacioncuantica... · computación...

Javier García IFAE / UAB

Introducción a la

Computación Cuántica Topológica PARTE 1

Sumario

- Computación clásica - Probabilidad - Mecánica cuántica - Computación cuántica

Computación Clásica

Computación Clásica

NOT

0

Puerta NOT

NOT

NOT 0

1

1

Computación Clásica

0

Puerta AND

AND

AND

0

0

1

AND

0

0

0

AND

1

0

1

AND

1

1

Computación Clásica

0

Puerta OR

0

0

1

0

1

0

1

1

1

1

1

OR

OR OR

OR OR

Computación Clásica

Nuestro Primer Algoritmo

f

Nos dan un dispositivo f

- Tanto la entrada como la salida es 0 ó 1. - Actúa siempre de la misma manera.

Nuestra misión Construir un algoritmo que nos diga si es o no una función constante

f

f

Computación Clásica

Esta es una solución

Este circuito devuelve 0 si es constante y 1 en caso contrario

f

f

Computación Clásica

Comprobamos I

0

= constante = 0

1

0

0

0

0

0

1

1

0

0

f

f

Computación Clásica

Comprobamos II

0

= constante = 1

1

0

1

0

1

1

1

0

0

0

f

f

Computación Clásica

Comprobamos III

0

= NO constante

1

1

0

0

1

1

0

0

1

1

f

f

Computación Clásica

Comprobamos IV

0

= NO constante

1

0

1

1

0

0

1

1

0

1

Probabilidad

Probabilidad

Tenemos dos armarios. En uno de ellos hay una pelota

P = 1/5 P = 4/5

Probabilidad

Tenemos dos armarios. En uno de ellos hay una pelota

P = 1/5 P = 4/5

Probabilidad

Tenemos un robot (que se llama U)

U está programado de manera que al abrir la puerta trasera del armario: 1) Si encuentra la pelota a la izquierda: - La dejará ahí con probabilidad 2/3 - o la moverá a la derecha con probabilidad 1/3 2) Si encuentra la pelota a la derecha: - La dejará ahí con probabilidad 1/4 - o la moverá a la izquierda con probabilidad 3/4

Probabilidad

Nos preguntamos cuál es la probabilidad de encontrar la pelota a la derecha después de que el robot haya actuado

Probabilidad

Diagrama de árbol

Probabilidad Existe un álgebra equivalente, por ser un proceso lineal

1/5 + 4/5 Estado inicial =

Estado final = Estado inicial .

. .

Estado final = . 1/5 + 4/5 . . ( )

2/3 + 1/3 . . =

Estado final = 1/5 + 4/5 . .

3/4 + 1/4 . . =

Estado final = 1/5 + 4/5 . . 2/3 + 1/3 ( ) 3/4 + 1/4 ( )

Estado final = 1/5 2/3 + 4/5 3/4 . . ( ) 1/5 1/3 + 4/5 1/4 . . ( ) +

Probabilidad Existe un álgebra equivalente, por ser un proceso lineal

1/5 + 4/5 Estado inicial =

Estado final = Estado inicial .

. .

Estado final = . 1/5 + 4/5 . . ( )

2/3 + 1/3 . . =

Estado final = 1/5 + 4/5 . .

3/4 + 1/4 . . =

Estado final = 1/5 + 4/5 . . 2/3 + 1/3 ( ) 3/4 + 1/4 ( )

Estado final = 1/5 2/3 + 4/5 3/4 . . ( ) 1/5 1/3 + 4/5 1/4 . . ( ) +

Probabilidad Existe un álgebra equivalente, por ser un proceso lineal

1/5 + 4/5 Estado inicial =

Estado final = Estado inicial .

. .

Estado final = . 1/5 + 4/5 . . ( )

2/3 + 1/3 . . =

Estado final = 1/5 + 4/5 . .

3/4 + 1/4 . . =

Estado final = 1/5 + 4/5 . . 2/3 + 1/3 ( ) 3/4 + 1/4 ( )

Estado final = 1/5 2/3 + 4/5 3/4 . . ( ) 1/5 1/3 + 4/5 1/4 . . ( ) +

Probabilidad Existe un álgebra equivalente, por ser un proceso lineal

1/5 + 4/5 Estado inicial =

Estado final = Estado inicial .

. .

Estado final = . 1/5 + 4/5 . . ( )

2/3 + 1/3 . . =

Estado final = 1/5 + 4/5 . .

3/4 + 1/4 . . =

Estado final = 1/5 + 4/5 . . 2/3 + 1/3 ( ) 3/4 + 1/4 ( )

Estado final = 1/5 2/3 + 4/5 3/4 . . ( ) 1/5 1/3 + 4/5 1/4 . . ( ) +

Probabilidad Existe un álgebra equivalente, por ser un proceso lineal

1/5 + 4/5 Estado inicial =

Estado final = Estado inicial .

. .

Estado final = . 1/5 + 4/5 . . ( )

2/3 + 1/3 . . =

Estado final = 1/5 + 4/5 . .

3/4 + 1/4 . . =

Estado final = 1/5 + 4/5 . . 2/3 + 1/3 ( ) 3/4 + 1/4 ( )

Estado final = 1/5 2/3 + 4/5 3/4 . . ( ) 1/5 1/3 + 4/5 1/4 . . ( ) +

Probabilidad Existe un álgebra equivalente, por ser un proceso lineal

1/5 + 4/5 Estado inicial =

Estado final = Estado inicial .

. .

Estado final = . 1/5 + 4/5 . . ( )

2/3 + 1/3 . . =

Estado final = 1/5 + 4/5 . .

3/4 + 1/4 . . =

Estado final = 1/5 + 4/5 . . 2/3 + 1/3 ( ) 3/4 + 1/4 ( )

Estado final = 1/5 2/3 + 4/5 3/4 . . ( ) 1/5 1/3 + 4/5 1/4 . . ( ) +

Probabilidad Existe un álgebra equivalente, por ser un proceso lineal

1/5 + 4/5 Estado inicial =

Estado final = Estado inicial .

. .

Estado final = . 1/5 + 4/5 . . ( )

2/3 + 1/3 . . =

Estado final = 1/5 + 4/5 . .

3/4 + 1/4 . . =

Estado final = 1/5 + 4/5 . . 2/3 + 1/3 ( ) 3/4 + 1/4 ( )

Estado final = 1/5 2/3 + 4/5 3/4 . . ( ) 1/5 1/3 + 4/5 1/4 . . ( ) +

Probabilidad

Probabilidad final

Estado final = 1/5 2/3 + 4/5 3/4 . . ( ) 1/5 1/3 + 4/5 1/4 . . ( ) +

Estado final = + 11/15 4/15

Probabilidad final de estar a la izquierda

Probabilidad final de estar a la derecha

Mecánica cuántica

Mecánica cuántica

Tenemos dos armarios. En uno de ellos hay una pelota cuántica

2 6

515

Amplitudes

15

2 2 6

5

2

1Se ha de cumplir

Tenemos dos armarios. En uno de ellos hay una pelota cuántica

Mecánica cuántica

2 6

5

15

Tenemos un robot cuántico (que se llama U)

U está programado de manera que al abrir la puerta trasera del armario: 1) Si encuentra la pelota a la izquierda: - La dejará ahí con AMPLITUD 2/3 - o la moverá a la derecha con AMPLITUD (√5)/3 2) Si encuentra la pelota a la derecha: - La dejará ahí con AMPLITUD -2/3 - o la moverá a la izquierda con AMPLITUD (√5)/3

Mecánica cuántica

Tenemos un robot cuántico (que se llama U)

U está programado de manera que al abrir la puerta trasera del armario: 1) Si encuentra la pelota a la izquierda: - La dejará ahí con AMPLITUD 2/3 - o la moverá a la derecha con AMPLITUD (√5)/3 2) Si encuentra la pelota a la derecha: - La dejará ahí con AMPLITUD -2/3 - o la moverá a la izquierda con AMPLITUD (√5)/3

Mecánica cuántica

A A2 A B2 1

B B2 B A2 1

A AB A A BB B 0

REVERSIBILIDAD y UNITARIEDAD

Nos preguntamos cuál es la AMPLITUD de encontrar la pelota a la derecha después de que el robot cuántico haya actuado sobre la pelota cuántica

Mecánica cuántica

Diagrama de árbol

Mecánica cuántica

Existe un álgebra equivalente, por ser un proceso lineal

1/5 + Estado inicial =

Estado final = Estado inicial .

. .

Estado final = . 1/5 . . ( )

2/3 + . . =

Estado final = 1/5 . .

- 2/3 . . =

Estado final = 1/5 2/3 + . . ( ) 1/5 . . ( ) +

Mecánica cuántica

2 6

5

2 6

5+

2 6

5+

2 6

5- 2 6

52/3

Probabilidad final

Estado final = - 0.8636 0.50413

AMPLITUD final de estar a la izquierda

AMPLITUD final de estar a la derecha

Mecánica cuántica

Estado final = 1/5 2/3 + . . ( ) 1/5 . . ( ) + 2 6

5- 2 6

52/3

0.74586 0.25414 1

Computación cuántica

Computación cuántica

Puerta cuántica Hadamard

H 1

2

1

2

H 1

2

1

2

Computación cuántica

Puerta cuántica: FUNCIÓN

f x x

a fxa

Reversible!

Computación cuántica

Puerta cuántica: FUNCIÓN

f x x

a fxa

x ,

a ,

H

Computación cuántica

Algoritmo Deutsch-Jozsa

f

H

H

H

?

Si = ? Función constante

Si = ? Función NO constante

H

Computación cuántica

Algoritmo Deutsch-Jozsa

f

H

H

H

?

Si = ? Función constante

Si = ? Función NO constante

La mejora con respecto al algoritmo clásico es que solo se usa la puerta f una vez.

Computación cuántica

Realización experimental Deutsch-Jozsa

Fin primera parte