Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations
arXiv:2209.08478 · doi:10.1016/j.jcp.2023.112149
Abstract
We construct quantum algorithms to compute the solution and/or physical observables of nonlinear ordinary differential equations (ODEs) and nonlinear Hamilton-Jacobi equations (HJE) via linear representations or exact mappings between nonlinear ODEs/HJE and linear partial differential equations (the Liouville equation and the Koopman-von Neumann equation). The connection between the linear representations and the original nonlinear system is established through the Dirac delta function or the level set mechanism. We compare the quantum linear systems algorithms based methods and the quantum simulation methods arising from different numerical approximations, including the finite difference discretisations and the Fourier spectral discretisations for the two different linear representations, with the result showing that the quantum simulation methods usually give the best performance in time complexity. We also propose the Schrödinger framework to solve the Liouville equation for the HJE with the Hamiltonian formulation of classical mechanics, since it can be recast as the semiclassical limit of the Wigner transform of the Schrödinger equation. Comparsion between the Schrödinger and the Liouville framework will also be made.
arXiv commentThis paper is published in Journal of Computational Physics, 487: 112149, 2023
References in corpus (25)
- 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
- Polynomial-time quantum algorithm for the simulation of chemical dynamics
- Preconditioned quantum linear system algorithm
- High-order quantum algorithm for solving linear differential equations
- Efficient quantum algorithm for dissipative nonlinear differential equations
- Quantum algorithm for linear differential equations with exponentially improved dependence on precision
- 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
- Koopman-von Neumann Approach to Quantum Simulation of Nonlinear Classical Dynamics
- Computing quantum dynamics in the semiclassical regime
- Quantum Algorithm for the Vlasov Equation
- On applications of quantum computing to plasma simulations
- Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms
- The power of one qumode for quantum computation
- On the Convergence of Time Splitting Methods for Quantum Dynamics in the Semiclassical Regime
- Time complexity analysis of quantum difference methods for linear high dimensional and multiscale partial differential equations
- On quantum algorithms for the Schrödinger equation in the semi-classical regime
- Client-friendly continuous-variable blind and verifiable quantum computing
- Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations
Cited by in corpus (21)
- Drug design on quantum computers
- Quantum simulation of partial differential equations via Schrodingerisation: technical details
- Quantum Cloud Computing: Trends and Challenges
- Quantum simulation of partial differential equations via Schrodingerisation
- Efficient quantum amplitude encoding of polynomial functions
- Nonlinear dynamics as a ground-state solution on quantum computers
- Analog quantum simulation of partial differential equations
- Quantum Circuits for partial differential equations via Schrödingerisation
- Quantum computing of reacting flows via Hamiltonian simulation
- Quantum algorithms for computing observables of nonlinear partial differential equations
- Efficient explicit gate construction of block-encoding for Hamiltonians needed for simulating partial differential equations
- Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling
- Quantum simulation for time-dependent Hamiltonians -- with applications to non-autonomous ordinary and partial differential equations
- Quantum algorithms for matrix geometric means
- Improved precision scaling for simulating coupled quantum-classical dynamics
- Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
- The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts
- Efficient explicit circuit for quantum state preparation of piecewise continuous functions
- Quantum circuits for partial differential equations in Fourier space
- Quantum Framework for Simulating Linear PDEs with Robin Boundary Conditions
- Nonlinear path-following via the asymptotic numerical method on a quantum processor