Quantum differential equation solvers: limitations and fast-forwarding

Abstract

We study the limitations and fast-forwarding of quantum algorithms for linear ordinary differential equation (ODE) systems with a particular focus on non-quantum dynamics, where the coefficient matrix in the ODE is not anti-Hermitian or the ODE is inhomogeneous. On the one hand, for generic linear ODEs, by proving worst-case lower bounds, we show that quantum algorithms suffer from computational overheads due to two types of ``non-quantumness'': real part gap and non-normality of the coefficient matrix. We then show that homogeneous ODEs in the absence of both types of ``non-quantumness'' are equivalent to quantum dynamics, and reach the conclusion that quantum algorithms for quantum dynamics work best. To obtain these lower bounds, we propose a general framework for proving lower bounds on quantum algorithms that are amplifiers, meaning that they amplify the difference between a pair of input quantum states. On the other hand, we show how to fast-forward quantum algorithms for solving special classes of ODEs which leads to improved efficiency. More specifically, we obtain exponential improvements in both $T$ and the spectral norm of the coefficient matrix for inhomogeneous ODEs with efficiently implementable eigensystems, including various spatially discretized linear evolutionary partial differential equations. We give fast-forwarding algorithms that are conceptually different from existing ones in the sense that they neither require time discretization nor solving high-dimensional linear systems.

Published version with improved presentation

References in corpus (36)

• Quantum algorithm for solving linear systems of equations
• Hamiltonian Simulation by Qubitization
• 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
• On the relationship between continuous- and discrete-time quantum walk
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A random compiler for fast Hamiltonian simulation
• High-order quantum algorithm for solving linear differential equations
• Efficient quantum algorithm for dissipative nonlinear differential equations
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• 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
• Quantum Algorithm for Simulating the Wave Equation
• Quantum spectral methods for differential equations
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Improved quantum algorithms for linear and nonlinear differential equations
• Hamiltonian simulation in the low-energy subspace
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• Quantum SDP-Solvers: Better upper and lower bounds
• Concentration for random product formulas
• Quadratic speedup for spatial search by continuous-time quantum walk
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Time-marching based quantum solvers for time-dependent linear differential equations
• Fast-forwarding quantum evolution
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Optimal state discrimination and unstructured search in nonlinear quantum mechanics
• A lower bound on the probability of error in quantum state discrimination
• Quantum simulation of real-space dynamics
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Complexity of quantum state verification in the quantum linear systems problem

Cited by in corpus (6)

• Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling
• Design nearly optimal quantum algorithm for linear differential equations via Lindbladians
• Quantum algorithms for solving a drift-diffusion equation: A complexity analysis
• Quantum algorithms for linear and non-linear fractional reaction-diffusion equations
• Quantum Framework for Simulating Linear PDEs with Robin Boundary Conditions
• Solving the Nonlinear Vlasov Equation on a Quantum Computer