Accuracy and Performance Evaluation of Quantum, Classical and Hybrid Solvers for the Max-Cut Problem

Resumo Técnico: Avaliação de Precisão e Desempenho de Solvers Quânticos, Clássicos e Híbridos para o Problema Max-Cut

Definição do Problema
Este estudo aborda o problema Max-Cut, que é NP-difícil, e sua formulação equivalente, o problema de Otimização Binária Quadrática Não Restrita (QUBO). O objetivo é particionar os vértices de um grafo não direcionado ponderado em dois conjuntos disjuntos de tal forma que a soma dos pesos das arestas que conectam os conjuntos seja maximizada. O artigo avalia a capacidade de vários solvers de encontrar soluções próximas do ótimo global, reconhecendo que, para instâncias grandes, soluções exatas são frequentemente computacionalmente intratáveis, necessitando de heurísticas aproximadas.

Metodologia e Configuração Experimental
Os autores conduziram um estudo de benchmarking abrangente utilizando três conjuntos de dados distintos compostos por 139 instâncias de problemas com tamanhos variando de 100 a 10.000 nós.

• Conjuntos de Dados:
  1. Billionnet e Elloumi (be): 50 instâncias com $n \in \{101, 121, 151\}$. Os ótimos globais foram computados usando os solvers exatos BiqBin e MADAM.
  2. Coleção Beasley (bqp): 20 instâncias com $n \in \{251, 501\}$. Os ótimos para $n=251$ foram computados exatamente; para $n=501$, foram utilizados os melhores valores conhecidos da literatura.
  3. Conjunto de dados G (G): 69 instâncias com $n \in \{800, 1000, 2000, 3000, 5000, 7000, 8000, 9000, 10000\}$. Os ótimos globais são desconhecidos; os melhores valores conhecidos da literatura foram usados como benchmarks.
• Solvers Avaliados:
  • Recozimento Quântico (QPU): Sistema D-Wave Advantage utilizando um recurso de "recoimento rápido" (fast annealing) para isolar os qubits de efeitos ambientais. Limitado a instâncias com $n \le 151$.
  • Solver Híbrido: "LeapHybridSampler" da D-Wave, baseado em nuvem, que combina iterativamente métodos clássicos (simulated annealing interrompível, busca tabu, parallel tempering) com chamadas de QPU. Capaz de lidar com todos os tamanhos de instância.
  • Simulated Annealing Clássico (SA): Duas variantes do algoritmo de [3] foram implementadas:
    • SA1: Tamanho de passo agressivo, temperatura inicial de 10.000 (otimizado para tempo de execução comparável ao QPU).
    • SA2: Tamanho de passo conservador, temperatura inicial de 40.000 (otimizado para qualidade da solução).
  • Simulated Bifurcation Machine (SBM): O solver de hardware da Toshiba. Os resultados foram obtidos de literatura existente [4], pois os autores não tiveram acesso direto ao solver.

Principais Resultados

• Instâncias Pequenas ($n \le 151$): O solver Híbrido e ambas as variantes de SA (SA1, SA2) alcançaram consistentemente o ótimo global para todas as instâncias. O QPU, no entanto, produziu consistentemente soluções significativamente distantes do ótimo global.
• Instâncias Médias ($n = 251, 501$): O solver Híbrido e as variantes de SA novamente igualaram os ótimos globais (para $n=251$) ou os melhores valores conhecidos (para $n=501$). O QPU não pôde ser testado devido a limites de capacidade.
• Instâncias Grandes ($n \ge 800$):
  • Qualidade da Solução: O SBM e o SA2 produziram as soluções de maior qualidade, frequentemente encontrando os melhores valores conhecidos. O solver Híbrido apresentou desempenho visivelmente inferior ao SBM e ao SA2, enquanto o SA1 produziu as soluções de menor qualidade entre os métodos testados.
  • Tempo Computacional: O solver Híbrido e o SBM demonstraram tempos de computação eficientes (segundos a dezenas de segundos). O SA2 exigiu significativamente mais tempo (centenas de segundos, aproximadamente 1000x mais lento que o Híbrido/SBM em algumas comparações) para alcançar uma qualidade de solução superior. O SA1 teve um tempo de execução comparável ao do solver Híbrido, mas rendeu soluções inferiores.

Significância e Alegações
O artigo afirma avançar a compreensão da otimização assistida por quantum ao testar rigorosamente o novo QPU de recozimento rápido da D-Wave e o solver Híbrido contra métodos clássicos de última geração em um conjunto padronizado e publicamente disponível de instâncias Max-Cut.

Os autores concluem que:

1. Limitações do QPU: O QPU da D-Wave, mesmo com recozimento rápido, falha em encontrar soluções ótimas para as instâncias testadas e é limitado pelo tamanho do problema ($n \le 151$).
2. Eficácia Híbrida: O solver Híbrido da D-Wave é altamente eficiente em termos de velocidade e escalabilidade (lidando com até 10.000 nós) e produz soluções próximas do ótimo para instâncias menores. No entanto, para as maiores instâncias, é superado em qualidade de solução pelo SA clássico (especificamente a variante SA2) e pelo SBM.
3. Competitividade Clássica: Algoritmos de simulated annealing clássicos transparentes (especificamente a variante SA2) permanecem altamente competitivos, muitas vezes superando o solver Híbrido de "caixa-preta" em qualidade de solução, embora com um custo computacional mais elevado.
4. Lacuna de Transparência: Os autores expressam frustração em relação à natureza de "caixa-preta" do solver Híbrido, observando que a falta de insights sobre seu fluxo de trabalho interno e a utilização de recursos quânticos dificulta a análise científica.

O estudo não reivindica uma vantagem quântica para os solvers e instâncias de problema específicos testados; em vez disso, destaca que, para o Max-Cut, heurísticas clássicas atuais (quando ajustadas para qualidade) e hardware especializado como o SBM podem superar ou igualar o desempenho das abordagens quântica e híbrida testadas.