Computação quântica, estamos preparados?De conceitos a implicações futuras

Fernando Vasconcelos Mendesfernandovm@gmail.comPh.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

1985

• “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

Bits clássicos

1985

• 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 :-))

Qubtis – os bits quânticos

• Equivalente quântico ao bit clássico

• Um qubit pode assumir os valores 0 ou 1, nqubits 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?

Podemos copiar uma informação quântica 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!

• 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} é balanceadaou constante

• Um soluçao clássica e determinística requer, no pior caso, 2n−1 + 1avaliaçõ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

AlgoritmoClássico

512 34s 4 dias

1024 4.5m 105 anos

2048 36m 1017 anos

4096 4,8h 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/nistir-8105/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

• http://www.idquantique.com/

• SeQureNet

• http://www.sequrenet.com/

• MagiQ

• 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

fernandovm@gmail.com