PARTE 1 - Aula 141aula141.cat/wp-content/uploads/2015/03/ComputacionCuantica... · Computación...
Transcript of 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