O algoritmo polinomial de Shor para fatoraÃÃo em um computador quÃntico

AUTOR(ES)
DATA DE PUBLICAÇÃO

2003

RESUMO

Sistemas de criptografia largamente difundidos como o RSA fundamentam a sua eficiÃncia na suposiÃÃo de que, em termos prÃticos, à impossÃvel fatorar nÃmeros inteiros suficientemente grandes em uma escala de tempo aceitÃvel. Mais precisamente, nÃo existem, atà o momento, algoritmos de fatoraÃÃo em tempo polinomial que possam ser implementados nos atuais computadores. Dentre os algoritmos conhecidos, o mais eficiente requer um tempo computacional de ordem exponencial na quantidade de dÃgitos binÃrios do nÃmero a ser fatorado. Em 1994, baseado nos trabalhos anteriores de Benioff, Bennett, Deutsch, Feynman e Simon, dentre outros, Peter Shor apresentou um algoritmo de fatoraÃÃo que requer assintoticamente uma quantidade em ordem polinomial de passos em um computador quÃntico para fatorar um nÃmero inteiro de tamanho arbitrÃrio. Esse algoritmo ao invÃs de abordar o problema de decompor tal nÃmero em dois fatores nÃo triviais pelo mÃtodo direto de divisÃes sucessivas, utiliza o problema equivalente de encontrar a ordem de um certo inteiro modulo o nÃmero fatorado, onde esse inteiro à escolhido aleatoriamente relativamente primo com o nÃmero fatorado. Shor faz uso de um algoritmo quÃntico para calcular essa ordem. A computaÃÃo quÃntica revela um paradigma computacional bastante adverso da computaÃÃo clÃssica. Enquanto esta Ãltima à realizada atravÃs de operaÃÃes binÃrias determinÃsticas com base na lÃgica booleana clÃssica, a computaÃÃo quÃntica fundamenta as suas operaÃÃes nos postulados que descrevem o comportamento quÃntico da matÃria. Portanto, à probabilÃstica no seu modus operandi. Essa diferenÃa entre os formalismos lÃgicos da computaÃÃo clÃssica e da computaÃÃo quÃntica à um reflexo direto da natureza dos sistemas fÃsicos que sÃo utilizados para implementar concretamente cada uma dessas computaÃÃes. Esta dissertaÃÃo apresenta o algoritmo de Shor para fatoraÃÃo em um computador quÃntico. Na seqÃÃncia, introduzimos no capÃtulo 1 alguns conceitos bÃsicos da computaÃÃo clÃssica com o objetivo de criar um ambiente de idÃias favorÃvel à apresentaÃÃo da computaÃÃo quÃntica como uma extensÃo, tÃo natural quanto possÃvel, do modelo clÃssico computacional. Assim, no capÃtulo 2, apresentamos as bases do formalismo matemÃtico que modela a computaÃÃo quÃntica, atendo-nos apenas aos aspectos conceituais que sÃo, direta ou indiretamente, aplicados na descriÃÃo do algoritmo de Shor. Os capÃtulos 3 e 4 sÃo dedicados à apresentaÃÃo do algoritmo de fatoraÃÃo de Shor, feita em duas partes. A primeira diz respeito a parte nÃo quÃntica e aborda os aspectos algÃbricos do algoritmo. TambÃm à demonstrado o teorema que assegura a viabilidade probabilÃstica da soluÃÃo desse problema. No capÃtulo 4, apresentamos a parte quÃntica do algoritmo de Shor. O ponto alto da dissertaÃÃo à alcanÃado mostrando-se como encontrar a ordem de um inteiro mÃdulo o nÃmero a ser fatorado relativamente primo com este, conciliando o algoritmo quÃntico com uma interpretaÃÃo clÃssica de seus dados de saÃda, mediante o uso da expansÃo de um nÃmero racional em fraÃÃes contÃnuas

ASSUNTO(S)

algoritmo polinomial - shor computador quÃntico matematica fatoraÃÃo

ACESSO AO ARTIGO

Documentos Relacionados