Download Computación Cuántica y Fundamentos de Lenguajes de

Introducción
a la Computación Cuántica
y
Fundamentos
de Lenguajes de Programación
Primer encuentro
Alejandro Díaz-Caro
LCC – FCEIA – UNR – 18 y 19 de octubre de 2016
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
Computación Cuántica y Fundamentos de Lenguajes de Programación
2 / 23
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
Computación Cuántica y Fundamentos de Lenguajes de Programación
2 / 23
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)
Computación Cuántica y Fundamentos de Lenguajes de Programación
3 / 23
Álgebra
En el pizarrón
I
I
I
Alejandro Díaz-Caro
Espacio de Hilbert
Producto tensorial
Notación bra-ket
Computación Cuántica y Fundamentos de Lenguajes de Programación
4 / 23
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
Computación Cuántica y Fundamentos de Lenguajes de Programación
5 / 23
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
Computación Cuántica y Fundamentos de Lenguajes de Programación
5 / 23
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
Computación Cuántica y Fundamentos de Lenguajes de Programación
5 / 23
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
Computación Cuántica y Fundamentos de Lenguajes de Programación
6 / 23
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
Computación Cuántica y Fundamentos de Lenguajes de Programación
7 / 23
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
Computación Cuántica y Fundamentos de Lenguajes de Programación
8 / 23
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
Computación Cuántica y Fundamentos de Lenguajes de Programación
8 / 23
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
Demostración en el pizarrón
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
8 / 23
Estados de Bell
|x i
H
•
βxy
|y i
Alejandro Díaz-Caro
Entrada
|00i
|01i
|10i
|11i
Salida
β00
β01
β10
β11
=
=
=
=
Computación Cuántica y Fundamentos de Lenguajes de Programación
√1 (|00i
2
√1 (|01i
2
√1 (|00i
2
√1 (|01i
2
+ |11i)
+ |10i)
− |11i)
− |10i)
9 / 23
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
Computación Cuántica y Fundamentos de Lenguajes de Programación
9 / 23
Codificación superdensa
Objetivo:
Transmitir 2 bits clásicos enviando tan sólo 1 qubit
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
10 / 23
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
Computación Cuántica y Fundamentos de Lenguajes de Programación
10 / 23
Teleportación cuántica
Objetivo:
Transmitir 1 qubit enviando 2 bits clásicos
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
11 / 23
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)
Computación Cuántica y Fundamentos de Lenguajes de Programación
11 / 23
Paralelismo cuántico
Primera intuición
f : {0, 1} → {0, 1}
Resultados posibles: 2
Cantidad de evaluaciones para obtenerlos: 2
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
12 / 23
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
Computación Cuántica y Fundamentos de Lenguajes de Programación
12 / 23
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
Computación Cuántica y Fundamentos de Lenguajes de Programación
12 / 23
Algoritmo de Deutsch
Objetivo:
Dado un “oráculo” Uf que implementa la función
f : {0, 1} → {0, 1}, determinar si f es constante o no
Uf |x , y i = |x , y ⊕ f (x )i
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
13 / 23
Algoritmo de Deutsch
Objetivo:
Dado un “oráculo” Uf que implementa la función
f : {0, 1} → {0, 1}, determinar si f es constante o no
Uf |x , y i = |x , y ⊕ f (x )i
|0i
H
H
Uf
|1i
Alejandro Díaz-Caro
H
Computación Cuántica y Fundamentos de Lenguajes de Programación
13 / 23
Algoritmo de Deutsch
Objetivo:
Dado un “oráculo” Uf que implementa la función
f : {0, 1} → {0, 1}, determinar si f es constante o no
Uf |x , y i = |x , y ⊕ f (x )i
|0i
H
H
Uf
|1i
|01i
Alejandro Díaz-Caro
H
Deustch alg.
··· →
Computación Cuántica y Fundamentos de Lenguajes de Programación
13 / 23
Algoritmo de Deutsch
Objetivo:
Dado un “oráculo” Uf que implementa la función
f : {0, 1} → {0, 1}, determinar si f es constante o no
Uf |x , y i = |x , y ⊕ f (x )i
|0i
H
H
Uf
|1i
|01i
Alejandro Díaz-Caro
Deustch alg.
H
· · · → ± |f (0) ⊕ f (1)i
h
|0i−|1i
√
2
Si es
constante
±|0i
h
|0i−|1i
√
2
i
±|1i
h
|0i−|1i
√
2
i
Sino
i
Computación Cuántica y Fundamentos de Lenguajes de Programación
13 / 23
Algoritmo de Deutsch-Jotza
Objetivo:
Dado un “oráculo” Uf que implementa la función
f : {0, 1}n → {0, 1}, determinar si f es constante o balanceada
Uf |x , y i = |x , y ⊕ f (x )i
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
14 / 23
Algoritmo de Deutsch-Jotza
Objetivo:
Dado un “oráculo” Uf que implementa la función
f : {0, 1}n → {0, 1}, determinar si f es constante o balanceada
Uf |x , y i = |x , y ⊕ f (x )i
|0i
H
|0i
H
..
.
|1i
Alejandro Díaz-Caro
H
H
Uf
..
.
H
Computación Cuántica y Fundamentos de Lenguajes de Programación
14 / 23
Algoritmo de Deutsch-Jotza
Objetivo:
Dado un “oráculo” Uf que implementa la función
f : {0, 1}n → {0, 1}, determinar si f es constante o balanceada
Uf |x , y i = |x , y ⊕ f (x )i
|0i
H
|0i
H
..
.
|1i
|0i
⊗n
Alejandro Díaz-Caro
|1i
H
H
Uf
..
.
H
D–J alg.
··· →
Computación Cuántica y Fundamentos de Lenguajes de Programación
14 / 23
Algoritmo de Deutsch-Jotza
Objetivo:
Dado un “oráculo” Uf que implementa la función
f : {0, 1}n → {0, 1}, determinar si f es constante o balanceada
Uf |x , y i = |x , y ⊕ f (x )i
|0i
H
|0i
H
..
.
|1i
⊗n
|1i
..
.
±|0i
⊗n
h
D–J alg.
··· →
Si es
balanceada
Alejandro Díaz-Caro
H
Uf
H
Si es
constante
|0i
H
±|ψi
h
|0i−|1i
√
2
i
|0i−|1i
√
2
i
Computación Cuántica y Fundamentos de Lenguajes de Programación
donde |ψi no
⊗n
incluye |0i
14 / 23
Algoritmo de búsqueda de Grover
Preliminares: Oráculo
Uf |x , y i = |x , y ⊕ f (x )i
Tomar y = |−i =
√1 (|0i
2
− |1i) entonces
1
1
Uf |x , y i = Uf |x i √ (|0i − |1i) = √ (Uf |x , 0i − Uf |x , 1i)
2
2
1
1
= √ (|x , f (x )i − |x , 1 ⊕ f (x )i) = |x i √ (|f (x )i − |1 ⊕ f (x )i)
2
2
f (x )
= (−1) |x , y i
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
15 / 23
Algoritmo de búsqueda de Grover
Preliminares: Oráculo
Uf |x , y i = |x , y ⊕ f (x )i
Tomar y = |−i =
√1 (|0i
2
− |1i) entonces
1
1
Uf |x , y i = Uf |x i √ (|0i − |1i) = √ (Uf |x , 0i − Uf |x , 1i)
2
2
1
1
= √ (|x , f (x )i − |x , 1 ⊕ f (x )i) = |x i √ (|f (x )i − |1 ⊕ f (x )i)
2
2
f (x )
= (−1) |x , y i
Uf no modifica y . . . lo omitimos
Oráculo
U|x i = (−1)f (x ) |x i
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
15 / 23
Algoritmo de búsqueda de Grover
Preliminares: Inversión sobre el promedio
1
|φi = √
2n
Alejandro Díaz-Caro
X
|x i
x ∈{0,1}n
Computación Cuántica y Fundamentos de Lenguajes de Programación
16 / 23
Algoritmo de búsqueda de Grover
Preliminares: Inversión sobre el promedio
 √1 
1
|φi = √
2n
Alejandro Díaz-Caro
2n
X
x ∈{0,1}n


|x i =  ... 
√1
2n
2n
Computación Cuántica y Fundamentos de Lenguajes de Programación
16 / 23
Algoritmo de búsqueda de Grover
Preliminares: Inversión sobre el promedio
 √1 
1
|φi = √
2n
2n
X


|x i =  ... 
x ∈{0,1}n
√1
2n
2n
Inversión sobre el promedio
G = 2|φihφ| − I
2
2n




−1
2
2n
..
.
2
2n
Alejandro Díaz-Caro
2
2n
2
2n
−1
..
.
2
2n
2
2n
2
2n
···
···
···
2
2n



.. 
. 
− 1 2n ×2n
Computación Cuántica y Fundamentos de Lenguajes de Programación
16 / 23
Algoritmo de búsqueda de Grover
Preliminares: Inversión sobre el promedio
 √1 
1
|φi = √
2n
2n
X


|x i =  ... 
√1
2n
x ∈{0,1}n
2n
Inversión sobre el promedio
G = 2|φihφ| − I

2
2n




−1
2
2n
..
.
2
2n
2
2n
2
2n
−1
..
.
2
2n
2
2n
2
2n
···
···
···
2
2n



.. 
. 
− 1 2n ×2n
G

X
ax |x i
x ∈{0,1}n
=
X
(2A − ax )|x i
x ∈{0,1}n
donde A es el promedio de los ax
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
16 / 23
Algoritmo de búsqueda de Grover
El algoritmo
Objetivo:
Localizar el x 0 tal que f (x 0 ) = 1
⊗n
1. Aplicar Hadamard a |0i
2. Aplicar el oráculo U
3. Aplicar la inversión sobre el promedio G
π√
4. Repetir pasos 2 y 3 durante
iteraciones
1
4arcsen(
2n
)
(cálculo del número óptimo de iteraciones, en el apunte, sección 2.3.4)
Explicación paso a paso en el pizarrón
(y ejemplo)
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
17 / 23
Aplicación criptográfica
One-time pad, un método clásico infalible. . .
b1 ⊕ b2
0
1
1
0
Mensaje
cifrado
Mensaje
Alejandro Díaz-Caro
b2
1
0
1
0
Clave
b1
1
1
0
0
z }| {
(b1 ⊕ b2 ) ⊕b2
1
1
0
0
Computación Cuántica y Fundamentos de Lenguajes de Programación
18 / 23
Aplicación criptográfica
One-time pad, un método clásico infalible. . .
b1 ⊕ b2
0
1
1
0
Mensaje
cifrado
Mensaje
Alejandro Díaz-Caro
b2
1
0
1
0
Clave
b1
1
1
0
0
z }| {
(b1 ⊕ b2 ) ⊕b2
1
1
0
0
Computación Cuántica y Fundamentos de Lenguajes de Programación
18 / 23
Aplicación criptográfica
One-time pad, un método clásico infalible. . .
Mensaje
cifrado
b1 ⊕ b2
0
1
1
0
Mensaje
cifrado
Mensaje
original
Mensaje
Alejandro Díaz-Caro
b2
1
0
1
0
Clave
b1
1
1
0
0
Clave
z }| {
(b1 ⊕ b2 ) ⊕b2
1
1
0
0
Computación Cuántica y Fundamentos de Lenguajes de Programación
18 / 23
Aplicación criptográfica
One-time pad, un método clásico infalible. . .
Mensaje
cifrado
Clave
b1
1
1
0
0
b2
1
0
1
0
b1 ⊕ b2
0
1
1
0
z }| {
(b1 ⊕ b2 ) ⊕b2
1
1
0
0
Mensaje
Clave
Mensaje
cifrado
Mensaje
original
Probabilidad de adivinar el mensaje original a partir del cifrado:
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
1
2n
18 / 23
Aplicación criptográfica
One-time pad, un método clásico infalible. . .
Mensaje
cifrado
b1 ⊕ b2
0
1
1
0
Mensaje
cifrado
Mensaje
original
Mensaje
b2
1
0
1
0
Clave
b1
1
1
0
0
Clave
z }| {
(b1 ⊕ b2 ) ⊕b2
1
1
0
0
Probabilidad de adivinar el mensaje original a partir del cifrado: 21n
¡Igual que la posibilidad de adivinar el mensaje original sin ninguna
información extra!
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
18 / 23
Aplicación criptográfica
One-time pad, un método clásico infalible. . .
Entonces, si es tan simple y seguro. . . ¿porqué no es utilizado?
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
19 / 23
Aplicación criptográfica
One-time pad, un método clásico infalible. . .
Entonces, si es tan simple y seguro. . . ¿porqué no es utilizado?
I
I
Largo del mensaje = largo de la clave (para 100 % de seguridad)
Clave de encriptación y desencriptación iguales (y secretas)
I
Alejandro Díaz-Caro
Dificultad para distribuir las claves
Computación Cuántica y Fundamentos de Lenguajes de Programación
19 / 23
Aplicación criptográfica
One-time pad, un método clásico infalible. . .
Entonces, si es tan simple y seguro. . . ¿porqué no es utilizado?
I
I
Largo del mensaje = largo de la clave (para 100 % de seguridad)
Clave de encriptación y desencriptación iguales (y secretas)
I
Dificultad para distribuir las claves
Ahí entra el método BB84: es un método de
distribución de claves de manera segura.
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
19 / 23
Aplicación criptográfica
QKD–BB84
Objetivo: Crear y transmitir una clave de manera segura
Esquema
Base
Codif.
+
{|0i, |1i}
×
{|+i, |−i}
0 = |0i
0 = |−i
1 = |1i
1 = |+i
1. A: secuencia aleatoria de 0s o 1s y elección aleatoria de esquemas para c/bit
2. B: elección aleatoria del esquema de medición para cada bit recibido
3. A: transmite la sucesión de esquemas empleada
4. B: informa en qué casos coincidieron
5. La clave queda definida por los bits donde se usaron los mismos esquemas
6. Intercambio de hashes para verificación
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
20 / 23
Aplicación criptográfica
QKD–BB84: Ejemplo
+:
0 = |0i,
1 = |1i
×:
0 = |−i,
1 = |+i
1. A: secuencia aleatoria de 0s o 1s y elección aleatoria de esquemas para c/bit
2. B: elección aleatoria del esquema de medición para cada bit recibido
3. A: transmite la sucesión de esquemas empleada
4. B: informa en qué casos coincidieron
5. La clave queda definida por los bits donde se usaron los mismos esquemas
6. Intercambio de hashes para verificación
Bits de A
Esquemas de A
Valores de A
Esquemas de B
Valores de B
Alejandro Díaz-Caro
1
×
|+i
+
|0i
0
+
|0i
×
|+i
0
+
|0i
+
|0i
1
×
|+i
×
|+i
0
×
|−i
+
|1i
0
+
|0i
+
|0i
Computación Cuántica y Fundamentos de Lenguajes de Programación
0
×
|−i
×
|−i
1
+
|1i
×
|−i
21 / 23
Aplicación criptográfica
QKD–BB84: Ejemplo
+:
0 = |0i,
1 = |1i
×:
0 = |−i,
1 = |+i
1. A: secuencia aleatoria de 0s o 1s y elección aleatoria de esquemas para c/bit
2. B: elección aleatoria del esquema de medición para cada bit recibido
3. A: transmite la sucesión de esquemas empleada
4. B: informa en qué casos coincidieron
5. La clave queda definida por los bits donde se usaron los mismos esquemas
6. Intercambio de hashes para verificación
Bits de A
Esquemas de A
Valores de A
Esquemas de B
Valores de B
Coincidencias
Alejandro Díaz-Caro
1
×
|+i
+
|0i
0
+
|0i
×
|+i
0
+
|0i
+
|0i
√
1
×
|+i
×
|+i
√
0
×
|−i
+
|1i
0
+
|0i
+
|0i
√
Computación Cuántica y Fundamentos de Lenguajes de Programación
0
×
|−i
×
|−i
√
1
+
|1i
×
|−i
21 / 23
Aplicación criptográfica
QKD–BB84: Ejemplo
+:
0 = |0i,
1 = |1i
×:
0 = |−i,
1 = |+i
1. A: secuencia aleatoria de 0s o 1s y elección aleatoria de esquemas para c/bit
2. B: elección aleatoria del esquema de medición para cada bit recibido
3. A: transmite la sucesión de esquemas empleada
4. B: informa en qué casos coincidieron
5. La clave queda definida por los bits donde se usaron los mismos esquemas
6. Intercambio de hashes para verificación
Bits de A
Esquemas de A
Valores de A
Esquemas de B
Valores de B
Coincidencias
Clave
Alejandro Díaz-Caro
1
×
|+i
+
|0i
0
+
|0i
×
|+i
0
+
|0i
+
|0i
√
1
×
|+i
×
|+i
√
0
1
0
×
|−i
+
|1i
0
+
|0i
+
|0i
√
0
×
|−i
×
|−i
√
0
0
Computación Cuántica y Fundamentos de Lenguajes de Programación
1
+
|1i
×
|−i
21 / 23
Aplicación criptográfica
QKD–BB84: Inviolabilidad (teórica)
Agregamos un espía: C
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
22 / 23
Aplicación criptográfica
QKD–BB84: Inviolabilidad (teórica)
Agregamos un espía: C
I
A envía 0 con esquema ×: |−i
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
22 / 23
Aplicación criptográfica
QKD–BB84: Inviolabilidad (teórica)
Agregamos un espía: C
I
A envía 0 con esquema ×: |−i
I
Si C usa esquema +, el estado pasa a |0i o |1i
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
22 / 23
Aplicación criptográfica
QKD–BB84: Inviolabilidad (teórica)
Agregamos un espía: C
I
A envía 0 con esquema ×: |−i
I
Si C usa esquema +, el estado pasa a |0i o |1i
I
Si B usa esquema ×, obtiene |−i con probabilidad
probabilidad 21
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
1
2
y |+i con
22 / 23
Aplicación criptográfica
QKD–BB84: Inviolabilidad (teórica)
Agregamos un espía: C
I
A envía 0 con esquema ×: |−i
I
Si C usa esquema +, el estado pasa a |0i o |1i
I
Si B usa esquema ×, obtiene |−i con probabilidad
probabilidad 21
I
Mientras más bits se envían, la probabilidad de no detectar a C
decrece exponencialmente:
Bits
Probabilidad
3/4 = 0,75
1 bit
8 bits
(3/4)8 = 0,10011
128 bits (3/4)128 = 1,018 × 10−16
1Mb
(3/4)1024 = 1,155 × 10−128
1MB
(3/4)8192 = 3,17 × 10−1024
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
1
2
y |+i con
22 / 23
Aplicación criptográfica
QKD–BB84 en la vida real
Alejandro Díaz-Caro
Computación Cuántica y Fundamentos de Lenguajes de Programación
23 / 23