Exponential Quantum Speedup for Simulating Classical Lattice Dynamics

Simulating large-scale lattice dynamics remains a long-standing challenge in condensed matter and materials science, where mechanical and thermal behaviors arise from coupled vibrational modes. We introduce a quantum algorithm that reformulates general harmonic lattice dynamics as a time-dependent Schr\"odinger equation governed by a sparse, Hermitian Hamiltonian. This enables the use of Hamiltonian simulation techniques on quantum devices, offering exponential speedup in the number of atoms N. Our approach applies to arbitrary harmonic lattices with vector-valued dynamics. A key ingredient is a matrix-valued Fej\'er-Riesz factorization of the phonon dynamical matrix, which preserves translational symmetry and enables efficient assembly of the Hamiltonian operator. We demonstrate the method's applicability across a broad class of lattice models.