Download Fundamentos de lenguajes de programación cuántica

Fundamentos de lenguajes
de programación cuántica
Día 1:
∼ Introducción a la computación cuántica ∼
Alejandro Díaz-Caro
Universidad Nacional de Quilmes
22o Escuela de Verano de Ciencias Informáticas
Río Cuarto, Córdoba – 9 al 14 de febrero de 2015
Un poco de historia
Richard Feynman
First Conference on the Physics of Computation, MIT, 1981
Simulación
I
Física clásica =⇒ computación clásica
I
Física cuántica =⇒ ¿computación clásica?
Necesidad de una computadora
cuántica para simular física cuántica
Alejandro Díaz-Caro
Fundamentos de lenguajes de programación cuántica - RIO’15
2 / 13
Un poco de historia
Richard Feynman
First Conference on the Physics of Computation, MIT, 1981
Simulación
I
Física clásica =⇒ computación clásica
I
Física cuántica =⇒ ¿computación clásica?
Necesidad de una computadora
cuántica para simular física cuántica
Entre tanto en Rusia. . .
R. P. Poplavskii
Uspekhi Fizicheskikh Nauk, 115:3, 465–501, 1975
Inviabilidad computacional de simular sistemas
cuánticos (debido al ppio de superposición)
Yuri I. Manin
I
Moscow, Sovetskoye Radio, 1980
I
Uso del número exponencial de estados de base
I
Propuesta de teoría de computación cuántica
Alejandro Díaz-Caro
Fundamentos de lenguajes de programación cuántica - RIO’15
2 / 13
Un poco de historia (continuación)
Paul Benioff
Charles Bennett y Gilles Brassard
Journal of Statistical Physics 29 (3):515–
Int. Conference on Computers, Systems and
546, 1982
Signal Processing, EE.UU., 1984
I
Primer framework teórico
para computación cuántica
I
BB84: Método de distribuciónd
de claves para criptografía
David Deutsch
Proceedings of the Royal Society A 400
(1818):97–117, 1985
I
. . . Varios hitos históricos
omitidos . . .
Máquina de Turing Cuántica:
máquina cuántica universal
Peter Shor
Lov Grover
35th Annual Symposium on Foundations
of Computer Science, EE.UU., 1994
28th Annual ACM Symposium on the
Theory of Computing, EE.UU., 1996
I
Algoritmo cuántico para
factorizar números primos
Alejandro Díaz-Caro
I
Algoritmo de búsqueda
(con ganancia cuadrática)
Fundamentos de lenguajes de programación cuántica - RIO’15
3 / 13
Contenido del curso
Lunes y Martes: Introducción a computación cuántica
I Álgebra
I Bits cuánticos y operadores
I Teorema de no-clonado
I Estados de Bell
I Codificación superdensa y teleportación cuántica
I Paralelismo cuántico
Algoritmo de Deutsch, Deutsch-Jotza, Grover y BB84
Miércoles: Introducción a λ-cálculo y teoría de tipos
Jueves y Viernes: Extensiones a λ-cálculo para computación cuántica
Alejandro Díaz-Caro
Fundamentos de lenguajes de programación cuántica - RIO’15
4 / 13
Álgebra
En el pizarrón
I
I
I
Alejandro Díaz-Caro
Espacio de Hilbert
Producto tensorial
Notación bra-ket
Fundamentos de lenguajes de programación cuántica - RIO’15
5 / 13
Bits cuánticos
Un qubit es. . .
(para un físico)
. . . un sistema cuántico con dos niveles de energía
y que puede ser manipulado arbitrariamente
Alejandro Díaz-Caro
Fundamentos de lenguajes de programación cuántica - RIO’15
6 / 13
Bits cuánticos
Un qubit es. . .
(para un físico)
. . . un sistema cuántico con dos niveles de energía
y que puede ser manipulado arbitrariamente
pero nosotros no somos físicos. . .
(para un matemático o informático)
. . . un vector normalizado del espacio de Hilbert C2
Alejandro Díaz-Caro
Fundamentos de lenguajes de programación cuántica - RIO’15
6 / 13
Bits cuánticos
Un qubit es. . .
(para un físico)
. . . un sistema cuántico con dos niveles de energía
y que puede ser manipulado arbitrariamente
pero nosotros no somos físicos. . .
(para un matemático o informático)
. . . un vector normalizado del espacio de Hilbert C2
n-qubits: un vector de
n
N
n
C2 = C 2
i=1
Alejandro Díaz-Caro
Fundamentos de lenguajes de programación cuántica - RIO’15
6 / 13
Operadores
En el pizarrón
I
I
I
I
Operador
Adjunto y propiedades
Proyector
Operador hermítico
Alejandro Díaz-Caro
I
I
I
I
Operador unitario
Operador de medición
Compuertas cuánticas
Evolución
Fundamentos de lenguajes de programación cuántica - RIO’15
7 / 13
No-controlada
Negación
H=
Alejandro Díaz-Caro
√1
2
1
1
+ |1i)
− |1i)
1
−1
X |0i = |1i
X |1i = |0i
0 1
X=
1 0
CNOT |0x i = |0x i
CNOT |1x i = |1i ⊗ X |x i
I 0
CNOT =
0 X
Identidad
H|1i =
√1 (|0i
2
√1 (|0i
2
Cambio
de fase
H|0i =
Matrices de
Pauli
Hadamard
Compuertas más comunes y operadores de Pauli
I|0i = |0i
I|1i = |1i
1 0
I=
0 1
Z |0i = |0i
Z |1i = −|1i
1
0
Z=
0 −1
I
X
iXZ
Z
Fundamentos de lenguajes de programación cuántica - RIO’15
8 / 13
Teorema de no-clonado
Teorema (No clonado)
No existe ninguna compuerta cuántica U tal que para algún |φi ∈ CN y
para todo |ψi ∈ CN se cumpla
U|ψφi = |ψψi
Es decir. . .
No existe una máquina universal de
clonado
Alejandro Díaz-Caro
Fundamentos de lenguajes de programación cuántica - RIO’15
9 / 13
Teorema de no-clonado
Teorema (No clonado)
No existe ninguna compuerta cuántica U tal que para algún |φi ∈ CN y
para todo |ψi ∈ CN se cumpla
U|ψφi = |ψψi
Es decir. . .
No existe una máquina universal de
clonado
o más simplemente
No se puede copiar un qubit
desconocido
Alejandro Díaz-Caro
Fundamentos de lenguajes de programación cuántica - RIO’15
9 / 13
Estados de Bell
|x i
H
•
βxy
|y i
Alejandro Díaz-Caro
Entrada
|00i
|01i
|10i
|11i
Salida
β00
β01
β10
β11
Fundamentos de lenguajes de programación cuántica - RIO’15
=
=
=
=
√1 (|00i
2
√1 (|01i
2
√1 (|00i
2
√1 (|01i
2
+ |11i)
+ |10i)
− |11i)
− |10i)
10 / 13
Estados de Bell
|x i
H
Entrada
|00i
|01i
|10i
|11i
•
βxy
|y i
Ejemplo:
M0
M=
M1
= |0ih0|
= |1ih1|
Salida
β00
β01
β10
β11
=
=
=
=
√1 (|00i
2
√1 (|01i
2
√1 (|00i
2
√1 (|01i
2
+ |11i)
+ |10i)
− |11i)
− |10i)
Entonces
(M ⊗ I)β00
Alejandro Díaz-Caro
|00i
|11i
Fundamentos de lenguajes de programación cuántica - RIO’15
10 / 13
Codificación superdensa
Objetivo:
Transmitir 2 bits clásicos enviando tan sólo 1 qubit
Alejandro Díaz-Caro
Fundamentos de lenguajes de programación cuántica - RIO’15
11 / 13
Codificación superdensa
Objetivo:
Transmitir 2 bits clásicos enviando tan sólo 1 qubit
1. A y B preparan β00
Z b1 X b2 | • H
β00
b1
|
|
2. Se llevan cada uno un qubit
3. A aplica Z b1 X b2 a su qubit
4. A envía su qubit a B
b2
5. B aplica CNOT y H a ambos
6. B mide
Alejandro Díaz-Caro
Fundamentos de lenguajes de programación cuántica - RIO’15
11 / 13
Teleportación cuántica
Objetivo:
Transmitir 1 qubit enviando 2 bits clásicos
Alejandro Díaz-Caro
Fundamentos de lenguajes de programación cuántica - RIO’15
12 / 13
Teleportación cuántica
Objetivo:
Transmitir 1 qubit enviando 2 bits clásicos
|ψi
1. A y B preparan β00
• H
2. Se llevan cada uno un qubit
3. A aplica CNOT y H al qubit a
transmitir y el suyo del par
β00
4. A mide y envía el resultado a B
Z b1 X b2
Alejandro Díaz-Caro
|ψi
5. B aplica Z b1 X b2 (b1 y b2 de A)
Fundamentos de lenguajes de programación cuántica - RIO’15
12 / 13
Paralelismo cuántico
Primera intuición
f : {0, 1} → {0, 1}
Resultados posibles: 2
Cantidad de evaluaciones para obtenerlos: 2
Alejandro Díaz-Caro
Fundamentos de lenguajes de programación cuántica - RIO’15
13 / 13
Paralelismo cuántico
Primera intuición
f : {0, 1} → {0, 1}
Resultados posibles: 2
Cantidad de evaluaciones para obtenerlos: 2
Supongamos que existe la siguiente compuerta:
Uf |x , 0i = |x , f (x )i
Alejandro Díaz-Caro
Fundamentos de lenguajes de programación cuántica - RIO’15
13 / 13
Paralelismo cuántico
Primera intuición
f : {0, 1} → {0, 1}
Resultados posibles: 2
Cantidad de evaluaciones para obtenerlos: 2
Supongamos que existe la siguiente compuerta:
Uf |x , 0i = |x , f (x )i
|0i
H
Uf
|ψi =
|0,f (0)i+|1,f (1)i
√
2
|0i
Es decir:
1
1
1
H(1)
Uf
√ (|0, f (0)i+|1, f (1)i)
|00i −−−→ √ (|0i+|1i)|0i = √ (|00i+|10i) −→
2
2
2
Cantidad de evaluaciones de Uf para obtener los dos resultados: 1
Alejandro Díaz-Caro
Fundamentos de lenguajes de programación cuántica - RIO’15
13 / 13