quântico - QCon São Paulo

Computação quântica, estamos
preparados?
De conceitos a implicações futuras
Fernando Vasconcelos Mendes
[email protected]
Ph.D., Software Architect, BCP, MCP, MCAD, MCSD, ITIL
Agenda
Contextualização
histórica
Fenômenos
quânticos
Algoritmos
quânticos
Protocolos
quânticos
Implicações
futuras
Mas, antes de começarmos ...
Uma breve nota sobre otimização…
Função Rastrigin
Uma breve nota sobre o que não é…
•
•
•
O uso inapropriado de alguns aspectos incompreensíveis da mecânica
quântica já era uma preocupação de Einstein.
Somos livres para exercer nossos pensamentos e direcionar nossas crenças,
e sejam quais forem estas, independente de uma realidade objetiva
consensuada, elas são capazes de provocar mudanças concretas em
nosso comportamento.
De todo modo, do ponto de vista científico, uma série de “doutrinas” usam
indevidamente o termo “quântica”, tais como:
✓ Empresa quântica
✓ Terapia quântica
✓ Cura quântica
✓ Saúde quântica
✓ Consciência quântica
✓ “Etc.” quântica
Contextualização histórica e
fundamentos...
Considerações de Richard Feynman
Pode a física ser simulada por um computador?
•
•
“. . . a possibilidade que existe é a de ser uma
simulação exata, que o computador irá fazer
exatamente o mesmo que a natureza.”
“... o número de componentes do computador
requeridos para simular um sistema físico arbitrário é
apenas proporcional ao volume do espaço-tempo
do sistema físico.”
Conclusão
•
“A natureza não é clássica, poxa, e se você quer
fazer uma simulação da natureza, é melhor fazê-lo
com a mecânica quântica, e pelo amor de Deus, é
um problema maravilhoso, pois não parece tão
fácil.”
1982
Considerações de David Deutsch
•
•
“Máquinas de computar que se assemelham à
um computador quântico universal poderiam,
em princípio, ser construídas e teriam muitas
propriedades notáveis não reproduzíveis por
uma máquina de Turing.”
Fundamentou a noção de computação
quântica
•
•
•
Primeira versão da máquina de Turing Quântica
Formulação de portas quânticas e circuitos
quânticos
Primeiro algoritmo quântico
1985
Bits clássicos
•
•
•
Unidade mínima de informação para
armazenamento ou processamento
Um bit pode assumir os valores 0 ou 1, n bits
podem representar 2n valores clássicos – um
por vez
Fisicamente representado por um sistema de
2-níveis:
•
•
•
Estado de um transistor
Magnetização da superfície de um disco rígido
Uma moeda :-))
1985
Qubtis – os bits quânticos
•
•
•
Equivalente quântico ao bit clássico
Um qubit pode assumir os valores 0 ou 1, n
qubits podem representar 2n valores
clássicos – ao mesmo tempo!
Fisicamente representado por um sistema
quântico de 2-níveis:
•
•
•
Polarização de um fóton
Alinhamento do spin nuclear em um campo magnético uniforme
Os estados (fundamental e excitado) de um elétron orbitando ao redor
de um átomo
Bits versus Qubtis
Alguns fenômenos quânticos...
Não-clonagem
Podemos copiar uma informação clássica arbitrária?
•
Intuitivamente pode-se facilmente dizer que sim, como
exemplo tem-se:
•
Xerox, faz, etc. (São cópias perfeitas?)
•
Cópia de arquivos digitais!
Podemos copiar uma informação quântica arbitrária?
•
Intuitivamente.. ops, stop! A mecânica quântica não é
intuitiva.
•
A resposta é NÃO!
Superposição
Superposição
Superposição
Superposição
Entrelaçamento
“I cannot seriously believe in it
because the theory cannot be
reconciled with the idea that
physics should represent a reality in
time and space, free from spooky
actions at a distance.”
Entrelaçamento
“Não existe uma analogia clássica para o entrelaçamento, mas você
pode pensar em algo como:”
Alguns algoritmos/protocolos
quânticos...
Algoritmo de Deutsch-Jozsa
•
Determinar se uma função f : {0, 1}n → {0, 1} é balanceada
ou constante
•
Um soluçao clássica e determinística requer, no pior caso, 2n−1 + 1
avaliações de f.
•
A solução quântica requer apenas 1 avaliação de f, independente
de n. Exponencialmente mais eficiente!
Algoritmo de Grover
•
•
•
Busca em uma base de dados desordenada
Complexidade para algoritmos clássicos: O(N)
Complexidade para o algoritmo quântico de Grover: O(√N)
Pausa para uma reflexão...
•
Os sistemas de criptografia clássicos são seguros?
•
•
•
Sistema simétrico
Sistema assimétrico
O que os confere segurança?
•
Barreiras tecnológicas!
Algoritmo de Shor
•
•
•
Logaritmo discreto e fatoração de números inteiros
Complexidade para o algoritmo clássico: O(e(log N)1/3(log log N)2/3).
Complexidade para o algoritmo quântico de Shor: O((log N)3).
Implicações ...
Constatações & Implicações ...
•
•
“The computer scientist Donald Knuth has estimated
that the factorization of a 250-digit number, using the
most efficient known methods, would take over a
million years on a network of a million computers.”
Comparativo (aproximado):
Entrada
(#bits)
Algoritmo de
Shor
Algoritmo
Clássico
512
1024
2048
4096
34s
4.5m
36m
4,8h
4 dias
105 anos
1017 anos
1035 anos
Constatações & Implicações ...
Constatações & Implicações ...
•
Report on Post-Quantum Cryptography (2016)
•
•
•
“If large-scale quantum computers are ever built, they will
be able to break many of the public-key cryptosystems
currently in use. This would seriously compromise the
confidentiality and integrity of digital communications on
the Internet and elsewhere.”
http://csrc.nist.gov/publications/drafts/nistir8105/nistir_8105_draft.pdf
Suite B Cryptography – Cryptography Today :
•
•
“… Our ultimate goal is to provide cost effective security
against a potential quantum computer… We look forward
to your continued support as we work together to improve
information security for National Security customers against
the threat of a quantum computer being developed.”
https://www.nsa.gov/ia/programs/suiteb_cryptography/
Protocolo BB84
• QDK – Distribuição Quântica de chaves
•
•
Alice gera um bit aleatório (0 ou 1)
Alice codifica o bit usando uma das bases:
{|0>, |1>} ou {|+>, |->}
•
•
•
•
•
Alice manda o qubit para Bob
Bob seleciona, aleatoriamente, uma das bases para fazer a
medição
Depois de uma dada quantidade de transmissão, Alice e Bob
anunciam suas bases.
Eles descartam as posições inadequadas e executam um
procedimento de amplificação de privacidade.
Uma nova chave é gerada!
Protocolo BB84
Protocolo BB84 – Aplicações comerciais
•
ID Quantique
•
•
SeQureNet
•
•
http://www.sequrenet.com/
MagiQ
•
•
http://www.idquantique.com/
http://www.magiqtech.com/
Quintessence Labs
•
http://www.quintessencelabs.com/
Uma nova reflexão...
•
Já temos um computador quântico?
•
Seria importante construirmos um computador quântico?
•
Qual a importância do poder computacional?
O método científico
Cenário atual
Cenário atual
•
Google says its quantum computer is 100 million times faster than PC
•
•
•
•
1s -> 3,17 anos (512 qubits)
http://arxiv.org/abs/1512.02206
http://www.theregister.co.uk/2015/12/09/googles_quantum_computer/
Empresas trabalhando nas pesquisas de computadores quânticos:
Conclusões
•
•
A computação quântica traz consigo não só as estranhezas da
mecânica quântica mas também sua elegância matemática e
possibilidades inteiramente novas de computar.
Tão, ou mais, importante quanto as contribuições à uma
estratégia de comunicação segura definitiva, é o potencial
incremento do poder computacional capaz de provocar uma
revolução (tecnológica) sem precedentes!
Dúvidas!?
Fernando Vasconcelos Mendes
[email protected]