Time complexity analysis of quantum difference methods for linear high dimensional and multiscale partial differential equations

Abstract

We investigate time complexities of finite difference methods for solving the high-dimensional linear heat equation, the high-dimensional linear hyperbolic equation and the multiscale hyperbolic heat system with quantum algorithms (hence referred to as the "quantum difference methods"). For the heat and linear hyperbolic equations we study the impact of explicit and implicit time discretizations on quantum advantages over the classical difference method. For the multiscale problem, we find the time complexity of both the classical treatment and quantum treatment for the explicit scheme scales as $\mathcal{O}(1/\epsilon )$, where $\epsilon$ is the scaling parameter, while the scaling for the multiscale Asymptotic-Preserving (AP) schemes does not depend on $\epsilon$. This indicates that it is still of great importance to develop AP schemes for multiscale problems in quantum computing.

arXiv commentquantum difference methods

References in corpus (16)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithm for solving linear systems of equations
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• High-order quantum algorithm for solving linear differential equations
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Quantum algorithms and the finite element method
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Quantum algorithm and circuit design solving the Poisson equation
• High-precision quantum algorithms for partial differential equations
• Quantum Algorithm for Simulating the Wave Equation
• Quantum spectral methods for differential equations
• Quantum Circuit Design for Solving Linear Systems of Equations
• Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
• The power of one qumode for quantum computation
• Client-friendly continuous-variable blind and verifiable quantum computing

Cited by in corpus (8)

• Quantum simulation of partial differential equations via Schrodingerisation: technical details
• Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations
• Quantum Circuits for partial differential equations via Schrödingerisation
• Quantum algorithms for computing observables of nonlinear partial differential equations
• Simulation of linear non-Hermitian boundary-value problems with quantum singular value transformation
• Explicit block encodings of boundary value problems for many-body elliptic operators
• Quantum algorithms for solving a drift-diffusion equation: A complexity analysis
• Integrating Quantum Algorithms Into Classical Frameworks: A Predictor-corrector Approach Using HHL