Um Algoritmo Heurístico Variacional Eficiente em Qubits para MaxCut

Por que chips quânticos minúsculos importam para grandes enigmas

Muitas tarefas do mundo real — desde o posicionamento de circuitos eletrônicos até a modelagem de materiais — reduzem-se a separar uma rede em dois grupos enquanto se cortam o máximo possível de conexões entre eles. Esse desafio, conhecido como MaxCut, é notoriamente difícil para computadores clássicos. O artigo apresenta um novo método inspirado em quântica que consegue lidar com redes surpreendentemente grandes usando apenas um punhado de bits quânticos (qubits), oferecendo uma maneira nova de testar e melhorar ferramentas de otimização, tanto quânticas quanto clássicas.

Dividindo uma rede em duas metades úteis

MaxCut formula uma pergunta de aparência simples: se você tem um conjunto de pontos (vértices) conectados por linhas (arestas), como deve colorir cada vértice, digamos azul ou branco, para que o maior número possível de linhas ligue vértices de cores diferentes? Essa melhor divisão possível é valiosa em áreas como projeto de circuitos e física estatística, mas é muito difícil de encontrar exatamente quando a rede é grande. Uma abordagem clássica amplamente usada, o algoritmo de Goemans–Williamson (GW), faz uma relaxação inteligente do problema e é garantido que encontra um corte que é pelo menos cerca de 88% tão bom quanto o ótimo verdadeiro. A computação quântica promete novas maneiras de atacar tais problemas, mas os dispositivos atuais são ruidosos e limitados em tamanho, o que dificulta executar circuitos grandes e profundos.

Resolvendo grafos grandes com apenas alguns qubits

Abordagens quânticas padrão, como o Quantum Approximate Optimization Algorithm (QAOA), exigem um qubit por vértice da rede, de modo que um grafo com 1.000 vértices demandaria 1.000 qubits — muito além das máquinas atuais. O novo método, chamado Qubit-Efficient MaxCut (QEMC), inverte essa escala: usa apenas aproximadamente o logaritmo do número de vértices, o que significa que 11 qubits podem codificar informações sobre mais de 2.000 vértices. Em vez de vincular cada qubit a um único vértice, o QEMC usa o estado quântico inteiro como um espaço de endereçamento compacto e permite que vértices diferentes correspondam a diferentes estados de base desse pequeno registrador. Essa economia de qubits mantém os circuitos rasos e mais fáceis de executar em hardware ruidoso, ao mesmo tempo em que representa grafos muito grandes.

Colorindo vértices por probabilidade em vez de estados fixos

A inovação chave é como o QEMC codifica a “cor” de cada vértice. Em vez de forçar cada vértice a ser exatamente azul ou branco em um único estado quântico, o método permite que a cor de cada vértice seja inferida a partir da probabilidade de sua observação na medição. Um vértice cujo estado de base aparece com baixa probabilidade é tratado como uma cor; um vértice com probabilidade mais alta é tratado como a outra. Um valor-limiar separa os dois regimes. Isso significa que muitos estados quânticos diferentes correspondem essencialmente à mesma partição do grafo. A função de custo que o QEMC minimiza é construída de modo que vértices conectados sejam incentivados a ficar em lados opostos desse limiar de probabilidade, o que tende a aumentar o número de arestas que cruzam entre os dois grupos de cores e, portanto, melhora o corte.

Testando desempenho em máquinas reais e simuladas

Os autores testam o QEMC em duas frentes: processadores quânticos reais e simulações clássicas dos circuitos quânticos. Em grafos regulares pequenos com até 32 vértices (usando apenas 2 a 5 qubits), o QEMC executado em hardware superconductivo da IBM encontra cortes que coincidem ou quase coincidem com as melhores respostas possíveis encontradas por busca exaustiva, superando claramente o palpite aleatório e estudos quânticos anteriores baseados em QAOA. Em simulações sem ruído, o QEMC alcança consistentemente mais de 97% do corte ótimo para esses grafos pequenos. O poder da codificação torna-se ainda mais aparente para grafos maiores: para grafos 9-regulares com até 2.048 vértices, simulações clássicas do QEMC ainda superam o GW tanto em cortes médios quanto nos melhores cortes por alguns pontos percentuais, e vantagens semelhantes são observadas em grafos aleatórios de 128 vértices com diferentes densidades.

Velocidade, limites e promessa inspirada em quântica

Apesar do sucesso, o QEMC ainda não entrega uma aceleracão quântica formal. Como usa apenas cerca de log N qubits, simular seus circuitos classicamente também escala aproximadamente de forma linear com o número de vértices, e o tempo necessário para avaliar a função de custo cresce com o número de arestas. Estudos empíricos sugerem que o tempo total para atingir desempenho ao nível do GW cresce cerca de forma quadrática com o tamanho do grafo, o que ainda é alcançável na prática para muitos problemas. Isso significa que o QEMC, na sua forma atual, funciona mais como uma heurística poderosa inspirada em quântica do que como uma prova de vantagem quântica.

O que este trabalho significa para o futuro

Para um não-especialista, a mensagem principal é que pequenos dispositivos quânticos ruidosos ainda podem ser cientificamente úteis se projetarmos algoritmos que se ajustem às suas forças. Ao codificar as cores dos vértices em faixas de probabilidade flexíveis em vez de valores rígidos de bits, o QEMC usa pouquíssimos qubits para enfrentar problemas de redes muito grandes e tolera naturalmente o ruído do hardware. O método estabelece um novo referencial para testar algoritmos de otimização quântica e também gera um algoritmo clássico prático baseado nas mesmas ideias. Mais amplamente, demonstra como repensar a forma como a informação é codificada — em vez de apenas construir máquinas maiores — pode abrir caminhos promissores para resolver problemas computacionais difíceis.

Citação: Tene-Cohen, Y., Kelman, T., Lev, O. et al. A Variational Qubit-Efficient MaxCut Heuristic Algorithm. npj Quantum Inf 12, 50 (2026). https://doi.org/10.1038/s41534-026-01186-2

Palavras-chave: MaxCut, otimização quântica, algoritmos variacionais, particionamento de grafos, computação inspirada em quântica