Resumen Técnico: Enfoques Variacionales Cuánticos para el Problema del Conjunto Independiente Máximo a Escala de Utilidad

Planteamiento del Problema

El problema del Conjunto Independiente Máximo (MIS, por sus siglas en inglés) busca el subconjunto más grande de vértices en un grafo no dirigido tales que ningún par de vértices sean adyacentes. Es un problema canónico NP-duro con aplicaciones en asignación de frecuencias, análisis de interacción de proteínas y diseño de VLSI. Mientras que los resolvedores exactos clásicos (branch-and-bound, programación entera) tienen dificultades con instancias difíciles que superan unos pocos cientos de vértices, la computación cuántica ofrece heurísticas potenciales. Sin embargo, los algoritmos variacionales basados en puertas enfrentan desafíos significativos en la era NISQ (Noisy Intermediate-Scale Quantum), incluyendo conteos limitados de qubits, tiempos de coherencia cortos y el fenómeno de la "meseta estéril" (barren plateau) donde los gradientes se desvanecen exponencialmente.

Un desafío estructural específico surge para grafos grandes y densos donde el MIS constituye una fracción minúscula del total de los vértices (por ejemplo, 15 de 180). En tales casos, la solución óptima ocupa una región exponencialmente pequeña del espacio de Hilbert. Los enfoques estándar que inicializan con una superposición uniforme asignan una amplitud insignificante al MIS, lo que causa que los circuitos variacionales converjan a cuencas de energía subóptimas de las cuales es difícil escapar sin cambios coordinados de múltiples qubits.

Metodología

Los autores proponen un marco estratificado que combina preprocesamiento de circuitos, optimización variacional y postprocesamiento clásico para abordar estos desafíos a través de tres instancias de referencia: 64, 99 y 180 nodos.

1. Preprocesamiento y Construcción de Circuitos

• Reordenamiento de Vértices: Para minimizar la sobrecarga de SWAP y mejorar la eficiencia del entrelazamiento, los autores comparan tres estrategias de reordenamiento: BFS ponderado por acoplamiento, Reverse Cuthill-McKee (RCM) y Reordenamiento Espectral (usando el vector de Fiedler). Se adopta el reordenamiento espectral ya que supera consistentemente a los demás en instancias densas al agrupar vértices estructuralmente próximos, minimizando así la distancia de índice entre qubits fuertemente acoplados.
• Esparcimiento Basado en Distancia: Aplicado específicamente a los circuitos QAOA, esta técnica elimina las interacciones de largo alcance de la construcción del circuito (reteniendo solo los bordes donde $|i-j| \le k$) mientras se evalúa la energía usando el Hamiltoniano completo. Esto reduce significamente la profundidad del circuito, haciendo que las simulaciones sean tratables en un simulador de Estado de Producto de Matriz (MPS).
• Algoritmos: El estudio compara el Solucionador de Valores Propios Cuánticos Variacional (VQE) utilizando un ansatz EfficientSU2 y el Algoritmo de Optimización Aproximada Cuántica (QAOA). Los optimizadores incluyen COBYLA y la Aproximación Estocástica de Perturbación Simultánea (SPSA). Se utiliza el objetivo de Valor en Riesgo Condicional (CVaR) para enfocarse en la cola de menor energía de la distribución de medición.

2. Pipeline de Postprocesamiento Clásico

Un pipeline heurístico de dos etapas de cadenas de bits convierte las mediciones cuánticas brutas en candidatos válidos de MIS:

• Supresión Guiada por Historia: Una Media Móvil Exponencial (EMA) rastrea la frecuencia de los qubits en el estado $|0\rangle$ a través de las cadenas de bits con mejor desempeño. Esto genera máscaras de supresión para eliminar vértices sobre-seleccionados (que violan la independencia) y añadir vértices sub-seleccionados.
• Corrección Codiciosa y Extensión de Maximalidad: Un algoritmo codicioso de dos pasadas primero repara los conjuntos no factibles eliminando violaciones de alto peso, y luego extiende el conjunto a la maximalidad añadiendo vértices compatibles en orden ascendente de grado.

3. Inicialización de Superposición Asistida por Ancilla (Instancia de 180 Nodos)

Para la instancia de 180 nodos, el VQE estándar se estanca en un tamaño de 14 (el MIS conocido es 15). Para superar esto, los autores introducen una técnica de inicialización novedosa:

• Selección de Semillas: El postprocesamiento clásico identifica múltiples conjuntos independientes diversos y casi óptimos de tamaño 14.
• Superposición de Ancilla: En lugar de inicializar desde una única semilla o una superposición uniforme, el circuito prepara una superposición cuántica uniforme de estas $m$ soluciones distintas de tamaño 14 usando qubits ancilla como un registro de índice.
• Ansatz de Preservación de Excitación: El estado evoluciona bajo un ansatz compuesto por puertas de simulación fermiónica (fSim) que conservan el peso de Hamming total (número de excitaciones). Esto restringe la búsqueda al subespacio de configuraciones de tamaño 14, eliminando la necesidad de términos de penalización y agudizando el paisaje de energía para una optimización de grano fino.
• Búsqueda en Paralelo Cuántico: Los parámetros variacionales se optimizan colectivamente a través de todas las ramas de las semillas simultáneamente. La distribución resultante es procesada por la heurística clásica, que puede extender los conjuntos de tamaño 14 hacia el MIS de tamaño 15.

Resultados Clave

Instancias de Referencia (64, 99 y 180 Nodos)

• Instancia de 64 Nodos: El VQE con SPSA y CVaR recupera exitosamente todos los 9 MIS certificados distintos (tamaño 10) a través de ejecuciones repetidas. QAOA recupera menos conjuntos (0–5 por ejecución) y falla en alcanzar el tamaño 10 con la Estrategia 2 (llevando todos los conjuntos recuperados a la maximalidad), resaltando la importancia de la diversidad de soluciones.
• Instancia de 99 Nodos: VQE recupera hasta 10 MIS distintos (tamaño 7) por ejecución, muestreando una fracción significativa de las 56 soluciones certificadas. No se prosigue con QAOA debido a los límites de esparcimiento en el simulador MPS.
• Instancia de 180 Nodos: El VQE estándar (Fase 1) converge a un tamaño 14 pero no puede alcanzar el 15. La Fase 3 asistida por ancilla (VQE de preservación de excitación) descubre exitosamente el MIS de tamaño 15. Los estudios de ablación confirman que las heurísticas clásicas aplicadas a semillas únicas, o los circuitos de preservación de excitación inicializados desde semillas únicas, fallan en encontrar el MIS de tamaño 15. Solo la superposición cuántica de múltiples semillas rompe la barrera del óptimo local.

Validación de Hardware (IBM Quantum ibm_marrakesh)

• VQE: Usando parámetros transferidos directamente de la simulación sin ruido (sin re-optimización de hardware), el VQE recupera aproximadamente el 50% de la diversidad del MIS sin ruido con el 40% del presupuesto de disparos (shots). Para la instancia de 64 nodos, se encontraron 3 MIS distintos (tamaño 10); para la de 99 nodos, se encontraron 5 MIS distintos (tamaño 7).
• QAOA: Bajo el mismo protocolo de transferencia de parámetros, QAOA recuperó cero conjuntos independientes válidos en hardware. Los autores atribuyen esto al efecto compuesto de un ancho de banda de circuito limitado (que requiere cadenas de SWAP profundas), una optimización clásica superficial y el ruido del hardware.

Significancia y Reivindicaciones

El artículo reivindica las siguientes contribuciones y significancia:

1. Simulación a Escala de Utilidad: Hasta donde los autores saben, la simulación MPS de 180 qubits representa la mayor escala en la que algoritmos variacionales basados en puertas han resuelto el problema del MIS de manera óptima.
2. Avance Metodológico: La contribución principal es la técnica de superposición de ancilla. Proporciona un marco principista para romper los óptimos locales que atrapan tanto a las heurísticas clásicas como a los enfoques variacionales estándar. Al inicializar una superposición uniforme sobre múltiples semillas clásicas casi óptimas y evolucionarlas bajo un ansatz de preservación de excitación, el método realiza una "búsqueda paralela híbrida cuántica-clásica". Esto permite el descubrimiento de soluciones (tamaño 15) que son inaccesibles para los métodos de semilla única.
3. Robustez al Ruido: La validación de hardware demuestra que el pipeline de heurística de cadenas de bits es robusto a condiciones de ruido realistas, recuperando una diversidad de soluciones significativa sin re-optimización consciente del hardware.
4. Reivindicaciones Modestas sobre Ventaja Cuántica: Los autores declaran explícitamente que no reclaman ventaja computacional cuántica para estas instancias específicas. Los circuitos estudiados son simulables eficientemente de forma clásica vía MPS (dimensión de enlace $\chi_{max} = 2$) debido a su estructura de entrelazamiento baja. La significancia radica en demostrar que la metodología funciona y proporciona una base para futuras implementaciones de hardware donde ansatze más profundos y poblaciones de semillas más grandes puedan generar una verdadera ventaja cuántica.

El trabajo establece que el descubrimiento del MIS en el caso de 190 nodos es una consecuencia de la búsqueda en paralelo cuántico sobre múltiples inicializaciones casi óptimas, más que del postprocesamiento clásico por sí solo. Este marco se presenta como un enfoque escalable para problemas de optimización combinatoria que admiten una formulación de Ising.