  We have recently seen the first plausible claims for quantum advantage using
sampling problems such as random circuit sampling and Gaussian boson sampling.
The obvious next step is to channel the potential quantum advantage to solving
practical applications rather than proof-of-principle experiments. Recently, a
quantum simulator, specifically a Gaussian boson sampler, has been proposed to
generate molecular vibronic spectra efficiently, which is an essential property
of molecules and an important tool for analyzing chemical components and
studying molecular structures. Computing molecular vibronic spectra has been a
challenging task, and its best-known classical algorithm scales combinatorially
in the system size. Thus, it is a candidate of tasks for which quantum devices
provide computational advantages. In this work, we propose a quantum-inspired
classical algorithm for molecular vibronic spectra for harmonic potential. We
first show that the molecular vibronic spectra problem corresponding to
Fock-state boson sampling can be efficiently solved using a classical algorithm
as accurately as running a boson sampler. In particular, we generalize
Gurvits's algorithm to approximate Fourier components of the spectra of
Fock-state boson sampling and prove using Parseval's relation that the error of
the spectra can be suppressed as long as that of the Fourier components are
small. We also show that the molecular vibronic spectra problems of Gaussian
boson sampling, which corresponds to the actual molecular vibronic spectra
problem in chemistry, can be exactly solved even without Gurvits-type
algorithms. Consequently, we demonstrate that those problems are not candidates
of quantum advantage. We then provide a more general molecular vibronic spectra
problem, which is also chemically well-motivated, for which we might be able to
take advantage of a boson sampler.
