Algoritmo de Shor

O algoritmo de Shor é um algoritmo quântico para encontrar os fatores primos de um inteiro. Foi desenvolvido em 1994 pelo matemático americano Peter Shor. É um dos poucos algoritmos quânticos conhecidos com aplicações potenciais convincentes e fortes evidências de aceleração superpolinomial em comparação com os melhores algoritmos clássicos (não quânticos) conhecidos. No entanto, superar os computadores clássicos exigirá computadores quânticos com milhões de qubits devido à sobrecarga causada pela correção de erros quânticos. Shor propôs múltiplos algoritmos semelhantes para resolver o problema da fatoração, o problema do logaritmo discreto e o problema de determinação de período. "Algoritmo de Shor" geralmente se refere ao algoritmo de fatoração, mas pode se referir a qualquer um dos três algoritmos. O algoritmo do logaritmo discreto e o algoritmo de fatoração são instâncias do algoritmo de determinação de período, e todos os três são instâncias do problema do subgrupo oculto. Num computador quântico, para fatorar um inteiro N {\displaystyle N} , o algoritmo de Shor é executado em tempo polinomial, o que significa que o tempo gasto é polinomial em log ⁡ N {\displaystyle \log N} . Ele requer portas lógicas quânticas da ordem de O ( ( log ⁡ N ) 2 ( log ⁡ log ⁡ N ) ( log ⁡ log ⁡ log ⁡ N ) ) {\displaystyle O((\log N)^{2}(\log \log N)(\log \log \log N))} usando multiplicação rápida, ou mesmo O ( ( log ⁡ N ) 2 ( log ⁡ log ⁡ N ) ) {\displaystyle O((\log N)^{2}(\log \log N))} usando o algoritmo de multiplicação assintoticamente mais rápido atualmente conhecido, devido a Harvey e van der Hoeven, demonstrando assim que o problema da fatoração de inteiros está na classe de complexidade BQP. O algoritmo de Shor é assintoticamente mais rápido que o algoritmo de fatoração clássico mais escalável, o crivo...