arXiv:2610.27416
Quantum algorithm for high-dimensional nonlinear stochastic differential equations based on Carleman linearization
Koichi Miyamoto
Abstract
Addressing nonlinear numerical problems in quantum computing remains challenging, but several approaches, including Carleman linearization (CL), have been proposed to construct quantum algorithms for such problems. In this work, we develop a CL-based method for a high-dimensional nonlinear stochastic differential equation (SDE) $\mathrm{d} \mathbf{X}_t = \left(A(t) \mathbf{X}_t + F(t) \mathbf{X}_t^{\otimes s}\right) \mathrm{d} t + B(t) \mathrm{d} \mathbf{W}_t$ for an $\mathbb{R}^N$-valued random process $\mathbf{X}_t$, aiming at quantum speed-up with respect to the dimension $N$. We introduce auxiliary processes $\mathbf{Y}^j_t$ that approximate $\mathbf{X}_t^{\otimes j}$, derive a linearized system of SDEs for them, and obtain the linear ordinary differential equation (ODE) governing their expectations. We then apply a quantum ODE solver to it and, from the resulting quantum state, extract an estimate for the expectation of a linear function of $\mathbf{X}_t$ by overlap estimation. We show that, provided the nonlinear and noise terms in the SDE are sufficiently small relative to the linear term, the CL error decreases exponentially with the truncation order $J$ in CL, and we can estimate the target expectation with a ${\rm polylog}(N)$ number of queries to unitaries encoding coefficient matrices $A$, $F$, and $B$. Finally, we also run a numerical demonstration for an SDE related to Langevin dynamics, observing the exponential decay of the CL error as $J$ increases.
AI Summary
The paper asks whether Carleman linearization can yield quantum algorithms with polylogarithmic dimension dependence for nonlinear stochastic differential equations. It considers $\mathrm dX_t=(A(t)X_t+F(t)X_t^{\otimes s})\mathrm dt+B(t)\mathrm dW_t$, with $s\ge3$, additive noise, deterministic initial data, and a contractive linear part satisfying $\mu(A(t))\le-\eta<0$. The output is a classical estimate of $\mathbb E[\sum_{n,i}C_{n,i}X^i_{t_n}]$. The construction rescales $X$, introduces auxiliary tensor-power processes, and truncates their linear stochastic system at order $J$. Their expectations satisfy a closed linear ODE, which is handled using a quantum history-state solver followed by overlap estimation. Gaussian-process tail bounds and moment estimates establish a sufficient approximation guarantee with $J=O(\log(1/\epsilon))$, suppressing other parameter dependence. The conditions include $(J+\tfrac12+\tfrac1{2J})\gamma^2\sigma^2+\gamma^{1-s}\alpha_F<\eta$ and an additional small-nonlinearity condition proportional to $\eta e^{-\eta T}$. Given coefficient block-encodings and initial-data and observable state-preparation oracles, the stated query complexity is $\tilde O((\alpha_AT)^2\|C\|_{\mathrm F}\sigma\sqrt T/[c(1-c)^{9/2}\epsilon])$. Dimension dependence is polylogarithmic only when the remaining parameters permit it; notably, $\sigma$ bounds the nuclear norm of $B$ and can grow linearly with $N$. A classical two-dimensional Langevin example at $T=0.5$ shows exponentially decreasing truncation error, including outside the sufficient conditions, against a $10^7$-trajectory Monte Carlo reference. The method only estimates linear observables; preparing sample-path states and treating more general observables are left open because the auxiliary system has multiplicative noise.
ChatGPT was used for grammar checking and to provide assistance with proofs, all of which were independently verified by the author.
Central claim may not hold: The advertised polylog(N) query scaling requires additional control of parameters such as the nuclear-norm noise bound σ, which the paper acknowledges can grow linearly with N. The final expectation-estimation theorem omits two hypotheses required by the Carleman-error lemma invoked in its proof. The history-state construction undernormalizes its forcing vector by neglecting the time-index summations, yielding an impossible unitary output component even for constant scalar coefficients. Algorithm 1 omits the factor 1/γ needed to convert the rescaled expectation into the intended expectation, although its appendix proof includes that factor. The second-moment and truncation-error proofs use lifted noise matrices in the wrong multiplication order for Itô's formula, leaving the stated convergence guarantee unsupported.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 49 pages, 2 figure