livro_cq_ver_2.pdf

Notas em Matemtica Aplicada 8

Editado por

Eliana X.L. de AndradeUniversidade Estadual Paulista - UNESP

So Jos do Rio Preto, SP, Brasil

Rubens SampaioPontifcia Universidade Catlica do Rio de Janeiro

Rio de janeiro, RJ, Brasil

Geraldo N. SilvaUniversidade Estadual Paulista - UNESP

So Jos do Rio Preto, SP, Brasil

Sociedade Brasileira de Matemtica Aplicada e Computacional

Notas em Matemtica Aplicada

1. Restaurao de Imagens com Aplicaes em Biologia e Engenharia

Geraldo Cidade, Antnio Silva Neto e Nilson Costa Roberty

2. Fundamentos, Potencialidades e Aplicaes de Algoritmos Evolutivos

Leandro dos Santos Coelho

3. Modelos Matemticos e Mtodos Numricos em guas Subterrneas

Edson Wendlander

4. Mtodos Numricos para Equaes Diferenciais Parciais

Maria Cristina de Castro Cunha e Maria Amlia Novais Schleicher

5. Modelagem em Biomatematica

Joyce da Silva Bevilacqua, Marat Rafikov e Cludia de Lello CourtoukeGuedes

6. Mtodos de Otimizao Randmica: algoritmos genticos e simulatedannealing"

Sezimria F. Pereira Saramago

7. Matemtica Aplicada Fisiologia e Epidemiologia

H.M. Yang, R. Sampaio e A. Sri Ranga

iii

8. Uma Introduo Computao Quntica

Renato Portugal, Carlile Campos Lavor, Luiz MarianoCarvalho e Nelson Maculan

9. Modelos Matemticos baseados em automatas celulares paraGeoprocessamento

Marilton Aguiar, Fbia Amorim da Costa, Graaliz Pereira Dimuro eAntnio Carlos da Rocha Costa

10. Computabilidade: os limites da Computao

Regivan Santiago e Benjamn Ren Callejas

11. Modelagem Multiescala em Materiais e Estruturas

Fernando Rochinha

12. Modelagem em Biomatemtica

1 - Modelagem de distribuio de espcies"

2 - Redes complexas e aplicaes nas Cincias"

3 - Possveis nveis de complexidade na modelagem de sistemas biolgicos"

Coraci Malta, 1 - Rafael Luis Fonseca, 2 - Jose Carlos Mombach e 3 -Henrique Lenzi

13. A lgica na construo dos argumentos

Angela Cruz

UMA INTRODUO COMPUTAOQUNTICA

2a edio

Renato Portugal - LNCC

[email protected]

Carlile Campos Lavor - UNICAMP

[email protected]

Luiz Mariano Carvalho - UERJ

[email protected]

Nelson Maculan - UFRJ

[email protected]

Sociedade Brasileira de Matemtica Aplicada e Computacional

Vitria - ES, Brasil2005

vCoordenao Editorial: Geraldo Nunes Silva

Coordenao Editorial da Srie: Geraldo Nunes Silva

Editora: SBMAC

Impresso na Grfica:

Capa: Matheus Botossi Trindade

Patrocnio: SBMAC

Copyright c2005 by Renato Portugal, Carlile Campos Lavor, Luiz MarianoCarvalho and Nelson MaculanDireitos reservados, 2005 pela SBMAC. A publicao nesta srie no impede o au-tor de publicar parte ou a totalidade da obra por outra editora, em qualquer meio,desde que faa citao edio original.

Catalogao elaborada pela Biblioteca do IBILCE/UNESP.

Portugal, RenatoUma Introduo Computao Quntica - Vitria - ES : SBMAC, 2005(?), 00 p. - (Notas em Matemtica Aplicada; 8)

ISBN

1. Computao Quntica. 2. Algoritmos Qunticos. 3. Circuitos Qunticos.I. Portugal, Renato. II. Lavor, Carlile Campos.III. Carvalho, Luiz Mariano. IV. Maculan, Nelson. V. Ttulo. VI. Srie

AMS 94A08/68U10

Prefcio

Esta uma nova edio em que acrescentamos novos exerccios e fizemos algumascorrees.

Apresentamos um estudo introdutrio computao quntica. Esse um do-mnio recente, uma combinao de trs reas bem conhecidas: matemtica, fsica ecomputao.

Vamos nos concentrar em aspectos matemticos da computao quntica. Ape-sar de desejvel, nenhum conhecimento prvio sobre fsica ou computao neces-srio. Quanto matemtica, a principal exigncia um curso bsico de lgebralinear.

O texto est dividido em quatro captulos. No Captulo 1, fazemos uma breveexposio sobre computadores clssicos (Seo 1.1) e apresentamos os conceitosbsicos usados no texto (Seo 1.2). Comparamos, rapidamente, computadoresclssicos e qunticos na Seo 1.1 (essa discusso ser mais til para aqueles comalgum conhecimento de computao). A Seo 1.2 fundamental para todo o livroe dever ser consultada constantemente.

No Captulo 2, descrevemos alguns dos circuitos qunticos que sero utilizadosnos captulos seguintes. Nos Captulos 3 e 4, cremos, est a nossa principal contri-buio: produzir um texto em portugus que estimule o estudante de graduao, emqualquer rea de cincias exatas, a estudar o assunto. Nesses captulos, descrevemosos dois algoritmos mais divulgados em computao quntica: o algoritmo de Grover(Captulo 3) e o algoritmo de Shor (Captulo 4). O quarto captulo denso e, porisso, exigir uma leitura mais atenta. No entanto, o texto tem todas as definies ereferncias necessrias para a compreenso desse algoritmo fundamental.

Existem timos livros sobre o assunto em lngua inglesa (veja a bibliografia). Omais famoso, j um clssico, o livro de Michael A. Nielsen e Isaac L. Chuang [16].

Para futuras edies melhoradas de nosso trabalho, gostaramos de receber cr-ticas e sugestes por parte dos leitores.

Finalmente, agradecemos o apoio da Sociedade Brasileira de Matemtica Apli-cada e Computacional (SBMAC), do Programa Institutos do Milnio (InformaoQuntica), da FAPERJ, do CNPq e, em particular, ao Prof. Rubens Sampaio, peloincentivo.

Os Autores

Rio de Janeiro, 11 de agosto de 2005.

vi

Contedo

1 Conceitos Bsicos 21.1 O Computador Clssico . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 O Computador Quntico . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.1 O bit quntico (q-bit) . . . . . . . . . . . . . . . . . . . . . . 51.2.2 Produto tensorial . . . . . . . . . . . . . . . . . . . . . . . . . 91.2.3 Produtos interno e externo . . . . . . . . . . . . . . . . . . . 12

2 Circuitos Qunticos 152.1 Notao e Convenes . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2 Porta NOT Quntica . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3 Porta Hadamard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.4 Porta de Fase ou Porta S . . . . . . . . . . . . . . . . . . . . . . . . 182.5 Porta pi/8 ou Porta T . . . . . . . . . . . . . . . . . . . . . . . . . . 182.6 Porta CNOT Quntica . . . . . . . . . . . . . . . . . . . . . . . . . . 192.7 Porta Toffoli Quntica . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Algoritmo de Grover 233.1 Introduo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2 Operadores do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . 243.3 Custo Computacional do Algoritmo . . . . . . . . . . . . . . . . . . 333.4 Exemplo: N=8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.5 Circuitos Qunticos para o Operador G . . . . . . . . . . . . . . . . 40

3.5.1 Circuito quntico para o operador Uf . . . . . . . . . . . . . 413.5.2 Circuito quntico para o operador 2|| I . . . . . . . . 41

4 Algoritmo de Shor 434.1 Reduo da Fatorao ao Clculo da Ordem . . . . . . . . . . . . . . 434.2 Algoritmo Quntico para o Clculo de Ordem . . . . . . . . . . . . . 454.3 A Transformada de Fourier Quntica Discreta . . . . . . . . . . . . 484.4 Generalizao por meio de um Exemplo . . . . . . . . . . . . . . . . 514.5 Transformada de Fourier em termos de Portas Universais . . . . . . 55

Bibliografia 61

Captulo 1

Conceitos Bsicos

1.1 O Computador Clssico

Um computador clssico pode ser descrito de forma bastante genrica como umamquina que l um certo conjunto de dados, codificado em zeros e uns, executaclculos e gera uma sada tambm codificada em zeros e uns. Zeros e uns so estadosque podem ser representados fisicamente. No caso dos computadores clssicos,atravs do potencial eltrico: 0 um estado de baixo potencial eltrico e 1 umestado de alto potencial eltrico.

Zeros e uns formam um nmero binrio que pode ser convertido para a basedecimal. Pensemos, ento, num computador como um dispositivo que calcula umafuno f : {0, . . . , N 1} {0, . . . , N 1}, onde N = 2n (n o nmero de bitsusados na memria do computador). Sem perda de generalidade, consideremos queo domnio e a imagem de f so do mesmo tamanho. A cada conjunto de n bitsde entrada, corresponde um nico conjunto de n bits de sada, o que caracterizaf como uma funo. Representamos o processo de clculo na Figura 1.1, onde esquerda, temos os bits de entrada e direita, os de sada (o processo de clculoocorre da esquerda para a direita).

Em geral, f descrita por blocos elementares que podem ser implementados fisi-camente por transistores e outros componentes eletrnicos. Os blocos so as portaslgicas AND, OR e NOT, conhecidas como portas universais (na verdade, bastaapenas a porta NOT e uma das duas outras portas, OR ou AND). Por exemplo, umexemplo de circuito que realiza a soma em aritmtica mdulo 2 de dois nmeros,cada um com um bit, apresentado na Figura 1.2. As entradas possveis so 00,01, 10 ou 11. As entradas so produzidas atravs de diferenas de potencial eltricoque geram corrente eltrica. Por sua vez, a corrente se propaga atravs dos fios,da esquerda para a direita, ativando as portas lgicas. Os smbolos de medida, direita, representam que medidas de corrente so realizadas, indicando o valor decada bit: 0 ou 1. O bit, na posio inferior, d o resultado da operao. O fiopara o bit da posio superior desnecessrio, sendo utilizado apenas para exibir amesma quantidade de bits de entrada e sada.

1.1. O COMPUTADOR CLSSICO 3

f

bit0

bit1

bitn1

bit0

bit1

bitn1

.

.

.

.

.

.

.

.

.

.

.

.

Figura 1.1: Esquema genrico para um computador clssico.

OR

OR

NOT

NOT

AND

Figura 1.2: Circuito para realizar a soma de dois nmeros, em aritmtica mdulo 2, cadaum com um bit.

O circuito da Figura 1.2 irreversvel, pois as portas AND e OR so irreversveis.Isso significa, no caso da porta AND, que se a sada for 0, no se sabe quais os valoresdos dois bits de entrada. Para a porta OR, ocorre o mesmo, caso a sada seja 1. Asportas AND e OR, descritas dessa forma, no podem ser representadas por portasqunticas, pois como veremos, so reversveis.

No entanto, o circuito apresentado na Figura 1.2 pode ser transformado em umequivalente reversvel. Para tanto, vamos utilizar a porta CNOT, representada naFigura 1.3. O valor do bit superior (chamado bit de controle) nunca muda nessaporta, enquanto que o bit inferior (chamado bit alvo) alterado apenas se a = 1.Se a = 0, nada acontece a ambos os bits (no caso quntico, que ser visto adiante,o comportamento bem diferente). A porta CNOT uma porta NOT, controladapelo valor do bit superior. Podemos verificar que o valor do bit inferior de sada dado por a+ b (mod 2).

1.1. O COMPUTADOR CLSSICO 4

a a

b a + b (mod 2)

Figura 1.3: Porta CNOT.

Generalizando a porta CNOT, usando dois bits de controle no lugar de apenasum, temos a porta Toffoli (Figura 1.4), que pode ser usada para obter a contrapar-tida reversvel da porta AND.

a a

c c + ab (mod 2)

b b

Figura 1.4: Porta Toffoli.

O valor do bit inferior (o bit alvo) invertido apenas se a e b valem 1. Casocontrrio, nada alterado. A seguir, descrevemos todas as possveis entradas e assadas correspondentes:

000 000001 001010 010011 011100 100101 101110 111111 110

A porta AND pode ser representada por uma porta Toffoli colocando c = 0. Asada do bit inferior ser, ento, a AND b. Para obter o equivalente reversvel paraa porta OR, consulte [16].

Ainda na Figura 1.2, observe que h uma bifurcao de fios e no h problemaalgum em faz-lo classicamente. Entretanto, isso no possvel em circuitos qun-ticos, devido ao teorema de no clonagem (veja [19], p. 162). Verifique que esseefeito pode ser obtido atravs de uma porta CNOT, colocando b = 0. Com isso, ovalor do bit superior ser duplicado.

Consideremos, novamente, a Figura 1.1. Se o computador tem n bits de entrada,h 2n entradas possveis, e, para cada uma delas, h tambm 2n sadas possveis.

1.2. O COMPUTADOR QUNTICO 5

Com isso, o nmero de funes que pode ser obtido (2n)2n

, ou seja, 2n2n

. Todasessas funes podem ser reduzidas a circuitos usando as portas universais [16, 18].

Uma questo fundamental a velocidade com que um computador calculaessas funes. Isso depender do nmero de portas usadas no circuito que calculaf . Se o nmero de portas cresce polinomialmente com n, dizemos que o circuito eficiente. Por outro lado, se o nmero de portas cresce exponencialmente comn, dizemos que o circuito ineficiente. Esse um mtodo grosseiro de medida deeficincia, mas til para a anlise terica quando n grande.

Todos os clculos realizados em um computador clssico tambm podem serefetuados em computadores qunticos. Basta substituirmos as portas irreversveisclssicas pelas homlogas reversveis qunticas. Entretanto, o atrativo da compu-tao quntica a possibilidade de se ter algoritmos qunticos mais rpidos que osclssicos, para uma mesma classe de problemas. Para tanto, os algoritmos qunti-cos devem usar propriedades qunticas, no disponveis nos computadores clssicos,como o paralelismo quntico e o emaranhamento.

1.2 O Computador Quntico

1.2.1 O bit quntico (q-bit)

Em computao quntica, utilizam-se estados qunticos em vez de estados clssicos.O bit , ento, substitudo pelo bit quntico, o q-bit , e os valores 0 e 1 de um bitso substitudos pelos vetores |0 e |1, representados por

|0 =[

10

]e |1 =

[01

].

Essa notao, utilizada em mecnica quntica, conhecida por notao de Dirac.A diferena entre um bit e um q-bit que um q-bit genrico | pode tambm

ser uma combinao linear dos vetores |0 e |1, ou seja,

| = |0+ |1, (1.1)onde e so nmeros complexos. Note que os vetores |0 e |1 formam uma baseortonormal do espao vetorial C2. Essa base chamada de base computacional eo vetor | chamado de superposio dos vetores |0 e |1, com amplitudes e. Em mecnica quntica, vetor tambm chamado de estado. Usaremos os doistermos com o mesmo significado.

A interpretao fsica do q-bit, em (1.1), que ele est simultaneamente nosestados |0 e |1. Isso faz com que a quantidade de informao que pode ser ar-mazenada no estado | seja infinita. Entretanto, essa informao est no nvelquntico. Para torn-la acessvel, no nvel clssico, precisamos fazer uma medida.A mecnica quntica diz que o processo de medida altera o estado de um q-bit,fazendo-o assumir o estado |0, com probabilidade ||2, ou o estado |1, com proba-bilidade ||2 (isso significa que os valores e no podem ser conhecidos atravs


de uma medida). Com apenas duas possibilidades, |0 ou |1, temos, ento,

||2 + ||2 = 1. (1.2)

Isso significa que a norma do vetor | vale 1 (vetor unitrio). Resumindo: mate-maticamente, um q-bit um vetor de norma 1 de C2.

Na verdade, a definio da base computacional deveria ser

|0 =[

(1, 0)(0, 0)

]e |1 =

[(0, 0)(1, 0)

],

pois todas as coordenadas so nmeros complexos. Para simplificar a notao,usaremos 1 para representar (1,0) e 0 para representar (0,0).

Na equao (1.2), considere = a+ i b (a, b R) e = c+ i d (c, d R). Como||2 = (a2 + b2)2 e ||2 = (c2 + d2)2, podemos escrever

a2 + b2 + c2 + d2 = 1. (1.3)

Nesse caso, podemos interpretar um q-bit como sendo um vetor unitrio de R4.Entretanto, existe uma representao geomtrica de um q-bit em R3: a esfera deBloch (Figura 1.5). Para tanto, passemos o q-bit

| = |0+ |1, (1.4)

de coordenadas cartesianas para coordenadas polares (como anteriormente, =a+ i b e = c+ i d (a, b, c, d R)). Usando as representaes polares de e ,

= || exp(i) e = || exp(i( + )),

e definindocos(/2) = || e sen(/2) = ||,

ou ainda

= 2arccos(a2 + b2) = 2 arcsen(

c2 + d2),

= arg() arg(), = arg(),

(1.5)

podemos, finalmente, escrever

| = exp(i)[cos(/2) |0+ exp(i) sen(/2) |1]. (1.6)

Exerccio 1.1 Usando as definies dadas em (1.5), demonstre que a expres-so (1.4) pode ser escrita na forma (1.6).


Para fins de representao, vamos desconsiderar o termo externo aos colchetes,exp(i), tambm chamado fator de fase global . Uma razo que permite essa sim-plificao que o valor do quadrado do mdulo das amplitudes de um q-bit no sealtera, quando exclumos esse fator. Por exemplo:

||2 = | exp(i) cos(/2)|2 = | exp(i)|2| cos(/2)|2 = | cos(/2)|2,o mesmo ocorrendo com ||2 (para um tratamento detalhado desse fato, con-sulte [16], p. 93). Ficamos, ento, com uma representao de trs parmetros:dois explcitos, e , e um implcito, o comprimento do vetor, que sempre igual aum. Esses parmetros podem ser utilizados para obtermos uma representao polarno R3, da forma

xyz

=

cos sen sen sen

cos

,

onde 0 pi e 0 < 2pi.Usando essas convenes, a representao da base computacional, na esfera de

Bloch (Figura 1.5), ser:

|0 =001

e |1 =

001

.

Ou seja, |0 ser o plo norte da esfera e |1 ser seu plo sul.

x

y

z

|0

|1

|

Figura 1.5: Esfera de Bloch.


Dessa forma, todos os estados de um q-bit podem ser representados (a menos deum fator multiplicativo) na esfera de Bloch. Por exemplo, os estados 1

2(|0+ |1)

e 12(|0 |1), que sero utilizados mais frente, so representados por (1, 0, 0) e

(-1, 0, 0), respectivamente.

Exerccio 1.2 D uma interpretao, em termos de amplitudes e probabilidades,para os estados representados na interseo entre o plano (x, y, 0) e a esfera deBloch.

Insistimos que no se pode calcular exatamente os valores de || ou ||, em (1.4),mesmo que haja uma grande quantidade de estados | de mesmo valor. Vejamospor qu. Aps serem feitas repetidas medidas dos estados com valores iguais a|, teremos apenas os resultados |0 ou |1. Atravs da quantidade de |0s e|1s encontrados, teremos um valor aproximado para os valores ||2 e ||2. Nopodemos garantir sua exatido, pois trata-se de probabilidades. E mais, se parasabermos o valor dos coeficientes de um simples q-bit, com uma preciso razovel,precisssemos de um nmero enorme de medidas repetidas de q-bits com mesmovalor, provavelmente haveria pouco interesse em computadores qunticos.

Essa seria uma situao paradoxal, pois apenas medindo estados que forneamos resultados |0 ou |1, no ultrapassaramos os marcos da computao clssica.Ou seja, apesar da quantidade infinita de informao que um q-bit guardaria empotencial, apenas dois valores seriam acessados por ns. No entanto, h outro tipode fenmeno que ocorre com um estado quntico, alm daquele ocasionado por suamedida. A mecnica quntica tambm nos diz que a evoluo no tempo de umsistema quntico isolado descrita matematicamente por uma transformao linear[16]. Ora, sistemas qunticos isolados so descritos por vetores unitrios, e, comosabemos da lgebra linear, as funes que transformam vetores unitrios em vetoresunitrios do mesmo espao vetorial so as transformaes unitrias.

Transformaes lineares unitrias U podem ser definidas (h outras definiesequivalentes) como aquelas que atendam seguinte propriedade:

UU = UU = I,

onde U=(U)T , com indicando a conjugao complexa, e T indicando a trans-posio matricial. U denominada transformao adjunta de U . Desse ponto emdiante, faremos referncia indistintamente transformao U e matriz que a re-presenta usando a mesma notao, salvo indicao explcita. Usaremos, tambm, otermo operador com esse mesmo significado. Com isso, quando escrevermos U |,estaremos falando tanto da aplicao de U , quanto da multiplicao da matriz Upelo estado |.

Resumindo: temos, ento, duas interaes bsicas de um computador qunticocom os dados de entrada: transformao unitria e medida. A primeira, atuando nonvel quntico, e a segunda, fazendo a ligao entre o mundo quntico e o clssico.


1.2.2 Produto tensorial

Para considerarmos estados com mais de um q-bit, precisamos introduzir o conceitode produto tensorial. H vrios graus de generalidade para a introduo dessadefinio. Usaremos, aqui, a mais simples e que ser plenamente suficiente para osnossos propsitos.

O produto tensorial de dois estados

| =

12...m

e | =

12...p

,

denotado por | |, tem como resultado o estado | com mp-linhas, dado por

| =

1112...

1p2122...

2p...

m1m2

...mp

, (1.7)

onde ij o produto usual dos complexos.Usaremos, tambm, outras notaes mais simplificadas para o produto tensorial

| |. So elas: ||, |, e |. Por exemplo:

|01 = |0 |1 =[10

][01

]=

0100

e

|10 = |1 |0 =[01

][10

]=

0010

.


Note que o produto tensorial no comutativo.O produto tensorial pode ser estendido para matrizes quaisquer. Dadas as ma-

trizes A Cmn e B Cpq, a matriz AB Cmpnq definida por

AB =

A11B A12B A1nBA21B A22B A2nB...

.... . .

...Am1B Am2B AmnB

, (1.8)

onde Aij o elemento da linha i e da coluna j de A. De forma mais precisa, pormmais criptogrfica, cada elemento da matriz AB definido por

(AB)rs = AijBkl, (1.9)onde r = (i 1)p+ k e s = (j 1)q+ l, com os ndices variando da seguinte forma:1 i m, 1 j n, 1 k p, 1 l q.

Por exemplo, se

A =

[0 11 0

]e B =

1 0 00 1 0

0 0 1

,

ento

AB =[

0 11 0

] 1 0 00 1 0

0 0 1

=

0 0 0 1 0 00 0 0 0 1 00 0 0 0 0 11 0 0 0 0 00 1 0 0 0 00 0 1 0 0 0

.

A seguir, damos algumas propriedades do produto tensorial que sero utilizadasao longo do texto (considere z C, v, v1, v2 Cn e w, w1, w2 Cm):

1. z(|v |w) = (z|v) |w = |v (z|w),2. (|v1+ |v2) |w = (|v1 |w) + (|v2 |w),3. |v (|w1+ |w2) = (|v |w1) + (|v |w2).

Exerccio 1.3 Demonstre as propriedade 1, 2 e 3 do produto tensorial.

Dadas duas transformaes lineares A e B, podemos definir um novo operadorlinear, AB, por

(AB)(|u |w) = A|u B|w, (1.10)desde que garantidas as dimenses corretas para possibilitar as multiplicaes dasmatrizes pelos vetores.

Ainda, introduzindo mais algumas notaes, diremos que |n e An so osprodutos tensoriais de |, por ele prprio n vezes, e de A, por ela prpria n vezes,respectivamente.


Vejamos, agora, a descrio de um estado genrico | de 2 q-bits. Esse seruma superposio dos estados |00, |01, |10 e |11 (estamos usando a notaosimplificada para o produto tensorial entre dois estados de 1 q-bit), ou seja,

| = |00+ |01+ |10+ |11, (1.11)onde

||2 + ||2 + ||2 + ||2 = 1.Visando a reduzir a notao, podemos considerar os zeros e uns que aparecem

na equao (1.11) como nmeros binrios, e assim,

|00, |01, |10, |11podem ser abreviados por

|0, |1, |2, |3,usando a notao decimal. claro que o |0 acima no o mesmo que aparece nadefinio de um q-bit, pois tm dimenses diferentes. Em cada caso, o contextoesclarecer a que situao estamos nos referindo.

Em geral, um estado | de n q-bits uma superposio de 2n estados da basecomputacional {|0, |1, . . . , |2n 1}, dada por

| =2n1i=0

i|i,

com as amplitudes i atendendo a

2n1i=0

|i|2 = 1.

Como havamos comentado anteriormente, a medio do estado genrico |produz um resultado |i0 com probabilidade |i0 |2, com 0 i0 2n 1. Usu-almente, a medida realizada q-bit a q-bit, produzindo zeros e uns que so lidosem conjunto, gerando a sada |i0. Repetiremos, aqui, uma propriedade central doprocesso de medida. O estado |, antes da medio, inacessvel, a no ser queele pertena base computacional. O procedimento de medida altera inevitavel-mente |, forando-o a um colapso para algum dos vetores da base computacional.Este colapso, como vimos, no-determinstico, com probabilidades dadas pelosquadrados dos mdulos das amplitudes de |.

Consideremos, agora, outro conceito fundamental em computao quntica: oemaranhamento. Um estado de 2 q-bits pode ou no ser o resultado do produtotensorial de estados de 1 q-bit. Vejamos. Considere os estados de 1 q-bit

| = a|0+ b|1e

| = c|0+ d|1,


onde a, b, c, d C. O estado definido pelo produto tensorial de | e | | | = (a|0+ b|1) (c|0+ d|1)

= ac|00+ ad|01+ bc|10+ bd|11. (1.12)Observe que um estado de 2 q-bits genrico (1.11) da forma (1.12) se, e somentese,

= ac,

= ad,

= bc,

= bd.

Dessas igualdades, temos que

=c

de

=c

d.

Ou seja, = .

Logo, um estado de 2 q-bits, em geral, no o produto tensorial de estados de 1q-bit. Quando isso acontece, dizemos que o estado est emaranhado. Por exemplo,o estado |01 pode, obviamente, ser descrito como produto tensorial dos estados |0e |1, isto ,

|01 =

0100

=

[10

][01

].

No entanto, o estado 0110

um estado emaranhado, pois no pode ser descrito como produto tensorial deestados de 1 q-bit.

1.2.3 Produtos interno e externo

Podemos definir o produto interno entre os estados |, | Cn, denotado por|, como sendo o produto matricial entre | e |, ou seja,

| = (|)| =ni=1

ii . (1.13)

O estado | chamado dual de | e denotado por | (| e | so denominadosket e bra, respectivamente).

O produto interno satisfaz s seguintes propriedades:


1. | = |,2. |(a|u+ b|v) = a|u+ b|v,3. | > 0 (se | 6= 0),

com a, b C e |, |, |u, |v Cn.

Exerccio 1.4 Demonstre as propriedades 1, 2 e 3 do produto interno.

A norma de um estado | pode, ento, ser definida por|| | || =

|.

Podemos, tambm, definir o produto externo entre os estados | Cm e | Cn, denotado por ||, como sendo o produto matricial de | por |, ou seja,

|| = |(|).Note que || uma matriz de ordem m n.

Como exemplos das definies acima, considere os estados de 1 q-bit

| = |0+ |1e

| = |0+ |1.Temos, ento,

| = [ ] [

]= + ,

para o produto interno, e

|| =[

] [

]=

[

],

para o produto externo.

Exerccio 1.5 Demonstre que, dados dois vetores |, | Cn, temos(||)| = ||. (1.14)

Usando o produto interno, podemos definir o ngulo entre dois vetores unitrios|, | Rn por

= arccos(|). (1.15)Observe que, usando essa definio, [0, pi].

Com os conceitos apresentados at aqui, podemos dar uma representao paraum computador quntico (Figura 1.6), generalizando o computador clssico, apre-sentado na Figura 1.1. Os bits de entrada so substitudos por estados de 1 q-bit ea funo f substituda por um operador unitrio U que, em geral, o resultadoda composio de vrios outros operadores unitrios. O resultado da computao dado pela medida de cada q-bit de sada.


U

|1

|2

|n 0 ou 1

.

.

.

.

.

.

0 ou 1

0 ou 1

Figura 1.6: Esquema genrico para um computador quntico.

A priori, usando n q-bits, existe a possibilidade de um nmero infinito de opera-dores unitrios U , representados por matrizes com 2n2n entradas. Na prtica, hque se levar os erros em conta, o que diminui o nmero de circuitos implementveis.Mesmo assim, os graus de liberdade so maiores que no computador clssico. Cadaoperador U implementado com portas formando circuitos qunticos, assunto doprximo captulo.

Captulo 2

Circuitos Qunticos

A representao grfica de circuitos clssicos , de certa forma, prxima da reali-dade fsica do circuito implementado. Por exemplo, linhas correspondem a fios ebifurcaes significam que a corrente eltrica passa por ambos os fios. Nos circuitosqunticos, os fenmenos ocorrem de outra forma, como veremos.

2.1 Notao e Convenes

Para apresentar as convenes usadas em circuitos qunticos, vamos utilizar umcircuito (porta U-controlada) em que a entrada e a sada so um estado de 2 q-bits(Figura 2.1).

U

Figura 2.1: Porta quntica U-controlada.

Entrada: pode ser o produto tensorial entre os q-bits de entrada ou um estadoemaranhado (os q-bits no devem ser considerados individualmente).

Linhas horizontais: as linhas que aparecem no so necessariamente fios. Elasrepresentam a evoluo de um q-bit, podendo ser apenas a passagem do tempoou, por exemplo, o deslocamento de um fton.

2.2. PORTA NOT QUNTICA 16

Sentido: o circuito descreve a evoluo do sistema quntico no tempo, da esquerdapara a direita. Com isso, no h sentido em aparecer retroalimentao, quepode ocorrer em um circuito clssico.

Linhas verticais: o segmento vertical que aparece unindo os smbolos e Uinforma que o circuito atua simultaneamente nos dois q-bits. A linha verticalrepresenta o sincronismo, e no o envio de informao. Portanto, no sopermitidas nem junes, nem bifurcaes de q-bits.

Controle: o smbolo indica que o q-bit representado nessa linha um q-bit decontrole, ou seja, caso esteja no estado |1, a porta U realiza a operao; casoesteja no estado |0, a porta U no realiza operao alguma. Caso o q-bit decontrole seja um estado superposto ou os 2 q-bits estejam emaranhados, no possvel compreender o comportamento individual do q-bit de controle e doq-bit alvo. Devemos considerar a ao do operador unitrio, que representatodo o circuito, atuando simultaneamente nos 2 q-bits.

Sada: os q-bits que compem a sada do circuito podem ou no ser medidos.Como o q-bit inferior est sendo medido (o smbolo de medida est indicadona Figura 2.1), o resultado ser 0 ou 1.

Vistas as principais convenes, vamos apresentar algumas portas qunticas.Comecemos por portas de 1 q-bit. No caso clssico, h apenas uma possibilidade:a porta NOT. O mesmo no ocorre nos circuitos qunticos, como veremos.

Antes de prosseguir, faamos uma observao. A importncia do estudo deportas lgicas em computao quntica baseia-se no fato de que toda matriz uni-tria 2 2 pode ser representada por um circuito quntico de 1 q-bit e vice-versa[16]. Sendo assim, a evoluo no tempo de um sistema quntico isolado, dado porum q-bit, pode ser representada tanto matematicamente (por uma transformaounitria) quanto logicamente (por um circuito quntico).

2.2 Porta NOT Quntica

No caso clssico, a porta NOT troca o 1 por 0 e vice-versa. A generalizao para ocaso quntico dada por um operador X que satisfaz

X|0 = |1 e X|1 = |0. (2.1)

Com isso, verifica-se facilmente que a representao matricial do operador X dadapor

X =

[0 11 0

].

Exerccio 2.1 Demonstre que X um operador unitrio.

2.3. PORTA HADAMARD 17

Com a porta NOT quntica, temos situaes sem contrapartida no caso clssico,pois, se a entrada | for uma superposio dos estados |0 e |1,

| = |0+ |1,a sada ser

X| = |0+ |1.A porta X apenas uma da portas de 1 q-bit, j que h infinitas matrizes unitrias2 2.

2.3 Porta Hadamard

Uma outra porta de 1 q-bit, largamente utilizada, a porta Hadamard H, definidapelo operador

H =12

[1 11 1

]. (2.2)

Exerccio 2.2 Demonstre que H um operador unitrio.

Aplicando H no estado |0, obtemos

H|0 = 12(|0+ |1),

que uma superposio dos estados |0 e |1, onde a probabilidade de se obter umdos estados, ao se fazer uma medida do estado H|0, a mesma: 50%. Aplicandoo operador H em cada q-bit de um registrador com 2 q-bits no estado |00, temos:

H2|00 = H|0 H|0=

(12(|0+ |1)

)(

12(|0+ |1)

)=

1

2(|00+ |01+ |10+ |11) .

Em notao decimal,

H2|00 = 12(|0+ |1+ |2+ |3) .

Generalizando para estados com n q-bits, obtemos:

Hn|0...0 = (H|0)n

=

(12(|0+ |1)

)n

=12n

2n1i=0

|i.

Esse resultado ser importante no algoritmo de Grover (Captulo 3).

2.4. PORTA DE FASE OU PORTA S 18

Exerccio 2.3 Aplique o operador H em um estado superposto qualquer e inter-prete o resultado.

2.4 Porta de Fase ou Porta S

A matriz unitria associada porta S

S =

[1 00 i

],

onde i a unidade imaginria (i2 = 1). A porta S pode tambm ser representadapor

S =

[1 00 exp(ipi/2)

],

j que exp(ipi/2) = cos(pi/2) + i sen(pi/2) = i.Aplicando S em um estado genrico

| = |0+ |1,obtemos

S| = |0+ i|1.Note que, se for feita uma medida do estado S|, as probabilidades de se obter osestados |0 ou |1 sero as mesmas, comparadas com uma medida realizada sobre oestado |. Isso no acontece, por exemplo, usando a porta H.

2.5 Porta pi/8 ou Porta T

A matriz unitria associada porta T

T =

[1 00 exp(ipi/4)

],

que poderia ser representada, tambm, na forma

T = exp(ipi/8)

[exp(ipi/8) 0

0 exp(ipi/8)

].

Aplicando T em um estado genrico

| = |0+ |1,obtemos

T | = |0+ exp(ipi/4)|1.Tambm, nesse caso, se for feita uma medida do estado T |, as probabilidadesde se obter os estados |0 ou |1 sero as mesmas, comparadas com uma medidarealizada sobre o estado |.

2.6. PORTA CNOT QUNTICA 19

2.6 Porta CNOT Quntica

Outra porta, essa atuando em estados de 2 q-bits, a contrapartida quntica docircuito clssico apresentado anteriormente na Figura 1.3. Ela tem 2 q-bits deentrada, o de controle e o alvo (Figura 2.2). Uma porta controlada, como j vimos(Figura 2.1), age dependendo do valor do q-bit de controle. Ela ativada se oq-bit de controle estiver no estado |1, e nada faz, se ele estiver no estado |0. Essadescrio adequada apenas quando o q-bit de controle est nos estados |0 ou|1. Entretanto, o que distingue a porta CNOT quntica da clssica que, na portaCNOT quntica, os q-bits alvo e de controle podem ser estados superpostos, e, almdisso, os dois q-bits podem estar emaranhados.

Figura 2.2: Porta CNOT quntica.

A ao da porta CNOT pode ser caracterizada pelas transformaes operadasnos elementos da base computacional associada, ou seja,

|00 |00,|01 |01, (2.3)|10 |11,|11 |10.

Note que podemos representar essa ao na base computacional de forma maisesquemtica por

|i, j |i, i j, (2.4)

onde i, j {0, 1} e a adio mdulo 2.

2.7. PORTA TOFFOLI QUNTICA 20

Para obtermos a matriz UCNOT associada porta CNOT, basta usarmos osvalores dados em (2.3), isto ,

UCNOT

1000

=

1000

, UCNOT

0100

=

0100

,

UCNOT

0010

=

0001

, UCNOT

0001

=

0010

,

que resulta em

UCNOT =

1 0 0 00 1 0 00 0 0 10 0 1 0

. (2.5)

Exerccio 2.4 Demonstre que UCNOT um operador unitrio.

Exerccio 2.5 D um exemplo de estado emaranhado produzido pela porta CNOT.

Um resultado importante sobre circuitos qunticos que qualquer operador uni-trio pode ser representado usando portas CNOT e portas de 1 q-bit [16].

Exerccio 2.6 Demonstre que a matriz UCNOT no pode ser descrita como pro-duto tensorial de matrizes 2 2.

Exerccio 2.7 Demonstre que a porta CNOT no pode ser descrita usando portasde 1 q-bit.

2.7 Porta Toffoli Quntica

A prxima porta a ser considerada a correspondente quntica da porta Toffoli(Figura 1.4). Tambm uma porta controlada, s que nesse caso, com dois q-bits de controle (Figura 2.3). Sua ao na base computacional associada pode serrepresentada por

|i, j, k |i, j, k ij,onde i, j, k {0, 1} e a adio mdulo 2. Observe que, nesse caso, a basecomputacional possui 8 elementos.


Figura 2.3: Porta Toffoli quntica.

Exerccio 2.8 Exiba a matriz associada porta Toffoli quntica.

Exerccio 2.9 Analise se a matriz associada porta Toffoli quntica pode serrepresentada pelo produto tensorial de matrizes quadradas de dimenses diferentesde 1 1.

A porta Toffoli usada para simplificar a representao de circuitos qunticos.Como j sabemos, ela pode ser descrita usando portas de 1 q-bit e portas CNOT.Uma representao possvel dada na Figura 2.4 (h outras representaes [19]).

H T

T

T T

T T

T

H

S

Figura 2.4: Decomposio da porta Toffoli em portas de 1 q-bit e portas CNOT.

Exerccio 2.10 Faa a evoluo dos estados da base computacional, na represen-tao da porta Toffoli da Figura 2.4.

Para simplificar ainda mais a representao de circuitos qunticos, temos tam-bm a porta Toffoli generalizada (Figura 2.5), que ser utilizada nos captulos se-guintes.


n 1

q-bits de

controle

q-bit alvo{

.

.

.

Figura 2.5: Porta Toffoli generalizada.

A decomposio da porta Toffoli generalizada, em termos de portas Toffoli sim-ples, mostrada na Figura 2.6. Os n 2 q-bits de trabalho so q-bits extras,cujas entradas so conhecidas antecipadamente. So utilizados para simplificar adecomposio.

n 1q-bits

de

controle

n 2q-bits

de

trabalho

q-bit

alvo

{

|0

|0

|0

|0

|0

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Figura 2.6: Porta Toffoli generalizada decomposta em portas Toffoli simples.

Exerccio 2.11 Analise as sadas da porta Toffoli generalizada (Figura 2.5) e assadas da sua decomposio (Figura 2.6), considerando, na entrada, elementos dabase computacional.

Captulo 3

Algoritmo de Grover

3.1 Introduo

Considere o seguinte problema: temos uma lista no ordenada com N elementos edesejamos encontrar um elemento especfico que est na lista. Classicamente, deve-ramos testar elemento a elemento. No pior caso possvel, precisaramos realizar Ntestes. Como veremos, usando as propriedades da mecnica quntica, a quantidadede testes necessrios para a identificao do elemento procurado ser proporcionalaN . Este resultado ser obtido usando o algoritmo de Grover [12, 13].Para representar matematicamente o problema, vamos supor que a busca ser

realizada sobre a lista {0, 1, ..., N 1}, onde N = 2n para algum nmero natural n,e que a funo

f : {0, 1, ..., N 1} {0, 1},definida por

f(i) =

{1, se i = i0,0, se i 6= i0, (3.1)

ser utilizada para o reconhecimento do elemento procurado i0 (assumiremos queexiste um nico elemento i {0, 1, ..., N1} tal que f(i) = 1). Dessa forma, o custocomputacional para resolver o problema est associado ao nmero de vezes que afuno f deve ser utilizada. Imagine a funo f como sendo um orculo que est disposio para informar se um dado elemento ou no o elemento procurado.

O algoritmo de Grover utiliza dois registradores qunticos (Figura 3.1): o primei-ro, com n q-bits, inicializado no estado |0...0, e o segundo, com 1 q-bit, inicializadono estado |1. O primeiro registrador est relacionado aos elementos da lista ondeser feita a busca, enquanto que o segundo um registrador que ter um papel fun-damental, como veremos. A cada elemento i da lista {0, 1, ..., N 1}, associaremoso estado |i de n q-bits.

3.2. OPERADORES DO ALGORITMO 24

3.2 Operadores do Algoritmo

Antes da execuo propriamente dita do algoritmo, o primeiro registrador alteradopara formar uma superposio de todos os estados associados aos elementos da lista.Isso pode ser obtido aplicando o operador Hadamard H (2.2) em cada q-bit doprimeiro registrador (Figura 3.1).

||1

|0

|0

G

| | |

| |G |G2 |Gk

H

H

H

G G

primeiroregistrador(n q-bits)

segundoregistrador(1 q-bit)

{

. . .

. . .

. . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Figura 3.1: Esquema genrico para o algoritmo de Grover (G um operador unitrio queser definido mais adiante).

A superposio obtida ser denotada por |, ou seja,

| = 1N

N1i=0

|i. (3.2)

Observe que aplicando n vezes o operador H, obtemos uma superposio de N = 2n

estados com mesma amplitude.Para completar a inicializao do algoritmo, o operador H tambm aplicado

sobre o estado inicial do segundo registrador (Figura 3.1). Denotando o resultadopor |, temos:

| = H|1 = 12(|0 |1). (3.3)

J sabemos que qualquer alterao de um sistema quntico isolado (que noseja uma medida) descrita por um operador unitrio. Para representar quanti-camente a funo f , em (3.1), utilizada para a identificao do elemento procurado,imaginemos, ento, um operador linear Uf que transforme |i em |f(i), onde |i oestado de n q-bits do primeiro registrador. Como Uf deve ser unitrio, a entradae a sada de Uf devem ter a mesma dimenso. Considere, ento,

|i|0 Uf |i|f(i), (3.4)onde, na entrada e na sada, o primeiro registrador tem n q-bits e o segundoapenas 1 q-bit. Usando (3.4), temos:

Uf (|i|0) ={ |i|1, se i = i0,|i|0, se i 6= i0. (3.5)


Ou seja, o operador Uf altera o estado do segundo registrador quando o primeiro re-gistrador representa o elemento procurado. Para completar a definio, precisamosdefinir o valor de Uf (|i|1). Mantendo a mesma idia, definimos:

Uf (|i|1) ={ |i|0, se i = i0,|i|1, se i 6= i0. (3.6)

Com isso, Uf fica bem definido, pois, sendo um operador linear, basta defini-lo noselementos da base. Note que a base formada usando o produto tensorial. Porexemplo, para uma lista com 4 elementos (o primeiro registrador ter 2 q-bits), abase ser

{|0|0, |0|1, |1|0, |1|1, |2|0, |2|1, |3|0, |3|1},ou melhor,

10000000

,

01000000

,

00100000

,

00010000

,

00001000

,

00000100

,

00000010

,

00000001

.

Exerccio 3.1 Exiba a matriz que representa Uf .

Para facilitar os clculos a seguir, representaremos (3.5) e (3.6) de uma nicamaneira, isto ,

Uf (|i|j) = |i|j f(i), (3.7)onde |i o estado de n q-bits do primeiro registrador (i {0, 1, . . . , N 1}), |j o estado de 1 q-bit do segundo registrador (j {0, 1}) e a soma mdulo 2.Note que Uf C(2n+12n+1).

Exerccio 3.2 Demonstre que Uf um operador unitrio.

O operador Uf foi definido para simular quanticamente o papel da funo f(3.1). Para identificar o elemento procurado i0, bastaria aplicar Uf em cada estadoassociado aos elementos da lista e manter o segundo registrador no estado |0 ou |1.Quando o estado do segundo registrador fosse alterado, saberamos que o elementobuscado teria sido encontrado. Neste caso, o estado do primeiro registrador seria|i0. No entanto, isso no proporcionaria ganho algum em relao ao caso clssico,usando a funo f . O que vai fazer diferena que podemos tambm aplicar Ufem estados superpostos. Vejamos.

O prximo passo do algoritmo aplicar o operador Uf sobre o estado ||,resultante da inicializao (Figura 3.2). Ou seja,

Uf (||) = Uf((

1N

N1i=0

|i)|).


|1

|0

|0

Uf

|

|

......

...

H

H

H

Figura 3.2: Aplicao do operador Uf sobre o estado ||.

Usando a distributividade do produto tensorial em relao adio de vetores,

Uf (||) = Uf(

1N

N1i=0

|i|).

Da linearidade do operador Uf ,

Uf (||) = 1N

N1i=0

Uf (|i|) .

Substituindo a definio do estado |, dada em (3.3), na expresso acima, obtemos:

Uf (||) = 1N

N1i=0

Uf

(|i(

12(|0 |1)

))

=1N

N1i=0

Uf

(12(|i|0 |i|1)

).

Novamente, da linearidade de Uf ,

Uf (||) = 1N

N1i=0

12(Uf (|i|0) Uf (|i|1)) .

Da definio de Uf , em (3.7), temos:

Uf (||) = 1N

N1i=0

12(|i|f(i) |i|1 f(i))

=1N

N1i=0

12(|i (|f(i) |1 f(i))) . (3.8)


Da definio de f , em (3.1),

|i (|f(i) |1 f(i)) ={ |i (|1 |0) , se i = i0,|i (|0 |1) , se i 6= i0. (3.9)

Substituindo a expresso anterior em (3.8), temos:

Uf (||) = 1N

N1

i=0,i 6=i0

(12(|i (|0 |1))

)+

12(|i0 (|1 |0))

.

Novamente, da definio de |,

Uf (||) = 1N

N1

i=0,i 6=i0|i|

|i0|

=1N

(N1i=0

(1)f(i)|i|).

Ou ainda,

Uf (||) =(

1N

N1i=0

(1)f(i)|i)|. (3.10)

Note que o estado do segundo registrador no se altera (como visto acima, isso noquer dizer que ele seja desnecessrio!). O estado do primeiro registrador continuasendo uma superposio de todos os estados associados aos elementos da lista.Entretanto, a amplitude do elemento procurado foi alterada de 1

Npara 1

N.

Aps a aplicao do operador Uf , um fato interessante ocorreu. Alm da funof ter sido avaliada em todos os elementos da lista onde est sendo feita a busca,com apenas uma aplicao de Uf (este fenmeno conhecido como paralelismoquntico [16]), o estado associado ao elemento procurado foi identificado comosendo o nico que teve sua amplitude alterada. No entanto, essa informao s estdisponvel quanticamente. No adiantaria fazer uma medida do primeiro registra-dor, pois a probabilidade de se obter o elemento procurado 1N

2 = 1N .Antes de prosseguirmos, consideremos a seguinte questo: a aplicao do opera-

dor Uf sobre um estado qualquer, no primeiro registrador, ainda mantm o segundoregistrador no estado |? Vejamos.


Seja |i, um estado qualquer da base computacional {|0, |1, ..., |N1}. Usandoas definies do operador Uf e do estado |, temos:

Uf (|i|) = Uf(|i(

12(|0 |1)

))

= Uf

(12(|i|0 |i|1)

)=

12(Uf (|i|0) Uf (|i|1))

=12(|i|f(i) |i|1 f(i)) .

Da mesma forma que fizemos no clculo de Uf (||), obtemos:Uf (|i|) = (1)f(i)|i|.

Ou seja,

Uf (|i|) ={ |i|, se i = i0,

|i|, se i 6= i0. (3.11)

Usando este resultado e aplicando Uf sobre um vetor unitrio qualquer

|v =N1

i=0,i 6=i0i|i+ i0 |i0,

gerado pelos elementos da base computacional {|0, |1, ..., |N 1}, no primeiroregistrador, e mantendo o estado |, no segundo registrador, temos:

Uf

N1

i=0,i 6=i0i|i+ i0 |i0

|

= Uf

N1

i=0,i 6=i0i|i|+ i0 |i0|

=

N1i=0,i 6=i0

iUf (|i|) + i0Uf (|i0|)

=N1

i=0,i 6=i0i|i| i0 |i0|

=

N1

i=0,i 6=i0i|i i0 |i0

|. (3.12)

Concluso: a aplicao de Uf sobre o estado |v| no altera o estado do segundoregistrador. Portanto, para simplificar os clculos, sempre que o estado do segundoregistrador for |, como o caso no algoritmo de Grover, omitiremos o segundoregistrador. importante destacar que o estado | fundamental no processo demarcao do elemento procurado.


Exerccio 3.3 Verifique o que acontece se, ao aplicarmos o operador Uf , o estadodo segundo registrador no for o estado |.

Voltemos ao algoritmo. Com o elemento a ser buscado j identificado quantica-mente, o prximo passo ser aumentar a probabilidade de esse elemento ser obtido,aps uma medida.

O novo estado do primeiro registrador ser denotado por |1, isto ,

|1 = 1N

N1i=0

(1)f(i)|i. (3.13)

Olhando com mais cuidado o resultado da aplicao de Uf sobre o estado |v|,em (3.12), podemos obter uma interpretao geomtrica do efeito do operador Ufsobre o primeiro registrador: a aplicao de Uf sobre um vetor unitrio qualquergerado pelos elementos da base computacional {|0, |1, ..., |N 1} resulta numareflexo desse vetor em relao ao subespao ortogonal a |i0, gerado por todos osoutros elementos da base computacional. Para visualizar esse resultado, podemosconsiderar essa reflexo como uma reflexo em relao projeo de |v sobre osubespao ortogonal a |i0. Considerando o vetor unitrio na direo dessa projeo,denotado por |u, temos:

|u = 1N 1

N1i=0,i 6=i0

|i. (3.14)

Exerccio 3.4 Demonstre que |u pode ser representado por:

|u =N

N 1 | 1N 1 |i0. (3.15)

Para completar a visualizao, calculemos os ngulos entre | e |i0 e entre |ue |i0. Usando o produto interno, temos:

|i0 = 1N

N1i=0

i|i0 = 1Ni0|i0 = 1

N(3.16)

e

u|i0 = 1N 1

N1i=0,i 6=i0

i|i0 = 0. (3.17)

Ou seja, o ngulo entre | e |i0 menor do que pi/2 rad (se N grande, o ngulo quase pi/2 rad) e o ngulo entre |u e |i0 exatamente pi/2 rad. Usando osresultados (3.16), (3.17) e a expresso dada em (3.15), podemos, finalmente, obteruma representao geomtrica para a ao do operador Uf sobre o estado |, dadana Figura 3.3.


um nmero real. Isso possibilita a comparao entre ngulos de dois pares de estadosquaisquer. A partir de agora, teremos em mente esse fato.

A projeo de |1 sobre | dada por |1|. Motivados pelo losangoabaixo (Figura 3.5), vemos que o vetor resultante da reflexo de |1 em relao a| pode ser descrito como

(2|1) | |1. (3.18)

|1

|1

|1|

2|1| |1

Figura 3.5: Reflexo de |1 em relao a |.

O que desejamos obter um novo operador que produza essa reflexo. Usandoa propriedade (1.14), podemos reescrever a expresso acima, obtendo:

(2|1) | |1 = (2||) |1 |1 = (2|| I) |1.

Ou seja, o operador que procuramos

2|| I, (3.19)

onde I o operador identidade.O estado resultante do primeiro registrador, aps a aplicao do operador Uf ,

em (3.13), pode ser reescrito como

|1 = | 2N|i0, (3.20)

onde

| = 1N

N1i=0

|i (3.21)


e i0 o elemento procurado. Denotando por |G (Figura 3.6), o estado resultanteda aplicao do operador 2|| I sobre |1, e usando (3.20), obtemos:

|G = (2|| I) |1= (2|| I)

(| 2

N|i0)

= (2|) | (

4N|i0

)| |+ 2

N|i0. (3.22)

Substituindo (3.16) em (3.22), temos:

|G = N 4N

|+ 2N|i0. (3.23)

Esse , ento, o estado do primeiro registrador aps a aplicao dos operadores Uf e2|| I (o estado do segundo registrador permanece inalterado). A composiodesses dois operadores chamada de operador de Grover G, isto ,

G = ((2|| I) I)Uf . (3.24)

O segundo operador identidade aparece, porque o operador 2|| I aplicadoapenas no primeiro registrador (Figura 3.6).

|1

|0

|0

Uf

|

| |1

|

......

...2|| I

|G

......

H

H

H

Figura 3.6: Uma aplicao do operador de Grover (G).

Exerccio 3.5 Demonstre que G um operador unitrio.

De (3.23), obtemos a amplitude do estado |i0, aps a primeira aplicao dooperador G: (

N 4N

)(1N

)+

2N

=

(3N 4NN

).

Por exemplo, para N = 4, a probabilidade de se obter o elemento procurado, apsuma medida do estado |, em (3.21), 25%. J a probabilidade de se obtero elemento procurado, aps uma medida do estado |G, em (3.23), 100%. No

3.3. CUSTO COMPUTACIONAL DO ALGORITMO 33

entanto, para valores grandes de N , essa probabilidade ainda pequena. At agora,o que podemos garantir que, com uma aplicao do operador G, a amplitude doestado |i0 aumentada, em relao sua amplitude no estado |. E se aplicarmosnovamente o operador G sobre o estado |G|? A interpretao geomtrica dosoperadores Uf e 2|| I nos induz justamente a isso (Figuras 3.3 e 3.4).

3.3 Custo Computacional do Algoritmo

Como demonstraremos nesta seo, o estado resultante do primeiro registrador,aps cada aplicao do operador G, vai se aproximando do estado |i0. Ento,para determinar o custo computacional do algoritmo de Grover, temos que calcularquantas aplicaes de G sero necessrias.

Inicialmente, demonstraremos que a aplicao de Gk (k N) produz um rotaode | em direo a |i0, de k rad, no subespao gerado pelos vetores | e |i0, onde o ngulo entre | e G| (Figura 3.7). Para facilitar a leitura, dividiremos ademostrao em 4 proposies. A Proposio 1 diz que Gk| pertence ao subespaogerado por | e |i0, para todo k N. A Proposio 2 estabelece que o ngulo entreGk| e Gk+1| tambm , para todo k N. Na Proposio 3, demonstramosque G rotaciona | em direo a |i0. Finalmente, na Proposio 4, provamos queo sentido da rotao produzida quando G aplicado sobre Gk|, para todo k N, o mesmo obtido quando G aplicado sobre |. O subespao gerado por | e|i0 ser denotado por e o estado do primeiro registrador de Gk| ser denotadopor |Gk. O estado do segundo registrador (|) ser omitido, pois ele constantedurante todo o processo.

|

|i0

G|

G2|

G3|

Figura 3.7: Efeito da aplicao do operador G.

Proposio 1 Gn| , para todo n N.


Prova. A demonstrao por induo. De (3.23), sabemos que

G| = N 4N

|+ 2N|i0. (3.25)

Com isso, temos o resultado para n = 1. Suponhamos que, para um dado k N,Gk| .

Isto , existem , R tais queGk| = |+ |i0. (3.26)

Temos que provar queGk+1| .

Aplicando o operador G nos dois lados de (3.26), obtemos:

Gk+1| = G|+ G|i0. (3.27)J sabemos que G| . Calculemos G|i0. Da definio de G, em (3.24), temos:

G|i0 = (2|| I)Uf |i0. (3.28)De (3.11),

Uf |i0 = |i0. (3.29)Substituindo (3.29) em (3.28) e usando (3.16), obtemos:

G|i0 = (2|| I) (|i0)= 2|i0|+ |i0= 2

N|+ |i0. (3.30)

Ou seja, G|i0 . Como os estados G| e G|i0 pertencem a , de (3.27),conclumos que

Gk+1| ,que finaliza a induo.

Proposio 2 O ngulo entre Gk| e Gk+1| rad, para todo k N.Prova. Usando a definio de ngulo entre dois vetores, dada no Captulo 1, p. 13,o enunciado deste lema torna-se equivalente a

Gk |Gk+1 = cos , k N.Reescrevendo, temos

Gk |Gk+1 = Gk |Gk|G= (Gk)Gk |G.


Proposio 4 A aplicao de G sobre |Gn, para todo n N, mantm o mesmosentido de rotao quando G aplicado sobre |.Prova. Pelas Proposies 1, 2 e 3, j sabemos que, quando aplicamos o operadorG sobre o estado |Gn, temos apenas duas possibilidades: G (Gn|) um estadoresultante de uma rotao de rad, em , no sentido horrio ou anti-horrio. Sedemonstrarmos que, para todo n N,

G (Gn|) 6= Gn1|,poderemos concluir que a rotao mantm o mesmo sentido quando G aplicadosobre |. A demonstrao ser, portanto, por induo. Inicialmente, mostremosque

G(G1|) 6= G0|,

ou seja,G|G 6= |.

Usando (3.25) e (3.30), podemos calcular G|G:

G|G = G(N 4N

|+ 2N|i0)

=N 4N

G|+ 2NG|i0

=N 4N

(N 4N

|+ 2N|i0)+

2N

( 2

N|+ |i0

)

=

(N 4N

)2|+ 2N 8

NN|i0 4

N|+ 2

N|i0

=

((N 4N

)2 4N

)|+ 4N 8

NN|i0.

Para N > 2, este estado diferente de |. Suponhamos agora que, para um dadok N,

G(Gk|) 6= Gk1|.

Como G um operador unitrio, podemos aplic-lo nos dois lados da expressoacima e ainda obter estados distintos, isto ,

G(Gk+1|) 6= Gk|.

Isso conclui a induo (d um exemplo mostrando que a concluso da induo s possvel, porque G um operador unitrio).

Concluso: a aplicao de Gk sobre | produz uma rotao de k rad em direoa |i0, no subespao gerado por | e |i0, para todo k N.

Consideremos, ento, o custo do algoritmo de Grover. De forma mais precisa,devemos calcular o nmero de vezes k que o operador G deve ser aplicado para


que o estado Gk| torne-se o mais prximo do estado |i0. Dito de outra forma,queremos saber que valor de k faz com que o ngulo entre |i0 e Gk| seja o maisprximo de zero (Figura 3.8). Admitindo que k seja um nmero real, podemosrepresentar matematicamente o problema acima atravs da seguinte equao:

arccos(|i0) k = 0. (3.32)

|

Gk|

G|

Gk1|

G2|

|i0

Figura 3.8: Aplicaes sucessivas do operador G.

De (3.31), j sabemos que o ngulo entre | e G|

= arccos

(N 2N

). (3.33)

Substituindo (3.16) e (3.33) em (3.32), obtemos:

arccos

(1N

) k arccos

(N 2N

)= 0.

Isolando k, temos:

k =arccos

(1N

)arccos

(N2N

) . (3.34)Para sabermos a ordem de grandeza de k, inicialmente, comparemos k com

N . Calculando o limite, temos:

limN

k

N= 0.

3.4. EXEMPLO: N=8 38

Ou seja, k menor do que N , para valores grandes de N . Calculemos, ento, oseguinte:

limN

k

log2(N)=.

Neste caso, k maior do que log2(N), para valores grandes de N . Tentando umvalor intermedirio, obtemos:

limN

kN

=pi

4.

Isso significa que, para valores suficientemente grandes de N , o nmero de vezesque o operador G deve ser aplicado , no mximo,

N vezes.

Esse o resultado que tnhamos enunciado no incio do captulo. Na prximaseo, daremos um exemplo usando uma lista com 8 elementos.

Exerccio 3.6 Calcule os trs limites acima.

3.4 Exemplo: N=8

Apliquemos o algoritmo de Grover em uma lista com N = 8 elementos. O primeiroregistrador ter, portanto, 3 q-bits. A primeira pergunta : quantas aplicaes dooperador G devem ser utilizadas? Usando (3.34), obtemos:

k =arccos

(18

)arccos

(828

) = 1, 67.Para que o estado resultante da ltima aplicao de G esteja o mais prximo de|i0, devemos aplicar 2 vezes o operador G (Figura 3.9). A idia arredondar ovalor de k para o inteiro mais prximo.

||1

|0

|0

|0

Uf 2|| I

|

Uf 2|| I

| |

| |1 |G |2 |G2

G G

1

1

0

H

H

H

H

Figura 3.9: Duas aplicaes do operador G, para N = 8 e i0 = 101.

3.4. EXEMPLO: N=8 39

Antes da aplicao de G, o algoritmo cria uma superposio | formada portodos os elementos da base computacional associada ao problema. Isso obtidoaplicando o operador H (2.2) sobre cada q-bit do estado inicial (|000) do primeiroregistrador, isto ,

| = H|0 H|0 H|0=

(12(|0+ |1)

)(

12(|0+ |1)

)(

12(|0+ |1)

)=

18(|000+ |001+ |010+ |011+ |100+ |101+ |110+ |111) .

Em notao decimal, temos:

| = 18(|0+ |1+ |2+ |3+ |4+ |5+ |6+ |7) .

Supondo que o elemento procurado seja

|i0 = |101 = |5,o prximo passo aplicar o operador Uf sobre o estado ||. O elemento procu-rado , ento, o nico que tem sua amplitude alterada:

|1| = Uf (||)=

( |0+ |1+ |2+ |3+ |4 |5+ |6+ |78

)|.

Em seguida, o operador 2|| I aplicado sobre o estado |1, produzindo oestado |G:

|G = (2|| I) |1= (2|1) | |1=

3

2| |1

=1

28(|0+ |1+ |2+ |3+ |4+ |6+ |7) + 5

28|5.

Se medirmos este estado, a probabilidade de se obter o elemento procurado (5

28

)2= 78, 12%.

Entretanto, j sabemos que devemos aplicar 2 vezes o operador G. Aplicando ooperador Uf sobre o estado |G|, obtemos:

|2| = Uf (|G|)=

(1

28(|0+ |1+ |2+ |3+ |4+ |6+ |7) 5

28|5)|.

3.5. CIRCUITOS QUNTICOS PARA O OPERADOR G 40

Novamente, o elemento procurado o nico que tem sua amplitude alterada. Apli-cando o operador 2|| I sobre |2, temos:

|G2 = (2|| I) |2= (2|2) | |2=

1

4| |2

=

( 148(|0+ |1+ |2+ |3+ |4+ |6+ |7) + 11

48|5).

|

|i0

|u

|1

|G

|2

|G2

Figura 3.10: Duas aplicaes do operador G, para N = 8 e i0 = 101.

Fazendo uma medida do estado |G2, obtemos o elemento procurado com pro-babilidade de (

11

48

)2= 94, 53%.

Na Figura 3.10, representamos geometricamente os passos do algoritmo resul-tantes de duas aplicaes do operador G.

Exerccio 3.7 Usando a Figura 3.10, d uma explicao para os sinais das ampli-tudes da superposio dada em |G2.

3.5 Circuitos Qunticos para o Operador G

Nesta seo, iremos decompor o operador G em termos de portas de 1 q-bit e portasCNOT. Essa decomposio mostrar como poderia ser uma implementao prticado operador G.


3.5.1 Circuito quntico para o operador Uf

Recordemos que a funo f (3.1) age como um orculo para identificar o elementoprocurado i0. De forma similar, o operador Uf tambm pode ser imaginado comoum orculo. Nesse sentido, ele um operador diferente do operador 2|| I,pois deve ser preparado para a identificao do estado |i0. O operador Uf podeser representado por uma porta Toffoli generalizada com n q-bits de controle, 1q-bit alvo no estado | e 2 portas X atuando no i-simo q-bit de controle, sempreque o i-simo dgito binrio de i0 for 0. Por exemplo, o circuito quntico para ooperador Uf , usado no exemplo dado na Seo 3.4 (n = 3 e i0 = 101), tem a formaapresentada na Figura 3.11. Se o elemento procurado fosse 111, nenhuma porta Xseria usada. Caso fosse 000, 3 pares de portas X seriam usadas, um par em cadaq-bit de controle.

| |

X X

Figura 3.11: Circuito quntico para o operador Uf (n = 3 e i0 = 101).

3.5.2 Circuito quntico para o operador 2|| IConsideremos, agora, a decomposio do operador 2|| I. Usando

| = Hn|0 e | = 0|(Hn),

temos, ento,

2|| I = 2Hn(|00|)(Hn) I= Hn(2|00|)(Hn) Hn(Hn)= Hn(2|00| I)(Hn)= Hn(2|00| I)Hn. (3.35)

Observe que Hn uma matriz simtrica com apenas entradas reais. Portanto,(Hn) = Hn.

Exerccio 3.8 Demonstre que o produto tensorial de matrizes simtricas umamatriz simtrica.


A equao (3.35) mostra que, para obtermos o circuito quntico do operador2|| I, basta considerarmos o operador 2|00| I. Esse operador faz umareflexo em relao ao estado |0. O circuito para esse operador dado na Figura3.12. Na Tabela 3.1, representamos a ao desse operador sobre o estado |0.

n

q-bits

|0 |1 |2

iI iIX X

X

X

H H XX

X

X

|3 |4 |5

.

.

.

.

.

.

.

.

.

......

......

......

Figura 3.12: Circuito quntico para o operador 2|00| I.

Observe que a nica porta que atua nos n q-bits ao mesmo tempo, na Figura 3.12, a porta Toffoli generalizada (Figura 2.5).

Exerccio 3.9 Teste a ao do circuito da Figura 3.12 em outros estados da basecomputacional para perceber que, para qualquer entrada |j, com 0 < j < N , asada ser sempre -|j.

Um ponto importante que ainda no foi discutido o custo computacional as-sociado a cada operador que compe G. Pode-se demonstrar que esse custo proporcional a log 2N (ver [16]). No captulo seguinte, trataremos em detalhes essaquesto, considerando o algoritmo de Shor.

|0 |1 |2 |3 |4 |5|0 |1 i |1 i |1 (-i i )|1 |0|0 |1 |1 |1 |1 |0...

......

......

...|0 |1 |1 |1 |1 |0|0 |1 | -| |1 |0

Tabela 3.1: Ao do operador 2|00| I no estado |0 da base computacional.

Captulo 4

Algoritmo de Shor

4.1 Reduo da Fatorao ao Clculo da Ordem

Nesse captulo vamos descrever o algoritmo de Shor [21] que acha os fatores primosde um nmero composto N . Comearemos mostrando como a fatorao pode serreduzida ao clculo da ordem de um nmero x menor que N , escolhido aleatori-amente. Imagine que N um nmero grande, por exemplo com 300 dgitos nanotao decimal, j que tais nmeros so usados em criptografia. Embora N sejagrande, o nmero de q-bits necessrio para guard-lo pequeno: log2N . Em geral,log2N no um inteiro, ento definimos

n = log2N,onde log2N o menor inteiro maior ou igual a log2N .

Um computador quntico com n q-bits pode guardarN ou qualquer outro inteiropositivo menor que N na memria. Facilmente, vemos que o nmero de fatoresprimos de N no mximo n. Se o nmero de q-bits e o nmero de fatores primosso menores ou iguais a n, ento natural perguntar se existe um algoritmo quefatora N em um nmero de passos que polinomial em n. Mais precisamente aquesto : existe um algoritmo de fatorao na classe de complexidade P [17]?

A reduo da fatorao de N ao problema de achar a ordem de um inteiro xmenor queN pode ser descrita da seguinte forma. Se x eN possuem fatores comuns,ento o MDC(x,N) fornece um fator de N ; portanto, suficiente investigar o casoquando x coprimo com N . A ordem de x, mdulo N , o menor inteiro positivor, tal que

xr 1 mod N.Se r for par, podemos definir y como sendo

xr/2 y mod N.A notao acima significa que y o resto da diviso de xr/2 por N e, pela definio,0 y < N . Note que y satisfaz y2 1 mod N , ou equivalentemente, (y1)(y+1)

4.1. REDUO DA FATORAO AO CLCULO DA ORDEM 44

0 mod N , o que significa que N divide (y 1)(y + 1). Se 1 < y < N 1, os fatoresy 1 e y + 1 satisfazem 0 < y 1 < y + 1 < N ; portanto, N no pode dividiry 1 nem y + 1 separadamente. A nica alternativa que ambos y 1 e y + 1tenham fatores de N . Ento, MDC(y 1, N) e MDC(y + 1, N) produzem fatoresno triviais de N . Se N tiver mais fatores, eles podem ser calculados aplicandoo algoritmo recursivamente. Considere N = 21 como exemplo. A seqncia deequivalncias

24 16 mod 2125 11 mod 2126 11 2 1 mod 21

mostra que a ordem de 2, mdulo 21, r = 6. Portanto, y 23 8 mod 21. Dey 1 resulta o fator 7 e de y+1 resulta o fator 3 de 21. Resumindo, se escolhermosaleatoriamente um inteiro positivo x menor que N e calcularmos o MDC(x,N), outeremos um fator de N , ou ficaremos sabendo que x coprimo com N . Neste ltimocaso, se x satisfizer as condies (1) a ordem r par, e (2) 0 < y 1 < y + 1 < N ,ento o MDC(y 1, N) e MDC(y + 1, N) produzem fatores de N . Se uma dascondies no verdadeira, recomeamos at achar um candidato x apropriado. Omtodo no seria til se estas suposies fossem restritivas demais, mas felizmenteeste no o caso. O mtodo sistematicamente falha, se N for uma potncia dealgum primo, mas nesse caso, um algoritmo clssico eficiente conhecido. Se N forpar, podemos continuar dividindo por 2 at o resultado passar a ser mpar. Resta-nos aplicar o mtodo para os inteiros compostos mpares que no so potncias dealgum nmero primo. complicado provar que a probabilidade de achar x coprimocom N satisfazendo as condies (1) e (2) alta; de fato, essa probabilidade 1 1/2k1, onde k o nmero de fatores primos de N . No pior dos casos (N tem2 fatores), a probabilidade maior ou igual a 1/2 (veja a prova no Apndice B de[10]). primeira vista, parece que acabamos de descrever um algoritmo eficientepara achar um fator de N . Isto no verdade, j que no so conhecidos algoritmosclssicos eficientes para calcular a ordem de um inteiro x mdulo N . Por outrolado, existe (depois do trabalho de Shor) um algoritmo quntico eficiente. Vamosdescrev-lo a seguir.

Exerccio 4.1 Calcule a ordem de 2 mdulo 15. A partir do resultado, como vocpode determinar os fatores de 15? Tente com outros inteiros menores do que 15, nolugar do nmero 2.

Exerccio 4.2 Com N = 21, determine todos os inteiros menores do que N quetm ordem par. Calcule a probabilidade do mtodo descrito nesta seo fornecer oresultado correto.

4.2. ALGORITMO QUNTICO PARA O CLCULO DE ORDEM 45

4.2 Algoritmo Quntico para o Clculo de Ordem

Considere o circuito da Figura 4.1 que calcula a ordem r de um inteiro positivo xmenor que N , coprimo com N . Vx um operador linear unitrio dado por

Vx(|j |k) = |jk + xj , (4.1)

onde |j e |k so os estados do primeiro e segundo registrador, respectivamente.As operaes aritmticas so feitas mdulo N , assim 0 k + xj < N . O operadorDFT (Discrete Fourier Transform) ser descrito mais adiante.

O primeiro registrador possui t q-bits, onde t deve ser escolhido de forma queN2 2t 2N2, por razes que ficaro claras mais adiante [20]. Se a ordem uma potncia de 2, ento suficiente tomar t = n. Nesta seo, vamos considerareste caso especial e deixar o caso geral para a Seo 4.4. Continuaremos usando avarivel t para generalizarmos nossa discusso mais adiante.

Os estados do computador quntico esto indicados por |0 at |5 na Figura4.1. O estado inicial

|0 = |0 . . . 0 t

|0 . . . 0 n

.

A aplicao do operador Hadamard

H =12

[1 11 1

],

em cada q-bit do primeiro registrador, resulta em

|1 = 12t

2t1j=0

|j |0 . (4.2)

O primeiro registrador est em uma superposio de todos os estados da base com-putacional com igual amplitude dada por 1

2t. Agora, note o que acontece quando

aplicamos Vx em |1:|2 = Vx |1

=12t

2t1j=0

Vx(|j |0)

=12t

2t1j=0

|j xj . (4.3)O estado |2 interessante, pois, j que Vx linear, ele atua simultaneamente emtodos os termos |j |0 para 2t valores de j. Logo, isto gera todas as potncias dex simultaneamente. Esta caracterstica chamada paralelismo quntico. Algumasdessas potncias so 1, as quais correspondem aos estados

|0 |1 , |r |1 , |2r |1 , ,(2t

r 1

)r

|1 . (4.4)


H

H

{{

Vx

DFT

|0

|0

|0

|0

1 registrador

(t q-bits)

2 registrador(n q-bits)

|0 |1 |2 |3 |4 |5

Figura 4.1: Circuito quntico para achar a ordem de um inteiropositivo x mdulo N .

Isto explica a escolha de (4.1) para Vx. Classicamente, poderamos calcular su-cessivamente xj , para j comeando de 2 at chegarmos a j = r. Quanticamente,pode-se calcular todas as potncias de x com uma nica aplicao de Vx. No nvelquntico, todos os valores de j que produzem xj 1 mod N so conhecidos. Masesta informao no est totalmente disponvel no nvel clssico. Uma informaoclssica de um estado quntico obtida atravs de uma medida e, neste ponto,no ajudaria se medssemos o primeiro registrador, j que todos os estados dasuperposio (4.3) possuem igual amplitude. A primeira parte da estratgia paradeterminar r observar que o primeiro registrador dos estados (4.4) peridico.Ento, a informao que queremos um perodo.

Para facilitar os clculos, vamos medir o segundo registrador. Antes de fazer isto,vamos reescrever o estado |2, fatorando os termos iguais do segundo registrador.Como xj uma funo peridica com perodo r, vamos substituir j por ar + b naequao (4.3), onde 0 a (2t/r)1 e 0 b r1. Lembre-se que supomos quet = n e r uma potncia de 2, portanto r divide 2t. A equao (4.3) convertidaem

|2 = 12t

r1b=0

2t

r 1a=0

|ar + b

xb . (4.5)

No segundo registrador, substitumos xb por xar+b, j que xr 1 mod N . Agora, osegundo registrador medido. Qualquer resultado x0, x1, ..., xr1 pode ser obtidocom igual probabilidade. Suponha que o resultado xb0 . O estado do computadorquntico agora

|3 =

r

2t

2t

r 1a=0

|ar + b0

xb0 . (4.6)


Note que depois da medida, a constante renormalizada parar/2t, j que existem

2t/r termos na soma (4.6). A Figura 4.2 mostra a probabilidade de obtermos osestados da base computacional, medindo o primeiro registrador. A probabilidadeforma uma funo peridica com perodo r. Estes valores so zero, exceto para osestados |b0, |r + b0, |2r + b0, ..., |2t r + b0.

{

0b0 r + b0 2r + b0 3r + b0

r2t

r

Distribuio de probabilidades

Termos de |3

(1 registrador)

Figura 4.2: Distribuio de probabilidades de |3 medido na base com-putacional (para o caso b0 = 3 and r = 8). O eixo horizontal tem 2

t

pontos, o nmero de picos 2t/r e o perodo r.

Como podemos descobrir o perodo de uma funo eficientemente? A resposta a transformada de Fourier. A transformada de Fourier de uma funo peridica deperodo r uma nova funo com perodo proporcional a 1/r. Isto faz diferena paradeterminar r. A transformada de Fourier a segunda e ltima parte da estratgiausada por Shor. Todo o mtodo depende de um algoritmo quntico eficiente paracalcular a transformada de Fourier, que no est disponvel classicamente. NaSeo 4.5, mostraremos que a transformada de Fourier calculada eficientementenum computador quntico.

Exerccio 4.3 Mostre que o operador descrito em (4.1) unitrio.

Exerccio 4.4 Faa todos os clculos desta seo, no caso N = 15 e x = 2, deforma explcita. Todas as expresses devem ter os respectivos somatrios expandi-dos.

4.3. A TRANSFORMADA DE FOURIER QUNTICA DISCRETA 48

4.3 A Transformada de Fourier Quntica Discreta

A transformada de Fourier de uma funo F : {0, . . . , N 1} C uma novafuno F : {0, . . . , N 1} C definida por

F (k) =1N

N1j=0

e2piijk/NF (j). (4.7)

Podemos aplicar a transformada de Fourier ou em uma funo ou em um estadoda base computacional. A transformada de Fourier aplicada ao estado |k da basecomputacional {|0 , . . . , |N 1}

DFT(|k) = |k = 1N

N1j=0

e2piijk/N |j , (4.8)

onde o conjunto {|k : k = 0, . . . , N 1} forma uma nova base ortonormal. Atransformada de Fourier um operador linear unitrio; portanto, se sabemos comoele atua nos estados da base computacional, tambm sabemos como ele atua numestado genrico

| =N1a=0

F (a) |a .

A transformada de Fourier de | pode ser obtida atravs de (4.7) ou (4.8). Noresto do trabalho, vamos usar a ltima forma.

Para provar que {|k : k = 0, . . . , N 1} uma base ortonormal, i.e.,

k |k = kk,

podemos usar a identidade

1

N

N1j=0

e2piijk/N =

{1, se k um mltiplo de N0, caso contrrio,

(4.9)

que til no contexto da transformada de Fourier. fcil verificar que (4.9) verdadeira. Se k um mltiplo de N , ento e2piijk/N = 1, justificando o primeirocaso da identidade. Se k no um mltiplo de N , (4.9) verdade, mesmo se Nno for uma potncia de 2. A Figura 4.3 mostra cada termo e2piijk/N (j = 0, ..., 6)para o caso k = 1 e N = 7 como vetores num plano complexo. Note que a somados vetores deve ser zero pelo argumento de simetria: a distribuio dos vetores isotrpica. Usualmente, diz-se que a interferncia destrutiva neste caso. Usandoessa identidade, podemos definir a transformada de Fourier inversa, que similar a(4.8), porm com um sinal de menos no expoente. Note que DFT1 = DFT, jque DFT um operador unitrio.

Apresentaremos os detalhes de um circuito quntico para realizar a transformadade Fourier na Seo 4.5. Agora, continuaremos o processo de clculo da Figura 4.1.


2pi7

Re

Im

j = 0

j = 1

j = 2

j = 3

j = 4

j = 5

j = 6

Figura 4.3: Desenho dos vetores e2piij/7 (j = 0, ..., 6) no plano complexo.A soma desses vetores zero por argumentos de simetria. Este umexemplo da equao (4.9) para N = 7, k = 1.

Estamos prontos para achar o prximo estado do computador quntico: |4.Aplicando a transformada de Fourier inversa no primeiro registrador, usando aequao (4.8) e a linearidade da DFT, obtemos

|4 = DFT(|3)

=

r

2t

2t

r 1a=0

1

2t

2t1j=0

e2piij(ar+b0)/2t |j

xb0 .

Invertendo a ordem do somatrio, temos

|4 = 1r

2t1

j=0

12t/r

2t

r 1a=0

e2piija2t/r

e2piijb0/2t |j

xb0 . (4.10)

Usando (4.9), vemos que a expresso nos colchetes diferente de zero, se e somentese j = k2t/r com k = 0, ..., r 1. Quando j assume tais valores, a expresso noscolchetes igual a 1. Ento, temos

|4 = 1r

(r1k=0

e2piikr b0

k2tr) xb0 . (4.11)

Para acharmos r, a expresso |4 tem duas vantagens sobre a expresso |3 (equa-o (4.6)): r est no denominador do ket e o parmetro aleatrio b0 foi movido doket para o expoente, ocupando agora um lugar inofensivo. A Figura 4.4 mostraa distribuio de probabilidades de |4 medido na base computacional. Medindo


{

0 2t

r22tr

32tr

1r

2t

r

Distribuio de probabilidades

Termos de |4

(1 registrador)

Figura 4.4: Distribuio de probabilidades de |4 medida na base com-putacional. O eixo horizontal tem 2t pontos, apenas os termos no nulosso mostrados. O nmero de picos r e o perodo 2t/r.

o primeiro registrador, obtemos o valor k02t/r, onde k0 pode ser qualquer nmeroentre 0 e r1, com igual probabilidade (picos na Figura 4.4). Se obtivermos k0 = 0,no teremos nenhuma informao sobre r, e o algoritmo tem que ser rodado no-vamente. Se k0 6= 0, dividimos k02t/r por 2t, obtendo k0/r. Nem k0 nem r soconhecidos. Se k0 coprimo com r, simplesmente selecionamos o denominador.

Se k0 e r tm fator comum, o denominador da frao reduzida k0/r um fator der, mas no o prprio r. Suponha que o denominador r1. Seja r = r1r2. Agora, oobjetivo determinar r2, que a ordem de xr1 , mdulo N . Rodamos novamente aparte quntica do algoritmo para achar a ordem de xr1 . Se acharmos r2 na primeirarodada, o algoritmo pra; caso contrrio, o aplicamos recursivamente. O processorecursivo no longo, porque o nmero de iteraes menor ou igual a log2 r.

Como exemplo, tome N = 15 que o menor nmero composto no trivial. Oconjunto de nmeros menores que 15 e coprimos com 15 {1, 2, 4, 7, 8, 11, 13, 14}.Os elementos 4, 11 e 14 tm ordem 2 e os elementos 2, 7, 8 e 13 tm ordem 4.Portanto, em qualquer caso, r uma potncia de 2 e os fatores de N = 15 podemser encontrados num computador quntico com 8 q-bits. Os autores de [23] usamum computador quntico com 7 q-bits, pulando partes do algoritmo original.

Exerccio 4.5 Prove a eq. (4.9) usando a srie geomtrica:

1 + r + r2 + + rn1 = rn 1r 1 .

Descubra quem deve ser r e note que, para r = 1, deve-se usar o lado esquerdo daequao acima.

Exerccio 4.6 Prove que o conjunto {|k : k = 0, . . . , N 1} uma base orto-normal onde |k dado por (4.8).

4.4. GENERALIZAO POR MEIO DE UM EXEMPLO 51

Exerccio 4.7 Continuando o exerccio 4.4, faa todos os clculos desta seo,no caso N = 15 e x = 2, de forma explcita. Todas as expresses devem ter osrespectivos somatrios expandidos.

4.4 Generalizao por meio de um Exemplo

Nas sees precedentes, consideramos um caso especial quando a ordem r umapotncia de 2 e t = n (t o nmero de q-bits no primeiro registrador, veja naFigura 4.1, e n = log2N). Nesta seo, consideramos a fatorao de N = 21, que o prximo nmero composto no trivial depois de N = 15. Devemos escolher ttal que 2t esteja entre N2 e 2N2, o que sempre possvel [20]. Para N = 21, omenor valor de t 9. Este o exemplo mais simples permitido pelos vnculos, mas suficiente para mostrar todas as propriedades do algoritmo de Shor. O primeiropasso escolher x aleatoriamente, tal que 1 < x < N , e testar se x coprimo comN . Se no for, encontramos facilmente um fator de N pelo clculo do MDC(x,N).Se for, iniciamos a parte quntica do algoritmo. Suponha que x = 2 foi escolhido.O objetivo encontrar a ordem de x, que r = 6. O computador quntico inicializado no estado

|0 = |0 |0 ,onde o primeiro registrador tem t = 9 q-bits e o segundo tem n = 5 q-bits. Oprximo passo a aplicao de H9 sobre o primeiro registrador, gerando (vejaequao (4.2))

|1 = 1512

511j=0

|j |0 .

Em seguida, aplicando Vx (definido em (4.1)), obtemos

|2 = 1512

511j=0

|j 2j mod N=

1512

(|0 |1+ |1 |2+ |2 |4+ |3 |8+ |4 |16+ |5 |11+|6 |1+ |7 |2+ |8 |4+ |9 |8+ |10 |16+ |11 |11+|12 |1+ . . .

).

Note que a expresso acima tem o seguinte padro: o estado do segundo registradorde cada coluna o mesmo. Portanto, podemos rearranjar os termos de forma a


fatorar o segundo registrador:

|2 = 1512

[( |0+ |6+ |12+ . . .+ |504+ |510 ) |1+( |1+ |7+ |13+ . . .+ |505+ |511 ) |2+( |2+ |8+ |14+ . . .+ |506 ) |4+ (4.12)( |3+ |9+ |15+ . . .+ |507 ) |8+( |4+ |10+ |16+ . . .+ |508 ) |16+( |5+ |11+ |17+ . . .+ |509 ) |11 ].Esta caracterstica foi explicitada na equao (4.5). Como a ordem no umapotncia de 2, aqui existe uma pequena diferena: as primeiras duas linhas daequao (4.12) tm 86 termos, enquanto o restante delas tem 85.

Agora feita uma medida no primeiro registrador1, gerando um dos seguintesnmeros com igual probabilidade: {1, 2, 4, 8, 16, 11}. Suponha que o resultado damedida seja 2. Ento,

|3 = 186

(|1+ |7+ |13+ . . .+ |505+ |511) |2 . (4.13)

Observe que o estado |3 foi renormalizado para ser unitrio. No importa oresultado da medida; o que importa o padro peridico de (4.13). O perododo estado do primeiro registrador a soluo para o problema, e a transformadade Fourier pode revelar o valor deste perodo. Ento, o prximo passo aplicar atransformada de Fourier inversa no primeiro registrador de |3:

|4 = DFT(|3)

= DFT(

186

85a=0

|6a+ 1)|2

=1512

511j=0

([186

85a=0

e2pii6ja512

]e2pii

j512 |j

)|2 , (4.14)

onde usamos a equao (4.8) e rearranjamos as somas. A ltima equao similar equao (4.10), mas com uma importante diferena. Na Seo 4.2, assumimos que rdivide 2t. Isto no verdade nesse caso (6 no divide 512); portanto, no podemosusar a identidade (4.9) para simplificar os termos nos colchetes da equao (4.14).Esses termos nunca se anulam, mas a contribuio principal ainda em torno dej = 0, 85, 171, 256, 341, 427, que so obtidos de 512k0/6 para k0 de 0 at 5 (comparecom a discusso logo aps a equao (4.11)). Para nos convencermos, faamos o

1Como a medida sempre pode ser feita no final do algoritmo (veja [16], p. 186), este passo no necessrio, serve apenas para simplificar as expresses seguintes.


grfico da probabilidade de dar o resultado j (no intervalo de 0 at 511), medindoo primeiro registrador do estado |4. De (4.14), temos que a probabilidade

Prob(j) =1

512 86

85a=0

e2pii6ja512

2

. (4.15)

O grfico da Prob(j) mostrado na Figura 4.5. Vemos os picos em torno de j =0, 85, 171, 256, 341, 427, indicando alta probabilidade de dar um destes valores, oualgum valor muito prximo deles. No intervalo entre eles, a probabilidade quasezero. A largura dos picos depende de t (nmero de q-bits no primeiro registrador).O limite inferior de 2t N2 assegura uma alta probabilidade em medir um valorde j carregando a informao desejada. Uma anlise cuidadosa da expresso (4.15) feita em [15], e um estudo meticuloso da forma do pico feita em [9].

Vamos analisar os possveis resultados da medida. Se o resultado for j = 0 (pri-meiro pico), o algoritmo no revela o valor de r. Deve ser executado novamente. Es-colhamos x = 2 e executamos novamente a parte quntica do algoritmo. A probabi-lidade de dar j = 0 baixa: da equao (4.15) temos que Prob(0) = 86/512 0, 167.Agora suponha que o resultado foi j = 85 (ou qualquer valor no segundo pico). Di-vidimos por 512, resultando 85/512, que uma aproximao racional de k0/6, parak0 = 1. Como podemos obter r de 85/512?

O mtodo de aproximao por fraes contnuas permite-nos extrair a informa-o desejada. Uma frao contnua de um nmero racional j1/j2 tem a forma

j1j2

= a0 +1

a1 +1

...+ 1ap

,

usualmente representada por [a0, a1, ..., ap], onde a0 um inteiro no-negativo ea1, ..., ap so positivos. O q-simo convergente (0 q p) definido como umnmero racional [a0, a1, ..., aq]. Isto uma aproximao para j1/j2 e tem o deno-minador menor que j2. Este mtodo aplicado facilmente pela inverso da frao,seguido pela diviso inteira com resto racional. Invertendo 85/512, temos 512/85,que igual a 6 + 2/85. Repetimos o processo com 2/85 at obtermos o numerador1. O resultado

85

512=

1

6 + 142+ 1

2

.

Assim, os convergentes de 85/512 so 1/6, 42/253 e 85/512. Devemos selecionaros convergentes que tenham um denominador menor que N = 21 (j que r < N)2.Este mtodo fornece 1/6, e ento, r = 6. Checamos que 26 1 mod 21, e a partequntica do algoritmo termina com a resposta correta. A ordem r = 6 um nmeropar, portanto MDC(2(6/2)1, 21) fornece dois fatores no triviais de 21. Um clculo

2A desigualdade r (N) segue do teorema de Euler: x(N) 1 mod N , onde x um inteiropositivo coprimo com N e a funo totiente de Euler ((N) fornece o nmero de inteirospositivos menores que N , coprimos com N). A desigualdade (N) < N segue da definio de (veja [24], p. 492).


0

0.05

0.1

0.15

0 50 100 150 200 250 300 350 400 450 500

PSfrag

Prob(j)

j

Figura 4.5: Grfico de Prob(j) em funo de j. Compare o formato dospicos deste grfico com o formato dos picos do grfico da Figura 4.4.

direto mostra que qualquer resultado no segundo pico (digamos 81 j 89) produzo convergente 1/6.

Considere agora o terceiro pico, que corresponde a k0 = 2 da frmula k0/6.Aplicamos novamente o mtodo de aproximao por fraes contnuas, resultandoem 1/3, para qualquer j no terceiro pico (digamos 167 j 175). Neste caso,obtemos um fator de r (r1 = 3), j que 23 8 6 1 mod 21. Rodamos a partequntica do algoritmo novamente, para achar a ordem de 8. Obteremos r2 = 2.Logo, r = r1r2 = 3 2 = 6.

O quarto e quinto picos tambm fornecem fatores de r. O ltimo pico similarao segundo, resultando r diretamente.

A avaliao geral da probabilidade de sucesso a seguinte. A rea abaixo detodos os picos aproximadamente a mesma: 0, 167. O primeiro e o quarto picosso diferentes dos outros eles no so espalhados. Para calcular suas contribuiespara a probabilidade total, tomamos a base igual a 1. As reas embaixo do segundo,terceiro, quinto e ltimo picos so calculadas, adicionando a Prob(j), para j rodandoem torno do centro de cada pico. Ento, em aproximadamente 17% dos casos, oalgoritmo falha (1 pico). Em aproximadamente 33% dos casos, o algoritmo retornar de primeira (2 e 6 picos). Em aproximadamente 50% dos casos, o algoritmoretorna r na segunda rodada ou mais (3, 4 e 5 picos). Agora, vamos calcular aprobabilidade de achar r na segunda rodada. Para o 3 e 5 picos, o fator restante r2 = 2. O grfico equivalente para a Figura 4.5, neste caso, tem 2 picos, ento oalgoritmo retorna r2 em 50% dos casos. Para o 4 pico, o fator restante r = 3 eo algoritmo retorna r2 em 66,6% dos casos. Assim, o resultado

250%+66,6%3 de

50%, que igual a aproximadamente 22%. Resumindo, a probabilidade de sucessopara x = 2 em torno de 55%.

4.5. TRANSFORMADA DE FOURIER EM TERMOS DE PORTAS UNIVERSAIS 55

Exerccio 4.8 Use um sistema de computao algbrica para refazer o grfico daeq. (4.15).

Exerccio 4.9 Faa todos os clculos desta seo, no caso N = 35 e x = 2. Faao grfico da distribuio de probabilidades e avalie a chance do algoritmo de Shorencontrar o resultado correto.

4.5 Transformada de Fourier em termos de PortasUniversais

Nas sees precedentes, mostramos que o algoritmo de Shor um algoritmo probabi-lstico eficiente, assumindo que a transformada de Fourier poderia se

Documents

livro_cq_ver_2.pdf