Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations

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.

This paper is published in Journal of Computational Physics, 487: 112149, 2023

References in corpus (4)

• Quantum algorithm for solving linear systems of equations
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Quantum algorithm and circuit design solving the Poisson equation
• Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations

Cited by in corpus (20)

• 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
• 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
• Improved precision scaling for simulating coupled quantum-classical dynamics
• Quantum algorithms for matrix geometric means
• 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