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 $n$th 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.
AI Summary
The paper studies whether exact discrete-time Carleman lifting can support efficient quantum state preparation despite tensor-product updates becoming dense. It considers forced quadratic recurrences $x_{t+1}=f+Ax_t+B x_t^{\otimes2}$ in a stable regime, with $\|A\|\le\alpha<1$, $\|B\|\le\beta$, $c=\|f\|$, $\Delta=(1-\alpha)^2-4\beta c>0$, and $\|x_0\|<r_+$, where $r_\pm=(1-\alpha\pm\sqrt\Delta)/(2\beta)$.
For degree-$N$ truncation, it proves $\sup_t\|x_t-y_{t,1}^{(N)}\|\le\rho(\rho/r_+)^N$, with $\rho=\max\{\|x_0\|,r_-\}$. Thus logarithmic degree suffices for fixed accuracy, independently of the iteration horizon. The proof majorizes lifted coefficients by a scalar quadratic map and inductively bounds propagated truncation errors. To avoid expanding dense tensor products, an exact auxiliary linear system applies coefficient maps one tensor factor at a time; its row and column sparsities are at most $1+s_f+s_A+s_B$, independently of $N$.
Rescaling yields uniformly bounded auxiliary inverses and lifted powers. These give a sparse history system with condition number $\Theta(n)$, uniformly in $N$. Terminal padding and amplitude amplification enable preparation of the normalized $n$th iterate. Assuming coherent sparse access, initial-state preparation, and a known bound $0<\xi\le\|x_n\|$, coefficient-oracle and right-hand-side preparation queries scale linearly in $n$ and polylogarithmically in inverse accuracy for fixed sparsity, stability parameters, and $\xi$; initial-state oracle calls incur an additional factor $N$.
The guarantees concern encoded state preparation, not classical readout or observable estimation. Stability and final-norm promises restrict applicability. Small one- and three-dimensional experiments illustrate truncation convergence; broader nonpolynomial dynamics remain open.
Little sign of AI-generated textStrong assumptions
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper studies whether exact discrete-time Carleman lifting can support efficient quantum state preparation despite tensor-product updates becoming dense. It considers forced quadratic recurrences xt+1=f+Axt+Bxt⊗2 in a stable regime, with ∥A∥≤α<1, ∥B∥≤β, c=∥f∥, Δ=(1−α)2−4βc>0, and ∥x0∥<r+, where r±=(1−α±Δ)/(2β).
For degree-N truncation, it proves supt∥xt−yt,1(N)∥≤ρ(ρ/r+)N, with ρ=max{∥x0∥,r−}. Thus logarithmic degree suffices for fixed accuracy, independently of the iteration horizon. The proof majorizes lifted coefficients by a scalar quadratic map and inductively bounds propagated truncation errors. To avoid expanding dense tensor products, an exact auxiliary linear system applies coefficient maps one tensor factor at a time; its row and column sparsities are at most 1+sf+sA+sB, independently of N.
Rescaling yields uniformly bounded auxiliary inverses and lifted powers. These give a sparse history system with condition number Θ(n), uniformly in N. Terminal padding and amplitude amplification enable preparation of the normalized nth iterate. Assuming coherent sparse access, initial-state preparation, and a known bound 0<ξ≤∥xn∥, coefficient-oracle and right-hand-side preparation queries scale linearly in n and polylogarithmically in inverse accuracy for fixed sparsity, stability parameters, and ξ; initial-state oracle calls incur an additional factor N.
The guarantees concern encoded state preparation, not classical readout or observable estimation. Stability and final-norm promises restrict applicability. Small one- and three-dimensional experiments illustrate truncation convergence; broader nonpolynomial dynamics remain open.
We develop a pivot-shifted Carleman linearization framework for quantum algorithms solving quadratic nonlinear ordinary differential equations. By shifting the dynamics by a pivot state prior to Carleman lifting, and combining this with a Lyapunov transform and rescaling, we enlarge the class of nonlinear systems that can be efficiently simulated on quantum computers. For systems that exhibit stability in the shifted coordinates, we establish long time convergence of the truncated Carleman embedding. We prove that the truncation order scales only logarithmically with the simulation time and target precision, and we derive end-to-end quantum query complexity bounds for preparing a state proportional to the final solution. By introducing a modified nonlinearity condition, this framework entirely removes the conventional lower bound requirement on the initial condition. For more general systems that remain unstable after shifting, we provide short time convergence guarantees that are similarly free from the initial condition constraints. Numerical experiments on the logistic and the Lotka-Volterra equations demonstrate that an appropriate pivot choice improves stability and accuracy, and yields exponential error decay with truncation order. These results show that pivot shifting provides a practical and theoretically justified route for extending Carleman-based quantum algorithms to a broader class of nonlinear dynamical systems.
We develop a quantum algorithm for solving the dynamics of the nonlinear viscous Burgers equation. We apply the Carleman linearization procedure on the spatially discretized equation, followed by a padding scheme that allows implementation on qubit registers. Existing Carleman-based quantum algorithms commonly formulate the lifted linear differential equation in an oracle model. Here we decompose the padded generator into diagonal masks and reversible arithmetic permutations using the Permutation Matrix Representation (PMR), which we show to be naturally compatible with the Linear Combination of Hamiltonian Simulations (LCHS) algorithm. Under the assumptions required by LCHS - most importantly positive semidefiniteness of the Hermitian part of the linear generator, possibly after a stabilizing shift - the algorithm prepares a normalized quantum state proportional to the solution of the truncated lifted system; the stabilizing shift introduces an exponential postselection overhead, which we quantify and mitigate through a rescaling scheme. We show that our algorithm scales with the off-diagonal norm of the Carleman generator instead of the matrix norm, which can be advantageous for other generators that are diagonally dominant. We also extend the PMR scheme to general fluid equations that may contain higher-order derivatives or nonlinear terms, or may involve multiple fluid variables or spatial dimensions. The construction illustrates how PMR can serve as a convenient Hamiltonian-simulation primitive for a broader class of LCU-based algorithms.
Addressing nonlinear numerical problems in quantum computing remains challenging, but several approaches, including Carleman linearization (CL), have been proposed to construct quantum algorithms for such problems. In this work, we develop a CL-based method for a high-dimensional nonlinear stochastic differential equation (SDE) dXt=(A(t)Xt+F(t)Xt⊗s)dt+B(t)dWt for an RN-valued random process Xt, aiming at quantum speed-up with respect to the dimension N. We introduce auxiliary processes Ytj that approximate Xt⊗j, derive a linearized system of SDEs for them, and obtain the linear ordinary differential equation (ODE) governing their expectations. We then apply a quantum ODE solver to it and, from the resulting quantum state, extract an estimate for the expectation of a linear function of Xt by overlap estimation. We show that, provided the nonlinear and noise terms in the SDE are sufficiently small relative to the linear term, the CL error decreases exponentially with the truncation order J in CL, and we can estimate the target expectation with a polylog(N) number of queries to unitaries encoding coefficient matrices A, F, and B. Finally, we also run a numerical demonstration for an SDE related to Langevin dynamics, observing the exponential decay of the CL error as J increases.
We give quantum algorithms for Hamiltonian simulation, linear differential equations, and linear systems with square-root dependence on sparsity. For an s-sparse Hermitian matrix with row and column Euclidean norms bounded by η, evolution for time t to error ε uses O(sτ+sτlog(1/ε)+log(1/ε)) queries, where τ=η∣t∣. The same bound holds for time-dependent Hamiltonians with coherent time-indexed sparse access and certified time discretisation. Our construction combines an exact entrywise representation with Cayley transducers. A joint lower bound nearly matches the time, sparsity, and precision dependence, ruling out a uniformly additive bound in sτ and log(1/ε). For dissipative linear differential equations we obtain O(gˉ[s(τ+τ)+1]log(Cgˉ/ε)) queries, where τ is the evolution time multiplied by a norm bound, gˉ bounds the ratio of combined input and source norms to the final-solution norm, and C is an absolute constant. We sharpen this bound by separating Hamiltonian and dissipative components, and treat general constant generators. Lower bounds capture joint parameter dependence for time-dependent equations and precision hardness for constant positive semidefinite dissipation. For linear systems, a Cayley walk and Chebyshev filter give O(κslog(1/ε)) queries when ∥A∥≤1 and ∥A−1∥≤κ, and we give an alternative proof of a matching joint lower bound. We also give gate-efficient implementations of time-independent Hamiltonian simulation and the dissipative ODE solver, including Lipschitz time dependence, retaining the query bounds with polylogarithmic overhead in inverse precision given efficient entry decoding, arithmetic, and required source preparations.
This paper presents a rigorous derivation pipeline for the quantum simulation of sparse polynomial nonlinear ordinary differential equations. The framework proceeds in three stages: (i) mapping the nonlinear dynamics to an exact infinite-dimensional linear system via Carleman–Koopman lifting; (ii) applying a graph-theoretic truncation and compression scheme that exploits the sparsity and locality of the dependency graph; and (iii) implementing Schr\"odingerisation for the resulting class of dissipative, Hermitian positive definite generators to yield a unitary-overlap formula compatible with standard quantum primitives. The study provides a comprehensive mathematical construction of these steps, establishing the algebraic and analytical foundations required for structure-preserving quantum simulation.
We give a quantum algorithm for simulating a d-sparse Hermitian Hamiltonian H, assuming a known upper bound Λ on its maximum column Euclidean norm ∥H∥1→2. For tΛ≥1/2, simulation with operator-norm error ε uses O(tΛd+dlog(2/ε)) sparse-oracle queries. This removes the subpolynomial overhead in Low's algorithm [STOC 2019], replacing it with an additive logarithmic precision term. For d>1 and tΛ≥log(2/ε), the bound matches the worst-case lower bound. A known spectral-norm upper bound may also be used in place of Λ. The number of 1- and 2-qubit gates is linear in the query scale, up to oracle costs and polynomial overhead in the input bit lengths and logarithmic precision parameters.
As applications, we obtain O(κdpolylog(κ/ε)) queries for solving d-sparse quantum linear systems with ∥A∥≤1 and ∥A−1∥≤κ, under standard sparse and state-preparation access. We also give a gate-efficient implementation of black-box unitaries with at most d nonzero entries per row and column using O(dlog(2/ε)) queries, given sparse access to the unitary and its adjoint. At constant error, the query bound is optimal and yields Θ(N) queries for arbitrary N×N unitaries, resolving the open question on black-box unitary implementation posed by Berry and Childs [QIC 2012].