Quantum algorithms for Hamiltonian simulation and linear differential equations more generally have provided promising exponential speed-ups over classical computers on a set of problems with high real-world interest. However, extending this to a nonlinear problem has proven challenging, with exponential lower bounds having been demonstrated for the time scaling. We provide a quantum algorithm matching these bounds. Specifically, we find that for a non-linear differential equation of the form d|u⟩dt=A|u⟩+B|u⟩⊗2 for evolution of time T , error tolerance ϵ and c dependent on the strength of the nonlinearity, the number of queries to the differential operators that approaches the scaling of the quantum lower bound of eo(T‖B‖) queries in the limit of strong non-linearity. Finally, we introduce a classical algorithm based on the Euler method allowing comparably scaling to the quantum algorithm in a restricted case, as well as a randomized classical algorithm based on path integration that acts as a true analogue to the quantum algorithm in that it scales comparably to the quantum algorithm in cases where sign problems are absent.
Quantum algorithms for Hamiltonian simulation and linear differential equations more generally have provided promising exponential speed-ups over classical computers on a set of problems with high real-world interest. However, extending this to a nonlinear problem has proven challenging, with exponential lower bounds having been demonstrated for the time scaling. We provide a quantum algorithm matching these bounds. Specifically, we find that for a non-linear differential equation of the form d|u⟩dt=A|u⟩+B|u⟩⊗2 for evolution of time T , error tolerance ϵ and c dependent on the strength of the nonlinearity, the number of queries to the differential operators that approaches the scaling of the quantum lower bound of eo(T‖B‖) queries in the limit of strong non-linearity. Finally, we introduce a classical algorithm based on the Euler method allowing comparably scaling to the quantum algorithm in a restricted case, as well as a randomized classical algorithm based on path integration that acts as a true analogue to the quantum algorithm in that it scales comparably to the quantum algorithm in cases where sign problems are absent.
We present an efficient, nearly optimal quantum algorithm for solving linear matrix differential equations, with applications to the simulation of open quantum systems and beyond. For unitary or dissipative dynamics, the algorithm computes an entry of the solution matrix with query complexity O(νLt/ε), where the constant ν depends on the problem parameters, L involves a time integral of upper bounds on the norms of evolution operators, and ε is the error. In particular, νL is linear in t for unitary dynamics and can be a constant for dissipative dynamics. Our result contrasts prior quantum approaches for differential equations that typically require exponential time for this problem due to the encoding in a quantum state, which can lead to exponentially small amplitudes. We demonstrate the utility of the algorithm through an end-to-end application, namely the simulation of dissipative dynamics for non-interacting fermions, which can be extended to other quantum and classical systems. We compare with classical algorithms and give evidence of polynomial quantum speedups for systems in a lattice, which become more pronounced for systems with long-range interactions and can be shown to be exponential in general. We also provide a lower bound of Ω(νLt/ε) for unitary or dissipative dynamics that proves our algorithm is optimal up to logarithmic factors.
Nonlinear stochastic differential equations (NSDEs) are a pillar of mathematical modeling for scientific and engineering applications. Accurate and efficient simulation of large-scale NSDEs is prohibitive on classical computers due to the large number of degrees of freedom, and it is challenging on quantum computers due to the linear and unitary nature of quantum mechanics. We develop a quantum algorithm to tackle nonlinear differential equations driven by the Ornstein-Uhlenbeck (OU) stochastic process. The query complexity of our algorithm scales logarithmically with the error tolerance and nearly quadratically with the simulation time. Our algorithmic framework comprises probabilistic Carleman linearization (PCL) to tackle nonlinearity coupled with stochasticity, and stochastic linear combination of Hamiltonian simulations (SLCHS) to simulate stochastic non-unitary dynamics. We obtain probabilistic exponential convergence for the Carleman linearization of Liu et al. [1], provided the NSDE is stable and reaches a steady state. We extend deterministic LCHS to stochastic linear differential equations, retaining near-optimal parameter scaling from An et al. [2] except for the nearly quadratic time scaling. This is achieved by using Monte Carlo integration for time discretization of both the stochastic inhomogeneous term in LCHS and the truncated Dyson series for each Hamiltonian simulation.
Nonlinear differential equations model diverse phenomena but are notoriously difficult to solve. While there has been extensive previous work on efficient quantum algorithms for linear differential equations, the linearity of quantum mechanics has limited analogous progress for the nonlinear case. Despite this obstacle, we develop a quantum algorithm for dissipative quadratic n-dimensional ordinary differential equations. Assuming [Formula: see text], where R is a parameter characterizing the ratio of the nonlinearity and forcing to the linear dissipation, this algorithm has complexity [Formula: see text], where T is the evolution time, ϵ is the allowed error, and q measures decay of the solution. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. While exponential decay precludes efficiency, driven equations can avoid this issue despite the presence of dissipation. Our algorithm uses the method of Carleman linearization, for which we give a convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for [Formula: see text] Finally, we discuss potential applications, showing that the [Formula: see text] condition can be satisfied in realistic epidemiological models and giving numerical evidence that the method may describe a model of fluid dynamics even for larger values of R.
Existing quantum algorithms for simulating dynamical systems -- from Hamiltonian simulation to linear and nonlinear differential equations solvers -- simulate Markovian dynamics, in which the system's future evolution depends solely on its current state. We turn our attention to developing quantum algorithms for non-Markovian dynamical systems where the system's future evolution depends on its past history and thus has memory. Specifically, we develop efficient algorithms for linear Volterra integro-differential equations (VIDEs) with a convolution memory kernel that output a quantum state encoding the state description over a time interval or at a particular time. Given efficient circuits for the problem inputs, our algorithms achieve an exponential speedup in system size over existing classical algorithms.
We develop an algorithm for general kernels assuming that M<1, where M characterizes the strength of the memory term relative to the dissipation of the Markovian part of the dynamics. We complement this with lower bounds for general-kernel VIDEs when M≥1, showing that the problem becomes intractable for a family of systems. However, by specializing to structured kernels which admit concise decompositions over exponentials, we develop efficient quantum algorithms even when M≥1 by converting the VIDE into a larger set of ODEs, a procedure which we call Markovianization. As an application of the overall framework, we discuss the Mori-Zwanzig formalism used in open quantum systems and fluid dynamics. Overall, our results expand the range of dynamical systems that quantum computers can simulate efficiently.
Abstract We introduce a family of identities that express general linear non-unitary evolution operators as a linear combination of unitary evolution operators, each solving a Hamiltonian simulation problem. This formulation can exponentially enhance the accuracy of the recently introduced linear combination of Hamiltonian simulation (LCHS) method [An, Liu, and Lin, Physical Review Letters, 2023]. For the first time, this approach enables quantum algorithms to solve linear differential equations with both optimal state preparation cost and near-optimal scaling in matrix queries on all parameters.
Stochastic nonlinear dynamics underlie many models in engineering and computational physics, yet accurate high-dimensional simulation remains challenging. We present a quantum algorithm for a broad class of N-dimensional stochastic differential equations with dissipation and quadratic drift. The algorithm applies to strongly nonlinear systems with all-to-all interactions, thereby extending the scope of previously known quantum algorithms that were limited to weak nonlinearity and sparse systems. For norm-preserving drifts, a condition satisfied by key fluid dynamics discretizations, our method approximates expectation values of low-order correlation functions with rigorous error bounds at a cost polynomial in log(N) and linear in the evolution time. Our main technical advance is a subroutine for simulating an auxiliary system of N interacting quantum harmonic oscillators with cost polylogarithmic in N. Finally, we formulate turbulence models, including Navier-Stokes and damped Euler equations, within this framework, opening a route to quantum simulation of strongly nonlinear SDEs governing turbulence and nonlinear wave dynamics.