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.
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.
This thesis describes quantum algorithms for Hamiltonian simulation, ordinary differential equations (ODEs), and partial differential equations (PDEs). Product formulas are used to simulate Hamiltonians which can be expressed as a sum of terms which can each be simulated individually. By simulating each of these terms in sequence, the net effect approximately simulates the total Hamiltonian. We find that the error of product formulas can be improved by randomizing over the order in which the Hamiltonian terms are simulated. We prove that this approach is asymptotically better than ordinary product formulas and present numerical comparisons for small numbers of qubits. The ODE algorithm applies to the initial value problem for time-independent first order linear ODEs. We approximate the propagator of the ODE by a truncated Taylor series, and we encode the initial value problem in a large linear system. We solve this linear system with a quantum linear system algorithm (QLSA) whose output we perform a post-selective measurement on. The resulting state encodes the solution to the initial value problem. We prove that our algorithm is asymptotically optimal with respect to several system parameters. The PDE algorithms apply the finite difference method (FDM) to Poisson's equation, the wave equation, and the Klein-Gordon equation. We use high order FDM approximations of the Laplacian operator to develop linear systems for Poisson's equation in cubic volumes under periodic, Neumann, and Dirichlet boundary conditions. Using QLSAs, we output states encoding solutions to Poisson's equation. We prove that our algorithm is exponentially faster with respect to the spatial dimension than analogous classical algorithms. We also consider how high order Laplacian approximations can be used for simulating the wave and Klein-Gordon equations. We consider under what conditions it suffices to use Hamiltonian simulation for time evolution, and we propose an algorithm for these cases that uses QLSAs for state preparation and post-processing.
In recent years, quantum linear system algorithms have been applied to partial differential equations (PDEs), particularly in high-dimensional settings, demonstrating an exponential speedup in dimension. Concurrently, randomized and quantum-inspired classical linear solvers have emerged, showing computational complexity comparable to their quantum counterparts in many application areas. In this paper, we investigate the applicability of these quantum-inspired classical algorithms to PDEs. We provide both upper and lower bounds on their computational complexity, proving that these methods cannot achieve exponential speedup in dimension for discretizations of high-dimensional Poisson problems. Our theoretical findings definitively demonstrate that quantum-inspired classical algorithms are not competitive with quantum algorithms for solving PDEs, confirming that quantum methods retain a significant advantage for high-dimensional problems.
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.
Abstract 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, in the sense of approximately computing the amount of heat in a given region. We find that, for spatial dimension d≥2 d≥2 , there is an at most quadratic quantum speedup in terms of the allowable error ϵ ϵ using an approach based on applying amplitude estimation to an accelerated classical random walk. However, an alternative approach based on a quantum algorithm for linear equations is never faster than the best classical algorithms.
Quantum computing has the potential to solve certain compute-intensive problems faster than classical computing by leveraging the quantum mechanical properties of superposition and entanglement. This capability can be particularly useful for solving Partial Differential Equations (PDEs), which are challenging to solve even for High-Performance Computing (HPC) systems, especially for multidimensional PDEs. This led researchers to investigate the usage of Quantum-Centric High-Performance Computing (QC-HPC) to solve multidimensional PDEs for various applications. However, the current quantum computing-based PDE-solvers, especially those based on Variational Quantum Algorithms (VQAs) suffer from limitations, such as low accuracy, long execution times, and limited scalability. In this work, we propose an innovative algorithm to solve multidimensional PDEs with two variants. The first variant uses Finite Difference Method (FDM), Classical-to-Quantum (C2Q) encoding, and numerical instantiation, whereas the second variant utilizes FDM, C2Q encoding, and Column-by-Column Decomposition (CCD). We evaluated the proposed algorithm using the Poisson equation as a case study and validated it through experiments conducted on noise-free and noisy simulators, as well as hardware emulators and real quantum hardware from IBM. Our results show higher accuracy, improved scalability, and faster execution times in comparison to variational-based PDE-solvers, demonstrating the advantage of our approach for solving multidimensional PDEs.
Quantum algorithms offer new avenues for solving partial differential equations (PDEs). While the potential for end-to-end quantum advantage is at present not well understood, recent literature presents explicit circuit constructions for solving certain classes of linear PDEs in the frequency domain and thus offers concrete examples to study. In this work, we develop end-to-end implementations of these quantum circuits compiled to machine-level instructions and benchmark them in both numerical simulations and IBMQ hardware experiments. We focus on the advection, wave, and Poisson equations and study quantum circuits that propagate the dynamics in frequency space via the quantum Fourier transform using approximate methods based on a first-order approximation which offer compact representations with uncontrollable approximation error, and polynomial approximation methods based on quantum signal processing (QSP) leading to deeper circuits with tunable algorithmic error. In addition, we experimentally demonstrate that the QSP-augmented algorithm can provide accurate solutions under realistic hardware constraints. Finally, we extend our method to address non-homogeneous Dirichlet boundary conditions and verify it numerically for a Poisson equation with source term obtained from high-fidelity physics simulations of a capacitively coupled plasma.