Resumo Técnico: O Decatlo Intratável – Uma Biblioteca de Benchmarking para Otimização Quântica

Definição do Problema

O artigo aborda a necessidade crítica de um benchmarking sistemático, justo e comparável de algoritmos de otimização quântica heurística contra solvers clássicos de última geração. Embora o hardware quântico tenha avançado a um ponto onde o benchmarking em larga escala é viável, a área carece de um conjunto padronizado de instâncias de problemas que sejam simultaneamente difíceis para métodos clássicos em escalas gerenciáveis e relevantes para aplicações práticas.

Os autores introduzem o Decatlo Intratável, uma coleção de dez classes distintas de problemas de otimização combinatória. Estes problemas foram selecionados porque:

1. São difíceis para os solvers clássicos existentes (frequentemente exigindo prova de otimalidade ou a busca por soluções viáveis) em tamanhos de sistema que variam de menos de 100 a aproximadamente 100.000 variáveis de decisão.
2. São predominantemente "primalmente difíceis", o que significa que encontrar uma boa solução é difícil, o que se alinha com as capacidades dos atuais algoritmos quânticos heurísticos.
3. Mapeiam-se para aplicações praticamente relevantes em logística, finanças, design de redes e física.
4. Podem ser modelados usando variáveis inteiras (preferencialmente binárias) com coeficientes inteiros, mitigando problemas de precisão numérica comuns em formulações quânticas.

As dez classes de problemas são:

• Divisão de Mercado (Market Split): Problemas de soma de subconjuntos multidimensionais.
• Sequências Binárias de Baixa Autocorrelação (LABS): Busca por sequências binárias com autocorrelação mínima.
• Decomposição de Birkhoff Mínima: Decompor matrizes duplamente estocásticas no número mínimo de matrizes de permutação.
• Empacotamento de Árvore de Steiner (Steiner Tree Packing): Empacotar árvores de Steiner disjuntas em nós em um grafo.
• Escalonamento de Torneios Esportivos: Escalonar torneios de ida e volta (double round-robin) com restrições complexas.
• Otimização de Portfólio: Otimização de média-variância multiperíodo com custos de transação.
• Conjunto Independente Máximo (MIS): Encontrar o maior conjunto de vértices não adjacentes em um grafo.
• Design de Rede: Construir grafos direcionados para minimizar a carga máxima de arestas.
• Problema de Roteamento de Veículos (CVRP): Roteamento de veículos com capacidade e tamanho de frota fixo.
• Design de Topologia: Minimizar o diâmetro da rede dado o grau e a ordem (Problema de Ordem e Grau).

Metodologia

Os autores propõem um framework de benchmarking independente de modelo para permitir a máxima flexibilidade na escolha de algoritmos, modelos e plataformas de hardware. A metodologia inclui:

1. Formulação e Modelagem de Problemas

• Foco em Inteiros: Os problemas são definidos sobre variáveis de decisão inteiras $x \in \mathbb{Z}^n$ com objetivos e restrições lineares ou quadráticas. Os coeficientes são reescalonados para inteiros para evitar imprecisões numéricas.
• Agnosticismo de Modelo: Embora a biblioteca forneça formulações padrão de Programação Inteira Mista (MIP) e Otimização Binária Quadrática Não Restrita (QUBO), o objetivo do benchmarking não está vinculado a uma formulação específica. Isso reconhece que reformular um problema (ex: de ILP para QUBO) pode alterar drasticamente o tamanho e a densidade do problema, potencialmente introduzindo novos desafios ou vantagens para solvers específicos.
• Viabilidade vs. Otimização: O framework distingue entre problemas de viabilidade (encontrar qualquer solução válida) e problemas de otimização (encontrar a melhor solução). Dado que a maioria dos algoritmos quânticos são heurísticas sem garantias de otimalidade, o benchmark foca em encontrar soluções viáveis de alta qualidade em vez de provar a otimalidade global.

2. Métricas e Relatórios

Para garantir reprodutibilidade e comparabilidade, os autores definem métricas específicas:

• Qualidade da Solução: Melhor valor de objetivo encontrado através de repetições. Para algoritmos estocásticos, reporta-se o número de execuções bem-sucedidas (encontrar uma solução dentro de uma tolerância $\epsilon$ da melhor solução encontrada).
• Recursos Computacionais:
  • Tempo Total de Execução (Runtime): Tempo de relógio (wall-clock time) excluindo tempos de fila/inatividade.
  • Detalhamento de Hardware: Separação do tempo gasto em CPUs, GPUs, Unidades de Processamento Quântico (QPUs) e outros hardwares.
  • Definição de Tempo de Execução Quântica: Especificamente definida para a plataforma IBM Quantum como o tempo desde o recebimento do payload até a extração da amostra, incluindo preparação de circuito e execução, mas excluindo o tempo de transpilação clássica (que é atribuído ao pré-processamento).
• Diretrizes de Submissão: Um template padronizado (Tabela 10) é fornecido para a Biblioteca de Benchmarking de Otimização Quântica (QOBLIB) para garantir que todos os detalhes necessários (abordagem de modelagem, contagem de variáveis, intervalos de coeficientes, etapas de fluxo de trabalho) sejam capturados.

3. Geração de Instâncias

A biblioteca contém instâncias geradas para serem "primalmente difíceis". Para problemas onde encontrar uma solução viável é trivial, as instâncias são construídas através de engenharia reversa a partir de soluções conhecidas para garantir a dificuldade. As instâncias variam em densidade, intervalos de coeficientes e contagem de variáveis para testar diferentes gargalos algorítmicos.

Contribuições Principais

1. O Repositório QOBLIB: Uma biblioteca de código aberto contendo instâncias de problemas, modelos (MIP/QUBO), verificadores de solução e resultados de base (baseline).
2. O Decatlo Intratável: Um conjunto curado de dez classes de problemas que unem a dificuldade teórica à relevância prática, selecionados especificamente para serem desafiadores para solvers clássicos em tamanhos acessíveis ao hardware quântico de curto prazo.
3. Protocolo de Benchmarking Padronizado: Um conjunto rigoroso de definições para métricas, medição de tempo de execução (especialmente para hardware quântico) e formatos de relatório para facilitar a comparação justa entre diferentes abordagens quânticas e clássicas.
4. Resultados de Base (Baselines): O artigo fornece extensos resultados de base clássica usando solvers de última geração (ex: Gurobi, CPLEX, heurísticas especializadas) para estabelecer pisos de desempenho. Também apresenta resultados quânticos ilustrativos para três problemas específicos usando diferentes algoritmos quânticos.

Resultados e Exemplos Ilustrativos

O artigo apresenta baselines clássicos para todas as dez classes de problemas, demonstrando que muitas instâncias são atualmente insolúveis para otimalidade provada por solvers clássicos em tempos razoáveis, ou requerem recursos computacionais significativos.

Baselines Quânticos Ilustrativos:
Os autores fornecem resultados preliminares para três classes de problemas usando algoritmos quânticos específicos para demonstrar o formato de submissão e as capacidades atuais:

• Sequências Binárias de Baixa Autocorrelação (LABS):

  • Algoritmo: Otimização Quântica Contra-Diabática Digitalizada com Campo de Viés (BF-DCQO).
  • Resultado: Em uma sequência de comprimento $n=20$ (excedendo as implementações quânticas anteriores de $n=18$), o algoritmo encontrou soluções ótimas no dispositivo ibm marrakesh. O tempo médio de execução foi de ~61 segundos (incluindo pré/pós-processamento), com o tempo de QPU sendo de ~60,8 segundos.
  • Comparação: O escalonamento do BF-DCQO foi comparável ao QAOA com 12 camadas, mas exigiu seis vezes menos portas de emaranhamento. Superou os solvers clássicos exatos (Gurom, CPLEX) no tempo para solução para a instância específica testada, embora os solvers clássicos eventualmente tenham encontrado soluções ótimas para instâncias menores.

• Decomposição de Birkhoff Mínima:

  • Algoritmo: Algoritmo Quântico Variacional (VQA) usando um circuito quântico parametrizado para amostrar matrizes de permutação.
  • Resultado: Testado em matrizes duplamente estocásticas de $n=4$ e $n=5$. Para $n=4$, o algoritmo encontrou consistentemente decomposições exatas com 3–4 permutações, igualando ou superando solvers clássicos aproximados (Birkhoff+, Blended FW). Para $n=5$, o desempenho degradou, com apenas algumas instâncias alcançando decomposições esparsas, destacando as limitações atuais das abordagens variacionais em instâncias maiores e mais complexas.

• Conjunto Independente Máximo (MIS):

  • Algoritmo: Solver heurístico (ABS2) em hardware GPU.
  • Resultado: Forneceu dados de baseline de desempenho para grafos de até 4000 nós, mostrando a lacuna entre soluções heurísticas e limites ótimos, servindo como alvo para heurísticas quânticas.

Significância e Alegações

O artigo afirma que o QOBLIB e o Decatlo Intratável fornecem a infraestrutura necessária para mover o foco do benchmarking de componentes (ex: fidelidade de porta) para o benchmarking de nível de aplicação.

• Demonstrando Vantagem Quântica: Os autores afirmam que apenas resolvendo instâncias de problemas que são difíceis para computadores clássicos (dificuldade primal) pode-se demonstrar uma verdadeira vantagem quântica. As instâncias selecionadas foram desenhadas para serem intratáveis para solvers clássicos nos tamanhos em que dispositivos quânticos de curto prazo podem operar.
• Colaboração Comunitária: O trabalho é estruturado como um chamado à ação para a comunidade de otimização utilizar estas instâncias para rastrear o progresso em algoritmos, software e hardware.
• Modéstia sobre Capacidades Atuais: O artigo é modesto quanto ao desempenho quântico atual. Reconhece que, embora os algoritmos quânticos mostrem promessa e escalonamento (como em LABS $n=20$), eles ainda não superam consistentemente as melhores heurísticas clássicas em todos os campos. O objetivo principal é estabelecer uma forma padronizada para apresentar soluções de benchmarking que garanta comparabilidade, reprodutibilidade e a capacidade de rastrear melhorias ao longo do tempo.

Os autores concluem que este framework é essencial para verificar a correção dos algoritmos, identificar gargalos e, finalmente, determinar se os computadores quânticos podem oferecer uma vantagem prática na resolução de problemas de otimização combinatória do mundo real.