← Últimos artigos
⚛️ física quântica

Max-Cut QAOA on Non-Hardware-Native Graphs via MinLA Surrogates and Configuration Recovery

Este artigo propõe um fluxo de trabalho híbrido quântico-clássico que reduz a profundidade do circuito QAOA em grafos não nativos de hardware através da construção de modelos substitutos baseados em MinLA com menos interações e, subsequentemente, recuperando soluções próximas da otimalidade para o problema MAX-CUT original por meio de estratégias de refinamento clássico.

Autor original: K. Bharati, Nathan Earnest-Noble, Ritajit Majumdar

Publicado 2026-11-16
📖 7 min de leitura🧠 Leitura aprofundada

Autor original: K. Bharati, Nathan Earnest-Noble, Ritajit Majumdar

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelo autor. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Na corrida para construir computadores quânticos úteis, os cientistas estão atualmente navegando por um difícil meio-termo. Eles possuem máquinas que podem realizar cálculos específicos muito mais rapidamente do que os computadores tradicionais, mas essas máquinas ainda são frágeis e limitadas em tamanho. Uma das formas mais promissoras de utilizá-las é resolver quebra-cabeças complexos conhecidos como problemas de otimização, onde o objetivo é encontrar a melhor configuração possível entre milhões de opções. Um método líder para fazer isso é chamado de Algoritmo de Otimização Aproximada Quântica. Ele funciona preparando um estado quântico que representa muitas respostas possíveis ao mesmo tempo e, em seguida, refinando-o para encontrar a melhor. No entanto, existe um grande obstáculo: os chips quânticos reais não foram construídos para lidar diretamente com todos os tipos de quebra-cabeças. Os chips possuem um layout específico e esparso de conexões entre suas minúsculas unidades de processamento, enquanto muitos problemas interessantes envolvem redes densas de conexões que não se encaixam. Para forçar um problema incompatível em um chip, os engenheiros devem inserir etapas extras para mover informações entre unidades distantes, um processo que adiciona camadas de complexidade e ruído. Esse ruído frequentemente destrói a delicada informação quântica antes que a resposta possa ser encontrada, deixando a máquina incapaz de resolver os próprios problemas que deveria enfrentar.

Pesquisadores da IBM Research e do Instituto Indiano de Tecnologia Madras desenvolveram uma nova estratégia para contornar esse gargalo, permitindo que computadores quânticos resolvam problemas de grafos maiores e mais complexos do que o possível anteriormente. A abordagem deles, testada em um processador de 156 qubits, envolve um fluxo de trabalho inteligente de duas etapas que equilibra o que a máquina quântica pode fazer com o que um computador clássico pode corrigir. Em vez de tentar forçar todo o problema complexo no chip de uma só vez, a equipe primeiro cria uma versão "substituta" simplificada do problema que se ajusta aos limites físicos do chip. Eles alcançam isso reordenando os componentes do problema para que as conexões mais importantes sejam curtas e locais, selecionando então apenas as conexões que podem ser executadas sem sobrecarregar a máquina com etapas de roteamento propensas a erros. Isso permite que o computador quântico execute um circuito muito mais curto e limpo e gere um conjunto de soluções candidatas.

A verdadeira inovação reside no que acontece a seguir. Os pesquisadores não aceitam simplesmente a saída do computador quântico como a resposta final. Em vez disso, eles pegam as melhores soluções candidatas geradas pelo circuito quântico simplificado e as alimentam em um computador clássico. Este computador clássico então realiza um processo de refinamento rigoroso e passo a passo para reparar a informação que foi deixada de fora durante a simplificação. Ele avalia os candidatos contra o problema original completo e complexo e os melhora sistematicamente até que alcancem um estado quase perfeito. Ao separar o trabalho pesado de amostragem quântica do polimento final da resposta, a equipe conseguiu resolver instâncias de um problema de grafo clássico chamado MAX-CUT em grafos com até 100 vértices. Esses grafos eram excessivamente densos para serem executados diretamente no hardware, mas o método híbrido produziu soluções que eram quase tão boas quanto as melhores respostas teóricas possíveis.

O núcleo deste método baseia-se em uma forma específica de organizar os dados do problema antes mesmo de chegarem ao chip quântico. Os pesquisadores usaram uma técnica matemática chamada Arranjo Linear Mínimo para reordenar os vértices do grafo. Imagine o problema como um mapa de cidades conectadas por estradas; o objetivo é encontrar uma maneira de dividir as cidades em dois grupos de modo que o número de estradas que cruzam entre os grupos seja maximizado. Em um chip quântico padrão, as conexões entre as cidades são fixas e esparsas. Se as cidades no problema estiverem longe umas das outras no mapa, o chip deve construir pontes longas e sinuosas para conectá-las, o que introduz erros. A técnica de ordenação dos pesquisadores rearranja as cidades para que aquelas com muitas conexões entre si sejam colocadas logo ao lado uma da outra na sequência. Isso permite que eles selecionem uma "banda" de interações que estão todas próximas, descartando as conexões longas e caras que exigiriam muitas etapas propensas a erros para serem executadas.

Este processo de seleção é guiado por um orçamento estrito para a profundidade do circuito, que é essencialmente uma medida de quantas etapas consecutivas o computador quântico deve realizar. Os pesquisadores determinaram a banda mais larga possível de conexões que poderia caber dentro desse limite de profundidade para o seu hardware específico. Eles garantiram que cada cidade no problema permanecesse parte do modelo simplificado, mesmo que algumas de suas conexões fossem temporariamente ignoradas. Isso criou um Hamiltoniano substituto, uma versão simplificada do panorama de energia do problema que o computador quântico realmente poderia executar. Quando rodaram este circuito simplificado no processador IBM, descobriram que ele reduzia o número de etapas necessárias em mais da metade em comparação com a tentativa de rodar o problema completo, mantendo, ainda assim, uma parte significativa da estrutura do grafo original. Para os maiores grafos testados, que tinham quase mil conexões, o método manteve cerca de metade das interações, um feito que teria sido impossível com técnicas anteriores que reduziam o grafo a uma simples cadeia.

O computador quântico então amostrou milhares de soluções potenciais a partir deste panorama simplificado. Como o circuito era mais curto e limpo, as soluções produzidas foram de maior qualidade do que as de uma tentativa de profundidade total ruidosa teriam sido. No entanto, essas soluções ainda eram baseadas em uma imagem incompleta do problema. Para corrigir isso, a equipe empregou duas estratégias de recuperação clássica distintas. A primeira foi uma abordagem gananciosa (greedy) que olhava para cada cidade individualmente e invertia sua atribuição de grupo se isso melhorasse o número total de estradas que cruzavam. A segunda estratégia, mais sofisticada, olhava para pares de grupos de cidades e resolvia um tipo específico de problema de otimização para encontrar a melhor maneira de rearranjá-los juntos. Este segundo método, que utiliza uma técnica relacionada à busca do corte mínimo em uma rede, permitiu que o sistema escapasse de armadilhas locais onde uma mudança única não ajudaria, mas uma mudança coordenada ajudaria.

Os resultados deste fluxo de trabalho híbrido foram impressionantes. Em grafos com 100 vértices, a saída bruta do computador quântico, mesmo após ser simplificada, já era muito boa. Mas após a etapa de recuperação clássica, a qualidade das soluções saltou dramaticamente. As melhores soluções encontradas após a recuperação alcançaram uma razão de aproximação de quase 0,997, o que significa que estavam a apenas 0,3 por cento da melhor resposta absoluta. Isso foi verdade mesmo que o computador quântico nunca tenha executado o conjunto completo e complexo de interações exigido pelo problema original. Os pesquisadores verificaram que essa melhoria veio inteiramente do refinamento clássico, pois o processo de recuperação rodou independentemente de cada solução candidata sem precisar de mais tempo no processador quântico.

Este trabalho demonstra que as limitações do hardware quântico atual não impedem necessariamente que ele resolva problemas grandes e complexos. Ao reconhecer as restrições do hardware e projetar um fluxo de trabalho que as respeite, os pesquisadores mostraram que é possível extrair sinais úteis de uma execução quântica simplificada e ampliá-los através da computação clássica. O método é particularmente poderoso porque é escalável: à medida que os processadores quânticos melhoram e podem tolerar circuitos mais profundos, a "banda" de interações pode ser alargada para incluir mais do problema original, exigindo menos trabalho do computador clássico. Por outro lado, para as máquinas ruidosas de hoje, o método fornece um caminho prático, provando que uma combinação de simplificação consciente do hardware e recuperação clássica pode entregar soluções de alta qualidade para problemas que antes estavam fora de alcance. O estudo confirma que o futuro da otimização quântica pode não estar em esperar por máquinas perfeitas e livres de erros, mas em construir sistemas híbridos inteligentes que saibam trabalhar com as ferramentas imperfeitas disponíveis atualmente.

Afogado em artigos na sua área?

Receba digests diários dos artigos mais recentes que correspondam às suas palavras-chave de pesquisa — com resumos técnicos, no seu idioma.

Experimentar Digest →