Exponential quantum speedup in simulating coupled classical oscillators

We study the problem of simulating the time evolution of a system of 2ⁿ classical coupled oscillators (e.g., 2ⁿ balls connected by springs) on a quantum computer. We map Newton's equation for harmonic potentials to Schrödinger's equation, such that the amplitudes of an O(n)-qubit quantum state encode the momenta and displacements of the 2ⁿ classical oscillators. Given oracle access to the masses and spring constants, we describe a quantum algorithm with query and time complexity poly (n) that solves this problem when certain parameters are polynomially bounded and the initial state is easy to prepare. As an example application, we apply our quantum algorithm to efficiently estimate the normalized kinetic energy of an oscillator at any time. We then show that any classical algorithm solving the same problem must make 2^Ωn queries to the oracle and we also show that when the oracles are instantiated by poly (n)-size circuits, the problem is BQP-complete. Thus, our approach solves a potentially practical application with an exponential speedup over classical computers.