Quantum Spectral Clustering Framework via Compact Circuit Structures

Resumen Técnico: Marco de Agrupamiento Espectral Cuántico mediante Estructuras de Circuitos Compactos

Planteamiento del Problema
Los métodos de aprendizaje automático espectral, basados en la teoría espectral de grafos, son herramientas poderosas para el agrupamiento (clustering) y el aprendizaje de variedades (manifold learning). Sin embargo, su aplicación práctica se ve obstaculizada por altos costos computacionales. La construcción de una matriz de núcleo (adyacencia) para $M$ muestras requiere típicamente un tiempo de $O(M^2)$, y resolver el problema de autovalores asociado exactamente cuesta $O(M^3)$. Aunque existen métodos de aproximación clásicos (por ejemplo, Nyström, Características de Fourier Aleatorias, Lanczos), estos a menudo aún requieren el acceso explícito a matrices de núcleo parciales o completas. En el contexto del aprendizaje automático cuántico, donde las entradas del núcleo se estiman mediante subrutinas cuánticas (por ejemplo, pruebas SWAP) en lugar de leerse directamente, el acceso entrada por entrada resulta prohibitivamente costoso, escalando como $O(\epsilon^{-2}M^4)$ para la estimación de la matriz completa. Los autores identifican una brecha en la realización eficiente del agrupamiento espectral utilizando núcleos cuánticos sin construir la matriz de núcleo o estimar sus entradas individuales.

Metodología
El artículo propone un marco variacional para el agrupamiento espectral que evita por completo la construcción de la matriz de núcleo. En su lugar, estima las cantidades necesarias directamente a través de formas cuadráticas agregadas mediante circuitos cuánticos compactos.

1. Función Objetivo: Los autores formulan una función objetivo de cociente de Rayleigh normalizado derivada del Laplaciano de grafo simétrico ($L_{sym}$). El objetivo es maximizar:
   $$J(\alpha) = \frac{\alpha^\dagger A \alpha - \xi \alpha^\dagger D \mathbf{1}\mathbf{1}^\dagger D \alpha}{\alpha^\dagger D \alpha}$$
   donde $A$ es la matriz de adyacencia, $D$ es la matriz de grado, $\mathbf{1}$ es el vector de unos y $\xi > 0$ es un parámetro de penalización. El numerador incluye un término de penalización diseñado para suprimir el autovector trivial (el vector constante), asegurando soluciones de agrupamiento no triviales.

2. Diseño del Circuito Cuántico: El marco utiliza tres estimadores cuánticos específicos para evaluar los términos de la función objetivo sin construir la matriz:

   • $q_a(\alpha)$: Estima la forma cuadrática de la adyacencia ($\alpha^\dagger A \alpha$).
   • $q_d(\alpha)$: Estima la forma cuadrática ponderada por el grado ($\alpha^\dagger D \alpha$).
   • $q_p(\alpha)$: Estima el término de penalización del proyector ($\alpha^\dagger D \mathbf{1}\mathbf{1}^\dagger D \alpha$).

   Estos estimadores dependen de una unitaria de codificación de datos $U_{\phi, D}$ que prepara una superposición indexada de puntos de datos y un estado de ponderación entrenable $|\alpha_\theta\rangle$ en un registro de índices. Los circuitos utilizan subrutinas de estilo prueba SWAP para computar fidelidades (similitud) entre estados cuánticos.

3. Inferencia (Prueba): Para puntos de datos no vistos $\hat{x}$, se define una función de puntuación basada en la fase del solapamiento entre el estado de prueba y el estado de ponderación entrenado. La fase $\hat{\phi}(\hat{x}, \hat{\alpha})$ se extrae mediante circuitos de interferencia (midiendo cúbits ancilla en las bases $\sigma_x$ y $\sigma_y$) y se utiliza para asignar etiquetas de agrupación mediante umbralización o agrupamiento circular.

4. Flujo de Trabajo de Entrenamiento: Los parámetros del estado de ponderación $|\alpha_\theta\rangle$ se optimizan utilizando un optimizador clásico (descenso de gradiente) guiado por los estimadores cuánticos. El gradiente se calcula utilizando la regla de desplazamiento de parámetros (parameter-shift rule).

Contribuciones Clave

• Estructuras de Circuitos Compactos: Los autores presentan una familia de circuitos cuánticos que estiman directamente los componentes del cociente de Rayleigh. Este enfoque evita la construcción de la matriz de núcleo completa o parcial y la estimación de las entradas del núcleo de forma individual, que son cuellos de botella en otros métodos espectrales cuánticos.
• Análisis Riguroso de la Complejidad de Disparos (Shot Complexity): Un análisis teórico demuestra que la complejidad de muestreo para el término de penalización ($q_p$) es tratable. Contrario a la intuición de que la menor magnitud del término de penalización podría requerir más disparos, los autores demuestran, utilizando desigualdades de concentración, que el número de disparos requerido crece, como máximo, de forma cuasi-polinomial con respecto a la probabilidad de fallo. Esto valida que el estimador de la penalización no domina el presupuesto total de muestreo.
• Flujo de Trabajo Unificado de Entrenamiento-Prueba: El marco proporciona un flujo de trabajo completo, desde la optimización variacional hasta la inferencia en datos no vistos utilizando un mecanismo de puntuación basado en la fase.

Resultados
Los autores validaron el marco utilizando simulaciones cuánticas sin ruido en conjuntos de datos canónicos:

• Conjuntos de Datos: El conjunto de datos Iris (agrupamiento binario de Setosa frente a Versicolor/Virginica) y el conjunto de datos MNIST (agrupamiento binario de los dígitos '0' y '1', reducido a 4 dimensiones mediante PCA).
• Desempeño:
  • Iris: Con un circuito relativamente poco profundo (4 capas, 24 parámetros), el modelo alcanzó una precisión de prueba promedio del 98.7%. El aumento de las capas a 6 o más estabilizó la precisión en $\ge 99.8\%$.
  • MNIST: El desempeño confiable comenzó en 6 capas, estabilizándose en una precisión promedio del 97.2% para 8 o más capas.
• Comportamiento de Disparos Finitos: Las simulaciones confirmaron que el estimador de la penalización se comporta según lo previsto. La media muestral del término de penalización convergió rápidamente a cero, y la varianza se contrajo de acuerdo. Crucialmente, el término de penalización pudo estimarse de manera confiable con un número relativamente pequeño de disparos (por ejemplo, 256–1024), consistente con el análisis teórico de que no requiere un presupuesto de disparos significativamente mayor que los otros términos.

Significancia y Reivindicaciones
El artículo posiciona este trabajo como una "prueba de concepto" para un marco de agrupamiento espectral que es compatible con circuitos cuánticos de poca profundidad y eficientes en hardware. La significancia principal radica en:

1. Evitar los Cuellos de Botella de la Matriz de Núcleo: Al operar sobre formas cuadráticas agregadas, el método elude los costos de $O(M^2)$ o $O(M^4)$ asociados con la estimación de entradas de núcleo elemento por elemento en entornos cuánticos.
2. Mitigar el Desajuste de Escala: El análisis riguroso muestra que el término de penalización, que a menudo es una fuente de inestabilidad numérica o de alto costo de muestreo, puede estimarse eficientemente, haciendo que el objetivo variacional sea práctico.
3. Contexto de Aprendizaje No Supervisado: Los autores señalan que, si bien los métodos de núcleo cuántico están bien estudiados en el aprendizaje supervisado, su aplicación al agrupamiento espectral no supervisado está menos explorada. Este trabajo une la teoría espectral de grafos con algoritmos cuánticos variacionales en este dominio específico.

Los autores mantienen la modestia respecto a reivindicaciones más amplias, declarando explícitamente que no abordan si el núcleo de fidelidad cuántica proporciona una ventaja cuántica sobre los núcleos clásicos para tareas generales. En su lugar, el enfoque es proporcionar una implementación eficiente asumiendo que el núcleo cuántico es la medida de similitud elegida. Sugieren que trabajos futuros podrían extender este enfoque de análisis de penalización a otros algoritmos variacionales con términos de penalización (por ejemplo, problemas QUBO) e investigar más a fondo las propiedades teóricas de las codificaciones cuánticas en entornos no supervisados.