Abstract
I'll describe a classical problem related to simulating the classical time dynamics of 2^n balls and springs that can be solved by quantum computers in poly(n) time (the problem is in BQP) and which also captures the power of quantum computing (the problem is BQP-complete). This yields a new problem of interest that can be solved by quantum computers. Conversely, we can design new quantum algorithms by only analyzing classical systems of balls and springs. This talk is based on the paper https://arxiv.org/abs/2303.13012, which is joint work with Ryan Babbush, Dominic W. Berry, Rolando D. Somma, and Nathan Wiebe.