Introdu o Computa o Qu ntica · MQ n~ao e F sica no sentido usual { n~ao e sobre mat eria ou...

Post on 06-Oct-2020

10 views 0 download

Transcript of Introdu o Computa o Qu ntica · MQ n~ao e F sica no sentido usual { n~ao e sobre mat eria ou...

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 April 29, 2015 1 / 82

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 2 / 82

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.

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 3 / 82

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!

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 4 / 82

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.

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 5 / 82

Algumas frases famosas

Roger Penrose

“Quantum theory seems to lead to

philosophical standpoints 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 the proclamations

of some of its most famous protagonists, it

provides us with no view of the world at all”

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 6 / 82

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”.

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 7 / 82

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.

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 8 / 82

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 9 / 82

Exemplo de estranheza: Interferometro de Mach-Zehnder

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 10 / 82

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).

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 11 / 82

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 situacoesimportantes/interessantes.

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 12 / 82

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 13 / 82

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?

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 14 / 82

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 contribuicoesfundamentais a teoria da informacao e computacaoquantica!

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 15 / 82

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 16 / 82

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 17 / 82

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.

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 18 / 82

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 19 / 82

Computacao Classica

Mais precisamente: Modelos de Circuitos.

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

Mais proximo do computador digital

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 20 / 82

Computacao Classica

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

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 21 / 82

Computacao Classica

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 22 / 82

Computacao Classica

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 23 / 82

Computacao Classica

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 24 / 82

Computacao Classica

NAND e universal (crossover, fanout)

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 25 / 82

Computacao Classica - exemplos

Meio Somador (half adder)

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 26 / 82

Computacao Classica - exemplos

Somador Completo (full adder)

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 27 / 82

Famılia consistente 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.

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 28 / 82

Computacao Classica ReversıvelCNot

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 29 / 82

Computacao Classica ReversıvelToffoli

Qualquer funcao f pode ser computada usando apenas Toffoli ecrossover!

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 30 / 82

Computacao Classica Reversıvel

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 31 / 82

Computacao Classica Reversıvel

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 32 / 82

Computacao Classica Reversıvel

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 33 / 82

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 34 / 82

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 35 / 82

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〉

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 36 / 82

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〉

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 37 / 82

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 38 / 82

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

)

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 39 / 82

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 40 / 82

Controlled-not gate

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 41 / 82

Toffoli gate

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 42 / 82

Computando funcoes classicas

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 43 / 82

Medicao: obetendo 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|

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 44 / 82

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 45 / 82

Emaranhamento (entanglement) Quantico

Suponhamos que |ψ〉 = |a〉|b〉. Entao:|ψ〉 = (α|0〉+ β|1〉)(γ|0〉+ δ|1〉)= αγ|00〉+ βγ|10〉+ αδ|01〉+ βδ|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 April 29, 2015 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!

A medicao do primeira determina completamente o resultado dosegundo.

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 48 / 82

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 49 / 82

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!

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 50 / 82

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 51 / 82

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...

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 52 / 82

Probabilidade?

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 53 / 82

Probabilidade?

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 54 / 82

Probabilidade Quantica

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 55 / 82

CuriosidadeSimulando um Computador Quantico

I 50 qubits

I Especificar um estado generico |ψ〉 requer

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

I 32 x 1015 = 32000 terabytes

I Dinamica requer a manipulacao de matrizes 250 x 250

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 56 / 82

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!

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 57 / 82

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!

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 58 / 82

Esquematicamente...

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 59 / 82

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〉

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 60 / 82

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?

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 61 / 82

Beam us up Scotty!

How do i do that?

Here’s is the code.

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 62 / 82

Circuito Teleportacao

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 63 / 82

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...

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 64 / 82

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 April 29, 2015 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!

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 66 / 82

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.

Com saber o que aplicar?

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 67 / 82

Os detalhes... [5]

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

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 68 / 82

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

Seja UP a porta quantica que implementa a funcao booleana P(x) en tal que 2n ≥ N .

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

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

1/√2nN−1∑i=0

|x, P (x)〉

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

√2n

.

Precisamos aumentar isto!!!Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 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)

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 70 / 82

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.

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 71 / 82

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 = 5x7x37.

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 72 / 82

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.

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 73 / 82

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!

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 74 / 82

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)

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 75 / 82

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)

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 76 / 82

ConclusoesNao eciste:

I PCI InstrucoesI Barramento

Possui uma arquitetura completamente nova!!

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 77 / 82

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)

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 78 / 82

ConclusoesTalvez a criacao de um PC Quantico seja muito complexa

Solucao: utilizar a computacao quantica em componentes de umPC

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 79 / 82

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!

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 80 / 82

References I

(por ordem de relevancia)

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.

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 81 / 82

Obrigado por sua atencao!

Wilson Rosa (DEInfo-UFRPE) Introducao a Computacao Quantica April 29, 2015 82 / 82