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 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.
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 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 15 {\displaystyle 15} em 3 × 5 {\displaystyle 3\times 5} , 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 15 {\displaystyle 15} foi realizada com qubits de estado sólido. Mais tarde, também em 2012, a fatoração de 21 {\displaystyle 21} foi alcançada. Em 2016, a fatoração de 15 {\displaystyle 15} 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.
O problema que estamos tentando resolver é: dado um número composto ímpar N {\displaystyle N} , encontre seus fatores inteiros. Para conseguir isso, o algoritmo de Shor consiste em duas partes:
Redução clássica
Um algoritmo de fatoração completo é possível se formos capazes de fatorar eficientemente um N {\displaystyle N} arbitrário em apenas dois inteiros p {\displaystyle p} e q {\displaystyle q} maiores que 1, já que, se p {\displaystyle p} ou q {\displaystyle q} 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 N {\displaystyle N} é par, caso em que 2 {\displaystyle 2} é trivialmente um fator. Vamos, portanto, assumir que N {\displaystyle N} é ímpar para o restante desta discussão. Depois, podemos usar algoritmos clássicos eficientes para verificar se N {\displaystyle N} é uma potência de um primo. Para potências de primos, existem algoritmos clássicos de fatoração eficientes; portanto, o restante do algoritmo quântico pode assumir que N {\displaystyle N} não é uma potência de primo.
Sub-rotina quântica de determinação de ordem
O objetivo da sub-rotina quântica do algoritmo de Shor é, dados inteiros coprimos N {\displaystyle N} e 1 < a < N {\displaystyle 1<a<N} , encontrar a ordem r {\displaystyle r} de a {\displaystyle a} módulo N {\displaystyle N} , ou seja, o menor inteiro positivo r {\displaystyle r} tal que a r ≡ 1 ( mod N ) {\displaystyle a^{r}\equiv 1{\pmod {N}}} . Para conseguir isso, o algoritmo de Shor usa um circuito quântico envolvendo dois registradores. O segundo registrador usa n {\displaystyle n} qubits, onde n {\displaystyle n} é o menor inteiro tal que N ≤ 2 n {\displaystyle N\leq 2^{n}} , ou seja, n = ⌈ log 2 N ⌉ {\displaystyle n=\left\lceil {\log _{2}N}\right\rceil } . O tamanho do primeiro registrador determina a precisão da aproximação produzida pelo circuito. Pode-se mostrar que usar 2 n {\displaystyle 2n} qubits fornece precisão suficiente para encontrar r {\displaystyle r} . O circuito quântico exato depende dos parâmetros a {\displaystyle a} e N {\displaystyle N} , que definem o problema. A seguinte descrição do algoritmo usa a notação bra-ket para denotar os estados quânticos, e ⊗ {\displaystyle \otimes } para denotar o produto tensorial.
O gargalo
O gargalo no tempo de execução do algoritmo de Shor é a exponenciação modular quântica, a qual é muito mais lenta do que a transformada de Fourier quântica e o pré/pós-processamento clássicos. Existem várias abordagens para construir e otimizar circuitos para a exponenciação modular. A abordagem mais simples e (atualmente) mais prática é mimetizar circuitos aritméticos convencionais com portas reversíveis, começando com somadores de propagação de transporte (ripple-carry adders). Conhecer a base e o módulo da exponenciação facilita otimizações adicionais. Circuitos reversíveis tipicamente usam em torno da ordem de n 3 {\displaystyle n^{3}} portas para n {\displaystyle n} qubits. Técnicas alternativas melhoram assintoticamente as contagens de portas usando transformadas de Fourier quânticas, mas não são competitivas com menos de 600 qubits devido a constantes muito altas.
Os algoritmos de Shor para os problemas do logaritmo discreto e para a determinação de ordem são instâncias de um algoritmo que resolve o problema de determinação de período. Todos os três são instâncias do problema do subgrupo oculto.
O algoritmo de Shor para logaritmos discretos
Dado um grupo G {\displaystyle G} com ordem p {\displaystyle p} e um gerador g ∈ G {\displaystyle g\in G} , suponha que sabemos que x = g r ∈ G {\displaystyle x=g^{r}\in G} , para algum r ∈ Z p {\displaystyle r\in \mathbb {Z} _{p}} , e desejamos calcular r {\displaystyle r} , que é o logaritmo discreto: r = log g ( x ) {\displaystyle r={\log _{g}}(x)} . Considere o grupo abeliano Z p × Z p {\displaystyle \mathbb {Z} _{p}\times \mathbb {Z} _{p}} , onde cada fator corresponde à adição modular de valores. Agora, considere a função: Isso nos dá um problema abeliano do subgrupo oculto, onde f {\displaystyle f} corresponde a um homomorfismo de grupos. O núcleo corresponde aos múltiplos de ( r , 1 ) {\displaystyle (r,1)} . Portanto, se pudermos encontrar o núcleo, seremos capazes de encontrar r {\displaystyle r} . Existe um algoritmo quântico para solucionar esse problema. Este algoritmo, tal como o de fatoração, é de autoria de Peter Shor e ambos são implementados criando uma superposição por meio de portas Hadamard, seguida pela implementação de f {\displaystyle f} como uma transformada quântica, finalizando com uma transformada de Fourier quântica. Devido a isso, o algoritmo quântico para calcular o logaritmo discreto também é ocasionalmente referido como "Algoritmo de Shor".
