Efficient Quantum Algorithms for Nonlinear Stochastic Dynamical Systems
- URL: http://arxiv.org/abs/2303.02463v3
- Date: Sat, 29 Jul 2023 17:32:21 GMT
- Title: Efficient Quantum Algorithms for Nonlinear Stochastic Dynamical Systems
- Authors: Abeynaya Gnanasekaran, Amit Surana, Tuhin Sahai
- Abstract summary: We propose efficient quantum algorithms for solving nonlinear differential equations (SDE) via the associated Fokker-Planck equation (FPE)
We discretize the FPE in space and time using two well-known numerical schemes, namely Chang-Cooper and implicit finite difference.
We then compute the solution of the resulting system of linear equations using the quantum linear systems.
- Score: 2.707154152696381
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose efficient quantum algorithms for solving nonlinear
stochastic differential equations (SDE) via the associated Fokker-Planck
equation (FPE). We discretize the FPE in space and time using two well-known
numerical schemes, namely Chang-Cooper and implicit finite difference. We then
compute the solution of the resulting system of linear equations using the
quantum linear systems algorithm. We present detailed error and complexity
analyses for both these schemes and demonstrate that our proposed algorithms,
under certain conditions, provably compute the solution to the FPE within
prescribed $\epsilon$ error bounds with polynomial dependence on state
dimension $d$. Classical numerical methods scale exponentially with dimension,
thus, our approach, under the aforementioned conditions, provides an
\emph{exponential speed-up} over traditional approaches.
Related papers
- Quantum algorithm for partial differential equations of non-conservative systems with spatially varying parameters [1.7453899104963828]
Partial differential equations (PDEs) are crucial for modeling various physical phenomena such as heat transfer, fluid flow, and electromagnetic waves.
In computer-aided engineering (CAE), the ability to handle fine resolutions and large computational models is essential for improving product performance and reducing development costs.
We propose a quantum algorithm for solving second-order linear PDEs of non-conservative systems with spatially varying parameters.
arXiv Detail & Related papers (2024-07-06T09:23:04Z) - Solving Fractional Differential Equations on a Quantum Computer: A Variational Approach [0.1492582382799606]
We introduce an efficient variational hybrid quantum-classical algorithm designed for solving Caputo time-fractional partial differential equations.
Our results indicate that solution fidelity is insensitive to the fractional index and that gradient evaluation cost scales economically with the number of time steps.
arXiv Detail & Related papers (2024-06-13T02:27:16Z) - Solving Poisson Equations using Neural Walk-on-Spheres [80.1675792181381]
We propose Neural Walk-on-Spheres (NWoS), a novel neural PDE solver for the efficient solution of high-dimensional Poisson equations.
We demonstrate the superiority of NWoS in accuracy, speed, and computational costs.
arXiv Detail & Related papers (2024-06-05T17:59:22Z) - An Efficient Quantum Algorithm for Linear System Problem in Tensor Format [4.264200809234798]
We propose a quantum algorithm based on the recent advances on adiabatic-inspired QLSA.
We rigorously show that the total complexity of our implementation is polylogarithmic in the dimension.
arXiv Detail & Related papers (2024-03-28T20:37:32Z) - Quantum Variational Solving of Nonlinear and Multi-Dimensional Partial Differential Equations [1.2670268797931266]
A variational quantum algorithm for numerically solving partial differential equations was proposed by Lubasch et al.
We generalize the method to cover a broader class of nonlinear PDEs as well as multidimensional PDEs.
We show via numerical simulations that the algorithm can solve instances of the Single-Asset Black-Scholes equation.
arXiv Detail & Related papers (2023-11-02T18:29:31Z) - Correspondence between open bosonic systems and stochastic differential
equations [77.34726150561087]
We show that there can also be an exact correspondence at finite $n$ when the bosonic system is generalized to include interactions with the environment.
A particular system with the form of a discrete nonlinear Schr"odinger equation is analyzed in more detail.
arXiv Detail & Related papers (2023-02-03T19:17:37Z) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization.
We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance.
The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
arXiv Detail & Related papers (2021-06-24T16:39:31Z) - 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) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space.
We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
arXiv Detail & Related papers (2020-12-09T20:19:32Z) - Deep learning based numerical approximation algorithms for stochastic
partial differential equations and high-dimensional nonlinear filtering
problems [4.164845768197489]
In this article we introduce and study a deep learning based approximation algorithm for solutions of partial differential equations (SPDEs)
We employ a deep neural network for every realization of the driving noise process of the SPDE to approximate the solution process of the SPDE under consideration.
In each of these SPDEs the proposed approximation algorithm produces accurate results with short run times in up to 50 space dimensions.
arXiv Detail & Related papers (2020-12-02T13:25:35Z) - A Dynamical Systems Approach for Convergence of the Bayesian EM
Algorithm [59.99439951055238]
We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based.
The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM)
We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
arXiv Detail & Related papers (2020-06-23T01:34:18Z)
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.