WorksPhysics and Astronomy
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 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 and polylogarithmic in the inverse accuracy. Numerical experiments in one and three dimensions illustrate the convergence of the truncated embedding.
Introduction
Discrete nonlinear dynamics are ubiquitous in scientific computing. They arise whenever a state is updated by a map . Such recurrences model populations with nonoverlapping generations [29] and time-stepping schemes for fluid dynamics [23]. Discrete nonlinear dynamics also arise naturally in machine learning, including gradient-based optimization [22, 12], recurrent neural networks [13], and the fixed-point formulations underlying deep equilibrium models [7]. The stability and convergence of these iterations play an important role in the design and analysis of learning algorithms [13, 8]. These examples are inherently specified by discrete updates: a discrete dynamical system need not be a sampling or numerical discretization of any continuous-time evolution. Even a low-degree map can exhibit behavior that is difficult to infer from a single update, while a high-dimensional map can be costly to iterate or probe over many steps. These observations motivate algorithms that exploit the structure of to access a later state or a selected observable. We focus on a stable quadratic regime in which the iterates converge to a fixed point.
A natural route toward quantum algorithms for nonlinear recurrences is to represent their updates as linear evolution in an enlarged space. For polynomial maps, Carleman embedding provides precisely this representation: introduce the monomials of the state, represented here by tensor powers , and expand their updates under to obtain an infinite linear recurrence [19]. Truncating this hierarchy yields a finite linear approximation to the original nonlinear dynamics. This construction connects nonlinear iteration with quantum algorithms for linear algebra, provided that the approximation error and the cost of accessing the enlarged system can be controlled.
Quantum linear-system algorithms (QLSAs) make this connection computationally useful. Beginning with the algorithm of Harrow, Hassidim, and Lloyd [15], these methods prepare quantum states proportional to solutions of linear systems, with subsequent developments improving the dependence on accuracy and conditioning [32, 28]. For a truncated Carleman recurrence, the lifted states at successive iterations can be coupled through a single history linear system, following the general strategy used in quantum algorithms for differential equations [26, 16, 27, 21]. Solving this system prepares a state encoding the lifted history, from which a state proportional to the desired nonlinear iterate can be extracted, subject to the truncation error. Under suitable sparsity and coherent-access assumptions, the linear-system solver can have only polylogarithmic dependence on the enlarged dimension.
Realizing this potential requires more than a finite-dimensional approximation. The truncation error must remain controlled over the iteration horizon, the lifted operator must admit efficient quantum access, and the history system must have manageable conditioning. The cost of extracting the desired physical state from the lifted history must also be included. These requirements are coupled: increasing the truncation order enlarges the representation and may increase its implementation cost, even when it improves the approximation. The central question is therefore whether a convergent Carleman approximation can be combined with a quantum implementation whose total cost remains controlled. We address this question for a stable class of quadratic discrete dynamical systems.
Other quantum approaches to nonlinear problems include evolution of multiple copies of a state through a mean-field approximation [17] and Koopman–von Neumann representations of classical dynamics [18]. Homotopy perturbation has also been used to construct quantum algorithms for dissipative nonlinear ordinary differential equations [30] and for quadratic nonlinear algebraic systems [31]. The latter solves for a root of a nonlinear equation, whereas our task is to prepare a state associated with the th iterate of a nonlinear map. These methods suggest different ways to expose linear structure, with distinct requirements for approximation, state preparation, and output recovery.
This paper studies Carleman embedding for discrete dynamical systems under specific assumptions. The discrete setting creates the sparsity challenge: The update of each tensor power contains products of the coefficients of , including terms absent from a continuous-time Carleman generator. Moreover, sparse coefficients need not give a sparse truncated update: for , its degree- block is , whose row sparsity can grow as if has row sparsity . A convergence bound for the truncation therefore does not by itself yield an efficient sparse-access quantum implementation. This motivates a representation that applies the original coefficient maps one tensor factor at a time, without expanding their tensor products.
Main Contributions
We study the forced quadratic iteration
The Carleman lift collects the tensor powers of the state into
Writing , , and , the blocks of are
with and for . Retaining degrees defines
The degree-zero coordinate remains one, and the degree-one block approximates . We establish the following results.
Uniform truncation error. Under the stability and initial-state assumptions in Assumption 1, the degree-one block of the truncated lift satisfies
For fixed parameters with , a truncation degree gives error at most independently of the iteration count.
Sparse realization of the lifted update. We construct a nilpotent auxiliary operator and embeddings for which the truncated Carleman matrix has the exact representation
When has at most nonzeros and the row and column sparsities of are bounded by , each row and column of has at most nonzeros, independent of . We also bound and its condition number.
History state QLSA. After rescaling, the first truncated updates form a sparse linear system
where
We prove with constants independent of . Under coherent sparse-access and input-state assumptions, the padded history system yields an algorithm for preparing a state close to . Its cost also accounts for output extraction and a lower bound on .
Combining the uniform truncation bound with the sparse history formulation, we obtain a quantum algorithm for preparing the normalized th iterate. Under coherent input-access assumptions and a known lower bound , the algorithm achieves trace-distance error at most with constant success probability, using
coefficient-oracle and right-hand-side preparation queries. Here bounds the sparsity, while and depend on the stability parameters and rescaling radius. For fixed parameters and , the query complexity is linear in the iteration count. Possible improvements of the sparsity dependence from to are discussed in Remark 4.6.
Related Work
Carleman representations of discrete recurrences predate quantum algorithms. Berkolaiko et al. [19] studied polynomial and analytic recursions, and Myszkowski [6] developed constructions for multivariate polynomial recurrences and systems with memory. Pruekprasert et al. [4, 5] studied truncated Carleman propagation for discrete-time stochastic polynomial systems and established approximation-error bounds. Deterministic polynomial maps are included as a special case of that setting. These results provide direct precedents for discrete lifting and truncation analysis.
Liu et al. [22] developed Carleman-based quantum algorithms for discrete gradient updates. Their supplementary analysis treats truncation error, history linear systems, conditioning, sparsity, and corrections arising from the discrete product rule. In particular, it includes an error bound independent of the iteration count under a contraction assumption on the chosen lifted update. Their main construction uses a small-learning-rate approximation, while the supplement also derives the higher-order discrete corrections. Our analysis instead treats the exact forced quadratic update throughout and derives its guarantees directly from explicit bounds on the original coefficient maps and initial state.
In fluid dynamics, Sanavio and Succi [1] applied Carleman lifting to the discrete collision and streaming updates of the lattice Boltzmann method, constructed quantum circuits, and numerically investigated the accuracy of low-order truncations. Sanavio et al. [2] subsequently developed matrix-access oracles and block encodings for the discrete Carleman update. They reported sparsity growing exponentially with truncation order and low success probabilities that hinder repeated time stepping. These works provide direct precedents for quantum implementation of discrete Carleman dynamics and motivate controlling the implementation cost as the truncation degree increases.
More recently, Jennings et al. developed a discrete Carleman formulation for lattice Boltzmann dynamics and examined time-stepping, conditioning, and data extraction through an end-to-end complexity analysis [23]. They also numerically investigated truncation convergence, but did not establish a rigorous convergence guarantee for that application. Our work considers forced quadratic maps under explicit stability assumptions and provides an exact sparse auxiliary realization of the truncated Carleman update, a truncation-error bound uniform in the iteration count, and a history-system analysis with sparsity independent of the tensor degree. The resulting quantum algorithm prepares an encoded solution state. Observable estimation and full classical readout incur additional costs.
Outline
The remainder of the paper is organized as follows. In § 2, we formulate the quadratic iteration and its Carleman embedding, then establish a truncation-error bound that is uniform in the number of iterations. In § 3, we construct an auxiliary sparse system that represents the truncated Carleman update exactly, without explicitly forming its potentially dense matrix. In § 4, we develop the rescaled history-system formulation and analyze its conditioning, the recovery of the physical state, and the quantum algorithm’s query complexity. Finally, § 5 presents numerical experiments illustrating the convergence of the truncated embedding. All of the proofs are deferred to appendices.
Notation.
Throughout, denotes the Euclidean norm for vectors and the induced operator norm for matrices. denotes the trace norm for matrices. For an invertible matrix , we write for its condition number. The superscripts and denote the transpose and conjugate transpose, respectively. We use for the standard Kronecker product and adopt the convention . The symbols and denote the identity on and , respectively. denotes the set of nonnegative integers. All vectors are in bold font.
Mathematical Formulation
Problem Setup
We consider discrete quadratic iteration
for any , where , , and .
We note that the convergence argument and the method for building the quantum linear system can be extended to higher-degree polynomial discrete systems. We provide further details in Remark 2.2. In the remainder of this paper, we focus on the quadratic case for simplicity.
Assumption 1. There are known bounds and , and the known forcing norm is , with ,
Carleman embedding replaces the nonlinear iteration by a linear evolution of all tensor powers of the state. Let and adopt the convention . Define
where . For , set
and set for . Each block collects the terms of input degree in the expansion
In particular, , , , and .
The Carleman embedding system.
Carleman introduced a method for embedding nonlinear polynomial ODEs into an infinite-dimensional linear system by lifting the state to all monomials [14]. Here, we apply the same lifting principle to the discrete-time quadratic iteration, obtaining an infinite-dimensional linear recurrence for the lifted state.
Setting and for , the exact nonlinear iteration becomes the linear recurrence
This identity is interpreted blockwise: each block row contains only finitely many nonzero blocks, so no summability assumption on the full infinite vector is required.
For continuous-time quadratic ODE systems, the Carleman embedding yields a block-tridiagonal matrix [20]. In contrast, the discrete-time Carleman matrix in (7) generally lacks this structure.
Exact equations for the retained degrees.
Fix a truncation degree and retain
The matrix has dimension . Splitting (5) into retained and omitted input degrees gives the exact identity
where
An empty sum is zero. Thus whenever .
(9) is exact, but it is not a closed linear recurrence for the retained variables: the remainder contains tensor powers of degree greater than . (9) is useful for error analysis, which will be compared with the truncated Carleman system afterwards.
The truncated Carleman system.
Dropping the remainder in (9) defines the finite Carleman approximation
The degree-zero coordinate remains exactly one. Consequently, the positive-degree equations are affine:
The approximation to the original state is the degree-one block .
To distinguish the omitted terms from the accumulated approximation error, define
Subtracting (11) from (9) yields
Since , its positive-degree blocks satisfy
The second sum introduces truncation error only when , while the first sum propagates existing errors between retained degrees. Therefore lower-degree errors, including the error in the physical block , can become nonzero even when their equations have no direct omitted-degree term.
Convergence of Carleman embedding
We now state the uniform convergence of the Carleman embedding at finite truncation level-.
Theorem 2.1 (Uniform geometric convergence). Under Assumption 1, let and . For every , , and , In particular,
We defer the proof to § 8.
Remark 2.2. The formal procedure extends to polynomial maps of arbitrary finite degree. Define the scalar majorant , where . If there exist such that , , and , then the same coefficient-majorization argument yields where is the degree- Carleman truncation initialized by the tensor powers of . Thus, for fixed and , a truncation degree suffices for error at most , uniformly in the number of iterations. When , taking and recovers (17).
From now on, we use to denote for simplicity.
Sparse Realization of the Truncated Carleman Embedding
Recall the quadratic iteration (1),
We use Euclidean vector norms and their induced operator norms throughout. Assume that and have at most and nonzero entries in every row and column, respectively, and that has at most nonzero entries.
The sparsity of these coefficients does not imply sparsity of the discrete Carleman matrix. Even if , the degree- block is , whose row sparsity can be . Thus explicitly expanding the discrete Carleman matrix can destroy sparsity. We avoid this expansion by introducing auxiliary variables that process one original tensor factor at a time.
A Scalar Example at
Before we show that how to handle the sparsity in general, we first show that how to overcome it by a simple example with truncation level . Consider a scalar example,
Expanding , one has
The Carleman matrix at truncation level is
To expand the power of one factor at a time, introduce the auxiliary expressions , where records the accumulated input degree and records the number of factors remaining to be expanded,
We then define
This simple example demonstrates that the sparsity is not guaranteed after Carleman embedding. We see that and are dense operators.
In order to avoid dense operators, we decompose the iteration of the Carleman system into several substeps and each step only contains sparse operators. We introduce sparse rectangular matrices and as
For any fixed vector , we set the auxiliary vector
to solve . Then , , Therefore,
We conclude that
General Construction and Recovery Identity
We now show the same construction for the general vector iteration and prove the construction is equivalent to the original Carleman setup.
Recall that the Carleman blocks are defined in (4) with and for . The truncated matrix acts on the enlarged Hilbert space
The dimension of is . For each pair , we introduce an auxiliary space , and we group the spaces as
Then and We order the coordinates first by and then by :
Here records the input degree already produced, and records the number of factors still to be expanded. For , define through its blocks:
Thus branches with are omitted. Each nonzero block maps
and
Under the natural tensor identifications, we have
Define and by
Notice that is -nilpotent. Hence
In particular, is invertible without any norm condition on .
Finally, we introduce the embeddings
Both matrices have dimensions . The map inserts into layer zero, while inserts into the block of layer . Consequently,
Lemma 3.1. The truncated Carleman matrix can be written as
We provide the proof in § 9.
Lemma 3.2. Suppose every row and column of and has at most and nonzero entries, respectively, and has at most nonzero entries. Then every row and column of has at most nonzero entries, independently of the truncation degree .
We provide the proof in § 10.
Quantum Algorithms and Complexity
We use the sparse representation to prepare a quantum state proportional to at a prescribed iteration . The construction has three steps: rescale the coefficients to control conditioning, solve a padded history system, and select its physical block.
Rescaling and uniform operator bounds
Under Assumption 1, choose a fixed radius such that
Since , such an exists and satisfies
With , the original iteration becomes
Let , and be the matrices obtained by applying the construction of § 3 to these coefficients. The embeddings and the operator are unchanged. In particular,
The rescaled parameters are
Direct substitution gives
Together with , these identities verify Assumption 1 for the rescaled iteration. Moreover, and the sum of the coefficient bounds is .
To relate the truncated trajectories, note that for . Every tensor product contributing to has factors whose input degrees sum to , so its scale factor is . Consequently, with ,
In particular,
whenever the physical block is nonzero. Thus the classical approximation is recovered by multiplying by , while its normalized quantum state needs no inverse rescaling. The circuit accesses directly.
For later use, define
These quantities depend on the problem parameters and on , but not on , , or when the supplied norm bounds are held fixed.
Lemma 4.1. For every , set . Then Along the truncated trajectory in (34), for all and . Moreover, the truncated update is uniformly power bounded:
We defer the proof to § 11.
The sparse history system
Having constructed a sparse realization of the discrete Carleman recurrence, we now employ the history-state framework of [21]. We encode the auxiliary trajectory in a linear system, analyze its conditioning, and subsequently use terminal padding to improve the probability of extracting the final state. For our discrete-time construction, we establish conditioning bounds whose constants are independent of the truncation degree.
Define the auxiliary vectors by
Multiplying by gives
Let for and . Stacking the first equations gives
Here , with . The complexity of solving (42) by using QLSA would require the condition number of
Lemma 4.2 (History conditioning, uniformly in the truncation degree). For all , In particular, the constants in are independent of .
We defer the proof to § 12.
Remark 4.3. An alternative approach is to reformulate the discrete iteration system as a suitable continuous-time evolution and apply Schrödingerization [3]. Here, we choose to use QLSA, which applies directly to the sparse history system and exploits the conditioning bounds established above.
Terminal padding and physical-state extraction
Extraction from the original history.
Conditioned on preparing the ideal normalized solution of (42), the history state is
Since , the desired physical vector occupies the auxiliary sector at clock value . Writing , the probability of selecting this clock value and this sector is
The first factor is the probability of selecting the terminal clock, and the second is the conditional probability of selecting its physical sector.
The degree-zero Carleman coordinate remains equal to one, and preserves it in auxiliary sector . Hence . Together with from Lemma 4.1, this gives
Thus extraction from a single terminal clock carries an explicit factor, in addition to the dependence on .
Terminal padding and physical-state extraction
To remove the factor in (46), we use the terminal-state padding construction of [16, 20]. Introduce additional blocks satisfying
These equations repeat the terminal auxiliary vector without advancing the original dynamics. The resulting unnormalized padded history vector is
In particular, contains blocks: the original auxiliary vectors followed by additional copies of the terminal vector.
The padded linear system is
where is block lower-bidiagonal, with nonzero blocks
We now extract the physical state from the normalized padded history . Let be the orthogonal projector selecting the appended labels and auxiliary sector . Every selected block contains , so
Meanwhile, orthogonality of the history labels gives
Consequently, conditioned on preparing the ideal normalized padded history, the extraction probability is
Padding therefore removes the explicit factor from the probability bound, while retaining the dependence on .
For , the normalized state after successful projection is
Discarding the history and auxiliary-label registers leaves , which equals the normalized unscaled truncated physical vector by (36).
Quantum implementation and complexity
Assumption 2 (Quantum input access). We have coherent row, column, and value oracles for , with controlled and inverse access. The parameters in Assumption 1 are known. For , a unitary prepares .
Lemma 4.4 (Preparation of the padded history). Under Assumption 2, set The padded matrix satisfies For , a coherent QLSA prepares an -approximation in vector norm to with constant heralded success probability, using queries to the coefficient oracles and a unitary preparing . Each use of requires at most controlled calls to , and none when .
The proof is provided in § 13.
Theorem 4.5 (Quantum preparation of the physical state). Suppose ass: main,ass:hs-access hold. Fix , , and a known lower bound . Choose as in (32), and set There is an algorithm with success probability at least whose conditional output satisfies Its query complexity is to the coefficient oracles and , including controlled and inverse queries. The number of queries is , and is zero when .
The proof is provided in § 14.
The lower bound is an additional input promise. For fixed stability parameters and , the query bound is linear in . The output encodes the direction of . Classical readout requires additional estimation.
Remark 4.6. To the best of our knowledge, recent works [10, 9] improve the sparsity dependence of the QLSA query complexity from linear in to proportional to .
Numerical Experiments
This section presents numerical evidence for the convergence of the truncated Carleman embedding.
We first consider the one-dimensional quadratic map
The map in (57) has two fixed points, and . The fixed point is stable, whereas is unstable. In particular, for the initial conditions considered below, the iterates converge to rather than .
In Figure 1, we consider
Figure 1a shows that the Carleman truncation error decreases as the truncation level increases. The y-axis plots the maximum of absolute error over all iteration . Moreover, Figure 1b shows that, at truncation level , the Carleman trajectories corresponding to these initial conditions approach the stable fixed point .

(a) Carleman truncation error versus truncation level .

(b) Trajectories from the finite Carleman system toward the fixed point with truncation level .
Figure 1. Numerical results for the discrete Carleman approximation.
We next consider a three-dimensional example from [11]. Its discrete iteration is
where
We set and , and initialize the iteration at . These parameters satisfy Assumption 1. Figure 2 shows the Carleman truncation error for several truncation levels .
Writing (58) as , we have , , and . Because this map contains only constant and quadratic terms, odd input-degree blocks do not contribute to the Carleman update. Consequently, truncation at levels and gives the same physical-state approximation for every . This explains why the error in Figure 2 decreases from odd to even , but remains unchanged from even to odd .

Figure 2. The Carleman truncation error versus truncation level .
Conclusion
We studied the Carleman embedding of forced quadratic discrete dynamical systems. Under explicit stability and initial-state assumptions, the degree- truncation approximates the original trajectory with an error that decreases geometrically in , uniformly over all iterations. In particular, for fixed stability parameters, a degree logarithmic in the inverse accuracy suffices, regardless of how many steps the system is evolved.
A finite Carleman lift is not automatically efficient to implement: even sparse coefficient maps can produce dense blocks when their tensor products are formed. We addressed this by representing the truncated Carleman update exactly through an auxiliary operator whose layers apply the coefficient maps one tensor factor at a time. The resulting linear system has row and column sparsities bounded independently of the truncation degree. This separates the accuracy needed for the Carleman approximation from the sparsity of the system used to compute it.
We then rescaled the auxiliary representation and assembled the updates into a history system. Its condition number grows as , with constants independent of the truncation degree. Combined with the uniform error bound, this gives a quantum algorithm for preparing a state close to the normalized th iterate. Under the stated coherent-access assumptions and a positive lower bound on the norm of that iterate, the query complexity is linear in and polylogarithmic in the inverse accuracy when the stability parameters are fixed. The result concerns state preparation. Estimating observables or recovering the full iterate classically requires additional queries. Finally, the numerical experiments illustrate the predicted decrease in truncation error for one- and three-dimensional examples.
In our work, we considered the polynomial discrete systems with focus on quadratic case. On the other hand, there are plenty of nonlinear discrete systems are not in polynomial in machine learning, optimization and physical models. Whether Carleman embedding guarantees error convergence for broader classes of functions is an interesting future direction. Extending the stability and error analysis, estimating the preparation and measurement cost will also help establish end to end cost.
Acknowledgments
The authors gratefully acknowledge support from the National Science Foundation under Grants Nos. DMS-2411120 and DMS-2552687. The authors fully acknowledge the use of LLM for polishing the language and implementing the numerical results.
Proof of Theorem 2.1
Proof. Define
Under Assumption 1, we know . Thus, to find the fixed point of , we have
Here , . . By triangular inequality, we have
Note that for nonnegative , thus is increasing for . Therefore, if ,
The last inequality follows from . Since , we conclude that for all .
For any , let
for some coefficients . Since and are upper norm bounds of and , for all . Thus,
Define
Then for ,
For , one has
Define We assume that for every as the induction hypothesis. When , then
For the case where ,
By induction, we know for every ,
Take , we obtain
◻
Proof of Lemma 3.1
Proof. Fix an arbitrary , and let be the unique solution of
The block equations give
Using (28), this becomes
We claim that
We prove (61) by induction on , simultaneously for all . For , the empty tensor product is the identity, and also , thus (61) holds for every . Now suppose (61) holds at layer as induction hypothesis for every . Substituting it into (60) yields
By Kronecker product properties,
Furthermore, all are nonnegative, so
The outer cutoff is therefore redundant, and the resulting sum is exactly (61). This proves the claim by induction.
Taking and , and grouping terms by , gives
Also, . Thus
Note that is arbitrary, so . ◻
Proof of Lemma 3.2
Proof. Recall that , , and . The nonzero blocks of are
where , , and .
Taking the adjoint exchanges row and column sparsity. Tensoring with identity matrices preserves the maximum number of nonzero entries in each row and column. Thus the blocks corresponding to have row and column sparsity bounded by , respectively. For , this follows because has at most nonzero entries in total.
Fix a source sector . For each , there is at most one destination sector,
Hence each block column of contains at most one block of each type. Every scalar column of therefore has at most nonzero entries.
Similarly, for a fixed destination sector and a fixed , the only possible source sector is
Thus each block row of contains at most one block of each type, and every scalar row of has at most nonzero entries.
The same row and column bounds hold for . Since changes the layer index, its diagonal is zero. Adding therefore contributes exactly one additional nonzero entry to each row and column, proving (31). ◻
Proof of Lemma 4.1
Proof. For , let contain precisely the blocks of involving . By eq:sparse-Q,eq:sparse-C, these blocks are
where and . For each fixed , distinct source sectors map to distinct destination sectors. Orthogonality of these sectors and multiplicativity of the operator norm under tensor products give
Consequently, using (33),
Since , we obtain
Moreover, , so
Therefore,
Next, is an isometry into layer zero, while increases the layer index by one. Thus, for any , the summands in
belong to mutually orthogonal layers. Hence
Taking the supremum over unit vectors proves , completing (38).
To prove (39), define
Since and ,
For , write
The tensor-product formula (4), applied to the rescaled coefficients, gives
Here denotes the corresponding rescaled Carleman block.
We prove by induction on , simultaneously for . The initial condition in (34) gives
and the degree-zero coordinate remains equal to one. Assuming the bounds hold at time , we obtain
The term uses and . Thus the blockwise bound holds for every . Orthogonality of the degree blocks now yields
Combining this with gives
which proves (39).
Finally, we establish the uniform bound from (40). Since , any vector satisfying for all obeys
The degree-zero block is unchanged and also has norm at most . Starting with and iterating this argument gives
Therefore,
Thus for every , and the same bound holds for because . All bounds are uniform in . ◻
Proof of Lemma 4.2
Proof. Write . Substituting gives
The first summand of has range in positive auxiliary layers, and the second has range in layer zero because . These ranges are orthogonal. Since and ,
Thus . Applying the triangle inequality to now gives
Now we bound the inverse norm, . Set . Then
Since , the second factor has inverse . Reversing the factors therefore yields
The recovery identity says . Starting with , induction gives
Using Lemma 4.1 and , we obtain
For the bound is . Taking norms in (62) and using gives
Multiplying by the preceding norm bound proves the upper bound on .
Let be the unit vector in the scalar sector , and solve . The scalar row of is the identity row, and . The scalar equations are therefore
so by induction. The squared norm of the right-hand side is , whereas . Consequently,
Every diagonal entry of is one, so . The definition of the condition number proves the lower bound. ◻
Proof of Lemma 4.4
Proof. The diagonal and subdiagonal parts of have norms at most and , respectively. Writing , forward substitution shows that every nonzero block of is either or . The estimates in the proof of Lemma 4.2 bound these blocks by . Their block row and column sums are at most , proving (53).
By Lemma 3.2 and the identity-copy construction, has row and column sparsity at most . Its entries have magnitude at most one, and its sparse-access oracles require coefficient queries. The sparse block-encoding construction of [24] therefore encodes . The Hermitian dilation
satisfies
The claimed solver complexity follows from [28 Theorem 11], with measurements deferred to coherent success flags. ◻
Proof of Theorem 4.5
Proof. By Theorem 2.1 and the choice of ,
Thus (50) gives . The inequality
bounds the normalized truncation error by .
Apply Lemma 4.4 with . Projection and normalization introduce error at most
Moreover, the approximate projection succeeds with probability at least . Including the solver flag, the joint success probability is therefore . Fixed-point amplitude amplification [25] raises it to at least using coherent solver calls, proving (56).
By (51) and (36), the ideal projected physical state is . Trace distance is bounded by the corresponding vector error and cannot increase under discarding auxiliary registers. The two error contributions therefore sum to less than , proving the claim. ◻
References
- [3]Jin, S., & Liu, N. (2024). Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 480(2291), 20230370. https://doi.org/10.1098/rspa.2023.0370
- [4]Pruekprasert, S., Takisaka, T., Eberhart, C., Cetinkaya, A., & Dubut, J. (2020). Moment Propagation of Discrete-Time Stochastic Polynomial Systems using Truncated Carleman Linearization. IFAC-PapersOnLine, 53(2), 14462–14469. https://doi.org/10.1016/j.ifacol.2020.12.1447
- [5]Pruekprasert, S., Dubut, J., Takisaka, T., Eberhart, C., & Cetinkaya, A. (2024). Moment propagation of polynomial systems through Carleman linearization for probabilistic safety analysis. Automatica, 160, 111441. https://doi.org/10.1016/j.automatica.2023.111441
- [6]Myszkowski, M. (2022). Carleman Linearization and Systems of Arbitrary Depth Polynomial Recursions. Advances in Linear Algebra & Matrix Theory, 12(1), 1–23. https://doi.org/10.4236/alamt.2022.121001
- [7]Bai, S., Kolter, J. Z., & Koltun, V. (2019). Deep Equilibrium Models. Advances in Neural Information Processing Systems, 32. https://proceedings.neurips.cc/paper/2019/hash/01386bd6d8e091c2ab4c7c7de644d37b-Abstract.htmlproceedings.neurips.cc/paper/2019/hash/01386bd6d8e091c2ab4c7c7de644d37b-Abstract.html
- [8]Bai, S., Koltun, V., & Kolter, J. Z. (2021). Stabilizing Equilibrium Models by Jacobian Regularization. Proceedings of the 38th International Conference on Machine Learning, 139, 554–565. https://proceedings.mlr.press/v139/bai21b.htmlproceedings.mlr.press/v139/bai21b.html
- [9]Berry, D. W., Rawat, A., Simon, S., & Low, G. H. (2026). Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers. https://arxiv.org/abs/2610.02939
- [10]Bravo-Prieto, C., Harrow, A. W., & Kothari, R. (2026). An Optimal Quantum Linear Systems Algorithm. https://arxiv.org/abs/2609.35660
- [11]Gleich, D. F., Lim, L.-H., & Yu, Y. (2015). Multilinear PageRank. SIAM Journal on Matrix Analysis and Applications, 36(4), 1507–1541. https://doi.org/10.1137/140985160
- [12]Lee, J. D., Simchowitz, M., Jordan, M. I., & Recht, B. (2016). Gradient Descent Only Converges to Minimizers. 29th Annual Conference on Learning Theory, 49, 1246–1257. https://proceedings.mlr.press/v49/lee16.htmlproceedings.mlr.press/v49/lee16.html
- [13]Pascanu, R., Mikolov, T., & Bengio, Y. (2013). On the difficulty of training recurrent neural networks. Proceedings of the 30th International Conference on Machine Learning, 28(3), 1310–1318. https://proceedings.mlr.press/v28/pascanu13.htmlproceedings.mlr.press/v28/pascanu13.html
- [14]Carleman, T. (1932). Application de la théorie des équations intégrales linéaires aux systèmes d'équations différentielles non linéaires. Acta Mathematica, 59, 63–87. https://doi.org/10.1007/BF02546499
- [15]Harrow, A. W., Hassidim, A., & Lloyd, S. (2009). Quantum Algorithm for Linear Systems of Equations. Physical Review Letters, 103, 150502. https://doi.org/10.1103/PhysRevLett.103.150502
- [16]Berry, D. W., Childs, A. M., Ostrander, A., & Wang, G. (2017). Quantum Algorithm for Linear Differential Equations with Exponentially Improved Dependence on Precision. Communications in Mathematical Physics, 356, 1057–1081. https://doi.org/10.1007/s00220-017-3002-y
- [17]Lloyd, S., De Palma, G., Gokler, C., Kiani, B., Liu, Z.-W., Marvian, M., Tennie, F., & Palmer, T. (2020). Quantum algorithm for nonlinear differential equations. https://arxiv.org/abs/2011.06571
- [18]Joseph, I. (2020). Koopman--von Neumann approach to quantum simulation of nonlinear classical dynamics. Physical Review Research, 2, 043102. https://doi.org/10.1103/PhysRevResearch.2.043102
- [19]Berkolaiko, G., Rabinovich, S., & Havlin, S. (1998). Analysis of Carleman Representation of Analytical Recursions. Journal of Mathematical Analysis and Applications, 224(1), 81–90. https://doi.org/10.1006/jmaa.1998.5986
- [20]Liu, J.-P., Kolden, H. Ø., Krovi, H. K., Loureiro, N. F., Trivisa, K., & Childs, A. M. (2021). Efficient quantum algorithm for dissipative nonlinear differential equations. Proceedings of the National Academy of Sciences, 118, e2026805118. https://doi.org/10.1073/pnas.2026805118
- [21]Krovi, H. (2023). Improved quantum algorithms for linear and nonlinear differential equations. Quantum, 7, 913. https://doi.org/10.22331/q-2023-02-02-913
- [22]Liu, J., Liu, M., Liu, J.-P., Ye, Z., Wang, Y., Alexeev, Y., Eisert, J., & Jiang, L. (2024). Towards provably efficient quantum algorithms for large-scale machine-learning models. Nature Communications, 15, 434. https://doi.org/10.1038/s41467-023-43957-x
- [23]Jennings, D., Korzekwa, K., Lostaglio, M., Ashworth, R., Marsili, E., & Rolston, S. (2026). End-to-End Quantum Algorithm for Nonlinear Fluid Dynamics with Bounded Quantum Advantage. PRX Quantum, 7(3), 033060. https://doi.org/10.1103/xysy-q3fp
- [24]Gilyén, A., Su, Y., Low, G. H., & Wiebe, N. (2019). Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 193–204. https://doi.org/10.1145/3313276.3316366
- [25]Yoder, T. J., Low, G. H., & Chuang, I. L. (2014). Fixed-Point Quantum Search with an Optimal Number of Queries. Physical Review Letters, 113(21), 210501. https://doi.org/10.1103/PhysRevLett.113.210501
- [26]Berry, D. W. (2014). High-order quantum algorithm for solving linear differential equations. Journal of Physics A: Mathematical and Theoretical, 47(10), 105301. https://doi.org/10.1088/1751-8113/47/10/105301
- [27]Childs, A. M., & Liu, J.-P. (2020). Quantum spectral methods for differential equations. Communications in Mathematical Physics, 375(2), 1427–1457. https://doi.org/10.1007/s00220-020-03699-z
- [28]Costa, P. C. S., An, D., Sanders, Y. R., Su, Y., Babbush, R., & Berry, D. W. (2022). Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem. PRX Quantum, 3, 040303. https://doi.org/10.1103/PRXQuantum.3.040303
- [29]May, R. M. (1976). Simple mathematical models with very complicated dynamics. Nature, 261, 459–467. https://doi.org/10.1038/261459a0
- [30]Xue, C., Wu, Y.-C., & Guo, G.-P. (2021). Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations. New Journal of Physics, 23, 123035. https://doi.org/10.1088/1367-2630/ac3eff
- [31]Xue, C., Xu, X.-F., Wu, Y.-C., & Guo, G.-P. (2022). Quantum algorithm for solving a quadratic nonlinear system of equations. Physical Review A, 106, 032427. https://doi.org/10.1103/PhysRevA.106.032427
- [32]Childs, A. M., Kothari, R., & Somma, R. D. (2017). Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision. SIAM Journal on Computing, 46(6), 1920–1950. https://doi.org/10.1137/16M1087072