Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

Planteamiento del Problema

La programación semidefinida (SDP) es un problema de optimización convexa fundamental con aplicaciones en la teoría de control, estadística, aprendizaje automático, finanzas e información cuántica. Sin embargo, resolver instancias de SDP a gran escala sigue siendo computacionalmente desafiante para los algoritmos clásicos. Los principales cuellos de botella son el alto costo de resolver sistemas lineales y realizar descomposiciones de autovalores (específicamente, proyectar sobre el cono semidefinido positivo) en cada iteración. Aunque se han propuesto algoritmos cuánticos como el Quantum Matrix Multiplicative Weights Updates (QMWU) y el Quantum Interior Point Methods (QIPM) para abordar estos problemas, estos suelen enfrentar compromisos en la dependencia de la dimensión, los parámetros de dispersión o los requisitos de precisión.

Metodología

Los autores proponen el Método de Alternating Direction Method of Multipliers Cuántico (QADMM), un algoritmo híbrido cuántico-clásico diseñado para resolver SDPs aprovechando las aceleraciones cuánticas para las subrutinas más costosas, manteniendo al mismo tiempo la robustez de los métodos de primer orden clásicos.

1. Marco de ADMM Inexacto:
El núcleo del enfoque es un marco de ADMM inexacto adaptado para SDPs. A diferencia del ADMM estándar, este marco tolera explícitamente los errores introducidos por las subrutinas cuánticas.

• Actualización de la Variable Dual: La actualización para la variable dual $y$ implica resolver un sistema lineal $(AA^*)y = \dots$. En el entorno cuántico, esto se resuelve utilizando un Solucionador de Sistemas Lineales Cuánticos (QLS).
• Actualizaciones de las Variables Primales: Las actualizaciones para las variables primales $S$ y $X$ implican la proyección sobre el cono semidefinido positivo (PSD). Clásicamente, esto requiere una descomposición de autovalores. El QADMM reemplaza esto con un operador proximal polinomial.
• Tolerancia al Error: El marco introduce términos de error ($\Delta \tilde{y}, \Delta \tilde{S}, \Delta \tilde{X}$, etc.) para dar cuenta de las imprecisiones de las aproximaciones de codificación de bloques (block-encoding), la Transformación de Valores Singulares Cuánticos (QSVT) y la tomografía de estado cuántico. Los autores demuestran que las iteraciones promediadas de este esquema inexacto aún convergen a una solución $\epsilon$-óptima.

2. Operador Proximal Polinomial y QSVT:
Para evitar la costosa descomposición de autovalores en el paso de proyección, los autores diseñan una función polinomial $g(x)$ que aproxima el operador de proyección $\text{Proj}_{S_+}(x) = \max(0, x)$.

• Utilizando la teoría de aproximación, construyen un polinomio creciente monótono $g$ de grado $d = O(1/\epsilon)$ que aproxima la función ReLU dentro de un error $\epsilon$.
• Este polinomio se implementa en una computadora cuántica utilizando la Transformación de Valores Singulares Cuánticos (QSVT) bajo el modelo de codificación de bloques (block-encoding).
• Se construye una función de barrera "virtual" $h(S)$ tal que su operador proximal corresponde a esta transformación polinomial, asegurando la estructura variacional requerida para el análisis de convergencia.

3. Flujo Algorítmico:
El algoritmo procede iterativamente:

1. Actualización de $y$: Calcular el mapa lineal clásicamente, preparar un estado cuántico y resolver el sistema lineal usando QLS.
2. Actualización de $V$: Calcular la variable intermedia $V = C - A^*(y) - \gamma X$ usando la Combinación Lineal de Unidades (LCU).
3. Actualización de $S$: Aplicar la transformación espectral polinomial (aproximando la proyección PSD) a $V$ usando QSVT, seguido de la tomografía para reconstruir la matriz clásica.
4. Actualización de $X$: Similar a la actualización de $S$, aplicando una transformación polinomial para actualizar la variable dual $X$.
5. Post-procesamiento Clásico: Las matrices reconstruidas se proyectan sobre conjuntos acotados (restricciones de norma de Frobenius) para asegurar la factibilidad.

Contribuciones Clave

1. Marco de ADMM Inexacto Robusto: El artículo establece un puente teórico entre la teoría de convergencia de ADMM clásico y la computación cuántica práctica. Demuestran que la iteración promediada converge a una solución $\epsilon$-óptima con una tasa de $O(1/\epsilon)$, incluso cuando las resoluciones de los subproblemas y las actualizaciones duales contienen errores limitados por el ruido cuántico y los límites de aproximación.
2. Mapeo Proximal Polinomial para SDP: Los autores introducen un método novedoso para reemplazar la descomposición de autovalores en ADMM con una transformación de autovalores polinomial. Esto permite el uso de QSVT para manejar las restricciones del cono semidefinido de manera eficiente, evitando el costo de $O(n^3)$ o $O(n^4)$ de las proyecciones espectrales clásicas.
3. Análisis de Complejidad y Comparación: El artículo proporciona un análisis de complejidad riguroso que muestra que QADMM logra una escala favorable con respecto a la dimensión $n$ en comparación con el ADMM clásico y los solucionadores cuánticos existentes (QMWU e QIPM).

Resultados y Complejidad

Los autores derivan la complejidad computacional total requerida para lograr una precisión absoluta $\epsilon_{abs}$ en el valor del objetivo y el residuo de factibilidad.

• Complejidad de Iteración: El algoritmo requiere $K = O\left(\frac{R_X^2 + R_S^2}{\epsilon_{abs}}\right)$ iteraciones, donde $R_X$ y $R_S$ son límites superiores en las normas de Frobenius de las soluciones primales y duales óptimas.
• Complejidad Total:
  • Operaciones Clásicas: $O\left((s_A + n^2)\frac{R_X^2 + R_S^2}{\epsilon_{abs}}\right)$, donde $s_A$ es el número de entradas no nulas en las matrices de restricción.
  • Complejidad de Puertas Cuánticas: $\tilde{O}\left( \left[ m\kappa_A^2(1+R_y)^2 + n^2(\kappa_A^2(1+R_y) + R_X) \right] \frac{(R_X + R_S)^3}{\epsilon_{abs}^3} \right)$.
  • Aquí, $\kappa_A$ es el número de condición de $AA^*$ y $R_y$ es el límite en la norma de la variable dual.

Comparación:

• Vs. ADMM Clásico: QADMM ofrece una mejor dependencia de la dimensión $n$ (evitando los factores de $O(n^6)$ o $O(n^4)$ asociados con las descomposiciones de autovalores y multiplicaciones de matrices en cada iteración).
• Vs. QIPM: QADMM evita la alta dependencia del número de condición del sistema de Newton ($\kappa_{newt}$) y ofrece un compromiso diferente en la dependencia de la precisión.
• Vs. QMWU: Aunque QADMM tiene una dependencia de dimensión similar a QMWU, logra una dependencia de orden inferior respecto al parámetro de precisión $\epsilon_{abs}$ (cúbica frente a potencias superiores en algunos regímenes) y es particularmente ventajoso cuando la norma de Frobenius de la solución $\|X^*\|_F$ es mucho menor que su traza $\text{Tr}(X^*)$ (por ejemplo, en incrustaciones de SDP diagonales).

Significado y Reivindicaciones

El artículo afirma que QADMM proporciona una escala favorable con respecto a la dimensión para resolver SDPs a gran escala, lo que lo convierte en un candidato prometedor para problemas donde los solucionadores clásicos luchan con el costo de las descomposiciones de autovalores.

Los autores enfatizan que su enfoque:

• Integra Aceleraciones Cuánticas: Aprovecha con éxito QSVT y QLS para acelerar las partes más intensas computacionalmente del algoritmo ADMM.
• Mantiene Garantías de Convergencia: Al desarrollar un marco inexacto, aseguran que los errores cuánticos no impidan la convergencia hacia una solución óptima.
• Depende de Supuestos Específicos: El algoritmo asume la disponibilidad de QRAM de tamaño polinomial para el acceso a datos y la codificación de bloques de las matrices de entrada. Los autores reconocen esto como un supuesto fuerte y señalan que el trabajo futuro se centrará en relajar este requisito.

El artículo concluye que, si bien el algoritmo está limitado por el supuesto de QRAM, representa un paso significativo hacia la aplicación de la computación cuántica a la optimización convexa a gran escala, ofreciendo específicamente una alternativa viable tanto para los métodos de primer orden clásicos como para otros solucionadores de SDP cuánticos en regímenes específicos de dimensión y precisión.