Time-marching based quantum solvers for time-dependent linear differential equations

Abstract

The time-marching strategy, which propagates the solution from one time step to the next, is a natural strategy for solving time-dependent differential equations on classical computers, as well as for solving the Hamiltonian simulation problem on quantum computers. For more general linear differential equations, a time-marching based quantum solver can suffer from exponentially vanishing success probability with respect to the number of time steps and is thus considered impractical. We solve this problem by repeatedly invoking a technique called the uniform singular value amplification, and the overall success probability can be lower bounded by a quantity that is independent of the number of time steps. The success probability can be further improved using a compression gadget lemma. This provides a path of designing quantum differential equation solvers that is alternative to those based on quantum linear systems algorithms (QLSA). We demonstrate the performance of the time-marching strategy with a high-order integrator based on the truncated Dyson series. The complexity of the algorithm depends linearly on the amplification ratio, which quantifies the deviation from a unitary dynamics. We prove that the linear dependence on the amplification ratio attains the query complexity lower bound and thus cannot be improved in the worst case. This algorithm also surpasses existing QLSA based solvers in three aspects: (1) the coefficient matrix $A(t)$ does not need to be diagonalizable. (2) $A(t)$ can be non-smooth, and is only of bounded variation. (3) It can use fewer queries to the initial state. Finally, we demonstrate the time-marching strategy with a first-order truncated Magnus series, while retaining the aforementioned benefits. Our analysis also raises some open questions concerning the differences between time-marching and QLSA based methods for solving differential equations.

arXiv comment45 pages, 6 figures

References in corpus (50)

• Quantum algorithm for solving linear systems of equations
• Strengths and Weaknesses of Quantum Computing
• Quantum Amplitude Amplification and Estimation
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Toward the first quantum simulation with quantum speedup
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• A Theory of Trotter Error
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A random compiler for fast Hamiltonian simulation
• Solving strongly correlated electron models on a quantum computer
• High-order quantum algorithm for solving linear differential equations
• Efficient quantum algorithm for dissipative nonlinear differential equations
• Exponential improvement in precision for simulating sparse Hamiltonians
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Nearly optimal lattice simulation by product formulas
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Faster quantum simulation by randomization
• Higher Order Decompositions of Ordered Operator Exponentials
• Quantum Algorithm for Simulating the Wave Equation
• Efficient phase-factor evaluation in quantum signal processing
• Quantum spectral methods for differential equations
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Koopman-von Neumann Approach to Quantum Simulation of Nonlinear Classical Dynamics
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Hamiltonian simulation in the low-energy subspace
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Concentration for random product formulas
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series
• On applications of quantum computing to plasma simulations
• On the energy landscape of symmetric quantum signal processing
• Hamiltonian Simulation in the Interaction Picture
• Hamiltonian Simulation by Uniform Spectral Amplification
• Black-box Hamiltonian simulation and unitary implementation
• Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Finding Angles for Quantum Signal Processing with Machine Precision
• Quantum algorithm for time-dependent Hamiltonian simulation by permutation expansion
• Stable factorization for phase factors of quantum signal processing
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Koopman wavefunctions and Clebsch variables in Vlasov-Maxwell kinetic theory
• Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation
• Quantum algorithm for matrix functions by Cauchy's integral formula

Cited by in corpus (27)

• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
• Quantum Algorithm for Solving the Advection Equation using Hamiltonian Simulation
• Quantum algorithm for time-dependent differential equations using Dyson series
• Compact quantum algorithms for time-dependent differential equations
• Quantum differential equation solvers: limitations and fast-forwarding
• Infinite quantum signal processing
• Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems
• Optimal Hamiltonian simulation for time-periodic systems
• Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Quantum Carleman linearisation efficiency in nonlinear fluid dynamics
• Design nearly optimal quantum algorithm for linear differential equations via Lindbladians
• Time-dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence
• Explicit block encodings of boundary value problems for many-body elliptic operators
• Quantum Algorithm for the Advection-Diffusion Equation by Direct Block Encoding of the Time-Marching Operator
• 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
• Encoding of linear kinetic plasma problems in quantum circuits via data compression
• Quantum algorithms for linear and non-linear fractional reaction-diffusion equations
• Quantum eigenvalue processing
• Unifying framework for quantum simulation algorithms for time-dependent Hamiltonian dynamics
• A Quantum-Inspired Algorithm for Wave Simulation Using Tensor Networks
• A time-marching quantum algorithm for simulation of the nonlinear Lorenz dynamics
• Quantum linear system algorithm with optimal queries to initial state preparation
• Spectral quantum algorithm for passive scalar transport in shear flows
• An efficient explicit implementation of a near-optimal quantum algorithm for simulating linear dissipative differential equations