Sparse Carleman Embeddings for Nonlinear Discrete Dynamical Systems

Technical Summary: Sparse Carleman Embeddings for Nonlinear Discrete Dynamical Systems

Problem Statement
The paper addresses the computational challenge of simulating discrete nonlinear dynamical systems of the form $x_{n+1} = F(x_n)$, specifically focusing on forced quadratic iterations ($x_{n+1} = f + Ax_n + Bx_n \otimes x_n$). These systems arise in population modeling, fluid dynamics, and machine learning (e.g., gradient-based optimization and recurrent neural networks). While Quantum Linear System Algorithms (QLSAs) offer exponential speedups for linear systems, applying them to nonlinear dynamics requires lifting the problem into a higher-dimensional linear space. The primary obstacles identified are:

1. Truncation Error: Carleman embedding converts nonlinear updates into an infinite linear recurrence. Truncating this hierarchy introduces errors that must remain controlled over long iteration horizons.
2. Sparsity Loss: A critical issue in the discrete setting is that even if the original coefficient maps ($f, A, B$) are sparse, the lifted Carleman matrix often becomes dense. For example, if $A$ has row sparsity $s_A$, the degree-$N$ block $A^{\otimes N}$ can have sparsity $s_A^N$, rendering standard sparse-access quantum algorithms inefficient.
3. Conditioning: The linear systems used to solve for the history of states must have manageable condition numbers to ensure efficient quantum solution.

Methodology
The authors propose a framework combining Carleman embedding with a novel sparse auxiliary representation and a history-state linear system formulation.

1. Carleman Embedding and Truncation:
   The state is lifted to a vector $X_n$ containing tensor powers $(1, x_n, x_n^{\otimes 2}, \dots)$. The nonlinear update becomes a linear recurrence $X_{n+1} = L X_n$. The authors analyze the truncated system $y^{(N)}_{n+1} = L_N y^{(N)}_n$, where $L_N$ retains degrees up to $N$.

2. Sparse Auxiliary Realization:
   To overcome the density of $L_N$, the authors construct an exact auxiliary linear system representation. Instead of explicitly forming the dense tensor products, they introduce an auxiliary operator $C$ and embeddings $E_{in}, E_{out}$ such that:
   $$L_N = E_{in}^\dagger (I - C^\dagger)^{-1} E_{out}$$
   The operator $C$ is constructed to apply the original coefficient maps ($f, A, B$) one tensor factor at a time. Crucially, the row and column sparsity of the resulting matrix $D = I - C^\dagger$ is bounded by $1 + s_f + s_A + s_B$, independent of the truncation degree $N$. This allows the use of sparse-access QLSAs without expanding the dense tensor structure.

3. Rescaling and History System:
   To control the condition number of the linear system over $n$ iterations, the authors rescale the coefficients using a radius $r$ within the stability region. They then formulate a "history system" that couples the first $n$ time steps into a single sparse linear system $\tilde{A}_n \mathbf{w} = \mathbf{b}$.

   • Conditioning: They prove the condition number $\kappa(\tilde{A}_n)$ grows linearly with $n$ ($\Theta(n)$), with constants independent of the truncation degree $N$.
   • State Extraction: To mitigate the $1/n$ probability loss inherent in extracting the final state from a history state, they employ a "terminal padding" technique, repeating the final auxiliary vector $n$ times. This improves the success probability of extracting the physical state to be independent of $n$ (dependent only on the norm of the state).

Key Contributions and Results

1. Uniform Geometric Convergence:
   Under explicit stability assumptions (Assumption 1), the authors prove that the truncation error for the degree-one block (the physical state approximation) decreases geometrically with the embedding degree $N$. Specifically, $\sup_{n \ge 0} \|x_n - y^{(N)}_{n,1}\| \le \rho R^N$ where $R < 1$. This implies that for a fixed error tolerance $\epsilon$, a truncation degree $N = O(\log(1/\epsilon))$ suffices, regardless of the number of iterations $n$.

2. Sparse Representation of Lifted Updates:
   The paper constructs an exact representation of the truncated Carleman matrix using an auxiliary operator with sparsity bounded independently of $N$. This resolves the "sparsity explosion" problem typical of discrete Carleman lifts, enabling efficient quantum access.

3. Quantum Algorithm Complexity:
   The authors derive a quantum algorithm to prepare a state approximating the normalized $n$-th iterate $x_n / \|x_n\|$.

   • Query Complexity: The algorithm achieves trace-distance error $\epsilon$ with constant success probability. The query complexity is $O(s n K_r \Gamma \log(\Gamma/\epsilon))$, where $s$ is the sparsity bound, $n$ is the iteration count, and $\Gamma$ depends on stability parameters and the lower bound $\xi$ on $\|x_n\|$.
   • Scaling: For fixed stability parameters and $\xi$, the complexity is linear in $n$ and polylogarithmic in $1/\epsilon$.
   • Assumptions: The result relies on coherent input access to the coefficients and a known positive lower bound on the final state norm.

4. Numerical Validation:
   Numerical experiments in one and three dimensions confirm the theoretical convergence rates. The results show that the truncation error decreases geometrically with $N$ and that the trajectories converge to the stable fixed points as predicted.

Significance and Claims
The paper claims to provide the first rigorous analysis of Carleman embedding for discrete quadratic systems that simultaneously addresses truncation error, sparsity, and conditioning for quantum implementation.

• Separation of Concerns: The work successfully separates the accuracy requirements of the Carleman approximation (controlled by $N$) from the sparsity requirements of the quantum solver (controlled by the auxiliary construction).
• Efficiency: By proving that the condition number of the history system is independent of $N$ and that sparsity is preserved, the authors demonstrate that a convergent Carleman approximation can be combined with a quantum implementation without the total cost exploding as the truncation degree increases.
• Scope: The results are specific to a stable class of quadratic discrete dynamical systems. The authors note that while the method extends to higher-degree polynomials, the current analysis focuses on the quadratic case. They acknowledge that extending these guarantees to broader non-polynomial classes or analyzing the full cost of observable estimation remain open directions.

The paper concludes that under the stated assumptions, it is possible to prepare an approximation of the $n$-th iterate of a nonlinear map with a quantum algorithm whose cost scales linearly with the number of iterations, offering a potential pathway for simulating complex discrete dynamics on quantum hardware.