Em 2001, o grupo do físico Isaac Chuang, da Universidade de Stanford, conseguiu construir e rodar um computador quântico capaz de descobrir quais são os dois fatores primos do número 15! Sim, a resposta deste cálculo é 3 e 5, mas o dito computador teve que ser rodado várias vezes, pois às vezes ele obtinha o resultado errado! (Um número primo é aquele que só é divisível por 1 e por ele mesmo, como 2, 3, 5, 7, 11, 13, 17, etc.)
Por que governos de todo o mundo estão investindo milhões de dólares para construir uma máquina capaz de fatorar o número 15, e às vezes errar? Bem, a idéia é que, aos poucos, essas máquinas possam fatorar o número 21, o número 187, até chegar em um número como o RSA-129, que tem 129 dígitos, e aparece na figura abaixo, juntamente com seus dois fatores primos.
E daí? Bem, o primeiro ponto é que é muito difícil achar os fatores primos de um número como o RSA-129. Em 1994, mais de 600 pessoas de 24 países participaram com seus computadores de um esforço que durou 8 meses, e finalmente fatoraram o RSA-129, e com isso conseguiram decifrar uma mensagem secreta gerada por pesquisadores do MIT, nos Estados Unidos.
Chegamos então ao segundo ponto: essa dificuldade de fatorar números (tente achar os fatores primos de um número pequeno, como 437) é o princípio mais usado em criptografia para cifrar mensagens secretas, por exemplo em governos e em bancos. A idéia é a seguinte: Astrobigo quer passar uma mensagem telefônica secreta para Biboca amanhã, sem que um eventual grampo possa decifrar a mensagem. Assim, hoje, ele se encontra com ela e lhe passa o número P-64 (o primeiro fator primo da figura acima). Amanhã, ele pega sua mensagem, transforma em números, e multiplica por P-65, o segundo fator primo da figura. Aí ele manda esta mensagem cifrada juntamente com o número RSA-129. Biboca então pega o RSA-129, divide por P-64, e encontra a chave para decifrar a mensagem. O agente que está fazendo o grampo não conseguirá decifrar a mensagem, pois demoraria uns oito meses para ele fatorar o RSA-129.
Está claro que o RSA-129 já não pode mais ser usado, mas o que se utiliza hoje são números com 300 dígitos, impossíveis de serem fatorados em uma vida humana com as técnicas atuais. Notem que é fácil, a partir de dois primos, como 19 e 23, calcular o produto 437, mas a operação inversa é bem mais difícil. Descobrir dois números primos como P-64 e P-65 não é tão difícil, e a partir daí é fácil gerar RSA-129, mas a operação inversa é bem mais difícil.
Pois muito bem: se o PC no qual você está agora funcionasse de maneira essencialmente quântica, você poderia fatorar em pouco tempo um número de 300 dígitos! Ou seja, se os chineses construírem tal computador antes que os americanos, os primeiros terão acesso a segredos de estado dos segundos! Então dá para entender porque tanto dinheiro está sendo investido nisso, inclusive no Brasil.
Agora precisamos explicar como funciona um computador quântico. Há dois pontos essenciais. O primeiro é que os bits quânticos são mais gerais do que os bits clássicos. Ou seja, um bit clássico, desses que são usuais em todos os computadores que usamos, tem apenas dois estados, usualmente designados por “0” e “1”. Na realidade, o “0” e “1” são estados magnéticos localizados em um ponto na memória do computador, assim podemos chamá-los de “S” (sul) e “N” (norte).
Na física quântica, porém, vale o chamado “princípio quântico de superposição”: dados dois estados possíveis, a soma ponderada deles também é um estado possível. Assim, por exemplo, a•N + b•S também é um estado possível, onde a e b são quaisquer números complexos que satisfazem a² + b² = 1. Ou seja, se ao invés de usar um sistema clássico, como uma fita magnética, se utilizar por exemplo o núcleo de um átomo, podem-se codificar valores intermediários entre N e S, o que a princípio torna a computação bem mais poderosa. Essa vantagem, porém, é perdida ao se constatar que quando se faz uma medição quântica, os únicos resultados possíveis são N e S. Ou seja, mesmo que eu codifique meu bit quântico em um estado intermediário, na hora de medir só poderei obter N ou S, com determinadas probabilidades (que dependem do estado escolhido).
Esse primeiro ponto é às vezes chamado de paralelismo quântico. Por exemplo, considere três bits quânticos, cada um representando o dígito “1”: N•N•N. Suponha agora que transformemos cada um desses bits em uma superposição: (N+S)•(N+S)•(N+S). Note porém que, se fizermos as multiplicações, este estado global pode ser visto como representando oito números diferentes: NNN + NNS + NSN + NSS + SNN+ SNS + SSN + SSS. Assim, fazendo operações em três sistemas quânticos, podemos computar o resultado de uma função para oito valores de entrada, de maneira paralela (ao mesmo tempo). Porém, se quisermos resgatar o resultado final da computação para esses oito números, só conseguiremos medir três números (um para cada sistema quântico), e ainda assim com uma certa probabilidade. Ou seja, a vantagem inicial do paralelismo é perdida no final, com as medições.
Há porém um segundo ponto essencial, que dá uma vantagem para a computação quântica. Este ponto é a não-localidade quântica, que estudamos nos textos “Teorema de Bell para Crianças” e “Astrobigobaldo quer Informação Instantânea” . Duas partículas do computador quântico podem ser colocados em um estado “emaranhado”, e com isso eles adquirem uma individualidade holística, de tal forma que não se pode atribuir um estado quântico puro a apenas uma das partículas.
O que acontece quando o estado de duas partículas se torna emaranhado? Já vimos que não se pode transmitir informação instantaneamente. Mas pode-se alterar o estado global (envolvendo os dois bits quânticos) a partir de manipulações em apenas uma das partículas. É como se o estado global fosse um disco de cartolina preso em um arame e livre para girar em torno do arame. Mexendo em uma das pontas do disco faz o disco girar, e isso altera o que pode acontecer no outro lado do disco. São esses tipos de manipulações que trazem a vantagem da computação quântica.
Em 1994, Peter Shor demonstrou como uma computação quântica pode acelerar o cálculo do problema da fatoração de um número. Figurativamente, podemos dizer que ele mostrou como “girar” o problema em uma direção apropriada (como o disco de cartolina), fazer o cálculo de maneira mais eficiente, e depois girar de volta para obter o resultado, a partir de uma medição quântica. Como o resultado de tal medição quântica é probabilista, o algoritmo de Shor dará vários resultados errados, até acertar. Isso não é um problema, pois é fácil checar para saber se a resposta obtida está correta.
Por fim, seria preciso dizer algo sobre porque o cálculo mencionado acima (após “girar” os estados emaranhados) é mais eficiente. Isso tem a ver com semelhanças entre, por um lado, os estados ondulatórios quânticos e sua evolução no tempo, e por outro a natureza do algoritmo para fatorar números grandes. Ambos envolvem periodicidades.
Suponha que tenhamos uma onda que sobe e desce, sobe e desce. Suponha também que o que nos interessa é a freqüência da onda, e não como cada ponto sobe e desce. Assim, ao invés de ficar medindo posições, é bem mais prático usar um instrumento que meça diretamente as freqüências. Seria mais ou menos isso que o algoritmo quântico permite fazer de forma eficiente: ao invés de trabalhar com listas de números (análogas a posições), “gira-se” o estado envolvendo os bits quânticos (como com o disco de cartolina), medem-se as periodicidades dos números (análogas às freqüências das ondas), e depois utiliza-se essa informação para gerar o resultado da computação.
Apesar dos avanços teóricos relacionados à computação quântica, ainda não se sabe o que pode ser conseguido na prática. O problema é que quanto mais bits quânticos são colocados no computador, maior é a influência deletéria das flutuações ambientais. Vimos esse fenômeno de “decoerência” no texto “A Fronteira entre o Quântico e o Clássico” . É por isso que, até hoje, o maior número fatorado por um computador quântico é apenas 15.