Laboratórios
O Algoritmo de Deutsch
Qui 25 Nov 2004 22:00 |
- Detalhes
- Categoria: Laboratório de Física Quântica
- Atualização: Quarta, 13 Janeiro 2010 23:47
- Autor: Mendonça
- Acessos: 17715
Este texto encerra a primeira rodada de um total de três artigos. Em cada um deles busquei mostrar para o leitor não especializado alguns resultados e conceitos de grande importância na física quântica.
O que acabamos de ver, foi o primeiro algoritmo de uma especialização da teoria quântica, hoje chamada computação quântica. Neste algoritmo, Deutsch demonstrou, com um exemplo simples, que computadores quânticos têm ampliado o poder computacional dos computadores clássicos. De fato, isso era algo esperado, pois sendo a física clássica uma particularização da física quântica, os computadores clássicos também deveriam ser limitações dos computadores quânticos.
Mas convenhamos, embora o Algoritmo de Deutsch mostre algo extremamente novo sobre o que os computadores quânticos podem fazer, descobir se uma função é contínua ou balanceada em 1 dia (em vez de 2 dias) é, no mínimo, uma aplicação "sem graça". Contudo, isso nao é regra para outros algoritmos da computação quântica moderna. Há, por exemplo, um algoritmo de fatoração devido a Shor [4]. Este, demonstra que é possível fatorar qualquer número inteiro em um tempo exponencialmente mais curto do que o requerido pelos algoritmos clássicos de fatoração; isso pode significar uma redução de milhares de anos de processamento clássico para alguns dias (ou até horas) de processamento quântico!
Quem conhece o protocolo de criptografia RSA, entende as implicações disso; toda a segurança desse esquema se sustenta no fato de que, para os computadores clássicos, é muito difícil (leva muito tempo) fatorar números inteiros muito grandes. Logo, computadores quânticos rodando o algoritmo de Shor são uma ameaça ao RSA. Porém, há ainda muito a ser feito até que um computador quântico capaz de rodar o algoritmo de Shor para números inteiros muito grandes se torne uma realidade (alguns físicos nem acreditam que isso seja possível), mas o importante é que, até o presente momento, ninguém encontrou uma barreira fundamental para refutar esse sonho. Portanto, continuamos sonhando.
Vale ainda salientar que a quebra do RSA não tem nada a ver com a criptografia quântica. Para essa última, nem computadores quânticos são uma ameaça. Por isso, alguns dizem tratar-se de um esquema absolutamente seguro, inquebrável. Talvez essa seja uma sentença muito forte, e na referência [5] você pode entender o porque.
Enfim, esperamos que esses primeiros artigos tenham sido úteis para mostrar o valor da teoria quântica. Esta não é um amontoado de fórmulas e abstrações vãs, mas uma ciência preciosa, que nos ensina a lidar (à nossa forma), com um mundo imperceptível aos nossos sentidos, mas incontestavelmente real.
Se você se sente convencido disto, o convite está feito para seguirmos adiante. A idéia agora é estabelecer em terreno mais firme (e isso pode significar um pouco mais matemático), as bases da física quântica. A teoria pura, independente de aplicações, também é bastante bela. Eu espero poder deixar essa "beleza intrínseca" à vista de quem quiser apreciá-la nos próximos artigos.
[1] J. Preskill, Physics 229: Advanced Mathematical Methods of Physics Quantum Computation and Information, http://www.theory.caltech.edu/people/preskill/ph229, California Institute of Technology (1998).
[2] M. A. Nielsen e I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press (2000).
[3] E. P. Wigner, The Unreasonable Effectiveness of Mathematics in the Natural Sciences, Communications in Pure and Applied Mathematics, vol. 13, No. I (Fevereiro 1960); edição online (http://www.dartmouth.edu/~matc/MathDrama/reading/Wigner.html).
[4] P. W. Shor, Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26, 1484 (1997).
[5] M. A. Nielsen, What’s wrong with those quantum cryptosystems?, http://www.qinfo.org/people/nielsen/blog/archive/000124.html, postado em blog em 17 de Agosto de 2004.
Este artigo encontra-se à disposição para download no formato PDF (117 Kb).
- << Anterior
- Próximo