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, o algoritmo de Shor é executado em tempo polinomial, o que significa que o tempo gasto é polinomial em log⁡N. Ele requer portas lógicas quânticas da ordem de 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)) 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: O(e1.9(log⁡N)1/3(log⁡log⁡N)2/3).

Viabilidade e impacto

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 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 em 3×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 foi realizada com qubits de estado sólido. Mais tarde, também em 2012, a fatoração de 21 foi alcançada. Em 2016, a fatoração de 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.

Algoritmo

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

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

  1. 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.
  2. 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 N arbitrário em apenas dois inteiros p e q maiores que 1, já que, se p ou 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 é par, caso em que 2 é trivialmente um fator. Vamos, portanto, assumir que N é ímpar para o restante desta discussão. Depois, podemos usar algoritmos clássicos eficientes para verificar se 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 não é uma potência de primo.

Se esses casos fáceis não produzirem um fator não trivial de N, o algoritmo prossegue para lidar com o caso restante. Escolhemos um número inteiro aleatório 2≤a<N. Um possível divisor não trivial de N pode ser encontrado calculando gcd⁡(a,N) (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 gcd⁡(a,N)≠1), o algoritmo termina, e o outro fator não trivial é N/gcd⁡(a,N). Se um fator não trivial não foi identificado, isso significa que N e a escolha de a são coprimos, então a está contido no grupo multiplicativo de inteiros módulo N, possuindo um inverso multiplicativo módulo N. Assim, a tem uma ordem multiplicativa r módulo N, o que significa que

ar≡1(modN),

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

A sub-rotina quântica encontra r. Pode-se ver pela congruência que N divide ar−1, denotado como N∣ar−1. Isso pode ser fatorado usando a diferença de quadrados:N∣(ar/2−1)(ar/2+1). Como fatoramos a expressão desta maneira, o algoritmo não funciona para r ímpar (porque ar/2 deve ser um número inteiro), o que significa que o algoritmo teria que ser reiniciado com um novo a. Daqui em diante, podemos, portanto, assumir que r é par. Não pode ser o caso em que N∣ar/2−1, já que isso implicaria ar/2≡1(modN), o que implicaria contraditoriamente que r/2 seria a ordem de a, a qual já definimos ser r. Neste ponto, pode ou não ser o caso de N∣ar/2+1. Se N não dividir ar/2+1, isso significa que somos capazes de encontrar um fator não trivial de N. Calculamos: d=gcd⁡(N,ar/2−1). Se d=1, então a afirmação N∣ar/2+1 era verdadeira, e um fator não trivial de N não pode ser alcançado a partir de a, exigindo que o algoritmo reinicie com um novo a. Caso contrário, encontramos um fator não trivial de N, sendo o outro fator N/d, e o algoritmo é concluído. Para este passo, também é equivalente calcular gcd⁡(N,ar/2+1); isso produzirá um fator não trivial se gcd⁡(N,ar/2−1) for não trivial, e não produzirá se for trivial (onde N∣ar/2+1).

O algoritmo reescrito de forma sucinta é o seguinte: seja N ímpar e não uma potência de primo. Queremos extrair dois fatores não triviais de N.

  1. Escolha um número aleatório 1<a<N.
  2. Calcule K=gcd⁡(a,N), o máximo divisor comum de a e N.
  3. Se K≠1, então K é um fator não trivial de N, com o outro fator sendo N/K, e terminamos.
  4. Caso contrário, use a sub-rotina quântica para encontrar a ordem r de a.
  5. Se r for ímpar, volte para a etapa 1.
  6. Calcule g=gcd⁡(N,ar/2+1). Se g for não trivial, o outro fator é N/g 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 N 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 N e 1<a<N, encontrar a ordem r de a módulo N, ou seja, o menor inteiro positivo r tal que ar≡1(modN). Para conseguir isso, o algoritmo de Shor usa um circuito quântico envolvendo dois registradores. O segundo registrador usa n qubits, onde n é o menor inteiro tal que N≤2n, ou seja, n=⌈log2N⌉. O tamanho do primeiro registrador determina a precisão da aproximação produzida pelo circuito. Pode-se mostrar que usar 2n qubits fornece precisão suficiente para encontrar r. O circuito quântico exato depende dos parâmetros a e N, 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:

  1. Usar a estimativa de fase quântica com uma matriz unitária U representando a operação de multiplicação por a (módulo N), e o estado de entrada |0⟩⊗2n⊗|1⟩ (onde o segundo registrador é |1⟩ formado por n qubits). Os autovalores deste U codificam informações sobre o período, e |1⟩ 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 jr22n para algum j=0,1,...,r−1 aleatório.
  2. Usar o algoritmo de frações contínuas para extrair o período r 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

Sub-rotina quântica no algoritmo de Shor

Em geral, o algoritmo de estimativa de fase quântica, para qualquer unitário U e autoestado |ψ⟩ tal que U|ψ⟩=e2πiθ|ψ⟩, envia estados de entrada |0⟩|ψ⟩ para estados de saída próximos de |ϕ⟩|ψ⟩, onde ϕ é uma superposição de inteiros próximos a 22nθ. Em outras palavras, ele envia cada autoestado |ψj⟩ de U 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:U|k⟩={|ak(modN)⟩0≤k<N,|k⟩N≤k<2n.A ação de U em estados |k⟩ com N≤k<2n 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 U requer ser capaz de implementar de forma eficiente as portas U2j. Isso pode ser alcançado através da exponenciação modular, que é a parte mais lenta do algoritmo.

A porta assim definida satisfaz Ur=I, o que imediatamente implica que seus autovalores são as r-ésimas raízes da unidade ωrk=e2πik/r. Além disso, cada autovalor ωrj tem um autovetor da forma |ψj⟩=r−1/2∑k=0r−1ωr−kj|ak⟩, e esses autovetores são tais que:1r∑j=0r−1|ψj⟩=1r∑j=0r−1∑k=0r−1ωrjk|ak⟩=|1⟩+1r∑k=1r−1(∑j=0r−1ωrjk)|ak⟩=|1⟩, onde a última identidade segue da fórmula da série geométrica, que implica ∑j=0r−1ωrjk=0.

Usar a estimativa de fase quântica em um estado de entrada |0⟩⊗2n|ψj⟩ retornaria, então, o inteiro 22nj/r com alta probabilidade. Mais precisamente, o circuito de estimativa de fase quântica envia |0⟩⊗2n|ψj⟩ para |ϕj⟩|ψj⟩ de modo que a distribuição de probabilidade resultante pk≡|⟨k|ϕj⟩|2 tenha pico em torno de k=22nj/r, com p22nj/r≥4/π2≈0.4053. Essa probabilidade pode ser feita tão próxima de 1 quanto se queira, usando qubits extras.

Aplicando o raciocínio acima à entrada |0⟩⊗2n|1⟩, a estimativa de fase quântica, portanto, resulta na evolução: |0⟩⊗2n|1⟩=1r∑j=0r−1|0⟩⊗2n|ψj⟩→1r∑j=0r−1|ϕj⟩|ψj⟩. Ao medir o primeiro registrador, agora temos uma probabilidade balanceada de 1/r para encontrar cada |ϕj⟩, e cada uma delas fornece uma aproximação inteira de 22nj/r, a qual pode ser dividida por 22n para se obter uma aproximação decimal para j/r.

Algoritmo de frações contínuas para recuperar o período

Em seguida, aplicamos o algoritmo de frações contínuas para encontrar inteiros b e c, onde b/c fornece a melhor aproximação fracionária para a aproximação medida no circuito, para b,c<N com b e c sendo coprimos. O número de qubits no primeiro registrador, 2n, que determina a exatidão da aproximação, garante que bc=jr, desde que a melhor aproximação da superposição de |ϕj⟩ tenha sido medida (o que pode ser tornado arbitrariamente provável usando bits extras e truncando a saída). Contudo, embora b e c sejam coprimos, pode ser o caso que j e r não o sejam. Por causa disso, b e c podem ter perdido alguns fatores que estavam contidos em j e r. Isso pode ser remediado reexecutando a sub-rotina de ordem quântica um número arbitrário de vezes, para produzir uma lista de aproximações em frações: b1c1,b2c2,…,bscs, onde s é o número de vezes que a sub-rotina foi executada. De cada ck podem ter sido removidos fatores diferentes, porque o circuito (provavelmente) terá medido valores distintos possíveis para j. Para recuperar o verdadeiro valor de r, podemos calcular o mínimo múltiplo comum (MMC) de cada ck: mmc⁡(c1,c2,…,cs). O mínimo múltiplo comum será a ordem r do inteiro original a com alta probabilidade. Na prática, uma única execução da sub-rotina quântica é em geral suficiente caso se utilize um pós-processamento mais avançado.

Escolhendo o tamanho do primeiro registrador

A estimativa de fase requer a escolha do tamanho do primeiro registrador para determinar a exatidão do algoritmo, e para a sub-rotina quântica do algoritmo de Shor, 2n qubits são suficientes para garantir que a sequência de bits (bitstring) ideal medida na estimativa de fase (isto é, o |k⟩ onde k/22n é a aproximação mais exata da fase advinda da estimativa de fase) permitirá que o valor real de r seja recuperado.

Cada |ϕj⟩ antes da medição no algoritmo de Shor representa uma superposição de inteiros aproximando 22nj/r. Deixe |k⟩ representar o inteiro ideal em |ϕj⟩. O teorema a seguir garante que o algoritmo das frações contínuas irá recuperar j/r a partir de k/22n:

Teorema — Se j e r são inteiros de n bits, e |jr−ϕ|≤12r2 então o algoritmo de frações contínuas executado sobre ϕ recuperará tanto jgcd⁡(j,r) quanto rgcd⁡(j,r).

Como k é a bitstring ótima da estimativa de fase, k/22n tem uma exatidão de 2n bits em relação a j/r. Logo: |jr−k22n|≤122n+1≤12N2≤12r2 o que implica que o algoritmo de frações contínuas irá recuperar j e r (ou eles com o seu máximo divisor comum já extraído).

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 n3 portas para 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.

Determinação de período e logaritmos discretos

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 com ordem p e um gerador g∈G, suponha que sabemos que x=gr∈G, para algum r∈ℤp, e desejamos calcular r, que é o logaritmo discreto: r=logg(x). Considere o grupo abeliano ℤp×ℤp, onde cada fator corresponde à adição modular de valores. Agora, considere a função:

f:ℤp×ℤp→G;f(a,b)=gax−b.

Isso nos dá um problema abeliano do subgrupo oculto, onde f corresponde a um homomorfismo de grupos. O núcleo corresponde aos múltiplos de (r,1). Portanto, se pudermos encontrar o núcleo, seremos capazes de encontrar 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 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".

O problema da determinação de ordem também pode ser visto como um problema do subgrupo oculto. Para visualizar isto, considere o grupo de inteiros sob a operação de adição, e para um dado a∈ℤ tal que ar=1, considere a função:

f:ℤ→ℤ;f(x)=ax,f(x+r)=f(x).

Para qualquer grupo abeliano finito G, há um algoritmo quântico que soluciona o subgrupo oculto para G em tempo polinomial.

Ver também