Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation

• URL: http://arxiv.org/abs/2205.01141v2
• Date: Mon, 6 Nov 2023 19:16:11 GMT
• Title: Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation
• Authors: Dong An, Di Fang, Stephen Jordan, Jin-Peng Liu, Guang Hao Low, Jiasu Wang
• Abstract summary: We develop an efficient quantum algorithm based on [1] for a class of nonlinear partial differential equations (PDEs) We show how to estimate the mean square kinetic energy in the solution by postprocessing the quantum state that encodes it to extract derivative information. As applications, we consider the Fisher-KPP and Allen-Cahn equations, which have interpretations in classical physics.
• Score: 5.576305273694895
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Nonlinear differential equations exhibit rich phenomena in many fields but are notoriously challenging to solve. Recently, Liu et al. [1] demonstrated the first efficient quantum algorithm for dissipative quadratic differential equations under the condition $R < 1$, where $R$ measures the ratio of nonlinearity to dissipation using the $\ell_2$ norm. Here we develop an efficient quantum algorithm based on [1] for reaction-diffusion equations, a class of nonlinear partial differential equations (PDEs). To achieve this, we improve upon the Carleman linearization approach introduced in [1] to obtain a faster convergence rate under the condition $R_D < 1$, where $R_D$ measures the ratio of nonlinearity to dissipation using the $\ell_{\infty}$ norm. Since $R_D$ is independent of the number of spatial grid points $n$ while $R$ increases with $n$, the criterion $R_D<1$ is significantly milder than $R<1$ for high-dimensional systems and can stay convergent under grid refinement for approximating PDEs. As applications of our quantum algorithm we consider the Fisher-KPP and Allen-Cahn equations, which have interpretations in classical physics. In particular, we show how to estimate the mean square kinetic energy in the solution by postprocessing the quantum state that encodes it to extract derivative information.

Related papers

• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• A quantum central path algorithm for linear optimization [5.450016817940232]
  We propose a novel quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path. This approach yields an algorithm for solving linear optimization problems involving $m$ constraints and $n$ variables to $varepsilon$-optimality. In the standard gate model (i.e., without access to quantum RAM), our algorithm can obtain highly-precise solutions to LO problems using at most $$mathcalO left( sqrtm + n textsfnnz (A) fracR_1
  arXiv  Detail & Related papers  (2023-11-07T13:26:20Z)
• 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)
• 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)
• Alternatives to a nonhomogeneous partial differential equation quantum algorithm [52.77024349608834]
  We propose a quantum algorithm for solving nonhomogeneous linear partial differential equations of the form $Apsi(textbfr)=f(textbfr)$. These achievements enable easier experimental implementation of the quantum algorithm based on nowadays technology.
  arXiv  Detail & Related papers  (2022-05-11T14:29:39Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  gradient Langevin Dynamics is one of the most fundamental algorithms to solve non-eps optimization problems. In this paper, we show two variants of this kind, namely the Variance Reduced Langevin Dynamics and the Recursive Gradient Langevin Dynamics.
  arXiv  Detail & Related papers  (2022-03-30T11:39:00Z)
• 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)
• 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)
• 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)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions. In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
  arXiv  Detail & Related papers  (2020-02-10T23:23:04Z)
• Differentially Quantized Gradient Methods [53.3186247068836]
  We show that Differentially Quantized Gradient Descent (DQ-GD) attains a linear contraction factor of $maxsigma_mathrmGD, rhon 2-R$. No algorithm within a certain class can converge faster than $maxsigma_mathrmGD, 2-R$.
  arXiv  Detail & Related papers  (2020-02-06T20:40:53Z)

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.