Algoritmo de shor

Disponível somente no TrabalhosFeitos
  • Páginas : 95 (23613 palavras )
  • Download(s) : 0
  • Publicado : 23 de novembro de 2012
Ler documento completo
Amostra do texto
Algoritmo de Shor e sua aplica¸˜o ` fatora¸˜o de n´meros inteiros
ca a
ca
u
Adriana Xavier Freitas
Fevereiro 2010

Algoritmo de Shor e sua aplica¸˜o ` fatora¸˜o
ca a
ca
de n´ meros inteiros
u

Adriana Xavier Freitas
Orientador: Prof. Marcelo de Oliveira Terra Cunha

Disserta¸˜o
ca

apresentada

`
a

UNIVERSIDADE

FEDERAL DE MINAS GERAIS, como requisito
parcial para aobten¸˜o do grau de mestre em
ca
matem´tica.
a
Fevereiro de 2010

Aos meus pais e irm˜s.
a

Agradecimentos
A Deus por tudo que aconteceu em minha vida, permitindo que eu conseguisse realizar o meu sonho de estudar na UFMG e fazer mestrado com
bolsa.
Aos meus pais por todo amor que me dedicaram e pela compreens˜o da
a
minha ausˆncia em suas vidas.
e
As minhas irm˜s que eu muitoamo, em especial a Ayessa, raz˜o do meu
a
a
viver.
As minhas colegas de rep´ blica Neila e Adriana por terem tido paciˆncia
u
e
em me ouvir dizer in´ meras vezes nesses ultimos meses: ’ser´ que vou entrar
u
´
a
no doutorado?’ Em especial a Adriana por sempre me salvar na v´spera das
e
provas daquelas d´ vidas cruciais e pelo companheirismo desses 5 anos.
u
Ao H´lvecio meu amor queridoque sempre ameniza as saudades que sinto
e
da minha fam´
ılia, me compreende nas v´speras das provas e por todas as
e
figuras desse texto.
Ao Marcelo pela orienta¸˜o nesses ultimos 3 anos em especial pela sua
ca
´
paciˆncia e generosidade de ler o meu texto cheio de erros de portuguˆs e por
e
e
ter ajudado a torn´-lo algo digno de chamar de disserta¸˜o.
a
ca
Aos professores quepassaram pela minha vida, tantos que ´ imposs´
e
ıvel
citar seus nomes. Mas, n˜o posso me esquecer do Bernardo, sem ele hoje
a
n˜o estaria aqui. Foi ele que desde o segundo per´
a
ıodo da gradua¸˜o me
ca
incentivou a fazer mestrado, sempre que eu estava prestes a desistir por
causa das dificuldades conversava com ele e tinha ˆnimo para continuar.
a
Sem d´ vidas sem ele e a minha fam´ eu n˜oestaria aqui.
u
ılia
a
A todos os amigos da gradua¸˜o que hoje s˜o para mim mais que amigos,
ca
a
j´ fazem parte da minha fam´ se h´ um nome desse per´
a
ılia;
a
ıodo que n˜o posso
a
esquecer ´ o da Silviane, minha amiga e companheira para toda hora.
e
Aos amigos que fiz durante o mestrado que s˜o muito especiais.
a
A Cl´lia e a Cla´ dia. N˜o posso esquecer do pessoal da Olimp´
eu
a
ıada Mii

neira: Seme, F´bio, M´rio Jorge e todos os monitores que por a´ passaram.
a
a
ı
Saudades de todos. Aos integrantes da OBMEP, que s˜o muitos, por isso
a
nem me atrevo a citar nomes.
Aos funcion´rios do Departamento de Matem´tica, em especial ao Valda
a
ney e a Andr´a que sempre nos socorrem com as burocracias.
e
Ao CNPQ por ter me tornado um rica bolsista de mestradoe pelo incentivo ` pesquisa.
a
N˜o poderia esquecer do Lula por um unico motivo: ele apoiou a cria¸˜o
a
´
ca
da OBMEP.

ii

Resumo

O algoritmo de Shor ´ um algoritmo quˆntico que encontra com alta proe
a
babilidade a ordem de um elemento x ∈ Z∗ . Uma de suas aplica¸˜es ´ a
co e
N

constru¸˜o de um algoritmo que encontra fatores de N . Nos cap´
ca
ıtulos iniciaisabordaremos ferramentas necess´rias para o entendimento do algoritmo de
a
Shor, tais como: aritm´tica modular, algoritmos, fra¸˜es cont´
e
co
ınuas, conceitos
introdut´rios de computa¸˜o quˆntica e transformada quˆntica de Fourier.
o
ca
a
a
Nos cap´
ıtulos seguintes apresentamos o algoritmo de Shor e sua aplica¸˜o `
ca a
fatora¸˜o de n´ meros inteiros.
ca
u

iii

Abstract

Shor’salgorithm is a quantum algorithm that finds with high probability the
order of an element x ∈ Z∗ . One of its applications is the construction of
N
an algorithm that finds the factors of N . In the initial chapters we approach
necessary tools for the comprehension of Shor’s algorithm such as: modular
arithmetic, algorithms, continued fractions, basic concepts of quantum computing and Fourier...
tracking img