A 0.651-approximation to quantum Max Cut via Rydberg atoms

Resumen Técnico: Una aproximación de 0.651 al Quantum Max Cut mediante Átomos de Rydberg

Definición del Problema
El artículo aborda el problema de Quantum Max Cut (QMC), el cual es equivalente a encontrar la energía del estado fundamental del Hamiltoniano de Heisenberg antiferromagnético. Este problema es QMA-completo, lo que significa que no puede resolverse eficientemente incluso con una computadora cuántica universal. El objetivo es encontrar un algoritmo de aproximación que garantice una solución dentro de un ratio específico ($\alpha$) de la energía del estado fundamental óptimo. El estado de la técnica actual, basado únicamente en relajaciones de programación semidefinida (SDP), logra un ratio de aproximación de $\alpha = 0.614$.

Metodología: Un Enfoque Híbrido Cuántico-Clásico
Los autores proponen un algoritmo híbrido que integra la dinámica cuántica natural de los sistemas de átomos de Rydberg con técnicas de optimización clásica (SDP y redondeo aleatorio). La metodología se desarrolla en cuatro etapas distintas:

1. Codificación y Recocido (Annealing):
   Una instancia de QMC definida sobre un grafo $G=(V, E, \omega)$ se codifica en un arreglo de átomos de Rydberg. La parte estática del Hamiltoniano de Rydberg, $H_r$, se construye para contener los términos de interacción $XX + YY$ correspondientes a las aristas del grafo:
   $$H_r = \sum_{(ij) \in E} \omega_{ij} (X_i X_j + Y_i Y_j)$$
   El sistema se somete a un procedimiento de recocido para preparar un estado fundamental aproximado, denotado como $\varrho_r$.

2. Medición y Formulación de Restricciones:
   Se miden los valores de expectativa $\langle X_i X_j + Y_i Y_j \rangle$ para todas las aristas en el estado recocido $\varrho_r$. Estos valores sirven como restricciones empíricas para un paso de optimización clásica posterior.

3. Programación Semidefinida y Redondeo:
   Se optimiza una matriz de pseudo-momentos $\Delta$ mediante SDP, sujeta a las restricciones derivadas de las mediciones de Rydberg y las relaciones algebraicas de los operadores de Pauli. Esta matriz es luego redondeada en un estado producto $\varrho_p$ utilizando una técnica de proyección aleatoria (descomposición de Cholesky seguida de una proyección aleatoria de $\mathbb{R}^{4n}$ a $\mathbb{R}^3$).

4. Selección del Estado Final:
   El algoritmo devuelve el estado con la energía más baja: ya sea el estado fundamental de Rydberg $\varrho_r$ o el estado producto redondeado clásicamente $\varrho_p$.

Contribuciones Teóricas Clave
El artículo establece un ratio de aproximación condicional de 0.651, superando el mejor ratio conocido anteriormente de 0.614. La derivación se basa en dos ideas teóricas principales:

• Límite Inferior vía el Estado Fundamental de Rydberg: Los autores demuestran que la energía del estado fundamental del Hamiltoniano QMC completo ($H_{qmc}$) puede acotarse inferiormente utilizando la energía del Hamiltoniano de Rydberg ($H_r$). Al explotar la invariancia $SU(2)$ del modelo de Heisenberg, muestran que los valores de expectativa de $XX$, $YY$y$ZZ$ son iguales en el estado fundamental óptimo. Esto permite la reconstrucción de la energía completa de QMC a partir de las mediciones parciales de $XX+YY$ obtenidas del sistema de Rydberg.
• Límite Superior vía Redondeo: El artículo analiza la energía del estado producto $\varrho_p$ generado por el redondeo de la SDP. Deriva una expresión analítica para la energía esperada de este estado basada en las correlaciones medidas.
• Optimización del Ratio: Al combinar el límite inferior (derivado del estado de Rydberg) y los límites superiores (tanto del estado de Rydberg como del estado producto), los autores formulan un problema de minimización sobre el parámetro de correlación $t_{ij}$. La resolución de este problema arroja el ratio de 0.651.

Resultados y Robustez

• Ratio de Aproximación: El algoritmo logra un ratio de aproximación condicional de $\kappa = 0.651$.
• Robustez al Ruido: Un hallazgo significativo es la resiliencia del algoritmo ante la preparación imperfecta del estado fundamental. Los autores demuestran que la ventaja de 0.651 persiste incluso si el procedimiento de recocido de Rydberg produce un estado con una energía de solo el 89% de la verdadera energía del estado fundamental de Rydberg ($\eta = 0.89$). Por debajo de este umbral, la ventaja sobre los métodos puramente clásicos de SDP disminuye.
• Complejidad Computacional: El enfoque híbrido reduce la dimensionalidad del problema de optimización clásica. Mientras que los esquemas clásicos dirigidos a estados entrelazados requieren $O(n^4)$ variables reales, este método híbrido opera con $O(n^2)$ variables, aprovechando el sistema cuántico para gestionar la complejidad de la estructura de entrelazamiento.

Significado
El artículo afirma abrir una nueva ruta para los algoritmos híbridos cuántico-clásicos. Demuestra que combinar hardware cuántico (específicamente arreglos de átomos de Rydberg) con optimización clásica puede generar garantías de aproximación más fuertes que los métodos clásicos por sí solos, incluso cuando el hardware cuántico no resuelve perfectamente el problema del Hamiltoniano subyacente. El trabajo sugiere que las plataformas cuánticas pueden servir como "proxies" efectivos para proporcionar límites inferiores de alta calidad y puntos de partida para procedimientos de redondeo clásicos, eludiendo efectivamente algunas de las limitaciones de escalamiento computacional de los enfoques puramente clásicos.