Computação quântica 101: Algoritmos quânticos e complexidade computacional

Este texto faz parte de uma série em andamento sobre computação quântica. Os textos anteriores podem ser acessados pelos links numerados: 1, 2, 3 e 4.

Em teoria da computação, um problema computacional é todo e qualquer problema que possa ser resolvido por meio de algoritmos. São problemas ligados a processos de decisão, à busca, à otimização, etc. Abarca desde questões como “o número 123.456.789.001 é primo?” (no caso, não é) até problemas mais complexos, conhecidos como problemas de função, como: “dada uma lista de cidades e as distâncias entre cada par de cidades, encontre a rota mais curta possível que visite cada cidade exatamente uma vez e retorne à cidade de origem.”  (o famoso problema do caixeiro-viajante). Esses problemas são costumeiramente divididos em classes de complexidade computacional.

Existem diferentes classes de complexidade, embora na maioria dos casos, pesquisadores da área da computação não tenham conseguido provar que uma classe é categoricamente distinta das outras. Provar esses tipos de distinções categóricas está entre os problemas em aberto mais difíceis e importantes da ciência da computação e geram discussões ao nível de um Fla-Flu. Embora ainda não se reconheça uma prova matemática cabal de que computadores quânticos são superiores (em termos de capacidade computacional) a computadores clássicos, há evidências que apontam para esse lado. Por exemplo, um relatório técnico publicado em 2018 [1] forneceu fortes evidências de que os computadores quânticos realmente possuem uma capacidade de computação que vai  muito além das que os computadores clássicos poderiam alcançar. Isto quer dizer que se pode considerar como diferentes, as duas classes de complexidade que representam computadores quânticos e clássicos.

Como as diferenças entre as classes de complexidade podem ser tanto sutis quanto gritantes, vale a pena fazer um pequeno resumo das classes de complexidade [2] antes de continuarmos. Vamos lá:

Classe P (Polynomial time)

É a classe de todos os problemas que são fáceis para um computador clássico (ou seja, não quântico) resolver. Um problema P típico seria a seguinte questão: “Qual é o caminho mais curto entre dois pontos?”. 

Classe NP (Nondeterministic Polynomial time)

É a classe de todos os problemas que podem ser rapidamente verificados por um computador clássico assim que uma solução é dada. Um problema NP típico seria o problema do caixeiro-viajante, descrito algumas linhas acima.

Classe PH (Polynomial Hierarchy)

A classe PH é uma generalização da NP. Ela contém todos os problemas que são possíveis obter se começarmos com um problema em NP e adicionarmos camadas extras de complexidade. Um problema típico seria “determine se existe um pequeno grupo de pessoas, com interesses compartilhados ou outras características em comum, que passam tempo juntos e não permitem que outros se juntem a eles prontamente, de tamanho 50, mas não de tamanho 51”.

Aqui vale um adendo sobre as classes P, NP e PH. Os cientistas da computação ainda não conseguiram provar que PH e NP são diferentes de P (P versus NP e PH versus P). Se P = NP, então todo PH também colapsa em P (isto é, P = PH). Isso traria um problemão para todo mundo, por exemplo, porque poderia tornar a maioria da criptografia ineficaz da noite para o dia ao provar que funções unidirecionais não existem. Uma prova  P = NP implicaria que quase nenhuma criptografia segura primitiva poderia existir de acordo com as definições aceitas de segurança (e.g., criptografia simétrica, MACs, geradores pseudoaleatórios, esquemas de assinatura). No entanto, é preciso reforçar que isso significaria apenas que nenhum esquema poderia ser comprovadamente seguro, mas não que todos os esquemas seriam quebrados na prática.

Classe PSPACE (Polynomial Space)

A classe PSPACE contém todos os problemas que podem ser resolvidos com uma quantidade razoável de memória. Isso quer dizer que em PSPACE, não nos importamos com o tempo gasto, nos importamos apenas com a quantidade de memória necessária para executar um algoritmo. Já foi provado que PSPACE contém PH, que contém NP, que contém P. Agora, não foi provado que PSPACE é diferente de P.

Classe BQP (Bounded-error Quantum Polynomial time)

É a classe de todos os problemas que são fáceis para um computador quântico resolver, ou seja, todos os problemas que podem ser resolvidos em tempo polinomial (P) por um computador quântico. Um problema típico BQP seria identificar os fatores primos de um inteiro. Já foi provado que BQP está contido em PSPACE e que BQP contém P. Mas, ainda não se pode afirmar com certeza se BQP está em NP. Acredita-se que as duas classes sejam incomparáveis (há problemas que estão em NP e não em BQP e vice-versa),  embora possam conter algumas interseções.

Classe EXPTIME (Exponential Time)

É a classe de todos os problemas que podem ser resolvidos em um tempo exponencial por um computador clássico. A classe EXPTIME (EXP, para os íntimos) contém todas as classes anteriores  P, NP, PH, PSPACE e BQP. Já foi provado que ela  é diferente de P, ou seja, existem problemas em EXP que não estão em P. Um problema típico desta classe seriam generalizações de jogos como xadrez e damas. Se um tabuleiro de xadrez pode ser de qualquer tamanho, torna-se um problema em EXP determinar qual jogador tem a vantagem em uma determinada posição do tabuleiro.

Classe BPP (Bounded-error Probabilistic Polynomial time)

É a classe dos problemas que podem ser resolvidos rapidamente por algoritmos que incluem um elemento de aleatoriedade. Detalhando um pouco mais a explicação, acredita-se que BPP é exatamente o mesmo que P, mas com a diferença de que o algoritmo pode incluir etapas em que a sua tomada de decisão é aleatória. Se considerarmos que BPP = P, isto significaria que todo algoritmo aleatório pode ser “desaleatorizado”. Ainda não se pôde provar, embora se acredite que este seja o caso, que exista um algoritmo determinístico (dada uma certa entrada, produz sempre a mesma saída) eficiente para cada problema para o qual exista um algoritmo randomizado (ou seja, aleatório) eficiente.

Uma boa maneira de se entender o que os computadores quânticos fazem melhor é estudando modelos matemáticos que os representem. Muitas vezes, se imagina um modelo de um computador quântico ou clássico emparelhado com uma máquina de calcular idealizada, chamada oráculo (no original, oracle). Os oráculos são funções matemáticas simples ou programas de computador, que recebem uma entrada e devolvem uma saída predeterminada. Eles podem ter um comportamento aleatório, emitindo “sim” se a entrada estiver dentro de um determinado intervalo aleatório (por exemplo, de 11 a 42) e “não” se não estiver. Os comportamentos também podem ser periódicos, de modo que uma entrada entre 1 e 10 retorne “sim”, 11 a 20 produza “não”, 21 a 30 produza “sim” novamente e assim por diante.

Digamos que tenhamos um desses oráculos periódicos e não conheçamos o seu período. Tudo o que podemos fazer nesse caso, é alimentá-lo com números e ver o que ele produz de resultado. A pergunta a ser respondida aqui é: com essas restrições, com que rapidez um computador poderia encontrar o período? Na década de 1990, Daniel Simon descobriu que um algoritmo quântico poderia calcular a resposta para um problema parecido ao descrito no início do parágrafo, exponencialmente mais rápido do que qualquer algoritmo clássico [4]. O resultado permitiu a Simon determinar um dos primeiros indícios de onde a superioridade dos computadores quânticos poderia ser esperada: o modelo quântico pode ter um poder teórico de complexidade significativamente maior do que o clássico. Ou seja, Simon determinou a classe BQP.

Peter Shor, com base no trabalho de Simon, descobriu que poderia adaptar o algoritmo para calcular o período de um oráculo. Depois, percebeu que poderia adaptar o algoritmo mais uma vez, para resolver uma equação que se comporta de forma semelhante a um oráculo periódico (a que descreve a fatoração, que é periódica) [5]. O algoritmo quântico proposto mostrou que se poderia reduzir rapidamente números gigantescos em seus fatores primos constituintes, algo que nenhum algoritmo clássico conhecido podia fazer. O algoritmo de Shor foi proposto em 1994 e com a popularização dos computadores quânticos ele, por si só, já impactaria nosso dia-a-dia online [8]. 

Dois dos criptossistemas mais comuns são Rivest-Shamir-Adleman (RSA) e a criptografia de curva elíptica (ECC). Quando estamos online, boa parte das informações que trocamos são criptografadas por eles [8]. Só que ambos são vulneráveis a ataques de computadores quânticos. Por exemplo, o RSA se baseia no problema de fatoração numérica (que Shor solucionou). Multiplicarmos dois números primos é relativamente fácil, mas pegarmos um número extremamente grande e fatorá-lo para obter esses dois números primos é extremamente laborioso. O algoritmo de Shor encontra os fatores primos de um número e “desfaz” a fatoração encontrando o período da função. Um exemplo, são os períodos das funções trigonométricas, como a da função do seno de x com período 2 ℼ (Fig. 1):

Perceba que os resultados sobem e descem, como uma onda de frequência. É essa “onda de frequência” que o algoritmo de Shor produz. Só para efeito de comparação, para fatorar uma chave de 4.096 bits com um computador clássico, se levaria mais tempo do que a idade do universo [8], enquanto com o Shor, o trabalho ficaria pronto em 8 horas [9].

Nos anos que se seguiram, outros algoritmos quânticos eficientes foram propostos. Alguns deles, assim como o algoritmo de Shor, até geram vantagem exponencial, mas ninguém conseguiu provar uma vantagem quântica dramática em qualquer problema NP que não fosse periódico. Provas de vantagem quântica sempre dependeram de oráculos que tivessem algum tipo de estrutura não aleatória, como periodicidade. Na década passada (de 2010), Scott Aaronson e Andris Ambainis conjecturaram que não poderia haver acelerações dramáticas em problemas NP que fossem aleatórios ou não estruturados. Resumindo, que não haveria vantagem quântica nesse tipo de problema.

A conjectura Aaronson-Ambainis colocou um limite nos poderes dos computadores quânticos. Mas, ela dizia apenas que não haveria acelerações dramáticas para um tipo específico de problema NP não estruturado, aqueles com respostas sim ou não (conhecidos como problemas de decisão). Se um problema envolvesse descobrir respostas quantitativas mais específicas, como o problema da busca, a conjectura não se aplicava. 

Um paper em preprint (é uma forma de divulgar um texto científico que ainda não foi submetido a um periódico ou conferência) postado em abril de 2022 [3], apresentou um novo tipo de problema que um computador quântico é capaz de resolver exponencialmente mais rápido do que um computador clássico. Envolve o cálculo das entradas para um processo matemático, baseado apenas em suas saídas e inspirado em uma instância do problema da busca [7]. 

A instância proposta por Regev [7] pode ser resumida da seguinte maneira: imagine um conjunto de cata-ventos que estão todos apontando para a mesma direção. Dê a cada um deles um empurrão controlado (nada muito fraco, nem muito forte). Depois, deixe que uma rajada de vento influencie a direção. Regev queria determinar, com base nas direções finais, para onde todos os cata-ventos apontavam inicialmente. Problemas como esse passaram a ser chamados de “aprender com erros” (learning with errors, no original), pois o empurrão e o vento atuam como uma fonte de erro aleatório na direção original. Há indícios de que é de difícil resolução tanto para algoritmos clássicos quanto para quânticos.

Yamakawa e Zhandry ajustaram a configuração, modificando a força desses “empurrões” iniciais, tornando-os mais previsíveis. Eles também fizeram com que o vento fosse determinado por um oráculo aleatório de modo que o ajuste se tornasse ainda mais aleatório em certos casos, mas completamente previsível em outros. Com essas modificações, eles descobriram que um algoritmo quântico poderia encontrar com eficiência a direção inicial. Também conseguiram provar que qualquer algoritmo clássico seria mais lento por um fator exponencial.

O fator exponencial atua como o fator de ponderação de Boltzmann e dá a probabilidade de um sistema estar em um determinado estado em função da energia desse estado e da temperatura do sistema. Assim como Shor, eles adaptaram o seu algoritmo para resolver uma versão real do problema, o que substitui um oráculo por uma equação matemática real.

Compressão de dados é uma das possíveis aplicações desse novo algoritmo quântico. Quando a informação está sendo comprimida, como por exemplo, quando você faz um zip de um arquivo, dois bits podem acidentalmente ser comprimidos no mesmo lugar, fazendo com que um substitua o outro (o que ocasiona perda de informação). O problema de prever essas colisões com antecedência, para que se possa evitá-las, tem alguma semelhança com encontrar eficientemente a direção inicial do vento.

O resultado fornece o primeiro exemplo de vantagem quântica em um problema de classe NP não estruturado. É um tipo de problema que o mundo quântico conseguiu mudar de praticamente insolúvel para solucionável. Se é o único ou o primeiro de muitos outros, ainda não se sabe. O que se pode afirmar, é que agora há mais razões para se pensar que podemos estar entrando em uma nova era de algoritmos. O impacto disso no nosso dia-a-dia, só o tempo dirá.

Referências

[1] Raz, Ran; Tal, Avishay. “Oracle Separation of BQP and PH”. 107, 2018. Electronic Colloquium on Computational Complexity, https://eccc.weizmann.ac.il/report/2018/107/.
[2] Hartnett, Kevin. “A Short Guide to Hard Problems”. Quanta Magazine, 2018, https://www.quantamagazine.org/a-short-guide-to-hard-problems-20180716/.
[3] Yamakawa, Takashi; Zhandry, Mark. “Verifiable Quantum Advantage without Structure”. arXiv:2204.02063, arXiv, 2022. arXiv.org, http://arxiv.org/abs/2204.02063.
[4] Simon, Daniel R. “On the Power of Quantum Computation”. SIAM Journal on Computing, vol. 26, no 5, October, 1997, p. 1474–83. DOI.org (Crossref), https://doi.org/10.1137/S0097539796298637.
[5] Shor, Peter W. “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Journal on Computing, vol. 26, no 5, October, 199, p. 1484–509. DOI.org (Crossref), https://doi.org/10.1137/S0097539795293172.
[6] Aaronson, Scott; Ambainis, Andris. “The Need for Structure in Quantum Speedups”. arXiv:0911.0996, arXiv, February, 2014. arXiv.org, http://arxiv.org/abs/0911.0996.
[7] Regev, Oded. “On lattices, learning with errors, random linear codes, and cryptography”. Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, Association for Computing Machinery, 2005, p. 84–93. ACM Digital Library, https://doi.org/10.1145/1060590.1060603.
[8] Marchenkova, Anastasia. “5 Quantum Algorithms That Could Change The World”. Quantum Bits, July, 2021, https://medium.com/quantum-bits/5-quantum-algorithms-that-could-change-the-world-2445cdd5c964.
[9] Gidney, Craig; Ekera, Martin. “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”. Quantum, vol. 5, April, 2021, p. 433. arXiv.org, https://doi.org/10.22331/q-2021-04-15-433.