Resumen Técnico: Muestreo de Sustitutos Informado por Cuántica (QISS) para Optimización Combinatoria

1. Planteamiento del Problema

Los problemas de optimización combinatoria, como el Corte Máximo (MaxCut) y el Conjunto Independiente Máximo (MIS), son computacionalmente desafiantes a escala. Si bien el Algoritmo de Optimización Aproximada Cuántica (QAOA) ofrece un enfoque híbrido cuántico-clásico prometedor, su rendimiento en hardware de la era NISQ está limitado por el ruido y las limitaciones de coherencia. Estas restricciones suelen restringir las implementaciones de QAOA a circuitos poco profundos (profundidad baja $p$).

Una limitación fundamental de un QAOA de profundidad reducida es la localidad: para grafos dispersos, el "cono de luz" del circuito está limitado por la profundidad $p$, no por el tamaño del problema $N$. En consecuencia, un QAOA de $p$ fijo a menudo no logra explotar las estructuras globales del problema y hereda limitaciones similares a las de los algoritmos clásicos locales. Además, la distribución de salida completa de un estado cuántico es generalmente intratable de muestrear clásicamente, y el dispositivo cuántico mismo no puede producir directamente soluciones de alta calidad cuando está restringido a profundidades bajas.

El artículo aborda la necesidad de un método que aproveche las fortalezas específicas de los dispositivos cuánticos de corto plazo —la estimación eficiente de estadísticas locales de bajo orden— mientras delega la generación de soluciones candidatas a un post-procesamiento clásico escalable.

2. Metodología: Muestreo de Sustitutos Informado por Cuántica (QISS)

Los autores proponen el Muestreo de Sustitutos Informado por Cuántica (QISS), un marco de post-procesamiento que genera soluciones candidatas a partir de correlaciones cuánticas de bajo peso sin requerir una dependencia explícita de la estructura del problema combinatorio durante la fase de muestreo.

Flujo de Trabajo Central

1. Estimación Cuántica: Se ejecuta un circuito QAOA poco profundo (profundidad $p$) en un dispositivo cuántico (o simulado) para estimar un conjunto seleccionado de valores de expectativa de bajo peso (correladores) $\mu_{S_\alpha}$:
   $$\mu_{S_\alpha} = \langle \psi_p(\gamma, \beta) | \prod_{i \in S_\alpha} Z_i | \psi_p(\gamma, \beta) \rangle$$
   El artículo se centra en pesos $|S_\alpha| \in \{1, 2\}$. Estos valores son accesibles mediante mediciones repetidas y son susceptibles de mitigación de errores.

2. Construcción de la Distribución Sustituta: Se construye una distribución de factores clásica $P(z)$ sobre el espacio de soluciones $\{-1, +1\}^N$ utilizando estos correladores medidos como parámetros:
   $$P(z) \propto \prod_{S_\alpha \in \mathcal{S}} \left( 1 + \mu_{S_\alpha} \chi_{S_\alpha}(z) \right)$$
   donde $\chi_{S_\alpha}(z) = \prod_{i \in S_\alpha} z_i$ es la función de paridad. Esta distribución es equivalente a una distribución de Gibbs de un Hamiltoniano de Ising efectivo $H'$ con acoplamientos $J_{S_\alpha} = -\text{arctanh}(\mu_{S_\alpha})$.

3. Muestreo Clásico: Las soluciones candidatas se extraen de $P(z)$ utilizando Monte Carlo por Cadenas de Markov (MCMC). El muestreo utiliza actualizaciones condicionales de un solo sitio, las cuales son eficientes porque la probabilidad condicional para un giro de espín depende solo de los factores locales que involucran a dicho espín. La constante de normalización (función de partición) nunca es requerida.

4. Selección de Correladores: El artículo distingue entre dos conjuntos de correladores:

   • Conjunto de Aristas ($\mathcal{S} = E \cup V$): Solo las aristas directas del grafo del problema. En grafos localmente similares a árboles, esto reproduce los momentos de QAOA sin mejora alguna.
   • Conjunto Aumentado ($\mathcal{S}' = E' \cup V$): Incluye todos los pares $(i, j)$ dentro de la distancia del cono de luz $d_G(i, j) \le 2p$. Esto crea un grafo de factores denso y no similar a un árbol, lo que permite que el sustituto capture correlaciones de orden superior de forma implícita y genere soluciones superiores a la salida bruta de QAOA.

Características Clave

• Libre de Entrenamiento: El método utiliza ángulos de QAOA óptimos para árboles fijos (de la Ref. [61]), lo que no requiere la optimización variacional del sustituto.
• Modularidad: El paso de muestreo es agnóstico a la función de costo; solo requiere los correladores.
• Resiliencia al Ruido: El mapeo de correladores a acoplamientos ($\text{arctanh}$) es suave, lo que hace que el sustituto sea robusto al ruido en las estadísticas medidas.

3. Contribuciones Clave y Resultados

A. MaxCut en Grafos 3-Regulares

• Rendimiento vs. Vanilla QAOA: Cuando se utiliza el conjunto de correladores aumentado (todos los pares dentro de la distancia $2p$), QISS supera significamente al QAOA convencional (vanilla). Específicamente, QISS utilizando correladores de un circuito QAOA de profundidad $p=3$ o $p=4$ logra fracciones de corte promedio que superan al QAOA de profundidad $p=17$ (la mayor profundidad para la cual se conocen los ángulos óptimos para árboles).
• Integración de Inicio en Caliente (Warm-Start): El método se combinó con el QAOA de Inicio en Caliente Regularizado (RWS-QAOA). Incluso a profundidades poco profundas ($p=1, 2$), el post-procesamiento QISS mejoró la calidad de la solución de RWS-QAOA, llevando la razón de aproximación cerca del límite óptimo.
• Validación en Hardware: Los experimentos se realizaron en el QPU IQM Emerald de 54 qubits. Los resultados demostraron que QISS es altamente resiliente al ruido. Las razones de aproximación obtenidas a partir de correladores ruidosos y brutos del QPU fueron casi indistinguibles de las obtenidas mediante simulaciones sin ruido. El ruido del dispositivo fue efectivamente "lavado" por el post-procesamiento, haciendo que la mitigación de errores fuera irrelevante para la calidad de la solución final en este régimen.
• Escalabilidad: El método mantuvo su rendimiento hasta $N=140$ (limitado por el número de qubits disponibles tras el congelamiento de variables), con razones de aproximación que permanecieron estables y muy por encima de las garantías estándar de SDP.

B. Conjunto Independiente Máximo (MIS)

• Manejo de Restricciones: A diferencia de MaxCut, el MIS es un problema con restricciones. Las muestras de QISS pueden contener conflictos (nodos adyacentes seleccionados simultáneamente). Los autores introdujeron una rutina de poda de post-procesamiento simple para resolver conflictos y añadir nodos válidos de forma codiciosa (greedy).
• Rendimiento: Para MIS, el uso de solo correladores de aristas resultó en un rendimiento peor que el de QAOA convencional debido a la falta de simetría $Z_2$ y los factores superpuestos. Sin embargo, el uso del conjunto aumentado de correladores combinado con la rutina de poda permitió que QISS superara al QAOA independiente y compitiera con heurísticas clásicas de vanguardia (por ejemplo, búsqueda de prioridad lineal y algoritmos codiciosos potenciados por computación cuántica).

C. Comparación con Solucionadores Clásicos

QISS se comparó con el Recocido Simulado (SA) y la relajación de rango dos de Burer–Monteiro (BM) del SDP de Goemans–Williamson.

• QISS combinado con RWS-QAOA produjo resultados competitivos con el solucionador BM.
• A diferencia de los muestreadores clásicos cuyo rendimiento se degrada a medida que el tamaño del sistema aumenta bajo un presupuesto de tiempo fijo, QISS aprovecha la localidad de las correlaciones de QAOA, las cuales permanecen estables con $N$.

4. Significado y Reivindicaciones

El artículo sostiene que QISS establece un nuevo régimen para la optimización de corto plazo donde los circuitos cuánticos poco profundos no sirven como muestreadores directos, sino como generadores de estadísticas informativas para un muestreo clásico escalable.

• División del Trabajo: El dispositivo cuántico se utiliza por su capacidad para estimar eficientemente observables locales de bajo orden (que son robustos al ruido e independientes del tamaño del sistema en costo de muestra), mientras que la computadora clásica se encarga de la compleja tarea de sintetizar estas estadísticas en soluciones globales.
• Resiliencia al Ruido: Un hallazgo crítico es que la distribución sustituta es tan robusta que puede recuperar soluciones casi óptimas a partir de datos de hardware ruidosos y brutos sin mitigar. Esto sugiere que, para ciertas tareas de optimización, la sobrecarga de la mitigación de errores compleja puede ser innecesaria si se emplea una capa de post-procesamiento robusta como QISS.
• Escalabilidad: El enfoque evita la escala exponencial de la contracción clásica para circuitos profundos al depender de circuitos poco profundos y MCMC clásico, ofreciendo una vía para resolver problemas más grandes de lo que el muestreo cuántico directo permitiría en el hardware actual.

Los autores concluyen que, si bien QISS depende de la estructura específica de las correlaciones medidas, proporciona una vía práctica, libre de entrenamiento y eficiente en hardware para mejorar el rendimiento de la optimización en dispositivos cuánticos de corto plazo.