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.
In this paper, we present a quantum implicit-explicit (IMEX) scheme for multiscale ordinary and partial differential equations whose discretization parameters are independent of the scaling parameter
ε. A key ingredient of our approach is a continuous-time formulation of classical IMEX schemes, which decouples the evolution time of the quantum algorithm from the physical time of the differential equation and is therefore particularly useful in multiscale settings. Building on this idea, we employ the Schrödingerization framework [Phys. Rev. Lett. 133 (2024), 230602] to implement IMEX schemes on quantum computers. Compared to previous HHL type quantum AP scheme [J. Comput. Phys. 471 (2022), 111641], this new method requires narrower -- an extra logarithmic factor -- auxiliary register numerical examples on linear heat and multiscale telegraph equations demonstrate the independence in
ε of the method.
Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity p o l y ( 1 / ϵ ) , where ϵ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be p o l y ( d , log ( 1 / ϵ ) ) , where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.
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)-based block-encodings for the first-order derivative and Laplacian operators in the non-local
N=2n-dimensional SLAC representation. We use state-preparation techniques designed for smoothly decaying functions to prepare the dense
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). For a
d-dimensional PDE, after projection away from the nullspace, the resulting quantum linear-system algorithm has overall gate complexity
O(dn3α(k)log(1/ε)), where
α(k) is the subnormalisation factor of the order-
k SLAC block-encoding and
ε denotes the algorithmic approximation error.