Breve introdução à computação quântica/Algoritmos quânticos: diferenças entre revisões

Saltar para a navegação Saltar para a pesquisa
[revisão pendente][revisão pendente]
 
== Fatorando em computadores quânticos: o algoritmo de Shor ==
 
Em 1994, Peter ShortsShor descreveu um algoritmo quântico que resolve o problema da fatoração em primos em tempo polinomial. Esse algoritmo foi batizado como "Algoritmo de Shor" e é o mais importante resultado obtido até agora na computação quântica. O resultado de Shor foi o principal motivo que alavancou o interesse do estudo da computação quântica ao redor do mundo. A seguir será dada uma breve noção do que vem a ser o algoritmo.
 
Uma forma ingênua de fatorar um número inteiro <math>n</math> é baseada em checar o resto da divisão de <math>n</math> por algum número <math>p</math> menor que a raiz quadrada de <math>n</math>. Se o resto é <math>0</math>, concluí-se que <math>p</math> é um fator. Este método é de fato muito ineficiente: com um computador que fazer testes para <math>10^{10}</math> <math>p'\text{s}</math> por segundo (isto é mais rápido que qualquer computador já construído), o tempo médio para encontrar o fator de um número de <math>60</math> dígitos (decimais) excederia a idade do universo.
Utilizador anónimo

Menu de navegação