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.