Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchy

Planteamiento del Problema

Las Redes Neuronales de Grafos (GNN) se han vuelto centrales para el aprendizaje a partir de datos relacionales en química, biología y optimización, impulsadas por la primitiva de "paso de mensajes". Sin embargo, las contrapartes cuánticas existentes enfrentan limitaciones significativas:

1. Falta de un Verdadero Paso de Mensajes: La mayoría de los modelos de grafos cuánticos propuestos no realizan el paso de mensajes dentro del circuito cuántico. En su lugar, mapean las aristas del grafo a puertas lógicas, pero dependen del procesamiento clásico para agregar la información de los vecinos, perdiendo las ventajas coherentes de las operaciones cuánticas.
2. Techo de Expresividad: Las GNN de paso de mensajes estándar están limitadas por la prueba 1-Weisfeiler–Leman (1-WL), lo que significa que no pueden distinguir ciertos grafos estructuralmente distintos (por ejemplo, moléculas no isomórficas específicas o subestructuras).
3. Entrenabilidad y Escalabilidad: Los Circuitos Cuánticos Variacionales (VQC) a menudo sufren el problema de los "plateaus desérticos" (barren plateaus), donde los gradientes se desvanecen exponencialmente a medida que el tamaño del circuito crece, haciendo imposible el entrenamiento para grafos grandes. Además, pocos modelos cuánticos ofrecen garantías de equivariancia de permutación o escalabilidad a instancias de grafos grandes.

Metodología

Los autores introducen un marco de Red Neuronal de Grafos Cuánticos (QGNN) basado en circuitos que preservan el subespacio que opera enteramente dentro del régimen cuántico. La arquitectura consta de cuatro componentes clave:

1. Cargador de Datos Jerárquico ($V$): El sistema utiliza dos registros:

   • Un Registro de Nodos ($N$ qubits) que codifica los nodos del grafo en un peso de Hamming específico $j$. Los estados base representan $j$-subconjuntos de nodos (por ejemplo, nodos individuales en $j=1$, aristas en $j=2$, triángulos en $j=3$).
   • Un Registro de Incrustación (Embedding) ($D$ qubits) que codifica características en un peso de Hamming $k$.
   • Un codificador de partículas de control-Givens carga las características de los nodos en el subespacio conjunto $H^j_N \otimes H^k_D$.

2. Capa de Adyacencia Equivariante ($A(G)$): Esta capa codifica la conectividad del grafo aplicando rotaciones de Givens entre pares de qubits de nodos correspondientes a las aristas. Los ángulos de rotación se derivan de los pesos de las aristas en un ordenamiento canónico, asegurando que la operación respete la estructura del grafo sin depender de las etiquetas de los nodos.

3. Evolución Entrenable ($W(\theta)$): Actuando únicamente sobre el registro de incrustación, esta capa actualiza las características de los nodos. Utiliza puertas que preservan el subespacio (específicamente una parametrización de Cayley de $SO(D)$ elevada a la representación compuesta) para asegurar que la dinámica permanezca dentro de un subespacio estructurado, evitando el plateau desértico.

4. Mezcla de Registros Conjuntos ($M(\theta_M)$): Una capa final acopla los registros de nodos e incrustación mediante rotaciones de Givens, permitiendo que la información fluya entre los subespacios estructurales y de características.

Mecanismos Clave:

• Paso de Mensajes: El circuito realiza el paso de mensajes de forma coherente. La capa de adyacencia enruta las amplitudes a lo largo de las aristas, y la evolución entrenable actualiza las características. La re-carga del cargador en cada capa introduce no linealidad.
• Equivariancia de Permutación: La arquitectura es exactamente equivariante a la permutación por construcción. Debido a que la evolución entrenable actúa solo en el registro de incrustación compartido y las capas de adyacencia/mezcla siguen un ordenamiento canónico basado en los pesos de las aristas (no en las etiquetas de los nodos), el reetiquetado de los nodos simplemente reetiqueta la salida sin cambiar la función.
• Lectura (Readout): Las características se extraen mediante la matriz de densidad de un solo cuerpo (1-RDM) del registro de incrustación ($\gamma_{pq} = \langle \psi | a^\dagger_p a_q | \psi \rangle$). Esto puede estimarse con un costo polinomial ($O(D^3/\epsilon^2)$) utilizando sombras de matchgate o lecturas deterministas de Hartree–Fock, independientemente del número total de nodos $N$.

Contribuciones Clave

1. Garantías Teóricas: El artículo demuestra que la QGNN realiza un verdadero paso de mensajes, es exactamente equivariante a la permutación y logra expresividad $j$-WL. Al establecer el número de partículas del registro de nodos como $j \ge 3$, el modelo puede distinguir pares de grafos que la prueba 1-WL estándar (y, por tanto, todas las GNN de paso de mensajes estándar) no puede.
2. Escalabilidad mediante la Preservación del Subespacio: Al confinar la dinámica a un subespacio de tamaño fijo (determinado por $D$ y $k$, no por $N$), el modelo evita el desvanecimiento exponencial de gradientes asociado con los VQC genéricos.
3. Estrategia de Pre-entrenamiento: El marco adopta un enfoque de "entrenar en pequeño, desplegar en grande". Dado que los parámetros entrenables actúan solo en el registro de incrustación (que es independiente del tamaño del grafo), un modelo entrenado en grafos pequeños puede transferirse a instancias más grandes inicializando el modelo más grande con los parámetros del modelo más pequeño.

Resultados

El marco fue validado mediante simulaciones clásicas a gran escala (hasta 56 qubits) en tres conjuntos de datos:

1. Grafos Cai–Fürer–Immerman (CFI):

   • Objetivo: Distinguir pares de grafos no isomórficos que la 1-WL no puede separar.
   • Resultado: La QGNN alcanzó una precisión de prueba del 100% exactamente en los números de partículas predichos ($j=3$ para CFI(K3) y $j=4$ para CFI(K4)), mientras que las bases 1-WL permanecieron en el nivel del azar. Esto confirma la capacidad del modelo para superar el techo de la 1-WL.

2. Predicción de Propiedades Moleculares QM9:

   • Objetivo: Predecir la brecha HOMO–LUMO para 130,831 moléculas.
   • Resultado: El aumento del número de partículas $j$ de 1 a 3 redujo el Error Absoluto Medio (MAE) de 0.398 eV a 0.235 eV, a pesar de mantener el recuento de parámetros casi constante. Esto demuestra que una mayor resolución estructural mejora el rendimiento en tareas químicas del mundo real.

3. Problema del Viajero de Comercio Euclídeo (TSP):

   • Objetivo: Encontrar rutas cuasi-óptimas para $N$ ciudades ($N$ hasta 50).
   • Resultado: El modelo produjo rutas con una razón de 1.201 para $N=50$ (donde 1.0 es el óptimo). Crucialmente, el modelo se mantuvo entrenable a estas escalas.
   • Entrenabilidad: La varianza del gradiente se mantuvo polinomial (no exponencial) a medida que aumentaba el número de qubits hasta 56. El aprendizaje por transferencia (inicializar modelos más grandes desde modelos más pequeños ya entrenados) mantuvo las señales de gradiente de 1 a 2 órdenes de magnitud por encima de la inicialización aleatoria.
   • Lectura (Readout): Las lecturas basadas en matchgates superaron significativamente a las lecturas de base computacional, recuperando la información fuera de la diagonal esencial para el rendimiento de la tarea.

Significancia y Reivindicaciones

El artículo afirma abrir un camino para algoritmos cuánticos de la era de la computación cuántica de escala intermedia (near-term) que poseen tanto garantías teóricas como escalabilidad práctica.

• Puente entre la Teoría y la Práctica: Trae los principios del aprendizaje de grafos (paso de mensajes, equivariancia, jerarquía WL) directamente al diseño de circuitos cuánticos, yendo más allá de los modelos cuánticos heurísticos.
• Solución a la Entrenabilidad: Al utilizar la dinámica de preservación de subespacios y el pre-entrenamiento, este trabajo aborda el cuello de botella de los plateaus desérticos, demostrando que los modelos de grafos cuánticos pueden entrenarse en instancias grandes.
• Expresividad: Proporciona el primer modelo de grafos cuánticos con garantía demostrada que puede superar el límite de expresividad 1-WL, ofreciendo una base teórica para distinguir estructuras de grafos complejas que las redes de paso de mensajes clásicas pasan por alto.

Los autores enfatizan que, si bien la validación actual es mediante simulación clásica, la arquitectura está diseñada para ser compatible con el hardware cuántico de corto plazo (requiriendo ~56 qubits para $N=50$), con costos de lectura que escalan polinomialmente con la dimensión de las características en lugar del tamaño del grafo.