Two Quantum Algorithms for Nonlinear Reaction-Diffusion Equation using Chebyshev Approximation Method

• URL: http://arxiv.org/abs/2510.19855v1
• Date: Tue, 21 Oct 2025 19:14:23 GMT
• Title: Two Quantum Algorithms for Nonlinear Reaction-Diffusion Equation using Chebyshev Approximation Method
• Authors: Manish Kumar,
• Abstract summary: We present two new quantum algorithms for reaction-diffusion equations that employ the truncated Chebyshevpoly approximation.<n>We derive the sufficient conditions for the diagonalization of the Carleman embedding matrix.<n>The success of the diagonalization is based on a conjecture that a specific trigonometric equation has no integral solution.
• Score: 1.775629639045375
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We present two new quantum algorithms for reaction-diffusion equations that employ the truncated Chebyshev polynomial approximation. This method is employed to numerically solve the ordinary differential equation emerging from the linearization of the associated nonlinear differential equation. In the first algorithm, we use the matrix exponentiation method (Patel et al., 2018), while in the second algorithm, we repurpose the quantum spectral method (Childs et al., 2020). Our main technical contribution is to derive the sufficient conditions for the diagonalization of the Carleman embedding matrix, which is indispensable for designing both quantum algorithms. We supplement this with an efficient iterative algorithm to diagonalize the Carleman matrix. Our first algorithm has gate complexity of O(d$\cdot$log(d)+T$\cdot$polylog(T/$\varepsilon$)). Here $d$ is the size of the Carleman matrix, $T$ is the simulation time, and $\varepsilon$ is the approximation error. The second algorithm is polynomial in $log(d)$, $T$, and $log(1/\varepsilon)$ - the gate complexity scales as O(polylog(d)$\cdot$T$\cdot$polylog(T/$\varepsilon$)). In terms of $T$ and $\varepsilon$, this is comparable to the speedup gained by the current best known quantum algorithm for this problem, the truncated Taylor series method (Costa et.al., 2025). Our approach has two shortcomings. First, we have not provided an upper bound, in terms of d, on the condition number of the Carleman matrix. Second, the success of the diagonalization is based on a conjecture that a specific trigonometric equation has no integral solution. However, we provide strategies to mitigate these shortcomings in most practical cases.

Related papers

• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
  Gradient descent is one of the most basic algorithms for solving continuous optimization problems. We propose a quantum algorithm that returns an $varepsilon$-approximation of its gradient with query complexity $widetildeO (1/varepsilon)$. We also propose two quantum algorithms for Hessian estimation, aiming to improve quantum analogs of Newton's method.
  arXiv  Detail & Related papers  (2024-07-04T11:03:48Z)
• Quantum speedups for linear programming via interior point methods [1.8434042562191815]
  We describe a quantum algorithm for solving a linear program with $n$ inequality constraints on $d$ variables. Our algorithm speeds up the Newton step in the state-of-the-art interior point method of Lee and Sidford.
  arXiv  Detail & Related papers  (2023-11-06T16:00:07Z)
• Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging [8.990961435218544]
  We propose a first-order algorithm named $B$-sample dual averaging with the logarithmic barrier. For the Poisson inverse problem, our algorithm attains an $varepsilon$ solution in $smashtildeO(d3/varepsilon2)$ time. When computing the maximum-likelihood estimate for quantum state tomography, our algorithm yields an $varepsilon$-optimal solution in $smashtildeO(d3/varepsilon2)$ time.
  arXiv  Detail & Related papers  (2023-11-05T03:33:44Z)
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs [0.0]
  We develop a quantum linear solver algorithm based on adiabatic quantum computing.<n>The algorithm is improved to the optimal scaling $O(kappa/log$)$ - an exponential improvement in $epsilon$.<n>We introduce a cheaper randomized walk operator method replacing Hamiltonian simulation.
  arXiv  Detail & Related papers  (2023-05-19T00:07:32Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  We consider learning in an adversarial Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes. This paper provides two algorithms that improve the regret to $tildemathcal O(K2/3)$ in the same setting.
  arXiv  Detail & Related papers  (2023-01-30T14:37:21Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines. We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature. Our algorithm is significantly faster than prior algorithms.
  arXiv  Detail & Related papers  (2021-06-01T19:51:55Z)
• 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)
• Second-order Conditional Gradient Sliding [70.88478428882871]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm.<n>The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations.<n>It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52: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.