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 , o algoritmo de Shor é executado em tempo polinomial, o que significa que o tempo gasto é polinomial em .Veja também Tempo pseudo-polinomial. Ele requer portas lógicas quânticas da ordem de usando multiplicação rápida, ou mesmo 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 geral do corpo de números, que funciona em tempo subexponencial: .

Viabilidade e impacto thumb|upright=1.2|Diagrama apresentando a criptografia e a descriptografia de um documento usando criptografia assimétrica. Algumas formas de criptografia (incluindo a criptografia assimétrica) correm o risco de serem quebradas por futuros computadores quânticos.

Assumindo que um computador quântico com um número suficiente de qubits possa operar sem sucumbir ao ruído quântico e a outros fenômenos de decoerência quântica, então o algoritmo de Shor poderia ser usado para quebrar esquemas de criptografia de chave pública, tais como:

O esquema RSA A troca de chaves Diffie-Hellman em corpos finitos A troca de chaves Diffie-Hellman de curva elíptica

O RSA pode ser quebrado se a fatoração de grandes inteiros for computacionalmente viável. Até onde se sabe, isso não é possível usando computadores clássicos (não quânticos); não se conhece nenhum algoritmo clássico que consiga fatorar inteiros em tempo polinomial. No entanto, o algoritmo de Shor mostra que a fatoração de inteiros pode ser feita com um circuito de complexidade polinomial num computador quântico ideal. Assim, pode ser viável derrotar o RSA construindo um computador quântico grande o suficiente. Esse foi um poderoso motivador para o design e a construção de computadores quânticos e para o estudo de novos algoritmos de computação quântica. Ele também facilitou a pesquisa de novos criptossistemas que sejam seguros contra computadores quânticos, coletivamente chamados de criptografia pós-quântica (PQC).

Implementação física A partir de 2026, com as altas taxas de erro dos computadores quânticos e o número limitado de qubits físicos disponíveis para a correção de erros quânticos, as demonstrações em laboratório do algoritmo de Shor obtêm resultados corretos apenas em uma fração das tentativas e só tiveram sucesso com pequenos semiprimos.

Em 2001, o algoritmo de Shor foi demonstrado por um grupo na IBM, que fatorou em , usando uma implementação baseada em RMN de um computador quântico com sete qubits. Após a implementação da IBM, dois grupos independentes implementaram o algoritmo de Shor usando qubits fotônicos, enfatizando que o entrelaçamento de múltiplos qubits foi observado durante a execução dos circuitos do algoritmo de Shor. Em 2012, a fatoração de foi realizada com qubits de estado sólido. Mais tarde, também em 2012, a fatoração de foi alcançada. Em 2016, a fatoração de foi realizada novamente usando qubits de íons aprisionados. Contudo, nenhuma dessas demonstrações atende aos requisitos do algoritmo de Shor genuíno: elas compilam o circuito usando conhecimento prévio da solução, e algumas simplificaram o algoritmo de uma forma que o torna equivalente ao lançamento de uma moeda.

Algoritmo O problema que estamos tentando resolver é: dado um número composto ímpar , encontre seus fatores inteiros.

Para conseguir isso, o algoritmo de Shor consiste em duas partes:

Uma redução clássica do problema de fatoração ao problema de determinação de ordem. Esta redução é semelhante à usada para outros algoritmos de fatoração de inteiros, como o crivo quadrático. Um algoritmo quântico para resolver o problema de determinação de ordem.

Redução clássica Um algoritmo de fatoração completo é possível se formos capazes de fatorar eficientemente um arbitrário em apenas dois inteiros e maiores que 1, já que, se ou não forem primos, o algoritmo de fatoração poderá, por sua vez, ser executado neles até que restem apenas primos.

Uma observação básica é que, usando o algoritmo de Euclides, podemos sempre calcular o MDC (maior divisor comum) entre dois inteiros de forma eficiente. Em particular, isso significa que podemos verificar eficientemente se é par, caso em que é trivialmente um fator. Vamos, portanto, assumir que é ímpar para o restante desta discussão. Depois, podemos usar algoritmos clássicos eficientes para verificar se é uma potência de um primo. Para potências de primos, existem algoritmos clássicos de fatoração eficientes;Por exemplo, calculando as primeiras raízes de , e.g., com o método de Newton e verificando o resultado inteiro quanto à sua primalidade (Teste de primalidade AKS). portanto, o restante do algoritmo quântico pode assumir que não é uma potência de primo.

Se esses casos fáceis não produzirem um fator não trivial de , o algoritmo prossegue para lidar com o caso restante. Escolhemos um número inteiro aleatório . Um possível divisor não trivial de pode ser encontrado calculando (o MDC), o que pode ser feito clássica e eficientemente usando o algoritmo de Euclides. Se isso produzir um fator não trivial (significando que ), o algoritmo termina, e o outro fator não trivial é . Se um fator não trivial não foi identificado, isso significa que e a escolha de são coprimos, então está contido no grupo multiplicativo de inteiros módulo , possuindo um inverso multiplicativo módulo . Assim, tem uma ordem multiplicativa módulo , o que significa que

e é o menor inteiro positivo que satisfaz essa congruência.

A sub-rotina quântica encontra . Pode-se ver pela congruência que divide , denotado como . Isso pode ser fatorado usando a diferença de quadrados: Como fatoramos a expressão desta maneira, o algoritmo não funciona para ímpar (porque deve ser um número inteiro), o que significa que o algoritmo teria que ser reiniciado com um novo . Daqui em diante, podemos, portanto, assumir que é par. Não pode ser o caso em que , já que isso implicaria , o que implicaria contraditoriamente que seria a ordem de , a qual já definimos ser . Neste ponto, pode ou não ser o caso de . Se não dividir , isso significa que somos capazes de encontrar um fator não trivial de . Calculamos:

Se , então a afirmação era verdadeira, e um fator não trivial de não pode ser alcançado a partir de , exigindo que o algoritmo reinicie com um novo . Caso contrário, encontramos um fator não trivial de , sendo o outro fator , e o algoritmo é concluído. Para este passo, também é equivalente calcular ; isso produzirá um fator não trivial se for não trivial, e não produzirá se for trivial (onde ).

O algoritmo reescrito de forma sucinta é o seguinte: seja ímpar e não uma potência de primo. Queremos extrair dois fatores não triviais de . Escolha um número aleatório . Calcule , o máximo divisor comum de e . Se , então é um fator não trivial de , com o outro fator sendo , e terminamos. Caso contrário, use a sub-rotina quântica para encontrar a ordem de . Se for ímpar, volte para a etapa 1. Calcule . Se for não trivial, o outro fator é e terminamos. Caso contrário, volte para a etapa 1.

Foi demonstrado que há grande probabilidade de sucesso após algumas execuções. Na prática, uma única chamada à sub-rotina de determinação de ordem quântica é suficiente para fatorar completamente com probabilidade muito alta de sucesso se for usada uma redução mais avançada.

Sub-rotina quântica de determinação de ordem O objetivo da sub-rotina quântica do algoritmo de Shor é, dados inteiros coprimos e , encontrar a ordem de módulo , ou seja, o menor inteiro positivo tal que . Para conseguir isso, o algoritmo de Shor usa um circuito quântico envolvendo dois registradores. O segundo registrador usa qubits, onde é o menor inteiro tal que , ou seja, . O tamanho do primeiro registrador determina a precisão da aproximação produzida pelo circuito. Pode-se mostrar que usar qubits fornece precisão suficiente para encontrar . O circuito quântico exato depende dos parâmetros e , que definem o problema. A seguinte descrição do algoritmo usa a notação bra-ket para denotar os estados quânticos, e para denotar o produto tensorial.

O algoritmo consiste em dois passos principais:

Usar a estimativa de fase quântica com uma matriz unitária representando a operação de multiplicação por (módulo ), e o estado de entrada (onde o segundo registrador é formado por qubits). Os autovalores deste codificam informações sobre o período, e pode ser visto como uma soma dos seus autovetores. Graças a essas propriedades, o estágio da estimativa de fase quântica dá como saída um inteiro aleatório na forma para algum aleatório. Usar o algoritmo de frações contínuas para extrair o período dos resultados da medição obtidos no estágio anterior. Este é um procedimento de pós-processamento (com um computador clássico) dos dados medidos a partir dos estados quânticos de saída, de forma a recuperar o período.

A conexão com a estimativa de fase quântica não foi discutida na formulação original do algoritmo de Shor, mas foi posteriormente proposta por Alexei Kitaev.

Estimativa de fase quântica frame|Sub-rotina quântica no algoritmo de Shor

Em geral, o algoritmo de estimativa de fase quântica, para qualquer unitário e autoestado tal que , envia estados de entrada para estados de saída próximos de , onde é uma superposição de inteiros próximos a . Em outras palavras, ele envia cada autoestado de para um estado contendo informações próximas ao autovalor associado. Para os propósitos da determinação de ordem quântica, empregamos esta estratégia usando o unitário definido pela ação:A ação de em estados com não é crucial para o funcionamento do algoritmo, mas precisa ser incluída para garantir que a transformação geral seja uma porta quântica bem definida. Implementar o circuito para estimativa de fase quântica com requer ser capaz de implementar de forma eficiente as portas . Isso pode ser alcançado através da exponenciação modular, que é a parte mais lenta do algoritmo.

A porta assim definida satisfaz , o que imediatamente implica que seus autovalores são as -ésimas raízes da unidade . Além disso, cada autovalor tem um autovetor da forma , e esses autovetores são tais que: onde a última identidade segue da fórmula da série geométrica, que implica .

Usar a estimativa de fase quântica em um estado de entrada retornaria, então, o inteiro com alta probabilidade. Mais precisamente, o circuito de estimativa de fase quântica envia para de modo que a distribuição de probabilidade resultante tenha pico em torno de , com . Essa probabilidade pode ser feita tão próxima de 1 quanto se queira, usando qubits extras.

Aplicando o raciocínio acima à entrada , a estimativa de fase quântica, portanto, resulta na evolução: