Sparse Carleman Embeddings for Nonlinear Discrete Dynamical Systems
Abstract
Discrete nonlinear dynamical systems arise in population models, iterative optimization, and numerical simulations, where computing many iterations can be costly in high dimensions. We study Carleman embedding for forced quadratic discrete systems and its application to quantum state preparation. Under explicit stability and initial-state assumptions, we prove that the truncation error decreases geometrically with the embedding degree, uniformly over all iterations. A central obstacle in discrete time is that the lifted update can become dense even when the original coefficient maps are sparse. We overcome this obstacle by constructing an exact auxiliary linear-system representation that applies the coefficient maps one tensor factor at a time, with row and column sparsities bounded independently of the truncation degree. After rescaling, the associated history system has a condition number that grows linearly with the iteration count, uniformly in the truncation degree. These results yield a quantum algorithm for preparing an approximation to the normalized nth iterate with constant success probability. Under coherent input-access assumptions, and for fixed sparsity, stability parameters, and a known positive lower bound on the final-state norm, the oracle query complexity is linear in n and polylogarithmic in the inverse accuracy. Numerical experiments in one and three dimensions illustrate the convergence of the truncated embedding.
Related
- Residual Carleman lift for nonlinear lattice Boltzmann simulations
- Universal Construction of Generalized Lyapunov Functions for Nonlinear Dynamical Systems Using Physics-Informed Neural Networks
- Reduction Based Dynamical Systems Analysis of Nonlinear Wave Equations: A Review
- Nonlinear Dynamical Systems as Scalable and Efficient Physical Neural Networks
- Quantum algorithm for high-dimensional nonlinear stochastic differential equations based on Carleman linearization
BibTeX
@misc{wu2026sparse,
title = {{Sparse Carleman Embeddings for Nonlinear Discrete Dynamical Systems}},
author = {Hsuan-Cheng Wu and Xiantao Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35824},
eprint = {2610.35824},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35824},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sparse Carleman Embeddings for Nonlinear Discrete Dynamical Systems
AU - Hsuan-Cheng Wu
AU - Xiantao Li
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35824
UR - https://arxiv.org/abs/2610.35824
AB - Discrete nonlinear dynamical systems arise in population models, iterative optimization, and numerical simulations, where computing many iterations can be costly in high dimensions. We study Carleman embedding for forced quadratic discrete systems and its application to quantum state preparation. Under explicit stability and initial-state assumptions, we prove that the truncation error decreases geometrically with the embedding degree, uniformly over all iterations. A central obstacle in discrete time is that the lifted update can become dense even when the original coefficient maps are sparse. We overcome this obstacle by constructing an exact auxiliary linear-system representation that applies the coefficient maps one tensor factor at a time, with row and column sparsities bounded independently of the truncation degree. After rescaling, the associated history system has a condition number that grows linearly with the iteration count, uniformly in the truncation degree. These results yield a quantum algorithm for preparing an approximation to the normalized nth iterate with constant success probability. Under coherent input-access assumptions, and for fixed sparsity, stability parameters, and a known positive lower bound on the final-state norm, the oracle query complexity is linear in n and polylogarithmic in the inverse accuracy. Numerical experiments in one and three dimensions illustrate the convergence of the truncated embedding.
ER -