Towards Tensor-Network SAT-Solvers for Quantum-Classical Workflows

Resumo Técnico: Rumo a SAT-Solvers de Redes de Tensores para Fluxos de Trabalho Quântico-Clássicos

Definição do Problema
Sistemas integrados de Computação de Alto Desempenho/Computação Quântica (HPC/QC) exigem mais do que simples mecanismos de despacho para kernels quânticos; eles necessitam de substitutos clássicos para observabilidade, execução de contingência (fallback) e tomada de decisão consciente de custos. No entanto, os substitutos clássicos devem navegar pela inescapável complexidade de pior caso exponencial da simulação clássica. Este trabalho investiga a eficácia dos métodos de redes de tensores, especificamente o Density Matrix Renormalization Group (DMRG), como um substituto para resolver problemas de satisfatibilidade booleana (SAT) dentro de fluxos de trabalho híbridos. O estudo foca em como as transformações de codificação do problema — especificamente a redução de problemas de ordem superior para formas quadráticas — afetam o desempenho desses substitutos clássicos em comparação com representações nativas e baselines clássicos como o Simulated Annealing (SA).

Metodologia
Os autores implementaram um pipeline de execução de ponta a ponta para comparar o DMRG contra o Simulated Annealing (SA) em instâncias de Max-3-SAT. O fluxo de trabalho experimental envolveu:

1. Geração de Instâncias: Instâncias de Max-3-SAT uniformes foram geradas com números variados de variáveis ($n$) e cláusulas ($m$).
2. Caminhos de Transformação: Dois caminhos de compilação distintos foram comparados:
   • Caminho Nativo: Max-3-SAT $\rightarrow$ Função Pseudo-Booleana (PUBO) $\rightarrow$ Modelo de Ising de Ordem Superior $\rightarrow$ Operador de Produto de Matriz (MPO).
   • Caminho Quadratizado: Max-3-SAT $\rightarrow$ PUBO $\rightarrow$ Quadratização para Otimização Binária Não Constrangida Quadrática (QUBO) via Redução de Estrutura Local (LSR) $\rightarrow$ Modelo de Ising Quadrático $\rightarrow$ MPO.
3. Otimização: Ambos os caminhos foram codificados como MPOs e otimizados usando um algoritmo DMRG de dois sítios (two-site). Uma configuração vanilla de DMRG foi utilizada com hiperparâmetros randomizados (varreduras, erro de truncamento, dimensão de ligação) ao longo de 100 ensaios independentes por instância.
4. Baseline: O SA foi empregado como um baseline de desempenho clássico com esquemas de resfriamento estocásticos.
5. Métricas: O desempenho foi avaliado com base no tempo de execução e no desvio em relação à energia do estado fundamental (GS) exato, derivado do panorama de energia da PUBO.

Principais Contribuições e Descobertas

• Impacto da Quadratização: O estudo demonstra que a quadratização não é um passo de transformação neutro. Converter formulações nativas de PUBO de ordem superior para QUBO via variáveis auxiliares e acoplamentos de pares degrada substancialmente a qualidade da solução. No regime QUBO (quadrático), tanto o DMRG quanto o SA exibiram desvios monotonicamente crescentes em relação ao estado fundamental conforme o tamanho do problema aumentava, com desvios excedendo 10–15% para instâncias maiores.
• Superioridade da Codificação Nativa: Em contraste, a representação nativa de Ising de ordem superior (PUBO) manteve desvio próximo de zero em todo o intervalo testado para ambos os solvers. Isso sugere que o overhead introduzido pelas variáveis auxiliares no processo de quadratização impacta negativamente a eficiência da contração de redes de tensores e da varredura variacional.
• Desempenho do Solver: O Simulated Annealing consistentemente igualou ou superou o DMRG em todas as instâncias e codificações testadas. O tempo de execução do DMRG escalou com o número de variáveis em ambas as codificações, frequentemente excedendo significativamente o tempo de execução do SA.
• Natureza do Espaço de Solução: Os autores atribuem a falta de vantagem do DMRG à natureza dos problemas derivados de SAT. Uma vez que as soluções ótimas para satisfatibilidade booleana são estados de produto clássicos (não emaranhados), a principal força do DMRG — representar eficientemente o emaranhamento de muitos corpos com dimensões de ligação limitadas — não se materializa neste contexto.

Significância e Alegações
O artigo postula que a seleção de substitutos (surrogates) em tempos de execução de HPC/QC deve ser "consciente da codificação e da instância". As descobertas desafiam a suposição de que métodos de redes de tensores são substitutos clássicos universalmente superiores para tarefas de otimização quântica. Em vez disso, os autores argumentam que:

• Design de Compilador e Tempo de Execução: Escolhas de representação (ex: nativa vs. quadratizada) dominam o comportamento do solver e devem ser tratadas como decisões de primeira classe no design do compilador.
• Papel dos Substitutos: O DMRG deve ser visto não como um solver universal, mas como um substituto clássico limitado. Seu valor em sistemas integrados reside em fornecer observabilidade e referências reproduzíveis para depuração de sub-rotinas quânticas — tarefas impossíveis com abordagens puramente quânticas, especialmente sob imperfeições NISQ — em vez de superar heurísticas clássicas para classes específicas de problemas como SAT.
• Framework de Decisão: Os dados empíricos fornecidos servem como uma base para o desenvolvimento de políticas de offloading conscientes de custo, ajudando sistemas a decidir quando substituir tarefas quânticas por substitutos clássicos com base nas características específicas de codificação e instância.