introdução a computação quântica

Introducao a Computacao Quantica(para computatas)

Wilson Rosa de Oliveira Jr.

DEInfo-UFRPE

Seminarios doQuantum Computing Group DEInfo-UFRPE

http://www.quantica.deinfo.ufrpe.br

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica May 13, 2014 1 / 82

http://www.quantica.deinfo.ufrpe.br

Prolegomena

Em Computacao Quantica (CQ) testemunhamos a juncao deduas das areas mais importantes na ciencia do sec. XX:

I Mecanica Quantica e Informatica

Esta juncao traz novos objetivos, desafios e potencialidades paraa Informatica bem como novas abordagens para a Fısica exploraro mundo quantico.

Mesmo que seja no momento difıcil prever impactos particularesda CQ sobre a computacao em geral, esperamos que esta juncaoleve a resultados importantes


Mecanica Quantica e...Uma teoria excelente para prever probabilidades de eventosquanticos.

Uma teoria elegante e conceitualmente simples que descreve comprecisao assustadora um amplo espectro de fenomenos naturais:

I Experimentalmente verificadas a 14 ordens de precisao;I Ate o momento nao ha conflito entre o teoricamente previsto e

o verificado experimentalmente

Sem MQ nao podemos explicar propriedades dos superfluidos,funcionamento dos lasers, a substancia da quımica, a estrutura efuncao do DNA, a existencia e comportamento de corpossolidos, cor das estrelas, semicondutores, etc.


Mecanica Quantica trata...Das entidades fundamentais da Fısica – partıculas tais como:

I Protons, eletrons e neutrons (que constituem a materia);I Fotons (que carregam radiacao eletromagnetica) – sao as unicas

partıculas que podemos observar diretamente;I Varias outras “partıculas elementares” que mediam outras

interacoes da Fısica.

Partıculas? Algumas de suas propriedades sao totalmentediscordantes das propriedades do que chamamos de partıculas nonosso mundo usual!

Propriedades? Nao e claro em que sentido estas “partıculas”podem ser ditas possuir propriedades!


Mecanica Quantica

Independente de sua qualidade, do ponto de

vista de explicar fenomenos quanticos, e uma

teoria muito insatisfatoria!

E uma teoria que tem princıpios difıceis de

aceitar e leva a misterios e paradoxos.


Algumas frases famosas

Roger Penrose

“Quantum theory seems to lead to philosophicalstandpoints that many find deeply unsatisfying. At

best, and taking its descriptions at their most literal,it provides us with a very strange view of the world

indeed. At worst, and taking literally theproclamations of some of its most famous

protagonists, it provides us with no view of the worldat all”


Algumas frases famosasRichard Feynman:

“I think it is safe to say that no one understands QuantumMechanics”.

“Nobody knows how it can be like that”.

Bernard Shaw:

“You have nothing to do but mention the quantum theory, andpeople will take your voice for the voice of science, and believe

anything”.


Mas afinal o que MQ nos diz?

Nos diz o que acontece

Mas nao diz porque acontece.

E nao nos diz como acontece.

Nem quanto custa


Compreensao da FQ

Vou lhe dizer o que acontece na Natureza,entretanto jamais pergunte a si mesmo:

“Mas como ela pode ser assim?”Porque senao voce sera sugado para uma escuridao

da qual ninguem conseguiu ate hoje escapar!“Nobody knows how it can be like that”.

Feynman


Exemplo de estranheza: Interferometro de Mach-Zehnder


Uma outra visao da Mecanica QuanticaMQ nao e Fısica no sentido usual – nao e sobremateria ou energia ou onda ou partıculas – e sobreinformacao, probabilidades, amplitudes deprobabilidades e observaveis; e como eles serelacionam entre si.

MQ e o que se obtem quando se generaliza teoria daprobabilidade a permitir numeros negativos. Poderiaate ter sido descoberta pelos matematicos semqualquer motivacao dos experimentos (Aaronson,1997).


Porque Informacao e Computacao Quantica sao taoimportantes?

ICQ pode levar a novas tecnologias que terao impactos amplos eprofundos.

Muitas das ciencias e tecnologias ja estao se aproximando doponto em que precisam isolar, manipular e transmitir partıculas.

Novos conhecimentos sobre os fenomenos e sistemas quanticoscomplexos podem ser gerados.

Criptografia quantica nos leva a um novo patamar de seguranca.

ICQ tem se mostrado ser mais eficiente em situacoesimportante;interessantes.


Por que devemos tentar construir computadores quanticos

”When you try to reach for stars you may notquite get one, but you won’t come with a

handful of mud either.”

Leo Burnett


Informacao x FısicaNorbert Wiener:

I Informacao e informacao, nem materia nem energia.

Ralf Landauer:I Informacao e fısica.

F Deve entao fazer parte da Fısica a Teoria da Informacao e aTeoria da Computacao?

Visao corrente:I Fısica e informacional.

F Deve a mecanica quantica (espacos de Hilbert) fazer parte daInformatica?


CuriosidadeFısica Quantica e uma teoria extremamenteelaborada, cheia de paradoxos e misterios. Leva-seanos para um fısico desenvolver um sentimento.

Alguns teoricos da computacao e matematicos, semqualquer base em FQ tem realizado contri-buicoesfundamentais a teoria da informacao e computacaoquantica!


Outra motivacaoLei de Moore que preve que em 2020 precisaremos de um eletronapenas para amarzenar um bit!


Historico (um pouco)

Richard FeynmanI 1959: Nanotecnologia

F “Ha muito mais espaco la embaixo”

I 1982:F Sistemas classicos nao modelam eficientemente

sistemas quanticosF Sugere construcao de computadores baseados nas leis

da mecanica quantica


HistoricoDavid Deutsch

I 1985: MTQ (Maquina de Turing Quantica)

I 1989: publicou primeiro algoritmo quanticoF Problema de determinar se uma funcao de um bit e

constante ou balanceada.


HistoricoPeter Shor

I 1993: Algoritmo de ShorF Fatoracao de numeros grandes

Tempo de Fatoracaopelo Algoritmo de

Shor

Comprimento donumero a ser

fatorado (bits)

Tempo de Fatoracaopelo Algoritmo

Classico

34s 512 4 dias4.5m 1024 105 anos36m 2048 1017 anos4.8h 4096 1035 anos


Computacao Classica

Mais precisamente: Modelos de Circuitos.

Outros modelos nao considerados aqui:I Maquinas de TuringI λ-CalculoI Funcoes Recursivas, etc.

Mais proximo do computador digital


Computacao Classica

f : {0, 1}m → {0, 1}n

ouf : {0, 1}m → {0, 1}


Computacao Classica


Computacao Classica


Computacao Classica


Computacao Classica

NAND e universal (crossover, fanout)


Computacao Classica - exemplos

Meio Somador (half adder)


Computacao Classica - exemplos

Somador Completo (full adder)


Famılia uniforme de circuitos

E uma sequencia enumeravel de circuitos {Cn}∞n=0

1 Os circuitos Cn tem n entradas e um numero finito de bitssuplementares (ancilla) de saıda.

2 A saıda Cn e denotada por Cn(x) e e definida para todo numerobinario x de no maximo n bits.

3 Se m < n e x tem no maximo m bits entao Cm(x) = Cn(x)

E uma famılia uniforme de circuitos se existe um procedimentoefetivo que computa a descricao de Cn para todo n.A famılia computa f : N → N se Cn(x(n)) = f(x) todo numero x ex(n) e a representacao binaria de no maximo n bits de x.


Computacao Classica ReversıvelCNot


Computacao Classica ReversıvelToffoli

Qualquer funcao f pode ser computada usando apenas Toffoli ecrossover!


Computacao Classica Reversıvel






Quantizacao MatematicaNiK Weaver (Washington University):

“Substituir conjuntos por um espaco de Hilbert apropriado” e“funcoes por mapas lineares”

O conjunto em consideracao passa a ser visto (representado)como uma base (ortonormal).

As funcoes consideradas sao as lineares (ou subclasse destas).

Finitamente dimensional = espaco vetorial


Classical Bits: CbitsBit abstrato: 0 e 1

Representacao como cbit: |0〉 e |1〉I par de vetores ortonormais, e.g:

|0〉 =[10

]e |1〉 =

[01

]Em R2 ou C2

Um estado arbitrario:|ϕ〉 = α|0〉+ β|1〉, onde|α|2 + |β|2 = 1


Classical Bits: Cbits

Formula de Euler: eiθ = cos(θ) + isin(θ)

Forma exponencial: c = ρeiθ

|ψ〉 = cos(θ)|0〉+ eiφsin(θ)|1〉

|+〉 = 1√2|0〉+ 1√

2|1〉 |−〉 = 1√

2|0〉 − 1√

2|1〉


Classical Bits: CbitsQuando precisarmos de mais de um Cbit:Produto tensorial

|0〉 ⊗ |0〉, |0〉 ⊗ |1〉, |1〉 ⊗ |0〉, |1〉 ⊗ |1〉

|0〉|0〉, |0〉|1〉, |1〉|0〉, |1〉|1〉

|00〉, |01〉, |10〉, |11〉


Notacao

|0〉2 |1〉2 |2〉2 |3〉2 |x〉n 0 ≤ x < 2n

|19〉6 = |010011〉 = |0〉|1〉|0〉|0〉|1〉|1〉

= |0〉 ⊗ |1〉 ⊗ |0〉 ⊗ |0〉 ⊗ |1〉 ⊗ |1〉

(y0y1

)(z0z1

)=

y0z0y0z1y1z0y1z1

(x0x1

)(y0y1

)(z0z1

)=

x0y0z0x0y0z1x0y1z0x0y1z1x1y0z0x1y0z1x1y1z0x1y1z1


Operacoes

1|0〉 = |0〉, 1|1〉 = |1〉

X|0〉 = |1〉, X|1〉 = |0〉 (σx)

S|xy〉 = |yx〉

Z|0〉 = |0〉, Z|1〉 = −|1〉 (σz)

C10|x〉|y〉 = (X0)x|x〉|y〉 = |x〉|y ⊕ x〉

X2 = 1⊗X ⊗ 1⊗ 1

S10 =12(1+Z1Z0+X1X0−Y1Y0)

Y = XZ (−iσy)

H = 1√2(X + Z) = 1√

2

(1 11 −1

)


Portas Logicas Quanticas Single-qbitPauli gates

X =

[0 11 0

]; Y =

[0 −ii 0

]; Z =

[1 00 −1

]Hadamard gate

H|0〉 = |0〉+|1〉√2

; H|1〉 = |0〉−|1〉√2

; H = 1√2

[1 11 −1

]Phase gate

P |0〉 = |0〉; P |1〉 = i|1〉; P =

[1 00 i

]; P 2 = Z


Controlled-not gate


Toffoli gate


Computando funcoes classicas


Medicao: obtendo resultadosMedida de um estado |ϕ〉 = α|0〉+ β|1〉

{Mm}p(m) = 〈ϕ|M †

mMm|ϕ〉

I |0〉 com probabilidade |α|2 eI |1〉 com probabilidade |β|2

Completeza ∑m

〈ϕ|M †mMm|ϕ〉 = I

Me = |e〉〈e|


Matrizes Unitarias

A =

[a bc d

]Conjugada Hermitiana; tomando a adjunta:

A† = (A∗)T =

[a∗ b∗

c∗ d∗

]

A e dita ser unitaria se AA† = A†A = I

Usualmente escrevemos unitarias como U .

Exemplo:

XX† =

[0 11 0

] [0 11 0

]=

[1 00 1

]= I


Emaranhamento (entanglement) Quantico

Suponhamos que |ψ〉 = |a〉|b〉. Entao:|ψ〉 = (α|0〉+ β|1〉)(γ|0〉+ δ|1〉)= αγ|00〉+ αδ|01〉+ βγ|10〉+ βδ|11〉

Logo (α = 0 ou δ = 0) e (β = 0 ou γ = 0), o que e um absurdo!

Schrodinger (1935):

”I would not call [entanglement] one but rather the characteristic trait ofquantum mechanics, the one that enforces its entire departure from

classical lines of thought.”Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica May 13, 2014 46 / 82

Estados EmaranhadosConsidere os estados de 2-qubits:

|ψ〉 = 1/√2(|00〉+ |11〉) e |ϕ〉 = 1/

√2(|00〉+ |01〉)

|ϕ〉 e composto do produto tensorial |0〉 ⊗ 1/√2(|0〉+ |1〉)

Medicao do segundo qubit resultara em |0〉 ou |1〉 com umaprobabilidade 1/2 para cada resultado, independente de oprimeiro qubit ser medido ou nao. Medicao do primeiro darasempre |0〉.|ψ〉 nao pode ser decomposto em um produto de dois outrosqubits.

E um estado emaranhado!entrelacado

A medicao do primeira determina completamente o resultado dosegundo.Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica May 13, 2014 47 / 82

C-Not em acao - Bell States

|00〉 C→ 1√2(|00〉+ |11〉)

|01〉 C→ 1√2(|01〉+ |10〉)

|10〉 C→ 1√2(|00〉 − |11〉)

|11〉 C→ 1√2(|01〉 − |10〉)

|000〉 C→ 1√2(|000〉+ |111〉)

|001〉 C→ 1√2(|001〉+ |110〉)

... etc


Emaranhamento (”entanglement”)Um experimento usa luz para provocar umemaranhamento entre dois atomos.

Dois atomos de iterbio para funcionar como qubits.

Excitaram os dois atomos induzindo eletrons a passarpara um estado mais baixo de energia e emitir umfoton.

Os atomos de iterbio sao capazes de emitir dois tiposde fotons, cada um com um comprimento de ondadiferente.

Cada foton esta entrelacado com seu atomo.

Manipulando os fotons emitidos por cada um dosatomos e guiando-os para interagir no interior de umafibra optica, os pesquisadores conseguiram detectar ochoque dos dois e entrelacar os dois atomos.

Entanglement of single-atom quantum bits at a distance D.L. Moehring, P. Maunz, S. Olmschenk, K. C. Younge, D. N.Matsukevich, L.-M. Duan, C. MonroeNature6 September 2007Vol.: 449, 68-71DOI: 10.1038/nature06118


Copia (Cloning)Estados quanticos nao podem ser copiados ou clonados!

Prova: assuma uma transformacao unitaria U tal queU |a〉|0〉 = |a〉|a〉Sejam |a〉 e |b〉 estados ortogonais e U |a〉|0〉 = |a〉|a〉 eU |b〉|0〉 = |b〉|b〉.Considere agora |c〉 = 1/

√2(|a〉+ |b〉).

Por linearidade,U |c〉|0〉 = 1/

√2(U |a〉|0〉+ U |b〉|0〉) = 1/

√2(|a〉|a〉+ |b〉|b〉)

Mas se U e uma transformacao de copia:

U |c〉|0〉 = |c〉|c〉 = 1/√2(|a〉+ |b〉)⊗ 1/

√2(|a〉+ |b〉)

= 1/2(|a〉|a〉+ |a〉|b〉+ |b〉|a〉+ |b〉|b〉)

Contradicao!


Probabilidade?

f : {0, 1} → {0, 1}

P01 = P10 = 0, P00 = P11 = 1 computa identidade

P01 = P10 = 1, P00 = P11 = 0 computa um NOT

P01 = P10 = P00 = P11 = 0.5 resulta 0 e 1 aleatoriamente


Probabilidade?Suponha que ao compor duas destas maquinas obtemos umamaquina inversora de 0s e 1s.

Como pode? Nao me pergunto como, mas posso mostrar que...


Probabilidade?


Probabilidade?


Probabilidade Quantica


CuriosidadeSimulando um Computador Quantico

I 50 qubits

I Especificar um estado generico |ψ〉 requer

I 250 ≈ 1015 numeros complexos com 2× 128 bitsou seja

I 32× 1015 = 32000 terabytes

I Dinamica requer a manipulacao de matrizes 250 × 250


Curiosidade51 qubits

I Requer o dobro de memoria

100 qubitsI Especificar um estado generico |ψ〉 requer 480 Gbytes em cada

milımetro quadrado da superfıcie da Terra!


Exemplo: Problema de DeutschDeterminar se uma funcao f dada e constante ou balanceada.

Dada uma caixa preta computando f : {0, 1} → {0, 1}Classicamente precisamos avaliar ambos f(0) e f(1).

Quanticamente precisamos apenas avaliar f uma unica vez!


Esquematicamente...

Calculemos a amplitude de sair 0 dado 0:

C1 i/√2 x (−1)f(0) x i/

√2 = −1/2 x (−1)f(0)

C2 1/√2 x (−1)f(1) x 1/

√2 = 1/2 x (−1)f(1)

soma 12((−1)f(1) − (−1)f(0))


Pondo informacao na fase

f(x) = 0:I |x〉(|0〉 − |1〉)→ |x〉(|0〉 − |1〉)

f(x) = 1:I |x〉(|0〉 − |1〉)→ |x〉(|1〉 − |0〉) = −|x〉(|0〉 − |1〉)

|x〉(|0〉 − |1〉)→ (−1)f(x)|x〉(|0〉 − |1〉)

|x〉 → (−1)f(x)|x〉


Algoritmo Quantico para o problema de Deutsch

f constante ⇒ todas as amplitudes em |0〉f balanceada ⇒ todas as amplitudes em |1〉Problema de pesquisa:

I O que faz computadores quanticos serem tao poderosos?


Beam us up Scotty!

How do i do that?

Here’s is the code.


Circuito Teleportacao


Os delates... [1]

Alice que enviar a Bob o estado:

|ϕ〉 = α|0〉+ β|1〉

Para tal, qdo estao juntos criam o estado emaranhado:

|β00〉 =|00〉+ |11〉√

2

Bob vai para o lugar dele...


Os detalhes... [2]

O estado geral do ”sistema” e:

|ψ〉 = |ϕ〉 ⊗ |β00〉 = (α|0〉+ β|1〉)⊗ |00〉+ |11〉√2

=α(|000〉+ |011〉) + β(|100〉+ |111〉)√

2

Aplicando CNOT ao qubit de Alice :=

|ψ′〉 = UX |ψ〉

=α(UX |000〉+ UX |011〉) + β(UX |100〉+ UX |111〉)√

2

=α(|000〉+ |011〉) + β(|110〉+ |101〉)√

2Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica May 13, 2014 65 / 82

Os detalhes... [3]

Aplicando Hadamard ao primeiro qubit de Alice:

|ψ′〉 = α|0〉(|00〉+ |11〉)√2

+β|1〉(|10〉+ |01〉)√

2

resulta em:

|ψ′′〉 = H|ψ′〉 = αH|0〉(|00〉+ |11〉)√2

+βH|1〉(|10〉+ |11〉)√

2

= α(|0〉+ |1〉√

2)|00〉+ |11〉√

2+ β(

|0〉 − |1〉√2

)|10〉+ |01〉√

2

Nao esqueca que Bob esta com o terceiro qubit!


Os detalhes... [4]

Alice mede seu par de qubits, onde o sistema reescrito esta em:|ψ′′〉= 1

2[|00〉(α|0〉+β|1〉)+|01〉(α|1〉+β|0〉)+|10〉(α|0〉−β|1〉)+|11〉(α|1〉−β|0〉)]

e Bob pode aplicar (resp.) I, X, Z e ZX ao resultado para obtero estado original.

Como saber o que aplicar?


Os detalhes... [5]

Alice telefona por um canal classico a Bob informando oresultado de sua medicao!


Busca desestruturada de GroverDada uma lista desestruturada de tamanho N e uma proposicaoP, encontre um x tal que P(x) seja verdadeiro.

Seja UP a porta quantica que implementa a funcao booleanaP(x) e n tal que 2n ≥ N .

UP : |x, 0〉 → |x, P (x)〉

UP operando na superposicao do todos os estados da base da:

1√2n

2n−1∑i=0

|x, P (x)〉

Se existe unico estado tal que P (x) = 1, a pobabilidade de obtereste resultado apos medicao e apenas 1/

√2n.

Precisamos aumentar isto!!!Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica May 13, 2014 69 / 82

Primalidade e FatoracaoProblema da primalidade:

I Dado: um inteiro n > 1I Descobrir: se n e primo ou compostoI Algoritmo: AKS (2002)

Problema da fatoracao:I Dado: um inteiro n compostoI Descobrir: um fator de nI Algoritmo: Shor (1994)


Algoritmo de Shor

Para fatorar N encontre x coprimo com N.

Usa computador quantico para encontrar r tal que xr = 1modN .

Se r e par, entao mdc(xr/2 + 1, xr/2 − 1, N) e um fator de Nque podemos encontrar com o algoritmo de Euclides.


Algoritmo de Shor (exemplo)

Para fatorar N = 1295 seja x coprimo com N, e.g., x = 6.

Use um computador quantico para encontrar r tal que6r = 1mod1295. r = 4.

Se r e par, entaomdc(64/2 + 1, 64/2 − 1, 1295) = mdc(35, 37, 1295) e um fator deN que podemos encontrar com o algoritmo de Euclides. 1295 =5 x 7 x 37.


Algoritmo de Shor: especificacaoRecebe:

I um inteiro n composto, ımparI que nao uma potencia de primoI (n tem pelo menos 2 divisores primos)

Devolve:I um fator de n, com probabilidade ≥ 1/2.


Algoritmo de Shor: caracterısticasIdeia:

I transforma problema da fatoracao em:busca do perıodo de uma funcao.

Consumo de tempo:I polinomial em logn.

Observacao:I um unico passo quantico!


Algoritmo de Shor

Shor(n)

1 x← rand {2, ..., n− 1}2 d← mdc(x, n)

3 se d > 1

4 entao devolva d

5 r ← ordem(x, n), menor a > 0 tal que xa ≡ 1(modn)

6 se r e ımpar ou xr/2 ≡ −1(modn)7 entao FALHOU!

8 senao devolva mdc(xr/2 − 1, n)


ConclusoesQC possui grande potencial

I Capacidade de um paralelismo exponencialI Capacidade exponencial de armazenamento de dados em um

espaco extremamente pequeno

E possıvel utilizar:I portas logicas (quanticas)I circuitos logicos (quanticos)


ConclusoesNao eciste:

I PCI InstrucoesI Barramento

Possui uma arquitetura completamente nova!!


ConclusoesSao necessarios aperfeicoamentos

I Nos instrumentos de inducao das transformacoes (RMN, laser)I Necessidade de controle dos erros (melhorar as formas de

isolamento e interacao com o sistema quantico)


ConclusoesTalvez a criacao de um PC Quantico seja muito complexa

Solucao: utilizar a computacao quantica em componentes de umPC


Meu interesse atualRAMs quanticas

Programmable gates arrays

Redes Neurais Quanticas (sem pesos)

Quantum Computing + Chaos ==> resolvendo problemasNP-completos em tempo polinomial.

Modelos discretos da geometria differencial (gravidade quantica)==> Hypercomputacao(?)

Computacao Relativıstica ==> Hypercomputacao!


References I

Noson S. Yanofsky; Mirco A. Mannucci, Quantum Computing forComputer Scientists, Cambridge University Press, 2008, ISBN978-0-521-87996-5.

David McMahon, Quantum Computing Explained,Wiley-Interscience, Hoboken, New Jersey, USA, 2008, ISBN978-0-470-09699-4.

N. David Mermin, Quantum Computer Science - AnIntroduction, Cambridge University Press, New York, USA, 2007,ISBN 978-0-521-87658-2.

Alexei Yu. Kitaev, Alexander H. Shen e Mikhail N. Vyalyi,Classical and Quantum Computation.


Obrigado por sua atencao!


Documents

introdução a computação quântica