Efficient Quantum Hermite Transform

We present a new primitive for quantum algorithms that implements a discrete Hermite transform efficiently, in time that is polylogarithmic in the dimension and the inverse of the allowable error. This transform, which maps basis states to states whose amplitudes are proportional to the Hermite functions, can be interpreted as the Gaussian analogue of the Fourier transform. Our algorithm is based on a method to exponentially fast-forward the evolution of the quantum harmonic oscillator, giving a simulation algorithm with nearly optimal circuit complexity for a fundamental Hamiltonian more than four decades after Feynman posed the simulation of quantum physics as an application of quantum computers. We apply this Hermite transform to give examples of provable quantum query advantage in property testing and learning. In particular, we give algorithms whose complexity is independent of the number of variables to test the property of being close to a low-degree in the Hermite basis when inputs are sampled from the Gaussian distribution, and solve a Gaussian analogue of the Goldreich-Levin learning task, analogous to the Boolean function case. We also comment on other potential uses of this transform to simulating time dynamics of quantum systems in the continuum.