Explicando o algoritmo de Shor de forma simples

Tentarei explicar a lógica por trás do famoso algoritmo de Shor, com um mínimo de fórmulas, e com muita explicação básica.

O Shor é aquele terrível algoritmo capaz de quebrar toda a criptografia do mundo atual com computadores quânticos. Imagine o poder de quebrar todas as transações bancárias do mundo? Será que isso é mesmo possível?

Há algumas pegadinhas também, que serão exploradas ao final do texto.

Este trabalho é inspirado em um artigo do prof. Scott Aaronson — link no final do texto.

1. Fatoração de primos

A criptografia dos dias de hoje é baseada na assimetria do problema da fatoração de números primos.

É muito fácil calcular 17*3 = 51. Mais difícil é, dado 51, encontrar 17*3.

Duvida? Gaste os próximos 5 minutos para encontrar os fatores primos de 6557.

Agora, faça a conta 79*83. Muito mais fácil, não?

Outro ponto a notar é que protocolos atuais utilizam centenas de dígitos. Imagine fatorar o número a seguir:

25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

2. A bela série de Euler

O matemático Leonard Euler tem tantas fórmulas e teoremas que é até difícil dar nome aos seus trabalhos. Esta fórmula vai fornecer uma forma alternativa de encontrar os fatores primos. Vejamos.

Imagine a série da potência de 2:
1, 2, 4, 8, 16, 32, 64, …

O que acontece se eu pegar a mesma série, módulo 5?
Dá:
[1, 2, 4, 3, 1, 2, 4, 3, 1, 2, 4, 3]

Obs. O módulo é o resto da divisão. 8 mod 5 = 3, porque a divisão de 8 por 5 dá 1 e sobram 3.

Note que a série acima é periódica. O [1, 2, 4, 3] se repete indefinidamente, com período 4.

A mesma série, módulo 15?
Dá:
[1, 2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8]

O período de repetição da série é 4 (seq 1, 2, 4, 8).

Há um padrão? Felizmente, Euler já descobriu o padrão há mais de 200 anos.

Dada a sequência: x mod N, x² mod N, x³ mod N, x⁴ mod N, …

Se N é o produto de dois primos p e q, e x não é divisível por p ou q, a sequência se repete com um período que divide (p-1)(q-1).

Ex. N =15. É fácil decompor em 3*5. p=3 e q =5. (p-1)(q-1) = 8.
Vimos acima que o período é 4.

Não é diretamente p ou q, mas dá uma dica boa de como proceder.

Ou seja, há uma forma alternativa de fatorar N em p e q.

Exercício. Use o método para encontrar os fatores de 221.

Isso dá:
[2, 4, 8, 16, 32, 64, 128, 35, 70, 140, 59, 118, 15, 30, 60, 120, 19, 38, 76, 152, 83, 166, 111, 1, 2, 4, 8, 16, 32, 64, 128, 35, 70, 140, 59, 118, 15, 30, 60]

Da série acima, o período é 24. Ou seja, 24 divide (p-1)(q-1). Testando várias alternativas, chego a p = 17 e q = 13. E, realmente, 24 divide (17–1)(13–1).

Uma conclusão parcial. O método acima pode ajudar, mas é muito complicado. O período pode ser perto de N, o que não vai ajudar em nada. É mais fácil ir testando várias alternativas. Há técnicas clássicas melhores, como o crivo de Erastótenes.

Isso, em computação clássica. Mas, e se eu tiver um computador quântico suficientemente poderoso?

3. Encontrar o período

Um bit clássico pode assumir valores 0 ou 1. Já um qubit, pode ficar na superposição desses estados. Dessa forma, uma quantidade de qubits pode representar um número exponencialmente maior de bits ao mesmo tempo.

A superposição e emaranhamento dos qubits são características dos computadores quânticos.

Em termos de circuito, uso portas Hadamard para colocar os qubits em superposição. Com isso, os qubits podem ficar em superposição para todas as alternativas de 1 a N.

Depois, utilizo uma função, uma caixa-preta, para codificar cada inteiro à sequência desejada b¹ mod N, b² mod N, b³ mod N, …

E posso encontrar o período, que é uma propriedade global, através da QFT — Quantum Fourier Transform.

A QFT é a versão computação quântica da DFT (Discrete Fourier Transform), e de seu primo rápido FFT (F de Fast).

Voltando mais ainda no conceito, a DFT é uma evolução da Série de Fourier, que decompõe qualquer série periódica num somatório de senos e cossenos. Cada seno e cosseno tem uma amplitude e uma frequência — e a frequência é inversamente proporcional ao período.

A FFT é largamente utilizada em processamento de sinais, para transformar um sinal qualquer no domínio do tempo para o domínio da frequência.

A FFT de uma senóide pura vai ser um pico, na frequência do sinal original.

O pulo do gato, o superpoder que faz toda a diferença, é a QFT, que faz o mesmo papel da DFT, porém, com um número exponencialmente menor de bits.

Depois disso, há uma série de outros truques para, a partir das informações encontradas, conseguir definir o período e os fatores primos da solução.

É uma técnica probabilística, no sentido de que serão necessárias algumas tentativas para gerar o resultado correto.

O tempo de execução do Shor varia polinomialmente com o número de bits, o que é um avanço enorme, sobre o tempo de execução exponencial do melhor algoritmo clássico.

4. Dificuldades

Algumas dificuldades.

Primeiro, os computadores quânticos ainda estão em sua infância. Os mais avançados, agora em 2021, têm cerca de 50 qubits no máximo.

Além disso, há o problema da correção de erros. Manipular os qubits é extremamente sensível, podendo ocorrer erros de decoerência, onde os mesmos deixam de estar emaranhados.

Algoritmos de correção de erros existem e estão sendo bastante estudados atualmente. Devido à correção de erros, há estimativas de que são necessárias centenas de qubits físicos para cada qubit lógico.

Outro ponto a considerar é a caixa-preta. Utilizo um número exponencialmente menor de qubits para representar a sequência inteira, e digo que o oráculo mapeia cada inteiro com o elemento da sequência. O oráculo deve ser muito especial: deve receber em paralelo os qubits e fazer as contas de forma eficiente.

Se o oráculo pegar o input em paralelo e calcular todas as alternativas classicamente, não há mais ganho em utilizar a abordagem acima.

É mais ou menos como varrer o problema para baixo do tapete. A esperança é que haja implementações eficientes da caixa-preta, e que, aliados ao resto do algoritmo de Shor, consigam bater os algoritmos clássicos.

Por fim, uma última consideração. Apesar da fatoração ser um problema difícil na prática, na teoria da complexidade este não é um problema NP-Completo. Ou seja, podem surgir algoritmos clássicos que tenham desempenho tão bom ou melhor do que o desempenho prometido pelo algoritmo de Shor.

É um tópico muito rico, e vale a pena estudar o mesmo mais a fundo.

Vide também:

Shtetl-Optimized “ Blog Archive “ Shor, I’ll do it (scottaaronson.com) https://informacaoquantica.wordpress.com/2020/08/27/por-que-a-complexidade-computacional-da-fatoracao-de-numeros-inteiros-e-expraizn/

Originally published at http://informacaoquantica.wordpress.com on February 3, 2021.

Project Manager on Analytics and Innovation. “Samurai of Analytics”. Passionate about Combinatorial Optimization, Philosophy and Quantum Computing.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store