Download Computación Cuántica Topológica PARTE 1

Introducción
a la
Computación Cuántica Topológica
PARTE 1
Javier García
IFAE / UAB
Sumario
- Computación clásica
- Probabilidad
- Mecánica cuántica
- Computación cuántica
Computación Clásica
Computación Clásica
Puerta NOT
NOT
0
NOT
1
1
NOT
0
Computación Clásica
Puerta AND
AND
0
0
AND
0
0
1
1
1
AND
0
0
1
AND
0
AND
1
Computación Clásica
Puerta OR
OR
0
0
OR
0
0
1
1
1
OR
0
1
1
OR
1
OR
1
Computación Clásica
Nuestro Primer Algoritmo
Nos dan un dispositivo f
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
Computación Clásica
Esta es una solución
Este circuito devuelve 0 si es constante y 1 en caso contrario
Computación Clásica
Comprobamos I
f
0
0
=
constante = 0
1
0
0
0
0
0
1
0
1
Computación Clásica
Comprobamos II
f
0
1
=
constante = 1
0
0
1
0
1
0
1
1
0
Computación Clásica
Comprobamos III
f
0
0
=
NO constante
1
1
1
1
0
0
1
1
0
Computación Clásica
Comprobamos IV
f
0
1
=
NO constante
0
0
0
1
1
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
Estado inicial = 1/5 .
+ 4/5 .
. Estado inicial
Estado final =
Estado final =
.
( 1/5 .
Estado final = 1/5 .
+ 4/5 .
(
Estado final = 1/5 . 2/3
(
+ 1/4 .
= 3/4 .
+ 1/3 .
= 2/3 .
)
+ 4/5 .
)+
+ 1/3
)
Estado final = 1/5 . 2/3 + 4/5 . 3/4
(
4/5 . 3/4
+
(1/5 . 1/3 +
)
+ 1/4
)
4/5 . 1/4
Probabilidad
Existe un álgebra equivalente, por ser un proceso lineal
Estado inicial = 1/5 .
+ 4/5 .
. Estado inicial
Estado final =
Estado final =
.
( 1/5 .
Estado final = 1/5 .
+ 4/5 .
(
Estado final = 1/5 . 2/3
(
+ 1/4 .
= 3/4 .
+ 1/3 .
= 2/3 .
)
+ 4/5 .
)+
+ 1/3
)
Estado final = 1/5 . 2/3 + 4/5 . 3/4
(
4/5 . 3/4
+
(1/5 . 1/3 +
)
+ 1/4
)
4/5 . 1/4
Probabilidad
Existe un álgebra equivalente, por ser un proceso lineal
Estado inicial = 1/5 .
+ 4/5 .
. Estado inicial
Estado final =
Estado final =
.
( 1/5 .
Estado final = 1/5 .
+ 4/5 .
(
Estado final = 1/5 . 2/3
(
+ 1/4 .
= 3/4 .
+ 1/3 .
= 2/3 .
)
+ 4/5 .
)+
+ 1/3
)
Estado final = 1/5 . 2/3 + 4/5 . 3/4
(
4/5 . 3/4
+
(1/5 . 1/3 +
)
+ 1/4
)
4/5 . 1/4
Probabilidad
Existe un álgebra equivalente, por ser un proceso lineal
Estado inicial = 1/5 .
+ 4/5 .
. Estado inicial
Estado final =
Estado final =
.
( 1/5 .
Estado final = 1/5 .
+ 4/5 .
(
Estado final = 1/5 . 2/3
(
+ 1/4 .
= 3/4 .
+ 1/3 .
= 2/3 .
)
+ 4/5 .
)+
+ 1/3
)
Estado final = 1/5 . 2/3 + 4/5 . 3/4
(
4/5 . 3/4
+
(1/5 . 1/3 +
)
+ 1/4
)
4/5 . 1/4
Probabilidad
Existe un álgebra equivalente, por ser un proceso lineal
Estado inicial = 1/5 .
+ 4/5 .
. Estado inicial
Estado final =
Estado final =
.
( 1/5 .
Estado final = 1/5 .
+ 4/5 .
(
Estado final = 1/5 . 2/3
(
+ 1/4 .
= 3/4 .
+ 1/3 .
= 2/3 .
)
+ 4/5 .
)+
+ 1/3
)
Estado final = 1/5 . 2/3 + 4/5 . 3/4
(
4/5 . 3/4
+
(1/5 . 1/3 +
)
+ 1/4
)
4/5 . 1/4
Probabilidad
Existe un álgebra equivalente, por ser un proceso lineal
Estado inicial = 1/5 .
+ 4/5 .
. Estado inicial
Estado final =
Estado final =
.
( 1/5 .
Estado final = 1/5 .
+ 4/5 .
(
Estado final = 1/5 . 2/3
(
+ 1/4 .
= 3/4 .
+ 1/3 .
= 2/3 .
)
+ 4/5 .
)+
+ 1/3
)
Estado final = 1/5 . 2/3 + 4/5 . 3/4
(
4/5 . 3/4
+
(1/5 . 1/3 +
)
+ 1/4
)
4/5 . 1/4
Probabilidad
Existe un álgebra equivalente, por ser un proceso lineal
Estado inicial = 1/5 .
+ 4/5 .
. Estado inicial
Estado final =
Estado final =
.
( 1/5 .
Estado final = 1/5 .
+ 4/5 .
(
Estado final = 1/5 . 2/3
(
+ 1/4 .
= 3/4 .
+ 1/3 .
= 2/3 .
)
+ 4/5 .
)+
+ 1/3
)
Estado final = 1/5 . 2/3 + 4/5 . 3/4
(
4/5 . 3/4
+
(1/5 . 1/3 +
)
+ 1/4
)
4/5 . 1/4
Probabilidad
Probabilidad final
(
)
Estado final = 1/5 . 2/3 + 4/5 . 3/4
Estado final = 11/15
Probabilidad final de
estar a la izquierda
+
(1/5 . 1/3 +
)
4/5 . 1/4
+ 4/15
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
Se ha de cumplir
2 6
5
1
5
Amplitudes
1
5
2

2 6
5
2
1
Mecánica cuántica
Tenemos dos armarios.
En uno de ellos hay una pelota cuántica
1
5
2 6
5
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
Tenemos un robot cuántico (que se llama U)
REVERSIBILIDAD y UNITARIEDAD
A  A 2  A  B 2  1
B  B 2  B  A 2  1
A  AB  A  A  BB  B  0
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
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
2 6 .
5
Estado inicial = 1/5 .
+
Estado final =
. Estado inicial
.
Estado final =
(
1/5 .
Estado final = 1/5 .
= 2/3 .
+
(
Estado final = 1/5 . 2/3 +
+
2 6
5
2 6 .
5
+
.
2 6
5
)
.
.
)
+
(
1/5 .
- 2/3 .
.
=
-
2 6
5
)
. 2/3
Mecánica cuántica
Probabilidad final
(
Estado final = 1/5 . 2/3 +
2 6
5
.
Estado final = 0.8636
AMPLITUD final de
estar a la izquierda
)
+
(
1/5 .
-
2 6
5
- 0.50413
AMPLITUD final de
estar a la derecha
0. 745 86  0. 254 14  1
)
. 2/3
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
x
x
f
a
Reversible!
a  fx
Computación cuántica
Puerta cuántica: FUNCIÓN
x
x
f
a  fx
a
x
,

a
,









Computación cuántica
Algoritmo Deutsch-Jozsa
H
H
?
H
f
H
Si ? =
 Función constante
Si ? =
 Función NO constante
Computación cuántica
Algoritmo Deutsch-Jozsa
H
H
?
H
f
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