Breve introdução à computação quântica/Algoritmos quânticos

Pode-se encontrar uma tarefa que um computador quântico realizará melhor do que um computador clássico? A resposta para esta questão é, como nos mostram os estudiosos de computação quântica, sim. É apresentada, a seguir, uma ideia geral de um dos algoritmos quânticos mais importantes, o algoritmo de Shor.

Fatorando em computadores quânticos: o algoritmo de Shor

Em 1994, Peter Shor descreveu um algoritmo quântico que resolve o problema da fatoração em primos em tempo polinomial. Esse algoritmo foi batizado como "Algoritmo de Shor" e é o mais importante resultado obtido até agora na computação quântica. O resultado de Shor foi o principal motivo que alavancou o interesse do estudo da computação quântica ao redor do mundo. A seguir será dada uma breve noção do que vem a ser o algoritmo.

Uma forma ingênua de fatorar um número inteiro $n$ é baseada em checar o resto da divisão de $n$ por algum número $p$ menor que a raiz quadrada de $n$. Se o resto é $0$, concluí-se que $p$ é um fator. Este método é de fato muito ineficiente: com um computador que fazer testes para $10^{10}$ $p'{\text{s}}$ por segundo (isto é mais rápido que qualquer computador já construído), o tempo médio para encontrar o fator de um número de $60$ dígitos (decimais) excederia a idade do universo.

Ao invés deste método de divisão ingênuo, computadores quânticos contam com uma técnica levemente diferente para realizar fatorização eficiente. Realmente, é possível mostrar que fatorar um número pode ser relacionado ao problema de avaliar o período de uma função. Para explicar como este método funciona, toma-se um exemplo simples: imagine que se quer encontrar os fatores primos de $n=15$. Para fazê-lo, toma-se um número aleatório a menor que $n$, por exemplo $a=7$, e define-se a função $f(x)=7^{x}mod15$. A matemática nos diz que $f(x)$ é periódica e que seu período $r$ pode ser relacionado com os fatores de $15$. Em nosso exemplo, pode-se checar que o período é $r=4$ ($f(x)$ assume os valores $1,7,4,13,1,7,4,\ldots$ quando $x=0,1,2,3,4,5,6,\ldots$ respectivamente). Com essa informação, computar os fatores de $n$ apenas requer que seja avaliado o máximo divisor comum de $n$ e $a^{\frac {r}{2}}\pm 1$. Em nosso exemplo, o cálculo de do máximo divisor entre $15$ e $50=7^{\frac {4}{2}}+1$ (ou $48=7^{\frac {4}{2}}-1$) retorna, de fato, o valor $5$ (ou $3$), que é um dos fatores primos de $15$.

Obviamente, computadores clássicos não podem realizar este método: encontrar o período de $f(x)$ requer que avalie-se esta função muitas vezes. De fato, os matemáticos nos dizem que o número médio de avaliações requeridas para se achar o período é da mesma ordem do número de divisões necessárias com o método ingênuo que foi descrito primeiramente. Com um computador quântico, a situação é completamente diferente: colocando um registrador quântico em uma superposição de estados representando $0,1,2,3,4,\ldots$ é possível computar em um único passo os valores de $f(0),f(1),f(2),\ldots .$ Estes valores são codificados em estados superpostos de um registrador quântico, e encontrar o período a partir deles requer outro passo (conhecido como transformada de Fourier quântica), que pode também ser executado muito eficientemente em um computador quântico , e então, encontram-se os fatores do número original. O que põe em risco os sistemas de criptografia atuais, baseados em chaves.

Criptografia quântica

O propósito da criptografia é transmitir informação de tal forma que o acesso a ela seja restrito inteiramente a um destinatário específico. Atualmente, os métodos de criptografia mais utilizados são baseados em chaves de bits suficientemente longas, e a cifragem/ decifragem do texto só pode ser feita de posse dessa chave. Uma vez que a chave esteja definida, a comunicação subsequente envolve o envio de criptogramas sobre um canal público o qual é vulnerável a todos os observadores. Entretanto, existe o problema de que, mesmo mantendo a mensagem criptografada, deve-se mandar a chave através de meios convencionais, também. Logo, nenhum sistema clássico de criptografia baseado em chaves é 100% seguro, pois a chave poderia ser descoberta, e fatorada.

Este módulo tem a seguinte tarefa pendente: Inserir a Figura 6: Criptografia quântica e o espião.

Contudo, se, por um lado, a computação quântica parece estar querendo colaborar com espiões e terroristas, por outro lado também, é possível utilizá-la para tornar invioláveis as mensagens trocadas entre computadores. De fato, ao interceptar uma mensagem clássica, um espião precisa descobrir quais são os bits que estão sendo transmitidos de um computador a outro. Descobrir o valor dos bits significa medi-los de algum modo. Na computação quântica, entretanto, o que se troca são q-bits, e a medição do estado de um q-bit acarreta uma perturbação grande demais para permanecer oculta. Ou seja, o processo de espionagem leva à descoerência (figura 6), o que pode ser quantificado de modo preciso. Alguém até poderia espionar, mas não passaria desapercebido. Estas ideias podem ser levadas a cabo com todo detalhe, de modo a produzir um esquema de transmissão segura de informação quântica. Inclusive, já existem experiências reais onde se troca, com absoluta segurança, informação quântica. Do exposto se conclui que a criptografia quântica é uma área florescente.

Um aspecto interessante da troca segura de informação quântica se refere à impossibilidade genérica de se copiar qubits com absoluta fidelidade. Isto se expressa matematicamente pelo teorema da não clonagem. No caso clássico, é fácil clonar informação, como no caso das máquinas de xerox ou copiadoras de CDs. No caso quântico, entretanto, o teorema da não clonagem impede a cópia de qubits. Caso contrário, seria possível elaborar um número suficientemente grande de cópias de um dado qubit, usando isto para descobrir seu estado sem nenhuma perturbação. Ou seja, se poderia medir o estado do qubit efetuando medidas de suas cópias e não dele próprio, evitando a descoerência. Na analogia do jogo de cara ou coroa, se repetiria o jogo copiando o estado da moeda em pleno voo e avaliando o resultado. Caso fosse encontrado o valor "cara" em 40% das vezes e o valor "coroa" em 60%, a conclusão seria que a moeda original estaria descrita pelo qubit composto por 40% de cara e 60% de coroa. Esta conclusão não implicaria em nenhuma perturbação do estado da moeda, já que foram as suas cópias que foram medidas! Entretanto, o teorema da não clonagem descarta esta experiência: não é possível copiar informação quântica com absoluta fidelidade, e sem perturbar o estado original.

Para se ter uma ideia do quanto a área da criptografia quântica está evoluindo, a empresa NEC em 2004 conseguiu realizar com sucesso um experimento no qual a geração contínua de uma chave criptográfica quântica permitiu o envio de informações num canal de dados completamente seguro. A geração de chaves foi feita utilizando uma rede óptica como as que existem atualmente (cabos de fibra óptica), à velocidade de 13 Kbps por uma distância de 16 Km. Ao que tudo indica a NEC pretende lançar em pouco tempo, um produto comercial que utiliza esta técnica.

O algoritmo de Grover

Além da criptografia quântica, existem aplicações da computação quântica ao problema da busca em bancos de dados. Um exemplo a este respeito é fornecido pelos programas de busca na Internet. O algoritmo de Grover nos proporciona um método quântico de acelerar o processo de procura em bancos de dados. No caso do algoritmo de Grover, o ganho não é tão espetacular quanto no caso do algoritmo de Shor. A título de comparação, se o número de etapas envolvidas no algoritmo clássico de busca for 1000, então esta mesma busca poderá ser efetuada com o algoritmo de Grover com um número aproximado de 32 etapas. Mesmo assim, trata-se de um avanço respeitável, levando em conta os terabits em bancos de dados da Internet.