Protocolos de Informação Quântica

Prévia do material em texto

Protocolos simples de processamento de 
informação quântica
• Teletransporte quântico 
• Codificação densa 
• BB84 
• Algoritmos de Deutsch e Deustch-Jozsa 
• Algoritmo de Bernstein-Vazirani
• Teletransporte quântico 
• Codificação densa 
• BB84 
• Algoritmos de Deutsch e Deustch-Jozsa 
• Algoritmo de Bernstein-Vazirani
Estrutura do tópico
Teletransporte quântico
• Suponha que queremos mandar alguém pra muito longe:
Infelizmente ainda não dá 🙁
Teletransporte quântico
• Suponha que queremos enviar o estado de um qubit:
|ψ⟩ |ψ⟩
Alice Bob
|ψ⟩ = α|0⟩ + β|1⟩
Teletransporte quântico (1993)
|ψ⟩ H
X Z |ψ⟩
|β00⟩
I II III IV V
Lembrete:
|β00⟩ =
1
2
(|00⟩ + |11⟩)
|0⟩ H
|0⟩
|β00⟩
Teletransporte quântico
|ψ⟩ |?⟩
01
Alice Bob
|ψ⟩ H
X Z |ψ⟩
|β00⟩
1
2
(|00⟩ + |11⟩)
01
Teletransporte quântico
Alice Bob
|ψ⟩ H
X Z |ψ⟩
|β00⟩
01
|?⟩
|ψ⟩
|ψ⟩
• Discussão: 
• Teletransporte permite clonar um estado? 
• O que tem de quântico no teletransporte? 
• Teletransporte permite enviar uma mensagem mais rápido que a 
velocidade da luz? 
• Não! Mas e daí, pra que que serve?
Teletransporte quântico
• Isso pode ser feito na prática? 
• Demonstração experimental do conceito: 1998 
• Teletransporte por 600 m usando fibras ópticas: 2004 
• Teletransporte por 143 km no espaço livre: 2012 
• (entre ilhas Canárias!) 
• Recorde (2017) - 1400 km usando teletransporte da Terra para satélite! 
• Já foi feito com fótons, átomos, nuvens atômicas, elétrons e 
circuitos supercondutores. 
• Além de curioso, é um primitivo computacional!
Teletransporte quântico
Minute Physics: https://www.youtube.com/watch?v=DxQK1WDYI_k
https://www.youtube.com/watch?v=DxQK1WDYI_k
Estrutura do tópico
• Teletransporte quântico 
• Codificação densa 
• BB84 
• Algoritmos de Deutsch e Deustch-Jozsa 
• Algoritmo de Bernstein-Vazirani
Codificação densa
• Alice quer enviar uma mensagem para Bob (00, 01, 10 or 11).
Alice Bob
01
• Alice quer enviar uma mensagem para Bob (00, 01, 10 or 11).
Codificação densa
X Z
H
b1
b2
b1
b2
I II III IV
Alice
Bob
|β00⟩
Codificação densa
Mensagem
00
01
10
11
Alice aplica
I = (1 00 1)
X = (0 11 0)
Y = (0 −ii 0 )
Z = (1 00 −1)
Codificação densa
Alice Bob
01
(0 11 0)
Codificação densa
Alice Bob
01
|01⟩
01!
Codificação densa
• Discussão: 
• Agora a gente enviou uma mensagem mais rápido que a luz!? 
• O limite de Holevo diz (informalmente) que n qubits só podem 
carregar n bits clássicos de informação. 
• O protocolo de codificação densa viola esse limite? 
• Não! Mas nesse caso, pra que serve?
Estrutura do tópico
• Teletransporte quântico 
• Codificação densa 
• BB84 
• Algoritmos de Deutsch e Deustch-Jozsa 
• Algoritmo de Bernstein-Vazirani
Criptografia quântica (BB84)
• Alice quer enviar uma mensagem secreta pra Bob. Para isso, 
bastaria eles compartilharem uma one time pad.
0
1
0
0
1
1
1
0
0
1
1
0
1
0
0
1
1
1
0
0
1
1
1
0
0
1
1
1
0
1
0
1
0
⊕
1
1
0
1
0
0
1
1
0
0
0
=
1
0
0
1
1
1
0
1
0
1
0
⊕ =
1
1
0
1
0
0
1
1
0
0
0
Criptografia quântica (BB84)
• Para gerar uma one time pad usando sistemas quânticos eles 
fazem o seguinte:
I - Alice sorteia duas sequências de bits aleatórios, ! e ! .x y
0 1 0 1 1 0 1 0 0 0 1 0 1 0
1 1 1 0 0 1 0 1 0 0 0 1 1 1
x =
y =
Criptografia quântica (BB84)
• Para gerar uma one time pad usando sistemas quânticos eles 
fazem o seguinte:
II - Ela prepara o qubit i em autovetor de ! (se ! ) ou ! (se ! ). 
 Ela escolhe o autovetor de valor +1 (se ! ) ou -1 (se ! ).
Z yi = 0 X yi = 1
xi = 0 xi = 1
0 1 0 1 1 0 1 0 0 0 1 0 1 0
1 1 1 0 0 1 0 1 0 0 0 1 1 1
x =
y =
| + ⟩| − ⟩| + ⟩| 1 ⟩| 1 ⟩| + ⟩| 1 ⟩| + ⟩| 0 ⟩| 0 ⟩| 1 ⟩| + ⟩| − ⟩| + ⟩
Criptografia quântica (BB84)
• Para gerar uma one time pad usando sistemas quânticos eles 
fazem o seguinte:
III - Ela envia o estado pra Bob. Ele escolhe uma sequência aleatória ! e 
mede o qubit i na base de ! (se ! ) ou ! (se ! )
z
Z zi = 0 X zi = 1
1 1 0 0 1 0 0 0 1 1 0 0 1 0z =
| + ⟩| − ⟩| + ⟩| 1 ⟩| 1 ⟩| + ⟩| 1 ⟩| + ⟩| 0 ⟩| 0 ⟩| 1 ⟩| + ⟩| − ⟩| + ⟩
0 1 0 1 1 0 1 0 0 1 1 0 1 1
Z Z Z Z Z Z Z ZX X X X X X
1 1 1 0 0 1 0 1 0 0 0 1 1 1
1 1 0 0 1 0 0 0 1 1 0 0 1 0
1 1 1 0 0 1 0 1 0 0 0 1 1 1
1 1 0 0 1 0 0 0 1 1 0 0 1 0
0 1 0 1 1 0 1 0 0 0 1 0 1 0x = 0 1 1 1 1 1
Criptografia quântica (BB84)
• Para gerar uma one time pad usando sistemas quânticos eles 
fazem o seguinte:
IV - Agora Alice e Bob publicam a lista de bases deles.
y =
z =
0 1 0 1 1 0 1 0 0 1 1 0 1 1
Onde as bases coincidiram, a medida de Bob coincide com a preparação de 
Alice. Esse conjunto de bits serve como one time pad.
0 1 1 1 1 1
Estrutura do tópico
• Teletransporte quântico 
• Codificação densa 
• BB84 
• Algoritmos de Deutsch e Deustch-Jozsa 
• Algoritmo de Bernstein-Vazirani
Funções Booleanas
Definição: função Booleana 
Uma função Booleana é uma função f : {0,1}n → {0,1} .
Funções Booleanas
NOT AND OR
NANDXOR
Funções Booleanas
• Bits clássicos manipulados em circuitos Booleanos:
• Primeiro exemplo de tarefa computacional que vamos ver:
Algoritmos simples: Deutsch
Problema de Deutsch 
Seja uma função Booleana de um bit 
Tarefa: Decidir se f é constante ou não. 
f : {0,1} → {0,1}
Constante
f(0) = f(1)
Não constante
f(1) = f(0) ⊕ 1
Algoritmos simples: Deutsch
Problema de Deutsch 
Seja uma função Booleana de um bit 
Tarefa: Decidir se f é constante ou não. 
f : {0,1} → {0,1}
Constante
f(0) = f(1) = 0
Não constante
f(x) = x ⊕ 1f(0) = f(1) = 1
f(x) = x
Algoritmos simples: Deutsch
Definição: “oráculo” 
Um oráculo associado a uma função f é uma “caixa-preta” 
que implementa a transformação unitária: 
|x⟩|0⟩ → |x⟩|f(x)⟩
|x⟩
|0⟩
Uf
|x⟩
|f(x)⟩
Pergunta: por que não usar 
 a transformação
|x⟩ → |f(x)⟩?
Algoritmos simples: Deutsch
Definição: “oráculo” 
Um oráculo associado a uma função f é uma “caixa-preta” 
que implementa a transformação unitária: 
|x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩
|x⟩
|y⟩
Uf
|x⟩
|y ⊕ f(x)⟩
Algoritmos simples: Deutsch
Definição: “oráculo de fase” 
Um oráculo de fase associado a uma função f é uma “caixa-
preta” que implementa a transformação unitária: 
|x⟩ → (−1) f(x)|x⟩
Algoritmos simples: Deutsch
Problema de Deutsch 
Seja uma função Booleana de um bit 
Tarefa: Decidir se f é constante ou não. 
f : {0,1} → {0,1}
Constante
f(0) = f(1) = 0
Não constante
f(x) = x ⊕ 1f(0) = f(1) = 1
f(x) = x
Algoritmos simples: Deutsch
|0⟩ H Uf H
|0⟩ se f(0) = f(1)
|1⟩ se f(0) ≠ f(1)
Oráculo de fase
• Discussão: 
• Algoritmo quântico resolve o problema com um uso do oráculo. 
• Qualquer circuito clássico precisa de dois usos.
Algoritmos simples: Deutsch
“Deutsch’s algorithm was, by some definition, the first quantum 
algorithm proposed in the mid-1980s. It achieves something 
unimpressive, except for the fact of being possible at all.” 
Scott Aaronson 
Algoritmos simples: Deutsch-Jozsa
Problema de Deutsch-Jozsa 
Seja uma função Booleana de n bits 
Promessa: f é constante ou balanceada. 
Tarefa: Decidir qual. 
f : {0,1}n → {0,1}
Constante
f(x) = 0
Balanceada
f(x) = {0  para metade dos x1  para a outra metade f(x) = 1
Algoritmos simples: Deutsch-Jozsa
|0⟩ H
Uf
H
|0⟩ H H
|0⟩ H H
|0⟩ H H
= |00…0⟩ se f constante.
Output
≠ |00…0⟩ se f balanceada.
I II
• Discussão: 
• Algoritmo quântico resolve o problema com um uso do oráculo. 
• Qualquer algoritmo clássico (determinístico) precisa de 2n-1+1 usos. 
• Separação exponencial! 
• Isso é o melhor que um computador clássico pode fazer? 
• Não! E um algoritmo clássico probabilístico? 
• Qual o interesse de um algoritmo baseado em uma caixa preta? 
• O que esse algoritmo nos ensina sobre computadores quânticos?
Algoritmos simples: Deutsch-Jozsa
Estrutura do tópico
• Teletransporte quântico 
• Codificação densa 
• BB84 
• Algoritmos de Deutsch e Deustch-Jozsa 
• Algoritmo de Bernstein-Vazirani
Algoritmos simples: Bernstein-Vazirani
Problema de Bernstein-Vazirani 
Seja uma função Booleana den bits 
Promessa: f é da forma 
Tarefa: Encontrar a string secreta 
f : {0,1}n → {0,1}
s ∈ {0,1}n
f(x) = s ⋅ x mod 2
Algoritmos simples: Bernstein-Vazirani
|0⟩ H
Uf
H
|0⟩ H H
|0⟩ H H
|0⟩ H H
Output = |s⟩
• Discussão: 
• Novamente, o algoritmo resolve o problema com um uso do oráculo. 
• Problema de busca, não de decisão. 
• Qualquer circuito clássico (determinístico ou probabilístico) precisa de 
n usos.
Algoritmos simples: Bernstein-Vazirani