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

Resumen Técnico: Algoritmo de Inspiración Cuántica para Hamiltonianos de Espín Clásicos Basado en Operadores de Producto de Matrices

Planteamiento del Problema
El artículo aborda el desafío de resolver problemas de optimización combinatoria (COP) formulados como Hamiltonianos de vidrio de espín clásicos. Estos problemas, que incluyen la búsqueda de los estados fundamentales de modelos de Ising con interacciones competitivas, son generalmente NP-duros debido al tamaño exponencial del espacio de configuración y la presencia de frustración. Los métodos heurísticos clásicos, como el Recocido Simulado (SA) y los Algoritmos Genéticos, suelen ofrecer soluciones casi óptimas pero pueden tener dificultades ante paisajes de energía complejos. Por el contrario, los algoritmos de inspiración cuántica que utilizan redes de tensores, como el Grupo de Renormalización de la Matriz de Densidad (DMRG), son eficientes pero propensos a quedar atrapados en mínimos locales, particularmente cuando el paisaje de energía presenta grandes degeneraciones.

Metodología
Los autores proponen un enfoque de "MPO potenciado" (powered-MPO) que combina el filtrado espectral con representaciones de redes de tensores para resolver estos problemas de optimización en hardware clásico. La metodología procede a través de los siguientes pasos:

1. Transformación del Hamiltoniano: El Hamiltoniano de costo $\hat{H}$ se desplaza y escala para formar un nuevo operador $\hat{G} = a\hat{H} + b\hat{I}$. Los parámetros $a$ y $b$ se eligen de tal manera que $\hat{G}$ sea semidefinido positivo y los estados fundamentales del problema original correspondan a los mayores autovalores de $\hat{G}$.
2. Amplificación Espectral: El operador $\hat{G}$ se eleva a una potencia alta $K$ (es decir, $\hat{G}^K$). Esta operación amplifica exponencialmente los pesos relativos de las configuraciones con los mayores autovalores (los estados fundamentales de $\hat{H}$) mientras suprime las demás.
3. Representación de Red de Tensores:
   • $\hat{G}$ se representa como un Operador de Producto de Matrices (MPO).
   • La potencia $\hat{G}^K$ se construye mediante contracciones repetidas de MPO-MPO. Los autores utilizan dos esquemas de contracción: un esquema "lineal" (multiplicando repetidamente por $\hat{H}$) y un esquema de "duplicación" (elevando el resultado al cuadrado iterativamente, $K=2^m$).
   • Durante la contracción, la dimensión de enlace se trunca utilizando la Descomposición en Valores Singulares (SVD) con un umbral fijo para gestionar el costo computacional, reteniendo una dimensión de enlace máxima $\chi$.
4. Muestreo: El MPO resultante se embebe en un Estado de Producto de Matrices (MPS) actuando sobre un estado de superposición uniforme $|+\rangle^{\otimes N}$. Debido a que $\hat{G}^K$ es diagonal en la base computacional, este embebido permite un "muestreo perfecto" de las cadenas de bits (bitstrings). La probabilidad de muestrear una configuración es proporcional al cuadrado de su elemento diagonal correspondiente en $\hat{G}^K$, sesgando la salida hacia estados de baja energía.

Contribuciones Clave

• Filtrado Espectral Libre de Trotter: A diferencia de los métodos de evolución en el tiempo imaginario cuántico que dependen de descomposiciones de compuertas y Trotterización, este enfoque embebe la función de costo no unitaria directamente en un único MPO clásico, evitando los errores de Trotter.
  el método ofrece una ruta más sistemática de mejora al aumentar la dimensión de enlace $\chi$.
• Construcción Eficiente: Los autores detallan la construcción del MPO para funciones de costo generales y proporcionan límites teóricos sobre la potencia $K$ requerida para alcanzar un objetivo de probabilidad de éxito, mostrando que $K$ escala inversamente con la brecha espectral y logarítmicamente con la dimensión del espacio de Hilbert.
• Programación Híbrida: El estudio identifica fortalezas complementarias entre los esquemas de contracción lineal y de duplicación: la duplicación proporciona un filtrado inicial rápido, mientras que la evolución lineal ofrece un refinamiento continuo y estable en etapas posteriores.

Resultados
Los autores evaluaron el método en dos clases de problemas:

1. Modelos de Vidrio de Espín de Edwards-Anderson: Probados en redes hipercúbicas de $D$ dimensiones ($D=2, 3$).
   • El método powered-MPO superó consistentemente al DMRG, particularmente cuando el DMRG fue inicializado con un estado de superposición uniforme, donde frecuentemente quedaba atrapado en mínimos locales.
   • Mientras que los resultados de DMRG mostraron poca mejora con el aumento de la dimensión de enlace en estos casos, el método powered-MPO mostró una mejora sistemática en la relación de aproximación a medida que $\chi$ aumentaba.
   • El método identificó con éxito los estados fundamentales exactos para tamaños de sistema menores y configuraciones de baja energía para instancias mayores (hasta $N=400$ variables).
2. Modelos de Ising de Orden Superior en Redes Hexagonales Pesadas: Probados en redes relevantes para los dispositivos cuánticos actuales de IBM (problemas HUBO con hasta interacciones cúbicas).
   • El método powered-MPO (con $\chi=64$) superó al Recocido Simulado (tanto en la formulación estándar como en la de orden reducido QUBO) en la búsqueda de configuraciones de menor energía.
   • El método demostró ser robusto contra los paisajes de energía accidentados característicos de estos problemas, siendo que el esquema lineal eventualmente superó el rendimiento del esquema de duplicación en potencias más altas ($m \geq 12$).

Significancia y Reivindicaciones
El artículo sostiene que este enfoque de inspiración cuántica proporciona una línea base clásica robusta para resolver problemas de optimización combinatoria, navegando eficazmente paisajes de energía donde los heurísticos tradicionales y los métodos variacionales como el DMRG tienen dificultades.

• Línea Base para Algoritmos Cuánticos: Los autores postulan que las soluciones de alta calidad generadas por este método basado en redes de tensores pueden servir como un punto de referencia crítico para evaluar la utilidad y ventaja de futuros algoritmos y hardware cuánticos.
• Escalabilidad y Direcciones Futuras: Los autores señalan que, aunque el método requiere más pasos que el DMRG para converger, evita el atrapamiento local. Sugieren que el trabajo futuro podría aprovechar el paralelismo a nivel de MPI y la aceleración por GPU para manejar mayores dimensiones de enlace ($\chi \sim O(10^3)$). Además, proponen que extender el método a redes de tensores de árbol o desarrollar técnicas de contracción más estables para los Operadores de Pares Entrelazados Proyectados (PEPO) podría mejorar aún más su aplicabilidad a topologías de red complejas.
• Limitaciones Modestas: El artículo reconoce que alcanzar soluciones exactas para todos los tipos de problemas todavía requiere superar las barreras de entrelazamiento elevadas, y que el escalamiento de la dimensión de enlace requerida a través de diferentes clases de problemas necesita una clarificación más sistemática. También señala que las limitaciones actuales del hardware (conteo de cúbits y operaciones no locales) impiden la implementación directa de la función de costo no unitaria en las computadoras cuánticas actuales, aunque identificar circuitos poco profundos para imitar esta acción sigue siendo una posibilidad futura.