Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach

• URL: http://arxiv.org/abs/2412.14868v2
• Date: Fri, 20 Dec 2024 03:59:58 GMT
• Title: Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach
• Authors: Shi Jin, Nana Liu, Wei Wei,
• Abstract summary: We propose quantum algorithms for linear differential equations. The gate complexity of our algorithms exhibits an $mathcalO(dlog(Nd))$ dependence on the dimensions. The algorithms are numerically verified for the Ornstein-Uhlenbeck processes, Brownian motions, and one-dimensional L'evy flights.
• Score: 29.662683446339194
• License:
• Abstract: Quantum computers are known for their potential to achieve up-to-exponential speedup compared to classical computers for certain problems. To exploit the advantages of quantum computers, we propose quantum algorithms for linear stochastic differential equations, utilizing the Schr\"odingerisation method for the corresponding approximate equation by treating the noise term as a (discrete-in-time) forcing term. Our algorithms are applicable to stochastic differential equations with both Gaussian noise and $\alpha$-stable L\'evy noise. The gate complexity of our algorithms exhibits an $\mathcal{O}(d\log(Nd))$ dependence on the dimensions $d$ and sample sizes $N$, where its corresponding classical counterpart requires nearly exponentially larger complexity in scenarios involving large sample sizes. In the Gaussian noise case, we show the strong convergence of first order in the mean square norm for the approximate equations. The algorithms are numerically verified for the Ornstein-Uhlenbeck processes, geometric Brownian motions, and one-dimensional L\'evy flights.

Related papers

• Classical Combinatorial Optimization Scaling for Random Ising Models on 2D Heavy-Hex Graphs [0.8192907805418583]
  Ising models on heavy-hex graphs are examined for their classical computational hardness via empirical time scaling. Because of the sparsity of these Ising models, the classical algorithms are able to find optimal solutions efficiently even for large instances.
  arXiv  Detail & Related papers  (2024-12-20T05:09:30Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
  We present a quantum algorithm for a non-linear differential equation of the form $fracd|urangledt. We also introduce a classical algorithm based on the Euler method allowing comparably scaling to the quantum algorithm in a restricted case.
  arXiv  Detail & Related papers  (2024-07-10T14:08:58Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Hybrid quantum-classical and quantum-inspired classical algorithms for solving banded circulant linear systems [0.8192907805418583]
  We present an efficient algorithm based on convex optimization of combinations of quantum states to solve for banded circulant linear systems. By decomposing banded circulant matrices into cyclic permutations, our approach produces approximate solutions to such systems with a combination of quantum states linear to $K$. We validate our methods with classical simulations and actual IBM quantum computer implementation, showcasing their applicability for solving physical problems such as heat transfer.
  arXiv  Detail & Related papers  (2023-09-20T16:27:16Z)
• Solving Systems of Linear Equations: HHL from a Tensor Networks Perspective [39.58317527488534]
  We present an algorithm for solving systems of linear equations based on the HHL algorithm with a novel qudits methodology. We perform a quantum-inspired version on tensor networks, taking advantage of their ability to perform non-unitary operations such as projection.
  arXiv  Detail & Related papers  (2023-09-11T08:18:41Z)
• 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)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Quantum vs. classical algorithms for solving the heat equation [0.04297070083645048]
  Quantum computers are predicted to outperform classical ones for solving partial differential equations, perhaps exponentially. Here we consider a prototypical PDE - the heat equation in a rectangular region - and compare in detail the complexities of ten classical and quantum algorithms for solving it.
  arXiv  Detail & Related papers  (2020-04-14T13:57:47Z)
• High-precision quantum algorithms for partial differential equations [1.4050836886292872]
  Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm. We develop quantum algorithms based on adaptive-order finite difference methods and spectral methods. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound.
  arXiv  Detail & Related papers  (2020-02-18T20:32:45Z)

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.