Ground and excited-state energies with analytic errors and short time evolution on a quantum computer

We propose a new eigenvalue problem to determine the frequencies of an autocorrelation function. In particular, we develop a rigorous approximation framework that enables precise frequency estimation from a finite number of signal samples. Our error bounds unveil a sharp accuracy transition governed by the observation time and spectral density of the signal. By combining our spectral method with a quantum subroutine for signal generation, we define quantum prolate diagonalization (QPD) — a hybrid classical-quantum algorithm. QPD simultaneously estimates ground and excited state energies within chemical accuracy at the Heisenberg limit.