⚛️ quantum physics

Minimum Bisection Problem: Machine Learning-Based Penalty Parameter Tuning for Optimization on Quantum Annealers

Este artigo propõe um framework baseado em aprendizado de máquina que ajusta automaticamente o parâmetro de penalidade para o Problema da Bisseção Mínima em quantum annealers, utilizando Regressores de Gradient Boosting para prever intervalos de penalidade eficazes e demonstrando desempenho superior sobre heurísticas clássicas como o Metis na geração de partições balanceadas com valores de corte menores.

Autores originais: Renáta Rusnáková, Martin Chovanec, Juraj Gazda

Publicado 2026-08-25

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Renáta Rusnáková, Martin Chovanec, Juraj Gazda

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 pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine uma vasta rede de estradas, computadores ou linhas de energia, todos conectados em uma teia complexa. Para gerenciar tal sistema de forma eficiente, engenheiros frequentemente precisam dividi-lo em dois metades iguais, garantindo que os dois novos grupos sejam equilibrados em tamanho enquanto se cortam o mínimo de conexões entre eles. Essa tarefa, conhecida como problema da bisseção mínima, é um desafio clássico na ciência da computação. Ela é fundamental para tudo, desde o design de microchips até a organização de centros de dados, mas encontrar a divisão perfeita é notoriamente difícil. À medida que a rede cresce, o número de maneiras possíveis de realizar o corte explode, tornando quase impossível para computadores tradicionais verificarem todas as opções. Nos últimos anos, um novo tipo de computador, chamado de recozimento quântico (quantum annealer), surgiu como uma ferramenta potencial para enfrentar esses problemas difíceis. Essas máquinas não calculam respostas passo a passo como um notebook padrão; em vez disso, elas usam as estranhas regras da física quântica para explorar muitas possibilidades ao mesmo tempo, buscando o estado de menor energia, que corresponde à melhor solução. No entanto, para que essas máquinas quânticas funcionem corretamente, o problema deve ser traduzido para um formato matemático específico, e uma parte crucial dessa tradução envolve um valor de "penalidade". Esse valor atua como uma regra estrita que força a máquina a manter as duas metades de tamanho igual. Se a penalidade for muito fraca, a máquina ignora a regra e produz um resultado desequilibrado e inútil. Se for muito forte, a máquina torna-se tão focada na regra que esquece de minimizar os cortes reais, levando a uma solução ruim. Encontrar o equilíbrio certo para essa penalidade tem sido, tradicionalmente, uma questão de tentativa e erro manual e de suposição.

Uma equipe de pesquisadores da Universidade Técnica de Košice, na Eslováquia, desenvolveu uma nova maneira de resolver esse jogo de adivinhação. Em vez de pedir a um humano para ajustar o valor da penalidade para cada nova rede, eles ensinaram um programa de computador a prever a configuração perfeita automaticamente. Os pesquisadores começaram gerando centenas de mapas de redes aleatórias, variando de pequenos aglomerados a vastas teias com milhares de nós. Para cada mapa, eles realizaram experimentos em um sistema quântico fornecido pela D-Wave Systems, testando uma ampla gama de valores de penalidade para ver quais produziam os melhores resultados. Eles descobriram que o valor de penalidade ideal não era aleatório; ele seguia um padrão baseado no tamanho da rede e na densidade com que os nós estavam conectados. Usando esses dados, eles treinaram dois modelos de aprendizado de máquina, especificamente um tipo de algoritmo conhecido como regressor de gradient boosting, para atuar como um preditor. Esses modelos aprenderam a olhar para uma nova rede não vista, contar seus nós, medir sua densidade e calcular uma estimativa inicial aproximada, para então fornecer uma faixa precisa para o valor da penalidade que provavelmente funcionaria melhor.

Quando os pesquisadores testaram este novo método em 126 redes completamente novas, os resultados foram impressionantes. Em todos os casos, o sistema de aprendizado de máquina guiou o solver quântico para encontrar uma divisão perfeitamente equilibrada. Além disso, a qualidade dessas divisões foi superior à produzida pelas melhores ferramentas de software tradicionais atualmente disponíveis. O software tradicional, que depende de algoritmos clássicos estabelecidos, falhou em produzir uma divisão equilibrada em cerca de metade dos casos de teste. Mesmo quando conseguia equilibrar os grupos, o número de conexões que precisava cortar era consistentemente maior do que o alcançado pelo sistema quântico com a penalidade ajustada pelo aprendizado de máquina. Os pesquisadores descobriram que essa melhoria se manteve em todos os tamanhos testados, desde pequenas redes de 100 nós até enormes redes com 4.000 nós. A abordagem de aprendizado de máquina essencialmente removeu a necessidade do processo tedioso de testar diferentes valores, permitindo que o sistema quântico se concentrasse inteiramente em encontrar a solução ideal.

O estudo também analisou como este método performou no hardware quântico real, em vez de apenas no sistema híbrido que combina processamento clássico e quântico. Para redes menores, o hardware quântico direto mostrou-se promissor, muitas vezes superando os métodos tradicionais, embora tenha tido mais dificuldades com as conexões muito densas encontradas em alguns grafos. Os pesquisadores observaram que o sucesso de sua abordagem depende fortemente do tipo específico de redes aleatórias que usaram para o treinamento. Embora o método tenha funcionado perfeitamente para esses mapas sintéticos, eles alertam que ele precisaria ser retreinado e testado em redes do mundo real, como mapas rodoviários reais ou redes sociais, antes de ser usado nesses contextos. Eles também apontaram que a limitação atual do hardware quântico significa que, para problemas muito grandes, o sistema híbrido continua sendo a ferramenta mais prática, pois pode realizar o trabalho pesado de preparar o problema enquanto a parte quântica busca pela solução.

Em última análise, este trabalho demonstra que o aprendizado de máquina pode servir como uma ponte vital entre problemas de otimização complexos e tecnologias quânticas emergentes. Ao automatizar o ajuste de parâmetros críticos, os pesquisadores tornaram o processo de recozcimento quântico mais confiável e eficaz. Suas descobertas sugerem que, à medida que os computadores quânticos continuam a evoluir, o pareamento com sistemas de ajuste inteligentes e baseados em dados será essencial para resolver problemas do mundo real que são atualmente difíceis demais para os computadores clássicos lidarem de forma eficiente. O estudo não afirma ter resolvido o problema da bisseção mínima para todos os cenários possíveis, mas fornece um framework robusto e comprovado para fazer as soluções quânticas funcionarem melhor do que nunca, transformando um processo que antes exigia intuição especializada em algo que pode ser tratado por um algoritmo treinado.

Resumo Técnico: Ajuste de Parâmetro de Penalidade Baseado em Aprendizado de Máquina para Bisseção Mínima em Recozedores Quânticos

Definição do Problema
O Problema da Bisseção Mínima (MBP) é um problema fundamental de particionamento de grafos NP-difícil que requer a divisão dos nós de um grafo em dois subconjuntos de tamanhos iguais, minimizando o número de arestas que os conectam. Embora o MBP tenha aplicações em computação paralela e design de redes, resolvê-lo via Recozimento Quântico (Quantum Annealing) exige a formulação do problema como um modelo de Otimização Binária Quadrática Não Restrita (QUBO). Um desafio crítico nesta formulação é a seleção do parâmetro de penalidade ( $\lambda$ ), que impõe a restrição de equilíbrio (tamanhos iguais dos subconjuntos). Se $\lambda$ for muito pequeno, o resolvedor retorna soluções infactíveis que violam a restrição de equilíbrio; se for muito grande, o termo de penalidade domina a função objetivo, obscurecendo o objetivo de minimização do corte. Os métodos atuais dependem de ajuste manual ou heurísticas estáticas, que são frequentemente dependentes do problema e não confiáveis em diferentes estruturas de grafos.

Metodologia
Os autores propõem uma estrutura orientada por dados para automatizar a seleção de $\lambda$ especificamente para o MBP em recozedores quânticos. A abordagem procede através de quatro estágios:

Limites Teóricos e Estimativa Inicial:
Os autores derivam uma estimativa inicial dependente do grafo ( $\lambda_{est}$ ) analisando o panorama de energia. Eles estabelecem um limite inferior teórico ( $\lambda \ge 1$ ) e um limite superior prático baseado no grau máximo de nó e no tamanho do grafo ( $\lambda \le \min(\Delta(G), n/2 - 1)$ ). A estimativa inicial é definida como o ponto médio deste intervalo. Este método baseia-se exclusivamente em propriedades mensuráveis do grafo ( $n$ e $\Delta(G)$ ), em vez dos parâmetros geradores do grafo, garantindo a aplicabilidade a grafos de entrada arbitrários.
Escalonamento Empírico e Calibração:
Experimentos preliminares revelaram que o ponto médio teórico frequentemente exigia maior escalonamento, particularmente para grafos maiores. Os autores conduziram uma fase de calibração utilizando 607 grafos de Erdős–Rényi ( $G(n, p)$ ) com tamanhos de até 4000 nós. Eles testaram vários multiplicadores ( $\lambda_{mult}$ ) aplicados ao $\lambda_{est}$ para identificar intervalos de valores que resultassem em partições equilibradas válidas com tamanhos de corte mínimos usando o resolvedor híbrido quântico-clássico da D-Wave (QA HS).
Predição por Aprendizado de Máquina:
Para eliminar a necessidade de busca manual custosa sobre multiplicadores candidatos, os autores treinaram dois modelos de Regressor de Gradient Boosting (GBR).

Entradas: Os modelos recebem três características: o número de nós ( $n$ ), a densidade realizada do grafo ( $\rho$ ) e a estimativa de penalidade inicial ( $\lambda_{est}$ ).
Saídas: Um modelo prevê o limite inferior ( $\lambda_{min}$ ) e o outro prevê o limite superior ( $\lambda_{max}$ ) do intervalo de multiplicador efetivo.
Cálculo Final: O parâmetro de penalidade final é computado como $\lambda = \lambda_{est} \times \frac{\lambda_{min} + \lambda_{max}}{2}$ .

Avaliação Experimental:
Os modelos treinados foram avaliados em 126 grafos de Erdős–Rényi gerados independentemente (até 4000 nós) e comparados com baselines clássicos: Metis (particionamento multinível) e Kernighan–Lin (refinamento local). Experimentos diretos no QPU também foram conduzidos em grafos menores ( $n \le 100$ ) para avaliar o desempenho específico do hardware.

Principais Contribuições

Estrutura Específica para MBP: O artigo introduz uma estrutura que combina uma estimativa analítica dependente do grafo com aprendizado de máquina para prever um intervalo de multiplicador de penalidade efetivo, indo além do ajuste de penalidade genérico.
Conjunto de Dados de Calibração: Os autores geraram e utilizaram um conjunto de dados de 607 grafos de Erdős–Rényi para treinar os modelos e avaliar em 126 instâncias não vistas, cobrindo uma ampla gama de tamanhos (até 4000 nós) e densidades.
Validação de Desempenho: O estudo demonstra que a seleção de penalidade aprendida permite que o resolvedor híbrido encontre partições equilibradas para 100% das instâncias de avaliação, uma melhoria significativa em relação às estimativas heurísticas iniciais.

Resultos

Factibilidade: Sob o setup experimental adotado, os parâmetros de penalidade previstos pelo GBR permitiram que o resolvedor híbrido da D-Wave retornasse partições equilibradas para todas as 126 instâncias de avaliação.
Qualidade da Solução: O resolvedor híbrido usando as penalidades previstas alcançou valores de corte menores (menos arestas de corte) do que o Metis em 100% dos casos avaliados. A análise estatística usando o teste de postos sinalizados de Wilcoxon confirmou que essas diferenças foram significativas ( $p < 0,001$ ).
Desempenho Direto no QPU: Para grafos pequenos ( $n \le 100$ ), o QPU superou o Metis na maioria das instâncias para $n \ge 80$ , embora o desempenho tenha sido misto para grafos menores, provavelmente devido ao modelo ter sido treinado principalmente em instâncias maiores.
Precisão do Modelo: O modelo GBR para o limite superior ( $\lambda_{max}$ ) alcançou um score $R^2$ de 0,9028. O modelo do limite inferior ( $\lambda_{min}$ ) teve um $R^2$ menor (0,4489) devido à baixa variância nos valores alvo, mas manteve um erro absoluto baixo (MAE 0,0124).

Significância e Alegações
O artigo afirma que sua principal contribuição não é o conceito geral de ajuste automático de penalidade, mas uma estrutura específica para MBP que deriva um intervalo de penalidade empiricamente efetivo a partir de propriedades básicas do grafo. Os autores afirmam que essa abordagem orientada por dados melhora a confiabilidade e a qualidade da solução do MBP em recozedores quânticos, reduzindo a necessidade de testes repetidos de parâmetros manuais.

O estudo posiciona-se como um passo para tornar as formulações QUBO mais robustas para o hardware quântico. Os autores explicitamente observam que seus resultados são específicos para a distribuição de grafos de Erdős–Rényi e para a configuração do resolvedor híbrido da D-Wave utilizada. Eles não alegam superioridade universal sobre todos os algoritmos clássicos (por exemplo, reconhecem que o Metis é significativamente mais rápido em termos de tempo de execução bruto), mas argumentam que o ajuste proposto torna a abordagem quântica competitiva em qualidade de solução, garantindo a factibilidade. O trabalho futuro é identificado como a extensão da estrutura para outras famílias de grafos, benchmarks do mundo real e problemas de $k$ -particionamento.

Mais como este