Gatos, Qubits e Teletransporte: O estranho mundo dos algoritmos quânticos (Parte 2)

Com a intenção de entender o porquê dos computadores quânticos serem interessantes, é necessário mergulhar (rapidamente!) na teoria da complexidade. Embora pareça algo remoto daquilo que muitos de nós faz diariamente, a teoria da complexidade não é apenas para cursos universitários e quadros brancos em entrevistas de emprego. O que torna a computação quântica tão rápida não é a velocidade de processamento dos computadores quânticos (que é devagar) ou a memória dos computadores (que é absurdamente minúscula). Em vez disso, são os algoritmos. Os computadores quânticos possibilitam novos algoritmos com características de complexidade completamente diferentes do que seus equivalentes clássicos.

Quem estuda a complexidade classifica os problemas em classes de complexidade. Um dado problema pode pertencer a múltiplas classes, e existem tantas classes de complexidade que algumas vezes se fala em um zoológico da complexidade. Felizmente, há apenas algumas classes que precisamos conhecer. Os problemas NP-complexo são, como o nome sugere, difíceis de serem resolvidos. E se tornam mais difíceis em uma taxa alarmante conforme o número de coisas (dígitos, ou pontos, ou cidades) nas soluções aumenta. Os problemas NP-completo são problemas NP-complexo cujas soluções podem ser generalizadas para resolver qualquer outro problema NP-complexo. Um algoritmo eficiente para um problema NP-completo é o santo graal da teoria da complexidade. (Antes que se empolgue demais, não, a computação quântica não oferece isso - ainda).

Uma classe de complexidade é definida por mais do que sua notação O-grande, mas em geral, os problemas NP-complexo escalam polinomialmente com o número de coisas - isto é, são solucionáveis em tempo 2 ^0(log(n)). Isso significa que uma computação que toma razoáveis 8 segundos para 3 pontos, tomaria muito menos razoáveis 17 minutos para 10 pontos, e ridículos 12 dias para 20 pontos, e 35.000 anos para 40 pontos. Outra forma de pensar sobre é que o hardware estaria obsoleto antes da computação terminar um cálculo de 26 pontos, e para um cálculo de 31 pontos, qualquer um que tenha escrito o programa provavelmente estaria morto antes de ter chegado a alguma resposta.

Algoritmos quânticos significativos

Teletransporte

Embora não seja uma computação, nenhuma discussão de informação quântica está completa sem mencionar o teletransporte. O teletransporte foi um dos primeiros processos de informação a ser descrito. Usa o entrelaçamento para transmitir (classificar) instantaneamente as informações entre grandes distâncias. Apesar do nome, não pode ser utilizado para transportar objetos grandes, como pessoas ou gatos. E aplica-se a apenas uma simples partícula, e sequer transmite esta única partícula, mas apenas a informação sobre seu estado. Entretanto, pode transmitir o estado completo do qubit daquela partícula, o que faz com que as pessoas que se importam com os estados quânticos fiquem consideravelmente entusiasmadas. As informações quânticas não podem ser transmitidas por canais clássicos porque qualquer medição clássica de um estado quântico o perturba ("colapsa").

A informação quântica não pode ser copiada (o teorema da não-clonagem), então a informação teleportada sobre uma partícula destrói o estado da partícula original, o que é provavelmente a inspiração para o nome "teletransporte"; apesar da matéria não ser desintegrada em um lugar e ser regenerada em outro lugar, a informação é.

A teoria da relatividade de Einstein afirma que a informação não pode viajar mais rápido do que a luz. O teletransporte não chega a violar isso, apenas parece (o que é quase tão excitante quanto). Para ser entrelaçado, um par de fótons tem que começar no mesmo lugar e então se distanciar um do outro. Isso significa que a informação "latente" viajou mais devagar do que a velocidade da luz, logo respeita a teoria de Einstein. É quase como a comunicação feita por um pombo-correio; embora os pombos possam carregar uma mensagem muito mais rápido do que uma pessoa ou um cavaleiro, um cavalo tem que transportar os pombos até seus destinos para que então possam ser enviados às suas casas com uma mensagem. Assim, para que transmitam uma informação útil (ao invés de apenas o resultado de um cálculo probabilístico), o protocolo de teletransporte também requer a comunicação clássica - ou seja, um cavalo tem que carregar o pombo-correio, e um segundo cavalo tem que seguir na direção oposta com instruções sobre como ler a mensagem amarrada na perna do pombo. Isso significa que o teletransporte quântico é improvável de ser usado para uma negociação de alta frequência no futuro próximo. Contudo, é uma forma efetiva de transmitir um estado quântico completo sem o colapsar.

Simulação de sistemas quânticos

Não é de surpreender que um sistema quântico, como um computador quântico, poderia ser usado para simular um outro sistema quântico. O que é surpreendente é que os computadores clássicos são muito ruins em simular sistemas quânticos. Os sistemas quânticos pequenos são bons, mas os grandes são efetivamente impossíveis; a riqueza de informação de estados quânticos significa o esforço de fazer uma simulação escalar exponencialmente com o número de elementos. Richard Feynman foi o primeiro a notar que os sistemas quânticos tinham complexidades computacionais seriamente altas, o que lançou as bases para os desenvolvimentos posteriores da teoria da informação quântica.

Fatoração

A teoria da informação quântica realmente deslanchou quando as pessoas perceberam que a complexidade computacional dos sistemas quânticos era, na verdade, uma capacidade computacional. Essa capacidade poderia ser aplicada a outros problemas, como a fatoração.

A fatoração é o problema de encontrar dois números que, juntos, multiplica-se para dar um certo número. Ocasionalmente, fatorar é útil por si só, mas a maior razão de ser interessante é por ser difícil e assimetricamente difícil. Fatorar é um exemplo do que se conhece como uma função de mão única; se ambos os divisores são conhecidos, encontrar seu produto é fácil, mas encontrar os divisores a partir do produto pode levar um bom tempo. O maior número já fatorado foi um número de 232 dígitos, o que na verdade não é muito grande (para efeitos de comparação, o pi já foi calculado até, no mínimo, 5 trilhões de dígitos). Ainda assim, fatorar 232 dígitos foi um enorme projeto; centenas de máquinas foram utilizadas e os pesquisadores responsáveis levaram 2 anos para encontrar os divisores.

A dificuldade assimétrica torna a fatoração útil para a criptografia de chaves públicas (por exemplo, RSA). O produto de dois primos é usado para gerar uma chave pública, que os remetentes usam para encriptar uma mensagem. O destinatário usa sua chave pública baseada em um dos fatores originais para decifrar a mensagem. É fácil decifrar se alguém conhece os divisores originais, mas sem eles, é um problema intratável.

Embora não tenha sido matematicamente provado, é comumente acreditado que a dificuldade clássica do problema de fatoração de casos gerais aumenta com o número de dígitos de uma maneira mais difícil do que polinomial, mas mais fácil do que exponencial. Isto é conhecido como sub-exponencial, e descrito como 2^O(n). Na prática, os números suficientemente grandes são essencialmente não-fatoráveis pelos meios clássicos.

Em 1994, Peter Show, um matemático, demonstrou que um computador quântico poderia ser usado para resolver o problema da fatoração em tempo polinomial. Ele havia ouvido uma palestra sobre alguns prospectos teóricos da computação quântica, mas naquele tempo, ninguém havia identificado ainda qualquer algoritmo útil para eles. Então, Shor começou a pensar sobre como fazer um computador quântico resolver problemas computacionais gerais, mas não contou para ninguém o que estava fazendo. Levou um ano até que Shor chegasse a um algoritmo quântico para encontrar logaritmos. Quatro dias depois, Shor havia conseguido adaptar seu algoritmo de logaritmos a um algoritmo eficiente de fatoração.

Uma vez que fator é uma peça fundamental das maiorias das criptografias de chaves públicas, o trabalho de Shor fez com que todos sentassem e prestassem atenção. Todavia, o algoritmo de Shor não mata a área da criptografia; protocolos de criptografia "à prova quântica" já estão sendo desenvolvidos. Além disso, como veremos na parte 3 desta série de artigos, é necessário um computador quântico com milhares de qubits para rodarmos com sucesso o algoritmo de Shor.

O algoritmo de Shor funciona utilizando uma sobreposição quântica para testar várias possibilidades.

Porém, os detalhes do algoritmo de Shor são mais complicados do que apenas "testar todos os possíveis fatores e ver qual deles é o certo". Embora isso pudesse ser feito em um computador quântico, qualquer cálculo iria trazer um fator aleatório e - muito provavelmente - incorreto.

A "grande sacada" do algoritmo de Shor é que, depois de experimentar muitas possibilidades, o algoritmo interfere em todas as respostas, de modo que é muito mais provável que um cálculo produza uma resposta correta do que uma resposta incorreta. "Interferir em respostas" não é algo que faça sentido para um computador clássico, mas os computadores quânticos aproveitam as características de onda dos estados quânticos para fazer isso. Interferir nas possibilidades para amplificar as corretas é uma característica comum de muitos algoritmos quânticos.

A primeira parte da solução de Shor é fazer a computação clássica reduzir o problema da fatoração a encontrar o período de uma função (isto é, sua frequência). Uma vez feito, o problema será sobre ondas e frequências, e começa a parecer uma solução mais natural possível envolvendo ondas quânticas e interferência.

Na matemática clássica, uma transformada de Fourier é usada para transformar uma função (como um sinal de onda) em suas freqüências constituintes. Para encontrar a transformada de Fourier de uma função desconhecida, seria necessário medi-la em muitos pontos, a fim de descobrir com que frequência é repetida. Por exemplo, a transformada de Fourier de uma onda senoidal padrão é um par de pontas (há apenas uma única frequência, espelhada ao redor do eixo y). A transformada de Fourier de uma função de caixa é uma colisão gradual.

A transformada quântica de Fourier tem o mesmo objetivo de escolher as frequências que compõem uma série temporal, mas é possível usar a sobreposição para medir efetivamente a função em múltiplos pontos no tempo e interferir nas ondas para que as respostas corretas sejam amplificadas e as respostas erradas canceladas. Uma vez que isso esteja feito, qualquer cálculo tem uma alta probabilidade de reduzir o sistema para a resposta correta.

Misturar ondas de forma que as respostas erradas cancelem a si mesmas é muito diferente de como os computadores clássicos funcionam, mas é algo que muitos de nós já vivenciou no mundo macroscópico. Por exemplo, os fones com cancelamento de ruído funcionam adicionando um ruído adicional ao ruído existente. Estes fones tocam uma onda de som extra que tenta reproduzir o ruído externo, mas com a fase deslocada. Enquanto as novas ondas de som estiverem exatamente 180 graus fora de fase com as indesejadas ondas de ruído, e com uma cópia perfeita delas, todas irão se anular mutuamente, resultando em um silêncio divino para o usuário.

Busca

O algoritmo de Shor foi o primeiro "app matador" quântico. O segundo, dois anos depois, foi o algoritmo de busca de Grover. O Algoritmo de Grover permite buscar em um banco de dados não ordenados em tempo . Por exemplo, poderia ser usado para encontrar um nome em um lista telefônica se alguém souber apenas o número do telefone. O algoritmo de Grover não provê a mesma aceleração espetacular do algoritmo de fatoração de Shor; é um aumento quadrático, ao invés de um aumento exponencial (ou seja, escala como a raiz quadrada do número de elementos). Essa aceleração mais modesta é contrabalanceada pela ampla aplicabilidade do algoritmo de Grover. 

Embora Grover tenha descrito seu algoritmo em termos de busca de banco de dados, na verdade ele é muito mais amplo do que isso. A coisa que está sendo pesquisada é algo que satisfaz uma função - em outras palavras, a resposta para um problema (tecnicamente falando, o objetivo é o "inverso de uma função"). O problema pode, por exemplo, ser "qual chave deveria ser usada para decifrar essa mensagem?". Em outras palavras, o algoritmo de Grover pode ser usado para acelerar o ataque de força bruta da criptografia, mesmo para criptografia não baseada em fatoração. Também pode ser usado para estimar a média (média ou mediana) de um conjunto de números.

O algoritmo de Grover, assim como muitos algoritmos quânticos, é probabilístico. Cada execução tem uma chance de trazer a resposta correta, e uma (baixa) chance de trazer a resposta incorreta. Isso parece consideravelmente insatisfatório, mas na verdade é muito mais útil do que parece. Isso porque a resposta é a solução para uma função, e será imediatamente óbvio se o algoritmo trouxe a resposta errada. Para um sistema de n-elementos, tem despendido tempo  trabalhando em uma solução, apenas para conseguir a solução errada, seria muito deprimente. Entretanto, mesmo se o cálculo longo e lento tenha de ser repetido inúmeras vezes, o tempo total de solução ainda é e muito mais rápido do que seria usando um algoritmo determinístico clássico (a probabilidade do cálculo estar errado não aumenta com n, o que explica o porquê de ser tolerável às chances de erro).

Colisão

Uma generalização do algoritmo de Grover pode ser usado para resolver "problemas de colisão". Isso é, em vez de procurar por algo que satisfaça uma dada função, pode se encontrar múltiplos elementos que produzem a mesma resposta. Isto é útil para entender as colisões físicas no espaço, e também para problemas mais genéricos, como encontrar duas pessoas que fazem aniversário no mesmo dia. Assim como o algoritmo original de Grover, pode formar a base de um ataque criptográfico através de dois números com o mesmo hash (a versão clássica disso foi batizada como "ataque de aniversário").

O problema do caixeiro-viajante

Como os algoritmos quânticos geralmente envolvem algum processo no qual todas as soluções possíveis são experimentadas para, então, a correta ser selecionada pela amplificação de amplitude, os computadores quânticos parecem ser excelentes na resolução de problemas de otimização. Até o momento, não existe um algoritmo universal de otimização quântica, mas há soluções quânticas atrativas para algumas subclasses de problemas de otimização. Um dos problemas mais famosos de otimização é conhecido como o problema do caixeiro-viajante. O desafio deste problema é encontrar o caminho mais curto para um vendedor que deve viajar entre um certo número de locais. À medida que o número de locais aumenta, também aumenta a dificuldade de encontrar uma rota ótima. O problema do caixeiro-viajante é NP-complexo e escala exponencialmente com o número de locais. Soluções precisas para esse problema do caixeiro-viajante podem levar muitos anos (ou até milhões de anos) para computar, mesmo para algumas dezenas de cidades.

O problema do caixeiro-viajante é uma área de pesquisa contínua. Até recentemente, o melhor algoritmo quântico conhecido era (um aumento quadrático), enquanto o melhor algoritmo clássico conhecido era O(2n). Em março de 2017, um algoritmo quântico foi publicado e demonstrou uma aceleração quase quadrática para muitos casos, e é possível que outras melhorias ainda possam ser descobertas.

Machine Learning

Com a computação quântica e o machine learning em alta nos últimos anos, é natural perguntar se podem ser combinados. A resposta, até agora, provisoriamente parece ser um "sim". Em termos matemáticos, ambos os cálculos de estado quântico e os modelos de machine learning se baseiam fortemente em matrizes. Conceitualmente, o machine learning é sobre encontrar padrões em dados, e o modelo de interferir-e-amplificar-ondas da computação quântica é bem adequado para encontrar padrões.

Os computadores quânticos podem fazer alguns tipos de inversão de matriz com recursos logarítmicos (uma inversão de matriz é equivalente a resolver um sistema linear de equações). A inversão de matriz é útil para uma série de problemas de machine learning. Mais genericamente, o algoritmo de Grover pode ser usado para pesquisar pela resposta "certa" (ou seja, aquela que satisfaz uma dada função). Outros problemas de machine learning, como o agrupamento de dados, tem unicamente algoritmos quânticos.

Os computadores quânticos têm sido teoricamente provados como sendo melhores em resolver o que é conhecido um "problema da caixa preta" (descobrir uma sequência de bits desconhecida e aleatória sondando-a), e pesquisadores demonstraram uma implementação da caixa preta para 5 bits. Além de poder (em princípio, com um computador grande o suficiente) descobrir seqüências tão longas que um computador clássico ficaria sem tempo antes de resolvê-las, os computadores quânticos são mais tolerantes ao ruído nas leituras.

Não há uma aceleração quântica universal

Todos esses algoritmos são direcionados a classes específicas de problemas. Alguns, como a busca, ou o problema do caixeiro-viajante, têm muitas aplicações potenciais, mas os próprios algoritmos são muito específicos. Ainda não existe uma "aceleração quântica universal" conhecida. Em outras palavras, em termos das classes de complexidade, sabe-se que o BQP se sobrepõe ao NP, mas ainda não se sabe o quanto de sobreposição existe. Parece provável que ,mas isso não foi provado ainda. Peter Shor apontou que, para um algoritmo quântico dar uma aceleração interessante, os caminhos computacionais para a resposta certa precisam interferir construtivamente, e os caminhos para a resposta errada precisam se anular mutuamente. Ainda não há um processo generalizável de fazer-caminhos-errados-cancelarem-um-ao-outro. Dado o quão difícil é o problema, provavelmente nunca haverá.

A falta de um algoritmo quântico geral não deve diminuir o quão interessantes são os algoritmos conhecidos, ou quão amplamente aplicáveis são. O próximo artigo desta série discutirá quais são alguns desses domínios problemáticos e examinará o que o futuro pode trazer para a computação quântica.

Esta é a segunda parte de uma série sobre computação quântica. A parte um, que fornece uma introdução ao tópico e enfoca a computação quântica, pode ser encontrada em "Gatos, Qubits e Teletransporte: O estranho mundo da computação quântica (Parte 1)". A parte três, que se concentra em aplicações quânticas, pode ser encontrada em "Gatos, Qubits e Teletransporte: O estranho mundo dos algoritmos quânticos (Parte 3)".

Sobre a Autora

Holly Cummins é uma desenvolvedora full-stack e líder técnica em computação em nuvem. Também é palestrante frequente, Java Champion e autora do Enterprise OSGi in Action. É PhD em computação quântica pela Universidade de Oxford.