Em 1994, um matemático descobriu como fazer um computador quântico fazer algo que nenhum computador clássico comum poderia. O trabalho revelou que, em princípio, uma máquina baseada nas regras da mecânica quântica poderia quebrar com eficiência um grande número em seus fatores primos – uma tarefa tão difícil para um computador clássico que forma a base de grande parte da segurança da Internet atual.
Seguiu-se uma onda de otimismo. Talvez, pensaram os pesquisadores, possamos inventar algoritmos quânticos que possam resolver uma enorme variedade de problemas diferentes.
Mas o progresso estagnou. “Tem sido uma trajetória um pouco chata”, disse Ryan O'Donnell da Universidade Carnegie Mellon. “As pessoas diziam: 'Isso é incrível, tenho certeza de que teremos todos os tipos de outros algoritmos incríveis.' Não." Os cientistas descobriram acelerações dramáticas apenas para uma única e estreita classe de problemas dentro de um conjunto padrão chamado NP, o que significa que eles tinham soluções verificáveis com eficiência — como fatoração.
Foi assim por quase três décadas. Então, em abril, pesquisadores inventado um tipo de problema fundamentalmente novo que um computador quântico deveria ser capaz de resolver exponencialmente mais rápido do que um computador clássico. Envolve o cálculo das entradas para um processo matemático complicado, baseado apenas em suas saídas confusas. Se o problema está sozinho ou é o primeiro em uma nova fronteira de muitos outros ainda não foi determinado.
“Há uma sensação de entusiasmo”, disse Vinod Vaikuntathan, cientista da computação do Instituto de Tecnologia de Massachusetts. “Muitas pessoas estão pensando sobre o que mais está lá fora.”
Os cientistas da computação tentam entender o que os computadores quânticos fazem melhor estudando modelos matemáticos que os representam. Muitas vezes, eles imaginam um modelo de um computador quântico ou clássico emparelhado com uma máquina de calcular idealizada chamada oráculo. Oráculos são como funções matemáticas simples ou programas de computador, recebendo uma entrada e cuspindo uma saída predeterminada. Eles podem ter um comportamento aleatório, emitindo “sim” se a entrada estiver dentro de um determinado intervalo aleatório (digamos, 12 a 67) e “não” se não estiver. Ou eles 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 você tenha um desses oráculos periódicos e não conheça o período. Tudo o que você pode fazer é alimentá-lo com números e ver o que ele produz. Com essas restrições, com que rapidez um computador poderia encontrar o período? Em 1993, Daniel Simon, então na Universidade de Montreal, descobriu que um algoritmo quântico poderia calcular a resposta para um problema intimamente relacionado exponencialmente mais rápido do que qualquer algoritmo clássico.
O resultado permitiu a Simon determinar um dos primeiros indícios de onde a superioridade dramática dos computadores quânticos poderia ser esperada. Mas quando ele submeteu seu artigo a uma importante conferência, foi rejeitado. O artigo, no entanto, interessou um membro júnior do comitê de programa da conferência – Peter Shor, que na época estava nos Laboratórios Bell em Nova Jersey. Shor descobriu que poderia adaptar o algoritmo de Simon para calcular o período de um oráculo, se ele tivesse um. Então ele 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 equação que descreve a fatoração, que é periódica.
O resultado de Shor foi histórico. O algoritmo quântico que ele descobriu poderia reduzir rapidamente números gigantescos em seus fatores primos constituintes, algo que nenhum algoritmo clássico conhecido pode fazer. Nos anos que se seguiram, os pesquisadores descobriram outros algoritmos quânticos eficientes. Alguns deles, como o algoritmo de Shor, até forneceram vantagem exponencial, mas ninguém conseguiu provar uma vantagem quântica dramática em qualquer problema NP que não fosse periódico.
Essa escassez de progresso levou dois cientistas da computação, Scott Aaronson da Universidade do Texas, Austin, e Andris Ambainis da Universidade da Letónia, para fazer uma observação. Provas de vantagem quântica sempre pareceram depender de oráculos que tinham algum tipo de estrutura não aleatória, como periodicidade. Em 2009, eles conjecturado que não poderia haver acelerações dramáticas em problemas NP que fossem aleatórios ou não estruturados. Ninguém poderia encontrar uma exceção.
Sua conjectura colocou um limite nos poderes dos computadores quânticos. Mas dizia apenas que não havia acelerações dramáticas para um tipo específico de problema NP não estruturado – aqueles com respostas sim ou não. Se um problema envolvesse descobrir respostas quantitativas mais específicas, o que é conhecido como problema de busca, a conjectura não se aplicava.
Pensando nisso, pesquisadores Takashi Yamakawa dos Laboratórios de Informática Social da NTT e Mark Zhandry da NTT Research e da Princeton University decidiram experimentar um problema de busca específico, introduzido em 2005 por Oded Regev.
Imagine um conjunto de cata-ventos que estão todos apontando na mesma direção. Dê a cada um deles um empurrão medido, depois deixe que uma rajada de vento influencie sua direção. Regev queria determinar, com base em suas direções finais, para onde todos apontavam inicialmente. Problemas como esse passaram a ser chamados de “aprender com erros”, pois o empurrão e o vento atuam como uma fonte de erro aleatório na direção original. Há evidências de que é difícil resolver tanto para algoritmos clássicos quanto quânticos.
Yamakawa e Zhandry ajustaram a configuração. Eles modificaram a força desses shoves iniciais, tornando-os mais previsíveis. Eles também fizeram com que o vento fosse determinado por um oráculo aleatório para que fosse ainda mais aleatório em certos casos, mas completamente adormecido em outros.
Com essas modificações, os pesquisadores descobriram que um algoritmo quântico poderia encontrar com eficiência a direção inicial. Eles também provaram que qualquer algoritmo clássico deve ser mais lento por um fator exponencial. Assim como Shor, eles adaptaram seu algoritmo para resolver uma versão real do problema, que substitui o oráculo por uma equação matemática real.
Os cientistas da computação ainda estão trabalhando para entender e desenvolver o problema. Vaikuntanathan o compara a um diferente que surge ao fazer a compactação de dados: quando as informações estão sendo compactadas, dois bits podem ser compactados acidentalmente no mesmo lugar, substituindo-os. O problema de prever essas colisões com antecedência, para que você possa evitá-las, tem alguma semelhança. “Essa é uma classe de problemas que basicamente se parece com isso”, disse ele. “Talvez esses problemas possam ser resolvidos quanticamente.”
Havia esperanças de que um problema não estruturado como o novo pudesse ser solucionado mesmo nas versões atuais de computadores quânticos, fornecendo assim um meio de testá-los. O pensamento era que problemas não estruturados poderiam exigir menos recursos para programar ou serem menos sensíveis a ruídos, uma vez que já são aleatórios. Mas até agora, o novo problema ainda parece avançado demais para os computadores quânticos existentes resolverem. “É um problema estranho. Eu não tinha pensado em defini-lo”, disse Aaronson. “Mas, em retrospecto, tem alguns recursos muito bons.”
O resultado fornece o primeiro exemplo de vantagem quântica dramática em um problema NP não estruturado. Poderia haver muitos outros problemas que o mundo quântico muda de praticamente insolúvel para solucionável? Agora há mais razões para pensar assim.
“É um pouco derrubado nossas crenças sobre quais tipos de problemas os computadores quânticos poderiam ser bons”, disse O'Donnell.
