Carleman linearization based efficient quantum algorithm for higher order polynomial differential equations

• URL: http://arxiv.org/abs/2212.10775v1
• Date: Wed, 21 Dec 2022 05:21:52 GMT
• Title: Carleman linearization based efficient quantum algorithm for higher order polynomial differential equations
• Authors: Amit Surana, Abeynaya Gnanasekaran and Tuhin Sahai
• Abstract summary: We present an efficient quantum algorithm to simulate nonlinear differential equations with vector fields of arbitrary degree on quantum platforms. Models of physical systems governed by ordinary differential equations (ODEs) or partial differential equation (PDEs) can be challenging to solve on classical computers.
• Score: 2.707154152696381
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present an efficient quantum algorithm to simulate nonlinear differential equations with polynomial vector fields of arbitrary degree on quantum platforms. Models of physical systems that are governed by ordinary differential equations (ODEs) or partial differential equation (PDEs) can be challenging to solve on classical computers due to high dimensionality, stiffness, nonlinearities, and sensitive dependence to initial conditions. For sparse $n$-dimensional linear ODEs, quantum algorithms have been developed which can produce a quantum state proportional to the solution in poly(log(nx)) time using the quantum linear systems algorithm (QLSA). Recently, this framework was extended to systems of nonlinear ODEs with quadratic polynomial vector fields by applying Carleman linearization that enables the embedding of the quadratic system into an approximate linear form. A detailed complexity analysis was conducted which showed significant computational advantage under certain conditions. We present an extension of this algorithm to deal with systems of nonlinear ODEs with $k$-th degree polynomial vector fields for arbitrary (finite) values of $k$. The steps involve: 1) mapping the $k$-th degree polynomial ODE to a higher dimensional quadratic polynomial ODE; 2) applying Carleman linearization to transform the quadratic ODE to an infinite-dimensional system of linear ODEs; 3) truncating and discretizing the linear ODE and solving using the forward Euler method and QLSA. Alternatively, one could apply Carleman linearization directly to the $k$-th degree polynomial ODE, resulting in a system of infinite-dimensional linear ODEs, and then apply step 3. This solution route can be computationally more efficient. We present detailed complexity analysis of the proposed algorithms, prove polynomial scaling of runtime on $k$ and demonstrate the framework on an example.

Related papers

• Variational Quantum Framework for Nonlinear PDE Constrained Optimization Using Carleman Linearization [0.8704964543257243]
  We present a novel variational quantum framework for nonlinear partial differential equation (PDE) constrained optimization problems. We use Carleman linearization (CL) to transform a system of ordinary differential equations into a system of infinite but linear system of ODE. We present detailed computational error and complexity analysis and prove that under suitable assumptions, our proposed framework can provide potential advantage over classical techniques.
  arXiv  Detail & Related papers  (2024-10-17T15:51:41Z)
• MultiSTOP: Solving Functional Equations with Reinforcement Learning [56.073581097785016]
  We develop MultiSTOP, a Reinforcement Learning framework for solving functional equations in physics. This new methodology produces actual numerical solutions instead of bounds on them.
  arXiv  Detail & Related papers  (2024-04-23T10:51:31Z)
• CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra [62.37017125812101]
  We propose a simple but general framework for large-scale linear algebra problems in machine learning, named CoLA. By combining a linear operator abstraction with compositional dispatch rules, CoLA automatically constructs memory and runtime efficient numerical algorithms. We showcase its efficacy across a broad range of applications, including partial differential equations, Gaussian processes, equivariant model construction, and unsupervised learning.
  arXiv  Detail & Related papers  (2023-09-06T14:59:38Z)
• Fast quantum algorithm for differential equations [0.5895819801677125]
  We present a quantum algorithm with numerical complexity that is polylogarithmic in $N$ but is independent of $kappa$ for a large class of PDEs. Our algorithm generates a quantum state that enables extracting features of the solution.
  arXiv  Detail & Related papers  (2023-06-20T18:01:07Z)
• Message Passing Neural PDE Solvers [60.77761603258397]
  We build a neural message passing solver, replacing allally designed components in the graph with backprop-optimized neural function approximators. We show that neural message passing solvers representationally contain some classical methods, such as finite differences, finite volumes, and WENO schemes. We validate our method on various fluid-like flow problems, demonstrating fast, stable, and accurate performance across different domain topologies, equation parameters, discretizations, etc., in 1D and 2D.
  arXiv  Detail & Related papers  (2022-02-07T17:47:46Z)
• Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations [0.25782420501870296]
  We propose a quantum algorithm for solving $n$-dimensional nonlinear dissipative ordinary differential equations (ODEs) Our algorithm provides exponential improvement over the best classical algorithms or previous quantum algorithms in $n$ or $epsilon$.
  arXiv  Detail & Related papers  (2021-11-15T01:34:43Z)
• QUBO formulations for numerical quantum computing [0.0]
  Harrow-Hassidim-Lloyd algorithm is a monumental quantum algorithm for solving linear systems on gate model quantum computers. We will find unconstrained binary optimization (QUBO) models for a vector x that satisfies Ax=b. We validate those QUBO models on the D-Wave system and discuss the results.
  arXiv  Detail & Related papers  (2021-06-21T02:49:59Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms [74.17312533172291]
  We describe a method for mapping any finite nonlinear dynamical system to an infinite linear dynamical system (embedding) We then explore an approach for approximating the resulting infinite linear system with finite linear systems (truncation)
  arXiv  Detail & Related papers  (2020-12-12T00:01:10Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Efficient quantum algorithm for dissipative nonlinear differential equations [1.1988695717766686]
  We develop a quantum algorithm for dissipative quadratic $n$-dimensional ordinary differential equations. Our algorithm has complexity $T2 qmathrmpoly(log T, log n, log 1/epsilon)/epsilon$, where $T$ is the evolution time, $epsilon$ is the allowed error, and $q$ measures decay of the solution.
  arXiv  Detail & Related papers  (2020-11-06T04:27:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.