betaFeedback

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 nnth 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 nn 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 xn+1=F(xn)\bm x_{n+1}=F(\bm x_n). 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 FF 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 1,x,x⊗2,…1,\bm x,\bm x^{\otimes2},\ldots, and expand their updates under xn+1=F(xn)\bm x_{n+1}=F(\bm x_n) 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 nnth 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 FF, including terms absent from a continuous-time Carleman generator. Moreover, sparse coefficients need not give a sparse truncated update: for F(x)=AxF(\bm x)=A\bm x, its degree-NN block is A⊗NA^{\otimes N}, whose row sparsity can grow as sANs_A^N if AA has row sparsity sAs_A. 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

xn+1=f+Axn+Bxn⊗xn.\bm x_{n+1}=\bm f+A\bm x_n+B\bm x_n\otimes \bm x_n.

The Carleman lift collects the tensor powers of the state into

Xn=(1,xn,xn⊗2,…)T,Xn+1=LXn.\bm X_n=(1,\bm x_n,\bm x_n^{\otimes2},\ldots)^T, \qquad \bm X_{n+1}=L\bm X_n.

Writing F0=fF_0=\bm f, F1=AF_1=A, and F2=BF_2=B, the blocks of LL are

Lj,k=∑ℓ1,…,ℓj∈{0,1,2}ℓ1+⋯+ℓj=kFℓ1⊗⋯⊗Fℓj,j≥1, k≥0,L_{j,k} =\sum_{\substack{\ell_1,\ldots,\ell_j\in\{0,1,2\}\\ \ell_1+\cdots+\ell_j=k}} F_{\ell_1}\otimes\cdots\otimes F_{\ell_j}, \qquad j\ge1,\ k\ge0,

with L0,0=1L_{0,0}=1 and L0,k=0L_{0,k}=0 for k≥1k\ge1. Retaining degrees 0,…,N0,\ldots,N defines

LN=(Lj,k)j,k=0N,yn+1(N)=LNyn(N),y0(N)=(1,x0,…,x0⊗N)⊤.L_N=(L_{j,k})_{j,k=0}^{N}, \qquad \bm y_{n+1}^{(N)}=L_N\bm y_n^{(N)}, \qquad \bm y_0^{(N)} =(1,\bm x_0,\ldots,\bm x_0^{\otimes N})^\top.

The degree-zero coordinate remains one, and the degree-one block yn,1(N)\bm y_{n,1}^{(N)} approximates xn\bm x_n. We establish the following results.

  1. Uniform truncation error. Under the stability and initial-state assumptions in Assumption 1, the degree-one block yn,1(N)\bm y_{n,1}^{(N)} of the truncated lift satisfies

    sup⁡n≥0∥xn−yn,1(N)∥≤ρRN,0≤R<1.\sup_{n\ge0}\left\|\bm x_n-\bm y_{n,1}^{(N)}\right\| \le \rho R^N,\qquad 0\le R<1.

    For fixed parameters with 0<R<10<R<1, a truncation degree N=O(log⁡(1/ε))N=O(\log(1/\varepsilon)) gives error at most ε\varepsilon independently of the iteration count.

  2. Sparse realization of the lifted update. We construct a nilpotent auxiliary operator CC and embeddings Ein⁡,Eout⁡E_{\operatorname{in}},E_{\operatorname{out}} for which the truncated Carleman matrix has the exact representation

    LN=Ein⁡†D−1Eout⁡,D=I−C†.L_N=E_{\operatorname{in}}^\dag D^{-1}E_{\operatorname{out}},\qquad D=I-C^\dag.

    When f\bm f has at most sfs_f nonzeros and the row and column sparsities of A,BA,B are bounded by sA,sBs_A,s_B, each row and column of DD has at most 1+sf+sA+sB1+s_f+s_A+s_B nonzeros, independent of NN. We also bound ∥D−1∥\left\|D^{-1}\right\| and its condition number.

  3. History state QLSA. After rescaling, the first nn truncated updates form a sparse linear system

    A~n=In⊗D~−Sn⊗P,\widetilde{\mathcal A}_n =I_n\otimes\widetilde D-S_n\otimes P,

    where

    Sn=∑t=0n−2∣t+1⟩⟨t∣,P=Eout⁡Ein⁡†.S_n=\sum_{t=0}^{n-2}\ket{t+1}\bra{t}, \qquad P=E_{\operatorname{out}}E_{\operatorname{in}}^\dag.

    We prove κ(A~n)=Θ(n)\kappa(\widetilde{\mathcal A}_n)=\Theta(n) with constants independent of NN. Under coherent sparse-access and input-state assumptions, the padded history system yields an algorithm for preparing a state close to xn/∥xn∥\bm x_n/\left\|\bm x_n\right\|. Its cost also accounts for output extraction and a lower bound on ∥xn∥\left\|\bm x_n\right\|.

Combining the uniform truncation bound with the sparse history formulation, we obtain a quantum algorithm for preparing the normalized nnth iterate. Under coherent input-access assumptions and a known lower bound 0<ξ≤∥xn∥0<\xi\le\|\bm x_n\|, the algorithm achieves trace-distance error at most ε\varepsilon with constant success probability, using

O ⁣(snKrΓlog⁡Γε),Γ=2rMrξ,O\!\left(snK_r\Gamma\log\frac{\Gamma}{\varepsilon}\right), \qquad \Gamma=\frac{2rM_r}{\xi},

coefficient-oracle and right-hand-side preparation queries. Here ss bounds the sparsity, while KrK_r and MrM_r depend on the stability parameters and rescaling radius. For fixed parameters and ξ\xi, the query complexity is linear in the iteration count. Possible improvements of the sparsity dependence from ss to s\sqrt{s} are discussed in Remark 4.6.

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, ∥⋅∥\|\cdot\| denotes the Euclidean norm for vectors and the induced operator norm for matrices. ∥⋅∥1\|\cdot\|_1 denotes the trace norm for matrices. For an invertible matrix MM, we write κ(M)=∥M∥∥M−1∥\kappa(M)=\|M\|\|M^{-1}\| for its condition number. The superscripts TT and †\dagger denote the transpose and conjugate transpose, respectively. We use ⊗\otimes for the standard Kronecker product and adopt the convention x⊗0=1\bm x^{\otimes 0}=1. The symbols IkI_k and IHI_{\mathcal H} denote the identity on Ck\mathbb C^k and H\mathcal H, respectively. N0\mathbb{N}_0 denotes the set of nonnegative integers. All vectors are in bold font.

Mathematical Formulation

Problem Setup

We consider discrete quadratic iteration

xn+1=f+Axn+Bxn⊗xn,x0∈Cd,\begin{equation} \bm x_{n+1} = \bm f + A\bm x_n + B \bm x_n \otimes\bm x_n, \qquad \bm x_0 \in\mathbb{C}^d, \tag*{(1)} \end{equation}

for any n∈N0n\in\mathbb{N}_0, where xn∈Cd\bm x_n\in \mathbb{C}^d, f∈Cd\bm f\in \mathbb{C}^d, A:Cd→CdA: \mathbb{C}^d\rightarrow\mathbb{C}^d and B:Cd2→CdB: \mathbb{C}^{d^2}\rightarrow\mathbb{C}^d.

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 ∥A∥≤α<1\left\|A\right\|\le \alpha<1 and ∥B∥≤β\left\|B\right\|\le\beta, and the known forcing norm is c=∥f∥c=\left\|\bm f\right\|, with β>0\beta>0, Δ=(1−α)2−4βc>0,r±=1−α±Δ2β,u:=∥x0∥<r+. \Delta=(1-\alpha)^2-4\beta c>0,\qquad r_\pm=\frac{1-\alpha\pm\sqrt\Delta}{2\beta},\qquad u:=\left\|\bm x_0\right\|<r_+.

Carleman embedding replaces the nonlinear iteration by a linear evolution of all tensor powers of the state. Let H=CdH=\mathbb C^d and adopt the convention x⊗0=1\bm x^{\otimes 0}=1. Define

F0=f,F1=A,F2=B,\begin{equation} F_0=\bm f,\qquad F_1=A,\qquad F_2=B, \tag*{(3)} \end{equation}

where Fℓ:H⊗ℓ→HF_\ell:H^{\otimes\ell}\rightarrow H. For j≥1j\ge1, set

Lj,k:=∑ℓ1,…,ℓj∈{0,1,2}ℓ1+⋯+ℓj=kFℓ1⊗⋯⊗Fℓj,0≤k≤2j,\begin{equation} L_{j,k} := \sum_{\substack{\ell_1,\ldots,\ell_j\in\{0,1,2\}\\ \ell_1+\cdots+\ell_j=k}} F_{\ell_1}\otimes\cdots\otimes F_{\ell_j}, \qquad 0\le k\le 2j, \tag*{(4)} \end{equation}

and set Lj,k=0L_{j,k}=0 for k>2jk>2j. Each block Lj,k:H⊗k→H⊗jL_{j,k}:H^{\otimes k}\rightarrow H^{\otimes j} collects the terms of input degree kk in the expansion

xn+1⊗j=(f+Axn+Bxn⊗2)⊗j=∑k=02jLj,kxn⊗k.\begin{equation} \bm x_{n+1}^{\otimes j} = \left(\bm f+A\bm x_n+B\bm x_n^{\otimes2}\right)^{\otimes j} = \sum_{k=0}^{2j}L_{j,k}\bm x_n^{\otimes k}. \tag*{(5)} \end{equation}

In particular, L1,0=fL_{1,0}=\bm f, L1,1=AL_{1,1}=A, L1,2=BL_{1,2}=B, and Lj,0=f⊗jL_{j,0}=\bm f^{\otimes j}.

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.

Xn:=(1xnxn⊗2xn⊗3⋮).\begin{equation} \bm X_n := \begin{pmatrix} 1\\ \bm x_n\\ \bm x_n^{\otimes2}\\ \bm x_n^{\otimes3}\\ \vdots \end{pmatrix}. \tag*{(6)} \end{equation}

Setting L0,0=1L_{0,0}=1 and L0,k=0L_{0,k}=0 for k≥1k\ge1, the exact nonlinear iteration becomes the linear recurrence

Xn+1=LXn,L=(10000⋯fAB00⋯L2,0L2,1L2,2L2,3L2,4⋯L3,0L3,1L3,2L3,3L3,4⋯⋮⋮⋮⋮⋮⋱).\begin{equation} \bm X_{n+1}=L\bm X_n, \qquad L= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & \cdots\\ \bm f & A & B & 0 & 0 & \cdots\\ L_{2,0} & L_{2,1} & L_{2,2} & L_{2,3} & L_{2,4} & \cdots\\ L_{3,0} & L_{3,1} & L_{3,2} & L_{3,3} & L_{3,4} & \cdots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{pmatrix}. \tag*{(7)} \end{equation}

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 N≥1N\ge1 and retain

Xn(N):=(1xn⋮xn⊗N),LN:=(Lj,k)0≤j,k≤N.\begin{equation} \bm X_n^{(N)} := \begin{pmatrix} 1\\ \bm x_n\\ \vdots\\ \bm x_n^{\otimes N} \end{pmatrix}, \qquad L_N:=(L_{j,k})_{0\le j,k\le N}. \tag*{(8)} \end{equation}

The matrix LNL_N has dimension ∑j=0Ndj\sum_{j=0}^{N}d^j. Splitting (5) into retained and omitted input degrees gives the exact identity

Xn+1(N)=LNXn(N)+τn(N),\begin{equation} \bm X_{n+1}^{(N)} = L_N\bm X_n^{(N)}+\bm\tau_n^{(N)}, \tag*{(9)} \end{equation}

where

τn,0(N)=0,τn,j(N):=∑k=N+12jLj,kxn⊗k,1≤j≤N.\begin{equation} \tau_{n,0}^{(N)}=0, \qquad \bm\tau_{n,j}^{(N)} := \sum_{k=N+1}^{2j}L_{j,k}\bm x_n^{\otimes k}, \qquad 1\le j\le N. \tag*{(10)} \end{equation}

An empty sum is zero. Thus τn,j(N)=0\bm\tau_{n,j}^{(N)}=0 whenever 2j≤N2j\le N.

(9) is exact, but it is not a closed linear recurrence for the retained variables: the remainder contains tensor powers of degree greater than NN. (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

yn+1(N)=LNyn(N),y0(N)=X0(N).\begin{equation} \bm y_{n+1}^{(N)}=L_N\bm y_n^{(N)}, \qquad \bm y_0^{(N)}=\bm X_0^{(N)}. \tag*{(11)} \end{equation}

The degree-zero coordinate remains exactly one. Consequently, the positive-degree equations are affine:

yn+1,j(N)=f⊗j+∑k=1min⁡(N,2j)Lj,kyn,k(N),1≤j≤N.\begin{equation} \bm y_{n+1,j}^{(N)} = \bm f^{\otimes j} + \sum_{k=1}^{\min(N,2j)} L_{j,k}\bm y_{n,k}^{(N)}, \qquad 1\le j\le N. \tag*{(12)} \end{equation}

The approximation to the original state is the degree-one block yn,1(N)\bm y_{n,1}^{(N)}.

To distinguish the omitted terms from the accumulated approximation error, define

ηn:=Xn(N)−yn(N).\begin{equation} \bm \eta_n := \bm X_n^{(N)}-\bm y_n^{(N)}. \tag*{(13)} \end{equation}

Subtracting (11) from (9) yields

ηn+1=LNηn+τn(N),η0=0.\begin{equation} \bm \eta_{n+1} = L_N\bm \eta_n+\bm\tau_n^{(N)}, \qquad \bm \eta_0=0. \tag*{(14)} \end{equation}

Since ηn,0=0\bm \eta_{n,0}=0, its positive-degree blocks satisfy

ηn+1,j=∑k=1min⁡(N,2j)Lj,kηn,k+∑k=N+12jLj,kxn⊗k.\begin{equation} \bm \eta_{n+1,j} = \sum_{k=1}^{\min(N,2j)} L_{j,k}\bm \eta_{n,k} + \sum_{k=N+1}^{2j} L_{j,k}\bm x_n^{\otimes k}. \tag*{(15)} \end{equation}

The second sum introduces truncation error only when 2j>N2j>N, while the first sum propagates existing errors between retained degrees. Therefore lower-degree errors, including the error in the physical block j=1j=1, 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-NN.

Theorem 2.1 (Uniform geometric convergence). Under Assumption 1, let ρ=max⁡{u,r−}\rho=\max\{u,r_-\} and R=ρ/r+<1R=\rho/r_+<1. For every N∈NN\in\mathbb{N}, n≥0n\ge0, and 1≤j≤N1\le j\le N, ∥xn⊗j−yn,j(N)∥≤r+jRN+1. \left\|\bm x_n^{\otimes j}-\bm y^{(N)}_{n,j}\right\| \le r_+^jR^{N+1}. In particular, sup⁡n≥0∥xn−yn,1(N)∥≤ρRN. \sup_{n\ge0}\left\|\bm x_n-\bm y^{(N)}_{n,1}\right\|\le\rho R^N.

We defer the proof to § 8.

Remark 2.2. The formal procedure extends to polynomial maps xn+1=∑ℓ=0pFℓxn⊗ℓ\bm x_{n+1}=\sum_{\ell=0}^{p}F_\ell\bm x_n^{\otimes\ell} of arbitrary finite degree. Define the scalar majorant h(s)=∑ℓ=0paℓsℓh(s)=\sum_{\ell=0}^{p}a_\ell s^\ell, where aℓ≥∥Fℓ∥a_\ell\ge\left\|F_\ell\right\|. If there exist 0<ρ<r0<\rho<r such that ∥x0∥≤ρ\left\|\bm x_0\right\|\le\rho, h(ρ)≤ρh(\rho)\le\rho, and h(r)≤rh(r)\le r, then the same coefficient-majorization argument yields sup⁡n≥0∥xn−yn,1(N)∥≤ρ(ρr)N, \sup_{n\ge0}\left\|\bm x_n-\bm y_{n,1}^{(N)}\right\| \le \rho\left(\frac{\rho}{r}\right)^N, where y(N)\bm y^{(N)} is the degree-NN Carleman truncation initialized by the tensor powers of x0\bm x_0. Thus, for fixed ρ\rho and rr, a truncation degree N=O(log⁡(1/ε))N=O(\log(1/\varepsilon)) suffices for error at most ε\varepsilon, uniformly in the number of iterations. When p=2p=2, taking r=r+r=r_+ and R=ρ/r+R=\rho/r_+ recovers (17).

From now on, we use y\bm y to denote y(N)\bm y^{(N)} for simplicity.

Sparse Realization of the Truncated Carleman Embedding

Recall the quadratic iteration (1),

xn+1=F(xn)=f+Axn+Bxn⊗2,xn∈H:=Cd.\begin{equation} \bm x_{n+1}=F(\bm x_n)=\bm f+A\bm x_n+B\bm x_n^{\otimes 2}, \qquad \bm x_n\in \mathcal{H}:=\mathbb C^d. \tag*{(19)} \end{equation}

We use Euclidean vector norms and their induced operator norms throughout. Assume that AA and BB have at most sAs_A and sBs_B nonzero entries in every row and column, respectively, and that f\bm f has at most sfs_f nonzero entries.

The sparsity of these coefficients does not imply sparsity of the discrete Carleman matrix. Even if f=B=0\bm f=B=0, the degree-NN block is A⊗NA^{\otimes N}, whose row sparsity can be sANs_A^N. 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 N=2N=2

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 N=2N=2. Consider a scalar example,

xn+1=F(xn)=f+axn+bxn2,f,a,b∈R.\begin{equation} x_{n+1}=F(x_n)= f+ax_n+bx_n^2, \quad f,a,b\in\mathbb{R}. \tag*{(20)} \end{equation}

Expanding F(x)2F(x)^2, one has

F(x)2=f2+2afx+(a2+2bf)x2+2abx3+b2x4.\begin{equation} F(x)^2 = f^2+ 2afx+ (a^2+2bf)x^2 + 2abx^3 + b^2x^4. \tag*{(21)} \end{equation}

The Carleman matrix at truncation level N=2N=2 is

L2=(100fabf22afa2+2bf).\begin{equation} L_2 = \begin{pmatrix}1 & 0 & 0 \\ f & a & b \\ f^2 & 2af & a^2+2bf \\ \end{pmatrix}. \tag*{(22)} \end{equation}

To expand the power of F(x)F(x) one factor at a time, introduce the auxiliary expressions xpF(x)ℓx^pF(x)^\ell, where pp records the accumulated input degree and ℓ\ell records the number of factors remaining to be expanded,

xpF(x)ℓ=fxpF(x)ℓ−1+axp+1F(x)ℓ−1+bxp+2F(x)ℓ−1.x^pF(x)^\ell = fx^p F(x)^{\ell-1} + ax^{p+1}F(x)^{\ell-1}+bx^{p+2} F(x)^{\ell-1}.

We then define

Q=(f00af0baf),C=(0Q000Q000),D=I−CT=(I300−QTI300−QTI3).\begin{equation} Q = \begin{pmatrix}f & 0 & 0 \\ a & f & 0\\ b & a & f \\ \end{pmatrix}, \quad C= \begin{pmatrix}0 & Q & 0 \\ 0 & 0 & Q \\ 0 & 0 & 0 \\ \end{pmatrix}, \quad D = I-C^T = \begin{pmatrix}I_3 & 0 & 0 \\ -Q^T & I_3 & 0 \\ 0 & -Q^T & I_3 \\ \end{pmatrix}. \tag*{(23)} \end{equation}

This simple example demonstrates that the sparsity is not guaranteed after Carleman embedding. We see that QQ and L2L_2 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 Ein⁡E_{\operatorname{in}} and Eout⁡E_{\operatorname{out}} as

Ein⁡=I3⊗e0,Eout⁡=e0⊗I3,e0=(100)T.\begin{equation} E_{\operatorname{in}}= I_3\otimes \bm e_0,\quad E_{\operatorname{out}}= \bm e_0\otimes I_3, \quad \bm e_0 = \begin{pmatrix}1 & 0 & 0 \\ \end{pmatrix}^T. \tag*{(24)} \end{equation}

For any fixed vector y∈R3\bm y\in\mathbb{R}^{3}, we set the auxiliary vector

w=(w(0)w(1)w(2)),w(ℓ)=(w0,ℓw1,ℓw2,ℓ).\begin{equation} \bm w = \begin{pmatrix}\bm w^{(0)} \\ \bm w^{(1)} \\ \bm w^{(2)} \\ \end{pmatrix},\quad \bm w^{(\ell)} = \begin{pmatrix}w_{0,\ell}\\ w_{1,\ell}\\ w_{2,\ell} \\ \end{pmatrix}. \tag*{(25)} \end{equation}

to solve Dw=Eout⁡yD\bm w = E_{\operatorname{out}}\bm y. Then w(0)=y\bm w^{(0)} = \bm y, w(1)=QTy\bm w^{(1)} = Q^T \bm y, w(2)=QTw(1).\bm w^{(2)} =Q^T \bm w^{(1)}. Therefore,

Ein⁡†w=L2y.\begin{equation} E_{\operatorname{in}}^\dag \bm w = L_2\bm y. \tag*{(26)} \end{equation}

We conclude that

L2=Ein⁡†(I−C†)−1Eout⁡.\begin{equation} L_2 = E_{\operatorname{in}}^\dag (I-C^\dag)^{-1} E_{\operatorname{out}}. \tag*{(27)} \end{equation}

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 L0,0=1L_{0,0}=1 and L0,k=0L_{0,k}=0 for k>0k>0. The truncated matrix LNL_N acts on the enlarged Hilbert space

VN≔⨁j=0NH⊗j.\mathcal{V}_N \coloneqq \bigoplus_{j=0}^N \mathcal{H}^{\otimes j}.

The dimension of VN\mathcal{V}_N is m=∑j=0Ndjm = \sum_{j=0}^N d^j. For each pair (p,ℓ)∈{0,⋯ ,N}2(p,\ell)\in \{0,\cdots, N\}^2, we introduce an auxiliary space H⊗(p+ℓ)\mathcal{H}^{\otimes(p+\ell)}, and we group the spaces as

Kℓ≔⨁p=0NH⊗(p+ℓ),K≔⨁ℓ=0NKℓ.\mathcal{K}_\ell \coloneqq \bigoplus_{p=0}^N \mathcal{H}^{\otimes(p+\ell)}, \quad \mathcal{K}\coloneqq \bigoplus_{\ell=0}^N \mathcal{K}_\ell.

Then dim⁡(Kℓ)=dℓm\dim(\mathcal{K}_\ell) = d^\ell m and dim⁡(K)=m2.\dim(\mathcal{K})= m^2. We order the coordinates first by ℓ\ell and then by pp:

w≔(w(0)⋮w(N)),w(ℓ)=(w0,ℓ⋮wN,ℓ),wp,ℓ∈H⊗(p+ℓ).\bm w\coloneqq\begin{pmatrix}\bm w^{(0)} \\ \vdots \\ \bm w^{(N)} \\ \end{pmatrix}, \quad \bm w^{(\ell)}=\begin{pmatrix} \bm w_{0,\ell} \\ \vdots \\ \bm w_{N,\ell} \\ \end{pmatrix}, \quad \bm w_{p,\ell}\in\mathcal{H}^{\otimes(p+\ell)}.

Here pp records the input degree already produced, and ℓ\ell records the number of factors still to be expanded. For 1≤ℓ≤N1\le\ell\le N, define Qℓ:Kℓ→Kℓ−1Q_\ell:\mathcal{K}_\ell\rightarrow\mathcal{K}_{\ell-1} through its blocks:

(Qℓ)p′,p={IH⊗p⊗Fi†⊗IH⊗(ℓ−1),p′=p+i,i∈{0,1,2},0,otherwise,0≤p,p′≤N.\begin{equation} (Q_\ell)_{p',p} = \begin{cases} I_{\mathcal{H}}^{\otimes p}\otimes F_i^\dag \otimes I_{\mathcal{H}}^{\otimes(\ell-1)}, & p'=p+i,\quad i\in\{0,1,2\},\\ 0,&\text{otherwise}, \end{cases} \qquad 0\le p,p'\le N. \tag*{(28)} \end{equation}

Thus branches with p+i>Np+i>N are omitted. Each nonzero block maps

H⊗(p+ℓ)⟶H⊗(p+i+ℓ−1),\mathcal{H}^{\otimes(p+\ell)} \longrightarrow \mathcal{H}^{\otimes(p+i+\ell-1)},

and

Qℓ∈C(dℓ−1m)×(dℓm).Q_\ell\in \mathbb C^{(d^{\ell-1}m)\times(d^\ell m)}.

Under the natural tensor identifications, we have

Qℓ=Q1⊗IH⊗(ℓ−1).Q_\ell=Q_1\otimes I_{\mathcal{H}}^{\otimes(\ell-1)}.

Define C:K→KC:\mathcal{K}\rightarrow\mathcal{K} and D:K→KD:\mathcal{K}\rightarrow\mathcal{K} by

C=(0Q10⋯000Q2⋯0⋮⋮⋱⋱⋮0⋯00QN0⋯000),D=IK−C†.\begin{equation} C= \begin{pmatrix} 0 & Q_1 & 0 & \cdots & 0\\ 0 & 0 & Q_2 & \cdots &0\\ \vdots & \vdots & \ddots & \ddots & \vdots\\ 0 & \cdots & 0 & 0 & Q_N\\ 0 & \cdots & 0 & 0 & 0 \\ \end{pmatrix}, \qquad D=I_{\mathcal{K}}-C^\dag. \tag*{(29)} \end{equation}

Notice that CC is (N+1)(N+1)-nilpotent. Hence

CN+1=0,D−1=∑s=0N(C†)s.C^{N+1}=0, \qquad D^{-1}=\sum_{s=0}^N(C^\dag)^s.

In particular, DD is invertible without any norm condition on CC.

Finally, we introduce the embeddings Eout,Ein:VN→KE_{\mathrm{out}},E_{\mathrm{in}}:\mathcal{V}_N\rightarrow\mathcal{K}

Eout=(Im0(m2−m)×m),Ein=⨁ℓ=0N(Idℓ0(m−1)dℓ×dℓ).\begin{equation} E_{\mathrm{out}} = \begin{pmatrix} I_m\\ 0_{(m^2-m)\times m} \end{pmatrix}, \qquad E_{\mathrm{in}} = \bigoplus_{\ell=0}^N \begin{pmatrix} I_{d^\ell}\\ 0_{(m-1)d^\ell\times d^\ell} \end{pmatrix}. \tag*{(30)} \end{equation}

Both matrices have dimensions m2×mm^2\times m. The map EoutE_{\mathrm{out}} inserts y\bm y into layer zero, while EinE_{\mathrm{in}} inserts yℓ\bm y_\ell into the p=0p=0 block of layer ℓ\ell. Consequently,

Ein†w=(w0,0,…,w0,N)T.E_{\mathrm{in}}^\dag\bm w=(\bm w_{0,0},\ldots,\bm w_{0,N})^T.

Lemma 3.1. The truncated Carleman matrix LNL_N can be written as LN=Ein⁡†(I−C†)−1Eout⁡. L_N = E_{\operatorname{in}}^\dag (I-C^\dag)^{-1} E_{\operatorname{out}}.

We provide the proof in § 9.

Lemma 3.2. Suppose every row and column of AA and BB has at most sAs_A and sBs_B nonzero entries, respectively, and f\bm f has at most sfs_f nonzero entries. Then every row and column of D=IK−C†D=I_{\mathcal{K}}-C^\dag has at most sD≔1+sf+sA+sB s_D\coloneqq 1+s_f+s_A+s_B nonzero entries, independently of the truncation degree NN.

We provide the proof in § 10.

Quantum Algorithms and Complexity

We use the sparse representation to prepare a quantum state proportional to xn\bm x_n at a prescribed iteration n≥1n\ge1. 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 rr such that

ρ<r<r+,a=ρr<1,q=cr+α+βr<1.\begin{equation} \rho<r<r_+,\qquad a=\frac{\rho}{r}<1,\qquad q=\frac cr+\alpha+\beta r<1. \tag*{(32)} \end{equation}

Since r−≤ρ<r+r_-\le\rho<r_+, such an rr exists and satisfies

q−1=h(r)−rr=βr(r−r−)(r−r+)<0.q-1=\frac{h(r)-r}{r} =\frac{\beta}{r}(r-r_-)(r-r_+)<0.

With zt=xt/r\bm z_t=\bm x_t/r, the original iteration becomes

zt+1=F~0+F~1zt+F~2zt⊗2,F~0=f/r,F~1=A,F~2=rB.\begin{equation} \bm z_{t+1} =\widetilde F_0+\widetilde F_1\bm z_t +\widetilde F_2\bm z_t^{\otimes2}, \qquad \widetilde F_0=\bm f/r,\quad \widetilde F_1=A,\quad \widetilde F_2=rB. \tag*{(33)} \end{equation}

Let L~N,C~\widetilde L_N,\widetilde C, and D~=IK−C~†\widetilde D=I_{\mathcal{K}}-\widetilde C^\dag be the matrices obtained by applying the construction of § 3 to these coefficients. The embeddings Ein⁡,Eout⁡E_{\operatorname{in}},E_{\operatorname{out}} and the operator P=Eout⁡Ein⁡†P=E_{\operatorname{out}}E_{\operatorname{in}}^\dag are unchanged. In particular,

L~N=Ein⁡†D~−1Eout⁡,y~t+1=L~Ny~t,y~0,j=(x0/r)⊗j.\begin{equation} \widetilde L_N=E_{\operatorname{in}}^\dag\widetilde D^{-1}E_{\operatorname{out}}, \qquad \widetilde{\bm y}_{t+1}=\widetilde L_N\widetilde{\bm y}_t, \qquad \widetilde{\bm y}_{0,j}=(\bm x_0/r)^{\otimes j}. \tag*{(34)} \end{equation}

The rescaled parameters are

(α~,β~,c~,u~)=(α,rβ,c/r,u/r).(\widetilde\alpha,\widetilde\beta,\widetilde c,\widetilde u) =(\alpha,r\beta,c/r,u/r).

Direct substitution gives

Δ~=(1−α)2−4(rβ)(c/r)=Δ,r~±=1−α±Δ2rβ=r±r,ρ~=max⁡{u/r,r−/r}=ρr,R~=ρ~r~+=R.\begin{align} \widetilde\Delta &=(1-\alpha)^2-4(r\beta)(c/r)=\Delta,\notag\\ \widetilde r_\pm &=\frac{1-\alpha\pm\sqrt\Delta}{2r\beta}=\frac{r_\pm}{r}, \qquad \widetilde\rho=\max\{u/r,r_-/r\}=\frac\rho r, \qquad \widetilde R=\frac{\widetilde\rho}{\widetilde r_+}=R. \tag*{(35)} \end{align}

Together with u~=u/r<r+/r=r~+\widetilde u=u/r<r_+/r=\widetilde r_+, these identities verify Assumption 1 for the rescaled iteration. Moreover, ρ~=a<1\widetilde\rho=a<1 and the sum of the coefficient bounds is q<1q<1.

To relate the truncated trajectories, note that F~i=ri−1Fi\widetilde F_i=r^{i-1}F_i for i=0,1,2i=0,1,2. Every tensor product contributing to Lj,kL_{j,k} has jj factors whose input degrees sum to kk, so its scale factor is rk−jr^{k-j}. Consequently, with Vr=⨁j=0Nr−jIdjV_r=\bigoplus_{j=0}^N r^{-j}I_{d^j},

L~N=VrLNVr−1,y~t=(VrLNVr−1)tVry0=Vryt.\widetilde L_N=V_rL_NV_r^{-1},\qquad \widetilde{\bm y}_t =(V_rL_NV_r^{-1})^tV_r\bm y_0=V_r\bm y_t.

In particular,

ry~t,1=yt,1,y~t,1∥y~t,1∥=yt,1∥yt,1∥\begin{equation} r\widetilde{\bm y}_{t,1}=\bm y_{t,1},\qquad \frac{\widetilde{\bm y}_{t,1}} {\left\|\widetilde{\bm y}_{t,1}\right\|} =\frac{\bm y_{t,1}}{\left\|\bm y_{t,1}\right\|} \tag*{(36)} \end{equation}

whenever the physical block is nonzero. Thus the classical approximation is recovered by multiplying by rr, while its normalized quantum state needs no inverse rescaling. The circuit accesses f/r,A,rB\bm f/r,A,rB directly.

For later use, define

δ=11−q,g=11−q2,Kr=δg2,Mr=g1−a2.\begin{equation} \delta=\frac1{1-q},\qquad g=\frac1{\sqrt{1-q^2}},\qquad K_r=\delta g^2,\qquad M_r=\frac{g}{\sqrt{1-a^2}}. \tag*{(37)} \end{equation}

These quantities depend on the problem parameters and on rr, but not on nn, NN, or dd when the supplied norm bounds are held fixed.

Lemma 4.1. For every N≥1N\ge1, set J=D~−1Eout⁡J=\widetilde D^{-1}E_{\operatorname{out}}. Then ∥C~∥≤q,∥D~∥≤1+q,∥D~−1∥≤δ,κ(D~)≤(1+q)δ,∥J∥≤g. \left\|\widetilde C\right\|\le q, \quad \left\|\widetilde D\right\|\le1+q, \quad \left\|\widetilde D^{-1}\right\|\le\delta, \quad \kappa(\widetilde D)\le(1+q)\delta, \quad \left\|J\right\|\le g. Along the truncated trajectory in (34), ∥y~t,j∥≤aj,∥y~t∥≤11−a2,∥Jy~t∥≤Mr \left\|\widetilde{\bm y}_{t,j}\right\|\le a^j, \qquad \left\|\widetilde{\bm y}_t\right\|\le\frac1{\sqrt{1-a^2}}, \qquad \left\|J\widetilde{\bm y}_t\right\|\le M_r for all t≥0t\ge0 and 0≤j≤N0\le j\le N. Moreover, the truncated update is uniformly power bounded: ∥L~Nk∥≤g∀k∈N0. \left\|\widetilde L_N^k\right\|\le g \qquad\forall k\in\mathbb{N}_0.

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

w~t=Jy~t,y~t+1=Ein⁡†w~t.\begin{equation} \widetilde{\bm w}_t=J\widetilde{\bm y}_t, \qquad \widetilde{\bm y}_{t+1}=E_{\operatorname{in}}^\dag\widetilde{\bm w}_t. \tag*{(41)} \end{equation}

Multiplying by D~\widetilde D gives

D~w~0=Eout⁡y~0,D~w~t=Eout⁡y~t=Eout⁡Ein⁡†w~t−1=Pw~t−1(t≥1).\widetilde D\widetilde{\bm w}_0=E_{\operatorname{out}}\widetilde{\bm y}_0, \qquad \widetilde D\widetilde{\bm w}_t =E_{\operatorname{out}}\widetilde{\bm y}_t =E_{\operatorname{out}}E_{\operatorname{in}}^\dag\widetilde{\bm w}_{t-1} =P\widetilde{\bm w}_{t-1}\quad(t\ge1).

Let Sn∣t⟩=∣t+1⟩S_n|t\rangle=|t+1\rangle for 0≤t<n−10\le t<n-1 and Sn∣n−1⟩=0S_n|n-1\rangle=0. Stacking the first nn equations gives

A~n(w~0⋮w~n−1)=∣0⟩⊗Eout⁡y~0,A~n=In⊗D~−Sn⊗P.\begin{equation} \widetilde{\mathcal A}_n \begin{pmatrix}\widetilde{\bm w}_0\\\vdots\\ \widetilde{\bm w}_{n-1}\end{pmatrix} =|0\rangle\otimes E_{\operatorname{out}}\widetilde{\bm y}_0, \qquad \widetilde{\mathcal A}_n =I_n\otimes\widetilde D-S_n\otimes P. \tag*{(42)} \end{equation}

Here dim⁡K=m2\dim\mathcal{K}=m^2, with m=∑j=0Ndjm=\sum_{j=0}^Nd^j. The complexity of solving (42) by using QLSA would require the condition number of A~n.\widetilde{\mathcal{A}}_n.

Lemma 4.2 (History conditioning, uniformly in the truncation degree). For all n,N≥1n,N\ge1, ∥A~n∥≤1+1+q2,∥A~n−1∥≤δ(1+(n−1)g2)≤nKr,n3≤κ(A~n)≤(1+1+q2)nKr.\begin{aligned} \left\|\widetilde{\mathcal A}_n\right\| &\le1+\sqrt{1+q^2},\\ \left\|\widetilde{\mathcal A}_n^{-1}\right\| &\le\delta\bigl(1+(n-1)g^2\bigr)\le nK_r, \\ \frac n{\sqrt3} \le\kappa(\widetilde{\mathcal A}_n) &\le\bigl(1+\sqrt{1+q^2}\bigr)nK_r. \end{aligned} In particular, the constants in κ(A~n)=Θ(n)\kappa(\widetilde{\mathcal A}_n)=\Theta(n) are independent of NN.

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

∣W⟩=1Hn∑t=0n−1∣t⟩⊗w~t,Hn=∑t=0n−1∥w~t∥2.\begin{equation} |W\rangle =\frac{1}{\sqrt{H_n}} \sum_{t=0}^{n-1}|t\rangle\otimes\widetilde{\bm w}_t, \qquad H_n=\sum_{t=0}^{n-1}\left\|\widetilde{\bm w}_t\right\|^2. \tag*{(44)} \end{equation}

Since Ein⁡†w~n−1=y~nE_{\operatorname{in}}^\dag\widetilde{\bm w}_{n-1}=\widetilde{\bm y}_n, the desired physical vector y~n,1\widetilde{\bm y}_{n,1} occupies the auxiliary sector (p,ℓ)=(0,1)(p,\ell)=(0,1) at clock value n−1n-1. Writing hn=∥y~n,1∥h_n=\left\|\widetilde{\bm y}_{n,1}\right\|, the probability of selecting this clock value and this sector is

praw=∥w~n−1∥2Hnhn2∥w~n−1∥2=hn2Hn.\begin{equation} p_{\mathrm{raw}} =\frac{\left\|\widetilde{\bm w}_{n-1}\right\|^2}{H_n} \frac{h_n^2}{\left\|\widetilde{\bm w}_{n-1}\right\|^2} =\frac{h_n^2}{H_n}. \tag*{(45)} \end{equation}

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 JJ preserves it in auxiliary sector (0,0)(0,0). Hence ∥w~t∥≥1\left\|\widetilde{\bm w}_t\right\|\ge1. Together with ∥w~t∥≤Mr\left\|\widetilde{\bm w}_t\right\|\le M_r from Lemma 4.1, this gives

n≤Hn≤nMr2,hn2nMr2≤praw≤hn2n.\begin{equation} n\le H_n\le nM_r^2, \qquad \frac{h_n^2}{nM_r^2} \le p_{\mathrm{raw}} \le\frac{h_n^2}{n}. \tag*{(46)} \end{equation}

Thus extraction from a single terminal clock carries an explicit 1/n1/n factor, in addition to the dependence on hnh_n.

Terminal padding and physical-state extraction

To remove the factor 1/n1/n in (46), we use the terminal-state padding construction of [16, 20]. Introduce nn additional blocks satisfying

v1=w~n−1,vj=vj−1,2≤j≤n.\bm v_1=\widetilde{\bm w}_{n-1}, \qquad \bm v_j=\bm v_{j-1}, \quad 2\le j\le n.

These equations repeat the terminal auxiliary vector without advancing the original dynamics. The resulting unnormalized padded history vector is

Ω=∑t=0n−1∣t⟩⊗w~t+∑t=n2n−1∣t⟩⊗w~n−1.\begin{equation} \bm\Omega =\sum_{t=0}^{n-1}|t\rangle\otimes\widetilde{\bm w}_t +\sum_{t=n}^{2n-1}|t\rangle \otimes\widetilde{\bm w}_{n-1}. \tag*{(47)} \end{equation}

In particular, Ω\bm\Omega contains 2n2n blocks: the original nn auxiliary vectors followed by nn additional copies of the terminal vector.

The padded linear system is

BnΩ=b,b=∣0⟩⊗Eout⁡y~0,\begin{equation} \mathcal B_n\bm\Omega=\bm b, \qquad \bm b=|0\rangle\otimes E_{\operatorname{out}}\widetilde{\bm y}_0, \tag*{(48)} \end{equation}

where Bn\mathcal B_n is block lower-bidiagonal, with nonzero blocks

(Bn)t,t={D~,0≤t<n,IK,n≤t<2n,(Bn)t,t−1={−P,1≤t<n,−IK,n≤t<2n.\begin{equation} (\mathcal B_n)_{t,t} =\begin{cases} \widetilde D,&0\le t<n,\\ I_{\mathcal{K}},&n\le t<2n, \end{cases} \qquad (\mathcal B_n)_{t,t-1} =\begin{cases} -P,&1\le t<n,\\ -I_{\mathcal{K}},&n\le t<2n. \end{cases} \tag*{(49)} \end{equation}

We now extract the physical state from the normalized padded history ∣Ω⟩=Ω/∥Ω∥|\Omega\rangle=\bm\Omega/\left\|\bm\Omega\right\|. Let Π\Pi be the orthogonal projector selecting the appended labels n,…,2n−1n,\ldots,2n-1 and auxiliary sector (p,ℓ)=(0,1)(p,\ell)=(0,1). Every selected block contains y~n,1\widetilde{\bm y}_{n,1}, so

ΠΩ=∑t=n2n−1∣t⟩⊗∣p=0,ℓ=1⟩⊗y~n,1,∥ΠΩ∥2=nhn2.\Pi\bm\Omega =\sum_{t=n}^{2n-1}|t\rangle \otimes|p=0,\ell=1\rangle \otimes\widetilde{\bm y}_{n,1}, \qquad \left\|\Pi\bm\Omega\right\|^2=nh_n^2.

Meanwhile, orthogonality of the history labels gives

∥Ω∥2=Hn+n∥w~n−1∥2≤2nMr2.\left\|\bm\Omega\right\|^2 =H_n+n\left\|\widetilde{\bm w}_{n-1}\right\|^2 \le 2nM_r^2.

Consequently, conditioned on preparing the ideal normalized padded history, the extraction probability is

pout=∥ΠΩ∥2∥Ω∥2=nhn2Hn+n∥w~n−1∥2≥hn22Mr2.\begin{equation} p_{\mathrm{out}} =\frac{\left\|\Pi\bm\Omega\right\|^2}{\left\|\bm\Omega\right\|^2} =\frac{nh_n^2} {H_n+n\left\|\widetilde{\bm w}_{n-1}\right\|^2} \ge\frac{h_n^2}{2M_r^2}. \tag*{(50)} \end{equation}

Padding therefore removes the explicit 1/n1/n factor from the probability bound, while retaining the dependence on hnh_n.

For hn>0h_n>0, the normalized state after successful projection is

ΠΩ∥ΠΩ∥=(1n∑t=n2n−1∣t⟩)⊗∣p=0,ℓ=1⟩⊗y~n,1hn.\begin{equation} \frac{\Pi\bm\Omega}{\left\|\Pi\bm\Omega\right\|} =\left(\frac{1}{\sqrt n} \sum_{t=n}^{2n-1}|t\rangle\right) \otimes|p=0,\ell=1\rangle \otimes\frac{\widetilde{\bm y}_{n,1}}{h_n}. \tag*{(51)} \end{equation}

Discarding the history and auxiliary-label registers leaves y~n,1/hn\widetilde{\bm y}_{n,1}/h_n, 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 f,A,B\bm f,A,B, with controlled and inverse access. The parameters in Assumption 1 are known. For u=∥x0∥>0u=\left\|\bm x_0\right\|>0, a unitary UxU_x prepares x0/u\bm x_0/u.

Lemma 4.4 (Preparation of the padded history). Under Assumption 2, set s=2+sf+sA+sB. s=2+s_f+s_A+s_B. The padded matrix satisfies ∥Bn∥≤2+q,∥Bn−1∥≤2nKr. \left\|\mathcal B_n\right\|\le2+q, \qquad \left\|\mathcal B_n^{-1}\right\|\le2nK_r. For 0<η≤1/20<\eta\le1/2, a coherent QLSA prepares an η\eta-approximation in vector norm to ∣Ω⟩=Ω∥Ω∥|\Omega\rangle=\frac{\bm\Omega}{\left\|\bm\Omega\right\|} with constant heralded success probability, using O ⁣(snKrlog⁡(1/η))O\!\left(snK_r\log(1/\eta)\right) queries to the coefficient oracles and a unitary UbU_b preparing b/∥b∥\bm b/\left\|\bm b\right\|. Each use of UbU_b requires at most NN controlled calls to UxU_x, and none when u=0u=0.

The proof is provided in § 13.

Theorem 4.5 (Quantum preparation of the physical state). Suppose ass: main,ass:hs-access hold. Fix n≥1n\ge1, 0<ε≤10<\varepsilon\le1, and a known lower bound 0<ξ≤∥xn∥0<\xi\le\left\|\bm x_n\right\|. Choose rr as in (32), and set N=max⁡{1,⌈log⁡(8ρ/(εξ))log⁡(1/R)⌉},Γ=2rMrξ. N=\max\left\{1, \left\lceil \frac{\log(8\rho/(\varepsilon\xi))} {\log(1/R)} \right\rceil\right\}, \qquad \Gamma=\frac{2rM_r}{\xi}. There is an algorithm with success probability at least 2/32/3 whose conditional output σout\sigma_{\mathrm{out}} satisfies 12∥σout−xnxn†∥xn∥2∥1≤ε. \frac12\left\| \sigma_{\mathrm{out}} -\frac{\bm x_n\bm x_n^\dag}{\left\|\bm x_n\right\|^2} \right\|_1\le\varepsilon. Its query complexity is Q=O ⁣(snKrΓlog⁡32Γε)=O~ ⁣(snΓ(1−q)(1−q2))=O~ ⁣(snrξ(1−q)(1−q2)3/2(1−a2)1/2). Q=O\!\left( snK_r\Gamma\log\frac{32\Gamma}{\varepsilon} \right) =\widetilde O\!\left( \frac{sn\Gamma}{(1-q)(1-q^2)} \right) = \widetilde{O}\!\left(\frac{snr}{\xi(1-q)(1-q^2)^{3/2}(1-a^2)^{1/2}}\right). to the coefficient oracles and UbU_b, including controlled and inverse queries. The number of UxU_x queries is O(NQ)O(NQ), and is zero when u=0u=0.

The proof is provided in § 14.

The lower bound ξ\xi is an additional input promise. For fixed stability parameters and ξ\xi, the query bound is linear in nn. The output encodes the direction of xn\bm x_n. 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 ss to proportional to s\sqrt{s}.

Numerical Experiments

This section presents numerical evidence for the convergence of the truncated Carleman embedding.

We first consider the one-dimensional quadratic map

xn+1=0.1+0.4xn+0.5xn2,x0>0.\begin{equation} x_{n+1} = 0.1 + 0.4x_n + 0.5x_n^2, \qquad x_0 > 0. \tag*{(57)} \end{equation}

The map in (57) has two fixed points, x=0.2x=0.2 and x=1x=1. The fixed point x=0.2x=0.2 is stable, whereas x=1x=1 is unstable. In particular, for the initial conditions considered below, the iterates converge to x=0.2x=0.2 rather than x=1x=1.

In Figure 1, we consider

x0∈{0.25,  0.5,  0.75,  0.9}.x_0 \in \{0.25,\; 0.5,\; 0.75,\; 0.9\}.

Figure 1a shows that the Carleman truncation error decreases as the truncation level NN increases. The y-axis plots the maximum of absolute error over all iteration n≤100n\le 100. Moreover, Figure 1b shows that, at truncation level N=12N=12, the Carleman trajectories corresponding to these initial conditions approach the stable fixed point x=0.2x=0.2.

Figure 1, panel a

(a) Carleman truncation error versus truncation level NN.

Figure 1, panel b

(b) Trajectories from the finite Carleman system toward the fixed point with truncation level N=12N=12.

Figure 1. Numerical results for the discrete Carleman approximation.

We next consider a three-dimensional example from [11]. Its discrete iteration is

xn+1=(1−η)v+ηT(xn⊗xn),\begin{equation} \bm x_{n+1}=(1-\eta)\bm v+\eta T(\bm x_n\otimes\bm x_n), \tag*{(58)} \end{equation}

where

T=(0120120112120000012001201121121201201).T= \begin{pmatrix}0 & \frac 12 & 0 & \frac 12 & 0 & 1 & \frac 12 & \frac 12 & 0\\ 0 & 0 & 0 & 0 & \frac 12 & 0 & 0 & \frac 12 & 0\\ 1 & \frac 12 & 1 & \frac 12 & \frac 12 & 0 & \frac 12 & 0 & 1 \\ \end{pmatrix}.

We set η=0.2\eta=0.2 and v=13(111)T\bm v=\frac13\begin{pmatrix}1&1&1 \\ \end{pmatrix}^{T}, and initialize the iteration at x0=v\bm x_0=\bm v. These parameters satisfy Assumption 1. Figure 2 shows the Carleman truncation error for several truncation levels NN.

Writing (58) as xn+1=f+Bxn⊗2\bm x_{n+1}=\bm f+B\bm x_n^{\otimes 2}, we have f=(1−η)v\bm f=(1-\eta)\bm v, A=0A=0, and B=ηTB=\eta T. Because this map contains only constant and quadratic terms, odd input-degree blocks do not contribute to the Carleman update. Consequently, truncation at levels 2k2k and 2k+12k+1 gives the same physical-state approximation for every k≥1k\geq1. This explains why the error in Figure 2 decreases from odd to even NN, but remains unchanged from even to odd NN.

Figure 2

Figure 2. The Carleman truncation error versus truncation level NN.

Conclusion

We studied the Carleman embedding of forced quadratic discrete dynamical systems. Under explicit stability and initial-state assumptions, the degree-NN truncation approximates the original trajectory with an error that decreases geometrically in NN, 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 Θ(n)\Theta(n), 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 nnth iterate. Under the stated coherent-access assumptions and a positive lower bound on the norm of that iterate, the query complexity is linear in nn 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

h(s)≔c+αs+βs2.\begin{equation} h(s)\coloneqq c+\alpha s + \beta s^2. \tag*{(59)} \end{equation}

Under Assumption 1, we know Δ>0\Delta>0. Thus, to find the fixed point of hh, we have

h(s)=s⟹s=(1−α)±Δ2β=r±.h(s)=s\Longrightarrow s= \frac{(1-\alpha)\pm\sqrt{\Delta}}{2\beta} = r_{\pm}.

Here r−<r+r_-<r_+, ρ≔max⁡{∥x0∥,r−}\rho\coloneqq\max\{\left\|\bm x_0\right\|, r_-\}. R≔ρr+<1R\coloneqq\frac{\rho}{r_+}<1. By triangular inequality, we have

∥F(x)∥≤∥f∥+∥A∥∥x∥+∥B∥∥x∥2≤h(∥x∥).\left\|F(\bm x)\right\| \le \left\|\bm f\right\|+\left\|A\right\|\left\|\bm x\right\|+\left\|B\right\|\left\|\bm x\right\|^2 \le h(\left\|\bm x\right\|).

Note that h′(s)≥0h'(s)\ge0 for nonnegative ss, thus h(s)h(s) is increasing for s≥0s\ge0. Therefore, if ∥xn∥≤ρ\left\|\bm x_n\right\|\le \rho,

∥xn+1∥=∥F(xn)∥≤h(∥xn∥)≤h(ρ)≤ρ.\left\|\bm x_{n+1}\right\| =\left\|F(\bm x_n)\right\| \le h(\left\|\bm x_n\right\|)\le h(\rho)\le \rho.

The last inequality follows from r−≤ρ<r+r_-\le \rho <r_+. Since ∥x0∥≤ρ\left\|\bm x_0\right\|\le\rho, we conclude that ∥xn∥≤ρ\left\|\bm x_n\right\|\le\rho for all n∈N0n\in \mathbb{N}_0.

For any j∈Nj\in\mathbb{N}, let

h(s)j=∑k=02jmj,ksk,h(s)^j = \sum_{k=0}^{2j}m_{j,k}s^k,

for some coefficients mj,km_{j,k}. Since α\alpha and β\beta are upper norm bounds of AA and BB, ∥Lj,k∥≤mj,k\left\|L_{j,k}\right\|\le m_{j,k} for all j,kj,k. Thus,

∑k=02j∥Lj,kxn⊗k∥≤∑k=02j∥Lj,k∥∥xn⊗k∥≤∑k=02jmj,kr+k=h(r+)j=r+j.\sum_{k=0}^{2j}\left\|L_{j,k}\bm x_n^{\otimes k}\right\|\le \sum_{k=0}^{2j}\left\|L_{j,k}\right\|\left\|\bm x_n^{\otimes k}\right\|\le \sum_{k=0}^{2j} m_{j,k}r_+^k = h(r_+)^j = r_+^j.

Define

ηn,j=xn⊗j−yn,j,ηn,0=0,η0,j=0.\bm \eta_{n,j} = \bm x_n^{\otimes j} - \bm y_{n,j}, \qquad \bm \eta_{n,0}=0, \qquad \bm \eta_{0,j}=0.

Then for j>⌊N2⌋j>\lfloor \frac{N}{2}\rfloor,

ηn+1,j=xn+1⊗j−yn+1,j=∑k=0NLj,k(xn⊗k−yn,k)+∑k=N+12jLj,kxn⊗k=∑k=0NLj,kηn,k+∑k=N+12jLj,kxn⊗k.\bm \eta_{n+1,j} = \bm x_{n+1}^{\otimes j} - \bm y_{n+1,j} = \sum_{k=0}^N L_{j,k}(\bm x_n^{\otimes k }-\bm y_{n,k})+\sum_{k=N+1}^{2j}L_{j,k}\bm x_n^{\otimes k}= \sum_{k=0}^N L_{j,k}\bm \eta_{n,k}+\sum_{k=N+1}^{2j}L_{j,k}\bm x_n^{\otimes k}.

For j≤⌊N2⌋j\le \lfloor \frac{N}{2}\rfloor, one has

ηn+1,j=∑k=0NLj,kηn,k.\bm \eta_{n+1,j} = \sum_{k=0}^N L_{j,k}\bm \eta_{n,k}.

Define δ≔RN+1.\delta\coloneqq R^{N+1}. We assume that ∥ηn,j∥≤r+jδ\left\|\bm \eta_{n,j}\right\|\le r_+^{j}\delta for every j=1,⋯ ,Nj=1,\cdots,N as the induction hypothesis. When 2j≤N2j \le N, then

∥ηn+1,j∥≤∑k=12j∥Lj,k∥r+kδ≤δ∑k=12jmj,kr+k≤δh(r+)j=δr+j.\left\|\bm \eta_{n+1,j}\right\|\le \sum_{k=1}^{2j}\left\|L_{j,k}\right\|r_+^k\delta \le \delta \sum_{k=1}^{2j}m_{j,k}r_+^k \le \delta h(r_+)^j = \delta r_+^j.

For the case where 2j>N2j>N,

∥ηn+1,j∥≤∑k=1N∥Lj,k∥∥ηn,k∥+∑k=N+12j∥Lj,k∥∥xn⊗k∥≤δ∑k=12jmj,kr+k=δh(r+)j=δr+j.\left\|\bm \eta_{n+1,j}\right\|\le \sum_{k=1}^{N}\left\|L_{j,k}\right\|\left\|\bm \eta_{n,k}\right\|+\sum_{k=N+1}^{2j}\left\|L_{j,k}\right\|\left\|\bm x_n^{\otimes k}\right\| \le \delta \sum_{k=1}^{2j}m_{j,k}r_+^k = \delta h(r_+)^j = \delta r_+^j.

By induction, we know for every n∈N0n\in\mathbb{N}_0,

∥ηn,j∥≤r+jδ.\left\|\bm \eta_{n,j}\right\|\le r_+^{j}\delta.

Take j=1j=1, we obtain

∥ηn,1∥≤r+RN+1=ρRN.\left\|\bm \eta_{n,1}\right\|\le r_+ R^{N+1} = \rho R^N.

◻

Proof of Lemma 3.1

Proof. Fix an arbitrary y=(y0,⋯ ,yN)∈VN\bm y=\begin{pmatrix}\bm y_0, \cdots , \bm y_N \\ \end{pmatrix}\in\mathcal{V}_N, and let w\bm w be the unique solution of

(I−C†)w=Eouty.(I-C^\dag)\bm w=E_{\mathrm{out}}\bm y.

The block equations give

w(0)=y,w(ℓ)=Qℓ†w(ℓ−1),1≤ℓ≤N.\bm w^{(0)}=\bm y, \quad \bm w^{(\ell)}=Q_\ell^\dag\bm w^{(\ell-1)},\quad 1\le\ell\le N.

Using (28), this becomes

wp,ℓ=∑i∈{0,1,2}p+i≤N(IH⊗p⊗Fi⊗IH⊗(ℓ−1))wp+i,ℓ−1.\begin{equation} \bm w_{p,\ell} = \sum_{\substack{i\in\{0,1,2\}\\p+i\le N}} \left( I_{\mathcal{H}}^{\otimes p}\otimes F_i \otimes I_{\mathcal{H}}^{\otimes(\ell-1)} \right) \bm w_{p+i,\ell-1}. \tag*{(60)} \end{equation}

We claim that

wp,ℓ=∑i1,…,iℓ∈{0,1,2}p+i1+⋯+iℓ≤N(IH⊗p⊗Fi1⊗⋯⊗Fiℓ)yp+i1+⋯+iℓ.\begin{equation} \bm w_{p,\ell} = \sum_{\substack{i_1,\ldots,i_\ell\in\{0,1,2\}\\ p+i_1+\cdots+i_\ell\le N}} \left( I_{\mathcal{H}}^{\otimes p}\otimes F_{i_1}\otimes\cdots\otimes F_{i_\ell} \right) \bm y_{p+i_1+\cdots+i_\ell}. \tag*{(61)} \end{equation}

We prove (61) by induction on ℓ\ell, simultaneously for all p∈{0,…,N}p\in\{0,\ldots,N\}. For ℓ=0\ell=0, the empty tensor product is the identity, and also w(0)=y\bm w^{(0)} = \bm y, thus (61) holds for every pp. Now suppose (61) holds at layer ℓ−1\ell-1 as induction hypothesis for every pp. Substituting it into (60) yields

wp,ℓ=∑i1∈{0,1,2}p+i1≤N ∑i2,…,iℓ∈{0,1,2}p+i1+⋯+iℓ≤N(IH⊗p⊗Fi1⊗IH⊗(ℓ−1))(IH⊗(p+i1)⊗Fi2⊗⋯⊗Fiℓ)yp+i1+⋯+iℓ.\begin{aligned} \bm w_{p,\ell} =& \sum_{\substack{i_1\in\{0,1,2\}\\p+i_1\le N}} \ \sum_{\substack{i_2,\ldots,i_\ell\in\{0,1,2\}\\ p+i_1+\cdots+i_\ell\le N}} \\ &\quad \left( I_{\mathcal{H}}^{\otimes p}\otimes F_{i_1} \otimes I_{\mathcal{H}}^{\otimes(\ell-1)} \right) \left( I_{\mathcal{H}}^{\otimes(p+i_1)} \otimes F_{i_2}\otimes\cdots\otimes F_{i_\ell} \right) \bm y_{p+i_1+\cdots+i_\ell}. \end{aligned}

By Kronecker product properties,

(IH⊗p⊗Fi1⊗IH⊗(ℓ−1))(IH⊗(p+i1)⊗Fi2⊗⋯⊗Fiℓ)=IH⊗p⊗Fi1⊗Fi2⊗⋯⊗Fiℓ.\left( I_{\mathcal{H}}^{\otimes p}\otimes F_{i_1} \otimes I_{\mathcal{H}}^{\otimes(\ell-1)} \right) \left( I_{\mathcal{H}}^{\otimes(p+i_1)} \otimes F_{i_2}\otimes\cdots\otimes F_{i_\ell} \right) = I_{\mathcal{H}}^{\otimes p}\otimes F_{i_1}\otimes F_{i_2} \otimes \cdots\otimes F_{i_\ell}.

Furthermore, all iti_t are nonnegative, so

p+i1+⋯+iℓ≤N⟹p+i1≤N.p+i_1+\cdots+i_\ell\le N \quad\Longrightarrow\quad p+i_1\le N.

The outer cutoff is therefore redundant, and the resulting sum is exactly (61). This proves the claim by induction.

Taking p=0p=0 and ℓ=j≥1\ell=j\ge1, and grouping terms by k=i1+⋯+ijk=i_1+\cdots+i_j, gives

w0,j=∑k=0N(∑i1,…,ij∈{0,1,2}i1+⋯+ij=kFi1⊗⋯⊗Fij)yk=∑k=0NLj,kyk.\bm w_{0,j} = \sum_{k=0}^N \left( \sum_{\substack{i_1,\ldots,i_j\in\{0,1,2\} \\ i_1+\cdots+i_j=k}} F_{i_1}\otimes\cdots\otimes F_{i_j} \right)\bm y_k=\sum_{k=0}^NL_{j,k}\bm y_k.

Also, w0,0=y0w_{0,0}=\bm y_0. Thus

Ein⁡†w=LNy.E_{\operatorname{in}}^\dag\bm w=L_N\bm y.

Note that y\bm y is arbitrary, so LN=Ein⁡†(I−C†)−1Eout⁡L_N = E_{\operatorname{in}}^\dag (I-C^\dag)^{-1}E_{\operatorname{out}}. ◻

Proof of Lemma 3.2

Proof. Recall that F0=fF_0=\bm f, F1=AF_1=A, and F2=BF_2=B. The nonzero blocks of CC are

C(p+i,ℓ−1),(p,ℓ)=IH⊗p⊗Fi†⊗IH⊗(ℓ−1),C_{(p+i,\ell-1),(p,\ell)} = I_{\mathcal{H}}^{\otimes p}\otimes F_i^\dag \otimes I_{\mathcal{H}}^{\otimes(\ell-1)},

where i∈{0,1,2}i\in\{0,1,2\}, 1≤ℓ≤N1\le\ell\le N, and 0≤p≤p+i≤N0\le p\le p+i\le N.

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 i=0,1,2i=0,1,2 have row and column sparsity bounded by sf,sA,sBs_f,s_A,s_B, respectively. For i=0i=0, this follows because f†\bm f^\dag has at most sfs_f nonzero entries in total.

Fix a source sector (p,ℓ)(p,\ell). For each i∈{0,1,2}i\in\{0,1,2\}, there is at most one destination sector,

(p+i,ℓ−1).(p+i,\ell-1).

Hence each block column of CC contains at most one block of each type. Every scalar column of CC therefore has at most sf+sA+sBs_f+s_A+s_B nonzero entries.

Similarly, for a fixed destination sector (p′,ℓ′)(p',\ell') and a fixed ii, the only possible source sector is

(p′−i,ℓ′+1).(p'-i,\ell'+1).

Thus each block row of CC contains at most one block of each type, and every scalar row of CC has at most sf+sA+sBs_f+s_A+s_B nonzero entries.

The same row and column bounds hold for C†C^\dag. Since C†C^\dag changes the layer index, its diagonal is zero. Adding IKI_{\mathcal{K}} therefore contributes exactly one additional nonzero entry to each row and column, proving (31). ◻

Proof of Lemma 4.1

Proof. For i∈{0,1,2}i\in\{0,1,2\}, let C~i\widetilde C_i contain precisely the blocks of C~\widetilde C involving F~i†\widetilde F_i^\dag. By eq:sparse-Q,eq:sparse-C, these blocks are

(C~i)(p+i,ℓ−1),(p,ℓ)=IH⊗p⊗F~i†⊗IH⊗(ℓ−1),(\widetilde C_i)_{(p+i,\ell-1),(p,\ell)} = I_{\mathcal{H}}^{\otimes p}\otimes\widetilde F_i^\dag \otimes I_{\mathcal{H}}^{\otimes(\ell-1)},

where 1≤ℓ≤N1\le\ell\le N and 0≤p≤p+i≤N0\le p\le p+i\le N. For each fixed ii, distinct source sectors map to distinct destination sectors. Orthogonality of these sectors and multiplicativity of the operator norm under tensor products give

∥C~iv∥2≤∥F~i∥2∑1≤ℓ≤N0≤p≤p+i≤N∥vp,ℓ∥2≤∥F~i∥2∥v∥2.\left\|\widetilde C_i\bm v\right\|^2 \le \left\|\widetilde F_i\right\|^2 \sum_{\substack{1\le\ell\le N\\0\le p\le p+i\le N}} \left\|\bm v_{p,\ell}\right\|^2 \le \left\|\widetilde F_i\right\|^2\left\|\bm v\right\|^2.

Consequently, using (33),

∥C~∥≤∑i=02∥C~i∥≤∑i=02∥F~i∥≤cr+α+βr=q<1.\left\|\widetilde C\right\| \le\sum_{i=0}^2\left\|\widetilde C_i\right\| \le\sum_{i=0}^2\left\|\widetilde F_i\right\| \le\frac cr+\alpha+\beta r=q<1.

Since D~=IK−C~†\widetilde D=I_{\mathcal{K}}-\widetilde C^\dag, we obtain

∥D~∥≤1+q.\left\|\widetilde D\right\|\le1+q.

Moreover, C~N+1=0\widetilde C^{N+1}=0, so

D~−1=∑ℓ=0N(C~†)ℓ,∥D~−1∥≤∑ℓ=0Nqℓ≤11−q=δ.\widetilde D^{-1} =\sum_{\ell=0}^N(\widetilde C^\dag)^\ell, \qquad \left\|\widetilde D^{-1}\right\| \le\sum_{\ell=0}^Nq^\ell \le\frac1{1-q}=\delta.

Therefore,

κ(D~)=∥D~∥∥D~−1∥≤(1+q)δ.\kappa(\widetilde D) =\left\|\widetilde D\right\|\left\|\widetilde D^{-1}\right\| \le(1+q)\delta.

Next, Eout⁡E_{\operatorname{out}} is an isometry into layer zero, while C~†\widetilde C^\dag increases the layer index by one. Thus, for any v∈VN\bm v\in\mathcal{V}_N, the summands in

Jv=∑ℓ=0N(C~†)ℓEout⁡vJ\bm v =\sum_{\ell=0}^N (\widetilde C^\dag)^\ell E_{\operatorname{out}}\bm v

belong to mutually orthogonal layers. Hence

∥Jv∥2=∑ℓ=0N∥(C~†)ℓEout⁡v∥2≤∑ℓ=0Nq2ℓ∥v∥2≤∥v∥21−q2.\left\|J\bm v\right\|^2 =\sum_{\ell=0}^N \left\|(\widetilde C^\dag)^\ell E_{\operatorname{out}}\bm v\right\|^2 \le\sum_{\ell=0}^Nq^{2\ell}\left\|\bm v\right\|^2 \le\frac{\left\|\bm v\right\|^2}{1-q^2}.

Taking the supremum over unit vectors proves ∥J∥≤(1−q2)−1/2\left\|J\right\|\le (1-q^2)^{-1/2}, completing (38).

To prove (39), define

h~(s):=cr+αs+βrs2.\widetilde h(s) :=\frac cr+\alpha s+\beta r s^2.

Since r−≤ρ<r+r_-\le\rho<r_+ and a=ρ/ra=\rho/r,

h~(a)−a=c+αρ+βρ2−ρr=βr(ρ−r−)(ρ−r+)≤0.\widetilde h(a)-a =\frac{c+\alpha\rho+\beta\rho^2-\rho}{r} =\frac{\beta}{r}(\rho-r_-)(\rho-r_+) \le0.

For j≥1j\ge1, write

h~(s)j=∑k=02jm~j,ksk,m~j,k≥0.\widetilde h(s)^j =\sum_{k=0}^{2j}\widetilde m_{j,k}s^k, \qquad \widetilde m_{j,k}\ge0.

The tensor-product formula (4), applied to the rescaled coefficients, gives

∥L~j,k∥≤m~j,k.\left\|\widetilde L_{j,k}\right\| \le\widetilde m_{j,k}.

Here L~j,k\widetilde L_{j,k} denotes the corresponding rescaled Carleman block.

We prove ∥y~t,j∥≤aj\left\|\widetilde{\bm y}_{t,j}\right\|\le a^j by induction on tt, simultaneously for 1≤j≤N1\le j\le N. The initial condition in (34) gives

∥y~0,j∥=(∥x0∥r)j≤aj,\left\|\widetilde{\bm y}_{0,j}\right\| =\left(\frac{\left\|\bm x_0\right\|}r\right)^j \le a^j,

and the degree-zero coordinate remains equal to one. Assuming the bounds hold at time tt, we obtain

∥y~t+1,j∥≤∑k=0min⁡{N,2j}∥L~j,k∥∥y~t,k∥≤∑k=0min⁡{N,2j}m~j,kak≤h~(a)j≤aj.\left\|\widetilde{\bm y}_{t+1,j}\right\|\le \sum_{k=0}^{\min\{N,2j\}}\left\|\widetilde L_{j,k}\right\|\left\|\widetilde{\bm y}_{t,k}\right\|\le\sum_{k=0}^{\min\{N,2j\}}\widetilde m_{j,k}a^k\le \widetilde h(a)^j \le a^j.

The k=0k=0 term uses y~t,0=1\widetilde{\bm y}_{t,0}=1 and a0=1a^0=1. Thus the blockwise bound holds for every t≥0t\ge0. Orthogonality of the degree blocks now yields

∥y~t∥2=∑j=0N∥y~t,j∥2≤∑j=0Na2j≤11−a2.\left\|\widetilde{\bm y}_t\right\|^2 =\sum_{j=0}^N \left\|\widetilde{\bm y}_{t,j}\right\|^2 \le\sum_{j=0}^Na^{2j} \le\frac1{1-a^2}.

Combining this with ∥J∥≤g\left\|J\right\|\le g gives

∥Jy~t∥≤g∥y~t∥≤g1−a2=Mr,\left\|J\widetilde{\bm y}_t\right\| \le g\left\|\widetilde{\bm y}_t\right\| \le\frac{g}{\sqrt{1-a^2}}=M_r,

which proves (39).

Finally, we establish the uniform bound from (40). Since h~(1)=q<1\widetilde h(1)=q<1, any vector v=(v0,…,vN)∈VN\bm v=(\bm v_0,\ldots,\bm v_N)\in\mathcal{V}_N satisfying ∥vj∥≤b\left\|\bm v_j\right\|\le b for all jj obeys

∥(L~Nv)j∥≤b∑k=0min⁡{N,2j}m~j,k≤bqj≤b,1≤j≤N.\left\|(\widetilde L_N\bm v)_j\right\| \le b\sum_{k=0}^{\min\{N,2j\}} \widetilde m_{j,k} \le bq^j \le b, \qquad 1\le j\le N.

The degree-zero block is unchanged and also has norm at most bb. Starting with b=∥v∥b=\left\|\bm v\right\| and iterating this argument gives

∥(L~Nkv)j∥≤qj∥v∥,k≥1,0≤j≤N.\left\|(\widetilde L_N^k\bm v)_j\right\| \le q^j\left\|\bm v\right\|, \qquad k\ge1,\quad 0\le j\le N.

Therefore,

∥L~Nkv∥2≤∑j=0Nq2j∥v∥2≤g2∥v∥2.\left\|\widetilde L_N^k\bm v\right\|^2 \le\sum_{j=0}^Nq^{2j}\left\|\bm v\right\|^2 \le g^2\left\|\bm v\right\|^2.

Thus ∥L~Nk∥≤g\left\|\widetilde L_N^k\right\|\le g for every k≥1k\ge1, and the same bound holds for k=0k=0 because g≥1g\ge1. All bounds are uniform in NN. ◻

Proof of Lemma 4.2

Proof. Write M=dim⁡K=m2M=\dim\mathcal{K}=m^2. Substituting D~=IK−C~†\widetilde D=I_\mathcal{K}-\widetilde C^\dag gives

A~n=InM−Z,Z=In⊗C~†+Sn⊗P.\widetilde{\mathcal A}_n=I_{nM}-Z, \qquad Z=I_n\otimes\widetilde C^\dag+S_n\otimes P.

The first summand of ZZ has range in positive auxiliary layers, and the second has range in layer zero because P=Eout⁡Ein⁡†P=E_{\operatorname{out}}E_{\operatorname{in}}^\dag. These ranges are orthogonal. Since ∥Sn∥≤1\left\|S_n\right\|\le1 and ∥P∥=1\left\|P\right\|=1,

∥Zv∥2=∥(In⊗C~†)v∥2+∥(Sn⊗P)v∥2≤(q2+1)∥v∥2.\left\|Z\bm v\right\|^2 =\left\|(I_n\otimes\widetilde C^\dag)\bm v\right\|^2 +\left\|(S_n\otimes P)\bm v\right\|^2 \le(q^2+1)\left\|\bm v\right\|^2.

Thus ∥Z∥≤1+q2\left\|Z\right\|\le\sqrt{1+q^2}. Applying the triangle inequality to A~n=InM−Z\widetilde{\mathcal A}_n=I_{nM}-Z now gives

∥A~n∥≤∥InM∥+∥Z∥≤1+1+q2.\left\|\widetilde{\mathcal A}_n\right\| \le\left\|I_{nM}\right\|+\left\|Z\right\|\le1+\sqrt{1+q^2}.

Now we bound the inverse norm, ∥A~n−1∥\left\|\widetilde{\mathcal{A}}_n^{-1}\right\|. Set T=D~−1P=JEin⁡†T=\widetilde D^{-1}P=JE_{\operatorname{in}}^\dag. Then

A~n=(In⊗D~)(InM−Sn⊗T).\widetilde{\mathcal A}_n =(I_n\otimes\widetilde D)(I_{nM}-S_n\otimes T).

Since Snn=0S_n^n=0, the second factor has inverse ∑k=0n−1Snk⊗Tk\sum_{k=0}^{n-1}S_n^k\otimes T^k. Reversing the factors therefore yields

A~n−1=∑k=0n−1Snk⊗TkD~−1.\begin{equation} \widetilde{\mathcal A}_n^{-1} =\sum_{k=0}^{n-1}S_n^k\otimes T^k\widetilde D^{-1}. \tag*{(62)} \end{equation}

The recovery identity says Ein⁡†J=L~NE_{\operatorname{in}}^\dag J=\widetilde L_N. Starting with T=JEin⁡†T=JE_{\operatorname{in}}^\dag, induction gives

Tk+1=(JL~Nk−1Ein⁡†)(JEin⁡†)=JL~NkEin⁡†,Tk=JL~Nk−1Ein⁡†,for k≥1.T^{k+1} =(J\widetilde L_N^{k-1}E_{\operatorname{in}}^\dag)(JE_{\operatorname{in}}^\dag) =J\widetilde L_N^kE_{\operatorname{in}}^\dag, \qquad T^k=J\widetilde L_N^{k-1}E_{\operatorname{in}}^\dag, \quad\text{for }k\ge1.

Using Lemma 4.1 and ∥Ein⁡†∥=1\left\|E_{\operatorname{in}}^\dag\right\|=1, we obtain

∥TkD~−1∥≤∥J∥∥L~Nk−1∥∥Ein⁡†∥∥D~−1∥≤g2δ=Kr,for k≥1.\left\|T^k\widetilde D^{-1}\right\| \le\left\|J\right\|\left\|\widetilde L_N^{k-1}\right\| \left\|E_{\operatorname{in}}^\dag\right\|\left\|\widetilde D^{-1}\right\| \le g^2\delta=K_r,\quad\text{for }k\ge1.

For k=0k=0 the bound is δ\delta. Taking norms in (62) and using ∥Snk∥≤1\left\|S_n^k\right\|\le1 gives

∥A~n−1∥≤δ+(n−1)Kr=δ(1+(n−1)g2)≤nKr.\left\|\widetilde{\mathcal A}_n^{-1}\right\| \le\delta+(n-1)K_r =\delta\bigl(1+(n-1)g^2\bigr)\le nK_r.

Multiplying by the preceding norm bound proves the upper bound on κ(A~n)\kappa(\widetilde{\mathcal A}_n).

Let e\bm e be the unit vector in the scalar sector (p,ℓ)=(0,0)(p,\ell)=(0,0), and solve A~nv=(e,…,e)T\widetilde{\mathcal A}_n\bm v=(\bm e,\ldots,\bm e)^T. The scalar row of D~\widetilde D is the identity row, and (Pvt)0,0=(vt)0,0(P\bm v_t)_{0,0}=(\bm v_t)_{0,0}. The scalar equations are therefore

(v0)0,0=1,(vt)0,0−(vt−1)0,0=1,(\bm v_0)_{0,0}=1,\qquad (\bm v_t)_{0,0}-(\bm v_{t-1})_{0,0}=1,

so (vt)0,0=t+1(\bm v_t)_{0,0}=t+1 by induction. The squared norm of the right-hand side is nn, whereas ∥v∥2≥∑t=0n−1(t+1)2\left\|\bm v\right\|^2\ge\sum_{t=0}^{n-1}(t+1)^2. Consequently,

∥A~n−1∥≥1n∑t=0n−1(t+1)2=(n+1)(2n+1)6≥n3.\left\|\widetilde{\mathcal A}_n^{-1}\right\| \ge\sqrt{\frac1n\sum_{t=0}^{n-1}(t+1)^2} =\sqrt{\frac{(n+1)(2n+1)}6}\ge\frac n{\sqrt3}.

Every diagonal entry of A~n\widetilde{\mathcal A}_n is one, so ∥A~n∥≥1\left\|\widetilde{\mathcal A}_n\right\|\ge1. The definition of the condition number proves the lower bound. ◻

Proof of Lemma 4.4

Proof. The diagonal and subdiagonal parts of Bn\mathcal B_n have norms at most 1+q1+q and 11, respectively. Writing T=D~−1PT=\widetilde D^{-1}P, forward substitution shows that every nonzero block of Bn−1\mathcal B_n^{-1} is either TjD~−1T^j\widetilde D^{-1} or IKI_\mathcal{K}. The estimates in the proof of Lemma 4.2 bound these blocks by KrK_r. Their block row and column sums are at most 2nKr2nK_r, proving (53).

By Lemma 3.2 and the identity-copy construction, Bn\mathcal B_n has row and column sparsity at most ss. Its entries have magnitude at most one, and its sparse-access oracles require O(1)O(1) coefficient queries. The sparse block-encoding construction of [24] therefore encodes Bn/s\mathcal B_n/s. The Hermitian dilation

HB=1s(0BnBn†0)\begin{equation} H_{\mathcal B} =\frac1s \begin{pmatrix} 0&\mathcal B_n\\ \mathcal B_n^\dag&0 \end{pmatrix} \tag*{(63)} \end{equation}

satisfies

∥HB∥≤1,∥HB−1∥≤2snKr,HB−1(b0)=(0sΩ).\left\|H_{\mathcal B}\right\|\le1, \qquad \left\|H_{\mathcal B}^{-1}\right\|\le2snK_r, \qquad H_{\mathcal B}^{-1}\binom{\bm b}{0} =\binom{0}{s\bm\Omega}.

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 NN,

∥xn−yn,1∥≤ρRN≤εξ8,hn=∥yn,1∥r≥ξ2r.\left\|\bm x_n-\bm y_{n,1}\right\| \le\rho R^N\le\frac{\varepsilon\xi}{8}, \qquad h_n=\frac{\left\|\bm y_{n,1}\right\|}{r} \ge\frac{\xi}{2r}.

Thus (50) gives pout≥1/(2Γ2)p_{\mathrm{out}}\ge1/(2\Gamma^2). The inequality

∥u∥u∥−v∥v∥∥≤2∥u−v∥∥u∥\left\| \frac{\bm u}{\left\|\bm u\right\|} -\frac{\bm v}{\left\|\bm v\right\|} \right\| \le\frac{2\left\|\bm u-\bm v\right\|}{\left\|\bm u\right\|}

bounds the normalized truncation error by ε/4\varepsilon/4.

Apply Lemma 4.4 with η=ε/(32Γ)\eta=\varepsilon/(32\Gamma). Projection and normalization introduce error at most

2ηpout≤22 Γη<ε4.\frac{2\eta}{\sqrt{p_{\mathrm{out}}}} \le2\sqrt2\,\Gamma\eta<\frac{\varepsilon}{4}.

Moreover, the approximate projection succeeds with probability at least (pout−η)2≥pout/4(\sqrt{p_{\mathrm{out}}}-\eta)^2 \ge p_{\mathrm{out}}/4. Including the solver flag, the joint success probability is therefore Ω(Γ−2)\Omega(\Gamma^{-2}). Fixed-point amplitude amplification [25] raises it to at least 2/32/3 using O(Γ)O(\Gamma) coherent solver calls, proving (56).

By (51) and (36), the ideal projected physical state is yn,1/∥yn,1∥\bm y_{n,1}/\left\|\bm y_{n,1}\right\|. 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 ε/2\varepsilon/2, proving the claim. ◻

References

  1. [1]Sanavio, C., & Succi, S. (2024). Lattice Boltzmann--Carleman quantum algorithm and circuit for fluid flows at moderate Reynolds number. AVS Quantum Science, 6, 023802. https://doi.org/10.1116/5.0195549
  2. [2]Sanavio, C., Simon, W. A., Ralli, A., Love, P., & Succi, S. (2025). Carleman-lattice-Boltzmann quantum circuit with matrix access oracles. Physics of Fluids, 37, 037123. https://doi.org/10.1063/5.0254588
  3. [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. [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. [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. [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. [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. [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. [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. [10]Bravo-Prieto, C., Harrow, A. W., & Kothari, R. (2026). An Optimal Quantum Linear Systems Algorithm. https://arxiv.org/abs/2609.35660
  11. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [29]May, R. M. (1976). Simple mathematical models with very complicated dynamics. Nature, 261, 459–467. https://doi.org/10.1038/261459a0
  30. [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. [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. [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

Paper details

vlnc:W_e9pggef6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

LLM

View statement
Looking for related papers…
Contents