Computação Quântica e a Relação com a RSA

A natureza da luz, do que esta é composta, é uma discussão antiga que até hoje ocupa um local central na ciência. Newton acreditava que a luz era composta de pequenas partículas, ainda que muitos outros cientistas acreditassem que luz são ondas de energia. Uma partícula concentra toda sua energia em um único ponto do espaço, enquanto uma onda distribui sua energia no espaço.

Um experimento foi crucial para favorecer uma das teorias. No final do século 19, o físico Thomas Young divulgou o resultado de seu experimento da fenda dupla. O experimento envolve uma fonte de luz (uma lanterna, por exemplo), um filme fotográfico e uma parede entre a fonte e o filme, com apenas duas fendas cortadas nesta parede, como abaixo.

A luz que passa pelas fendas atinge o filme fotográfico e a revelação deste permite observar em que locais a luz chegou. Se a luz for composta de partículas, então o filme revelará concentrações de luz logo a frente de cada fenda. Pense em uma arma de paintball atirando contra as fendas. Algumas bolinhas passarão pelas fendas e seguirão até atingirem o filme, as demais serão retidas pelo aparato. Assim, se luz for partícula espera-se um padrão como o abaixo:

Por outro lado, se luz são ondas então estas ondas atingirão o aparato e parte da energia será refletida, enquanto parte da energia será transmitida pelas fendas. Pela natureza de ondas, cada fenda se comportará como um emissor de ondas, como se emitindo ondas independentes. As ondas de cada fenda sofrerão interferência do outro lado do aparato. Interferência é o nome dado a interação dos picos e vales das ondas: se dois picos se encontrarem no mesmo ponto do espaço ao mesmo tempo, suas energias se somam, gerando um pico maior; se um pico e um vale se encontrarem, suas energias se anulam. É o mesmo princípio dos fones com cancelamento de ruído, onde um microfone capta sons externos e gera um som com fase oposta, de forma que a soma das duas ondas sonoras se cancelem antes de atingir nosso ouvido. Assim, se a hipótese de que luz são ondas estiver correta, então devemos ver um padrão de interferência no filme fotográfico, algo como abaixo.

Esse padrão é típico de interferência, com bandas alternadas onde interferência construtiva e destrutiva ocorrem. Note como a área mais forte ocorre entre as fendas.

Young demonstrou que de fato é um padrão de interferência que ocorre neste experimento e que, portanto, a luz é uma onda ou, pelo menos, se comporta como uma. De fato, nossa compreensão sobre luz é precisamente a de uma onda eletromagnética e sabemos que a luz é apenas um espectro de frequência bastante estreito entre outras ondas como raios-X, microondas, raios gama e Wi-Fi.

Este poderia ser o fim da história da luz, não fossem uma série de experimentos e teorias no início do século 20 que levaram à Mecânica Quântica. Em particular, Albert Einstein ganhou seu prêmio Nobel ao explicar o fenômeno fotoelétrico, que só é consistentemente explicado se tratarmos a luz como partículas (denominadas fótons) e não ondas, gerando uma crise de identidade para a luz. Como poderia em alguns experimentos a luz se comportar como onda, mas em outros como partícula? Esta é a dualidade onda-partícula da luz. Einstein observou:

It seems as though we must use sometimes the one theory and sometimes the other, while at times we may use either. We are faced with a new kind of difficulty. We have two contradictory pictures of reality; separately neither of them fully explains the phenomena of light, but together they do.

O experimento de Young fornece pistas sobre o que ocorre. Suspeitando que a luz é uma partícula, podemos alterar o experimento de Young para que a fonte de luz emita uma pequena quantidade de luz por vez. De fato, podemos fazer com que ela emita apenas uma unidade de luz, seja ela partícula ou uma onda. Por exemplo, quando um elétron de um átomo excitado decai para uma órbita inferior, ele libera uma quantidade de energia na forma de onda eletromagnética (um fóton). O fenômeno fotoelétrico é o inverso, quando um elétron é excitado por um fóton. Este fóton emitido agora percorrerá o espaço da fonte até as fendas e ou será refletido ou passará por alguma das fendas e atingirá o filme fotográfico.

Podemos agora emitir múltiplos fótons, um por vez, e então revelar o filme fotográfico. O que observaremos é o padrão de interferência antes visto. Como estamos emitindo um fóton por vez e o padrão de interferência só pode ocorrer entre duas ondas, então é o caso que o fóton é uma onda que se distribuiu em duas ondas, uma em cada fenda. A teoria da onda ainda prevalece.

Porém, ainda insatisfeitos podemos adicionar um sensor em uma das fendas, para detectar quando a luz passa por ali. Esperamos que o sensor sempre se ative quando um fóton é emitido, pois o fóton como onda passa por ambas as fendas simultaneamente. Mas não é o que acontece. O sensor não dispara a cada fóton emitido, indicando que o fóton não passa por ambas fendas ao mesmo tempo. Mas, se o fóton passa apenas por uma fenda, como pode ocorrer o padrão de interferência? E, de fato, a parte interessante do experimento é que o padrão de interferência desaparece quando observamos por qual fenda o fóton passa. 🤯

A interpretação deste experimento é que o fóton se comporta como onda no filme fotográfico desde que não seja observado nas fendas. Se ele for observado, então ele se passa a se comportar como uma partícula a partir do ponto de observação.

Uma das explicações para este fenômeno, que está no coração da Mecânica Quântica, é que a luz não é nem onda, nem partícula, mas algo diferente chamado função de onda. Uma função de onda é uma onda de probabilidades e não energia. Quando um fóton é emitido, ele se propaga como uma nuvem de probabilidades sobre sua posição no espaço e tempo — cada posição espacial e temporal possui uma probabilidade de o fóton estar naquela posição em um dado momento. Quando esta função de onda é observada, se realiza uma medida da sua posição, como quando o filme fotográfico é atingido, ela colapsa: toda a sua energia passa a estar localizada em um único ponto no espaço, onde o fóton se localiza com probabilidade máxima. É como se o fóton não soubesse onde está até alguém perguntar, quando então ele decide onde estará.

A função de onda não descreve uma incerteza em relação a posição do fóton. Ela é probabilística na sua natureza: o fóton de certa forma não existe até ser observado. E isto explica perfeitamente o experimento da fenda dupla com o sensor.

A função de onda (o fóton) é emitida pela fonte e se propaga no espaço como uma onda de probabilidades. Ao atingir as fendas, a função de onda se comporta como uma onda e passa por ambas as fendas, interferindo com ela após as fendas pois, do outro lado do aparato, ela continua se comportando como uma função de onda — mas são as probabilidades que se interferem e não as energias. Por outro lado, ao incluirmos o sensor, causamos o colapso prematuro da função de onda: ao medirmos sua posição, a função de onda colapsa e “decide” por qual fenda ela passará, concentrando toda a energia em uma única fenda, como uma partícula (ou, mais precisamente, como uma função de onda que só está passando por uma das fendas, pois não existem realmente partículas de acordo com esta teoria — tudo são funções de onda). Como ela se comporta como partícula dali para frente, ela não pode interferir consigo mesma e o padrão de interferência desaparece.

Se não observamos as fendas, dizemos que a função de onda se encontra em um estado de superposição: não sabemos por qual fenda o fóton passa realmente, apenas podemos modelar as probabilidades dele passar por uma ou por outra fenda e, assim, o estado onde o fóton passa por uma fenda e o estado onde o fóton passa pela outra se encontram superpostos, co-existindo no modelo dado pela função de onda. Este conceito ficou famoso pelo cenário proposto por Erwin Schrödinger, o famoso Gato de Schrödinger. Nele, um gato é preso em uma caixa opaca e, dentro da caixa, um dispositivo probabilístico pode ser ativado e matar o gato, ou não ativar e manter o gato vivo. Em qualquer momento, há 50% de chance do dispositivo disparar. Schrödinger propôs este cenário para tentar demonstrar o absurdo das teorias quânticas, apontando que de acordo com estas teorias o gato estaria vivo e morto ao mesmo tempo — os dois estados se encontrariam em superposição até que alguém abrisse a caixa e causasse o colapso da função de onda, efetivamente matando o gato ou mantendo-o vivo. O absurdo, de acordo com Schrödinger, é que é evidente que o gato ou está vivo ou está morto durante o experimento. No entanto, Schrödinger acabou convencido de que é isso que ocorre de fato, pelo menos no mundo subatômico ainda que talvez não no mundo macroscópico (o que é uma possibilidade), e foi um dos grandes contribuidores da Mecânica Quântica. De fato, a função de onda é descrita pela equação de Schrödinger!

O conceito de função de onda é pouco intuitivo, mas ele é necessário pois múltiplos experimentos só podem realmente ser explicados se incluirmos este conceito. Ademais, todos experimentos que tratam a luz como onda ou partícula são ainda consistentes com funções de onda. A função de onda como instrumento para compreender fenômenos naturais é indiscutivelmente útil mas pouco se sabe sobre o que realmente é uma função de onda, ou se sequer faz sentido fazer esta pergunta.

Um Computador Quântico é um computador que faz uso da Mecânica Quântica para realizar computação. A unidade básica de informação em um computador quântico é o quantum bit, ou qubit. Enquanto um bit clássico pode assumir o valor 0 ou 1, um qubit pode ser colocado em um estado de superposição. Isto é, ele é representado por uma função de onda onde se atribui probabilidades para 0 e para 1. Ao observarmos um qubit, ele terá valor 0 ou 1, como o clássico, mas antes de observarmos qualquer dos dois valores pode ser observado com alguma probabilidade.

A composição de vários qubits dá origem a registradores quânticos. Um registrador de 2 qubits antes de ser observado existe em um estado com quatro estados superpostos (00, 01, 10 e 11). A função de onda descreve as probabilidades de cada estado, e não precisam ser iguais. De fato, um computador quântico opera manipulando as funções de onda por meio de interferências de forma a ampliar ou reduzir probabilidades de acordo com um algoritmo quântico.

Operadores quânticos são equivalentes a operadores lógicos em computadores clássicos. Estes operam sobre registradores quânticos e transformam suas funções de onda. Dado um registrador que representa a saída de um algoritmo, este manipula a função de onda do registrador de forma a ampliar a probabilidade associada ao estado que representa uma solução desejada, reduzindo as demais probabilidades. Assim, quando observamos o registrador ao fim da computação, temos uma probabilidade mais alta de observar o resultado correto do que um incorreto. Semelhante a um algoritmo probabilístico, um algoritmo quântico tem uma resposta probabilística e tipicamente é necessário rodar a computação múltiplas vezes para obter uma probabilidade baixa de erro. Mas a semelhança com algoritmos probabilísticos é limitada. Em um algoritmo probabilístico, qualquer registrador se encontra em apenas um único estado em qualquer momento; apenas as decisões do algoritmo são probabilísticas. Em um computador quântico, não só decisões são probabilísticas, mas os próprios registradores também são probabilísticos.

De certa forma, computação quântica pode ser vista como um processo de filtragem. Iniciando com um registrador quântico onde todos estados possuem a mesma probabilidade associada, os operadores quânticos vão filtrando estados indesejáveis, reduzindo suas probabilidades, de forma que o estado que representa a solução se sobressaia.

Um dos motivos do interesse em computação quântica é devido a um algoritmo em particular, o Algoritmo de Shor. Proposto em 1994 pelo matemático Peter Shor, este é um algoritmo de fatoração de inteiros que executa em tempo polinomial em um computador quântico. O tempo de execução deste algoritmo para um inteiro N é de:

Observe que N é a magnitude do número e, portanto, log N é linear no número de bits necessários para representar N. Como vimos antes, o melhor algoritmo de fatoração de inteiros que executa em computadores convencionais, o GNFS, é super-polinomial, ainda que sub-exponencial. Assim, o algoritmo de Shor melhoraria substancialmente o desempenho em problemas de fatoração de inteiros e isto teria um impacto direto em algoritmos de criptografia como o RSA. A segurança do RSA depende do fato de que fatoração é um problema relativamente difícil para um computador solucionar. Com o algoritmo de Shor, as chaves do RSA teriam que ser impraticavelmente grandes para garantir a mesma segurança, essencialmente tornando o RSA inseguro, afetando boa parte dos sistemas criptográficos da internet (o HTTPS, protocolo utilizado para comunicação segura em navegadores faz uso do RSA).

A descoberta do algoritmo de Shor só não foi catastrófica para a RSA por que computadores quânticos ainda estão na sua infância. É muito difícil manter um registrador quântico estável, mesmo pequenas flutuações térmicas podem causar o colapso da função de onda, impedindo a computação. Estes computadores precisam ser altamente refrigerados e o aumento do número de qubits dificulta ainda mais o problema. Até 2012, o maior número fatorado por um computador quântico com o algoritmo de Shor foi… 21. Ainda demorará um bom tempo até atingirmos os 4096 bits do RSA. Já há, claro, planos para mover sistemas criptográficos para sistemas imunes a computação quântica, as chamadas cifras pós-quânticas, algumas inclusive baseadas em mecânica quântica (criptografia quântica é uma área relativamente nova e fértil).

Uma Máquina de Turing Quântica é um modelo de computação que captura as capacidades de um computador quântico. Uma MTQ é equivalente computacionalmente a uma Máquina de Turing Determinística — o que uma computa, a outra também computa. Isto é, computadores quânticos não permitem solucionar problemas incomputáveis.

A classe BQP (Bounded-error Quantum Polynomial) é uma das principais classes de complexidade para computação quântica. A classe BQP contém todos problemas que podem ser solucionados por uma Máquina de Turing Quântica em tempo polinomial com erro limitado e é semelhante a classe BPP neste sentido. Fatoração de inteiros está em BQP.

A existência do Algoritmo de Shor pode passar a impressão que computadores quânticos são mais capazes do que computadores convencionais. Porém, não foi provado que a fatoração de inteiros não é um problema P. Pode ser o caso de que existe um algoritmo eficiente para fatoração de inteiros que não exige um computador quântico, mas ninguém ainda o descobriu.

Durante muito tempo não se sabia se computadores quânticos eram capazes de fazer algo demonstrativamente diferente de computadores convencionais e era perfeitamente possível que ambos modelos fossem equivalentes em termos de complexidade. Apenas em 2018 uma forte evidência de que de fato computadores quânticos podem solucionar algum problema de forma mais eficiente que computadores convencionais. A prova envolve demonstrar que existe pelo menos um problema em BQP que não está em PH. A classe PH é a chamada Polynomial Hierarchy, e é uma generalização da classe NP que permite níveis de complexidade incrementalmente e arbitrariamente maiores. Por exemplo, o problema “existe um ciclo hamiltoniano menor do que 10 para um dado grafo” é NP, enquanto “existe um ciclo hamiltoniano menor do que 10 mas maior do que 7” está em PH. Ambos podem ser verificados em tempo polinomial, mas o segundo é estritamente mais difícil e ocupa uma hierarquia polinomial superior.

O problema em específico é amplamente artificial e não reflete nenhum problema real, mas foi uma prova crucial de que BQP não está contida em PH. Acredita-se que o panorama da relação entre as principais classes é algo como abaixo.

Observe que BPQ engloba totalmente P, mas não NP-Completo. É um erro comum a crença de que computadores quânticos tornariam fáceis todos problemas computáveis. Ademais, computadores quânticos dão respostas probabilísticas e é preferível utilizar um computador convencional para solucionar problemas em P. Assim, é provável que computadores quânticos complementem computadores convencionais e não os substituam. Diversas empresas como Google, Amazon e Microsoft estão se movendo para oferecer computação quântica na nuvem, de forma que somente quando for necessário solucionar um problema que exige um servidor quântico iremos delegar a tarefa para estes servidores.