quinta-feira, 10 de dezembro de 2009

Algoritmo de Shor Explicado - Fatorando Grandes Números

Há alguns dias, procurando material sobre computação quântica, achei um excelente texto explicando o funcionamento de um dos algoritmos mais conhecidos dessa natureza, utilizado para fatorar grandes números.

O artigo está em inglês, mas eu traduzi ele (de uma forma bem informal) e apresento ele aqui. Boa leitura.

Algoritmo de Shor Explicado - Fatorando Grandes Números

Tá, vamos lá. Digamos que você queira quebrar o sistema de criptografia RSA, PGP, ou qualquer outro sistema baseado em chave pública (na verdade, qualquer sistema que use um número/hash para verificação/encriptação de dados), para roubar algum banco, chantagear o presidente dos EUA, ler os e-mails comprometedores do seu chefe, não importa. Todos sabemos (ou pelo menos assim acredito) que quebrar a criptografia RSA se reduz à encontrar os fatores primos de um dado valor N.

Infelizmente, nós também sabemos que calcular todos os divisores possíveis em paralelo e então instantaneamente pegar a resposta correta não é exatamente a resposta que queremos alcançar. Vários textos na internet fazem uso da computação quântica como se ele fosse somente um computador que pode processar muito mais informações em paralelo do que os computadores determinísticos. E, mesmo que fosse assim, se você tentasse todos os possíveis divisores, ao fazer a leitura do sistema, ele te retornaria um número randômico, o que certamente não seria o número que você estava querendo.




O que isso significa é que, se nós quisermos um algoritmo rápido de fatoração, nós teremos que explorar algumas estruturas dentro do problema da fatoração: em outras palavras, algumas propriedades matemáticas da fatoração de forma a não tornar ele somente um "buscar uma agulha num palheiro" quântico.

Por sorte, o problema da fatoração têm várias propriedades que nos podem ser úteis. Deixe-me exemplificar algumas: Dado um número inteiro positivo N, você pode não saber sua fatoração exata, mas você têm como saber se o número N têm exatamente uma única fatoração. Difícil de entender? Então continue lendo.

No entanto, se você pega, por exemplo, um jogo de Sudoku e tenta resolver, à princípio você não têm como saber se ele não têm solução, se têm só uma solução ou se têm 200 milhões de soluções. E claro, saber que o jogo têm somente uma única solução possível também não nos ajudará em nada na busca da solução do problema. No entanto, essa uniquidade é um sinal de que o problema da fatoração pode conter outras propriedades matemáticas legais em torno da agulha. E realmente têm mesmo.

A propriedade explorada no algoritmo de Shor é, na verdade, uma redução do problema da fatoração em um outro, chamado periodicidade. Não se entendie, pois vou explicar como isso ocorre. Como exemplo, vamos olhar minha sequência numérica preferida desde que aprendi a multiplicar: as potências de dois.

1, 2, 4, 8, 16, 32, 64, 238, 256, 512, 1024, ...


Uma bonita sequência, não? E onde entra a periodicidade aí? Bom, façamos então o seguinte: pegar cada valor da sequência e dividir, por exemplo, por 15, e pegar seu resto. Em termos matemáticos, 2^x mod 15. Para nosso teste, vou gerar uma lista, conforme a seguir:

>>> [(2**x)%15 for x in range(21)]
[1, 2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8, 1]


Eu não sei se você percebeu mas, o resto da divisão nos fornece uma sequência periódica, cujo período é 4. Para outro exemplo, vamos olhar a seguinte expressão: 2^x mod 21:

>>> [(2**x)%21 for x in range(21)]
[1, 2, 4, 8, 16, 11, 1, 2, 4, 8, 16, 11, 1, 2, 4, 8, 16, 11, 1, 2, 4]


Dessa vez, nós pegamos uma sequência periódica cujo período é 6.

Agora, peguemos outras duas sequências: 2^x mod 8 e 2^x mod 16:

>>> [(2**x)%8 for x in range(21)]
[1, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

>>> [(2**x)%16 for x in range(21)]
[1, 2, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]


Para estes dois valores em particular, não há uma sequência periódica, pois a partir de um dado momento, a sequência converge para 0.

Bom, você deve estar derretendo sua cabeça: Há alguma regra geral com a qual nós podemos "prever" o período? Bom, eu acho que os matemáticos já tenham pensado sobre essa questão ...

Bem, eles pensaram, e um mátemático chamado Euler (eu adoro esse kra) descobriu um belo padrão. Peguemos um número qualquer N, composto por dois números primos, p e q, e considere a sequência ...

x mod N, x^2 mod N, x^3 mod N, x^4 mod N, ...

Tá, e qual é a mágica? Olhe bem: Quando o x fornecido não é divisível por p ou por q, a sequência acima irá se repetir com um período que eventualmente divide (p-1)(q-1).

Tomando o primeiro exemplo, N=15, os seus fatores primos são p=3 e q=5, então (p-1)(q-1)=8. E o período da sequência foi 4, que divide 8. Se N=21, seus fatores primos são p=3 e q=7, então (p-1)(q-1)=12. E, concluindo, o período foi 6, que é divisível por 12.

Agora, eu quero que você volte um pouco e raciocine um pouco sobre o que isso significa. em termos genéricos, se nós podemos encontrar o período da sequência ...

x mod N, x^2 mod N, x^3 mod N, x^4 mod N, ...

... então nós podemos aprender algo sobre os fatores primos de N!! Em particular, nós podemos descobrir um divisor de (p-1)(q-1). Agora, admitamos, não é a mesma coisa como aprender os fatores p e q, no entanto isso me garante que possa ser algo! No entanto, é mais do que isso! Isso nos mostra que, se pudermos descobrir randomicamente vários divisores de (p-1)(q-1) (por exemplo, tentando diferentes valores para x), então com muita probabilidade nós poderíamos colocar estes divisores juntos para descobrir o próprio (p-1)(q-1). E assim que descobrirmos (p-1)(q-1), nós poderemos usar alguns truques matemáticos para recuperar p e q, os fatores primos que estamos procurando.

Então, qual é o problema nisso? Bem, até a sequência eventualmente começar a se repetir, o número de passos antes que esta se repita pode ser tão grande quando o prórpio N, e N pode ter milhares ou milhões de dígitos. É por isto que encontrar o período não nos leva a algoritmos clássocos de fatoração mais rápidos.

Ah, mas nós temos um computador quântico! (Ou, pelo menos, acreditamos que temos um) Então, ainda há esperança. Então, imagine que possamos criar uma enorme superposição quântica usando todos os números em nossa sequência x mod N, x^2 mod N, etc. Então, há algumas operações que podemos fazer nessa superposição que poderia revelar o período.

O ponto chave é que nós não estaremos procurando uma agulha num palheiro de dimensões exponenciais, algo que talvez seja difícil até para um computador quântico descobrir. Em vez disso, devemos tentar encontrar o período da sequência, a qual é uma propriedade global para todos os números da sequência juntos.

Veja bem: Se você pensa na computação quântica em termos de "universos paralelos", já lhe adianto que não há uma forma fácil de detectar um universo único que seja diferente de todos os outros.

Então ... A tarefa que se interpõe entre nós e nossos fatores não é humanamente impossível. No entanto, se nós queremos fazer essa idéia da busca pelo período funcionar, nós precisaremos responder a duas questões:

1.: Usando um computador quântico, poderemos criar rapidamente uma superposição de estados de nossa sequência x mod N, x^2 mod N, x^3 mod N, etc?

2.: Supondo que, Sim, nós podemos construir esta superposição rapidamente, como nós poderemos descobrir o período?

Vamos então responder a primeira questão. Nós podemos certamente criar uma superposição com todos os números inteiros r, de 1 até N, ou mais. O problema é, dado um número r, como nós poderemos rapidamente computar x^r mod N? Se r é, por exemplo, o número 20 trilhões, nós teremos de multiplicar x por si mesmo 20 trilhões de vezes? Com certeza isso não seria muito rápido e, para nossa sorte, isso não é necessário. O que nós poderemos fazer é chamado repetição quadrática. Isso é facilmente entendível olhando o exemplo:

Suponha que tenhamos os seguintes valores: N=17, x=3 e r=14. O primeiro passo para fazer a repetição é representar r como uma soma de potências de 2:

r = 2^3 + 2^2 + 2^1.

Então ...

x^r = 3^14 = 3^((2^3) + (2^2) + (2^1)) = 3^2^2^2 + 3^2^2 + 3^2

Tendo isso em mente, podemos fazer todas as multiplicações do x^r mod N, sendo assim, prevenindo os números de crescer descontroladamente nos estágios iniciais. Isto nos leva ao resultado:

3^14 mod 17 = 2.

Ok, então nós podemos criar uma superposição de todos os pares de inteiros na forma (r, x^r mod N), onde r varia de 1 até N (ou menos). Mas, tendo uma superposição de todos os elementos de uma sequência periódica, como podemos extrair o período da sequência?

Boa pergunta!

Agora chegamos ao coração do negócio - A única parte do algoritmo quântico de Shor que depende realmente da mecânica quântica. Para recuperar o período da superposição, não podemos ler diretamente a superposição, pois ela colapsará para um estado randômico. No entanto, Shor demonstrou que é possível fazê-lo usando algo chamado quantum Fourier transform ou em português bem dizido, transformada quântica de fourier. O problema agora é explicar "como" funciona a QFT sem usar nenhum conceito matemático. Mas vamos tentar ...

Para exemplificarmos, peguemos como exemplo um experimento feito nos anos 70, onde várias pessoas são colocadas em uma sala, sem relógios e luz solar. No decorrer de algumas semanas, as pessoas vão gradualmente mudando seu ritmo diário de um ciclo de 24 horas para ciclos maiores, de 26, 27, 28 e por aí vai. Um dia, essas pessoas acordam às às 9h da manhã, no outro dia às 11h e depois à 1h da tarde, e assim sucessivamente. Então, se nada atrapalhar, eles uma hora vão voltar a acordar às 9h da manhã, completando um ciclo.

Calma, a parte doida da explicação ainda está por vir. Agora, digamos que hoje eu, que faço parte do experimento, acordei às 5h da tarde. Com esse fato, somente, o que você pode concluir à respeito de quão longo meu dia é?

Nada, não é mesmo? A única coisa que eu posso inferir é que não estou mais em um ciclo de 24 horas, já que não acordo no mesmo horário sempre. Agora uma coisa. Não importa qual fosse o ciclo de horas que eu estivesse, em qualquer outro ciclo de horas que não fosse o que eu sigo, eu iria em algum momento voltar a acordar na mesma hora inicial.

Beleza, até aí tudo bem, não é? Agora, imagine que neste quarto onde eu estou as paredes estão cobertas com vários relógios analógicos. No entanto, estes não são relógios comuns. Primeiro, eles marcam somente as horas. Segundo, cada relógio segue um ciclo diferente: um, por exemplo, completa sua volta em 17 horas; outro às 22 horas e um ainda, faz seu ciclo em 24.7 horas, e muitos outros em várias outras contagens. Agora imagine que abaixo de cada um desses relógios há uma folha com uma agulha marcadora ao centro. Quando eu entrei a primeira vez nessa sala, todos eles marcavam o mesmo lugar, o centro da sua respectiva folha. E como tarefa, sempre que acordar, a primeira coisa que devo fazer é mover o marcador de cada um desses relógios em um centímetro na direção que o ponteiro do relógio está apontando.



Agora, uma pergunta. Examinando os marcadores na sala, é possível descobrir qual é o ciclo de horas que eu estou seguindo?

Sim, por mais estranho que possa parecer, é possível, se você lembrar do que escrevi logo ali atrás. Suponhamos que eu siga um ciclo de 26 horas. O que acontecerá na folha do relógio que têm um ciclo de 24 horas? Não é difícil perceber que as marcações seguirão um movimento periódico. Cada dia que eu acordo e marco a folha, eu estarei acordando em uma hora diferente, pois meu ciclo não é sincronizado com este e, eventualmente, todos estes movimentos em direções diferentes se cancelarão uns aos outros, levando o marcador a chegar novamente ao centro da folha.

Por outro lado, o que acontecerá no relógio que têm o ciclo de 26 horas? A resposta será diferente pois, até onde meu ciclo é sincronizado com precisão ao ciclo de 26 horas, sempre que eu acordar o ponteiro do relógio estará apontando na mesma direção que estava da última vez em que eu acordei. E assim será, até que o marcador nem mais esteja dentro da folha.

Isso significa, então, que bastaria eu olhar para o marcador que mais se afastou do ponto de início para saber em qual ciclo de horas eu me encontro. Em outras palavras, eu posso inferir o período da sequência periódica da minha vida (profundo ...).

Isto é, basicamente, o significado da transformada quântica de Fourier. Bem, pra ser um pouco mais preciso, a transformada quântica de Fourier é uma transformação linear (entenda como transformação unitária) que mapeia um vetor de números complexos em outro vetor de números complexos. O vetor de entrada é um vetor não nulo que corresponde à todas as marcações de horas do momento em que eu acordei, enquanto o vetor de saída registra todas as posições dos marcadores em todas as folhas. Então, o que nós conseguimos no final é uma transformação linear que mapeia um estado quântico onde se encontra codificada uma sequência periódica em outro estado quântico que codifica o período da sequência citada.

Outra maneira de pensar nisso é em termos da interferência. Eu penso que, a chave para o uso da mecânica quântica - e o que faz a diferença entre esta e a teoria clássica da probabilidade - é que, enquanto as probabilidades são semrpe não-negativas, amplitudes na mecânica quântica podem ser positivas, negativas, e até mesmo complexas. E por causa disso, as amplitudes correspondem a diferentes formas de pegar uma resposta que "interfira destrutivamente" e cancele todas as outras respostas não consonantes.

E é exatamente o que faz o algoritmo de Shor. Cada "universo paralelo", correspondendo a um elemento da sequência, contribui com alguma amplitude à todos os "universos paralelos", correspondendo a um possível período da sequência. O fato é que, para todos os períodos que não sejam o verdadeiro, estas contribuições de amplitude apontarão para diferentes direções, e se cancelarão mutuamente. Somente para o período verdadeiro as contribuições dos diferentes universos irão, todos, apontar para a mesma direção. E é assim que, quando fizermos a medição, ao final, encontraremos o período verdadeiro com uma probabilidade bastante alta de sucesso.

Então, é isso. Se você esperava uma implementação em C (ou Python) do algoritmo, infelismente vc terá de continuar nesse site ou neste site para ver o código. Pelo menos agora você têm um pouco mais de entendimento de como ele funciona. Só não vá usar seu computador quântico para quebrar criptografia de banco por aí, viu?

Fontes:

Shor, I'll do it
http://en.wikipedia.org/wiki/Shor%27s_algorithm

Referências:

http://www.arxiv.org/abs/quant-ph/9508027

http://alumni.imsa.edu/%7Ematth/quant/299/paper/index.html
http://homepages.cwi.nl/%7Erdewolf/publ/qc/survey.ps
http://www.cs.berkeley.edu/%7Evazirani/f04quantum/notes/lec9.ps
http://www.theory.caltech.edu/people/preskill/ph229/notes/chap6.ps
http://www-users.cs.york.ac.uk/%7Eschmuel/comp/comp.html
http://www.cs.ucr.edu/%7Eneal/1996/cosc185-S96/shor/high-level.html
http://people.ccmr.cornell.edu/%7Emermin/qcomp/chap3.pdf
http://www.arxiv.org/abs/quant-ph/0303175
http://www.arxiv.org/abs/quant-ph/0010034
http://www.cs.princeton.edu/theory/complexity/quantumchap.pdf