QAOA Inside ADMM: Subproblem Wins Do Not Become Decomposition Wins at Matched Budgets

No mundo da tomada de decisão complexa, os computadores frequentemente enfrentam problemas com milhões de respostas possíveis, onde encontrar a única melhor é como procurar uma agulha em um palheiro que muda de forma constantemente. Para lidar com isso, cientistas usam uma estratégia chamada decomposição, que quebra um problema massivo e emaranhado em peças menores e gerenciáveis que podem ser resolvidas separadamente. Um método popular para fazer isso é o método de multiplicadores de direção alternada, ou ADMM. Ele funciona alternando entre resolver as partes contínuas de um problema e as partes discretas, de ligar/desligar, trocando informações até que as peças se encaixem. Por anos, pesquisadores se perguntaram se computadores quânticos, que operam sob as estranhas regras da mecânica quântica, poderiam resolver essas peças discretas mais rapidamente do que computadores clássicos. O principal candidato para este trabalho é um algoritmo conhecido como algoritmo de otimização aproximada quântica, ou QAOA, que é projetado para encontrar boas soluções explorando muitas possibilidades ao mesmo tempo. A grande questão tem sido se essa abordagem quântica realmente vale o custo e o esforço em comparação com os métodos clássicos muito fortes que já possuímos.

Uma equipe de pesquisadores partiu para responder a isso, colocando o algoritmo quântico à prova rigorosa dentro da estrutura ADMM. Eles não apenas rodaram o computador quântico e esperaram pelo melhor; eles construíram uma comparação justa onde tanto o solver quântico quanto o clássico receberam exatamente a mesma quantidade de esforço computacional, ou "orçamento", para resolver as peças menores do quebra-cabeça. O estudo focou em um tipo específico de problema onde as variáveis são binárias, significando que elas podem ser apenas zero ou um. Os pesquisadores rodaram simulações em uma versão perfeita e sem ruído de um computador quântico de doze qubits para ver como o solver quântico se comportava contra um conjunto de solvers clássicos, incluindo busca aleatória, recozimento simulado (simulated annealing) e técnicas mais avançadas como a busca tabu. Eles testaram o sistema em dois tipos diferentes de famílias de problemas: uma que era relativamente suave e fácil, e outra que era irregular e difícil, projetada para imitar os cenários complexos encontrados em aplicações do mundo real.

A descoberta mais surpreendente veio de como os resultados eram contados. No mundo da computação quântica, uma única execução de um algoritmo produz um fluxo de respostas potenciais, ou bitstrings, e o algoritmo gasta a maior parte do tempo ajustando suas configurações internas para melhorar essas respostas. Os pesquisadores descobriram que o veredito final dependia inteiramente de qual resposta era escolhida para representar a execução. Se os pesquisadores creditassem ao computador quântico apenas seu último conjunto de respostas, como é comum em alguns tutoriais de software padrão, o solver quântico performava pior do que uma simples busca aleatória. Ele falhava em encontrar a melhor solução com mais frequência do que um computador que apenas adivinhava aleatoriamente. No entanto, quando os pesquisadores creditaram ao solver quântico sua única melhor resposta encontrada em qualquer ponto durante toda a sua execução, a história mudou completamente. Sob esta pontuação de "melhor amostra" (best-sample), o solver quântico superou a busca aleatória e até venceu vários métodos clássicos sofisticados nos problemas difíceis e irregulares no nível do subproblema. Isso revelou que a percepção de falha da abordagem quântica era frequentemente um artefato de como os dados eram pontuados, e não uma falha da própria física.

Quando os pesquisadores olharam mais profundamente para o desempenho de uma versão específica do algoritmo quântico que utilizava configurações pré-treinadas, conhecidas como ângulos transferidos, descobriram que ela podia resolver os subproblemas difíceis com uma precisão notável. Na família de problemas irregulares, essa abordagem quântica encontrou a solução exata melhor mais vezes do que métodos de busca local ajustados (97,3% contra 67,4% para as heurísticas locais mais fortes), embora não tenha superado uma técnica clássica baseada em programação semidefinida (SDP+LS). No entanto, essa vantagem não se transferiu para o resultado final do problema global. O estudo descobriu que nenhuma família deu ao QAOA um resultado final de ADMM melhor do que o melhor solver clássico e penalidade. Os pesquisadores calcularam que, para o mesmo tamanho de problema, a abordagem quântica levou aproximadamente cinquenta vezes mais tempo em segundos do que um método clássico chamado busca tabu. Além disso, o desempenho do método quântico não escalou tão bem quanto os clássicos; conforme os problemas cresciam, a vantagem do solver quântico no número de tentativas desaparecia, e ele ficava atrás de uma técnica clássica baseada em programação semidefinida.

O estudo também descobriu uma falha sutil, mas crítica, na forma como o próprio método de decomposição funciona. Os pesquisadores descobriram que, para certos tipos de problemas, a maneira como as peças são remontadas depende fortemente de um parâmetro chamado penalidade. Quando essa penalidade era definida em um valor específico, o método de decomposição essencialmente resolvia todo o problema diretamente, tornando a qualidade do sub-solver irrelevante. Mas quando a penalidade era mais alta, o método às vezes ficava preso em uma solução subótima, recusando-se a avançar mesmo que uma melhor existisse. Nesses casos, a natureza "ruidosa" do solver quântico, que mantinha suas respostas mudando, na verdade ajudava o sistema a escapar dessas armadilhas e encontrar uma solução global melhor do que um solver perfeito e exato que ficaria preso. Isso sugeriu que o sucesso do solver quântico não era sempre devido à sua natureza quântica, mas às vezes porque ele se comportava como uma busca aleatória, que é uma forma conhecida de escapar de armadilhas locais em cenários de otimização difíceis.

Em última análise, o artigo conclui que, embora os algoritmos quânticos mostrem promessa na resolução de subproblemas específicos com alta precisão, eles ainda não demonstraram uma vantagem clara sobre os melhores métodos clássicos quando todo o sistema é considerado. O solver quântico não proporcionou um resultado final melhor para o problema global do que o melhor solver clássico poderia alcançar com as configurações corretas. O estudo destaca que, para a computação quântica ser verdadeiramente útil nesses sistemas híbridos, ela deve não apenas encontrar boas respostas, mas fazê-lo em menos tempo e com melhor escalabilidade do que as alternativas clássicas. Os pesquisadores descobriram que, embora a abordagem quântica pudesse igualar os solvers clássicos em precisão sob condições específicas, ela era significativamente mais lenta e não escalava tão eficientemente. O trabalho serve como um necessário choque de realidade, mostrando que o caminho para a vantagem quântica não é apenas construir um hardware quântico melhor, mas projetar cuidadosamente como essas máquinas são usadas dentro de estruturas clássicas maiores.