Iterative quantum algorithms for the minimum vertex cover problem based on continuous-time quantum walks

Resumen Técnico: Algoritmos Cuánticos Iterativos para el Cobertura Mínima de Vértices Basados en Caminatas Cuánticas de Tiempo Continuo

Planteamiento del Problema
El artículo aborda los problemas de Cobertura Mínima de Vértices (MVC) y Conjunto Independiente Máximo (MIS), que son tareas de optimización combinatoria canónicas NP-completas. Dado un grafo $G=(V, E)$, el objetivo es encontrar un subconjunto de vértices de tamaño mínimo que cubra todas las aristas. Los autores enmarcan esto como un problema de optimización con restricciones donde el subespacio factible consiste en cadenas de bits que satisfacen las restricciones de arista ($x_i + x_j \geq 1$ para todo $(i,j) \in E$). Las heurísticas clásicas codiciosas (p. ej., Largest-Degree-First) están limitadas por su dependencia de la estructura local del grafo, lo que a menudo les impide captar correlaciones globales. Por el contrario, los enfoques cuánticos estándar como QAOA o VQE suelen mapear el problema a Hamiltonianos no restringidos mediante términos de penalización, lo que introduce problemas de ajuste de parámetros y crea paisajes de energía poblados por estados de baja energía que son infactibles.

Metodología
Los autores proponen un marco híbrido cuántico-clásico codicioso que preserva las restricciones que evita los términos de penalización y el entrenamiento variacional. La metodología central consta de tres etapas:

1. Operadores de Preservación de Restricciones:
   El subespacio factible se define mediante operadores de Pauli-X proyectados, $\hat{X}_i = \Pi_{N(i)} X_i$, donde $\Pi_{N(i)}$ proyecta sobre el subespacio donde todos los vecinos del vértice $i$ ya están en la cobertura. Esto asegura que voltear un bit $i$ (eliminarlo de la cobertura) solo sea permitido si no viola ninguna restricción de arista. Estos operadores generan un Hamiltoniano de caminata cuántica de tiempo continuo (CTQW), $H_{MVC} = \sum_i \hat{X}_i$.

2. Grafo de Estados Factibles Inducido y CTQW:
   La dinámica de $H_{MVC}$ se interpreta como una CTQW en un grafo de estados factibles inducido $G_{VC}(G)$. Los vértices de este grafo son coberturas válidas y las aristas conectan coberturas que difieren en un único cambio de bit que preserva la factibilidad. El grafo está enraizado en el estado de "todos en la cobertura" ($\Omega = |1\rangle^{\otimes |V|}$) y es conexo; por lo tanto, la caminata puede alcanzar cualquier cobertura factible desde $\Omega$. La caminata propaga la amplitud desde la raíz hacia capas de peso de Hamming decreciente (coberturas más pequeñas).

3. Reducción Codiciosa Iterativa:
   En lugar de intentar medir directamente una cobertura mínima (lo cual el artículo muestra que está exponencialmente suprimido en probabilidad para sistemas grandes), el algoritmo utiliza el estado de la CTQW para generar puntuaciones de vértices que guían una reducción clásica recursiva:

   • Codicioso Probabilístico Cuántico (QPG): Puntúa los vértices basándose en su probabilidad de ocupación marginal $P_v(t) = \langle \psi(t) | \Pi_v | \psi(t) \rangle$ en el estado de la CTQW.
   • Codicioso de Energía Cuántica (QEG): Puntúa los vértices basándose en el tamaño de la cobertura esperada obtenida al condicionar la caminata sobre la fijación de un vértice específico $v$ en la cobertura. Esto implica ejecutar una caminata condicionada separada para cada vértice candidato.
   • Reglas de Reducción: En cada paso, el algoritmo selecciona un vértice basado en estas puntuaciones (ya sea la puntuación más alta para incluirlo en la cobertura, o la más baja para excluirlo e incluir a sus vecinos) y reduce el grafo. El proceso se repite hasta que el grafo esté vacío o sea clasificablemente soluble.

Contribuciones Clave

• Marco Libre de Penalizaciones: El trabajo introduce un método que impone la factibilidad por construcción utilizando operadores de Pauli proyectados, eliminando la necesidad de términos de penalización o de optimización de parámetros variacionales.
• Perspectiva de Grafo Inducido: Establece que la dinámica restringida corresponde a una CTQW en un grafo conectado y estratificado de coberturas factibles, proporcionando una base teórica de por qué la caminata explora el espacio de soluciones de manera efectiva.
• Dos Heurísticas Informadas por Cuántica: El artículo define y evalúa algoritmos QPG y QEG. Se destaca que QEG es superior al agregar información estructural global al evaluar el impacto del costo de fijar cada vértice, mientras que QPG depende de probabilidades marginales locales.
• Robustez de Baja Profundidad: El marco está diseñado para dispositivos de la era de la escala intermedia con ruido (near-term). Para grafos de grado acotado, cada capa de Trotter tiene una profundidad de circuito independiente del tamaño del sistema. Los autores demuestran que QEG mantiene un rendimiento cercano al límite continuo exacto incluso bajo una Trotterización de baja profundidad ($p=4$).

Resultados
Se realizaron evaluaciones numéricas en grafos aleatorios de tipo Erdős–Rényas de 3 y 4 regulados ($n \in \{8, \dots, 20\}$).

• Rendimiento: Los algoritmos informados por cuántica (particularmente QEG-LDF) logran ratios de aproximación medios y resuelven una fracción de instancias óptimas más grandes en comparación con las bases codiciosas clásicas (Greedy LDF, Greedy SDF) y la heurística de búsqueda local FastVC.
• Trotterización: Mientras que el rendimiento de QPG se degrada significamente en profundidades de Trotter bajas ($p=4$) debido a su sensibilidad a los contrastes de probabilidad finos, QEG permanece robusto y cercano al límite de tiempo continuo exacto. Esto sugiere que QEG es mejor adecuado para hardware con profundidad de circuito limitada.
• Tiempo de la Caminata: Los algoritmos requieren un tiempo de caminata $t$ específico (calibrado en conjuntos independientes) para maximizar la separación de las puntuaciones de los vértices. El tiempo óptimo ocurre típicamente después de que la onda frontal ha atravesado las capas y los patrones de interferencia han establecido un ranking, en lugar de en el momento en que la onda frontal alcanza por primera vez la capa de cobertura mínima.

Significancia y Reivindicaciones
El artículo afirma que la utilidad principal del componente cuántico no es producir una solución completa directamente, sino generar puntuaciones por vértice que codifican información estructural no local del espacio de estados factibles. Estas puntuaciones guían una reducción clásica recursiva, combinando efectivamente la exploración cuántica restringida con la simplificación clásica.

Los autores enmarcan la significancia de manera modesta de la siguiente manera:

• El método proporciona una alternativa práctica y libre de penalizaciones a los algoritmos variacionales para la optimización combinatoria.
• Demuestra que las caminatas cuánticas que preservan las restricciones pueden generar rankings útiles para la reducción codiciosa, superando a las heurísticas codiciosas puramente locales.
• El trabajo identifica un compromiso (trade-off): las puntuaciones basadas en energía (QEG) ofrecen mayor robustez a los errores de Trotter a costa de una mayor sobrecarga de medición ($O(|V|)$ evaluaciones por paso), mientras que las puntuaciones basadas en probabilidad (QPG) son más económicas pero más sensibles al ruido.
• El artículo concluye que la cuestión abierta clave no es si tales caminatas generan rankings útiles, sino cómo escala la separación estadística entre las puntuaciones competidoras con el tamaño del problema, lo que determinará el régimen de ventaja práctica.

Los autores declaran explícitamente que el marco no pretende resolver el MVC en tiempo polinómico ni proporcionar una aceleración cuántica para la optimización exacta en el sentido de la computación tolerante a fallos; más bien, ofrece una mejora heurística para algoritmos híbridos de la era actual.