I will describe a quantum algorithm for simulating the classical dynamics of 2^n coupled oscillators (e.g., 2^n masses coupled by springs). The algorithm is based on a mapping between the Schr\"odinger equation and Newton's equations for harmonic potentials such that the amplitudes of the evolved quantum state encode the kinetic and potential energies of the classical oscillators. When individual masses and spring constants can be efficiently queried, and when the initial state can be efficiently prepared, the complexity of the quantum algorithm is polynomial in n, almost linear in the evolution time, and sublinear in the sparsity. As an example application, I will show how to use the quantum algorithm to efficiently estimate the kinetic energy of an oscillator at any time, for a specification of the problem that we prove is BQP-complete. A related result shows that our quantum algorithm can solve an oracular problem related to the dynamics of oscillators exponentially faster than classical computers in the oracle model. Thus, the quantum algorithm solves a potentially practical application with an exponential speedup over classical computers. Under similar conditions this approach can also efficiently simulate more general classical harmonic systems with 2^n modes. I will also discuss limitations of the quantum algorithm and its applications to some real-world problems with significant speedups.
Copyright. All Rights Reserved.