Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2306.11802 · Physical Review Research

Fast quantum algorithm for differential equations

Mohsen Bagherimehrab, Kouhei Nakaji, Nathan Wiebe, Gavin K. Brennen, Barry C. Sanders, Alán Aspuru-Guzik

Published Oct 19, 2026• 4 citations
arXivHTMLPDF

Abstract

Partial differential equations (PDEs) are ubiquitous in science and engineering. Prior quantum algorithms for solving the system of linear algebraic equations obtained from discretizing a PDE have a computational complexity that scales at least linearly with the condition number $κ$ of the matrices involved in the computation. For many practical applications, $κ$ scales polynomially with the size $N$ of the matrices, rendering a polynomial complexity in $N$ for these algorithms. Here we present a quantum algorithm with a complexity that is polylogarithmic in $N$ but is independent of $κ$ for a large class of PDEs. Our algorithm generates a quantum state from which features of the solution can be extracted. Central to our methodology is using a wavelet basis as an auxiliary system of coordinates in which the condition number of associated matrices becomes independent of $N$ by a simple diagonal preconditioner. We present numerical simulations showing the effect of the wavelet preconditioner for several differential equations. Our work could provide a practical way to boost the performance of quantum simulation algorithms where standard methods are used for discretization.

DOI
10.1103/2mlq-dbfg

Related papers

An efficient quantum algorithm for simulating polynomial differential equations

Amit Surana, Abeynaya Gnanasekaran, Tuhin Sahai

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.

arXiv:2212.10775•Dec 21, 2022•5 citations

Quantum algorithm for solving differential equations using SLAC derivatives

Rakshit M. Gharat, Gopikrishnan Muraleedharan, Dominic W. Berry +1 more

In numerical approaches to solving differential equations on a lattice, a representation of the derivative operator that correctly matches the continuum behaviour of functions of momentum up to the band limit must be non-local. We present the construction of efficient linear-combination-of-unitaries ($\mathrm{LCU}$)-based block-encodings for the first-order derivative and Laplacian operators in the non-local \(N=2^n\)-dimensional SLAC representation. We use state-preparation techniques designed for smoothly decaying functions to prepare the dense $\mathrm{LCU}$ amplitudes with high success probability and low gate cost. Furthermore, we demonstrate how Shannon wavelet transforms can be applied to these block-encodings to obtain multiscale representations of the SLAC derivative operators. We then show how to apply a diagonal preconditioner that reduces the condition number of these matrices in the multiscale wavelet basis to a small constant. This enables the solution of partial differential equations (PDEs) with SLAC-discretised derivative operators on a finite lattice using the quantum linear solving algorithm ($\mathrm{QLSA}$). For a $d$-dimensional PDE, after projection away from the nullspace, the resulting quantum linear-system algorithm has overall gate complexity ${O}(dn^3α^{(k)}\log(1/\varepsilon))$, where $α^{(k)}$ is the subnormalisation factor of the order-$k$ SLAC block-encoding and $\varepsilon$ denotes the algorithmic approximation error.

quant-pharXiv:2605.04861•May 7, 2026•0 citations

A fast quantum algorithm for solving partial differential equations

Azim Farghadan, Mohammad Mahdi Masteri Farahani, Mohsen Akbari

The numerical solution of partial differential equations (PDEs) is essential in computational physics. Over the past few decades, various quantum-based methods have been developed to formulate and solve PDEs. Solving PDEs incurs high-time complexity for high-dimensional real-world problems, and using traditional methods becomes practically inefficient. This paper presents a fast hybrid classical-quantum paradigm based on successive over-relaxation (SOR) to accelerate solving PDEs. Using the discretization method, this approach reduces the PDE solution to solving a system of linear equations, which is then addressed using the block SOR method. The block SOR method is employed to address qubit limitations, where the entire system of linear equations is decomposed into smaller subsystems. These subsystems are iteratively solved block-wise using Advantage quantum computers developed by D-Wave Systems, and the solutions are subsequently combined to obtain the overall solution. The performance of the proposed method is evaluated by solving the heat equation for a square plate with fixed boundary temperatures and comparing the results with the best existing method. Experimental results show that the proposed method can accelerate the solution of high-dimensional PDEs by using a limited number of qubits up to 2 times the existing method.

Scientific Reports•Feb 13, 2025•4 citations

Reduced basis algorithm for solving nonlinear differential equations on quantum computers

Monica Lăcătuş, Matthias Möller, Sauro Succi

As quantum computing moves toward scientific computing applications, nonlinear differential equations remain a central challenge since quantum evolution is intrinsically linear. In this work, we introduce a reduced basis algorithm (RBA) for polynomial nonlinear ordinary differential equations (ODEs) and spatially discretized partial differential equations (PDEs). After time discretization, the method composes the resulting polynomial update map over $m$ timesteps, identifies the reduced monomial basis appearing in this composed map, and constructs a linear RBA operator whose action recovers the exact $m$-timestep nonlinear dynamics. Thus, at the level of the chosen discrete update rule, the method introduces no additional approximation error beyond the time discretization error. The qubit number requirement is governed by the size of the reduced monomial basis. For an $n$-dimensional polynomial ODE system of degree $p>1$, the lifted register requires at most $q_m^{\mathrm{ODE}} = O(nm\log p)$ qubits in the full basis scenario. For PDEs discretized on $N^D$ grid points, a locality-based construction requires at most $q_m^{\mathrm{PDE}} = O(D\log N + n m^{D+1}\log p)$ qubits. Hence, the dependence on the grid size remains logarithmic, while the nonlinear overhead is controlled by local reduced basis size. The main computational burden is moved from the quantum computer to a classical preprocessing step, where the reduced monomial basis and RBA operator are constructed for the chosen timestep window. Through numerical tests on the Lorenz system and the one-dimensional Burgers equation, we verify that the RBA reproduces the corresponding discrete time nonlinear dynamics exactly, while exposing the trade-off between timestep composition, reduced basis growth, and locality.

math.NACross-listedarXiv:2606.13457•Jun 12, 2026•0 citations

Quantum Algorithms for Multiscale Partial Differential Equations

Junpeng Hu, Shi Jin, Lei Zhang

Abstract. Partial differential equation (PDE) models with multiple temporal/spatial scales are prevalent in several disciplines such as physics, engineering, and many others. These models are of great practical importance but notoriously difficult to solve due to prohibitively small mesh and time step sizes limited by the scaling parameter and CFL condition. Another challenge in scientific computing could come from curse-of-dimensionality. In this paper, we aim to provide a quantum algorithm, based on either direct approximations of the original PDEs or their homogenized models, for prototypical multiscale problems inPDEs, including elliptic, parabolic, and hyperbolic PDEs. To achieve this, we will lift these problems to higher dimensions and leverage the recently developed Schrödingerization based quantum simulation algorithms to efficiently reduce the computational cost of the resulting high-dimensional and multiscale problems. We will examine the error contributions arising from discretization, homogenization, and relaxation, and analyze and compare the complexities of these algorithms in order to identify the best algorithms in terms of complexities for different equations in different regimes.

arXiv:2304.06902•Multiscale Modeling and Simulation•Jul 30, 2024•6 citations

High-order quantum algorithm for solving linear differential equations

Dominic William Berry

Linear differential equations are ubiquitous in science and engineering. Quantum computers can simulate quantum systems, which are described by a restricted type of linear differential equations. Here we extend quantum simulation algorithms to general inhomogeneous sparse linear differential equations, which describe many classical physical systems. We examine the use of high-order methods to improve the efficiency. These provide scaling close to $Δt^2$ in the evolution time $Δt$. As with other algorithms of this type, the solution is encoded in amplitudes of the quantum state, and it is possible to extract global features of the solution.

arXiv:1010.2745•Journal of Physics A Mathematical and Theoretical•Feb 19, 2014•277 citations
Partial differential equations (PDEs) are ubiquitous in science and engineering. Prior quantum algorithms for solving the system of linear algebraic equations obtained from discretizing a PDE have a computational complexity that scales at least linearly with the condition number κκκ of the matrices involved in the computation. For many practical applications, κκκ scales polynomially with the size NNN of the matrices, rendering a polynomial complexity in NNN for these algorithms. Here we present a quantum algorithm with a complexity that is polylogarithmic in NNN but is independent of κκκ for a large class of PDEs. Our algorithm generates a quantum state from which features of the solution can be extracted. Central to our methodology is using a wavelet basis as an auxiliary system of coordinates in which the condition number of associated matrices becomes independent of NNN by a simple diagonal preconditioner. We present numerical simulations showing the effect of the wavelet preconditioner for several differential equations. Our work could provide a practical way to boost the performance of quantum simulation algorithms where standard methods are used for discretization.
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 nnn-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 kkk-th degree polynomial vector fields for arbitrary (finite) values of kkk. The steps involve: 1) mapping the kkk-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 kkk-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 kkk and demonstrate the framework on an example.
In numerical approaches to solving differential equations on a lattice, a representation of the derivative operator that correctly matches the continuum behaviour of functions of momentum up to the band limit must be non-local. We present the construction of efficient linear-combination-of-unitaries (LCU\mathrm{LCU}LCU)-based block-encodings for the first-order derivative and Laplacian operators in the non-local N=2nN=2^nN=2n-dimensional SLAC representation. We use state-preparation techniques designed for smoothly decaying functions to prepare the dense LCU\mathrm{LCU}LCU amplitudes with high success probability and low gate cost. Furthermore, we demonstrate how Shannon wavelet transforms can be applied to these block-encodings to obtain multiscale representations of the SLAC derivative operators. We then show how to apply a diagonal preconditioner that reduces the condition number of these matrices in the multiscale wavelet basis to a small constant. This enables the solution of partial differential equations (PDEs) with SLAC-discretised derivative operators on a finite lattice using the quantum linear solving algorithm (QLSA\mathrm{QLSA}QLSA). For a ddd-dimensional PDE, after projection away from the nullspace, the resulting quantum linear-system algorithm has overall gate complexity O(dn3α(k)log⁡(1/ε)){O}(dn^3α^{(k)}\log(1/\varepsilon))O(dn3α(k)log(1/ε)), where α(k)α^{(k)}α(k) is the subnormalisation factor of the order-kkk SLAC block-encoding and ε\varepsilonε denotes the algorithmic approximation error.
The numerical solution of partial differential equations (PDEs) is essential in computational physics. Over the past few decades, various quantum-based methods have been developed to formulate and solve PDEs. Solving PDEs incurs high-time complexity for high-dimensional real-world problems, and using traditional methods becomes practically inefficient. This paper presents a fast hybrid classical-quantum paradigm based on successive over-relaxation (SOR) to accelerate solving PDEs. Using the discretization method, this approach reduces the PDE solution to solving a system of linear equations, which is then addressed using the block SOR method. The block SOR method is employed to address qubit limitations, where the entire system of linear equations is decomposed into smaller subsystems. These subsystems are iteratively solved block-wise using Advantage quantum computers developed by D-Wave Systems, and the solutions are subsequently combined to obtain the overall solution. The performance of the proposed method is evaluated by solving the heat equation for a square plate with fixed boundary temperatures and comparing the results with the best existing method. Experimental results show that the proposed method can accelerate the solution of high-dimensional PDEs by using a limited number of qubits up to 2 times the existing method.
As quantum computing moves toward scientific computing applications, nonlinear differential equations remain a central challenge since quantum evolution is intrinsically linear. In this work, we introduce a reduced basis algorithm (RBA) for polynomial nonlinear ordinary differential equations (ODEs) and spatially discretized partial differential equations (PDEs). After time discretization, the method composes the resulting polynomial update map over mmm timesteps, identifies the reduced monomial basis appearing in this composed map, and constructs a linear RBA operator whose action recovers the exact mmm-timestep nonlinear dynamics. Thus, at the level of the chosen discrete update rule, the method introduces no additional approximation error beyond the time discretization error. The qubit number requirement is governed by the size of the reduced monomial basis. For an nnn-dimensional polynomial ODE system of degree p>1p>1p>1, the lifted register requires at most qmODE=O(nmlog⁡p)q_m^{\mathrm{ODE}} = O(nm\log p)qmODE​=O(nmlogp) qubits in the full basis scenario. For PDEs discretized on NDN^DND grid points, a locality-based construction requires at most qmPDE=O(Dlog⁡N+nmD+1log⁡p)q_m^{\mathrm{PDE}} = O(D\log N + n m^{D+1}\log p)qmPDE​=O(DlogN+nmD+1logp) qubits. Hence, the dependence on the grid size remains logarithmic, while the nonlinear overhead is controlled by local reduced basis size. The main computational burden is moved from the quantum computer to a classical preprocessing step, where the reduced monomial basis and RBA operator are constructed for the chosen timestep window. Through numerical tests on the Lorenz system and the one-dimensional Burgers equation, we verify that the RBA reproduces the corresponding discrete time nonlinear dynamics exactly, while exposing the trade-off between timestep composition, reduced basis growth, and locality.
Abstract. Partial differential equation (PDE) models with multiple temporal/spatial scales are prevalent in several disciplines such as physics, engineering, and many others. These models are of great practical importance but notoriously difficult to solve due to prohibitively small mesh and time step sizes limited by the scaling parameter and CFL condition. Another challenge in scientific computing could come from curse-of-dimensionality. In this paper, we aim to provide a quantum algorithm, based on either direct approximations of the original PDEs or their homogenized models, for prototypical multiscale problems inPDEs, including elliptic, parabolic, and hyperbolic PDEs. To achieve this, we will lift these problems to higher dimensions and leverage the recently developed Schrödingerization based quantum simulation algorithms to efficiently reduce the computational cost of the resulting high-dimensional and multiscale problems. We will examine the error contributions arising from discretization, homogenization, and relaxation, and analyze and compare the complexities of these algorithms in order to identify the best algorithms in terms of complexities for different equations in different regimes.
Linear differential equations are ubiquitous in science and engineering. Quantum computers can simulate quantum systems, which are described by a restricted type of linear differential equations. Here we extend quantum simulation algorithms to general inhomogeneous sparse linear differential equations, which describe many classical physical systems. We examine the use of high-order methods to improve the efficiency. These provide scaling close to Δt2Δt^2Δt2 in the evolution time ΔtΔtΔt. As with other algorithms of this type, the solution is encoded in amplitudes of the quantum state, and it is possible to extract global features of the solution.