Exponential quantum speedup in simulating coupled classical oscillators *

We study the problem of simulating the time evolution of a system of 2 n classical coupled oscillators (e. g. , 2 n 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 $\mathcal{O}(n)$-qubit quantum state encode the momenta and displacements of the 2 n 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^{\Omega(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.

Authors

• Ryan Babbush
• Dominic W. Berry
• Robin Kothari
• Rolando D. Somma
• Nathan Wiebe

Keywords

• Computer science
• Quantum algorithm
• Quantum state
• Harmonic analysis
• Mathematical models
• Kinetic energy
• Springs
• Classical Oscillator
• Exponential Speedup
• Classification Algorithms
• Spring Constant
• Quantum Computing
• Coupled Oscillators
• Classical Computer
• Quantum Algorithms
• Total Energy
• Square Root
• Differential Equations
• Equations Of Motion
• Class Of Systems
• Simulated Algorithm
• Harmonic Oscillator
• Diagonal Entries
• Positive Semidefinite Matrix
• Phase Estimation
• Version Of Problem
• Quantum Circuit
• Rest Position
• Small Angle Approximation
• Single Oscillator
• Spring System
• Special Case Of Problem
• Hamiltonian Operator
• Off-diagonal Entries
• Direct Substitution
• BQP-complete
• harmonic oscillators