2  Computação Quântica

2.1  Fundamentos da Mecânica Quântica

   (Topo)

A mecânica quântica surgiu como uma forma de explicar os fenômenos da dualidade onda-partícula. No final do século XIX e início do século XX, experimentos mostraram que a luz, antes considerada uma onda, admitia caracteristícas corpusculares (de partícula). Outros experimentos mostravam que a matéria, já há muito tempo considerada composta de partículas indivisíveis, assumia comportamento ondulatório. A solução foi um modelo que explicava, ao mesmo tempo, os comportamentos ondulatório e corpuscular da matéria e da energia [6].

A explicação, de forma simplificada, é que uma partícula é descrita por uma função de estado Ψ que assume comportamento ondulatório, de forma que a posição da partícula está “distribuída” pelo espaço como uma onda. No entanto, ao medir sua posição, a partícula não pode estar em dois lugares ao mesmo tempo ou distribuída pelo espaço (pois é uma partícula). Nesta situação, dizemos que ocorre o colapso da função de onda, isto é, imediatamente após a medida, a função de onda passa a indicar somente o estado medido. A explicação dada a este fenômeno é que o observador sempre afeta o experimento, de forma que é impossível medir propriedades de uma partícula sem alterar seu estado. [24].

A mecânica quântica admite diversas interpretações, determinísticas ou não, mas na prática, o comportamento de uma partícula pode ser considerado aleatório. Um experimento que busca medir a posição de uma partícula tem probabilidade |Ψ(x)|2 de encontrá-la na posição x [10].

2.2  Q-Bits e o Computador Quântico

   (Topo)

A diferença entre a computação “clássica” e a quântica é análoga à entre as mecânicas clássica e quântica. Na mecânica clássica, uma partícula admite posição bem definida, que podemos medir sem alterar seu comportamento, enquanto na quântica há uma função de estado da posição, que colapsa ao ser medida. Analogamente, na computação clássica, um conjunto de n bits assume um valor bem definido dentre os 2n possíveis e pode ser lido sem problemas, ao passo que, na quântica, esses Q-bits (bits quânticos) admitem uma função de superposição dos 2n estados, e após a medida, seu estado colapsa para o valor binário medido. Por exemplo, enquanto na computação clássica um conjunto de dois bits pode admitir os estados 00, 01, 10 ou 11; na computação quântica o conjunto está em uma superposição desses estados ψ00|00⟩ + ψ01|01⟩ + ψ10|10⟩ + ψ11|11⟩, onde |ψ00|2+|ψ01|2|+ψ10|2+|ψ11|2=1, e há uma probabilidade |ψE|2 de medir o conjunto em um estado E.

Isto nos leva a um novo e revolucionário paradigma de computação: o fato de um conjunto de bits não admitir um único estado, mas sim uma função de estado, possibilita a criação de algoritmos capazes de tratar os vários estados possíveis ao mesmo tempo, de forma a resolver os problemas em menor complexidade temporal. Além disto, a computação quântica é, no mínimo, tão poderosa quanto a clássica, apesar de algumas dificuldades, como incapacidade de cópia da função de estado (clonagem, isto é, uma réplica não-emaranhada), e o fato de que todas as operações quânticas (análogas às operações lógicas como AND, OR, NOT) devem ser unitárias (transformações que preservam ∑E|ψE|2=1 e, consequentemente, são reversíveis).

Os algoritmos quânticos combinatoriais normalmente se baseiam na técnica de amplificação de amplitude. Trata-se de um algoritmo que, supondo um custo O(A) para verificar uma solução e dadas N combinações possíveis, leva um tempo O(A√N) para descobrir a solução [11]. Desta forma, se há 2N chaves possíveis para um algoritmo criptográfico, e supondo que o custo de testar uma chave é O(1), teremos um custo de O(2N/2) de quebrar a chave. O custo continua sendo exponencial no tamanho da chave, mas é muito melhor do que o custo O(2N) da computação clássica.

Outra aplicação da computação quântica é a utilização do fenômeno do emaranhamento quântico (entanglement). Considere um par de Q-bits, com estado |00⟩ + |11⟩/√2. Ou seja, há 50% de probabilidade de assumirem o estado 00, e 50% para 11. Nesta situação, podemos dizer que os dois Q-bits estão emaranhados, pois a medida de um deles define o estado do outro. E nada impede que os dois Q-bits estejam geograficamente isolados: isso possibilitaria técnicas de “telepatia” quântica, pois medir o valor de um Q-bit instantaneamente define o valor do outro. Esse fenômeno é explorado em algumas técnicas de criptografia quântica, que serão abordadas na seção 3 [19].

2.3  Algoritmo de Shor e Critpoanálise

   (Topo)

Em 1996, Peter Shor sugeriu um algoritmo que foi um marco na criptografia. Até aquele momento, tinha-se a certeza de que a criptografia assimétrica era resistente a qualquer tipo de ataque, como “força bruta” ou fatoração da chave, algo que tornava impossível a obtenção do conteúdo criptografado em tempo hábil.

Como visto anteriormente, a vulnerabilidade de algoritmos como o RSA se encontra na possibilidade de fatorar os números da chave pública para obter a privada. O algoritmo de Shor permite a exploração deste ponto fraco ao fatorar números desta magnitude em tempos muito menores. Se a operação de fatoração de um número n (com log(n) bits) é feita com complexidade O(exp(c . (log(n))1/3 . (log(log(n)))2/3)) atualmente [15], o algoritmo de Shor realiza o mesmo procedimento com complexidade O((log(n))2 . (log(log(n)) . (log(log(log(n))))) [40]. Este novo algoritmo de fatoração representa a passagem de uma complexidade exponencial para uma polinomial. Para ilustrar esta diferença, a Figura 1 compara o número aproximado de operações necessárias para a realização da fatoração em um computador clássico e em um quântico (hipotético).

Figura 1: Comparação entre Crivo do Campo Numérico e Algoritmo de Shor

Shor usa o mesmo princípio introduzido por Euler [1], tentando encontrar o menor r tal que ar ≡ 1 (mod n ), onde a é um valor aleatório contido no intervalo (1, n). Para tanto, ele procura uma potência de 2, q, tal que n2 ≤ q ≤ 2n2 e aplica operações como a Transformada de Fourier Quântica (QFT), retornando, por fim, o valor de r [40].

O que torna o algoritmo de Shor polinomial é a capacidade de calcular o período r da função ax (mod n ) em tempo polinomial, lembrando que r é um divisor de ϕ(n). A aplicação da QFT no vetor uniformemente distribuído |x⟩ emaranhado com |ax modn⟩ permite medir as frequências da função, que são (predominantemente) múltiplas de 1/r (e consequentemente múltiplas de 1/ϕ(n)). Emular esse algoritmo em um computador clássico aplicando FFT (transformada rápida de Fourier) seria impraticável, lembrando que o custo da FFT é O(nlog(n)) enquanto o da QFT é O(log(n)log(log(n))).

Figura 2: Atuação da QFT no algoritmo de Shor. Inicialmente |x⟩ é um vetor uniformemente distribuído, e |ax modn⟩ = 0. Em seguida calcula-se ax modn. Ao final, aplica-se a QFT, obtendo o espectro de frequências de ax, que são múltiplas de 1/r.

O surgimento de algoritmos de criptoanálise capazes de decifrar informações codificadas pelo RSA está apenas condicionado à aparição de computadores quânticos com memória suficiente para executá-los, algo que não está tão longe de acontecer. Segundo reportagem da Scientific American [41], “algumas agências de governo e instituições financeiras estão com medo de terem suas mensagens criptografadas capturadas para que sejam armazenadas até o momento em que o computador quântico possa decifrá-las, provavelmente em torno de uma década”.

2.4  Presente e Futuro

   (Topo)

Quando se ouve falar sobre computação quântica, geralmente um pensamento de algo em um futuro longínquo vem à cabeça. Porém, isto não é verdade, pelo menos não desde o fim do século passado, quando a IBM lançou os primeiros computadores quânticos para mostrar a viabilidade desta nova área da computação [21]. Com 2, 3 e 5 Q-bits, eles foram um marco na história da computação quântica: a passagem da teoria para a prática, efetivamente. No início deste século, a mesma IBM criou um computador quântico com 7 Q-bits, no qual foi realizada a fatoração do número 15 com o uso do algoritmo de Shor [22].

Mais recentemente, pesquisadores da Universidade de Yale criaram o primeiro processador quântico em estado sólido com 2 Q-bits [43], um passo muito importante no que diz respeito à criação de um computador quântico para usos que não o acadêmico, já que este estado físico é mais facilmente manipulável. Atualmente, a IBM está engajada em um projeto de cinco anos nesta área, após um período relativamente longo de ociosidade [27]. Segundo David DiVicenzo, físico e gerente de pesquisa da IBM, o objetivo é “transformar as recentes descobertas em algo material”.

Anterior | Topo | Próxima