Quantum-Inspired Algorithm for Classical Spin Hamiltonians Based on Matrix Product Operators

Resumo Técnico: Algoritmo de Inspiração Quântica para Hamiltonianos de Spin Clássicos Baseado em Operadores de Produto de Matrizes

Definição do Problema
O artigo aborda o desafio de resolver problemas de otimização combinatória (COPs) formulados como Hamiltonianos de spin clássico de vidro de spin. Esses problemas, que incluem a busca pelos estados fundamentais de modelos de Ising com interações competitivas, são geralmente NP-difíceis devido ao tamanho exponencial do espaço de configuração e à presença de frustração. Métodos heurísticos clássicos, como o Simulated Annealing (SA) e Algoritmos Genéticos, frequentemente produzem soluções próximas da ótima, mas podem ter dificuldades com paisagens de energia complexas. Por outro:// lado, algoritmos de inspiração quântica que utilizam redes de tensores, como o Density-Matrix Renormalization Group (DMRG), são eficientes, mas propensos a ficarem presos em mínimos locais, particularmente quando a paisagem de energia exibe grandes degenerescências.

Metodologia
Os autores propõem uma abordagem de "powered-MPO" que combina filtragem espectral com representações de redes de tensores para resolver esses problemas de otimização em hardware clássico. A metodologia procede através dos seguintes passos:

1. Transformação do Hamiltoniano: O Hamiltoniano de custo $\hat{H}$ é deslocado e escalonado para formar um novo operador $\hat{G} = a\hat{H} + b\hat{I}$. Os parâmetros $a$ e $b$ são escolhidos de modo que $\hat{G}$ seja semidefinido positivo e os estados fundamentais do problema original correspondam aos maiores autovalores de $\hat{G}$.
2. Amplificação Espectral: O operador $\hat{G}$ é elevado a uma potência alta $K$ (ou seja, $\hat{G}^K$). Esta operação amplifica exponencialmente os pesos relativos das configurações com os maiores autovalores (os estados fundamentais de $\hat{H}$), enquanto suprime as demais.
3. Representação por Rede de Tensores:
   • $\hat{G}$ é representado como um Operador de Produto de Matrizes (MPO).
   • A potência $\hat{G}^K$ é construída via contrações repetidas de MPO-MPO. Os autores utilizam dois cronogramas de contração: um cronograma "linear" (multiplicando repetidamente por $\hat{G}$) e um cronograma de "dobramento" (elevando o resultado ao quadrado iterativamente, $K=2^m$).
   • Durante a contração, a dimensão de ligação é truncada usando Decomposição de Valor Singular (SVD) com um limiar fixo para gerenciar o custo computacional, mantendo uma dimensão de ligação máxima $\chi$.
4. Amostragem: O MPO resultante é incorporado em um Estado de Produto de Matrizes (MPS) ao agir sobre um estado de superposição uniforme $|+\rangle^{\otimes N}$. Como $\hat{G}^K$ é diagonal na base computacional, esta incorporação permite uma "amostragem perfeita" de bitstrings. A probabilidade de amostrar uma configuração é proporcional ao quadrado de seu elemento diagonal correspondente em $\hat{G}^K$, enviesando a saída para estados de baixa energia.

Principais Contribuições

• Filtragem Espectral Livre de Trotter: Ao contrário dos métodos de evolução no tempo imaginário quântico que dependem de decomposições de portas e Trotterização, esta abordagem incorpora a função de custo não unitária diretamente em um único MPO clássico, evitando erros de Trotter.
• Melhoria Sistemática: O artigo demonstra que, diferentemente do DMRG, que pode estagnar em mínimos locais, o método powered-MPO oferece uma rota mais sistemática para melhoria ao aumentar a dimensão de ligação $\chi$.
• Construção Eficiente: Os autores detalham a construção do MPO para funções de custo gerais e fornecem limites teóricos para a potência $K$ necessária para atingir uma probabilidade de sucesso alvo, mostrando que $K$ escala inversamente com o gap espectral e logaritmicamente com a dimensão do espaço de Hilbert.
• Cronograma Híbrido: O estudo identifica forças complementares entre os cronogramas de contração linear e de dobramento: o dobramento fornece uma filtragem inicial rápida, enquanto a evolução linear oferece um refinamento contínuo e estável nas etapas posteriores.

Resultados
Os autores testaram o método em duas classes de problemas:

1. Modelos de Vidro de Spin de Edwards-Anderson: Testados em redes hipercúbicas de $D$ dimensões ($D=2, 3$).
   • O método powered-MPO superou consistentemente o DMRG, particularmente quando o DMRG foi inicializado com um estado de superposição uniforme, onde ele frequentemente ficou preso em mínimos locais.
   • Enquanto os resultados do DMRG mostraram pouca melhoria com o aumento da dimensão de ligação nestes casos, o método powered-MPO mostrou uma melhoria sistemática na razão de aproximação conforme $\chi$ aumentava.
   • O método identificou com sucesso estados fundamentais exatos para tamanhos de sistema menores e configurações de baixa energia para instâncias maiores (até $N=400$ variáveis).
2. Modelos de Ising de Ordem Superior em Redes Hexagonais Pesadas: Testados em redes relevantes para dispositivos quânticos atuais da IBM (problemas HUBO com até interações cúbicas).
   • O método powered-MPO (com $\chi=64$) superou o Simulated Annealing (tanto o padrão quanto as formulações QUBO de ordem reduzida) na busca por configurações de menor energia.
   • O método provou ser robusto contra as paisagens de energia acidentadas características desses problemas, sendo que o cronograma linear eventualmente superou o desempenho do cronograma de dobramento em potências mais altas ($m \geq 12$).

Significância e Alegações
O artigo alega que esta abordagem de inspiração quântica fornece uma linha de base clássica robusta para resolver problemas de otimização combinatória, navegando efetivamente em paisagens de energia onde heurísticas tradicionais e métodos variacionais como o DMRG encontram dificuldades.

• Linha de Base para Algoritmos Quânticos: Os autores postulam que as soluções de alta qualidade geradas por este método baseado em redes de tensores podem servir como um benchmark crítico para avaliar a utilidade e a vantagem de futuros algoritmos e hardwares quânticos.
• Escalabilidade e Direções Futuras: Os autores observam que, embora o método exija mais etapas do que o DMRG para convergir, ele evita o aprisionamento local. Eles sugerem que trabalhos futuros possam aproveitar o paralelismo em nível de MPI e aceleração por GPU para lidar com maiores dimensões de ligação ($\chi \sim O(10^3)$). Além disso, propõem que estender o método para redes de tensores em árvore ou desenvolver técnicas de contração mais estáveis para Operadores de Par Entrançado Projetado (PEPOs) poderia aumentar ainda mais sua aplicabilidade a topologias de rede complexas.
• Limitações Modestas: O artigo reconhece que alcançar soluções exatas para todos os tipos de problemas ainda exige superar barreiras de emaranhamento elevadas, e que a escala da dimensão de ligação necessária através de diferentes classes de problemas precisa de uma clarificação mais sistemática. Notam também que as limitações atuais de hardware (contagem de qubits e operações não locais) impedem a implementação direta da função de custo não unitária em computadores quânticos atuais, embora identificar circuitos rasos para mimetizar esta ação permaneça uma possibilidade futura.