A reduction scheme for general-order Ising-like Hamiltonians in quantum heuristic solvers

Resumo Técnico: Redução de Hamiltoniano Geral para Modelos de Tipo Ising de Ordem Superior

Declaração do Problema
O modelo de Ising é um arcabouço padrão para codificar problemas de otimização combinatória, onde encontrar o estado fundamental corresponde a encontrar a solução ótima. Embora solvers heurísticos (ex: recozimento quântico, bifurcação simulada) tenham avançado, eles frequentemente lutam contra a explosão combinatória inerente a instâncias de grande escala. Uma estratégia comum de pré-processamento é a redução de Hamiltoniano, que visa diminuir o número de variáveis lógicas ao identificar subconjuntos de spins que mantêm configurações relativas fixas em todos os estados fundamentais.

Técnicas de redução existentes, como o FastHare e a dualidade de telhado (roof duality), são projetadas primariamente para modelos de Ising de segunda ordem (quadráticos). No entanto, muitos problemas de otimização práticos, incluindo satisfatibilidade e modelos de rede de ordem superior, formulam-se naturalmente como Hamiltonianos de tipo Ising de ordem superior contendo interações de múltiplos corpos. Métodos atuais não conseguem lidar diretamente com esses termos de ordem superior e, embora existam técnicas de redução de ordem para converter problemas de ordem superior em quadráticos, elas frequentemente introduzem variáveis auxiliares, aumentando o tamanho do problema. Há uma carência de esquemas especializados de redução de Hamiltoniano para interações de ordem geral.

Metodologia
Os autores propõem o GeneralHare (GH), um framework que generaliza a teoria de grupos não separáveis (NGs) para modelos de tipo Ising de ordem arbitrária. A metodologia central envolve três componentes principais:

1. Grupos Não Separáveis Generalizados (gNGs):
   O artigo estende a definição de NGs (onde todos os spins de um grupo compartilham o mesmo sinal em todos os estados fundamentais) para gNGs. Um gNG é um subconjunto de spins que mantém uma configuração relativa específica (ex: $\sigma_a = -\sigma_b = \sigma_c$) em todos os estados fundamentais, ou seu inverso global. Isso permite a fusão de spins com correlações internas complexas, não apenas os idênticos.

2. Critérios Computáveis para Identificação:
   Calcular o índice de não-separabilidade exato (o gap de energia entre configurações separáveis e não separáveis) é NP-difícil. Para tornar o algoritmo tratável, os autores derivam limites inferiores facilmente computáveis ($\hat{\nu}_H(X)$) para o índice de não-separabilidade.

   • O método decompõe o Hamiltoniano por ordem de interação ($m$).
   • Utiliza uma estimativa de limite inferior que evita a minimização sobre todas as possíveis configurações de spin, considerando, em vez disso, bisseções específicas do grupo candidato $X$.
   • Se o limite inferior $\hat{\nu}_H(X) > 0$, o grupo é identificado como um grupo não separável. Se $\hat{\nu}_H(X) = 0$, ele é tratado como um grupo "fracamente" não separável.

3. O Algoritmo GeneralHare:
   O esquema opera iterativamente em rodadas até que não sejam mais possíveis reduções:

   • Fixação de Nós: Antes de identificar os grupos, nós com termos lineares (biases) que dominam suas interações locais são fixados a valores específicos ($\pm 1$), removendo-os efetivamente e reduzindo a ordem das hiperarestas incidentes.
   • Identificação: O algoritmo varre as hiperarestas (até um limite de tamanho $\xi$) para detectar gNGs e gNGs fracos usando os critérios de limite inferior derivados.
   • Ampliação: Usando a propriedade de "fechamento sob união", gNGs sobrepostos são fundidos para formar grupos maiores.
   • Compressão: Os grupos identificados são fundidos em nós únicos. Isso envolve inverter spins para alinhar as configurações relativas, fundir nós e agregar os pesos das hiperarestas paralelas. Constantes aditivas resultantes deste processo são rastreadas para preservar a correspondência dos estados fundamentais.
   • Otimização: Para melhorar a velocidade, o algoritmo restringe as buscas de candidatos aos vizinhos atualizados e emprega a fusão simultânea de gNGs fracos independentes.

Principais Resultados
Os autores testaram o GeneralHare em hipergrafos sintéticos (Erdős-Rényi e Scale-Free) e conjuntos de dados de redes de ordem superior públicos (ex: redes de contato, redes de e-mail).

• Desempenho de Redução:
  • Em dados sintéticos, o GeneralHare alcança razões de redução significativas (até ~50% em hipergrafos scale-free esparsos).
  • A eficiência da redução diminui conforme a densidade do grafo (grau médio) aumenta e conforme a ordem de interação sobe (grafos de quarta ordem mostraram aproximadamente metade da razão de redução de grafos de terceira ordem).
  • Em conjuntos de dados do mundo real, as razões de redução variaram de 2,1% a 67,4%, com 5 de 7 instâncias excedendo 20%.
• Comparação com FastHare (Caso de Segunda Ordem):
  • Quando aplicado a modelos de Ising de segunda ordem, o GeneralHare supera o algoritmo FastHare padrão em termos de razão de redução, identificando mais grupos não separáveis devido aos seus critérios generalizados.
  • O GeneralHare incorre em um tempo de execução computacional mais alto em grafos muito pequenos, mas escala eficientemente, mostrando um ponto de cruzamento (tornando-se mais rápido ou comparável) em aproximadamente 5.000 nós.
• Integração com Redução de Ordem:
  • O artigo avalia um pipeline combinando GeneralHare com redução de ordem (quadratização) e solvers subsequentes.
  • Os resultados indicam que aplicar o GeneralHare antes da quadratização (especificamente usando o demonstrador conservador GH_minimal) resulta em um menor overhead de variáveis final em comparação com aplicar o FastHare após a quadratização.
  • A estratégia mais eficaz identificada é um pipeline combinado: GeneralHare $\to$ Quadratização $\to$ FastHare.

Significância e Alegações
O artigo afirma que o GeneralHare estabelece uma base para a redução de Hamiltoniano em problemas de otimização de tipo Ising de ordem superior. Suas principais contribuições são:

1. Extensão Teórica: Ele generaliza com sucesso a teoria de não-separabilidade de modelos de segunda ordem para modelos de ordem arbitrária, abordando a falta de tais técnicas para interações de ordem superior.
2. Eficiência Prática: Fornece uma ferramenta de pré-processamento que reduz o tamanho lógico dos problemas, potencialmente melhorando o desempenho de solvers heurísticos subsequentes (tanto clássicos quanto de inspiração quântica) ao reduzir o espaço de busca.
3. Preservação dos Estados Fundamentais: O método garante que os estados fundamentais do Hamiltoniano reduzido correspondam aos estados fundamentais do problema original através de um mapa de reconstrução explícito.

Os autores observam que, embora o método seja geralmente aplicável, sua eficácia pode variar dependendo da estrutura do problema (ex: distribuições de grau homogêneas em problemas 3-SAT podem resultar em menores razões de redução). Eles sugerem que trabalhos futuros possam envolver a combinação desta abordagem com solvers especializados, como solvers de SAT, para classes específicas de problemas.