Efficiency in Measurement-Based Quantum Simulations of Nonlinear Dynamics

We present a quantum algorithm to solve initial-value nonlinear ordinary differential equations (ODEs). The algorithm relies on classical evaluation of a summation over sub-Hamiltonians, weighted by the expectation values of paired observables, obtained by repeated measurement of the solution state. Standard quantum Hamiltonian simulation bridges the short times between evaluation of new Hamiltonian matrices. This algorithm requires an ensemble of quantum states, where each step consumes a subset of quantum states, which are used for measurements and are discarded from further time advance. Having demonstrated that our algorithm is capable of solving nontrivial problems, in this work, we explore the question of efficiency: For what class of problems is the algorithm efficient? For a range of problem classes, we use classical simulations to estimate how algorithmic errors scale with simulation time. For problems where the algorithm is efficient, the scaling is polynomial, rather than exponential, indicating that more accurate results is attainable with a small increase of computational resources. We present potential physical systems for the problem classes, providing further analytical analysis.