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

== Fatorando em computadores quânticos: o algoritmo de Shor ==

 

 

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.