@INPROCEEDINGS {BabbushFOCS23,
author = {R. Babbush and D. W. Berry and R. Kothari and R. D. Somma and N. Wiebe},
booktitle = {2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)},
title = {Exponential quantum speedup in simulating coupled classical oscillators*},
year = {2023},
volume = {},
issn = {},
pages = {405-414},
abstract = {We study the problem of simulating the time evolution of a system of 2n classical coupled oscillators (e.g., 2n 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 2n 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.},
keywords = {computer science;quantum algorithm;quantum state;harmonic analysis;mathematical models;kinetic energy;springs},
doi = {10.1109/FOCS57990.2023.00030},
url = {https://doi.ieeecomputersociety.org/10.1109/FOCS57990.2023.00030},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
month = {nov}
}