The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts
arXiv:2309.07881 · doi:10.22331/q-2024-12-10-1553
Abstract
How well can quantum computers simulate classical dynamical systems? There is increasing effort in developing quantum algorithms to efficiently simulate dynamics beyond Hamiltonian simulation, but so far exact resource estimates are not known. In this work, we provide two significant contributions. First, we give the first non-asymptotic computation of the cost of encoding the solution to general linear ordinary differential equations into quantum states -- either the solution at a final time, or an encoding of the whole history within a time interval. Second, we show that the stability properties of a large class of classical dynamics allow their fast-forwarding, making their quantum simulation much more time-efficient. From this point of view, quantum Hamiltonian dynamics is a boundary case that does not allow this form of stability-induced fast-forwarding. In particular, we find that the history state can always be output with complexity for any stable linear system. We present a range of asymptotic improvements over state-of-the-art in various regimes. We illustrate our results with a family of dynamics including linearized collisional plasma problems, coupled, damped, forced harmonic oscillators and dissipative nonlinear problems. In this case the scaling is quadratically improved, and leads to significant reductions in the query counts after inclusion of all relevant constant prefactors.
17+38 pages
References in corpus (27)
- Quantum algorithm for solving linear systems of equations
- Even more efficient quantum computations of chemistry through tensor hypercontraction
- High-order quantum algorithm for solving linear differential equations
- Efficient quantum algorithm for dissipative nonlinear differential equations
- Fixed-point quantum search with an optimal number of queries
- Quantum algorithm for linear differential equations with exponentially improved dependence on precision
- Quantum Algorithm for Simulating the Wave Equation
- Quantum spectral methods for differential equations
- Koopman-von Neumann Approach to Quantum Simulation of Nonlinear Classical Dynamics
- Improved quantum algorithms for linear and nonlinear differential equations
- Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
- Quadratic speedup for spatial search by continuous-time quantum walk
- Time-marching based quantum solvers for time-dependent linear differential equations
- Exponential quantum speedup in simulating coupled classical oscillators
- Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations
- Practical Quantum Computing: solving the wave equation using a quantum approach
- Block-encoding structured matrices for data input in quantum computing
- Lecture Notes on Quantum Algorithms for Scientific Computation
- Quantum algorithm for time-dependent differential equations using Dyson series
- On efficient quantum block encoding of pseudo-differential operators
- Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
- Challenges for quantum computation of nonlinear dynamical systems using linear representations
- A quantum algorithm for the linear Vlasov equation with collisions
- Fast quantum algorithm for differential equations
- Mixed Quantum-Semiclassical Simulation
- Quantum algorithms for linear and non-linear fractional reaction-diffusion equations
- Eigenpath traversal by Poisson-distributed phase randomisation