Um novo algoritmo quântico acelera a resolução de uma enorme classe de problemas

A versão original desta história apareceu na Quanta Magazine .

Para cientistas da computação, resolver problemas é um pouco como escalar montanhas. Primeiro, eles precisam escolher um problema para resolver — semelhante a identificar um pico para escalar — e, em seguida, desenvolver uma estratégia para resolvê-lo. Pesquisadores clássicos e quânticos competem usando estratégias diferentes, com uma rivalidade saudável entre os dois. Pesquisadores quânticos relatam uma maneira rápida de resolver um problema — geralmente escalando um pico que ninguém achava que valia a pena escalar —, então equipes clássicas correm para ver se conseguem encontrar uma maneira melhor.

Essa disputa quase sempre termina em um empate virtual: quando pesquisadores acham que criaram um algoritmo quântico que funciona mais rápido ou melhor do que qualquer outro, pesquisadores clássicos geralmente criam um que se iguala a ele. Na semana passada, uma suposta aceleração quântica, publicada na revista Science , foi recebida com ceticismo imediato por dois grupos distintos que demonstraram como realizar cálculos semelhantes em máquinas clássicas.

Mas em um artigo publicado no site de pré-impressão científica arxiv.org no ano passado, pesquisadores descreveram o que parece ser uma aceleração quântica convincente e útil . Os pesquisadores descreveram um novo algoritmo quântico que funciona mais rápido do que todos os clássicos conhecidos na busca de boas soluções para uma ampla classe de problemas de otimização (que buscam a melhor solução possível entre um enorme número de opções).

Até o momento, nenhum algoritmo clássico destronou o novo algoritmo, conhecido como interferometria quântica decodificada (DQI). É "um avanço nos algoritmos quânticos", disse Gil Kalai , matemático da Universidade Reichman e um cético proeminente da computação quântica . Relatos de algoritmos quânticos empolgam os pesquisadores, em parte porque podem iluminar novas ideias sobre problemas complexos e, em parte, porque, apesar de toda a agitação em torno das máquinas quânticas, não está claro quais problemas realmente se beneficiarão delas. Um algoritmo quântico que supere todos os clássicos conhecidos em tarefas de otimização representaria um grande avanço no aproveitamento do potencial dos computadores quânticos.

"Estou entusiasmado com isso", disse Ronald de Wolf , cientista teórico da computação do CWI, o instituto nacional de pesquisa em matemática e ciência da computação da Holanda, que não esteve envolvido com o novo algoritmo. Mas, ao mesmo tempo, ele alertou que ainda é bem possível que os pesquisadores eventualmente encontrem um algoritmo clássico que funcione tão bem quanto. E, devido à falta de hardware quântico, ainda levará algum tempo até que possam testar o novo algoritmo empiricamente.

O algoritmo pode inspirar novos trabalhos na área clássica, de acordo com Ewin Tang , cientista da computação da Universidade da Califórnia, Berkeley, que ganhou destaque na adolescência ao criar algoritmos clássicos que se equiparam aos quânticos . As novas alegações "são interessantes o suficiente para que eu dissesse aos especialistas em algoritmos clássicos: 'Ei, vocês deveriam ler este artigo e trabalhar neste problema'", disse ela.

Quando algoritmos clássicos e quânticos competem, eles frequentemente o fazem no campo de batalha da otimização, um campo focado em encontrar as melhores opções para resolver um problema complexo. Pesquisadores geralmente se concentram em problemas em que o número de soluções possíveis aumenta exponencialmente à medida que o problema se torna maior. Qual é a melhor maneira de um caminhão de entrega visitar 10 cidades em três dias? Como você deve embalar as encomendas na caçamba? Métodos clássicos de resolução desses problemas, que frequentemente envolvem a busca de possíveis soluções de maneiras inteligentes, rapidamente se tornam insustentáveis.

O problema específico de otimização que o DQI aborda é basicamente este: você recebe um conjunto de pontos em uma folha de papel. Você precisa criar uma função matemática que passe por esses pontos. Especificamente, sua função precisa ser um polinômio — uma combinação de variáveis ​​elevadas a expoentes inteiros e multiplicadas por coeficientes. Mas não pode ser muito complicada, o que significa que as potências não podem ser muito altas. Isso resulta em uma reta curva que oscila para cima e para baixo à medida que se move pela página. Sua tarefa é encontrar a reta sinuosa que toca o maior número de pontos.

Variações desse problema aparecem em diversas formas na ciência da computação, especialmente na codificação de erros e na criptografia — áreas focadas na codificação segura e precisa de dados à medida que são transmitidos. Os pesquisadores do DQI reconheceram, basicamente, que traçar uma linha melhor é semelhante a deslocar uma mensagem codificada com ruído para mais perto de seu significado preciso.

Mas tudo isso veio depois. Quando os pesquisadores por trás do DQI começaram a trabalhar em seu algoritmo, eles nem sequer tinham esse problema em mente.

“Teria sido perfeitamente plausível para um pesquisador orientado a objetivos começar definindo o problema e, em seguida, investigar se algoritmos quânticos poderiam resolvê-lo mais rapidamente do que algoritmos clássicos”, disse Stephen Jordan , físico do Google Quantum AI e um dos principais arquitetos do DQI. “É claro que, para nós, não foi assim que aconteceu. Chegamos a ele por um caminho tortuoso e inverso.”

Jordan embarcou nessa jornada em 2023, quando ingressou no Google e descobriu que trabalharia com Eddie Farhi , um físico do Google cujo trabalho há muito se concentra em algoritmos quânticos que superam os clássicos. (Farhi já foi orientador de doutorado de Jordan no Instituto de Tecnologia de Massachusetts.) Jordan sabia que, em 2014, Farhi havia feito um ataque quântico a um problema de otimização pensando em energia, com energias mais baixas correspondendo a melhores soluções. Para Farhi, a energia conectava a otimização à física quântica.

Mas Jordan queria fazer algo diferente. Ele se voltou para outro conceito inerente à física quântica: reconhecer tudo como ondas. Usando uma ferramenta matemática chamada transformada quântica de Fourier, Jordan encontrou uma maneira de traduzir todas as respostas potenciais para uma classe bem conhecida de problemas de otimização em ondas quânticas. Ao fazer isso, ele conseguiu manipular o sistema quântico de modo que ondas maiores (na forma de amplitudes quânticas mais elevadas) correspondessem a soluções melhores.

Mas ainda havia um enorme desafio a ser superado. Em um sistema quântico, perguntar "Qual é a maior amplitude?" não é tão simples quanto reconhecer a maior onda na praia. O cenário quântico é incrivelmente complexo, e não estava claro como identificar as amplitudes quânticas que corresponderiam às melhores soluções.

Após muitos começos frustrados, Jordan fez um grande avanço: o processo de seleção das melhores soluções revelou-se semelhante ao processo de eliminação de erros em mensagens codificadas, conhecido como decodificação. Esta é uma área bem estudada da ciência da computação, repleta de técnicas que Jordan poderia explorar. Ao traduzir um problema de otimização para um problema quântico e, em seguida, aplicar a lente da decodificação a ele, ele havia descoberto uma nova maneira de desenvolver algoritmos quânticos.

Juntamente com Noah Shutty , também do Google, Jordan começou a testar esquemas de decodificação, observando como eles se saíam em relação a algoritmos clássicos em diversos problemas de otimização. Eles precisavam tanto da abordagem correta quanto de um problema em que ela funcionasse. "Acontece que algoritmos clássicos são difíceis de superar", disse Jordan. "Depois de alguns meses de tentativas, ainda não havíamos conquistado nenhuma vitória para a computação quântica."

Mas, eventualmente, a dupla chegou a um algoritmo de decodificação introduzido pela primeira vez na década de 1960 para encontrar e corrigir erros individuais em uma mensagem codificada. Encontrar esse problema foi a chave. "Quando investigamos, parece que obtivemos sucesso quase imediatamente", disse Jordan. Finalmente, eles encontraram um problema e uma abordagem que, juntos, pareciam uma aceleração quântica.

Claro, isso não significava que fosse infalível. "Talvez exista algum método clássico que possa replicar toda a sua abordagem com eficiência", disse Jordan. "Tais desquantizações nem sempre são óbvias."

Para amenizar esses temores, eles consultaram Mary Wootters , especialista em teoria da codificação (e ex-orientadora de doutorado de Shutty na Universidade Stanford). Ela procurou cuidadosamente por qualquer algoritmo clássico conhecido que pudesse corresponder à sua aceleração quântica. A vantagem se manteve. As verificações da equipe também sugerem que ela continuará se mantendo. "Eles fizeram a devida diligência", disse Tang.

Fortalecidos por essa análise, eles examinaram com mais cuidado o problema de otimização que estavam resolvendo. Jordan temia que pudesse ser um problema de nicho, sem aplicações mais amplas, mas Shutty reconheceu que esse problema de decodificação era uma variação de problemas bem conhecidos e úteis em criptografia e outras áreas.

Jordan reconhece que, sem uma máquina quântica suficientemente grande, o DQI continuará sendo um avanço teórico. "O DQI não pode ser executado nos computadores quânticos atuais", disse ele. Mas eles ainda estão avançando. Desde que o grupo publicou seu trabalho em agosto passado, eles estenderam a aplicação do DQI além do problema original para uma classe mais ampla de problemas de otimização, que inclui mais casos desses problemas de "melhor caminho".

Até agora, disse Jordan, ele espera que o DQI possa superar algoritmos clássicos nesses problemas também.

Por enquanto, a comunidade quântica continua eufórica. "Encontrar algoritmos quânticos que demonstrem uma vantagem sobre os algoritmos clássicos é um empreendimento muito empolgante das últimas três décadas, e o número de algoritmos definitivos que demonstram tal vantagem não é grande", disse Kalai. "Portanto, cada novo algoritmo é motivo de comemoração."

História original reimpressa com permissão da Quanta Magazine , uma publicação editorialmente independente da Fundação Simons cuja missão é aumentar a compreensão pública da ciência cobrindo desenvolvimentos e tendências de pesquisa em matemática e ciências físicas e biológicas.