Sparse Carleman Embeddings for Nonlinear Discrete Dynamical Systems

Resumen Técnico: Incrustaciones de Carleman Dispersas para Sistemas Dinámicos Discretos No Lineales

Planteamiento del Problema
El artículo aborda el desafío computacional de simular sistemas dinámicos discretos no lineales de la forma $x_{n+1} = F(x_n)$, centrándose específicamente en iteraciones cuadráticas forzadas ($x_{n+1} = f + Ax_n + Bx_n \otimes x_n$). Estos sistemas surgen en el modelado de poblaciones, la dinámica de fluidos y el aprendizaje automático (por ejemplo, optimización basada en gradientes y redes neuronales recurrentes). Aunque los Algoritmos de Sistemas Lineales Cuánticos (QLSA) ofrecen aceleraciones exponenciales para sistemas lineales, la aplicación de estos a la dinámica no lineal requiere elevar el problema a un espacio lineal de mayor dimensión. Los principales obstáculos identificados son:

1. Error de Truncamiento: La incrustación de Carleman convierte las actualizaciones no lineales en una recurrencia lineal infinita. Truncar esta jerarquía introduce errores que deben permanecer controlados durante horizontes de iteración prolongados.
2. Pérdida de Dispersión (Sparsity): Un problema crítico en el entorno discreto es que, incluso si los mapas de coeficientes originales ($f, A, B$) son dispersos, la matriz de Carleman elevada suele volverse densa. Por ejemplo, si $A$ tiene una dispersión de fila $s_A$, el bloque de grado-$N$, $A^{\otimes N}$, puede tener una dispersión de $s_A^N$, lo que hace que los algoritmos cuánticos estándar de acceso disperso sean ineficientes.
3. Condicionamiento: Los sistemas lineales utilizados para resolver la historia de los estados deben tener números de condición manejables para asegurar una solución cuántica eficiente.

Metodología
Los autores proponen un marco que combina la incrustación de Carleman con una novedosa representación auxiliar dispersa y una formulación de sistema lineal de estado de historia.

1. Incrustación de Carleman y Truncamiento:
   El estado se eleva a un vector $X_n$ que contiene potencias tensoriales $(1, x_n, x_n^{\otimes 2}, \dots)$. La actualización no lineal se convierte en una recurrencia lineal $X_{n+1} = L X_n$. Los autores analizan el sistema truncado $y^{(N)}_{n+1} = L_N y^{(N)}_n$, donde $L_N$ retiene los grados hasta $N$.

2. Realización Auxiliar Dispersa:
   Para superar la densidad de $L_N$, los autores construyen una representación exacta de un sistema lineal auxiliar. En lugar de formar explícitamente los productos tensoriales densos, introducen un operador auxiliar $C$ y las incrustaciones $E_{in}, E_{out}$ tales que:
   $$L_N = E_{in}^\dagger (I - C^\dagger)^{-1} E_{out}$$
   El operador $C$ se construye para aplicar los mapas de coeficientes originales ($f, A, B$) un factor tensorial a la vez. Crucialmente, la dispersión de fila y columna de la matriz resultante $D = I - C^\dagger$ está acotada por $1 + s_f + s_A + s_B$, independientemente del grado de truncamiento $N$. Esto permite el uso de QLSAs de acceso disperso sin expandir la estructura tensorial densa.

3. Reescalado y Sistema de Historia:
   Para controlar el número de condición del sistema lineal a lo largo de $n$ iteraciones, los autores reescalan los coeficientes utilizando un radio $r$ dentro de la región de estabilidad. Luego, formulan un "sistema de historia" que acopla los primeros $n$ pasos de tiempo en un único sistema lineal disperso $\tilde{A}_n \mathbf{w} = \mathbf{b}$.

   • Condicionamiento: Demuestran que el número de condición $\kappa(\tilde{A}_n)$ crece linealmente con $n$ ($\Theta(n)$), con constantes independientes del grado de truncamiento $N$.
   • Extracción de Estado: Para mitigar la pérdida de probabilidad de $1/n$ inherente a la extracción del estado final de un estado de historia, emplean una técnica de "relleno terminal" (terminal padding), repitiendo el último vector auxiliar $n$ veces. Esto mejora la probabilidad de éxito de la extracción del estado físico para que sea independiente de $n$ (dependiendo únicamente de la norma del estado).

Contribuciones Clave y Resultados

1. Convergencia Geométrica Uniforme:
   Bajo supuestos de estabilidad explícitos (Supuesto 1), los autores demuestran que el error de truncamiento para el bloque de grado uno (la aproximación del estado físico) disminuye geométricamente con el grado de incrustación $N$. Específicamente, $\sup_{n \ge 0} \|x_n - y^{(N)}_{n,1}\| \le \rho R^N$ donde $R < 1$. Esto implica que para una tolerancia de error fija $\epsilon$, un grado de truncamiento $N = O(\log(1/\epsilon))$ es suficiente, independientemente del número de iteraciones $n$.

2. Representación Dispersa de Actualizaciones Elevadas:
   El artículo construye una representación exacta de la matriz de Carleman truncada utilizando un operador auxiliar con una dispersión acotada independientemente de $N$. Esto resuelve el problema de la "explosión de dispersión" típico de las elevaciones de Carleman discretas, permitiendo un acceso cuántico eficiente.

3. Complejidad del Algoritmo Cuántico:
   Los autores derivan un algoritmo cuántico para preparar un estado que aproxime la $n$-ésima iteración normalizada $x_n / \|x_n\|$.

   • Complejidad de Consulta (Query Complexity): El algoritmo logra un error de distancia de traza $\epsilon$ con una probabilidad de éxito constante. La complejidad de consulta es $O(s n K_r \Gamma \log(\Gamma/\epsilon))$, donde $s$ es la cota de dispersión, $n$ es el número de iteraciones, y $\Gamma$ depende de los parámetros de estabilidad y el límite inferior $\xi$ de $\|x_n\|$.
   • Escalabilidad: Para parámetros de estabilidad fijos y $\xi$, la complejidad es lineal en $n$ y polilogarítmica en $1/\epsilon$.
   • Supuestos: El resultado depende del acceso coherente a los coeficientes de entrada y de un límite inferior positivo conocido sobre la norma del estado final.

4. Validación Numérica:
   Experimentos numéricos en una y tres dimensiones confirman las tasas de convergencia teórica. Los resultados muestran que el error de truncamiento disminuye geométricamente con $N$ y que las trayectorias convergen a los puntos fijos estables según lo previsto.

Significancia y Reivindicaciones
El artículo afirma proporcionar el primer análisis riguroso de la incrustación de Carleman para sistemas cuadráticos discretos que aborda simultáneamente el error de truncamiento, la dispersión y el condicionamiento para la implementación cuántica.

• Separación de Preocupaciones: El trabajo separa con éxito los requisitos de precisión de la aproximación de Carleman (controlados por $N$) de los requisitos de dispersión del resolvedor cuántico (controlados por la construcción auxiliar).
• Eficiencia: Al demostrar que el número de condición del sistema de historia es independiente de $N$ y que la dispersión se preserva, los autores demuestran que una aproximación de Carleman convergente puede combinarse con una implementación cuántica sin que el coste total explote a medida que aumenta el grado de truncación.
• Alcance: Los resultados son específicos para una clase estable de sistemas dinámicos discretos cuadráticos. Los autores señalan que, si bien el método se extiende a polinomios de grado superior, el análisis actual se centra en el caso cuadrático. Reconocen que extender estas garantías a clases más amplias no polinómicas o analizar el coste completo de la estimación de observables siguen siendo direcciones abiertas.

El artículo concluye que, bajo los supuestos establecidos, es posible preparar una aproximación de la $n$-ésima iteración de un mapa no lineal con un algoritmo cuántico cuyo coste escala linealmente con el número de iteraciones, ofreciendo una vía potencial para simular dinámicas discretas complejas en hardware cuántico.